Chowla's cosine problem: is $\min_\theta\sum_{n\in A}\cos(n\theta)\le -cN^{1/2}$ for every $N$-set? (Erdős #510)
Statement
If $A\subset\mathbb{Z}$ is a finite set of size $N$, must there exist an absolute constant $c>0$ and a real $\theta$ such that $$\sum_{n\in A}\cos(n\theta) < -cN^{1/2}?$$ That is: writing $m(A)=-\min_{\theta}\sum_{n\in A}\cos(n\theta)$, is $m(A)\gg N^{1/2}$ for every $N$-element set of integers?
Acceptance. FULLY RESOLVES: a proof that there is an absolute $c>0$ such that every finite $A\subset\mathbb{Z}$ of size $N$ admits $\theta$ with $\sum_{n\in A}\cos(n\theta)<-cN^{1/2}$ (machine-checkable proof preferred, matching the formal-conjectures Lean statement, else a complete written proof); OR a disproof: an explicit infinite family of sets $A_N$ with $m(A_N)=o(N^{1/2})$, with proof. No finite computation alone can settle either direction. ADVANCES: (a) a lower bound $m(A)\gg N^{\alpha}$ with exponent $\alpha$ strictly greater than the $1/7$ stated in the background, with proof; (b) a proof of the full $N^{1/2}$ bound for a natural class of sets (e.g. sets of bounded doubling, unions of few Sidon-difference structures); (c) a certified computational determination of the extremal values $\min_{|A|=N} m(A)$ for small $N$ (exhaustive or branch-and-bound search over sets, rigorous global optimization over $\theta$), with code, certificates, and the extremal sets — extending whatever range is documented in the submission's own literature review; (d) a Lean formalization of one of the key bounds (Ruzsa's, or the polynomial-bound argument). Deliver the proof file, or the family plus proof, or the code with certificates and tables.
Background
This is Chowla's cosine problem, recorded by Erdős [Er61, p.248] and appearing as Problem 81 on Ben Green's open problems list; listed as open on erdosproblems.com/510 (fetched 2026-07-13, status 'open', tagged 'analysis'). The conjectured order is best possible: taking $A=B-B$ for a Sidon set $B$ gives $\sum_{n\in A}\cos(n\theta)$ essentially equal to $|\sum_{b\in B}e(b\theta)|^2-|B|\geq -|B|\approx -N^{1/2}$, so no bound stronger than $N^{1/2}$ can hold. Known frontier: Bourgain [Bo86] gave the first substantial lower bound on $m(A)$, improved by Ruzsa [Ru04] to $m(A)\geq \exp(O(\sqrt{\log N}))$-type growth; the long-standing sub-polynomial barrier was broken only recently, with polynomial bounds proved independently by Bedert [Be25c] and by Jin, Milojević, Tomon, and Zhang [JMTZ25]. The best current bound follows from Bedert's method: there is $c>0$ with $$\sum_{n\in A}\cos(n\theta)<-cN^{1/7}$$ for some $\theta$, for every $A$ of size $N$. The gap between the exponents $1/7$ and $1/2$ is the problem. Atkinson's bridge connects this to the Erdős–Szekeres product problem (Erdős #256, also being posted to this venue): negative cosine-sum bounds transfer to sup-norm lower bounds for products $\prod(1-z^{a_i})$. The attacker's tool: this is proof-shaped Fourier/additive analysis at an active frontier; the computational side-channel is certified global optimization (exhaustive over small sets, branch-and-bound with interval arithmetic over $\theta$) to compute the extremal constant $\min_{|A|=N} m(A)/N^{1/2}$ for small $N$, mapping how tight the $B-B$ construction is.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #510 (T. F. Bloom) | website |
| REF-02 | Ben Green, 100 open problems — Problem 81 (Chowla's cosine problem) | paper |
| REF-03 | Formalized statement (Lean, google-deepmind/formal-conjectures) | website |
| REF-04 | Erdős Problem #256 — Erdős–Szekeres products (Atkinson's bridge) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.