The equidistribution theorem asserts that if ${\alpha \in {\bf R}/{\bf Z}}$ is an irrational phase, then the sequence ${(n\alpha)_{n=1}^\infty}$ is equidistributed on the unit circle, or equivalently that

$\displaystyle \frac{1}{N} \sum_{n=1}^N F(n\alpha) \rightarrow \int_{{\bf R}/{\bf Z}} F(x)\ dx$

for any continuous (or equivalently, for any smooth) function ${F: {\bf R}/{\bf Z} \rightarrow {\bf C}}$. By approximating ${F}$ uniformly by a Fourier series, this claim is equivalent to that of showing that

$\displaystyle \frac{1}{N} \sum_{n=1}^N e(hn\alpha) \rightarrow 0$

for any non-zero integer ${h}$ (where ${e(x) := e^{2\pi i x}}$), which is easily verified from the irrationality of ${\alpha}$ and the geometric series formula. Conversely, if ${\alpha}$ is rational, then clearly ${\frac{1}{N} \sum_{n=1}^N e(hn\alpha)}$ fails to go to zero when ${h}$ is a multiple of the denominator of ${\alpha}$.

One can then ask for more quantitative information about the decay of exponential sums of ${\frac{1}{N} \sum_{n=1}^N e(n \alpha)}$, or more generally on exponential sums of the form ${\frac{1}{|Q|} \sum_{n \in Q} e(P(n))}$ for an arithmetic progression ${Q}$ (in this post all progressions are understood to be finite) and a polynomial ${P: Q \rightarrow \/{\bf Z}}$. It will be convenient to phrase such information in the form of an inverse theorem, describing those phases for which the exponential sum is large. Indeed, we have

Lemma 1 (Geometric series formula, inverse form) Let ${Q \subset {\bf Z}}$ be an arithmetic progression of length at most ${N}$ for some ${N \geq 1}$, and let ${P(n) = n \alpha + \beta}$ be a linear polynomial for some ${\alpha,\beta \in {\bf R}/{\bf Z}}$. If

$\displaystyle \frac{1}{N} |\sum_{n \in Q} e(P(n))| \geq \delta$

for some ${\delta > 0}$, then there exists a subprogression ${Q'}$ of ${Q}$ of size ${|Q'| \gg \delta^2 N}$ such that ${P(n)}$ varies by at most ${\delta}$ on ${Q'}$ (that is to say, ${P(n)}$ lies in a subinterval of ${{\bf R}/{\bf Z}}$ of length at most ${\delta}$).

Proof: By a linear change of variable we may assume that ${Q}$ is of the form ${\{0,\dots,N'-1\}}$ for some ${N' \geq 1}$. We may of course assume that ${\alpha}$ is non-zero in ${{\bf R}/{\bf Z}}$, so that ${\|\alpha\|_{{\bf R}/{\bf Z}} > 0}$ (${\|x\|_{{\bf R}/{\bf Z}}}$ denotes the distance from ${x}$ to the nearest integer). From the geometric series formula we see that

$\displaystyle |\sum_{n \in Q} e(P(n))| \leq \frac{2}{|e(\alpha) - 1|} \ll \frac{1}{\|\alpha\|_{{\bf R}/{\bf Z}}},$

and so ${\|\alpha\|_{{\bf R}/{\bf Z}} \ll \frac{1}{\delta N}}$. Setting ${Q' := \{ n \in Q: n \leq c \delta^2 N \}}$ for some sufficiently small absolute constant ${c}$, we obtain the claim. $\Box$

Thus, in order for a linear phase ${P(n)}$ to fail to be equidistributed on some long progression ${Q}$, ${P}$ must in fact be almost constant on large piece of ${Q}$.

As is well known, this phenomenon generalises to higher order polynomials. To achieve this, we need two elementary additional lemmas. The first relates the exponential sums of ${P}$ to the exponential sums of its “first derivatives” ${n \mapsto P(n+h)-P(n)}$.

Lemma 2 (Van der Corput lemma, inverse form) Let ${Q \subset {\bf Z}}$ be an arithmetic progression of length at most ${N}$, and let ${P: Q \rightarrow {\bf R}/{\bf Z}}$ be an arbitrary function such that

$\displaystyle \frac{1}{N} |\sum_{n \in Q} e(P(n))| \geq \delta \ \ \ \ \ (1)$

for some ${\delta > 0}$. Then, for ${\gg \delta^2 N}$ integers ${h \in Q-Q}$, there exists a subprogression ${Q_h}$ of ${Q}$, of the same spacing as ${Q}$, such that

$\displaystyle \frac{1}{N} |\sum_{n \in Q_h} e(P(n+h)-P(n))| \gg \delta^2. \ \ \ \ \ (2)$

Proof: Squaring (1), we see that

$\displaystyle \sum_{n,n' \in Q} e(P(n') - P(n)) \geq \delta^2 N^2.$

We write ${n' = n+h}$ and conclude that

$\displaystyle \sum_{h \in Q-Q} \sum_{n \in Q_h} e( P(n+h)-P(n) ) \geq \delta^2 N^2$

where ${Q_h := Q \cap (Q-h)}$ is a subprogression of ${Q}$ of the same spacing. Since ${\sum_{n \in Q_h} e( P(n+h)-P(n) ) = O(N)}$, we conclude that

$\displaystyle |\sum_{n \in Q_h} e( P(n+h)-P(n) )| \gg \delta^2 N$

for ${\gg \delta^2 N}$ values of ${h}$ (this can be seen, much like the pigeonhole principle, by arguing via contradiction for a suitable choice of implied constants). The claim follows. $\Box$

The second lemma (which we recycle from this previous blog post) is a variant of the equidistribution theorem.

Lemma 3 (Vinogradov lemma) Let ${I \subset [-N,N] \cap {\bf Z}}$ be an interval for some ${N \geq 1}$, and let ${\theta \in{\bf R}/{\bf Z}}$ be such that ${\|n\theta\|_{{\bf R}/{\bf Z}} \leq \varepsilon}$ for at least ${\delta N}$ values of ${n \in I}$, for some ${0 < \varepsilon, \delta < 1}$. Then either

$\displaystyle N < \frac{2}{\delta}$

or

$\displaystyle \varepsilon > 10^{-2} \delta$

or else there is a natural number ${q \leq 2/\delta}$ such that

$\displaystyle \| q \theta \|_{{\bf R}/{\bf Z}} \ll \frac{\varepsilon}{\delta N}.$

Proof: We may assume that ${N \geq \frac{2}{\delta}}$ and ${\varepsilon \leq 10^{-2} \delta}$, since we are done otherwise. Then there are at least two ${n \in I}$ with ${\|n \theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$, and by the pigeonhole principle we can find ${n_1 < n_2}$ in ${Q}$ with ${\|n_1 \theta \|_{{\bf R}/{\bf Z}}, \|n_2 \theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$ and ${n_2-n_1 \leq \frac{2}{\delta}}$. By the triangle inequality, we conclude that there exists at least one natural number ${q \leq \frac{2}{\delta}}$ for which

$\displaystyle \| q \theta \|_{{\bf R}/{\bf Z}} \leq 2\varepsilon.$

We take ${q}$ to be minimal amongst all such natural numbers, then we see that there exists ${a}$ coprime to ${q}$ and ${|\kappa| \leq 2\varepsilon}$ such that

$\displaystyle \theta = \frac{a}{q} + \frac{\kappa}{q}. \ \ \ \ \ (3)$

If ${\kappa=0}$ then we are done, so suppose that ${\kappa \neq 0}$. Suppose that ${n < m}$ are elements of ${I}$ such that ${\|n\theta \|_{{\bf R}/{\bf Z}}, \|m\theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$ and ${m-n \leq \frac{1}{10 \kappa}}$. Writing ${m-n = qk + r}$ for some ${0 \leq r < q}$, we have

$\displaystyle \| (m-n) \theta \|_{{\bf R}/{\bf Z}} = \| \frac{ra}{q} + (m-n) \frac{\kappa}{q} \|_{{\bf R}/{\bf Z}} \leq 2\varepsilon.$

By hypothesis, ${(m-n) \frac{\kappa}{q} \leq \frac{1}{10 q}}$; note that as ${q \leq 2/\delta}$ and ${\varepsilon \leq 10^{-2} \delta}$ we also have ${\varepsilon \leq \frac{1}{10q}}$. This implies that ${\| \frac{ra}{q} \|_{{\bf R}/{\bf Z}} < \frac{1}{q}}$ and thus ${r=0}$. We then have

$\displaystyle |k \kappa| \leq 2 \varepsilon.$

We conclude that for fixed ${n \in I}$ with ${\|n\theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$, there are at most ${\frac{2\varepsilon}{|\kappa|}}$ elements ${m}$ of ${[n, n + \frac{1}{10 |\kappa|}]}$ such that ${\|m\theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$. Iterating this with a greedy algorithm, we see that the number of ${n \in I}$ with ${\|n\theta \|_{{\bf R}/{\bf Z}} \leq \varepsilon}$ is at most ${(\frac{N}{1/10|\kappa|} + 1) 2\varepsilon/|\kappa|}$; since ${\varepsilon < 10^{-2} \delta}$, this implies that

$\displaystyle \delta N \ll 2 \varepsilon / \kappa$

and the claim follows. $\Box$

Now we can quickly obtain a higher degree version of Lemma 1:

Proposition 4 (Weyl exponential sum estimate, inverse form) Let ${Q \subset {\bf Z}}$ be an arithmetic progression of length at most ${N}$ for some ${N \geq 1}$, and let ${P: {\bf Z} \rightarrow {\bf R}/{\bf Z}}$ be a polynomial of some degree at most ${d \geq 0}$. If

$\displaystyle \frac{1}{N} |\sum_{n \in Q} e(P(n))| \geq \delta$

for some ${\delta > 0}$, then there exists a subprogression ${Q'}$ of ${Q}$ with ${|Q'| \gg_d \delta^{O_d(1)} N}$ such that ${P}$ varies by at most ${\delta}$ on ${Q'}$.

Proof: We induct on ${d}$. The cases ${d=0,1}$ are immediate from Lemma 1. Now suppose that ${d \geq 2}$, and that the claim had already been proven for ${d-1}$. To simplify the notation we allow implied constants to depend on ${d}$. Let the hypotheses be as in the proposition. Clearly ${\delta}$ cannot exceed ${1}$. By shrinking ${\delta}$ as necessary we may assume that ${\delta \leq c}$ for some sufficiently small constant ${c}$ depending on ${d}$.

By rescaling we may assume ${Q \subset [0,N] \cap {\bf Z}}$. By Lemma 3, we see that for ${\gg \delta^2 N}$ choices of ${h \in [-N,N] \cap {\bf Z}}$ such that

$\displaystyle \frac{1}{N} |\sum_{n \in I_h} e(P(n+h) - P(n))| \gg \delta^2$

for some interval ${I_h \subset [0,N] \cap {\bf Z}}$. We write ${P(n) = \sum_{i \leq d} \alpha_i n^i}$, then ${P(n+h)-P(n)}$ is a polynomial of degree at most ${d-1}$ with leading coefficient ${h \alpha_d n^{d-1}}$. We conclude from induction hypothesis that for each such ${h}$, there exists a natural number ${q_h \ll \delta^{-O(1)}}$ such that ${\|q_h h \alpha_d \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N^{d-1}}$, by double-counting, this implies that there are ${\gg \delta^{O(1)} N}$ integers ${n}$ in the interval ${[-\delta^{-O(1)} N, \delta^{-O(1)} N] \cap {\bf Z}}$ such that ${\|n \alpha_d \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N^{d-1}}$. Applying Lemma 3, we conclude that either ${N \ll \delta^{-O(1)}}$, or that

$\displaystyle \| q \alpha_d \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N^d. \ \ \ \ \ (4)$

In the former case the claim is trivial (just take ${Q'}$ to be a point), so we may assume that we are in the latter case.

We partition ${Q}$ into arithmetic progressions ${Q'}$ of spacing ${q}$ and length comparable to ${\delta^{-C} N}$ for some large ${C}$ depending on ${d}$ to be chosen later. By hypothesis, we have

$\displaystyle \frac{1}{|Q|} |\sum_{n \in Q} e(P(n))| \geq \delta$

so by the pigeonhole principle, we have

$\displaystyle \frac{1}{|Q'|} |\sum_{n \in Q'} e(P(n))| \geq \delta$

for at least one such progression ${Q'}$. On this progression, we may use the binomial theorem and (4) to write ${\alpha_d n^d}$ as a polynomial in ${n}$ of degree at most ${d-1}$, plus an error of size ${O(\delta^{C - O(1)})}$. We thus can write ${P(n) = P'(n) + O(\delta^{C-O(1)})}$ for ${n \in Q'}$ for some polynomial ${P'}$ of degree at most ${d-1}$. By the triangle inequality, we thus have (for ${C}$ large enough) that

$\displaystyle \frac{1}{|Q'|} |\sum_{n \in Q'} e(P'(n))| \gg \delta$

and hence by induction hypothesis we may find a subprogression ${Q''}$ of ${Q'}$ of size ${|Q''| \gg \delta^{O(1)} N}$ such that ${P'}$ varies by most ${\delta/2}$ on ${Q''}$, and thus (for ${C}$ large enough again) that ${P}$ varies by at most ${\delta}$ on ${Q''}$, and the claim follows. $\Box$

This gives the following corollary (also given as Exercise 16 in this previous blog post):

Corollary 5 (Weyl exponential sum estimate, inverse form II) Let ${I \subset [-N,N] \cap {\bf Z}}$ be a discrete interval for some ${N \geq 1}$, and let ${P(n) = \sum_{i \leq d} \alpha_i n^i}$ polynomial of some degree at most ${d \geq 0}$ for some ${\alpha_0,\dots,\alpha_d \in {\bf R}/{\bf Z}}$. If

$\displaystyle \frac{1}{N} |\sum_{n \in I} e(P(n))| \geq \delta$

for some ${\delta > 0}$, then there is a natural number ${q \ll_d \delta^{-O_d(1)}}$ such that ${\| q\alpha_i \|_{{\bf R}/{\bf Z}} \ll_d \delta^{-O_d(1)} N^{-i}}$ for all ${i=0,\dots,d}$.

One can obtain much better exponents here using Vinogradov’s mean value theorem; see Theorem 1.6 this paper of Wooley. (Thanks to Mariusz Mirek for this reference.) However, this weaker result already suffices for many applications, and does not need any result as deep as the mean value theorem.

Proof: To simplify notation we allow implied constants to depend on ${d}$. As before, we may assume that ${\delta \leq c}$ for some small constant ${c>0}$ depending only on ${d}$. We may also assume that ${N \geq \delta^{-C}}$ for some large ${C}$, as the claim is trivial otherwise (set ${q=1}$).

Applying Proposition 4, we can find a natural number ${q \ll \delta^{-O(1)}}$ and an arithmetic subprogression ${Q}$ of ${I}$ such that ${|Q| \gg \delta^{O(1)}}$ and such that ${P}$ varies by at most ${\delta}$ on ${Q}$. Writing ${Q = \{ qn+r: n \in I'\}}$ for some interval ${I' \subset [0,N] \cap {\bf Z}}$ of length ${\gg \delta^{O(1)}}$ and some ${0 \leq r < q}$, we conclude that the polynomial ${n \mapsto P(qn+r)}$ varies by at most ${\delta}$ on ${I'}$. Taking ${d^{th}}$ order differences, we conclude that the ${d^{th}}$ coefficient of this polynomial is ${O(\delta^{-O(1)} / N^d)}$; by the binomial theorem, this implies that ${n \mapsto P(qn+r)}$ differs by at most ${O(\delta)}$ on ${I'}$ from a polynomial of degree at most ${d-1}$. Iterating this, we conclude that the ${i^{th}}$ coefficient of ${n \mapsto P(qn+r)}$ is ${O(\delta N^{-i})}$ for ${i=0,\dots,d}$, and the claim then follows by inverting the change of variables ${n \mapsto qn+r}$ (and replacing ${q}$ with a larger quantity such as ${q^d}$ as necessary). $\Box$

For future reference we also record a higher degree version of the Vinogradov lemma.

Lemma 6 (Polynomial Vinogradov lemma) Let ${I \subset [-N,N] \cap {\bf Z}}$ be a discrete interval for some ${N \geq 1}$, and let ${P: {\bf Z} \rightarrow {\bf R}/{\bf Z}}$ be a polynomial ${P(n) = \sum_{i \leq d} \alpha_i n^i}$ of degree at most ${d}$ for some ${d \geq 1}$ such that ${\|P(n)\|_{{\bf R}/{\bf Z}} \leq \varepsilon}$ for at least ${\delta N}$ values of ${n \in I}$, for some ${0 < \varepsilon, \delta < 1}$. Then either

$\displaystyle N \ll_d \delta^{-O_d(1)} \ \ \ \ \ (5)$

or

$\displaystyle \varepsilon \gg_d \delta^{O_d(1)} \ \ \ \ \ (6)$

or else there is a natural number ${q \ll_d \delta^{-O_d(1)}}$ such that

$\displaystyle \| q \alpha_i \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)} \varepsilon}{N^i}$

for all ${i=0,\dots,d}$.

Proof: We induct on ${d}$. For ${d=1}$ this follows from Lemma 3 (noting that if ${\|P(n)\|_{{\bf R}/{\bf Z}}, \|P(n_0)\|_{{\bf R}/Z} \leq \varepsilon}$ then ${\|P(n)-P(n_0)\|_{{\bf R}/{\bf Z}} \leq 2\varepsilon}$), so suppose that ${d \geq 2}$ and that the claim is already proven for ${d-1}$. We now allow all implied constants to depend on ${d}$.

For each ${h \in [-2N,2N] \cap {\bf Z}}$, let ${N_h}$ denote the number of ${n \in [-N,N] \cap {\bf Z}}$ such that ${\| P(n+h)\|_{{\bf R}/{\bf Z}}, \|P(n)\|_{{\bf R}/{\bf Z}} \leq \varepsilon}$. By hypothesis, ${\sum_{h \in [-2N,2N] \cap {\bf Z}} N_h \gg \delta^2 N^2}$, and clearly ${N_h = O(N)}$, so we must have ${N_h \gg \delta^2 N}$ for ${\gg \delta^2 N}$ choices of ${h}$. For each such ${h}$, we then have ${\|P(n+h)-P(n)\|_{{\bf R}/{\bf Z}} \leq 2\varepsilon}$ for ${\gg \delta^2 N}$ choices of ${n \in [-N,N] \cap {\bf Z}}$, so by induction hypothesis, either (5) or (6) holds, or else for ${\gg \delta^{O(1)} N}$ choices of ${h \in [-2N,2N] \cap {\bf Z}}$, there is a natural number ${q_h \ll \delta^{-O(1)}}$ such that

$\displaystyle \| q_h \alpha_{i,h} \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)} \varepsilon}{N^i}$

for ${i=1,\dots,d-1}$, where ${\alpha_{i,h}}$ are the coefficients of the degree ${d-1}$ polynomial ${n \mapsto P(n+h)-P(n)}$. We may of course assume it is the latter which holds. By the pigeonhole principle we may take ${q_h= q}$ to be independent of ${h}$.

Since ${\alpha_{d-1,h} = dh \alpha_d}$, we have

$\displaystyle \| qd h \alpha_d \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)} \varepsilon}{N^{d-1}}$

for ${\gg \delta^{O(1)} N}$ choices of ${h}$, so by Lemma 3, either (5) or (6) holds, or else (after increasing ${q}$ as necessary) we have

$\displaystyle \| q \alpha_d \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)} \varepsilon}{N^d}.$

We can again assume it is the latter that holds. This implies that ${q \alpha_{d-2,h} = (d-1) h \alpha_{d-1} + O( \delta^{-O(1)} \varepsilon / N^{d-2} )}$ modulo ${1}$, so that

$\displaystyle \| q(d-1) h \alpha_{d-1} \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)} \varepsilon}{N^{d-2}}$

for ${\gg \delta^{O(1)} N}$ choices of ${h}$. Arguing as before and iterating, we obtain the claim. $\Box$

The above results also extend to higher dimensions. Here is the higher dimensional version of Proposition 4:

Proposition 7 (Multidimensional Weyl exponential sum estimate, inverse form) Let ${k \geq 1}$ and ${N_1,\dots,N_k \geq 1}$, and let ${Q_i \subset {\bf Z}}$ be arithmetic progressions of length at most ${N_i}$ for each ${i=1,\dots,k}$. Let ${P: {\bf Z}^k \rightarrow {\bf R}/{\bf Z}}$ be a polynomial of degrees at most ${d_1,\dots,d_k}$ in each of the ${k}$ variables ${n_1,\dots,n_k}$ separately. If

$\displaystyle \frac{1}{N_1 \dots N_k} |\sum_{n \in Q_1 \times \dots \times Q_k} e(P(n))| \geq \delta$

for some ${\delta > 0}$, then there exists a subprogression ${Q'_i}$ of ${Q_i}$ with ${|Q'_i| \gg_{k,d_1,\dots,d_k} \delta^{O_{k,d_1,\dots,d_k}(1)} N_i}$ for each ${i=1,\dots,k}$ such that ${P}$ varies by at most ${\delta}$ on ${Q'_1 \times \dots \times Q'_k}$.

A much more general statement, in which the polynomial phase ${n \mapsto e(P(n))}$ is replaced by a nilsequence, and in which one does not necessarily assume the exponential sum is small, is given in Theorem 8.6 of this paper of Ben Green and myself, but it involves far more notation to even state properly.

Proof: We induct on ${k}$. The case ${k=1}$ was established in Proposition 5, so we assume that ${k \geq 2}$ and that the claim has already been proven for ${k-1}$. To simplify notation we allow all implied constants to depend on ${k,d_1,\dots,d_k}$. We may assume that ${\delta \leq c}$ for some small ${c>0}$ depending only on ${k,d_1,\dots,d_k}$.

By a linear change of variables, we may assume that ${Q_i \subset [0,N_i] \cap {\bf Z}}$ for all ${i=1,\dots,k}$.

We write ${n' := (n_1,\dots,n_{k-1})}$. First suppose that ${N_k = O(\delta^{-O(1)})}$. Then by the pigeonhole principle we can find ${n_k \in I_k}$ such that

$\displaystyle \frac{1}{N_1 \dots N_{k-1}} |\sum_{n' \in Q_1 \times \dots \times Q_{k-1}} e(P(n',n_k))| \geq \delta$

and the claim then follows from the induction hypothesis. Thus we may assume that ${N_k \geq \delta^{-C}}$ for some large ${C}$ depending only on ${k,d_1,\dots,d_k}$. Similarly we may assume that ${N_i \geq \delta^{-C}}$ for all ${i=1,\dots,k}$.

By the triangle inequality, we have

$\displaystyle \frac{1}{N_1 \dots N_k} \sum_{n_k \in Q_k} |\sum_{n' \in Q_1 \times \dots \times Q_{k-1}} e(P(n',n_k))| \geq \delta.$

The inner sum is ${O(N_k)}$, and the outer sum has ${O(N_1 \dots N_{k-1})}$ terms. Thus, for ${\gg \delta N_1 \dots N_{k-1}}$ choices of ${n' \in Q_1 \times \dots \times Q_{k-1}}$, one has

$\displaystyle \frac{1}{N_k} |\sum_{n_k \in Q_k} e(P(n',n_k))| \gg \delta. \ \ \ \ \ (7)$

We write

$\displaystyle P(n',n_k) = \sum_{i_k \leq d_k} P_{i_k}(n') n_k^i$

for some polynomials ${P_{i_k}: {\bf Z}^{k-1} \rightarrow {\bf R}/{\bf Z}}$ of degrees at most ${d_1,\dots,d_{k-1}}$ in the variables ${n_1,\dots,n_{k-1}}$. For each ${n'}$ obeying (7), we apply Corollary 5 to conclude that there exists a natural number ${q_{n'} \ll \delta^{-O(1)}}$ such that

$\displaystyle \| q_{n'} P_{i_k}(n') \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N_k^{i_k}$

for ${i_k=1,\dots,d_k}$ (the claim also holds for ${i_k=0}$ but we discard it as being trivial). By the pigeonhole principle, there thus exists a natural number ${q \ll \delta^{-O(1)}}$ such that

$\displaystyle \| q P_{i_k}(n') \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N_k^{i_k}$

for all ${i_k=1,\dots,d_k}$ and for ${\gg \delta^{O(1)} N_1 \dots N_{k-1}}$ choices of ${n' \in Q_1 \times \dots \times Q_{k-1}}$. If we write

$\displaystyle P_{i_k}(n') = \sum_{i_{k-1} \leq d_{k-1}} P_{i_{k-1},i_k}(n_1,\dots,n_{k-2}) n_{k-1}^{i_{k-1}},$

where ${P_{i_{k-1},i_k}: {\bf Z}^{k-2} \rightarrow {\bf R}/{\bf Z}}$ is a polynomial of degrees at most ${d_1,\dots,d_{k-2}}$, then for ${\gg \delta^{O(1)} N_1 \dots N_{k-2}}$ choices of ${(n_1,\dots,n_{k-2}) \in Q_1 \times \dots \times Q_{k-2}}$ we then have

$\displaystyle \| \sum_{i_{k-1} \leq d_{k-1}} q P_{i_{k-1},i_k}(n_1,\dots,n_{k-2}) n_{k-1}^{i_{k-1}} \|_{{\bf R}/{\bf Z}} \ll \delta^{-O(1)} / N_k^{i_k}.$

Applying Lemma 6 in the ${n_{k-1}}$ and the largeness hypotheses on the ${N_i}$ (and also the assumption that ${i_k \geq 1}$) we conclude (after enlarging ${q}$ as necessary, and pigeonholing to keep ${q}$ independent of ${n_1,\dots,n_{k-2}}$) that

$\displaystyle \| q P_{i_{k-1},i_k}(n_1,\dots,n_{k-2}) \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)}}{N_{k-1}^{i_{k-1}} N_k^{i_k}}$

for all ${i_{k-1}=0,\dots,d_{k-1}}$ (note that we now include that ${i_{k-1}=0}$ case, which is no longer trivial) and for ${\gg \delta^{O(1)} N_1 \dots N_{k-2}}$ choices of ${(n_1,\dots,n_{k-2}) \in Q_1 \times \dots \times Q_{k-2}}$. Iterating this, we eventually conclude (after enlarging ${q}$ as necessary) that

$\displaystyle \| q \alpha_{i_1,\dots,i_k} \|_{{\bf R}/{\bf Z}} \ll \frac{\delta^{-O(1)}}{N_1^{i_1} \dots N_k^{i_k}} \ \ \ \ \ (8)$

whenever ${i_j \in \{0,\dots,d_j\}}$ for ${j=1,\dots,k}$, with ${i_k}$ nonzero. Permuting the indices, and observing that the claim is trivial for ${(i_1,\dots,i_k) = (0,\dots,0)}$, we in fact obtain (8) for all ${(i_1,\dots,i_k) \in \{0,\dots,d_1\} \times \dots \times \{0,\dots,d_k\}}$, at which point the claim easily follows by taking ${Q'_j := \{ qn_j: n_j \leq \delta^C N_j\}}$ for each ${j=1,\dots,k}$. $\Box$

An inspection of the proof of the above result (or alternatively, by combining the above result again with many applications of Lemma 6) reveals the following general form of Proposition 4, which was posed as Exercise 17 in this previous blog post, but had a slight misprint in it (it did not properly treat the possibility that some of the ${N_j}$ could be small) and was a bit trickier to prove than anticipated (in fact, the reason for this post was that I was asked to supply a more detailed solution for this exercise):

Proposition 8 (Multidimensional Weyl exponential sum estimate, inverse form, II) Let ${k \geq 1}$ be an natural number, and for each ${j=1,\dots,k}$, let ${I_j \subset [0,N_j]_{\bf Z}}$ be a discrete interval for some ${N_j \geq 1}$. Let

$\displaystyle P(n_1,\dots,n_k) = \sum_{i_1 \leq d_1, \dots, i_k \leq d_k} \alpha_{i_1,\dots,i_k} n_1^{i_1} \dots n_k^{i_k}$

be a polynomial in ${k}$ variables of multidegrees ${d_1,\dots,d_k \geq 0}$ for some ${\alpha_{i_1,\dots,i_k} \in {\bf R}/{\bf Z}}$. If

$\displaystyle \frac{1}{N_1 \dots N_k} |\sum_{n \in I_1 \times \dots \times I_k} e(P(n))| \geq \delta \ \ \ \ \ (9)$

for some ${\delta > 0}$, then either

$\displaystyle N_j \ll_{k,d_1,\dots,d_k} \delta^{-O_{k,d_1,\dots,d_k}(1)} \ \ \ \ \ (10)$

for some ${1 \leq j \leq d_k}$, or else there is a natural number ${q \ll_{k,d_1,\dots,d_k} \delta^{-O_{k,d_1,\dots,d_k}(1)}}$ such that

$\displaystyle \| q\alpha_{i_1,\dots,i_k} \|_{{\bf R}/{\bf Z}} \ll_{k,d_1,\dots,d_k} \delta^{-O_d(1)} N_1^{-i_1} \dots N_k^{-i_k} \ \ \ \ \ (11)$

whenever ${i_j \leq d_j}$ for ${j=1,\dots,k}$.

Again, the factor of ${N_1^{-i_1} \dots N_k^{-i_k}}$ is natural in this bound. In the ${k=1}$ case, the option (10) may be deleted since (11) trivially holds in this case, but this simplification is no longer available for ${k>1}$ since one needs (10) to hold for all ${j}$ (not just one ${j}$) to make (11) completely trivial. Indeed, the above proposition fails for ${k \geq 2}$ if one removes (10) completely, as can be seen for instance by inspecting the exponential sum ${\sum_{n_1 \in \{0,1\}} \sum_{n_2 \in [1,N] \cap {\bf Z}} e( \alpha n_1 n_2)}$, which has size comparable to ${N}$ regardless of how irrational ${\alpha}$ is.