Problem #510: If $A\subset \mathbb{Z}$ is a finite set of size $N$ then...

---

Progress

Chowla's cosine problem. 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ć, 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.

This problem is Problem 81 on Green's open problems list.

This is related to [256].