Gelfond’s Problem

Let n = ∑_{i} d_{i}2^{i} be the binary expansion of n, so that each d_{i} is either 0 or 1. Then s(n) = ∑_{i} d_{i} is the sum of the binary digits of n. Since s(2n + 1) = s(2n) + 1, it follows that | ∑_{0≤n≤N}(−1)^{s(n)}| ≤ 1 for all N. Our object now is to show that ∑_{p≤x}(−1)^{s(p)} = o(π(x)). We begin with some basic observations of harmonic analysis, and then address the generating function of (−1)^{s(n)}.

Lemma 18.1 Let M and N be integers with N ≥ 2. Then there exist weights w(n) such that w(n) ≥ 1 for M + 1 ≤ n ≤ M + N, w(n) ≥ 0 for all other n, and

W (α) = ∑_{n=−∞}^{∞} w(n)e(nα)

has the properties that max_{α} |W (α)| = W (0) ≪ N and W (α) = 0 if ∥α∥ ≥ 1/N.

Suppose that M + 1 ≤ n ≤ M + N. Then

1 ≤ w(n) = ∫_{0}^{1} W (α)e(−nα) dα = ∫_{−1/N}^{1/N} W (α)e(−nα) dα ≤ \frac{2}{N} max_{α} |W (α)| .

Thus our bound for max |W (α)| is optimal, apart from constants. If sharp constants were required, then we would appeal to Theorem E.4, but for our present purposes we have no need for such sophistication.

Proof We recall that if f(x) = max(0, 1−|x|), then f̂(t) = (\frac{sin πt}{πt})^{2}. If N is even, put K = M +N/2. If N is odd, put K = M +(N +1)/2. Thus in either case, K is an integer. After several changes of variable we deduce that if g(x) = N max(0, 1 − N|x + α|)e(K(x + α)), then

ĝ(t) = (\frac{sin π(t − K)/N}{π(t − K)/N} )^{2}e(tα) .

By the Poisson summation formula in the form of Theorem D.3, we find that ∑_{n} g(n) = ∑_{k} ĝ(k). Thus

W (α) = \frac{π^{2}}{4} ∑_{n=−∞}^{∞} (\frac{sin π(n − K)/N}{π(n − K)/N} )^{2}e(nα) = \frac{π^{2}}{4} N max(0, 1 − N∥α∥)e(Kα)

has the required properties. □

Lemma 18.2 Let M be an integer, M ≥ 2, put f(x) = min(M, 1/∥x∥), and set

g(x) = ∑_{m=−M}^{M} f̂(m)(1 − |m|/M)e(mx) .

Then f̂(m) ≪ log M uniformly in m, and f(x) ≪ g(x) uniformly in x.

Proof For the first assertion we note that

|f̂(m)| ≤ ∫_{0}^{1} |f(x)| dx = 2 + 2 log M/2 ≪ log M .

For the second part, let

Δ_{M}(x) = \frac{1}{M} (\frac{sin πMx}{sin πx})^{2} = ∑_{m=−M}^{M}(1 − |m|/M)e(mx)

be Fejér’s kernel. Since Δ_{M}(x) is monotonically decreasing for 0 ≤ x ≤ 1/M, it follows that

∫_{0}^{1/(2M)} Δ_{M}(x) dx ≥ \frac{1}{2M} Δ_{M}(1/(2M)) = \frac{1}{2M^{2} sin^{2} π/(2M)} ≥ \frac{2}{π^{2}}

since sin δ ≤ δ. But f(x) is monotonically decreasing in the interval [−1/M, 1/2], so

g(x) = ∫_{0}^{1} Δ_{M}(u)f(x − u) du ≥ ∫_{0}^{1/(2M)} Δ_{M}(u)f(x − u) du
≥ f(x) ∫_{0}^{1/(2M)} Δ_{M}(u) du ≫ f(x) .

The bound therefore also holds for 1/2 ≤ x ≤ 1, since f and g are both even functions. □

The function (−1)^{s(n)} has a power series generating function

(18.xx+1)  P (z) = ∑_{n=0}^{∞}(−1)^{s(n)}z^{n} = ∏_{j=0}^{∞} (1 − z^{2^{j}})

for |z| < 1, but we find it easier to work on the circle with a truncated sum, so we set

(18.xx+2)  T_{J}(θ) = ∑_{0≤n<2^{J}}(−1)^{s(n)}e(nθ) = ∏_{j=0}^{J−1} (1 − e(2^{j}θ)) .

In order to derive an upper bound for max |T_{J}(θ)|, we show that |1−e(θ)| and |1−e(2θ)| cannot both be near 2 for the same θ.

Lemma 18.3 Let f(θ) = |1 − e(θ)||1 − e(2θ)|. Then

max_{θ} f(θ) = \frac{16}{3\sqrt{3}} .

Proof As f(θ) is an even function with period 1, we may restrict our attention to 0 ≤ θ ≤ 1/2. In this interval,

f(θ) = 4 sin πθ sin 2πθ .

Since f(0) = f(1/2) = 0, f attains its maximum at an interior critical point. But

f′(θ) = 4π cos πθ sin 2πθ + 8π sin πθ cos 2πθ = 8π sin πθ(3 cos^{2} πθ − 1) .

This vanishes at θ = 0, where the minimum is attained, and also when cos πθ = 1/\sqrt{3}. For this θ we have sin πθ = \sqrt{2/3} and sin 2πθ = 2\sqrt{2}/3, so the maximum value is 4\sqrt{2/3}2\sqrt{2}/3 = 16/(3\sqrt{3}). □

Lemma 18.4 Let α = 0.188722 … be determined by the equation 4^{α} = 3\sqrt{3}/4, and let T_{J}(θ) be defined as in (18.xx+2). Then

T_{J}(θ) ≪ 2^{(1−α)J}

uniformly in θ.

The bound T_{J}(θ) ≪ 2^{J} would be trivial, so α reflects the margin by which our bound is non-trivial.

Proof By lemma 18.3 we know that

|1 − e(2^{2j}θ)||1 − e(2^{2j+1}θ)| ≤ 2^{2(1−α)} .

We multiply these inequalities together for 0 ≤ j ≤ J/2 − 1. If J is odd, then there is one further factor, which we bound trivially: |1 − e(2^{J−1}θ)| ≤ 2. □

Since the functions log |1 − e(2^{j}θ)| move on widely different scales, we expect them to be nearly independent, and so we expect that log |T_{J}(θ)| should be distributed as if it were a sum of J independent random variables. As

(18.xx+3)  ∫_{0}^{1} log |1 − e(θ)| dθ = 0

and

(18.xx+4)  ∫_{0}^{1} ( log |1 − e(θ)|)^{2} dθ = \frac{π^{2}}{12} ,

we expect that

(18.xx+5)  exp ( − C\sqrt{J}) ≤ |T_{J}(θ)| ≤ exp (C\sqrt{J})

for most θ, if C is a large positive constant. On the other hand, by Parseval’s identity it is trivial that

(18.xx+6)  ∫_{0}^{1} |T_{J}(θ)|^{2} dθ = 2^{J},

which is to say that ∥T_{J}∥_{2} = 2^{J/2}. This is much larger than the order of magnitude in (18.xx+5), so we infer that the large value of the 2-norm is due to a small set of θ for which |T_{J}(θ)| is exceptionally large. If this is the case, then we would expect ∥T_{J}∥_{1} to be smaller than the root-mean-square, ∥T_{J}∥_{2}. The next lemma helps us to show that this is the case.

Lemma 18.5 Let g(θ) = sin πθ sin 2πθ, and put

h(θ) = |g(θ)| + |g(θ + 1/4)| + |g(θ + 1/2)| + |g(θ + 3/4)| .

Then

max_{θ} h(θ) = h(1/8) = \sqrt{2 + \sqrt{2}} .

Proof Clearly h(θ) has period 1/4. Since g(θ) is even, it follows that h(θ) is also even. Hence we may restrict our attention to 0 ≤ θ ≤ 1/8. In this interval, g(θ) ≥ 0, g(θ+1/4) ≥ 0, g(θ + 1/2) ≤ 0, and g(θ + 3/4) ≤ 0, so

h(θ) = \frac{1}{2}(2 − \sqrt{2}) sin^{2} πθ cos πθ + \frac{1}{2} sin πθ cos^{2} πθ − \frac{1}{4}\sqrt{2} cos^{3} πθ

(18.xx+7)  = \frac{1}{2}(1 + \sqrt{2}) cos πθ + \frac{1}{2} sin πθ + \frac{1}{2}(\sqrt{2} − 1) cos 3πθ + \frac{1}{2} sin 3πθ .

Consequently,

h′(θ) = − \frac{π}{2} (1 + \sqrt{2}) sin πθ + \frac{π}{2} cos πθ − \frac{3π}{2} (\sqrt{2} − 1) sin 3πθ + \frac{3π}{2} cos 3πθ,
h′′(θ) = − \frac{π^{2}}{2} (1 + \sqrt{2}) cos πθ − \frac{π^{2}}{2} sin πθ − \frac{9π^{2}}{2} (\sqrt{2} − 1) cos 3πθ − \frac{9π^{2}}{2} sin 3πθ .

In this last formula all terms are ≤ 0, so it is clear that h′′(θ) ≤ 0. But

h′(1/8) = − \frac{π}{2} (1 + \sqrt{2})\sqrt{\frac{1 − 1/\sqrt{2}}{2}} + \frac{π}{2} \sqrt{\frac{1 + 1/\sqrt{2}}{2}}

− \frac{3π}{2} (\sqrt{2} − 1)\sqrt{\frac{1 + 1/\sqrt{2}}{2}} + \frac{3π}{2} \sqrt{\frac{1 − 1/\sqrt{2}}{2}}

= \frac{π}{4} (2 − \sqrt{2})\sqrt{2 − \sqrt{2}} + \frac{π}{4} (4 − 3\sqrt{2})\sqrt{2 + \sqrt{2}}

because \sqrt{2 − \sqrt{2}} = (\sqrt{2} − 1)\sqrt{2 + \sqrt{2}} and (\sqrt{2} − 1)(2 − \sqrt{2}) = −(4 − 3\sqrt{2}). Hence the maximum is attained at θ = 1/8, and from (18.xx+7) we see that

h(1/8) = \frac{1}{2}(3 − \sqrt{2})\sqrt{\frac{1 + 1/\sqrt{2}}{2}} + \frac{1}{2}\sqrt{2}\sqrt{\frac{1 − 1/\sqrt{2}}{2}} = \sqrt{2 + \sqrt{2}} .

□

It is convenient to observe that

(18.xx+8)  T_{J}(θ) = T_{J−j}(θ)T_{j}(2^{J−j}θ) .

Lemma 18.6 Let β = 0.057111674 … be determined by the relation 4^{β} = 2/\sqrt{2 + \sqrt{2}}. Then

∑_{a=1}^{2^{J}} |T_{J}(θ + a/2^{J})| ≪ 2^{(3/2−β)J}

uniformly in θ.

By integrating this bound over 0 ≤ θ ≤ 1/2^{J}, it is immediate that

(18.xx+9)  ∫_{0}^{1} |T_{J}(θ)| dθ ≪ 2^{(1/2−β)J} .

Thus β reflects the margin by which we can say that ∥T_{J}∥_{1} is smaller than ∥T_{J}∥_{2}.

Proof Let S_{J}(θ) denote the sum to be bounded. By taking j = J − 2 in (18.xx+8), we find that

S_{J}(θ) = ∑_{a=1}^{2^{J}} |T_{2}(θ + a/2^{J})||T_{J−2}(4θ + a/2^{J−2})| .

Here the second factor has period 2^{J−2} with respect to a, so the above is

= 4 ∑_{a=1}^{2^{J−2}} |T_{J−2}(4θ + a/2^{J−2})|h(θ + a/2^{J})

in the notation of Lemma 18.5. Hence by that lemma it is immediate that

S_{J}(θ) ≤ 4\sqrt{2 + \sqrt{2}}S_{J−2}(4θ) .

We apply this K = [J/2] times to see that

S_{J}(θ) ≤ (4\sqrt{2 + \sqrt{2}})^{K}S_{J−2K}(2^{2K}θ) .

But S_{0}(θ) ≪ 1, S_{1}(θ) ≪ 1, and 2(2 + \sqrt{2})^{1/4} = 2^{3/2−β}, so we have the stated result. □

By applying (18.xx+8) and then Lemma 18.6 with J replaced by J − j, we deduce that

(18.xx+10)  ∑_{c=1}^{2^{J−j}} |T_{J}(θ + c/2^{J−j})| ≪ |T_{j}(2^{J−j}θ)|2^{(3/2−β)(J−j)} .

In Chapter 16 we saw that θ is irrational, then the numbers nθ are uniformly distributed modulo 1. In general, as we let n run from 1 to N, we expect that nθ will fall into a short interval I approximately the expected number of times. However, it can sometimes happen that a short interval is hit far more times than expected. We now show that this can only happen when θ has a rational approximation a/q that is exceptionally good, and with q unusually small.

Lemma 18.7 Let θ be a given real number. Suppose that δ_{1} ≤ δ_{2}/12, that N ≥ 3/δ_{2}, and that nθ ∈ I = [ϕ − δ_{1}, ϕ + δ_{1}] (mod 1) for at least δ_{2}N of the integers n ∈ [1, N]. Then there is an integer q with 1 ≤ q ≤ 9/δ_{2}, such that

(18.xx+11)  ∥qθ∥ ≤ \frac{3δ_{1}}{δ_{2}N}

By Dirichlet’s theorem we know that there is a q ≤ N such that ∥qθ∥ ≤ 1/N, but the q described above gives a better approximation, and is quite small as well.

Proof Among the positive integers q ≤ N, let q be the one for which ∥qθ∥ is minimal. For 0 ≤ n ≤ N, arrange the numbers {nθ} in increasing order, and consider the minimal gap between consecutive terms, say {n_{1}θ} ≤ {n_{2}θ}. Then ∥(n_{1} − n_{2})θ∥ is the length of this gap. But 0 < |n_{1} − n_{2}| ≤ N, and ∥qθ∥ is minimal, so we see that of all the gaps between the numbers {nθ}, the gap between {qθ} and 0 (or 1) is minimal. With nθ ∈ I for at least δ_{2}N values of N, we have ≥ δ_{2}N − 1 gaps, each of length at least ∥qθ∥. Hence ∥qθ∥(δ_{2}N − 1) ≤ 2δ_{1}. This implies (18.xx+11), since δ_{2}N ≥ 3.

We divide the interval [1, N] into ≤ N/q + 1 intervals of length ≤ q. For a given n_{0}, we consider those n, n_{0} ≤ n < n_{0} + q such that nθ ∈ I (mod 1). We put δ = θ − a/q, so that

nθ = n_{0}θ + (n − n_{0})a/q + (n − n_{0})δ .

By (18.xx+11) we know that |δ| ≤ 3δ_{1}/(δ_{2}qN). Hence |(n − n_{0})δ| ≤ 3δ_{1}/(δ_{2}N ≤ 1/(4N), since δ_{1} ≤ δ_{2}/12. Thus if nθ ∈ I, then (n − n_{0})a/q ∈ J = [ϕ − n_{0}θ − δ_{1} − 1/(4N), ϕ − n_{0}θ + δ + 1/(4N)]. Since the numbers (n − n_{0})a/q are in arithmetic progression with common difference 1/q, the number of n, n_{0} ≤ n < n_{0} + q, for which (n − n_{0})a/q ∈ J is ≤ 1+q(2δ_{1} +1/(2N)) ≤ 2δ_{1}q +3/2 since q ≤ N. Consequently, the total number of n ≤ N for which nθ ∈ I is

≤ (N/q + 1)(2δ_{1}q + 3/2) = 2δ_{1}N + 3N/(2q) + 2δ_{1}q + 3/2 .

Since q ≤ N, the first and third terms on the right hand side sum to ≤ 4δ_{1}N ≤ δ_{2}N/3. The last term is ≤ δ_{2}N/2, since N ≥ 3/δ_{2}. Since the number of n ≤ N for which nθ ∈ I is by hypothesis ≥ δ_{2}N, we conclude that

δ_{2}N ≤ \frac{5}{6}δ_{2}N + \frac{3N}{2q} ,

which implies that q ≤ 9/δ_{2}. □

18.2 Applications 7

Theorem 18.8 (Mauduit–Rivat) Let s(n) denote the sum of the binary digits of n. Then

∑_{n≤N}(−1)^{s(n)}Λ(n) ≪ N^{1−1/263} .

Proof For N ≥ 2 we set T (θ) = ∑_{n≤N}(−1)^{s(n)}e(nθ). If we choose J so that 2^{J−1} < N ≤ 2^{J}, then T is a truncation of the sum T_{J}, and hence by (E.13) and (E.14) we know that

(18.xx+12)  ∥T ∥_{∞} ≪ N^{1−α} log N

and that

(18.xx+13)  ∥T ∥_{1} ≪ N^{1/2−β} log N

where α and β are defined in Lemmas 18.4 and 18.6. We take f(n) = (−1)^{s(n)} in Vaughan’s identity in order to estimate S = ∑_{n≤N} f(n)Λ(n). Our treatment of the Type I sums is very simple:

∑_{\begin{matrix}n≤N \\ t|n \end{matrix}} f(n) = \frac{1}{t} ∑_{a=1}^{t} T (a/t) .

By the triangle inequality and (18.xx+12) it follows that

(18.xx+14)  ∑_{t≤U} | ∑_{r≤N/t} f(rt)| ≪ UN^{1−α} log N .

By a second appeal to (E.13) we see that

max_{w} | ∑_{w≤n≤N} f(n)e(nθ)| ≪ N^{1−α} log N

uniformly in θ. Hence by the same reasoning,

∑_{d≤V} max_{w≥1} | ∑_{w≤h≤N/d} f(dh)| ≪ V N^{1−α} log N .

Thus

(18.xx+15)  S_{3} ≪ V N^{1−α}(log N)^{2}

in the notation of (18.6). We write S_{2} = ∑_{t≤U} + ∑_{U<t≤UV} = S_{I} + S_{II}; then

(18.xx+16)  S_{I} ≪ UN^{1−α}(log NUV)^{2}

by (18.xx+14). We treat S_{II} and S_{4} as Type II sums, and for that we show that if |b_{m}| ≤ 1 for all m, |c_{k}| ≤ 1 for all k, and M ≤ K, then (18.xx+17)

∑_{\begin{matrix}M<m≤2M \\ K<k≤2K \\ mk≤N \end{matrix}} b_{m}c_{k}f(mk) ≪ K^{1+ε}M^{1−β/(3−4β)+ε} + K^{1−1/(10−8β)+ε}M^{1+(1−2β)/(10−8β)+ε} .

Here the second term is largest when M ≍ K ≍ N^{1/2}, at which point it is ≍ N^{1−β/(10−8β)}. Here β/(10 − 8β) = 0.00598 … > 1/200. The first term on the right above becomes larger as M becomes smaller (with K ≍ N/M), but we take U = V = N^{α(3−4β)/(3−3β)}, and note that then NU^{−β/(3−4β)} = UN^{1−α} = N^{1−αβ/(3−3β)}. Here αβ/(3 − 3β) = 0.0038104 > 1/263. To treat a block with M > K we simply reverse the roles of m and k. For S_{4} we take

b_{m} = μ(m), c_{k} = \frac{1}{log N} ∑_{\begin{matrix}d|k \\ d>V \end{matrix}} Λ(d)

or vice versa if M > K. Conditions such as m > U and k > V can be met by stipulating that b_{m} = 0 if m ≤ U and c_{k} = 0 if k ≤ V. To treat S_{II} we take

b_{m} = \{ \begin{matrix}b(m)/ log N & (m ≥ U), \\ 0 & (m < U), \end{matrix} c_{k} = \{ \begin{matrix}1 & (k ≤ UV), \\ 0 & (k > UV) \end{matrix}

or vice versa.

By Cauchy’s inequality, the left hand side of (18.xx+17) is

≤ M^{1/2}( ∑_{M<m≤2M} | ∑_{\begin{matrix}K<k≤2K \\ mk≤N \end{matrix}} c_{k}f(mk)|^{2})^{1/2} .

Thus to prove (18.xx+17), it suffices to show that

(18.xx+18) \begin{aligned}∑_{M<m≤2M} | ∑_{\begin{matrix}K<k≤2K \\ mk≤N \end{matrix}} c_{k}f(mk)|^{2} & ≪ K^{2+ε}M^{1−2β/(3−4β)+ε} \\ & + K^{2−1/(5−4β)+ε}M^{1+(1−2β)/(5−4β)+ε} . \end{aligned}

By van der Corput’s lemma (Lemma 17.6) we see that

| ∑_{\begin{matrix}K<k≤2K \\ mk≤N \end{matrix}} c_{k}f(mk)|^{2} ≤ \frac{K + H − 1}{H} ∑_{\begin{matrix}K<k≤2K \\ mk≤N \end{matrix}} |c_{k}f(mk)|^{2}

+ 2ℜ\frac{K + H − 1}{H} ∑_{h=1}^{H}(1 − h/H) ∑_{\begin{matrix}K<k≤2K−h \\ m(k+h)≤N \end{matrix}}c_{k+h}\overline{c_{k}}f(m(k + h))f(mk) .

Here H is a parameter to be chosen later, subject to H ≤ K. The first term on the right hand side above is ≪ K^{2}/H. We sum the above over m to see that the left hand side of (18.xx+18) is

(18.xx+19)  ≪ \frac{K^{2}M}{H} + \frac{K}{H} ∑_{h=1}^{H} ∑_{K<k≤2K} | ∑_{\begin{matrix}M<m≤2M \\ m(k+h)≤N \end{matrix}} f(m(k + h))f(mk)| .

Let n = ∑_{j} d_{j}2^{j} be the binary expansion of n. We divide 2^{J} into n, so that n = q2^{J} + r. Then r = ∑_{j<J} d_{j}2^{j} and s(n) = s(q) + s(r). Put s_{J}(n) = ∑_{j<J} d_{j} = s(r) = s(n) − s(q). Thus if q2^{J} ≤ m, n < (q + 1)2^{J}, then s(m) − s_{J}(m) = s(q) = s(n) − s_{J}(n). Put f_{J}(n) = (−1)^{s_{J} (n)}. Then f(m(k + h))f(mk) = f_{J}(m(k + h))f_{J}(mk) unless there is a multiple of 2^{J} between mk and m(k + h). We choose J so that 2^{J} is large compared with MH, but small compared with MK. Suppose that mk < q2^{J} ≤ m(k + h). Then {mk/2^{J}} ≥ 1 − mh/2^{J} ≥ 1 − 2MH/2^{J}. Thus

(18.xx+20)  \begin{aligned}∑_{\begin{matrix}M<m≤2M \\ m(k+h)≤N \end{matrix}} f(mk)f(m(k + h)) & = ∑_{\begin{matrix}M<m≤2M \\ m(k+h)≤N \end{matrix}} f_{J}(mk)f_{J}(m(k + h)) \\ & + O( ∑_{\begin{matrix}M<m≤2M \\ \{mk/2^{J} \}≥1−2MH/2^{J} \end{matrix}} 1) . \end{aligned}

We group pairs m, k according to the value of mk to see that

\frac{K}{H} ∑_{h=1}^{H} ∑_{K<k≤2K} ∑_{\begin{matrix}M<m≤2M \\ \{mk/2^{J} \}≥1−2MH/2^{J} \end{matrix}} 1 ≪ K^{1+ε}M^{ε} ∑_{\begin{matrix}n≤4MK \\ \{n/2^{J} \}≥1−2MH/2^{J} \end{matrix}} 1

since d(n) ≪ (MK)^{ε}. We divide the interval 0 < n ≤ 4MK into ≪ MK/2^{J} intervals of length 2^{J}. For n in an interval of length 2^{J}, the inequality {n/2^{J}} ≥ 1 − 4MH/2^{J} holds for ≪ MH values of n. Hence the above is

(18.xx+21)  ≪ (KM)^{2+ε}H/2^{J} .

The function f_{J} is periodic with period 2^{J}, and so has a finite Fourier transform,

f̂_{J}(a) = \frac{1}{2^{J}} ∑_{n=1}^{2^{J}} f_{J}(n)e(−an/2^{J}) = \frac{1}{2^{J}} T_{J}(−a/2^{J}),

so that

f_{J}(n) = ∑_{a=1}^{2^{J}} f̂_{J}(a)e(an/2^{J}) .

Thus the first term on the right hand side of (18.20) is

∑_{a=1}^{2^{J}} ∑_{b=1}^{2^{J}}f̂_{J}(a)f̂_{J}(b) ∑_{\begin{matrix}M<m≤2M \\ m(k+h)≤N \end{matrix}} e((am(k + h) + bmk)/2^{J})

≪ ∑_{a=1}^{2^{J}} ∑_{b=1}^{2^{J}} |f̂_{J}(a)f̂_{J}(b)| min(M, 1/∥(am(k + h) + bmk)/2^{J}∥)

by (16.5). To (18.xx+19) this contributes an amount

≪ \frac{K}{H} ∑_{h=1}^{H} ∑_{K<k≤2K} ∑_{a=1}^{2^{J}} ∑_{b=1}^{2^{J}} |f̂_{J}(a)f̂_{J}(b)| min(M, 1/∥(am(k + h) + bmk)/2^{J}∥) .

Our estimate for this depends on the power of 2 dividing a + b. Write a + b = c2^{j} with c odd. We may assume that a and b are odd, since f̂_{J}(a) = 0 if a is even. Thus 1 ≤ j ≤ J, and the above is (18.xx+22)

≪ \frac{K}{H} ∑_{a=1}^{2^{J}} ∑_{j=1}^{J} ∑_{\begin{matrix}c=1 \\ 2∤c \end{matrix}}^{2^{J−j}} |f̂_{J}(a)f̂_{J}(c2^{j} − a)| ∑_{h=1}^{H} ∑_{K<k≤2K} min(M, 1/∥ck/2^{J−j} + ah/2^{J}∥) .

Let w_{1}(h) be weights that arise when Lemma 18.1 is applied to the interval [1, H], and let w_{2}(k) denote the weights when Lemma 18.1 is applied to the interval [K, 2K]. Then

∑_{h=1}^{H} ∑_{K<k≤2K} min(M,1/∥ck/2^{J−j} + ah/2^{J}∥)

≤ ∑_{h=−∞}^{∞} ∑_{k=−∞}^{∞} w_{1}(h)w_{2}(k) min(M, 1/∥ck/2^{J−j} + ah/2^{J}∥) .

Let g(x) be defined as in Lemma 18.1. Then the above is

≪ ∑_{h=−∞}^{∞} ∑_{k=−∞}^{∞} w_{1}(h)w_{2}(k)g(ck/2^{J−j} + ah/2^{J})

= ∑_{m=−M}^{M} ĝ(m) ∑_{h=−∞}^{∞} w_{1}(h)e(mah/2^{J}) ∑_{k=−∞}^{∞} w_{2}(k)e(mck/2^{J−j})

= ∑_{m=−M}^{M} ĝ(m)W_{1}(ma/2^{J})W_{2}(mc/2^{J−j}) .

18.2 Applications 11

By Lemmas 18.1 and 18.2, this is

≪ HK(log M)(1 + ∑_{\begin{matrix}m=1 \\ ∥ma/2^{J} ∥<1/H \\ ∥mc/2^{J−j}∥<1/K \end{matrix}}^{M} 1) . (18.xx+23)

By (18.xx+10) we see that

(18.xx+24)  ∑_{c=1}^{2^{J−j}} |f̂_{J}(c2^{j} − a)| ≪ |f̂_{j}(a)|2^{(1/2−β)(J−j)} .

Hence

(18.xx+25) ∑_{a=1}^{J} |f̂_{J}(a)| ∑_{c=1}^{2^{J−j}} |f̂_{J}(c2^{j} − a)| ≪ 2^{(1/2−β)(J−j)} ∑_{a=1}^{2^{J}} |f̂_{J}(a)f̂_{j}(a)| .

By (18.xx+8) we see that

(18.xx+26) f̂_{J}(a) = \frac{1}{2^{J}} T_{J}(a/2^{J}) = \frac{1}{2^{J}} T_{J−j}(a/2^{J})T_{j}(a/2^{j}) = \frac{1}{2^{J−j}} T_{J−j}(a/2^{J})f̂_{j}(a) .

Write a = a_{0} + a_{1}2^{j}. Then the right hand side of (18.xx+25) is

= 2^{(−1/2−β)(J−j)} ∑_{a_{0}=1}^{2^{j}} |f̂_{j}(a_{0})|^{2} ∑_{a_{1}=1}^{2^{J−j}} |T_{J−j}(a_{0} + a_{1}/2^{J−j})| .

By Lemma 18.6 this is

≪ 2^{(1−2β)(J−j)} ∑_{a_{0}=1}^{j} |f̂_{j}(a_{0})|^{2} .

Here the sum over a_{0} is = 1 by Parseval’s identity, so we conclude that

(18.xx+27)  ∑_{a=1}^{J} |f̂_{J}(a)| ∑_{c=1}^{2^{J−j}} |f̂_{J}(c2^{j} − a)| ≪ 2^{(1−2β)(J−j)} .

Hence the term HK log M in (18.xx+23), which reflects the mean value of min(M, 1/∥x∥), contributes to (18.xx+22) an amount that is

(18.xx+28)  ≪ K^{2}2^{(1−2β)J} log M .

It remains to estimate

(18.xx+29)  K^{2}(log M) ∑_{a=1}^{2^{J}} ∑_{j=1}^{J} ∑_{\begin{matrix}c=1 \\ 2∤c \end{matrix}}^{2^{J−j}} |f̂_{J}(a)f̂_{J}(c2^{j} − a)| ∑_{\begin{matrix}m=1 \\ ∥ma/2^{J} ∥<1/H \\ ∥mc/2^{J−j}∥<1/K \end{matrix}}^{M} 1 .

The way that we proceed depends on the size of 2^{J−j}. Suppose first that 2^{J−j} ≥ K. Since M ≤ K, the numbers m = 1, 2, …, M comprise at most one complete system of residues modulo 2^{J−j}, and hence the number of them for which ∥mc/2^{J−j}∥ ≤ 1/K is ≪ 2^{J−j}/K since c is odd. By (18.xx+27), such a j contributes to (18.xx+29) an amount

≪ K2^{(2−2β)(J−j)} log M,

and the sum over such j contributes

(18.xx+30)  ≪ K2^{(2−2β)J} log M .

Next suppose that M < 2^{J−j} < K. For 1 ≤ m ≤ M < 2^{J−j} we have m ≢ 0 (mod 2^{J−j}), and hence ∥mc/2^{J−j}∥ ≥ 1/2^{J−j} > 1/K. Thus in (18.27), the sum over m is empty when M < 2^{J−j} < K. Finally, suppose that 2^{J−j} ≤ M. Since K ≥ M, the inequality ∥mc/2^{J−j}∥ < 1/K holds only when m is a multiple of 2^{J−j}. Write m = r2^{J−j}. Then we have to estimate

(18.xx+31)  K^{2}(log M) ∑_{a=1}^{2^{J}} ∑_{\begin{matrix}j \\ 1≤2^{J−j}≤M \end{matrix}} ∑_{c=1}^{2^{J−j}} |f̂_{J}(a)f̂_{J}(c2^{j} − a)| ∑_{\begin{matrix}r=1 \\ ∥ra/2^{j}∥<1/H \end{matrix}}^{M/2^{J−j}} 1 .

To the extent possible, we argue as before. By (18.xx+24) the above is

≪ K^{2}(log M) ∑_{a=1}^{2^{J}} ∑_{\begin{matrix}j \\ 1≤2^{J−j}≤M \end{matrix}} 2^{(1/2−β)(J−j)}|f̂_{J}(a)f̂_{j}(a)| ∑_{\begin{matrix}r=1 \\ ∥ra/2^{j}∥<1/H \end{matrix}}^{M/2^{J−j}} 1 .

We appeal to (18.xx+26) and write a = a_{0} + a_{1}2^{j} to see that the above is

= K^{2}(log M) ∑_{\begin{matrix}j \\ 1≤2^{J−j}≤M \end{matrix}}2^{(−1/2−β)(J−j)} ∑_{a_{0}=1}^{2^{j}} |f̂_{j}(a_{0})|^{2} ∑_{\begin{matrix}r=1 \\ ∥ra/2^{j}∥<1/H \end{matrix}}^{M/2^{J−j}} ∑_{a_{1}=1}^{2^{J−j}} |T_{J−j}(a_{0}/2^{J} +a_{1}/2^{J−j})| .

We apply Lemma 18.6 to the sum over a_{1}, and thus see that the above is

(18.xx+32)  ≪ K^{2}(log M) ∑_{\begin{matrix}j \\ 1≤2^{J−j}≤M \end{matrix}} 2^{(1−2β)(J−j)} ∑_{a_{0}=1}^{2^{j}} |f̂_{j}(a_{0})|^{2} ∑_{\begin{matrix}r=1 \\ ∥ra_{0}/2^{j}∥<1/H \end{matrix}}^{M/2^{J−j}} 1 .

In general, we would expect the sum over r to be about M/(H2^{J−j}) in size. Let B be chosen later, B ≤ H. The a_{0} for which the sum over r is ≤ M/(B2^{J−j}) contribute an amount ≪ M/(B2^{J−j}), by Parseval’s identity. Now consider those a_{0} for which the sum over r lies between 2^{i}M/(B2^{J−j}) and 2^{i+1}M/(B2^{J−j}). This is far more solutions than we expect, and by Lemma 18.7 it follows that there is a q ≪ B/2^{i} such that ∥qa_{0}/2^{j}∥ ≪ B2^{J−j}/(2^{i}HM). Let h denote the integer nearest qa_{0}/2^{j}. Then 1 ≤ h ≤ q, and

|a_{0} − \frac{2^{j}h}{q}| ≪ \frac{B2^{J}}{2^{i}HMq} ,

so for each h there are ≪ B2^{J}/(2^{i}HMq) such a_{0}. (There is no need to add 1 to this estimate, since the interval in which the a_{0} lie has length ≫ 1.) On summing over h and over q ≪ B/2^{i}, we find that there are ≪ B^{2}2^{J}/(2^{2i}HM) values a_{0} in question. Since f̂_{j}(a_{0}) ≪ 2^{−αj} by Lemma 18.4, we find that the contribution of such a_{0} is ≪ B2^{(1−2α)j}/(2^{i}H). We sum over i, and combine our estimates to see that

∑_{a_{0}=1}^{2^{j}} |f̂_{j}(a_{0})|^{2} ∑_{\begin{matrix}r=1 \\ ∥ra_{0}/2^{j}∥<1/H \end{matrix}}^{M/2^{J−j}} 1 ≪ \frac{M}{B2^{J−j}} + \frac{B2^{(1−2α)j}}{H} .

To optimize this bound we take B = M^{1/2}H^{1/2}2^{−J/2+αj}, and thus see that

(18.xx+33)  ∑_{a_{0}=1}^{2^{j}} |f̂_{j}(a)|^{2} ∑_{\begin{matrix}r=1 \\ ∥ra_{0}/2^{j}∥<1/H \end{matrix}}^{M/2^{J−j}} 1 ≪ M^{1/2}H^{−1/2}2^{−J/2+(1−α)j} .

Hence the quantity (18.xx+32) is

≪ K^{2}M^{1/2}H^{−1/2}2^{(1/2−α)J}(log M) ∑_{\begin{matrix}j \\ 1≤2^{J−j}≤M \end{matrix}} 2^{(α−2β)(J−j)} .

But α − 2β > 0, so the largest term occurs when 2^{J−j} ≍ M, and hence the above is

(18.xx+34)  ≪ K^{2}M^{1/2+α−2β}H^{−1/2}2^{(1/2−α)J} log M .

On combining this with (18.xx+19), (18.xx+21), (18.xx+28), and (18.xx+30), we conclude that the left hand side of (18.xx+18) is

≪K^{2}MH^{−1} + (KM)^{2+ε}H2^{−J} + K^{2}2^{(1−2β)J} log M
+ K2^{(2−2β)J} log M + K^{2}M^{1/2+α−2β}H^{−1/2}2^{(1/2−α)J} log M .

Suppose that 2^{J} ≍ MHA. Then (apart from the ε in the exponent), the first two terms are ≪ K^{2}M(1/H + 1/A). If A and H are allowed to vary in such a way that AH is held constant, then the third and fourth terms above are fixed, and the sum of the first two terms is minimized by taking A = H. Accordingly, we take J so that 2^{J} ≍ MH^{2}. Thus the above is

≪K^{2+ε}M^{1+ε}H^{−1} + K^{2}M^{1−2β}H^{2−4β} log M
+ KM^{2−2β}H^{4−4β} log M + K^{2}H^{1/2−2α}M^{1−2β} log M .

Here the last term is smaller than the second one, so may be ignored. If K^{1−4β/3} ≤ M ≤ K, then we take H = K^{1/(5−4β)}/M^{(1−2β)/(5−4β)}. Then the first and third terms are roughly equal and the second term is smaller. In this range, all terms are

≪ K^{1−1/(5−4β)+ε}M^{1+(1−2β)/(5−4β)+ε} .

For 2 ≤ M ≤ K^{1−4β/3}, we take H = M^{2β/(3−4β)}. Then the first and second terms are nearly equal, and the third one is smaller. In this range, all terms are

≪ K^{2+ε}M^{1−2β/(3−4β)+ε} .

Thus we have (18.xx+18), and the proof is complete. □

We note that (18.xx+33) is worse than the trivial bound

∑_{a_{0}=1}^{2^{j}} |f̂_{j}(a)|^{2} ∑_{\begin{matrix}r=1 \\ ∥ra_{0}/2^{j}∥<1/H \end{matrix}}^{M/2^{J−j}} 1 ≪ M2^{−(J−j)} ∑_{a_{0}=1}^{2^{j}} |f̂_{j}(a)|^{2} ≪ M2^{−(J−j)}

when 2^{α(J−j)} > M^{α}H^{−1/2+2α}. Thus we could improve on (18.xx+34), but this would not lead to a stronger conclusion because the bound in (18.xx+34) makes a smaller contribution than the estimate (18.xx+28).

Exercises

1. Let f(x) be defined as in Lemma 19.1. Show that f̂(m) ≪ log 2M/|m| for |m| ≤ M, and that f̂(m) ≪ (M/|m|)^{2} for |m| ≥ M.

2. Let T_{J}(θ) be defined as in (18.2). (a) Show that |T_{J}(1/3)| = 3^{J/2}.

(b) Suppose that 4/3 = 4^{α′}, so that α′ = 0.20752 . . .. Show that Lemma 18.4 would be false if α is replaced by a number > α′.

3. For 0 ≤ r ≤ 1, let f_{r}(θ) = log |1 − re(θ)|.

(a) Show that if 0 ≤ r < 1, then

f_{r}(θ) = − ∑_{n=1}^{∞} \frac{r^{n}}{n} cos 2πnθ .

(b) Show that if θ ∉ ℤ, then ∑_{n=1}^{∞}(cos 2πnθ)/n converges.

(c) By Abel’s theorem (cf §5.2), deduce that

f_{1}(θ) = − ∑_{n=1}^{∞} \frac{cos 2πnθ}{n}

when θ ∉ ℤ.

(d) Show that

f_{1}(θ) − f_{r}(θ) ≪ min (\frac{1 − r}{∥θ∥} , log \frac{1 − r}{∥θ∥} ) .

(e) Deduce that ∥f_{1} − f_{r}∥_{1} ≪ (1 − r) log(2/(1 − r)).

(f) Show that if 0 ≤ r < 1, then

f̂_{r}(n) = \{ \begin{matrix}\frac{−r^{|n|}}{2|n|} & (n ≠ 0), \\ 0 & (n = 0) \end{matrix}

(g) By the inequality |f̂_{r}(n) − f̂_{1}(n)| ≤ ∥f_{r} − f_{1}∥_{1}, deduce that

f̂_{1}(n) = \{ \begin{matrix}\frac{−1}{2n} & (n ≠ 0), \\ 0 & (n = 0). \end{matrix}

(h) Deduce (18.3).

(i) Deduce (18.4).

4. (a) Show that |1 − e(θ)| + |1 + e(θ)| ≤ 2\sqrt{2} for all θ.

(b) Let S_{J}(θ) denote the sum in Lemma 18.6. Show that S_{J}(θ) ≤ 2\sqrt{2}S_{J−1}(2θ).

5. For 1 ≤ n ≤ N, let X_{n} denote independent random variables with P (X_{n} = ±1) = 1/2. For a generic point ω of our probability space, let f_{ω}(θ) = ∑_{n=1}^{N} X_{n}e(nθ) denote a random exponential polynomial.

(a) Show that

∫_{0}^{1} |f_{ω}(θ)|^{2} dθ = N

for all ω.

(b) Show that

∫_{0}^{1} |f_{ω}(θ)|^{4} dθ = ∑_{n=2}^{2N} ( ∑_{\begin{matrix}1≤m,k≤N \\ m+k=n \end{matrix}} X_{m}X_{k})^{2} .

(c) Show that the number of pairs (m, k) with 1 ≤ m, k ≤ N and m + k = n is max(0, N − |N + 1 − n|).

(d) Show that if n is odd, 2 ≤ n ≤ 2N, then

E[ ∑_{\begin{matrix}1≤m_{1},k_{1},m_{2},k_{2}≤N \\ m_{1}+k_{1}=m_{2}+k_{2}=n \end{matrix}} X_{m_{1}}X_{k_{1}}X_{m_{2}}X_{k_{2}}] = 2(N − |N + 1 − n|) .

(e) Show that if n is even, 2 ≤ n ≤ 2N, then

E[ ∑_{\begin{matrix}1≤m_{1},k_{1},m_{2},k_{2}≤N \\ m_{1}+k_{1}=m_{2}+k_{2}=n \end{matrix}} X_{m_{1}}X_{k_{1}}X_{m_{2}}X_{k_{2}}] = 2(N − |N + 1 − n|) − 1 .

(f) Show that

E[ ∫_{0}^{1} |f_{ω}(θ)|^{4} dθ] = 2N^{2} − N .

(g) Deduce that

P ( ∫_{0}^{1} |f_{ω}(θ)|^{4} dθ > 4N^{2}) ≤ \frac{1}{2} .

(h) Show that

∫_{0}^{1} |f|^{2} ≤ ( ∫_{0}^{1} |f|)^{2/3}( ∫_{0}^{1} |f|^{4})^{1/3}

for all f.

(i) Show that

P ( ∫_{0}^{1} |f_{ω}(θ)| dθ ≥ \frac{\sqrt{N}}{2} ) ≥ \frac{1}{2} .

With more work, it can be shown that ∫_{0}^{1} |f_{ω}(θ)|^{4} dθ is usually near its expectation, with the result that the probability considered in (i) above tends rapidly to 1 as N tends to infinity. Also, it is unlikely that ∥f_{ω}∥_{∞} would be much larger than \sqrt{N log N}. Hence in Lemma 18.6 and Exercise 2(a) we see that the coefficients (−1)^{s(n)} produce behavior that would be highly atypical for a random sequence.

6. Suppose that 0 < δ_{1} ≤ δ_{2}/2, that N ≥ 1/δ_{2}, that 1 ≤ q ≤ 1/(2δ_{2}), choose a so that (a, q) = 1, put θ = a/q + δ_{1}/(δ_{2}qN), and set I = [0, 2δ_{1}].

(a) Show that ∥qθ∥ = δ_{1}/(δ_{2}N).

(b) Show that nθ ∈ I (mod 1) for at least δ_{2}N values of n, 1 ≤ n ≤ N.

7. (a) Explain why |T_{J}(θ)|^{4} = |T_{J−2}(θ)|^{4}|T_{2}(2^{J−2}θ)|^{4}.

(b) Explain why |T_{J−1}(θ)|^{4} = |T_{J−2}(θ)|^{4}|T_{1}(2^{J−2}θ)|^{4}.

(c) Write |T_{2}(α)|^{4} − 2|T_{1}(α)|^{4} − 16 = ∑_{n=0}^{6} c_{n} cos 2πnα. Show that c_{0} = c_{1} = 0.

(d) Explain why ∫_{0}^{1} |T_{J−2}(θ)|^{4}e(kθ) dθ = 0 if |k| ≥ 2^{J−1} − 1.

(e) Put u_{J} = ∫_{0}^{1} |T_{J}(θ)|^{4} dθ. Show that u_{0} = 1, u_{1} = 6, and that

u_{J} = 2u_{J−1} + 16u_{J−2}

for J ≥ 2.

(f) Show that

u_{J} = \frac{17 + 5\sqrt{17}}{34}(1 + \sqrt{17})^{J} + \frac{17 − 5\sqrt{17}}{34}(1 − \sqrt{17})^{J} .