This is Problem 7.21 in [Ha74], where it is attributed to Erdős.

Erdős [Er64b] remarks it is 'easy to see' that\[\limsup_{k\to \infty}\left(\sup_n\left\lvert \sum_{j\leq n} e(kx_j)\right\rvert\right)=\infty.\]Erdős [Er65b] later found a 'very easy' proof that $A_k\gg \log k$ for infinitely many $k$. Clunie [Cl67] proved that $A_k\gg k^{1/2}$ infinitely often, and that there exist sequences with $A_k\leq k$ for all $k$. Tao has independently found a proof that $A_k\gg k^{1/2}$ infinitely often (see the comment section).

Liu [Li69] showed that, for any $\epsilon>0$, $A_k\gg k^{1-\epsilon}$ infinitely often, under the additional assumption that there are only a finite number of distinct points. Clunie observed in the Mathscinet review of [Li69], however, that under this assumption in fact $A_k=\infty$ infinitely often.

The question of whether $A_k=o(k)$ is possible (repeated in [Er65b] and [Ha74]) seems to still be open.

View the LaTeX source

This page was last edited 29 December 2025.