# 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](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/510.lean).

## 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](https://doi.org/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](https://doi.org/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](https://doi.org/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](https://arxiv.org/abs/2509.03490)
5. B. Bedert, Polynomial bounds for the Chowla cosine problem (2025). [arXiv:2509.05260](https://arxiv.org/abs/2509.05260)

## Source

Imported from [Erdős Problems 510](https://www.erdosproblems.com/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.