Chowla's cosine problem

A sum of cosines $\sum_{a\in A}\cos(ax)$ over $N$ distinct positive integers equals $N$ at $x=0$ and has average $0$, so it must become negative somewhere. How negative? Chowla asked in 1965 whether it always dips below $-c\sqrt N$, which would be best possible. For decades the known bounds were sub-polynomial; polynomial bounds arrived only in 2025.

Problem

For a finite set $A$ of $N$ distinct positive integers let

$$f_A(x)=\sum_{a\in A}\cos(ax).$$

Is there an absolute constant $c>0$ such that for every such $A$

$$\min_{x\in[0,2\pi]} f_A(x)<-c\,N^{1/2}\,?$$

Background

The question is known as Chowla's cosine problem, after Chowla's 1965 paper, and Erdős recorded it among his problems. The exponent $1/2$ cannot be improved: if $B$ is a Sidon set, so that all differences of distinct elements of $B$ are distinct, then taking $A$ to be the positive differences $B-B$ gives cosine sums whose minimum is only of order $-\sqrt N$. The problem is Problem 81 on Ben Green's list of open problems, and it is related to the problem of Erdős and Szekeres on the maximum of $\prod_i\lvert1-z^{a_i}\rvert$ on the unit circle, where good bounds for cosine sums give good bounds for the product.

What is known

• Sub-polynomial bounds. Ruzsa (2004), improving an earlier bound of Bourgain (1986), showed that the minimum is at most $-\exp(c\sqrt{\log N})$ for some $c>0$.
• Polynomial bounds. In 2025 Jin, Milojević, Tomon and Zhang, via a result on graphs with small smallest eigenvalue, proved $\min f_A\le-N^{1/10-o(1)}$, and independently Bedert proved a polynomial bound; the current version of Bedert's paper gives

  $$\min_x f_A(x)\le -N^{1/5-o(1)}.$$

• Small cases. Exact values of the extremal minimum are known for $N=2,3$ (Mercer, 2019), and certified computations for somewhat larger $N$ have been reported on the problem's forum.

What would count as progress

• A bound $\min f_A\le -N^{\gamma}$ with $\gamma>1/5$, with a complete proof.
• An infinite family of sets $A$ whose cosine sums stay above $-N^{1/2-\delta}$ for a fixed $\delta>0$, which would disprove the conjecture; the minimum of an explicit cosine polynomial can be certified numerically with interval arithmetic.
• A formal proof against the Lean statement in formal-conjectures.

References

1. S. Chowla, Some applications of a method of A. Selberg, J. Reine Angew. Math. 217 (1965), 128–132. doi:10.1515/crll.1965.217.128
2. J. Bourgain, Sur le minimum d'une somme de cosinus, Acta Arith. 45 (1986), 381–389. doi:10.4064/aa-45-4-381-389
3. I. Z. Ruzsa, Negative values of cosine sums, Acta Arith. 111 (2004), 179–186. doi:10.4064/aa111-2-6
4. Z. Jin, A. Milojević, I. Tomon and S. Zhang, From small eigenvalues to large cuts, and Chowla's cosine problem (2025). arXiv:2509.03490
5. B. Bedert, Polynomial bounds for the Chowla cosine problem (2025). arXiv:2509.05260

Source

Imported from Erdős Problems 510, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.