Problem 510

Erdős Problem #510: declared status 'open'. Formalized: yes. If $A\subset \mathbb{Z}$ is a finite set of size $N$ then is there some absolute constant $c>0$ and $\theta$ such that$$\sum_{n\in A}\cos(n\theta) < -cN^{1/2}?$$ Current best: Ruzsa [Ru04] (improving on an earlier result of Bourgain [Bo86]), proved an upper bound of$$-\exp(O(\sqrt{\log N})).$$Polynomial bounds were proved independently by Bedert [Be25c] and Jin, Milojevi\'{c}, Tomon, and Zhang [JMTZ25]. The best bound follows from the method of Bedert [Be25c], which proved the existence of some $c>0$ such that, for all $A$ of size $N$,$$\sum_{n\in A}\cos(n\theta) < -cN^{1/7}.$$The example $A=B-B$, where $B$ is a Sidon set, shows that $N^{1/2}$ would be the best possible here. Prize: no. Tags: analysis.