Friday, November 21, 2014

Vinogradov's mean value theorem and Weyl sums

In this post, we consider Weyl sums, which are exponential sums with polynomial phases; a Weyl sum is defined by
\[\begin{eqnarray}f(\alpha,N):=\sum_{n\leq N}e(\alpha_kn^k+...+\alpha_1n),\quad \alpha\in \mathbb{R}^k.\end{eqnarray}\]
We also consider the closely related Vinogradov integrals
which are moments of Weyl sums with respect to the coefficient vector $\alpha$. We derive an efficient estimate for the Vinogradov integrals, known as Vinogradov's mean value theorem and essentially due to Vinogradov, following a simple proof by Wooley. We then utilize this estimate to achieve significant cancellation in general exponential sums $\sum_{n\leq N}e(F(n))$, whose phase function $F$ is smooth and grows very slowly. In proving that estimate, we follow Chandrasekharan's book Arithmetical functions. In a later post, this general estimate, also due to Vinogradov, will be employed to bound the zeta sums
\[\begin{eqnarray}\sum_{M\leq n\leq N}n^{-it}.\end{eqnarray}\]
These estimates in turn give bounds for growth of the Riemann zeta function, and further a zero-free region, and eventually a much better error term for the prime number theorem than the classical $\pi(x)=Li(x)+O(x\exp(-c\log^{\frac{1}{2}} x))$ ($\log^{\frac{1}{2}}x$ will be replaced by $\log^{\frac{4}{7}} x$). With some effort, one could use the Vinogradov integrals to bound Weyl sums, but we instead put the method of Weyl differencing into use, obtaining usually weaker bounds but with less effort.

Vinogradov's mean value theorem

A central feature of a Vinogradov integral is that its interpretation is twofold. On one hand, it is the moment of an exponential sum, to which one can apply Hölder's inequality and other analytic inequalities. On the other hand, using the orthogonality relation
\[\begin{eqnarray}\int_{[0,1]^k}e(m_1\alpha_1+...+m_{k}\alpha_k)d\alpha=\begin{cases}1,\quad m_1=....=m_k=0,\\0\quad \text{otherwise}\end{cases}\end{eqnarray}\]
from Fourier analysis and multiplying out the definition of $J_{s,k}(X)$, we immediately see that $J_{s,k}(X)$ counts the number of solutions to the system of Diophantine equations
\[\begin{eqnarray}\sum_{i=1}^k x_i^{j}=\sum_{i=1}^k y_i^j,\quad 1\leq j\leq k\quad (1)\end{eqnarray}\]
with $x_i,y_i\in [0,X]$ being integer variables. This interpretation enables us to use methods from combinatorics and finite fields to attack the problem of bounding $J_{s,k}(X)$. As will soon be seen, it is the combination of these two sides that turns out to be most fruitful in giving bounds for the Vinogradov integrals.

The estimate of Theorem 3 below gives for instance $J_{s,k}(X)\ll_{s,k} X^{2s-\frac{1}{2}k(k+1)+\frac{1}{2k}}$ for $s\geq k+3k^2\log k$. What is expected to be true is that for any fixed $\varepsilon>0$ and positive integers $s$ and $k$
\[\begin{eqnarray}J_{s,k}(X)\ll_{s,k} X^{\varepsilon}(X^{2s-\frac{1}{2}k(k+1)}+X^{s}).\end{eqnarray}\]
This bound would be the best one can hope for, up to the factor $X^{\varepsilon},$ and under the assumption $s\geq k+3k^2\log k$, the bound that will be proved falls short of the conjecture by merely $X^{\frac{1}{2k}-\varepsilon}$. Recently, Wooley was able to prove the conjecture for the Vinogradov integrals in the range $s\geq k^2-1$ (in this paper). One should of course ask where this conjectured bound comes from, and the following proposition answers it.

Proposition 1. We have
\[\begin{eqnarray}J_{s,k}(X)\gg_{s,k} X^{s}+X^{2s-\frac{1}{2}k(k+1)}.\end{eqnarray}\]
Also a trivial upper bound is $J_{s,k}(X)\leq k!X^{2s-k}$.

Proof. We use the interplay between the analytic and combinatorial sides of $J_{s,k}(X)$. From the combinatorial interpretation, it is evident that $J_{s,k}(X)\geq (X+1)^s$, as this is the number of trivial solutions with $x_i=y_i$ for all $i$. On the other hand, $|e(\alpha_kn^k+...+\alpha_1 n)|\geq \frac{1}{2}$ whenever $|\alpha_j|\leq \frac{1}{6kX^j}$ for $1\leq j\leq k$. Hence the analytic interpretation gives
\[\begin{eqnarray}J_{s,k}(X)&\geq& \int_{|\alpha_1|\leq \frac{1}{6kX}}...\int_{|\alpha_k|\leq \frac{1}{6kX^k}}\left(\frac{X}{2}\right)^{2s}d\alpha_k....d\alpha_1\\&\gg_{k,s}&X^{2s-\frac{1}{2}k(k+1)},\end{eqnarray}\]
so the lower bound follows. The weak upper bound follows just from the fact that if $2s-k$ variables in $(1)$ are fixed, the remaining $k$ can be solved at most uniquely, up to ordering. ■

We now turn to proving Vinogradov's mean value theorem, but we first need a lemma whose purpose is to bound the number of solutions to $(1)$, after certain systems of equations following from $(1)$ have been transformed into congruence equations.

Lemma 2. Let $p$ be a prime, $p>k\geq 1$. For fixed $h_1,...,h_k$, the number $\mathcal{N}$ of solutions to the congruence system
\[\begin{eqnarray}\sum_{i=1}^{k} x_i^{j}\equiv h_{j}\pmod{p^j},\quad 1\leq j\leq k\quad (2),\end{eqnarray}\]
with $x_1,x_2,...,x_k$ distinct modulo $p$ and $0\leq x_i\leq p^k-1$, satisfies $\mathcal{N}\leq k!\cdot p^{\frac{1}{2}k(k-1)}.$

Proof. Let us write $x_j=x_{j,1}+x_{j,2}p+...+x_{j,k}p^{k-1}$ for $1\leq j\leq k$ and some $0\leq x_{j,i}\leq p-1$. Then the equations $(2)$ imply
\[\begin{eqnarray}&&x_{1,1}+...+x_{k,1}\equiv h_1\pmod p\\&&x_{1,1}^2+...+x_{k,1}^2\equiv h_2\pmod p\\&&\hspace{1.0cm}...\hspace{4.5cm} (3)\\&&x_{1,1}^k+...+x_{k,1}^k\equiv h_k\pmod p.\end{eqnarray}\]
This system of equations has at most one solution, disregarding the order of the variables. To see this, notice that the sequence $z_n=x_1^n+...+x_k^n,n=1,2,...$ satisfies the linear recurrence equation
where the $b_i$'s are determined from the identity $(x-x_1)...(x-x_k)=x^k+b_{k-1}x^{k-1}+...+b_0$. We know that $z_1\equiv h_1\pmod p,...,z_k\equiv h_k\pmod p$, and this is enough to determine all the terms of sequence. Hence $(3)$ has at most $k!$ solutions, taking the order of the variables into account.

Next, we consider the system of equations $(2)$ modulo $p^2$, with $x_{1,1},...,x_{k,1}$ fixed. It yields the congruences
\[\begin{eqnarray}&&x_{1,1}x_{1,2}+...+x_{k,1}x_{k,2}\equiv h_1'\pmod p\\&&x_{1,1}^2x_{2,2}+...+x_{k,1}^2x_{k,2}\equiv h_2'\pmod p\\&&\hspace{1.6cm}...\hspace{5.3cm}(4)\\&&x_{1,1}^{k-1}x_{k,2}+...+x_{k,1}^{k-1}x_{k,k}\equiv h_k\pmod p.\end{eqnarray}\]
To arrive at these congruences, we multiplied out $(x_{1,k}+px_{j,2})^m$ for $1\leq j,m\leq k$, and used the fact that the prime factors of the resulting binomial coefficients are at most $k<p$. The numbers $x_1,...,x_k$ are distinct $\pmod p$, so some $k-1$ of them are not divisible by $p$, say $x_1,...,x_{k-1}$. Now the system $(4)$ above has a unique solution for a given $x_k$, because the determinant does not vanish:
\[\begin{eqnarray}\begin{vmatrix}x_{1,1}&...&x_{k-1,1}\\...&...&...\\x_{1,1}^{k-1}&...&x_{k-1,1}^{k-1}\end{vmatrix}=x_{1,1}...x_{k-1,1}\prod_{i<j\leq k-1}(x_{i,1}-x_{j,1})\not \equiv 0\pmod p\end{eqnarray}\]
by Vandermonde's formula. Hence $(4)$ has at most $p$ solutions in total.

We proceed similarly, considering the system $(2)$ modulo $p^3$ and reducing it to a system of $k-2$ congruences modulo $p^2$, which have at most $p^2$ solutions by the same argument as before. In the end, we find that the original system $(2)$ has at most $k!p^{1+2+...+(k-1)}=k!p^{\frac{1}{2}k(k-1)}$ solutions, proving the lemma. ■

We can now formulate Vinogradov's mean value theorem precisely; see also its corollary below. Preserving the $k$ dependence of constants in the inequality will be crucial in the subsequent Theorem 5 that bounds general exponential sums with slowly growing phases, and hence it is also necessary for our applications to the Riemann zeta function in a later post.

Theorem 3 (Vinogradov's mean value theorem). Let $r\geq 1$ and $k\geq 2$ be positive integers. Then for some absolute constant $c>0$ we have
\[\begin{eqnarray}J_{rk,k}(X)\leq \exp(crk^2 \log k)X^{2rk-\frac{k(k+1)}{2}+\eta(r,k)},\end{eqnarray}\]

Proof. (Wooley). The proof is by induction on $r$. For $r=1$, the desired inequality becomes
\[\begin{eqnarray}J_{k,k}(X)\leq \exp(ck^2\log k)X^{2k-\frac{1}{2}k^2-\frac{1}{2}k^2-\frac{1}{2}k}=\exp(ck^2\log k)X^{k},\end{eqnarray}\]
which follows from the trivial estimate $J_{k,k}(X)\leq k!X^{k}$ if $c$ is large. Now assume that all the cases up to $r-1$ have been proved, and consider the case $r$. For any $k$-tuple $h=(h_1,...,h_k)$, denote by $R_1(h)$ the number of solutions to the simultaneous equations
\[\begin{eqnarray}\sum_{i=1}^{rk}z_i^{j}=h_j,\quad 1\leq j\leq k\quad (5)\end{eqnarray}\]
in the range $0\leq z_i\leq X$ and with $z_1,...,z_k$ distinct. Let $R_2(h)$ count the rest of the solutions to $(4)$, meaning that some of the numbers $z_1,...,z_k$ are equal. We say that a $k$-tuple $h$ is admissible if $R_1(h)+R_2(h)>0$. Now all the solutions to $(5)$ can be formed uniquely as follows. Take an admissible $k$-tuple $h$ and choose $(x_1,...,x_k)$ and $(y_1,...,y_k)$ such that $(4)$ holds with $z_i=x_i$ and with $z_i=y_i$. Therefore
\[\begin{eqnarray}J_{rk,k}(X)=\sum_{h}(R_1(h)+R_2(h))^2\leq 2\left(\sum_{h}R_1(h)^2+\sum_{h}R_2(h)^2\right)=2(S_1+S_2).\end{eqnarray}\]

We have two possibilities, either $S_1\leq S_2$ or $S_1>S_2.$ We start with the first case. Then $J_{rk,k}(X)$ is at most $4\binom{k}{2}^2$ times the number of solutions to the system of equations
with $0\leq x_i,y_i\leq X$. The number of solutions to this system is given by the integral
which is by Hölder's inequality (applied twice) at most
\[\begin{eqnarray}\left(\int_{[0,1]^k}|f(\alpha,X)|^{rk}d\alpha \right)^{1-\frac{2}{rk}}\left(\int_{[0,1]^k}|f(2\alpha,X)|^{2rk}d\alpha\right)^{\frac{1}{rk}}.\end{eqnarray}\]
The two integrals are otherwise equal, except that the latter one is $2^{\frac{1}{r}}$ times the former. Hence
\[\begin{eqnarray}J_{rk,k}(X)\leq k^{4}\cdot 2^{\frac{1}{r}}J_{rk,k}(X)^{1-\frac{1}{rk}},\end{eqnarray}\]
\[\begin{eqnarray}J_{rk,k}(X)\leq 2^{k+2}\exp(4rk\log k),\end{eqnarray}\]
which is plainly less than the bound we seek to prove if $c$ is large.

We now turn to the case $S_1>S_2.$ Set $M=X^{\frac{1}{k}}$ and let $\mathcal{P}$ be the set of the $k^3$ least primes above $M$. By the prime number theorem (or Chebychev's estimate), we have $M\leq p\leq 2M$ for $p\in \mathcal{P}$ if the quantity
\[\begin{eqnarray}\pi(2M)-\pi(M)\geq \frac{M}{\log M}c_1\end{eqnarray}\]
is at least $k^3$ ($c_1$ is a suitable constant), which holds at least when $X\geq \exp(c_2k\log k)$ for sufficiently large $c_2$. This assumption on $X$ can be made, because otherwise the trivial bound $J_{rk,k}(X)\leq X^{2rk}$ beats the bound we want to prove. Next, assign a number $\Pi_x:=\prod_{1\leq i<j\leq k}(x_i-x_j)$ to each solution $x=(x_1,...,x_{rk})$ counted by $R_1(h)$. These numbers do not exceed $X^{\frac{1}{2}k(k-1)}$ in absolute value and are nonzero by assumption. The number $\Pi_x$ cannot be divisible by all the elements of $\mathcal{P}$, since otherwise we would have $\Pi_x>M^{k^3}=X^{k^2}$. Hence for every $x=(x_1,...,x_{rk})$ counted by $R_1(h)$ for some $h$, there is a prime $p\in P$ such that $x_1,..,x_k$ are distinct also modulo $p$. In particular, $R_1(h)\leq \sum_{p\in \mathcal{P}}R_1^{*}(h,p)$, where $R_1^{*}(h,p)$ counts the solutions to $(4)$ with $x_1,...,x_k$ distinct. We deduce
\[\begin{eqnarray}J_{rk,k}(X)\leq 4\sum_{h}R_1(h)^2\leq 4|\mathcal{P}|^2\max_{p\in\mathcal{P}} \sum_{h}R_1^{*}(h,p)^2.\quad (6)\end{eqnarray}\]
Denoting $I(p):=\sum_{h}R_1^{*}(h,p)$, $I(p)$ counts the solutions to
\[\begin{eqnarray}\sum_{i=1}^{rk}x_i^j=\sum_{i=1}^{rk}y_i^j,\quad 1\leq j\leq k\quad (7)\end{eqnarray}\]
with $0\leq x_i\leq X$ and $x_1,...,x_k$ distinct $\pmod p$, $y_1,...,y_k$ distinct $\pmod p.$ Fix a prime $p\in \mathcal{P}$ (the one that maximizes $I(p)$), and write
\[\begin{eqnarray}f(\alpha,X,m):=\sum_{0\leq n\leq X\atop n\equiv m \pmod p}e(\alpha_kn^k+...+\alpha_1 n).\end{eqnarray}\]
Let $\mathcal{A}$ be the collection of all $k$-tuples whose coordinates are distinct $\pmod p$. In $(7)$, $(x_1,...,x_k)$ and $(y_1,...,y_k)$ are in $\mathcal{A}$, whereas $(x_{k+1},...,x_{rk})$ and $(y_{k+1},...,y_{rk})$ can be arbitrary $\pmod p$. Therefore
\[\begin{eqnarray}I(p)&=&\int_{[0,1]^k}\left|\left(\sum_{0\leq m<p}f(\alpha,X,m)\right)^{(r-1)k}\sum_{a\in \mathcal{A}}f(\alpha,X,a_1)...f(\alpha,X,a_k)\right|^2d\alpha\\&\leq& p^{2(r-1)k-1} \int_{[0,1]^k}\left(\sum_{0\leq m<p}f(\alpha,X,m)|^{2(r-1)k}\right)\left|\sum_{a\in \mathcal{A}}f(\alpha,X,a_1)...f(\alpha,X,a_k)\right|^2d\alpha\\&\leq& p^{2(r-1)k}\max_{0\leq m<p}\int_{[0,1]^k}\left|\sum_{a\in \mathcal{A}}f(\alpha,X,m)^{(r-1)k}f(\alpha,X,a_1)...f(\alpha,X,a_k)\right|^2d\alpha\end{eqnarray}\]
by Hölder's inequality. This integral in turn is the number of solutions to the Diophantine equations
\[\begin{eqnarray}\sum_{i=1}^{k}(x_i^j-y_i^{j})=\sum_{i=1}^{(r-1)k}((pz_i+m)^j-(pw_i+m)^j),\quad 1\leq j\leq k\quad (8)\end{eqnarray}\]
with $x_1,...,x_k$ as well as $y_1,...,y_k$ distinct modulo $p$, and $-\frac{m}{p}\leq y_i,z_i\leq \frac{X-m}{p}.$ This system is actually equivalent to the system
\[\begin{eqnarray}\sum_{i=1}^{k}((x_i-m)^j-(y_i-m)^{j})=\sum_{i=1}^{(r-1)k}p^j(z_i^j-w_i^j)\quad (9).\end{eqnarray}\]
under the same conditions. To simplify notations, we prove the equivalence for $k=2$, but it is straightforward to generalize the proof. We expand by the binomial theorem to see that
By the $j=1$ case in $(8)$, and subtracting the last result from the first, we find that the first system $(8)$ implies the second system $(9)$ (and the converse follows similarly, though we will not need it). We are now in a position to apply Lemma 2 to $(9)$. We have $p^k>X$ and $p>k$, so by Lemma 2, for any given $(y_1,...,y_k)$ and $(h_1,...,h_k)$, the system
\[\begin{eqnarray}\sum_{i=1}^k ((x-i-m)^j-(y_i-m)^j)\equiv h_i\pmod{p^j}, \quad 1\leq j\leq k\end{eqnarray}\]
has at most $k!\cdot p^{\frac{1}{2}k(k-1)}$ solutions with $x_i$ distinct $\pmod p$. Hence, for fixed $z_i$ and $w_i$ but variable $x_i$ and $y_i$, there are no more than $k!\cdot p^{\frac{1}{2}k(k-1)}X^k$ solutions. Moreover, for given $(h_1,...,h_k)$, the system
\[\begin{eqnarray}\sum_{i=1}^{(r-1)k}p^j(z_i^j-w_i^j)=h_j,\quad 1\leq j\leq k\end{eqnarray}\]
has at most $\max_h J_{(r-1)k,k}(\frac{X}{p},-\frac{m}{p},h)$ solutions, where $J_{s,k}(Y,a,h)$ counts the solutions to
\[\begin{eqnarray}\sum_{i=1}^s (x_i^j-y_i^j)=h_j\quad 1\leq j\leq k\end{eqnarray}\]
such that $x_i,y_i\in [a,Y]$. Such a system can be "translated" (so that $x_i,y_i\in [0,Y-a]$ and the equation stays the same) by the binomial formula without altering the number of solutions, so that the bound for $I(p)$ implies
\[\begin{eqnarray}I(p)\leq X^kp^{2(r-1)k+\frac{1}{2}k(k-1)}\cdot k!\cdot J_{(r-1)k,k}\left(1+\frac{X}{p}\right).\end{eqnarray}\]
Thus, by formula $(6)$,
\[\begin{eqnarray}J_{rk,k}(X)\leq 4k^6e^{k\log k}p^{2(r-1)k+\frac{1}{2}k(k+1)}X^k\cdot J_{(r-1)k,k}(X),\end{eqnarray}\]
We can finally employ the induction assumption together with the inequality $1+\frac{X}{p}\leq \frac{X}{p}e^{\frac{p}{X}}$ and the fact that $2(r-1)k-\frac{1}{2}k(k+1)+\eta(r-1,k)\leq 2(r-1)k$. For brevity, we denote $s(m,k):=2mk-\frac{1}{2}k(k+1)+\eta(m,k)$. Then
\[\begin{eqnarray}J_{rk,k}(X)&\leq& e^{10k\log k+c(r-1)k^2\log k}\cdot p^{2(r-1)k+\frac{1}{2}k(k-1)}X^k\left(\frac{X}{p}\right)^{s(r-1,k)}\cdot e^{\frac{2(r-1)kp}{X}}\\&\leq& e^{10k\log k+c(r-1)k^2\log k}\cdot p^{k^2-\eta(r-1,k)}X^{(2r-1)k-\frac{1}{2}k(k+1)+\eta(r-1,k)}\cdot e^{\frac{2(r-1)kp}{X}}\\&\leq& e^{10k\log k+c(r-1)k^2\log k}\cdot 2^{k^2}X^{2rk-\frac{1}{2}k(k+1)+(1-\frac{1}{k})\eta(r-1,k)}\cdot\exp\left(\frac{4k^3}{X^{1-\frac{1}{k}}}\right)\\&\leq& e^{crk^2\log k-1}X^{s(r,k)}\exp\left(\frac{4k^3}{X^{1-\frac{1}{k}}}\right),\end{eqnarray}\]
where we used $p\leq 2M=2X^{\frac{1}{k}}$, the definition of $\eta(r-1,k)$ and assumed that $c$ is large (say $c=1000$). If $X\geq (4k^3)^2$, say, we are done. Otherwise we estimate trivially $J_{rk,k}(X)\leq X^{2rk}=\exp(4rk\log(4k^3))$, which is less than the desired bound. This concludes the proof. ■

When compared to the trivial estimate $J_{rk,k}(X)\leq k!X^{2rk-k}$, Theorem 3 gives a saving of the multiplicative factor $X^{\frac{1}{2}k(k-1)-\eta(r,k)}$ if we ignore the dependence on $k$. When $r\geq 3k\log k$, say, the saving is very significant, as $\eta(r,k)\leq \frac{1}{2k}$ then. We record the following corollary for later use.

Corollary. Let $k$ be a positive integer. For any $s$, not necessarily integral, $s\geq k+3k^2\log k$ implies
\[\begin{eqnarray}J_{s,k}(X)\leq \exp(csk\log k)X^{2s-\frac{1}{2}k(k+1)+\frac{1}{k}}.\end{eqnarray}\]
Also, $s\geq k+2k^2\log k$ implies the same bound with $\frac{1}{2}$ in place of $\frac{1}{2k}$.

Proof. Let $r$ be the largest integer such that $rk\leq s$. For $s\geq k+3k^2\log k$ we have $r\geq 3k\log k$, so that Theorem 3 and $\eta(r,k)\leq \frac{1}{2k}$ give
\[\begin{eqnarray}J_{s,k}(X)&\leq& X^{2(s-rk)}J_{rk,k}(X)\\&\leq& X^{2(s-rk)}\exp(crk^2\log k)X^{2rk-\frac{1}{2}k(k+1)+\frac{1}{2k}}\\&\leq& \exp(csk\log k)X^{2s-\frac{1}{2}k(k+1)+\frac{1}{2k}},\end{eqnarray}\]
as wanted. The other claim is proved completely analogously. ■

Exponential sums with a slowly growing phase function

We put Vinogradov's mean value theorem into use by proving a very general cancellation sums for
\[\begin{eqnarray}\sum_{M\leq n\leq M+N}e(F(n)),\end{eqnarray}\]
where $F$ is smooth (or just many times differentiable). It turns out that a bound of the form $c(k)N^{1-\frac{c_3}{k^2\log k}}$ is valid whenever $\frac{F^{(k+1)}}{(k+1)!}$ varies by at most a factor of $2$ on $[M,M+N]$ and the values of this quantity are relatively close to $\frac{1}{N}$ (this is what we mean by slow growth). In the application to zeta sums, we are not interested only in the case where $k$ is bounded (though that case is already useful), so we preserve the constant $c(k)$ as explicit. Before we prove or formulate the exact theorem, we start with a necessary lemma, concerning how often certain functions can be close to integers.

Lemma 4. Let $\varphi$ be any real-valued function defined on the set of integers $\{M,M+1,...,M+N-1\}$ such that $\varphi(n+1)-\varphi(n)\in [\delta,a\delta]$ for some $a>1,\delta>0$ and all $n=M,M+1,...,M+N-2$. Let $W>0$. Then the number of solutions to the inequality
\[\begin{eqnarray}\|\varphi(n)\|\leq W\delta\end{eqnarray}\]
is less than $(Na\delta+1)(2W+1)$, where, as usual, $\|\cdot\|$ denotes the distance to the nearest integer.

Proof. We may assume $W\delta<\frac{1}{2}$, as otherwise $(Na\delta+1)(2W+1)>N$. Let $n_0\in [M,M+N-1]$ be any solution to $\|\varphi(n)\|\leq W\delta$.
Define $y$ by $W\delta+ya\delta=1-W\delta$. Then among the integers $n_0,...,n_0+\lfloor y\rfloor$ there are at most $2W+1$ solutions to the inequality. This is obvious because $\varphi(n)$ is an increasing function which grows at each step by at least $\delta$ but by not more than by $a\delta$. We have $y=\frac{1-2W\delta}{a\delta}$, so starting from any solution $n_0$ to the inequality, there is a block of $1+\lfloor\frac{1-2W\delta}{a\delta}\rfloor\geq \frac{1-2W\delta}{a\delta}$ consecutive integers containing at most $2W+1$ solutions. This means that on $[M,M+N-1]$ there are at most
\[\begin{eqnarray}N\cdot \frac{2W+1}{\frac{1-2W\delta}{a\delta}}+(2W+1)<(Na\delta+1)(2W+1)\end{eqnarray}\]
solutions ($2W+1$ was added because some of the numbers $n_0+1,...,n_0+\lfloor y\rfloor$ may lie outside the range $[M,M+N-1]$).■

We are ready to state and prove the estimate for exponential sums with slowly growing phase.

Theorem 5 (Vinogradov). Let $k$ be a positive integer and let $F$ be any $k+1$ times continuously differentiable real-valued function on the positive real numbers. Also let $M<N,N\geq 2$, and assume that
\[\begin{eqnarray}\left|\frac{F^{(k+1)}(x)}{(k+1)!}\right|\in [\lambda, 2\lambda]\end{eqnarray}\]
for all $M\leq x\leq M+N$ and some $\lambda$. We have
\[\begin{eqnarray}\left|\sum_{M\leq n\leq M+N}e(F(n))\right|\leq e^{Ck\log k}N^{1-\frac{1}{100k^2\log k}}\end{eqnarray}\]
for an absolute constant $C>0$, given that one of the following holds.
(i) $k\geq 6$ and $\lambda^{-\frac{1}{4}}\leq N\leq \lambda^{-1}$
(ii) $k\geq 3$ and $\lambda^{-0.9}\leq N\leq \lambda^{-1}$.

Proof. $(i)$ We seek to bound the exponential sum by an average of a "differenced" version of it, namely
and $q$ is to be optimized subsequently (this same idea reappears when we cstudy Weyl sums). This upper bound will then be estimated further to something depending on $J_{\ell,k}(q)$, where
\[\begin{eqnarray}\ell=k+2k^2\log k,\end{eqnarray}\]
and then Vinogradov's mean value theorem becomes useful. To verify the first upper bound, we observe
\[\begin{eqnarray}q\left|\sum_{M\leq n\leq M+N}e(F(n))\right|&=&\left|\sum_{m=1}^{q}\sum_{M\leq n\leq M+N}e(F(n))\right|\\&\leq& \left|\sum_{m=1}^{q}\sum_{n=M+1+m}^{M+N+m-q}e(F(n))\right|+\sum_{m=1}^{q}q\\&=&\left|\sum_{m=1}^{q}\sum_{n=M+1}^{M+N-q}e(F(m+n))\right|+q^2\\&\leq& \sum_{m=1}^{q}\left|\sum_{n=M+1}^{M+N-q}(e(F(m+n))-F(n))\right|+q^2\\&=&\sum_{n=M+1}^{M+N-1}|T(n)|+q^2.\end{eqnarray}\]
By Hölder's inequality,
\[\begin{eqnarray}\sum_{n=M+1}^{M+N-1}|T(n)|\leq N^{1-\frac{1}{2\ell}}\left(\sum_{n=M+1}^{M+N-1}|T(n)|^{2\ell}\right)^{\frac{1}{2\ell}},\end{eqnarray}\]
and we wish to compare $T(n)$ to $f(\alpha,q)$ (this notation is the same as earlier) for a suitable $\alpha$, and then the $2\ell$th moment of $T(n)$ to the $2\ell$th moment of $f(\alpha,q)$, which is $J_{\ell,k}(q)$. We express
\[\begin{eqnarray}F(m+n)-F(n)=A_1m+..+A_km^k+2\lambda\cdot \theta q^{k+1},\quad |\theta|\leq 1,\end{eqnarray}\]
where $A_r=A_r(n)=\frac{F^{(r)}(n)}{r!}$, $\lambda$ is as in the theorem and we have applied a generalized intermediate value theorem. For $1\leq m\leq q$ we have
\[\begin{eqnarray}&&|e(F(m+n)-F(n))-e(\alpha_km^k+...+\alpha_1m)\\&\leq& 2\pi|(F(m+n)-F(n)-\alpha_km^k-...-\alpha_1m|\\&\leq& 2\pi \sum_{r=1}^{k}|\alpha_r-A_r|m^r+4\pi \lambda q^{k+1}.\end{eqnarray}\]
Let $Q_n$ be the $k$-dimensional box
\[\begin{eqnarray}Q_n=\prod_{r=1}^{k}\left[A_r(n)-\frac{1}{2}\lambda q^{k+1-r},A_r(n)+\frac{1}{2}\lambda q^{k+1-r}\right],\end{eqnarray}\]
so that for $\alpha\in Q_n$ we get
\[\begin{eqnarray}2\pi \sum_{r=1}^{k}|\alpha_r-A_r|m^r+4\pi \lambda q^{k+1}&\leq& \pi \lambda q^{k+1}\sum_{r=1}^k \left(\frac{m}{q}\right)^r+4\pi \lambda q^{k+1}\\&\leq& \pi \lambda q^{k+1}(k+4)\leq 5\pi k\lambda q^{k+1}.\end{eqnarray}\]
Therefore, for $\alpha\in Q_n$,
\[\begin{eqnarray}|T(n)|\leq |f(\alpha,q)|+5\pi \lambda q^{k+2}\end{eqnarray}\]
\[\begin{eqnarray}|T(n)|^{2\ell}\leq 2^{2\ell}(|f(\alpha,q)|^{2\ell}+(5\pi \lambda q^{k+2})^{2\ell}).\end{eqnarray}\]
We arrive at the estimate
\[\begin{eqnarray}|T(n)|^{2\ell}\leq \frac{2^{\ell}}{|Q_n|}\int_{Q_n}|f(\alpha,q)|^{2\ell}d\alpha+(10\pi \lambda q^{k+2})^{2\ell}.\end{eqnarray}\]
Thus, calculating the measure of $Q_n$,
\[\begin{eqnarray}\sum_{m=M+1}^{M+N-q}|T(n)|^{2\ell}&\leq& 2^{2\ell}q^{\frac{1}{2}k(k+1)}(\lambda q^{k+1})^{-k}\int_{[0,1]^k}|f(\alpha,q)|^{2\ell}\sum_{n=M+1}^{M+N-q}1_{Q_n'}(\alpha)d\alpha\\&+&(N-q)(10\pi \lambda q^{k+2})^{2\ell},\end{eqnarray}\]
where $Q_n'$ is a sort of translate of $Q_n$ to the cube $[0,1]^k$; $Q_n'$ is the image of $Q_n$ under $x\mapsto x\pmod 1$. This transformation is allowed by the periodicity of the integrand. We are going to prove that any $\alpha$ does not belong to too many boxes $Q_n'$, and then we get an estimate for the $2\ell$th moment of $T(n)$ in terms of $J_{\ell,k}(q)$.

Suppose $\alpha$ belongs to at least one set $Q_{n_0}'$. Let $Q_n'$ be any other ''translate'' of a box containing $\alpha$. Then
\[\begin{eqnarray}\|A_k(n)-A_{k}(n_0)\|\leq \lambda q.\end{eqnarray}\]
Clearly, $\alpha$ does not belong to more $Q_n'$s than there are solutions $n\in [M,M+N]$ to this inequality. Here Lemma 4 comes into use, with $\varphi(n)=A_k(n)-A_k(n_0)$ and
\[\begin{eqnarray}\varphi(n+1)-\varphi(n)=\frac{F^{(k)}(n+1)-F^{(k)}(n)}{k!}=\frac{F^{k+1}(n+\xi)}{k!},\quad \xi\in [0,1],\end{eqnarray}\]
so that we may take $\delta=\lambda(k+1)$, $a=2$ and $W=\frac{q}{k+1}$, if $F^{(k)}(x)$ is positive on $[M,N]$. By assumption, $F^{(k)}(x)$ does not change sign on $[M,N]$, so by symmetry we may suppose that it is indeed positive. Lemma 4 results in the inequality having at most
solutions, since $N\leq \frac{1}{\lambda}$. We deduce
\[\begin{eqnarray}\sum_{n=M+1}^{M+N-q}|T(n)|^{2\ell}\leq 2^{2\ell}q^{\frac{1}{2}k(k+1)}(\lambda q^{k+1})^{-k}\cdot 9kq\cdot J_{\ell,k}(q)+(N-q)(10\pi \lambda q^{k+2})^{2\ell}.\end{eqnarray}\]
The corollary to Vinogradov's mean theorem yields the inequality
\[\begin{eqnarray}\,&&\left|\sum_{M\leq n\leq M+N}e(F(n))\right|\\&\leq& q^{-1}N^{1-\frac{1}{2\ell}}(2^{2\ell}q^{\frac{1}{2}k(k+1)}(\lambda q^{k+1})^{-k}\cdot 9kq\cdot J_{\ell,k}(q)+(N-q)(10\pi \lambda q^{k+2})^{2\ell})^{\frac{1}{2\ell}}+q\\&\leq& 4N^{1-\frac{1}{2\ell}}(\lambda^{-\frac{k}{2\ell}}q^{-\frac{1}{4}k(k+1)\ell^{-1}+\frac{3}{4}\ell^{-1}}e^{ck\log k} (9k)^{\frac{1}{2\ell}})+N\cdot 10\pi k\lambda q^{k+1}+q\end{eqnarray}\]
We optimize in $q$, $1\leq q \leq N.$ Set $q=\lfloor\lambda^{-\gamma}\rfloor,\gamma=\frac{1-\eta}{k+1},0<\eta<1.$ Then $1\leq q \leq N^{\frac{4(1-\eta)}{k+1}}<N$ for $k\geq 3.$ Since $\lambda^{-1}$ is large ($\lambda\geq N$), we may ignore the floor in the definition of $q$ and using $\lambda\leq N^{-1},\lambda^{-1}\leq N^4$ obtain the bound
\[\begin{eqnarray}\left|\sum_{M\leq n\leq M+N}e(F(n))\right|&\leq&(N^{1-\frac{1}{2\ell}}\lambda^{\frac{-k-\gamma(\frac{3}{2}-k(k+1))}{2\ell}}+\lambda^{-(k+1)\gamma}+\lambda^{-\gamma})e^{Ck\log k}\\&\leq& (N^{1-\frac{1}{2\ell}+\frac{2}{\ell}(\eta k+\frac{3(1-\eta)}{2(k+1)})}+N^{\gamma(k+1)})e^{Ck\log k},\end{eqnarray}\]
provided $-k+\gamma(k(k+1)+\frac{3}{2})<0$. We set the two powers of $N$ to be equal. We get
\[\begin{eqnarray}1-\frac{1}{2\ell}+\frac{2}{\ell}\left(\eta k+\frac{3(1-\eta)}{2(k+1)}\right)=1-\eta,\end{eqnarray}\]
or equivalently
\[\begin{eqnarray}\eta=\frac{\frac{1}{2\ell}-\frac{3(1-\eta)}{\ell(k+1)}}{1+\frac{2k}{\ell}}=\frac{\frac{1}{2}-\frac{3(1-\eta)}{k+1}}{2\ell+k}>\frac{\frac{1}{20}}{2\ell+k}>\frac{1}{100k^2\log k}\end{eqnarray}\]
for $k\geq 6$. To summarize,
\[\begin{eqnarray}\left|\sum_{M\leq n\leq M+N}e(F(n))\right|\leq N^{1-\eta}e^{Ck\log k}\leq e^{Ck\log k}N^{1-\frac{1}{100k^2\log k}},\end{eqnarray}\]
so the proof is finished in this case. ■

$(ii)$ The proof above goes verbatim until we apply $\lambda\leq N^{-1},\lambda^{-1}\leq N^4$ near the end. Here we use $\lambda\leq N^{-1},\lambda^{-1}\leq N^{\frac{10}{9}}$ instead. Again we set the resulting powers of $N$ to be equal, we have
\[\begin{eqnarray}\eta=\frac{\frac{1}{2\ell}-\frac{\frac{10}{9}\cdot3(1-\eta)}{2\ell(k+1)}}{1+\frac{k}{2\ell}}>\frac{\frac{1}{20}}{2\ell+k}>\frac{1}{100k^2\log k},\end{eqnarray}\]
completing the proof also in this case. ■

Weyl Sums and Weyl differencing

We now study Weyl sums. One could use Vinogradov's mean value theorem together with inequalities bounding a Weyl sum by something depending on $J_{s,k}(N)$ to derive a bound of the form
\[\begin{eqnarray}\left|\sum_{n\leq N}e(\alpha P(n))\right|\ll N^{1-\frac{c_4}{k^2\log k}},\end{eqnarray}\]
where $P$ is a monic polynomial of degree $k$ (not necessarily with integral coefficients), $\alpha$ is an irrational number having bounded continued fraction coefficients, and the implicit constant depends only on $k$ (one would naturally obtain a bound even if $\alpha$ does not have bounded continued fraction coefficients, but then we might save a smaller power of $N$).

Nevertheless, we follow a different approach to Weyl sums, as the approach outlined above requires considerably more work than the following simple method of Weyl. The multiplicative saving in Weyl's estimates is only around $N^{-2^{1-k}}$ at best, when compared to the trivial estimate $N$, but this is already sufficient for various things (such as proving Waring's conjecture) and is almost the best that is known in the "minor arc case", where $\alpha$ is close to a rational with a small denominator. In addition, when $k$ is small, the Weyl differencing method produces stronger results than the ones following from Vinogradov's mean value theorem We remark that $N^{-\frac{1}{k}}$ would generally be the best possible multiplicative saving for Weyl sums, as is illustrated by the following special case.

Proposition 6. Let $p$ be a prime not dividing $k$, and let $N=p^k$. For any integer $a$ coprime to $p$, we have
\[\begin{eqnarray}\Sigma(a,q):=\sum_{n=0}^{N-1} e\left(\frac{a}{N}n^k\right)=N^{1-\frac{1}{k}}.\end{eqnarray}\]
Proof. To show this, we alter the summation index into $n=p^{k-1}m+r$, $0\leq m\leq p-1,0\leq r\leq p^{k-1}-1$. We get
\[\begin{eqnarray}\Sigma(a,q)=\sum_{r=0}^{p^{k-1}-1}\sum_{m=0}^{p-1} e\left(\frac{a(kp^{k-1}mr^{k-1}+r^{k})}{N}\right).\end{eqnarray}\]
As $p$ does not divide $a$ or $k$ and $N=p^k$, the inner sum over $m$ equals zero unless $r=0$, in which case we have a sum of $p^{k-1}$ ones, giving the result. ■

The basic idea behind Weyl's method is simple: we square the Weyl sum involving a polynomial of degree $k$ and rearrange the squared sum as an average of "differenced" Weyl sums involving the polynomials $P(n)-P(n-h)$, each of degree $k-1$. This reduces estimating the original sum to estimating several sums with polynomials of lower degree, so we can apply induction. We illustrate this in the case $k=2$ before moving on to the general case. Observe that
\[\begin{eqnarray}\left|\sum_{n\leq N}e(\alpha_2n^2+\alpha_1n)\right|^2&=&\sum_{m\leq N}\sum_{n\leq N}e(\alpha_2(n^2-m^2)+\alpha_1(n-m))\\&=&\sum_{m\leq N}\sum_{-n\leq h\leq N-n}e(2\alpha_2 mh+\alpha_1h+\alpha_2h^2).\end{eqnarray}\]
This is bounded in modulus by
\[\begin{eqnarray}\sum_{m\leq N}\left|\sum_{-n\leq h\leq N-n}e(2\alpha_2 mh)\right|\leq \sum_{m\leq N}\min\left\{N,\frac{1}{\|2\alpha m\|}\right\},\quad (10)\end{eqnarray}\]
and this is an expression that can certainly be bounded in a useful manner. We proceed to the general case, where we also estimate such sums.

Theorem 7. Let $\varepsilon>0$ be fixed, and let $\alpha$ be a real number such that $|\alpha-\frac{a}{q}|\leq \frac{1}{q^2}$ with $a$ and $q$ coprime. We have
\[\begin{eqnarray}\left|\sum_{n\leq N}e(\alpha P(n))\right|\ll_{k} N^{1+\varepsilon}\left(\frac{1}{q}+\frac{1}{N}+\frac{q}{N^{k}}\right)^{2^{1-k}}\end{eqnarray}\]
for any monic polynomial $P$ of degree $k\geq 2$.

Proof. We first prove by induction on $k$ that
\[\begin{eqnarray}|f(\alpha,N)|^K\leq 2^{2K}N^{K-1}+2^K N^{K-k}\sum_{m_1,...,m_{k-1}=1}^{N-1}\min\left\{N,\frac{1}{\|\alpha k!m_1...m_{k-1}\|}\right\},\end{eqnarray}\]
where $K=2^{k-1}$ and $\|\cdot\|$ is the distance to the nearest integer. The assumptions on $\alpha$ are as in the theorem. The case $k=2$ has already been established in formula $(10)$. Now suppose the cases up to $k-1$ have been proved, and consider a monic polynomial $P$ of degree $k$. We square and expand to obtain
\[\begin{eqnarray}|f(\alpha,N)|^2&=&\sum_{|h|\leq N-1}\sum_{n=\max\{h+1,1\}}^{\min\{h+N,N\}}e(\alpha P(n)-\alpha P(n-h))\\&=&\sum_{|h|\leq N-1}\sum_{n=\max\{h+1,1\}}^{\min\{h+N,N\}}e(\alpha khn^{k-1}+...).\end{eqnarray}\]
Denoting by $S_h$ the inner sum, Hölder's inequality tells that
\[\begin{eqnarray}|f(\alpha,N)|^2\leq (2N)^{1-\frac{2}{K}}\left(N^{\frac{K}{2}}+\sum_{|h|\leq N-1\atop h\neq 0}|S_h|^{\frac{K}{2}}\right)^{\frac{2}{K}}.\quad (11)\end{eqnarray}\]
Further, the trivial inequality $|S_h|\leq |S_N|$ combined with the induction hypothesis yields
\[\begin{eqnarray}|S_h|^{\frac{K}{2}}\leq 2^{K}N^{\frac{K}{2}-1}+2^{\frac{K}{2}}N^{\frac{K}{2}-k+1}\sum_{m_2,...,m_{k-1}=1}^{N-1}\min\left\{N,\frac{1}{\|(kh\alpha) (k-1)!m_2...m_{k-1}\|}\right\}\end{eqnarray}\]
Raising both sides of $(11)$ to the power of $\frac{K}{2}$ and applying the previous formula, we see that
\[\begin{eqnarray}|f(\alpha,N)|^{K}&\leq& 2^{\frac{K}{2}-1}N^{\frac{K}{2}-1}\Big(N^{\frac{K}{2}}+2^{K}N^{\frac{K}{2}-1}\cdot N\\&+&2^{\frac{K}{2}+1}N^{\frac{K}{2}-k+1}\sum_{h,m_2,...,m_{k-1}=1}^{N-1}\min\left\{N,\frac{1}{\|\alpha k!h m_2...m_{k-1}\|}\right\}\Big),\end{eqnarray}\]
so the induction is finished.

Next, notice that for any $m\leq M$ the equation $m=k!m_1...m_{k-1}$ has $\ll_{k} M^{\varepsilon}$ solutions. Indeed, if $\tau_k(M)$ denotes this number of solutions to $M=a_1...a_k$ in positive integers, then
\[\begin{eqnarray}\tau_k(M)=\sum_{m\mid M}\frac{\tau_{k-1}\left(\frac{M}{m}\right)}{m},\end{eqnarray}\]
for $k\geq 3$ from which the bound $\tau_k(M)\ll_{k} M^{\varepsilon}$ follows by induction, when we take into account the well-known inequality $\tau_2(M)\ll M^{\varepsilon}$. Thus
\[\begin{eqnarray}|f(\alpha,N)|^K&\leq& 2^{2K}N^{K-1}+2^K N^{K-k}(k!N^{k-1})^{\varepsilon}\sum_{m=1}^{N^{k-1}}\min\left\{N,\frac{1}{\|\alpha m\|}\right\}\\&\leq& 2^{2K}N^{K-1}+2^K N^{K-k}(k!N^{k-1})^{\varepsilon}\sum_{m=1}^{N^{k-1}}\min\left\{\frac{N^k}{m},\frac{1}{\|\alpha m\|}\right\}\\&\ll& 2^{2K}N^{K-1}+2^K N^{K-k}(kN)^{k\varepsilon}\left(\frac{k!N^k}{q}+q+k!N^{k-1}\right)\log(qN^{k-1})\end{eqnarray}\]
by Lemma 3 of this post on prime exponential sums. That lemma required the assumption $|\alpha-\frac{a}{q}|\leq \frac{1}{q^2}.$ We find that
\[\begin{eqnarray}|f(\alpha,N)|^K\ll 2^{2K}N^{K-1}+2^KN^{K}(kN)^{k\varepsilon}k!\left(\frac{1}{q}+\frac{1}{N}+\frac{q}{N^k}\right)\log (qN^{k-1}).\end{eqnarray}\]
When we take the $K$th root, all the constants depending on $k$ become bounded, so
\[\begin{eqnarray}|f(\alpha,N)|\ll_k N^{1+\varepsilon'}\left(\frac{1}{q}+\frac{1}{N}+\frac{q}{N^k}\right)^{2^{1-k}}\end{eqnarray}\]
for $q\leq N^k$ (otherwise the bound is useless), as then $\log N\leq N^{\varepsilon}$ for large $N$. Here $\varepsilon'$ differs from $\varepsilon$ but can still be taken to be any fixed positive number. This completes the proof. ■