Chapter 17

Exponential sums

17.1 Exponential integrals

We are interested in non-trivial bounds for sums of the form ∑_{n=1}^{N} e(f(n)) where f(x) is a smooth function. In this chapter we develop methods whereby one may show that such a sum is indeed o(N). The quality of the results are dependent on the finer properties of f. In some simple cases the estimates are best possible, but in most the bounds obtained fall far short of what we suppose to be the truth. We begin with the simpler continuous analogue. This provides motivation, and the results also have their uses in dealing with the discrete case.

We seek bounds for integrals of the form ∫_{a}^{b} r(t)e^{iθ(t)} dt in terms of the behaviour of r(t) and θ(t). We begin by generalizing the obvious inequality

(17.1)  | ∫_{a}^{b} e^{iαt} dt| ≤ min (b − a, \frac{2}{|α|}).

Theorem 17.1 Let r(t) and θ(t) be real-valued functions on [a, b] for which r(t) is continuous on [a, b], θ(t) is differentiable on [a, b] (where if necessary we take the right and left hand deriviatives at a and b respectively), θ′(t) is continuous on [a, b], and θ′(t) ≠ 0. Suppose that λ satisfies var_{[a,b]}r/θ′ ≤ 2λ and |r(t)/θ′(t)| ≤ λ when a ≤ t ≤ b. Then

| ∫_{a}^{b} r(t)e^{iθ(t)} dt| ≤ 4λ.

In many interesting cases r/θ′ is monotonic and then the bound on r/θ′ implies the bound on the variation.

Proof. Let ρ(t) = r(t)/θ′(t). We integrate by parts, using the Riemann–Stieltjes integral as developed in Appendix A. Thus

(17.2)  ∫_{a}^{b} r(t)e^{iθ(t)} dt = −i ∫_{a}^{b} ρ(t)de^{iθ(t)} = −iρ(t)e^{iθ(t)}|_{a}^{b} + i ∫_{a}^{b} e^{iθ(t)} dρ(t).

Hence

| ∫_{a}^{b} r(t)e^{iθ(t)} dt| ≤ |ρ(a)| + |ρ(b)| + ∫_{a}^{b} |dρ(t)| ≤ 4λ.

It is instructive to view the above argument geometrically. When a ≤ t ≤ b, let Z(t) = ∫_{a}^{t} r(u)e^{iθ(u)} du. These points describe a curve in the complex plain, with tangent vector r(t)e^{iθ(t)}. Thus Z(t) is moving with speed |r(t)|, and the argument of the tangent vector is changing at a rate θ′(t). Hence the curve has curvature κ = |θ′(t)/r(t)|. Consequently the radius of curvature at time t is |ρ(t)|, and C(t) = Z(t) + iρ(t)e^{iθ(t)} is the centre of the osculating circle. One may reach Z(b) from the origin by following the path Z(t). Alternatively, to reach Z(b) one may first move along the line segment from 0 to C(a), then follow the path C(t) to C(b), and finally pass along the line segment from C(b) to Z(b). These two alternatives are expressed in the identity (17.2). When ρ(t) is differentiable we find that C′(t) = iρ′(t)e^{iθ(t)}. Thus the tangent vector C′(t) to the curve C(t) is at all times perpendicular to the tangent vector Z′(t) to the curve Z(t), and C(t) moves with a speed equal to the rate of change of the radius of curvature. Suppose for simplicity that ρ(t) is positive and decreasing. Then the curve Z(t) spirals inward, in the sense that the osculating circles are nested. To see this, observe that if a ≤ t_{1} ≤ t_{2} ≤ b, then

|C(t_{1}) − C(t_{2})| = |i ∫_{t_{1}}^{t_{2}} e^{iθ(t)} dρ(t)| ≤ ∫_{t_{1}}^{t_{2}} |dρ(t)| = ρ(t_{1}) − ρ(t_{2}).

In particular, the circle with centre C(a) and radius ρ(a) passes through the point Z(a) = 0, whilst Z(b) falls within the circle. Hence Z(b)| ≤ 2ρ(a) in this case.

If θ′(t) vanishes at some point of the interval [a, b], then Theorem 17.1 does not apply, but we can still obtain a bound when θ′′(t) exists and is not too small.

Theorem 17.2 Suppose that r(t) and θ(t) are real valued and continuous on [a, b], that 0 < r(t) ≤ M, that θ(t) is twice differentiable on [a, b] (where if necessary we take the right and left hand derivatives at a and b respectively), that θ′(t)/r(t) is monotonic and that 0 < μ ≤ θ′′(t) when a ≤ t ≤ b. Then

| ∫_{a}^{b} r(t)e^{iθ(t)} dt| ≤ \frac{8M}{\sqrt{μ}} .

The above often suffices in applications. If necessary, a more precise approximation can be derived, say via the more elaborate Theorem 17.11 below. However, generally the above bound is of the correct order of magnitude. For example, in the case r(t) ≡ 1 and θ(t) = ct^{2} with c > 0 we have θ′′(t) = 2c and

(17.3)  ∫_{−∞}^{∞} e^{ict^{2}} dt = e(1/8)\sqrt{π/c} .

(A proof of this is outlined in Exercise 9.3.1.5.) If we were to apply Theorem 17.2 to the integral above, we would find that it is ≪ 1/\sqrt{c}, which is to say we would obtain a bound of the correct order of magnitude. Depicted below is the curve Z(t) = ∫_{−∞}^{t} e^{iu^{2}} du, which spirals tightly except near the inflection point at t = 0.

Figure 17.1 Graph of Z(t) = ∫_{−∞}^{t} e^{iu^{2}} du for −7 ≤ t ≤ 7

Proof of Theorem 17.2. Let δ > 0 be a parameter at our disposal. Since θ′′(t) > 0, we know that θ′(t) is increasing, and hence if there are t for which |θ′(t)| ≤ δμ, then such t comprise an interval, say I_{0}. If I_{0} is a proper subinterval of [a, b], then the complement of I_{0} consists of one or two intervals, say I_{±1}. The length of I_{0} is at most 2δ, since θ′′(t) ≥ μ. Hence

| ∫_{I_{0}} r(t)e^{iθ(t)} dt| ≤ 2Mδ.

For t ∈ I_{±1} we have |θ′(t)| ≥ δμ. Thus, by Theorem 17.1 with λ = Mμ^{−1}δ^{−1}, we deduce that

| ∫_{I_{±1}} r(t)e^{iθ(t)} dt| ≤ \frac{4M}{δμ} .

Hence altogether

| ∫_{a}^{b} r(t)e^{iθ(t)} dt| ≤ 2Mδ + \frac{8M}{δμ} ,

and the desired bound follows on taking δ = 2μ^{−1/2}.

17.1.1 Exercises

1. Suppose that k ≥ 2, that f : [a, b] → ℝ is k times differentiable on [a, b] and that there is a positive number λ_{k} such that for each x in (a, b) we have f^{(k)}(x) ≥ λ_{k}. Show that

| ∫_{a}^{b} e(f(x)) dx| ≤ k2^{k}λ_{k}^{−1/k}.

2. Suppose that α_{1}, α_{2}, … α_{k} are real and let

I(t; α) = ∫_{0}^{t} e(α_{1}u + α_{2}u^{2} + ⋯ α_{k}u^{k}) du.

Show that for any positive number t,

I(t; α) ≪ \frac{t}{(1 + |α_{1}|t + |α_{2}|t^{2} + ⋯ + |α_{k}|t^{k})^{1/k}} .

17.2 Elementary estimates

We now derive discrete analogues of the estimates of the the preceding section. The discrete analogue of (17.1) is found already in (16.5). As an analogue of Theorem 17.1 we have

Theorem 17.3 (Kusmin–Landau) Let α_{1}, α_{2}, …, α_{N} be real numbers and for 1 ≤ n < N put δ_{n} = α_{n+1} − α_{n}. Suppose that Δ is a positive real number and that Δ ≤ δ_{1} ≤ δ_{2} ≤ … ≤ δ_{N−1} ≤ 1 − Δ < 1. Then

| ∑_{n=1}^{N} e(α_{n})| ≤ cot \frac{πΔ}{2} .

Proof. Let z_{n} = e(α_{n}), w_{n} = z_{n+1}/z_{n} = e(δ_{n}) and ρ_{n} = 1/(1 − w_{n}). Then

∑_{n=1}^{N} e(α_{n}) = ∑_{n=1}^{N−1} ρ_{n}(z_{n} − z_{n+1}) + z_{N}.

By partial summation the right hand side above is

= ρ_{1}z_{1} + ∑_{n=2}^{N−1}(ρ_{n} − ρ_{n−1})z_{n} + (1 − ρ_{N−1})z_{N}, (17.4)

so that

| ∑_{n=1}^{N} e(α_{n})| ≤ |ρ_{1}| + ∑_{n=2}^{N−1} |ρ_{n} − ρ_{n−1}| + |1 − ρ_{N−1}| .

If ρ = 1/(1 − w) and w = e(δ) with 0 < δ < 1, then ρ = (1 + i cot πδ)/2 and |ρ| = |1 − ρ| = 1/(2 sin πδ). Hence the above is

≤ \frac{1}{2 sin πδ_{1}} + \frac{1}{2} ∑_{n=2}^{N−1} ( cot πδ_{n−1} − cot πδ_{n}) + \frac{1}{2 sin πδ_{N−1}}

= \frac{1}{2}(\frac{1}{sin πδ_{1}} + \frac{1}{tan πδ_{1}} − \frac{1}{tan πδ_{N−1}} + \frac{1}{sin πδ_{N−1}} )

≤ \frac{1}{sin πΔ} + \frac{1}{tan πΔ}

= cot \frac{πΔ}{2} ,

and the proof is complete.

The above argument can be interpreted geometrically as follows. Let s_{n} denote the n-th partial sum of the sum on the left of (17.4), and for 1 < n < N, put c_{n} = s_{n} + z_{n+1}ρ_{n}. Then c_{n} = s_{n−1} + z_{n}ρ_{n} = s_{n+1} − z_{n+1}(1 − ρ_{n}). Thus c_{n} is the centre of the circle that passes through the three points s_{n−1}, s_{n}, s_{n+1}, and the radius of this circle is |ρ_{n}|. Hence ρ_{n} corresponds to the function ρ(t) introduced in the proof of Theorem 17.1. One may construct a polygonal path from 0 to s_{N} whose vertices are the partial sums s_{n}. Alternatively, we may construct such a path that goes from 0 to c_{1}, then to c_{2}, and so on, and finally from c_{N−1} to s_{N}. This suggests writing s_{N} as a telescoping sum

s_{N} = c_{1} + ∑_{n=2}^{N−1}(c_{n} − c_{n−1}) + (s_{N} − c_{N−1}).

Since c_{n} − c_{n−1} = z_{n}(ρ_{n} − ρ_{n−1}), this is precisely the identity (17.4).

In most applications, the α_{n} are values of a function with continuous derivatives, as follows.

Corollary 17.4 Let f(x) be a real valued function continuous on [a, b], differentiable on (a, b), and such that f′(x) is increasing. Suppose further that M_{1} is a positive real number such that ∥f′(x)∥ ≥ M_{1} for all x ∈ (a, b). Then

| ∑_{a≤n≤b} e(f(n))| ≤ \frac{2}{πM_{1}} .

Here ∥θ∥ is the distance from θ to the nearest integer, ∥θ∥ = min_{n∈ℤ} |θ − n|.

Proof. Let M be an integer chosen so that M < f′(x) < M + 1 for x ∈ (a, b). If we replace f(x) by f(x) − Mx, then the sum is unchanged and M_{1} ≤ f′(x) ≤ 1 − M_{1}, which allows us to apply Theorem 17.3 with α_{n} = f(n) and Δ = M_{1}. By the mean value theorem for derivatives we know that if [n, n + 1] ⊂ [a, b], then there is a ξ_{n} ∈ (n, n + 1) such that δ_{n} = f(n + 1) − f(n) = f′(ξ_{n}). Thus the hypotheses of the Theorem 17.3 are satisfied and it remains only to note that cot u < 1/u when 0 < u ≤ π/2.

The bounds provided in Theorem 17.3 and Corollary 17.4 are quite sharp (see Exercise 1). The partial sums spiral tightly in intervals in which ∥f′(x)∥ is large, but the terms tend to pull in one direction when f′(x) is near an integer. For example, consider f(x) = x^{2}/1600 with a = 0, b = 800. Then f′(a) = 0 and f′(b) = 1, but f′(x) is increasing and ∥f′(x)∥ ≥ 1/50 when 16 ≤ x ≤ 784, so that

| ∑_{n=16}^{784} e(\frac{n^{2}}{1600})| ≤ \frac{100}{π} < 31.831.

This with just the trivial bound for the contribution of the first 15 and last 16 terms shows that

| ∑_{n=1}^{800} e(\frac{n^{2}}{1600})| < 62.831.

(The exact value of this sum is 20 + 20i, as we see from Corollary 9.16.)

Figure 17.2 Partial sums of (a) ∑_{n=1}^{800} e(n^{2}/1600) = 20 + 20i, (b) ∑_{n=1}^{300} e((n/3)^{3/2}) = 25.56 + 25.81i.

In general when f′(b) − f′(a) is large but f′′(x) is small we may obtain a useful bound by treating separately the subintervals in which ∥f′(x)∥ is small or large.

Theorem 17.5 Let N be a positive integer with a ≤ b ≤ a + N and suppose that f is twice differentiable on [a, b] and that 0 < M_{2} ≤ f′′(x) ≤ AM_{2} when a ≤ x ≤ b. Then

∑_{a≤n≤b} e(f(n)) ≪_{A} M_{2}^{1/2}N + M_{2}^{−1/2}.

If instead we have −AM_{2} ≤ f′′(x) ≤ −M_{2}, then the same bound applies, as we see by taking complex conjugates. If M_{2} ≥ 1, then the bound given above is trivial, as it must be, since f(x) may be increasing so rapidly that all the numbers f(n) are integers (consider the case f(x) = x(x + 1)/2). If M_{2} ≤ N^{−2}, then again the bound is trivial, as it must be because f(x) may be essentially constant throughout the interval in question (here consider f(x) = (x/(2N))^{2} on the interval [a, b] = [0, N]). If N^{−2} ≤ M_{2} ≤ N^{−1}, then the bound provided is likely to be of the correct order of magnitude, unless Theorem 17.3 is applicable. If N^{−1} ≤ M_{2} ≤ 1, then it may be possible to obtain a sharper estimate by using Theorem 17.14. We could estimate how the implicit constant depends on A, but in practice one should cut the interval into subintervals so that A is bounded in each application. For example, suppose that we wish to estimate

(17.5)  ∑_{n=1}^{N} e((n/3)^{3/2}).

We take f(x) = (x/3)^{3/2}, and note that we may take M_{2} ≍ a^{1/2} and A ≪ 1 when a ≤ x ≤ b ≤ 2a. Then Theorem 17.4 gives the estimate

∑_{a≤n≤b} e((n/3)^{3/2}) ≪ a^{3/4}.

On summing over dyadic blocks, we deduce that the sum in (17.5) is ≪ N^{3/4}, which is best possible (see Exercise 17.3.1.3). In Figure 17.2(b) one may note that the partial sums resemble a number of copies of the curve in Figure 17.1, one for each solution of f′(x) ∈ ℤ. If f′(x_{ν}) = ν ∈ ℤ, then we obtain a copy of the curve of Figure 17.1, scaled by a factor ≍ f′′(x_{ν})^{−1/2}, and rotated by 2π(f(x_{ν}) − νx_{ν}). In the case under consideration we find that x_{ν} = 12ν^{2}, and hence f(x_{ν}) − νx_{ν} = −4ν^{3} ∈ ℤ, so that these contributions all pull in the same direction. More typically in general the f(x_{ν}) are not integers and one is led to consider a new exponential sum of the form ∑_{ν} e(f(x_{ν}) − νx_{ν}). The transformation from the original sum to this new sum is achieved by means of an analytic technique which we develop in the next section.

Proof. We have already noted that the bound is trivial when M_{2} ≫ 1. Thus we suppose that M_{2} ≤ 1/4. Since f′(b) − f′(a) = (b − a)f′′(ξ) ≤ AM_{2}(b − a) and f′ is increasing, we see that the interval f′([a, b]) contains ≪ AM_{2}(b − a) + 1 integers. Let λ be a positive parameter at our disposal. Then the set of x ∈ [a, b] such that ∥f′(x)∥ ≥ λ can be partitioned into at most ≪ AM_{2}(b − a) + 1 intervals, and likewise so can the set x ∈ [a, b] such that ∥f′(x)∥ < λ and in the latter case each interval is of length at most ≪ λM_{2}^{−1}. By Corollary 17.4 the contribution to the sum from the terms with n in a subinterval of the first kind is ≪ λ^{−1}, and trivially the contribution from such n in an subinterval of the second kind is ≪ λM_{2}^{−1} + 1. Hence the sum in question is

≪_{A} (M_{2}N + 1)(λ^{−1} + λM_{2}^{−1} + 1),

and the choice λ = M_{2}^{1/2} gives the stated bound.

As a further application of Theorem 17.4, we consider the trigonometric polynomial

(17.6)  P (α) = ∑_{n=1}^{N} e(n log n + nα).

Take f(x) = x log x + αx. Then we find that f′′(x) = 1/x, and Theorem 17.5 gives the estimate

∑_{a≤n≤b} e(n log n + nα) ≪ a^{1/2}

when a ≤ b ≤ 2a. On summing over dyadic blocks we deduce that

(17.7)  P (α) ≪ N^{1/2}

This is best possible, at least for some α, since by Parseval’s identity we have

∫_{0}^{1} |P (α)|^{2}d α = N.

Thus P (α) is an example of a trigonometric polynomial with unimodular coefficients and such that ∥P ∥_{2} = ∥P ∥_{∞}.

We have noted that Corollary 17.4 is useless when f′(x) is large, but that Theorem 17.5 provides a substitute when f′′(x) is small. If f′′(x) is large, then Theorem 17.5 is useless but we may still obtain non-trivial estimates if f′′′(x) (or some higher derivative) is small. To derive bounds which depend on higher derivatives we introduce an important new idea.

Lemma 17.6 (van der Corput) Let z_{1}, z_{2}, …, z_{N} be arbitrary complex numbers. Then for any integer H with 1 ≤ H ≤ N we have

H^{2}| ∑_{n=1}^{N} z_{n}|^{2} ≤ H(N + H − 1) ∑_{n=1}^{N} |z_{n}|^{2} + 2(N + H − 1) ∑_{h=1}^{H−1}(H − h)| ∑_{n=1}^{N−h} z_{n+h}z̄_{n}|.

Proof. To simplify the ranges of summation, we suppose that z_{n} = 0 when n < 1 or n > N. Then

H ∑_{n=1}^{N} z_{n} = ∑_{0≤r<H} ∑_{0<n<N+H} z_{n−r} = ∑_{0<n<N+H} ∑_{0≤r<H} z_{n−r}.

Hence, by Cauchy’s inequality, we see that

(17.8)  H^{2}| ∑_{n=1}^{N} z_{n}|^{2} ≤ (N + H − 1) ∑_{0<n<N+H} | ∑_{0≤r<H} z_{n−r}|^{2}.

On multiplying out the square on the right, and inverting the order of summation we see that this is

(N + H − 1) ∑_{\begin{matrix}0≤r<H \\ 0≤s<H \end{matrix}} ∑_{n} z_{n−r}z̄_{n−s}.

The inner sum depends only on r − s, and a given value h of r − s occurs for H − |h| different pairs r, s. Thus the above is

(17.9)  H(N + H − 1) ∑_{n=1}^{N} |z_{n}|^{2} + 2(N + H − 1)ℜ ∑_{h=1}^{H−1}(H − h) ∑_{n} z_{n+h}z̄_{n},

and the desired result now follows.

In applications, if H = o(N), then it is likely that some cancellation has been discarded when Cauchy’s inequality is applied. That is, there may be some loss in the inequality (17.8). Similarly, in passing from (17.9) to the final result by means of the triangle inequality, some cancellation may have been lost. As a first application of this lemma we note

Theorem 17.7 (van der Corput) Let {u_{n}} be a sequence of real numbers with the property that, for each positive integer h, the sequence {u_{n+h} − u_{n}} is uniformly distributed. Then the sequence {u_{n}} is uniformly distributed.

From the example u_{n} = nθ with θ irrational we see that the converse of the above theorem is false.

Proof. By Weyl’s criterion (Theorem 16.1) we know that it suffices to show that for any positive integer k

(17.10)  ∑_{n=1}^{N} e(ku_{n}) = o(N)

as N → ∞. Taking z_{n} = e(ku_{n}) in the lemma, we see that

(17.11)  ∑_{n=1}^{N} e(ku_{n}) ≪ NH^{−1/2} + N^{1/2}(\frac{1}{H} ∑_{h=1}^{H} | ∑_{n=1}^{N−h} e(k(u_{n+h} − u_{n}))|)^{1/2}.

Since the sequence {u_{n+h} − u_{n}} is uniformly distributed, we find by a second application of Weyl’s criterion that the innermost sum is o(N) for each h. Hence for any given H the right hand side is O(NH^{−1/2}) + o(N). Since H may be taken arbitrarily large, we deduce that (17.10) holds, and the proof is complete.

Corollary 17.8 (Weyl) Let P (x) = ∑ c_{i}x^{i} be a polynomial with real coefficents. If there is an i > 0 for which the coefficient c_{i} is irrational, then the sequence {P (n)} is uniformly distributed.

The constant term c_{0} may be rational or irrational, since it only causes the sequence to be translated. The converse is obvious, for if the coefficients c_{i} were to be rational for all i > 0, then the sequence {P (n)} would be periodic and then the numbers P (n) would not even be dense in 𝕋.

Proof. We first prove the assertion by induction under the stronger hypothesis that the leading coefficient is irrational. If deg(P) = 1, then the result follows by Theorem 14.2. If deg(P) = d > 1 and the leading coefficent c_{d} is irrational, then for any positive integer h the polynomial P (x + h) − P (x) has an irrational leading coefficient hdc_{d}. Hence the numbers P (n + h) − P (n) are uniformly distributed by the inductive hypothesis. This establishes the result when the leading coefficient is irrational.

Now suppose that P (x) has an irrational coefficient (other than the constnat term), which may or may not be the leading coefficient. Write P (x) = P_{i}(x) + P_{r}(x)/q where all the non-zero coefficients of P_{i} are irrational and all the coefficients of P_{r} are integers. Then P_{i}(x) has positive degree. Moreover, for any integer a the polynomial P_{i}(qx + a) has positive degree and irrational leading coefficient. Hence the sequence P_{i}(qn + a) s uniformly distributed. On the other hand, the sequence P_{r}(qn + a)/q is constant modulo 1. Hence the sequence P (qn + a) is uniformly distributed. It follows at once from the definition of uniform distribution that the sequence P (n) is also uniformly distributed.

We now use the van der Corput Lemma (Lemma 17.6) to derive bounds for the exponential sum ∑ e(f(n)) that depend on higher derivatives of f.

Theorem 17.9 Let N be a positive integer and suppose that a ≤ b ≤ a+N and 0 < M_{3} ≤ f′′′(x) ≤ AM_{3} when a ≤ x ≤ b. Then

∑_{a≤n≤b} e(f(n)) ≪_{A} N(M_{3}^{1/6} + N^{−1/4} + N^{−3/4}M_{3}^{−1/4}).

If M_{3} < N^{−3} or M_{3} > 1, then the bound is trivial, for then the second factor on the right is larger than 1. Of the three terms in parentheses on the right, we see that the first one is largest when N^{−3/2} ≤ M_{3} ≤ 1, the second is largest when N^{−2} ≤ M_{3} ≤ N^{−3/2}, and the third is largest when N^{−3} ≤ M_{3} ≤ N^{−2}.

Proof. In view of the remarks above, we may suppose that N^{−3} ≤ M_{3} ≤ 1. Suppose that 0 < h ≤ b − a, and let f_{h}(x) = f(x + h) − f(x) for a ≤ x ≤ b − h. By the van der Corput Lemma we see that

(17.12)  ∑_{a≤n≤b} e(f(n)) ≪ NH^{−1/2} + N^{1/2}(\frac{1}{H} ∑_{h=1}^{H} | ∑_{n} e(f_{h}(n))|)^{1/2}.

Since f′′_{h}(x) = f′′(x + h) − f′′(x) = hf′′′(ξ) ≍ hM_{3}, it follows from Theorem 17.4 that the inner sum is ≪_{A} h^{1/2}M_{3}^{1/2}N + h^{−1/2}M_{3}^{−1/2}. On inserting this estimate, we see that the right hand side above is

≪_{A} NH^{−1/2} + M_{3}^{1/4}H^{1/4}N + M_{3}^{−1/4}H^{−1/4}N^{1/2}.

If N^{−3/2} ≤ M_{3} ≤ 1, then we take H = [M_{3}^{−1/3}], and the first two terms are the same size and the third is smaller. If N^{−2} ≤ M_{3} ≤ N^{−3/2}, then we take H = [M_{3}^{−1}N^{−1}], whence the second and third terms are the same size and the first is smaller. In both these cases the chosen value of H satisfies the requirement that 1 ≤ H ≤ N. Finally, if N^{−3} ≤ M_{3} ≤ N^{−2}, then we take H = N, and the third term is the largest.

We note that if the innermost sum on the right in (17.12) is estimated trivially, then the bound obtained for the left hand side is trivial, but no worse. Consequently, a nontrivial estimate for the inner sum on the right will yield a non-trivial estimate for the sum on the left. Thus the Weyl–van der Corput inequality is a very useful tool, although (as we have already noted) it may be expected to involve some loss of quantitative precision. One may attempt to avoid some of this loss by constructing estimates for two-dimensional exponential sums, i.e. sums of the form ∑_{h,n} e(f(h, n)). Such estimates may then be applied to the double sum in (17.9), thereby avoiding the appeal to the triangle inequality in the last step of the proof of the Lemma.

Before considering further bounds involving derivatives of higher order, we note an immediate application to the zeta function. From the approximate functional equation for the zeta function (Theorem 10.2) it may be shown that ζ(1/2 + it) ≪ τ^{1/4}. Indeed, since ζ(1 + it) ≪ log τ and ζ(it) ≪ τ^{1/2} log τ for t ≥ 1, it follows “by convexity” that ζ(1/2 + it) ≪ τ^{1/4} log τ (recall Exercise 10.1.1.19). We now use our tools to derive a sub-convex bound.

Theorem 17.10 Let τ = |t| + 4. Then for any real t,

ζ(1/2 + it) ≪ τ^{1/6} log τ.

Proof. By Theorem 1.12 we know that

ζ(1/2 + it) = ∑_{n≤τ^{2}} n^{−1/2−it} + O(1)

where τ = |t| + 4. By Corollary 17.4 with f(x) = −t(log x)/(2π) we see that if τ ≤ a ≤ b ≤ 2a, then

(17.13)  ∑_{a≤n≤b} n^{−it} ≪ \frac{a}{τ} .

Similarly, by Theorem 17.5 we find that if τ^{2/3} ≤ a ≤ τ and a ≤ b ≤ 2a, then

(17.14)  ∑_{a≤n≤b} n^{−it} ≪ τ^{1/2}.

This bound also holds for τ^{1/2} ≤ a ≤ τ^{2/3}, but for such smaller a we obtain a better bound from Theorem 17.9: If τ^{1/3} ≤ τ^{2/3} and a ≤ b ≤ 2a, then

(17.15)  ∑_{a≤n≤2a} n^{−it} ≪ a^{1/2}τ^{1/6}.

On comparing (17.13) and (17.14) with (17.15), we discover that we have shown that (17.15) holds uniformly for a ≥ τ^{1/3}. The stated estimate now follows by (Riemann– Stieltjes) integration by parts.

If f′′′(x) is large, then the estimate of Theorem 17.9 is trivial, but if f^{(4)}(x) is small, then we may still obtain a useful estimate by applying the van der Corput Lemma and Theorem 17.9, in the same way that we derived Theorem 17.9 from Theorem 17.5. Continuing by induction, we obtain the following general result, of which Theorems 17.5 and 17.9 are the first two cases.

Theorem 17.11 Let N be a positive integer, and let r be an integer with r ≥ 2. Suppose that a ≤ b ≤ a + N and that 0 < M_{r} ≤ f^{(r)}(x) ≤ AM_{r} when a ≤ x ≤ b. Put R = 2^{r}. Then

∑_{a≤n≤b} e(f(n)) ≪_{A,r} N(M_{r}^{1/(R−2)} + N^{−2/R} + (N^{r}M_{r})^{−2/R}).

Proof. Since we have already established this for r = 2 and r = 3, we may suppose that r ≥ 4, and that the estimate has been established for r − 1. We may also suppose that N^{−r} ≤ M_{r} ≤ 1, for otherwise the bound is trivial. We apply the van der Corput Lemma as in the proof of Theorem 17.9, to obtain the estimate (17.12). As f_{h}^{(r−1)}(x) = f^{(r−1)}(x+h)−f^{(r−1)}(x) = hf^{(r)}(ξ) ≍ hM_{r}, we deduce from the inductive hypothesis that

∑_{a≤n≤b−h} e(f_{h}(n)) ≪_{A,r} N((hM_{r})^{2/(R−4)} + N^{−4/R} + (N^{r−1}hM_{r})^{−4/R}).

Inserting this in (17.12), we find that the sum in question is

≪_{A,r} N(H^{−1/2} + (HM_{r})^{1/(R−4)} + N^{−2/R} + (N^{r−1}HM_{r})^{−2/R}).

If M_{r} is not very small, say N^{−2+4/R} ≤ M_{r} ≤ 1, then we take H = [M_{r}^{−2/(R−1)}]. Then the first two terms are the same size, and the remaining terms are smaller. If M_{r} is extremely small, say N^{−r} ≤ M_{r} ≤ N^{−r+1}, then we take H = N. Then the last term is largest. In the intermediate range N^{−r+1} ≤ M_{r} ≤ N^{−2+4/R} we have some freedom in our choice of H, because it suffices to choose H so that the first, second and fourth terms are majorized by the third term. That is, we take H to be an integer such that H ≫ N^{4/R}, H ≪ M_{r}^{−1}N^{−2+8/R}, H ≫ M_{r}^{−1}N^{2−r}, and of course 1 ≤ H ≤ N. To complete the proof it suffices to verify that the lower bounds for H are indeed smaller than the upper bounds when M_{r} is in the interval under consideration.

17.2.1 Exercises

1. Let M, K be positive integers with K ≤ (M − 1)/2 and take N = 2M, Δ = (K + 1/2)/M, α_{n} = Δn, (1 ≤ n ≤ M), α_{n} = (1 − Δ)(n − M) + ΔM (M < n ≤ N). Further let δ_{n} = α_{n+1} − α_{n} (1 ≤ n < N) and S = ∑_{n=1}^{N} e(α_{n}). Show that

Δ ≤ δ_{1} ≤ δ_{2} ≤ … ≤ δ_{N−1} ≤ 1 − Δ,

that |S| = 2 cot πΔ, and that if M/K is large, then

|S| ∼ cot \frac{πΔ}{2}.

2. Suppose that the sequence u_{n} is weakly increasing, that u_{n+1}−u_{n} is weakly decreasing to 0, and that lim_{n→∞} n(u_{n+1} − u_{n}) = ∞. (Note that the sequence considered in Exercise 16.1.4 satisfies the first two hypotheses, but not the third.)

(a) Show that lim_{n→∞} u_{n}/ log n = ∞.

(b) Use the Kusmin–Landau inequality to show that u_{n} is uniformly distributed (mod 1).

(c) (Fejér (19xx) Suppose that f(x) is a real-valued function defined on the positive real numbers, such that f is weakly increasing, f′ decreases weakly to 0, and that xf′(x) → ∞ as x → ∞. Show that the sequence f(n) is uniformly distributed (mod 1).

3. Let P (α) = ∑_{n=1}^{N} e(n^{2}/N + nα). Show that P (α) ≪ N^{1/2} uniformly in α.

”4.”For arbitrary real c > 0, prove that

∑_{n=N}^{2N} e(c/n^{2}) ≪ c^{1/2}N^{−1} + c^{−1/2}N^{2}.

5. Show that

∑_{n=N}^{2N} e(\frac{n^{2}}{6N} ) ≪ 1,

but that

| ∑_{n=N}^{2N} e(\frac{n^{2}}{3N} )| ≍ N^{1/2}.

6. Prove that if M_{3} ≤ f′′′(x) ≤ AM_{3} and f′′(0) = 0, then

∑_{n=1}^{N} e(f(n)) ≪_{A} M_{3}^{−1/3} + N^{3/2}M_{3}^{1/2}.

7. Prove that if 1/N ≤ c ≤ 2/N, then ∑_{n=1}^{N} e(cn^{3}) ≪ N^{5/6}. Better still, show that this bound can be replaced by N^{3/4+ε}.

8. By writing n = mp^{2} + h, show that

∑_{n=1}^{p^{3}} e(\frac{n^{3}}{p^{3}} ) = ∑_{h=1}^{p^{2}} e(\frac{h^{3}}{p^{3}} ) ∑_{m=1}^{p} e(\frac{3mh^{2}}{p} ) .

(b) Deduce that if p ≠ 3, then the above is equal to p^{2}.

(c) By writing n = 3m + h, show that

∑_{n=1}^{27} e(\frac{n^{3}}{27} ) = ∑_{h=1}^{3} e(\frac{h^{3}}{27} ∑_{m=1}^{9} e(\frac{h^{2}m}{3}).

(d) Deduce that the above is = 9.

9. In many applications, such as in treating the sum ∑_{n=N}^{2N} n^{it}, we find that M_{r+1} ≍ M_{r}/N. Show that when this is the case, the best estimate from Theorem 17.11 is obtained by taking r so that

N^{−2+4/R} ≪_{r} M_{r} ≪_{r} N^{−1+2/R},

and that the estimate is then

≪_{r} NM_{r}^{1/(R−2)}.

10. Let f(x) be real valued with k + 1 continuous derivatives, and put

P (x) = ∑_{r=0}^{k} \frac{f^{(r)}(0)}{r!}x^{r}.

Then show that for k ≥ 1,

∑_{n=1}^{N} e(f(n)) ≪ S^{∗}(1 + MN^{k+1})

where

M = max_{0≤x≤N} \frac{|f^{(k+1)}(x)|}{(k + 1)!}, S^{∗} = max_{X≤N} ∑_{n≤X} e(P (n)).

17.3 van der Corput’s method

By means of the Weyl-van der Corput Lemma we may reduce the problem of estimating one exponential sum to that of estimating some other sums. We now use the Poisson summation formula to establish a second, quite different, transformation of the initial sum.

Theorem 17.12 Let f(x) be real valued, and suppose that f′(x) is continuous and increasing on the interval [a.b]. Put f′(a) = α and f′(b) = β. Then

(17.16)  ∑_{a≤n≤b} e(f(n)) = ∑_{α−1≤ν≤β+1} ∫_{a}^{b} e(f(x) − νx) dx + O(log(2 + β − α)).

Proof. Let N be an integer such that |N − (α + β)/2| ≤ 1/2. If we replace f(x) by f(x) − Nx, then the terms in the sum on the left are unchanged, f′(x) is still continuous and increasing, and the sum on the right is unchanged, although the indexing of the terms has been translated, as α has been replaced bt α′ = α − N, and β has been replaced by β′ = β − N. We note that α′ + β′ = α + β − 2N, so that |α′ + β′| ≤ 1. Thus by making a change of variable of this sort, we may suppose that |α + β| ≤ 1.

Let F (x) = e(f(x)) for a ≤ x ≤ b, and put F (x) = 0 otherwise. Then F ∈ L^{1}(ℝ) and F has bounded variation on ℝ, so by the Poisson summation formula (Theorem D.3),

∑_{n} \frac{1}{2}(F (n^{+}) + F (n^{−})) = lim_{K→∞} ∑_{k=−K}^{K} F̂(k) .

Since F (x) is continuous apart from possible jump discontinuities at a or b, the left hand side here is within O(1) of the left hand side in (17.16). The integral on the right in (16) is simply F̂(ν), so to complete the proof it suffices to show that

(17.17)  ∑_{\begin{matrix}|k|≤K \\ k∉[α−1,β+1] \end{matrix}} F̂(k) ≪ log(2 + β − α)

for all sufficiently large K. Integrating by parts, we find that

F̂(k) = \frac{e(f(a) − ka)}{2πik} − \frac{e(f(b) − kb)}{2πik} + \frac{1}{k} ∫_{a}^{b} f′(x)e(f(x) − kx) dx.

If k > β, then f′(x)/(f′(x) − k) is monotonic, so by Theorem 17.1 this integral is ≪ β/(k − β). We note that

∑_{k>β+1} \frac{β}{k(k − β)} ≍ log(2 + β).

We treat k < α similarly, and find that the left hand side of (17.17) is

\frac{e(f(a))}{2πi} ∑_{\begin{matrix}0<|k|≤K \\ k∉[α−1,β+1] \end{matrix}} \frac{e(−ka)}{k} − \frac{e(f(b))}{2πi} ∑_{\begin{matrix}0<|k|≤K \\ k∉[α−1,β+1] \end{matrix}} \frac{e(−kb)}{k} + O(log(2 + β − α)).

Since |α + β| ≤ 1, we may pair each k in these sums with −k, except for at most one k, whose contribution is bounded. Hence the above is

= e(f(b)) ∑_{β+1<k≤K} \frac{sin 2πkb}{πk} − e(f(a)) ∑_{β+1<k≤K} \frac{sin 2πka}{πk} + O(log(2 + β − α)).

That these sums are bounded can be seen from Theorem D.1, but we find the following direct argument to be instructive. It suffices to bound the first sum, which is an odd function of b with period 1. Hence it suffices to bound this sum when 0 ≤ b ≤ 1/2. For those k (if there are any) for which k ≤ 1/b, we use the inequality sin u ≤ u to see that the summand is ≤ 2b. Since the number of such k is ≪ 1/b, it follows that the total contribution of such terms is ≪ 1. By taking the imaginary part of (16.5) we see that

∑_{u≤k≤v} sin 2πkb ≪ \frac{1}{b} .

By summation by parts it follows that if u > 0, then

∑_{u≤k≤v} \frac{sin 2πkb}{πk} ≪ \frac{1}{ub} .

Since u ≥ 1/b in our application, this contribution is also bounded, and the proof is complete.

When we apply Theorem 17.12 to a function f(x) such that f′′(x) ≥ M_{2} > 0, then by Theorem 17.2 the integrals on the right hand side are ≪ M_{2}^{−1/2}. The number of terms in the sum on the right is f′(b) − f′(a) + O(1). If we suppose that f′′(x) ≤ AM_{2}, then the number of terms is ≪_{A} (b − a)M_{2} + 1, and thus the right hand side is ≪_{A} (b − a)M_{2}^{1/2} + M_{2}^{−1/2}. This provides a second (more complicated) proof of Theorem 17.4, but now we are in a position to determine whether there is any cancellation in the sum on the right in (17.16). To this end we must first derive a more precise estimate for the integrals in (17.16). Suppose that g(x) is a real-valued function on [a, b], that there is a point x_{0} ∈ [a, b] such that g′(x) = 0, and also that

(17.18)  0 < M_{2} ≤ g′′(x)

for x ∈ [a, b]. Let q(x) be the quadratic polynomial q(x) = g(x_{0}) + \frac{1}{2}g′′(x_{0})(x − x_{0})^{2}. we expect that q(x) provides a good approximation to g(x), at least when x is near x_{0}. Consider first the idealized situation in which g(x) is exactly equal to q(x). By (17.3) we see that

∫_{−∞}^{∞} e(q(x)) dx = e (g(x_{0}) + \frac{1}{8}) g′′(x_{0})^{− \frac{1}{2}} .

As q′(x) is increasing and q′(x) ≥ M_{2}(b − x_{0}) for x ≥ b, we see from Theorem 17.1 that

∫_{b}^{∞} e(q(x)) dx ≪ M_{2}^{−1}(b − x_{0})^{−1}.

This estimate is weak if x_{0} is close to b, in which case we use Theorem 17.2 instead and obtain

∫_{b}^{∞} e(q(x)) dx ≪ M_{2}^{− \frac{1}{2}} .

We may treat ∫_{−∞}^{a} e(q(x)) dx similarly, and thus we find that

(17.19)  ∫_{a}^{b} e(q(x)) dx = e (g(x_{0}) + \frac{1}{8}) g′′(x_{0})^{− \frac{1}{2}} + O(R_{1})

where

(17.20)  R_{1} = min (M_{2}^{−1}(x_{0} − a)^{−1}, M_{2}^{− \frac{1}{2}} ) + min (M_{2}^{−1}(b − x_{0})^{−1}, M_{2}^{− \frac{1}{2}} ) .

In the general case g(x) is not a quadratic polynomial, but if the higher derivatives of g are not too large, then the expression above provides a good approximation to the integral in question.

Theorem 17.13 Let g(x) be a thrice continuously differentiable real-valued function on [a, b]. Suppose that there is an x_{0} ∈ [a, b] such that g′(x_{0}) = 0, and that (17.18) holds throughout this interval. If |g′′′(x)| ≤ M_{3} for x ∈ [a, b], then

(17.21)  ∫_{a}^{b} e(g(x)) dx = e (g(x_{0}) + \frac{1}{8}) g′′(x_{0})^{−1/2} + O(R_{1}) + O(R_{2})

where R_{1} is given by (17.20) and

(17.22)  R_{2} = M_{2}^{−1}M_{3}^{1/3}.

If additionally g^{(4)}(x) exists, is continuous and |g^{(4)}(x)| ≤ M_{4} for x ∈ [a, b], then we may take

(17.23)  R_{2} = (b − a)M_{2}^{−2}M_{4} + (b − a)M_{2}^{−3}M_{3}^{2}.

If instead of (17.18) we have

(17.24)  g′′(x) ≤ −M_{2} < 0,

then we apply the theorem to −g(x) and take complex conjugates in (17.21). This gives a similar result, but the main term in (17.21) must be replaced by

(17.25)  e (g(x_{0}) − \frac{1}{8}) |g′′(x_{0})|^{−1/2}.

Proof. By (17.18) and Theorem 17.2 we know that the integral in (17.21) is ≪ M_{2}^{−1/2}. Thus if a ≤ x_{0} < a + M_{2}^{−1/2} or b − M_{2}^{−1/2} < x_{0} ≤ b, then there is nothing further to be done, in view of the error term R_{1}. Thus in continuing, we may assume that

(17.26)  a + M_{2}^{−1/2} ≤ x_{0} ≤ b − M_{2}^{−1/2}.

We multiply both sides of (17.21) by e(−g(x_{0})) to reduce to the case g(x_{0}) = 0. Similarly, we may translate the coordinates so that x_{0} = 0. We take q(x), as above, to be the Taylor approximation of order 2. Then g(x) = q(x) + r(x) where the remainder term r(x) may be written explicitly as

(17.27)  r(x) = \frac{1}{2}x^{3} ∫_{0}^{1}(1 − u)^{2}g^{(3)}(xu) du.

Similarly, q′(x) is the Taylor approximation of order 1 to g′(x), so the remainder term r′(x) can be written as

(17.28)  r′(x) = x^{2} ∫_{0}^{1}(1 − u)g^{(3)}(xu) du.

In view of (17.18), it suffices to show that

(17.29)  ∫_{a}^{b} e(q(x))(e(r(x)) − 1) dx ≪ R_{1} + R_{2}.

Let δ be a parameter at our disposal, and let ℐ = [c, d] denote the portion of the interval [a, b] for which |x| ≤ δ, and let 𝒥 = [a, b] \ ℐ. The set 𝒥 may be empty, but if it is not, then it consists of one or two intervals. By (17.18) we see that |g′(x)| ≥ δM_{2} for all x ∈ 𝒥. Hence, by Theorem 17.1 we find that

∫_{𝒥} e(g(x)) dx ≪ δ^{−1}M_{2}^{−1}.

Since q′′(x) = g′′(0) ≥ M_{2}, a similar argument applies to q(x), and so

(17.30)  ∫_{𝒥} e(q(x))(e(r(x)) − 1) dx ≪ δ^{−1}M_{2}^{−1}.

We now consider the integral (17.29), restricted to the interval ℐ. Since e(q(x))/(2πig′′(0)) is an antiderivative of xe(q(x)), we integrate by parts to see that the integral is

(17.31) = [\frac{e(q(x))(e(r(x)) − 1)}{2πig′′(0)x}|_{c}^{d} − \frac{1}{g′′(0)} ∫_{ℐ} e(q(x))(\frac{e(r(x))r′(x)}{x} − \frac{e(r(x)) − 1}{2πix^{2}}) dx.

Since d = min(b, δ), it follows that 1/d ≤ 1/b + 1/δ. Thus the upper endpoint contributes an amount

≪ b^{−1}M_{2}^{−1} + δ^{−1}M_{2}^{−1} ≪ R_{1} + δ^{−1}M_{2}^{−1}.

The lower endpoint is treated similarly. By (17.27) we see that r(x) ≪ |x|^{3}M_{3}, and by (28) we find that r′(x) ≪ x^{2}M_{3}. Using the inequality |e(u) − 1| ≤ 2π|u|, we deduce that the integrand is ≪ |x|M_{3}, and hence the second term in (17.31) is ≪ δ^{2}M_{2}^{−1}M_{3}. On comparing this with (17.30), we discover that the choice δ = M_{3}^{−1/3} is optimal. This gives (17.29) with R_{2} given by (17.22). Our choice of δ is plausible, since (17.27) allows us to show that r(x) is small precisely when x ∈ ℐ.

It remains to derive (17.21) with the refined error term (17.23). We integrate by parts as above, but take ℐ = [a, b]. Since d = b, the upper endpoint now contributes an amount ≪ b^{−1}M_{2}^{−1} ≪ R_{1}. The lower endpoint is treated similarly. Write the integral in (17.31) as T_{1} + T_{2} where T_{1} arises from the first term in brackets, and T_{2} from the second. Let h(x) = r′(x)x^{−2} and j(x) = g′(x)x^{−1}. Then

T_{1} = ∫_{a}^{b} \frac{h(x)}{j(x)}e(g(x))g′(x) dx = [\frac{h(x)e(g(x))}{j(x)2πi}]_{a}^{b} − ∫_{a}^{b} \frac{d}{dx} (\frac{h(x)}{j(x)}) \frac{e(g(x))}{2πi} dx.

Since h(x) is the integral in (17.28), we see that h(x) ≪ M_{3}. By differentiating this integral with respect to x, we find also that h′(x) ≪ M_{4}. Similarly j(x) = ∫_{0}^{1} g′′(xu) du ≥ M_{2} by (17.18), and j′(x) = ∫_{0}^{1} ug′′′(xu) du ≪ M_{3}. Hence

\frac{d}{dx} (\frac{h(x)}{j(x)}) = \frac{h′(x)}{j(x)} − \frac{h(x)j′(x)}{j(x)^{2}} ≪ \frac{M_{4}}{M_{2}} + \frac{M_{3}^{2}}{M_{2}^{2}} ,

so that

T_{1} ≪ M_{2}^{−1}M_{3} + M_{2}^{−1}M_{4}(b − a) + M_{2}^{−2}M_{3}^{2}(b − a).

To bound the integral T_{2} we follow the method used to derive the estimate (17.22). We let ℐ and 𝒥 be defined as before. Put k(x) = r(x)x^{−3}. By (27) we see that k(x) ≪ M_{3}, and that k′(x) ≪ M_{4}. Set m(x) = (e(x) − 1)/x. Then m(x) ≪ 1 and m′(x) ≪ 1. The contribution of the interval ℐ to T_{2} is

∫_{c}^{d} e(q(x))xm(r(x))k(x) dx = [\frac{e(q(x))}{2πig′′(0)}m(r(x))k(x)|_{c}^{d}

− ∫_{c}^{d} \frac{e(q(x))}{2πig′′(0)}(m′(r(x))r′(x)k(x) + m(r(x))k′(x)) dx

≪ M_{2}^{−1}M_{3} + M_{2}^{−1}M_{3}^{2}(d − c)^{3} + M_{2}^{−1}M_{4}(d − c).

In the second factor we use the inequality d − c ≤ δ, but in the third factor we use instead d − c ≤ b − a. Thus we find that

∫_{ℐ} e(q(x)) (\frac{e(r(x)) − 1}{2πix^{2}}) dx ≪ M_{2}^{−1}M_{3} + M_{2}^{−1}M_{3}^{2}δ^{3} + M_{2}^{−1}M_{4}(b − a).

With regard to the set 𝒥, we consider separately the integrals ∫_{𝒥} e(g(x))x^{−2} dx and ∫_{𝒥} e(q(x))x^{−2} dx. Applying Theorem 17.1 to the first of these integrals, we are lead to consider the function g′(x)x^{2}. The absolute value of this quantity is bounded below by M_{2}δ^{3}, and the expression is monotonic since its derivative is g′′(x)x^{2} + 2g′(x)x > 0. Thus by Theorem 17.1, ∫_{𝒥} e(g(x))x^{−2} dx ≪ M_{2}^{−1}δ^{−3}. Similarly, since q′(x)x^{2} = g′′(0)x^{3} is monotonic, ∫_{𝒥} e(q(x))x^{−2} dx ≪ M_{2}δ^{−3}. On combining these estimates, we conclude that

T_{2} ≪ M_{2}^{−1}M_{3} + M_{2}^{−1}M_{3}^{2}δ^{3} + M_{2}^{−1}M_{4}(b − a) + M_{2}^{−1}δ^{−3}.

To optimise this estimate we again take δ = M_{3}^{−1/3}. We combine this with our estimate for T_{1} to see that the integral in (17.31) is

≪ R_{1} + M_{2}^{−1}(T_{1} + T_{2})
≪ R_{1} + M_{2}^{−2}M_{3} + M_{2}^{−2}M_{4}(b − a) + M_{2}^{−3}M_{3}^{2}(b − a).

Put U = M_{2}^{−1}(b−a)^{−1}. The second term above is the geometric mean of U and the fourth term. By (26) we deduce that U ≪ R_{1}, so the second term is majorised by the maximum of the first and fourth terms, and therefore may be omitted. Thus we have (17.21) with the error term (17.23), and the proof is complete.

Theorem 17.14 Let N be a positive integer and a ≤ b ≤ a + N, suppose that f is thrice continuously differentiable on [a, b] and that

0 < M_{2} ≤ f′′(x) ≤ AM_{2}, |f′′′(x)| ≤ M_{3}.

Let α = f′(a), β = f′(b) and for each integer ν in [α, β] let x_{ν} be defined by f′(x_{ν}) = ν. Then

∑_{a≤n≤b} e(f(n)) = ∑_{α≤ν≤β} \frac{e (f(x_{ν}) − νx_{ν} + 1/8)}{\sqrt{f′′(x_{ν})}} + O_{A}(E_{1} + E_{2})

where

E_{1} = log(2 + M_{2}N) + M_{2}^{−1/2}

and

(17.32)  E_{2} = M3^{\frac{1}{3}} N.

If, moreover, f^{(4)}(x) exists, is continuous and satisfies |f^{(4)}(x)| ≤ M_{4} on [a, b], then (17.32) may be replaced by

(17.33)  E_{2} = \frac{M_{4}}{M_{2}} N^{2} + \frac{M_{3}^{2}}{M_{2}^{2}} N^{2}.

If instead

0 < M_{2} ≤ −f′′(x) ≤ AM_{2},

then the above holds with α = f′(b), β = f′(a), 1/8 replaced by −1/8 and the f′′(x_{ν}) in the sum on the right replaced by −f′′(x_{ν}).

Proof. We may suppose that M_{2} ≥ N^{−2} for otherwise the conclusion is trivial since the number of terms on the left is at most N + 1 and E_{1} ≫ M_{2}^{−1/2}. By Theorem 17.12,

∑_{a≤n≤b} e(f(n)) = ∑_{α−1≤ν≤β+1} ∫_{a}^{b} e(f(x) − νx) dx + O(log(2 + β − α)).

By Theorem 17.2,

(17.34)  ∫_{a}^{b} e(f(x) − νx) dx ≪ M_{2}^{− \frac{1}{2}} .

uniformly in ν, and

(17.35)  β − α = (b − a)f(ξ) ≪_{A} M_{2}N.

Hence

∑_{a≤n≤b} e(f(n)) = ∑_{α≤ν≤β} ∫_{a}^{b} e(f(x) − νx) dx + O_{A}(E_{1}).

If β − α ≤ 1, then by (17.34) we are done. Thus we may suppose that β − α > 1, and then by (17.35) the sum on the right is non-empty and the number of terms is

(17.36)  ∑_{α≤ν≤β} 1 ≍_{A} M_{2}N.

By Theorem 17.13 we may replace each integral on the right by

\frac{e (f(x_{ν}) − νx_{ν} + 1/8)}{\sqrt{f′′(x_{ν})}}

with an error

(17.37) ≪ M_{2}^{−1}M3^{\frac{1}{3}} + min (M_{2}^{−1}(x_{ν} − a)^{−1}, M_{2}^{− \frac{1}{2}} ) + min (M_{2}^{−1}(b − x_{ν})^{−1}, M_{2}^{− \frac{1}{2}} ) .

By (17.36) the first term contributes a total amount ≪ M3^{\frac{1}{3}} N = E_{2}. To treat the second term we observe that ν − α = f′(x_{ν}) − f′(a) = (x_{ν} − a)f′′(ξ) ≤ AM_{2}(x_{ν} − a) and so the second term is bounded by

min (\frac{A}{ν − α}, M_{2}^{− \frac{1}{2}} ) .

Thus the total contribution from the second term is

≪_{A} M_{2}^{− \frac{1}{2}} + ∑_{α+1≤ν≤β} \frac{1}{ν − α} ≪ E_{1}.

Likewise the same upper bound holds for the contribution from the third term. The first part of the theorem now follows. For the second part we appeal to the concomitant part of Theorem 17.13. Then the

term M_{2}^{−1}M_{3}^{1/3} in (17.37) is replaced by

(b − a)M_{2}^{−2}M_{4} + (b − a)M_{2}^{−3}M_{3}^{2}

and so by (17.36) the total contribution is

≪ \frac{M_{4}}{M_{2}} N^{2} + \frac{M_{3}^{2}}{M_{2}^{2}} N^{2}.

Corollary 17.15 Suppose that ℐ is a sub-interval of [N, 2N], f has four continuous derivatives on ℐ, and that there are positive real numbers A, λ, θ such that on ℐ

0 < λN^{−θ−1} ≤ f^{(2)}(x) ≤ AλN^{−θ−1},
|f^{(3)}(x)| ≤ AλN^{−θ−2},
|f^{(4)}(x)| ≤ AλN^{−θ−3}

for x ∈ ℐ. Then the error term is

≪_{A} log(2 + λN^{−θ}) + λ^{− \frac{1}{2}} N^{\frac{θ+1}{2}} .

The proof is immediate on observing that the contribution from E_{2}, given by (17.33), is ≪ 1, which can be absorbed in the logarithmic term.

The conditions of the above Corollary are those which are very largely met in applications.

We now have two essentially different lines of approach for dealing with a given exponential sum. In each of these we begin by transforming the sum into a new one. The first of these is via the Weyl–van der Corput lemma (Lemma 17.5). The second is via Theorem 17.14 (or, usually more conveniently, via Corollary 17.15). With either of these processes the presumption is that the transformed sum is one about which we already have information. The normal requirement is that the function f behaves somewhat like that considered in the above Corollary. To this end we define the following class of functions.

Defintion 17.1 Let N, λ, θ, ε be positive real numbers, let r be a positive integer and let ℐ be a subinterval of [N, 2N]. Let

(17.38)  ϕ(x) = \{ \begin{matrix}\frac{λx^{1−θ}}{1−θ} & when θ ≠ 1, \\ λ log x & otherwise. \end{matrix}

We define ℱ(N, ℐ, λ, θ, r, ε) to be the set of functions f r-times continuously differentiable on ℐ and which for each s with 1 ≤ s ≤ r and x ∈ ℐ satisfy

(17.39)  |f^{(s)}(x) − ϕ^{(s)}(x)| < ε|ϕ^{(s)}(x)|.

We are now in a position to define precisely what we mean by exponent pairs.

Definition 17.2 An exponent pair is a pair (k, l) of real numbers k and l satisfying

(17.40)  0 ≤ k ≤ \frac{1}{2} ≤ l ≤ 1

and such that for every θ > 0 there is an integer r = r(k, l, θ) ≥ 2 and an ε = ε(k, l, θ) satisfying 0 < ε < 1/2 for which for every N > 0, λ > 0, ℐ ⊂ [N, 2N] and f ∈ ℱ(N, ℐ, λ, θ, r, ε) we have

(17.41)  ∑_{n∈ℐ}e(f(n)) ≪ (λN^{−θ})^{k} N^{l} + λ^{−1}N^{θ}.

There are a number of observations which can be made.

1. In establishing that a particular pair is an exponent pair we may suppose that

(17.42)  λN^{−θ} ≥ 1

for otherwise the inequality always holds. To see this we consider two cases. First of all if λN^{−θ} < 1/2, then by the Corollary 17.4 we have at once

∑_{n∈ℐ}e(f(n)) ≪ λ^{−1}N^{θ}.

Secondly, if 1/2 ≤ λN^{−θ} < 1, then by Theorem 17.5, since l ≥ 1/2, we have

∑_{n∈ℐ}e(f(n)) ≪ N^{\frac{1}{2}} ≪ (λN^{−θ})^{k}N^{l}.

Henceforward we always assume (17.42).

2. By examining some special functions f we can explain why we have imposed the conditions (17.40) on the ordered pairs. Let m be a positive integer, let M = [N], let λ = mlcm(1, 2, …, 2M) and let

f(x) = −\frac{λ}{x}.

Then f(n) ∈ ℤ for 1 ≤ n ≤ 2N so that

∑_{M+1≤n≤2M} e(f(n)) = M ≫ N.

Suppose that m is large. In particular λN^{−2} will be large, and f′(x) = λx^{−2} > 1 on [M + 1, 2M]. Thus any exponent pair has to satisfy

N ≪ (λN^{−2})^{k}N^{l}

Moreover since λ is arbitrarily large we cannot have k < 0. As an additional observation here we see that if k = 0 we will have to have l ≥ 1 and since we have imposed the condition l ≤ 1 in (17.40) we find that

k = 0 ⟹ l = 1.

In other words, the only permissible exponent pair with k = 0 is the “trivial” pair (0, 1).

3. Suppose we have an exponent pair with l > 1. In view of (17.42) the bound (17.41) would then be worse than (k, 1) (and this in turn would be worse than the trivial pair (0, 1)). This explains why we have imposed the condition l ≤ 1 in (17.40).

4. Consider the expression

∫_{Λ}^{2Λ} | ∑_{M+1}^{2M} e (−λn^{−1})|^{2} dλ

where M = [N]. The numbers 1/n with M +1 ≤ n ≤ 2M are spaced at least δ = \frac{1}{2M(2M+1)} apart. Let S_{−}(x) be the function of Theorem D.6 with α = Λ, β = 2Λ and δ as above. Then the above integral is at least

∫_{−∞}^{∞} S_{−}(λ) | ∑_{M+1}^{2M} e (−λn^{−1})|^{2} dλ = ∑_{m=M+1}^{2M} ∑_{n=M+1}^{2M} Ŝ_{−} (\frac{1}{m} − \frac{1}{n})
= Ŝ_{−}(0)M
= (Λ − 2M(2M + 1))M.

Thus we see that if Λ = 4M(2M + 1), then there is a λ ∈ [Λ, 2Λ] such that

| ∑_{n=M+1}^{2M} e(f(n))| ≫ N^{\frac{1}{2}}

where f(x) = −λ/x. Now f′(x) = λx^{−2} and so if (k, l) is an exponent pair we would have

N^{\frac{1}{2}} ≪ (λN^{−2})^{k}N^{l} + N^{2}λ^{−1} ≪ N^{l}

since we have already seen the necessity of imposing the condition k ≥ 0 in (17.40). Thus we see that it is necessary also to impose the condition \frac{1}{2} ≤ l in (17.40).

5. A direct application of Theorem 17.5 shows that

(17.43)  (\frac{1}{2}, \frac{1}{2})

is an exponent pair. Thus if we had an exponent pair (k,l) with k ≥ \frac{1}{2}, since of necessity we have l ≥ \frac{1}{2}, the exponent pair (17.43) is superior. Thus we can restrict our attention to k ≤ \frac{1}{2}, which explains this condition in (17.40).

6. Finally we show that (\frac{1}{2}, \frac{1}{2}) is the only permissible exponent pair with l = \frac{1}{2}. Let M be an arbitrary positive integer and define λ to be the positive number with λ^{2} = lcm\{1, 2, …, M\}. Now let N = λ^{2}H^{−2} and f(x) = 2λx^{\frac{1}{2}} and suppose that (k, \frac{1}{2}) is an exponent pair, so that 0 ≤ k ≤ \frac{1}{2}. Then

∑_{N<n≤2N} e(f(n)) ≪ (λN^{− \frac{1}{2}} )^{k} N^{\frac{1}{2}} + λ^{−1}N^{\frac{1}{2}}

and λN^{− \frac{1}{2}} = H so that

∑_{N<n≤2N} e(f(n)) ≪ H^{k}N^{\frac{1}{2}} + H^{−1} ≪ H^{k}N^{\frac{1}{2}} .

By the Corollary 17.15 we have

∑_{a≤n≤b} e(f(n)) = ∑_{α≤ν≤β} \frac{e (f(x_{ν}) − νx_{ν} − 1/8)}{\sqrt{−f′′(x_{ν})}} + O_{A} (log(2 + H) + N^{\frac{1}{2}} H^{− \frac{1}{2}} )

where α = \frac{H}{\sqrt{2}}, β = H, x_{ν} = λ^{2}ν^{−2},

−f′′(x_{ν}) = \frac{1}{2}ν^{3}λ^{−2} ≫ HN^{−1},

f(x_{ν}) − νx_{ν} = t^{2}ν^{−1} ∈ ℤ.

Hence

| ∑_{n<n≤2N} e(f(n))| ≫ H^{\frac{1}{2}} N^{\frac{1}{2}} .

Thus

(17.44)  l = \frac{1}{2} ⟹ k = \frac{1}{2}.

7. The set of exponent pairs forms a convex set, since given any two exponent pairs (k′, l′), (k′′, l′′) we have (assuming (17.42), of course)

∑_{n∈I} e(f(n)) ≪ min ((λN^{−θ})^{k′}N^{l′}, (λN^{−θ})^{k′′}N^{l′′})

and for any η with 0 ≤ η ≤ 1 we can replace this by

(λN^{−θ})^{k}N^{l}

with k = k′η + k′′(1 − η), l = l′η + l′′(1 − η). In particular we see that the pairs

(k, 1 − k) with (0 ≤ k ≤ \frac{1}{2})

are all exponent pairs. Moreover, given any pair above this line, there will always be one on the line which gives superior bounds. Thus in practice the main interest lies in finding suitable exponent pairs below this line.

We now proceed to show how when we apply the Weyl–van der Corput Lemma the parameters describing the functions arising in the transformed sums are related to those of the original function.

Lemma 17.16 Suppose

f ∈ ℱ(N, [a, b], λ, θ, r, ε)

and that

1 ≤ h ≤ min (b − a, \frac{2εN}{r + θ} ) .

Let 𝒥 = [a, b − h] and f_{1}(x) = f(x; h) = f(x) − f(x + h). Then

f_{1} ∈ ℱ(N, 𝒥, λθh, θ + 1, r − 1, 3ε)

17.3 van der Corput’s method 605

Proof. This is a simple verification. Let

ϕ_{1}(x) = ϕ_{1}(x; h) = ϕ(x) − ϕ(x + h), ψ(x) = −λθhx^{−θ}.

The latter of these two functions plays the same rôle for f_{1} that ϕ does for f. For 1 ≤ s ≤ r − 1 we have

f_{1}^{(s)}(x) − ϕ_{1}^{(s)}(x) = − ∫_{x}^{x+h} (f^{(s+1)}(y) − ϕ^{(s+1)}(y)) dy

and in modulus this does not exceed

∫_{x}^{x+h} ε|ϕ^{(s+1)}(y)| dy = ε|ϕ_{1}^{(s)}(x)|.

We also have hϕ′(x) = −ψ(x), so that

ϕ_{1}^{(s)}(x) − ψ^{(s)}(x) = − ∫_{x}^{x+h} (ϕ^{(s+1)}(y) − ϕ^{(s+1)}(x)) dy
= − ∫_{x}^{x+h} (∫_{x}^{y} ϕ^{(s+2)}(z) dz) dy

and in modulus this does not exceed

\frac{1}{2}h^{2}|ϕ^{(s+2)}(x)| = \frac{1}{2}h|ψ^{(s+1)}(x)| ≤ ε|ψ^{(s)}(x)|.

Combining inequalities we have

|ϕ_{1}^{(s)}(x)| < (1 + ε)|ψ^{(s)}(x)|

and

|f_{1}^{(s)}(x) − ψ^{(s)}(x)| < ε (|ϕ_{1}^{(s)}(x)| + |ψ^{(s)}(x)|) < (2ε + ε^{2})|ψ^{(s)}(x)|.

The next theorem is the formal statement which describes process “A”. Theorem 17.17 Suppose that (k, l) is and exponent pair. Then so is

(k′, l′) = A(k, l) = (\frac{k}{2k + 2}, \frac{k + l + 1}{2k + 2}) .

Proof. We first check that 0 ≤ k′ ≤ \frac{1}{2} ≤ l′ ≤ 1. We have 0 ≤ \frac{k}{2k+2} < \frac{k+1}{2k+2} = \frac{1}{2} and \frac{1}{2} ≤ \frac{1}{2} + \frac{l}{2k+2} = \frac{k+l+1}{2k+2} ≤ \frac{1}{2} + \frac{1}{2k+2} ≤ 1. We now show that there exist r′ ≥ 2, ε′ with 0 < ε′ < \frac{1}{2} such that if ℐ = [a, b] with N ≤ a ≤ b ≤ 2N, and

f ∈ ℱ(N, ℐ, λ, θ, r′, ε′), 606 Exponential sums then

∑_{n∈ℐ}e(f(n)) ≪ (λN^{−θ})^{k′}N^{l′}.

We observe that

l′ = \frac{1}{2} + \frac{l}{2k + 2} ≥ \frac{1}{2} + \frac{1/2}{2 · \frac{1}{2} + 2} = \frac{2}{3}.

As usual we may assume (17.42). Hence we may suppose that

(17.45)  |ℐ| > N^{\frac{2}{3}}

for otherwise the conclusion is immediate. When 1 ≤ λN^{−θ} ≤ N^{\frac{1}{6}} we have, by Theorem 17.5,

∑_{n∈ℐ}e(f(n)) ≪ (λN^{−θ−1})^{\frac{1}{2}} N + (λ^{−1}N^{θ+1})^{\frac{1}{2}} ≪ N^{\frac{2}{3}}

which is more than sufficient. Thus we may also suppose that

(17.46)  λN^{−θ} ≥ N^{\frac{1}{6}} .

Suppose that r ≥ 1 + r(k, l), 0 < ε ≤ \frac{1}{3}ε(k, l) and

f ∈ ℱ(N, [a, b], λ, θ, r, ε).

Let

S = ∑_{n∈ℐ}e(f(n)).

By the Weyl–van der Corput Lemma (Lemma 17.6) we have

|S|^{2} ≪ N^{2}H^{−1} + NH^{−1} ∑_{1≤h≤H} |S_{1}(h)|

where we take ℐ = [a, b] and

S_{1}(h) = ∑_{a<n≤b−h} e(f_{1}(n; h)),

and we suppose that

(17.47)  1 ≤ H ≤ min (b − a, \frac{2εN}{r + θ} )

and H is otherwise at our disposal. Let 𝒥 = [a, b − h]. Then, by Lemma 17.16, f_{1} ∈ ℱ(N, 𝒥, λθh, θ + 1, r − 1, 3ε) and by the choices made for r and ε above we see that the exponent pair (k, l) applies to f_{1}. Thus

|S|^{2} ≪ N^{2}H^{−1} + NH^{−1} ∑_{1≤h≤H} ((hλN^{−θ−1})^{k} N^{l} + h^{−1}λ^{−1}N^{θ+1})

≪ N^{2}H^{−1} + N^{l+1−k(θ+1)}λ^{k}H^{k} + N^{θ+2}λ^{−1}H^{−1} log N. (17.48)

By (17.46) the last term is bounded by the first. The good choice for H would be given by

(17.49)  H^{k+1} = N^{−l+1+k(θ+1)}λ^{−k}

provided that this does not violate (17.47), and this leads to the bound

S ≪ (λN^{−θ})^{\frac{k}{2k+2}} N^{\frac{k+l+1}{2k+2}}

as required. If (17.49) violates (17.47), then we take

H = min (b − a, \frac{2εN}{r + θ} ) .

In this case the first term on the left of (17.48) will dominate the first. Hence by (17.45) we have

S ≪ NH^{− \frac{1}{2}} ≪ N^{\frac{2}{3}}

and the theorem follows once more.

We now come to the second process, process “B”. This corresponds to applying the Poisson summation formula as embodied in Corollary 17.15. For a suitable function f we need to understand how the function f(x(y)) − yx(y) behaves when x and y are related by

(17.50)  f′(x(y)) = y.

Let

(17.51)  g(y) = yx(y) − f(x(y)).

The function x(y) is the inverse function of f′, so we have

(17.52)  x′(y) = 1/f′′(x(y))

and

(17.53)  g′(y) = x(y) + yx′(y) − f′(x(y))x′(y) = x(y).

In the special case

f(x) = ϕ(x)

we have

f′(x) = λx^{−θ}, x(y) = λ^{1/θ}y^{−1/θ}.

Let

(17.54)  ψ(y) = \{ \begin{matrix}\frac{λ^{1/θ}y^{1−1/θ}}{1−1/θ} & when θ ≠ 1, \\ λ log y & when θ = 1. \end{matrix}

Then in general we can expect that if f is close to ϕ, then g is close to ψ. We need to show that our concept of close in terms of the first r derivatives of f and ϕ carries through to g and ψ. We have

(17.55)  g′′(y) = \frac{1}{f′′(x(y))}

and it is an easy induction on s to show that for 3 ≤ s ≤ r there are coefficients c_{s}(t) which depend only s and t such that

(17.56) g^{(s)}(y) = \frac{1}{f′′(g′(y))^{2s−3}} ∑_{t_{1}=2}^{s} ⋯ ∑_{{t_{s−2}=2 \atop t_{1}+···+t_{s−2}=3s−6}}^{s} c_{s}(t)f^{(t_{1})}(g′(y)) … f^{(t_{s−2})}(g′(y)),

and with an obvious convention for an empty product of sums this also holds when s = 2.

Lemma 17.18 Suppose

f ∈ ℱ(N, [a, b], λ, θ, r, ε)

and let α = f′(b), β = f′(a), and g, ψ be defined as above. Then there is a positive number C = C(θ, r) such that

|g^{(s)}(y) − ψ^{(s)}(y)| < Cε|ψ^{(s)}(y)|

whenever 1 ≤ s ≤ r and y ∈ [α, β].

Proof. We have α ≥ (1−ε)λ(2N)^{−θ} and β ≤ (1+ε)λN^{−θ}. Also, for x ∈ [N, 2N] we have ϕ′(x) ≤ λN^{−θ}, and for y ∈ [α, β] we have, by (17.54), ψ′(y) ≤ λ^{1/θ}α^{−1/θ} ≤ (1 − ε)^{−1/θ}2N and ψ′(y) ≥ λ^{1/θ}β^{−1/θ} ≥ (1 + ε)^{−1/θ}N.

By (17.53) and the facts that x(y) is the inverse function of f′ and ψ′ is the inverse function of ϕ′ we have

ϕ′(g′(y)) − f′(g′(y)) = ϕ′(g′(y)) − y = ϕ′(g′(y)) − ϕ′(ψ′(y))

and by the first mean value of the differential calculus this is

(g′(y) − ψ′(y))ϕ′′(ξ)

where ξ lies between g′(y) and ψ′(y). Thus |ϕ′′(ξ)| ≥ θλ(1 − ε)^{1+1/θ}(2N)^{−θ−1} and so

|ϕ′(x(y)) − f′(x(y))| ≥ |g′(y) − ψ′(y)|θλ(1 − ε)^{1+1/θ}(2N)^{−θ−1}.

Hence

|g′(y) − ψ′(y)| ≤ θ^{−1}λ^{−1}(1 − ε)^{−1−1/θ}(2N)^{θ+1}εϕ′(x(y))
≤ θ^{−1}(1 − ε)^{−1−1/θ}2^{θ+1}εN
≤ θ^{−1}(1 − ε)^{−1−1/θ}2^{θ+1}(1 + ε)^{1/θ}εψ′(y).

This settles the first derivative. To deal with higher derivatives we use (56) both as stated and in the special case f′ = ϕ′ (and so g′ = ψ′). Consider the effect first of all on a single monomial term in the sum (17.56) of replacing f′ by ϕ′. We have an expression of the general shape

F (z_{1}, …, z_{k}) = cz_{1}^{−m}z_{2} … z_{k}.

Moreover

F (z_{1}, …, z_{k})−F (w_{1}, …, w_{k})

= ∑_{j=1}^{k} (F (z_{1}, …, z_{j}, w_{j+1}, …, w_{k}) − F (z_{1}, …, z_{j−1}, w_{j}, …, w_{k}))

and by the mean value theorem of the differential calculus, provided z_{1} and w_{1} have the same sign, the general term here is of the form

(z_{j} − w_{j})F_{j}(z_{1}, …, z_{j−1}, ξ_{j}, w_{j+1}, …, w_{k})

where ξ_{j} lies between z_{j} and w_{j}. Thus in considering g^{(s)}(y)−ψ^{(s)}(y) the difference z_{j} −w_{j} becomes an expression of the form f^{(t)}(g′(y)) − ϕ^{(t)}(ψ′(y)) = f^{(t)}(g′(y)) − ϕ^{(t)}(g′(y)) + ϕ^{(t)}(g′(y)) − ϕ^{(t)}(ψ′(y)). The first difference here is bounded by ε|ϕ^{(t)}(g′(y))| and to the second we may apply the mean value theorem once more to obtain (g′(y) − ψ′(y))ϕ^{(t+1)}(ξ) and to this we can apply the first derivative bound obtained above. Thus

|f^{(t)}(g′(y)) − ϕ^{(t)}(ψ′(y))| ≤ ε|ϕ^{(t)}(g′(y))| + C′ε|ψ′(y)||ϕ^{(t+1)}(ξ)|.

A straightforward calculation now completes the argument.

Theorem 17.19 Suppose that (k, l) is an exponent pair. Then so is

(k′, l′) = B(k, l) = (l − \frac{1}{2}, k + \frac{1}{2}) .

Proof. It is immediate that if (k, l) is an exponent pair, then 0 ≤ l − \frac{1}{2} ≤ \frac{1}{2} ≤ k + \frac{1}{2}. Also, we know that (0, 1) and (\frac{1}{2}, \frac{1}{2}) are exponent pairs and there are no others with l = \frac{1}{2}. Hence we may suppose that l > 1/2.

Choose r ≥ max(3, r(k, l, 1/θ) and let C = C(θ, r) be as in Lemma 17.18. Then choose ε′ so small that

0 < ε′ ≤ min(1, C^{−1})ε(k, l, 1/θ).

Let f ∈ ℱ(N, ℐ, λ, θ, r, ε). Choose a, b so that I = [a, b] and define α = f′(b), β = f′(a). Now suppose that 𝒥 = [M, M′] ⊂ [α, β] with M′ ≤ 2M. Then the function g defined by (17.51) certainly includes 𝒥 in its support, and so by Lemma 17.18, g ∈ ℱ(M, J, λ^{1/θ}, 1/θ, r, ε′). Hence

∑_{n∈𝒥}e(−g(n)) ≪ (λ^{1/θ}M^{−1/θ})^{k} M^{l} + λ^{−1/θ}M^{1/θ}

We have λN^{−θ} ≪ α ≤ β ≪ λN^{−θ}, and as usual we are assuming (17.42). Summing over M = α, 2α, … we see that for any interval 𝒦 = [α, γ] with α ≤ γ ≤ β we have

∑_{n∈𝒦} e(−g(n) ≪ N^{k}(λN^{−θ})^{l} + N^{−1}.

Moreover, −f′′(x(n)) ≍ λN^{−1−θ} where x(y) is given by (17.40), and since r ≥ 3, f′′ is monotonic. Hence, by partial summation

∑_{n∈[α,β]} \frac{e(−g(n))}{\sqrt{−f′′(x(n))}} ≪ N^{k}(λN^{−θ})^{l}λ^{− \frac{1}{2}} N^{\frac{1}{2} + \frac{θ}{2}} + N^{−1}λ^{− \frac{1}{2}} N^{\frac{1}{2} + \frac{θ}{2}}
≪ (λN^{−θ})^{l− \frac{1}{2}} N^{k+ \frac{1}{2}} + λ^{− \frac{1}{2}} N^{\frac{1}{2} + \frac{θ}{2}} .

Thus, by the Corollary 17.15,

∑_{n∈ℐ}e(f(n)) ≪ (λN^{−θ})^{l− \frac{1}{2}} N^{k+ \frac{1}{2}} + log(1 + λN^{−θ}) + λ^{− \frac{1}{2}} N^{\frac{1}{2} + \frac{θ}{2}} .

By (17.42) and the fact that k ≥ 0 the second term is easily seen to be dominated by the first. Likewise, the third term is bounded by N^{1/2} which is also dominated by the first term. This completes the proof of the theorem.

We can now compute some exponent pairs. It is normal to start from the trivial exponent pair (0, 1). This is equivalent to taking the trivial bound for an exponential sum at the final stage.

B(0, 1) = (\frac{1}{2}, \frac{1}{2}), AB(0, 1) = (\frac{1}{6}, \frac{2}{3}), A^{2}B(0, 1) = (\frac{1}{14}, \frac{11}{14}), BA^{2}B(0, 1) = (\frac{2}{7}, \frac{4}{7}),
ABA^{2}B(1, 0) = (\frac{1}{9}, \frac{13}{18}), BABA^{2}B(0, 1) = (\frac{2}{9}, \frac{11}{18}), A^{2}BA^{2}B(0, 1) = (\frac{1}{20}, \frac{33}{40}),
A^{3}B(0, 1) = (\frac{1}{30}, \frac{13}{15}), BA^{3}B(0, 1) = (\frac{11}{30}, \frac{8}{15}), ABA^{3}B(0, 1) = (\frac{11}{82}, \frac{57}{82}),
A^{2}BA^{3}B(0, 1) = (\frac{11}{186}, \frac{25}{31}), BA^{2}BA^{3}B(0, 1) = (\frac{19}{62}, \frac{52}{93}), BABA^{3}B(0, 1) = (\frac{8}{41}, \frac{26}{41}),
ABABA^{3}B(0, 1) = (\frac{4}{49}, \frac{75}{98}), BABABA^{3}B(0, 1) = (\frac{13}{49}, \frac{57}{98}),
A^{4}B(0, 1) = (\frac{1}{62}, \frac{57}{62}), BA^{4}B(0, 1) = (\frac{13}{31}, \frac{16}{31}), ABA^{4}B(0, 1) = (\frac{13}{88}, \frac{15}{22}),
BA^{2}BA^{2}B(0, 1) = (\frac{13}{40}, \frac{11}{20}), BABA^{4}B(0, 1) = (\frac{2}{11}, \frac{57}{88}).

Figure 17.3 Some exponent pairs.

Note that

BA^{2}B(0, 1), BABA^{4}B(0, 1), BAB(0, 1) = AB(0, 1), A^{2}B(0, 1), ABA^{4}B(0, 1)

lie inside the convex hull of the others so always give inferior bounds to some combination of the others. In many applications one needs to minimise k + l, and then the best of the above exponent pairs is (\frac{11}{82}, \frac{57}{82}) or (\frac{8}{41}, \frac{26}{41}).

We now return to the question of bounding the Riemann zeta function on the \frac{1}{2}-line.

Theorem 17.20 Let τ = |t| + 4 and let (k, l) be an exponent pair. Then for any real t,

ζ (\frac{1}{2} + it) ≪ τ^{\frac{k}{2} + \frac{l}{2} − \frac{1}{4}} log τ.

Proof. The pattern has already been set in Theorem 17.10, where in retrospect we see that that conclusion follows from the exponent pair (\frac{1}{6}, \frac{2}{3}). Following the proof there we see that it suffices to show that when a ≤ b ≤ 2a and a ≤ τ^{2} we have

∑_{a≤n≤b} n^{it} ≪ a^{\frac{1}{2}} τ^{η}

where

η = η(k, l) = \frac{k}{2} + \frac{l}{2} − \frac{1}{4}.

Again as in Theorem 17.10, this is immediate from the Corollary 17.4 when τ < a ≤ τ^{2}. By the exponent pairs (k, l) and B(k, l) = (l − \frac{1}{2}, k + \frac{1}{2}), we see that

∑_{a≤n≤b} n^{it} ≪ min ((τa^{−1})^{k}a^{l}, (τa^{−1})^{l− \frac{1}{2}} a^{k+ \frac{1}{2}} ) + τ^{−1}a
≪ a^{\frac{1}{2}} min (a^{l−k− \frac{1}{2}} τ^{k}, a^{k−l+ \frac{1}{2}} τ^{l− \frac{1}{2}} ) + 1.

We replace the minimum of a^{l−k− \frac{1}{2}} τ^{k} and a^{k−l+ \frac{1}{2}} τ^{l− \frac{1}{2}} by their geometric mean to obtain the desired conclusion.

The following corollary is immediate from the exponent pair (\frac{11}{82}, \frac{57}{82}) .

Corollary 17.21 Let τ = |t| + 4. Then for any real t,

ζ (\frac{1}{2} + it) ≪ τ^{\frac{27}{164}} log τ.

Many questions in analytic number theory can be rephrased in terms of the saw-tooth function

(17.57)  s(x) = x − [x] − \frac{1}{2}

and it is natural to consider approximating this function by trigonometric polynomials and thereby relate the original question to the theory of exponential sums.

Theorem 17.22 Suppose that (k, l) is an exponent pair and that θ > 0. Let r = r(k, l, θ), ε = ε(k, l, θ), N > 0, λ > 0, ℐ ⊆ [N, 2N] and f ∈ ℱ(N, ℐ, λ, θ, r, ε). Then

∑_{n∈ℐ}s(f(n)) ≪ (λN^{−θ})^{\frac{k}{k+1}} N^{\frac{k+l}{k+1}} + λ^{−1}N^{θ}.

Proof. By Exercise E.1.1.3(a) there are trigonometric polynomials

T_{J}^{±}(x) = ∑_{0<|j|≤J} T̂_{J}^{±}(j)e(xj)

such that

(17.58)  T̂_{J}^{±}(j) ≪ \frac{1}{j}

and

T_{J}^{−}(x) − \frac{1}{2J + 2} ≤ s(x) ≤ T_{J}^{+}(x) + \frac{1}{2J + 2}.

Hence

∑_{n∈ℐ}s(f(n))

lies between

−\frac{N}{2J + 2} + ∑_{0<|j|≤J} T̂_{J}^{−}(j) ∑_{n∈ℐ}e(jf(n))

and

\frac{N}{2J + 2} + ∑_{0<|j|≤J} T̂_{J}^{+}(j) ∑_{n∈ℐ}e(jf(n))

Moreover, for f ∈ ℱ(N, ℐ, λ, θ, r, ε) we have |j|f ∈ ℱ(N, ℐ, |j|λ, θ, r, ε) and so the exponent pair (j, l) applies to each of the sums

∑_{n∈ℐ}e(jf(n)).

Therefore, by (17.58),

∑_{n∈ℐ}s(f(n)) ≪ \frac{N}{J + 1} + ∑_{j=1}^{J} \frac{1}{j} ((jλN^{−θ})^{k}N^{l} + j^{−1}λ^{−1}N^{θ})

≪ \frac{N}{J + 1} + (JλN^{−θ})^{k}N^{l} + λ^{−1}N^{θ}.

A good choice for J is

J = [λ^{− \frac{k}{k+1}} N^{\frac{1+kθ−l}{k+1}} ]

and this gives the desired conclusion when k ≠ 0. When k = 0 we have l = 1 and the conclusion is trivial.

One obvious application of the above is to the Dirichlet divisor problem.

Theorem 17.23 Let Δ(x) = ∑_{n≤x} d(n) − x log x − (2C_{0} − 1)x, and suppose that (k, l) is an exponent pair. Then, provided that (k, l) ≠ (\frac{1}{2}, \frac{1}{2}), we have

Δ(x) ≪ x^{\frac{k+l}{2k+2}} .

Proof. From the initial steps of the proof of Theorem 2.3 we see that

(17.59)  ∑_{n≤x} d(n) = 2 ∑_{n≤\sqrt{x}} \frac{x}{n} − 2 ∑_{n≤\sqrt{x}} s (\frac{x}{n}) − [\sqrt{x}]^{2} − [\sqrt{x}]

and from the initial steps of the proof of (1.26) we have

∑_{n≤y} \frac{1}{n} = log y + C_{0} − \frac{s(y)}{y} − ∫_{y}^{∞} \frac{s(u)}{u^{2}} du.

We observe that ∫_{y}^{u} s(v) dv ≪ 1, and so by integrating the last term by parts it follows that it is ≪ y^{−2}. Hence

∑_{n≤y} \frac{1}{n} = log y + C_{0} − \frac{B(y)}{y} + O (y^{−2}) .

We also have

x − [\sqrt{x}]^{2} − [\sqrt{x}] = 2\sqrt{x}s(\sqrt{x}) + O(1).

Inserting these two expressions in (17.59) gives

Δ(x) = −2 ∑_{n\sqrt{x}} s (\frac{x}{n}) + O(1).

We now divide the interval of summation into subintervals of the form [N, N′] with N′ ≤ 2N and N ≤ \sqrt{x} and appeal to Theorem 17.22 with θ = 2. The contribution from a typical such subinterval is

≪ (xN^{−2})^{\frac{k}{k+1}} N^{\frac{k+l}{k+1}} + x^{−1}N^{2} ≪ x^{\frac{k}{k+1}} N^{\frac{l−k}{k+1}} + x^{−1}N^{2}.

Since (k, l) ≠ (\frac{1}{2}, \frac{1}{2}) we have l > k. Hence on adding up the contribution from the different subintervals we obtain the bound

x^{\frac{k+l}{2k+2}} + 1 ≪ x^{\frac{k+l}{2k+2}}

as required.

For completeness we observe that in the case of the exponent pair (\frac{1}{2}, \frac{1}{2}) the proof gives an extra factor of log x in the conclusion. More interestingly one can observe that (k′, l′) = A(k, l) satisfies

k′ = \frac{k}{2k + 2}, l′ = \frac{k + l + 1}{2k + 2},

and so the exponent of x in the conclusion is k′ + l′ − \frac{1}{2}. With the exponent pairs obtained by the A and B operations there is symmetry in the line l = k + \frac{1}{2} between those in which the last operation is an A and those in which the last operation is a B. Thus, just as in Theorem 20, we are interested in exponent pairs (k′, l′) in which k′ + l′ is minimal. Amongst those listed above (k, l) = (\frac{11}{30}, \frac{8}{15}) (which gives (k′, l′) = (\frac{11}{82}, \frac{57}{82}), of course) gives the following corollary.

Corollary 17.24 We have Δ(x) ≪ x^{\frac{27}{82}} .

17.3.1 Exercises

1. Let I(α) = ∫_{0}^{1} e (αx + log log \frac{e}{x}) dx. Show that

I(α) = \frac{1}{2πiα} (e(α) − e(log log α)) + o (\frac{1}{α})

as α → ∞. Note that this is larger than \frac{1}{\sqrt{f′′(x_{0})}}. Why?

2. Let I(α) = ∫_{0}^{1} e (αx + log log \frac{1}{x(1−x)}) dx. Show that

|I(α)| ≍ \frac{1}{α\sqrt{log α}}

as α → +∞.

3. Show that if a is a positive integer, then

∑_{a≤n≤2a} e ((n/3)^{\frac{3}{2}} ) = da^{\frac{3}{4}} + O (a^{\frac{1}{2}} )

where d is a non-zero complex number.

4. (a) Let χ(d) = (−1)^{\frac{d−1}{2}} when d is odd and 0 when d is even and let

S(y) = ∑_{n≤y} χ(n).

Show that

S(y) = \frac{1}{2} − B (\frac{y − 1}{4}) + B (\frac{y − 3}{4})

and that

∑_{n≤y} \frac{χ(n)}{n} = \frac{π}{4} + \frac{S(y) − \frac{1}{2}}{y} + O(1).

(b) Let

r(n) = 4 ∑_{d|n} χ(d),

R(x) = ∑_{n≤x} r(n) − πx,

17.3 van der Corput’s method 615

and

T (y; a, b) = ∑_{n≤y} B (\frac{x − a}{4n + b}) .

Show that

\frac{1}{4}R(x) = T (\sqrt{x}; 0, 1) − T (\sqrt{x}; 0, 3) + T (\sqrt{x}; 3, 0) − T (\sqrt{x}; 1, 0) + O(1).

(c) Suppose that (k, l) is an exponent pair other than (\frac{1}{2}, \frac{1}{2}). Show that R(x) ≪ x^{\frac{k+l}{2k+2}} ,

and in particular that

R(x) ≪ x^{\frac{27}{82}} .

5. (a) Let Q(x, h) denote the number of squarefree numbers q with x − h < q ≤ x.

Suppose that 1 ≤ h ≤ \frac{x}{2} and that \sqrt{h} ≤ z ≤ \sqrt{x}. Show that

Q(x, h) = \frac{6h}{π^{2}} + O((R + S) log x + \sqrt{h})

where

R = sup_{a≤z} sup_{b≤2a} sup_{x−h≤y≤x} | ∑_{a≤n≤b} B (\frac{y}{n^{2}} )|

and

S = sup_{a≤xz^{−2}} S(a), S(a) = sup_{b≤2a} sup_{x−h≤y≤x} | ∑_{a≤n≤b} B (\frac{y^{1/2}}{n^{1/2}} )| .

(b) Show that

R ≪ x^{\frac{1}{3}} z^{− \frac{1}{3}} + xz^{−3}

and that if (k, l) is an exponent pair, then

S ≪ x^{\frac{k}{k+1}} a^{\frac{l−2k}{k+1}} + x^{−1}z^{3}.

(c) Show that there is a positive number C such that whenever Cx^{2/9} log x ≤ h ≤ x there is a squarefree number q with x − h < q ≤ x.

616 Exponential sums