Let $f(x)$ be a function such that for all $T \leq f(x), \ T / x \to \infty$ we have $$ \sum_{x \leq n < 2 x} e^{2 \pi i T / n} = o(x). $$ How fast can $f(x)$ grow?

I can show that for any $\varepsilon > 0$, $f(x) = e^{(\log x)^{2 - \varepsilon}}$ works, and that any such function $f$ must satisfy $f(x) \leq e^{x^{\varepsilon}}$ for large enough $x$, and I am interested in an improvement of either of these bounds.

For the lower bound, I tried the two standard methods I know of to deal with exponential sums which are Poisson summation and Weyl differencing. Poisson summation seemed to lead nowhere, as this sum is very rapidly oscillating.

Weyl differencing leads to the lower bound I've written. The problem with iterated Weyl differencing is that applying it more than $\log x$ times is useless, because even if each sum (after the iterated Weyl differencing) was bounded by $\mathcal{O}(1)$, we still could not get a nontrivial bound. This happens because applying the triangle inequality many times "loses" cancellation.

As for the upper bound, taking $T = \operatorname{lcm} (1, \dotsc, 2 x)$ leads to an upper bound of $e^{2 x}$, and this can be improved by taking $T = k \cdot \operatorname{lcm} (1, \dotsc, x^{\varepsilon} )$, where $\varepsilon > 0$ is fixed and $k$ is a small random number. The trick here is that the probability that a natural number of size at most $x$ is $x^{\varepsilon}$-smooth (has all prime factors at most $x^\varepsilon$) is a positive constant. Thus, running over (say) $k \leq x^2$ and taking the expected value of the sum, we see that on average it is a positive constant times $x$, and thus for some $k$ the sum has absolute value at least a constant times $x$.

  • $\begingroup$ I changed "has all prime factors at most $\varepsilon$" to "has all prime factors at most $x^\varepsilon$". I hope that was correct. $\endgroup$
    – LSpice
    Commented Apr 28, 2023 at 20:19

1 Answer 1


I doubt that one is able to get as far as $T = \exp(\log^{2-\varepsilon} x)$ with Weyl differencing. Standard Weyl differencing arguments, such as that in Theorem 8.4 of

Iwaniec, Henryk; Kowalski, Emmanuel, Analytic number theory, Colloquium Publications. American Mathematical Society 53. Providence, RI: American Mathematical Society (AMS) (ISBN 0-8218-3633-1/hbk). xi, 615 p. (2004). ZBL1059.11001.

give the bound $$\sum_{x \leq n < 2x} e^{2\pi i T/n} \ll (T/x^{k+1} + x/T)^{4/k2^k} x \log x$$ for any $k \geq 2$, which after optimising in $k$ gives a non-trivial bound only for $T$ as large as $\exp( c \log x \log\log x )$ for some absolute constant $c>0$. Van der Corput's method (Theorem 8.20 of Iwaniec--Kowalski) gives a similar range (and can also cover the easy range $x \lll T \ll x^{O(1)}$ that is not quite covered by the above estimate). Basically, each application of Weyl differencing (or the van der Corput inequality) applies a square root to the gain, so one can only expect to apply this method no more than $O(\log\log x)$ times before the gain vanishes (up to constants).

The state of the art is given by Vinogradov's method (Theorem 8.25 of Iwaniec--Kowalski), which yields $$\sum_{x \leq n < 2x} e^{2\pi i T/n} \ll x \exp( -c \log^3 x / \log^2 T )$$ for some absolute constant $c>0$, assuming for instance that $T \geq x^2$. (Roughly speaking, Vinogradov manages to lower the $k2^k$ denominator in the exponent of Weyl's method all the way to $k^2$.) This is non-trivial for $T = \exp(o(\log^{3/2} x))$. Even the recent advances on the Vinogradov mean value theorem via decoupling or efficient congruencing have unfortunately failed to make further improvements on this bound (other than perhaps improving the value of $c$), which has stood for over six decades. This estimate (applied to the extremely similar sum $\sum_{x \leq n < 2x} e^{2\pi i T \log n}$) is the main input in the current best known (up to constants) asymptotic zero free region for the Riemann zeta function, due to Vinogradov and Korobov, which has similarly stood for six decades, so further improvement in this direction seems very difficult.

EDIT: See also my lecture notes on these topics.

SECOND EDIT: Any increase in the range of $T$ for which one gains non-trivial estimates on $\sum_{x \leq n < 2x} e^{2\pi i T/n}$ in particular would likely also lead to progress on Singmaster's conjecture; see Footnote 2 of this paper of mine with Matomäki, Radziwiłł, Shao, and Teräväinen.

  • $\begingroup$ $+1$, thanks! Why is $\sum_{x \le n < 2x} e^{2\pi i T \log n}$ "extremely similar"? $\endgroup$ Commented Apr 29, 2023 at 15:55
  • 3
    $\begingroup$ All of the exponential sum methods mentioned here can handle sums of the form $\sum_{x \leq n < 2x} e^{2\pi i f(n)}$ where $f$ is a smooth function obeying bounds such as $\alpha^{-j^2} F \leq \frac{t^j}{j!} |f^{(j)}(t)| \leq \alpha^{j^2} F$ for some constants $\alpha, F$ and all $t \in [x,2x]$, and some suitable range of $j$. Both $t \mapsto T/t$ and $t \mapsto T \log t$ obey estimates of this form (with $\alpha \asymp 1$ and $F$ equal to $T/x$ in the former case and $T$ in the latter case). $\endgroup$
    – Terry Tao
    Commented Apr 29, 2023 at 16:18
  • $\begingroup$ Thanks, this is exactly what I was looking for. Regarding your second edit, I think the upper bound I describe in the question shows that contrary to what is conjectured in footnote $2$, the upper bound on $M, N$ cannot be relaxed all the way to $O(\text{exp} (P^c))$ right? $\endgroup$
    – Random
    Commented Apr 29, 2023 at 19:59
  • 1
    $\begingroup$ For the sum $\sum_{x \leq n \leq 2x} e^{2\pi i T/n}$, yes; but for our specific application we were actually concerned with the variant sum $\sum_{x \leq p \leq 2x} e^{2\pi i T/p}$ over primes, to which your upper bound construction doesn't apply. (That said, currently the only way to control the sum over primes is to first control the sum over natural numbers, so some other method would have to be used if we were to ever get close to that conjecture.) $\endgroup$
    – Terry Tao
    Commented Apr 29, 2023 at 20:44
  • $\begingroup$ One more question: as you've mentioned here and in the blog, both methods essentially approximate $1/n$ by its Taylor expansion. Are there other methods that work specifically for $1/n$ or $\log n$ and not for generic smooth functions $f$ (that maybe give less optimal bounds than Vinogradov's method)? The reason I ask is that for $k > \log x$ (that is, $T > e^{\log(x)^2}$) we cannot approximate $T/n$ with its Taylor expansion, so another idea must be used to get past this. $\endgroup$
    – Random
    Commented Apr 30, 2023 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.