ERDŐS/DAILY ▸

← back to the ledger

ERDőS #510 · PARTIAL

Erdős problem 510 — wave w042

Date of live check and computation: 2026-07-31 (UTC)

Outcome

The full \(\sqrt N\) conjecture is not proved here. The concrete outputs are:

  1. an elementary root-of-unity lemma proving the conjectured \(\sqrt N\) lower bound (with constant \(1\)) whenever \(A\) occupies at most \(\log _2(\sqrt N+1)\) distinct \(2\)-adic valuation levels;
  2. an elementary fourth-moment reduction proving the conjecture for signed spectra of energy \(O(N^2)\);
  3. an exact exhaustive computation for every \(4\)-, \(5\)-, and \(6\)-element subset of \(\{1,\ldots,24\}\), with rational point certificates for every lower bound and rational Sturm certificates for the upper witnesses.

The exact checker is erdos510_wavew042_verify.py.

I use the requested labels:

0. Mandatory live-page check

The page was fetched through the Bright Data browser path, first at https://www.erdosproblems.com/510 and then at its full discussion thread. The browser was allowed to render the page before document.body.innerText was extracted.

Verbatim current statement

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}? > \]

Collision/status audit

the exponent to \(1/5\), with a new arXiv version imminent.

\(1/7\) result. The 2026 comment is now borne out by arXiv v3, so it is a completed partial-result update, not a claimed proof of the \(1/2\) conjecture. The explicit current-worker marker remains None.

Thus the task's stop condition was not triggered.

Literal wording caveat

(a) Read as a statement for every finite \(A\subset\mathbb Z\), with no “sufficiently large \(N\)” convention, the displayed wording has finite degeneracies:

\[ A=\{0\}\implies f_A(\theta)\equiv1,\qquad A=\{0,m\}\implies\min_\theta f_A(\theta)=0. \]

I do not call the intended problem falsified on this basis. The page's linked Lean formalisation uses \(A\subset\mathbb N\), excludes \(0\), and quantifies over all sufficiently large \(N\). The current primary papers likewise formulate the standard problem for distinct positive integers. I therefore:

including both signs;

positive-integer normalisation;

asymptotic question.

1. Verified literature state

Results stated on the live page

The page identifies this as Chowla's cosine problem and lists:

\(\exp(O(\sqrt{\log N}))\)-scale negative value;

would be optimal;

Primary-source audit and the actual current frontier

  1. (b) Benjamin Bedert,

Polynomial bounds for the Chowla Cosine Problem, arXiv:2509.05260v3. ArXiv records v3 on 2026-07-24. Theorem 1.1 states \[ K(N):=\inf_{|A|=N}\left(-\min_x\sum_{a\in A}\cos(ax)\right) \gg N^{1/5-o(1)}. \] This verifies the newest page comment and supersedes the \(1/7\) text in the page body.

  1. (b) Zhihan Jin, Aleksa Milojević, István Tomon, and Shengtong Zhang,

From small eigenvalues to large cuts, and Chowla's cosine problem, arXiv:2509.03490v2. ArXiv records v2 on 2025-10-27; its abstract gives \(K(N)\gg N^{1/10-o(1)}\).

  1. (b) Imre Z. Ruzsa,

Negative values of cosine sums, Acta Arith. 111 (2004), 179–186, DOI 10.4064/aa111-2-6. The official PDF exists and treats finite sets of positive integers. Its Section 4 derives \[ K\ge \exp\!\left(\frac{\log 2}{2}\frac{\log N}{4\log K+c_6}-2\right), \] which rearranges to the familiar \(K\ge \exp(c\sqrt{\log N})\) scale. The PDF's introductory display (1.2) visibly prints a minus sign in the exponential; that sign is inconsistent with the Section 4 derivation and with later primary-source summaries. I use the derivation, not that apparently mistyped display.

  1. (b) Jean Bourgain,

Sur le minimum d'une somme de cosinus, Acta Arith. 45 (1986), 381–389, was verified to exist with the page range and DOI claimed on the live page.

  1. (b) Idris Mercer,

On a function related to Chowla's cosine problem, arXiv:1206.5012, proves the global small cases \[ K(2)=\frac98,\qquad K(3)=\frac{17+7\sqrt7}{27}=1.315565\ldots. \] Mercer reports the still-unproved candidates \[ \begin{array}{c|c|c} N&\text{suspected }K(N)&\text{candidate}\\ \hline 4&1.519558\ldots&\{1,2,3,4\}\\ 5&1.627461\ldots&\{1,2,4,5,6\}\\ 6&1.591832\ldots&\{1,2,4,6,7,8\}, \end{array} \] obtained by considering maximum frequency at most \(20\). His later primary paper Finite Searches, Chowla's Cosine Problem, and Large Newman Polynomials, Integers 19 (2019), A4 reiterates that reducing \(K(4),K(5),K(6)\) to a finite search remains unknown.

  1. Targeted exact-title, exact-phrase, arXiv-ID, and 2026 searches found no

primary source later than Bedert v3 improving \(1/5-o(1)\), and no proof of the \(1/2\) conjecture. This is a reported search miss, not a claim that no unindexed manuscript can exist.

Therefore the best result located as of the run date is Bedert's \(N^{1/5-o(1)}\), while the live problem remains open.

2. Elementary progress I: a dyadic-valuation regime

Theorem

(a) Let \(A\subset\mathbb Z\setminus\{0\}\) be finite and nonempty, let \(N=|A|\), and put

\[ r(A)=\left|\{v_2(|a|):a\in A\}\right|. \]

Then some \(\theta\) satisfies

\[ \boxed{\quad \sum_{a\in A}\cos(a\theta)\le -\frac{N}{2^{r(A)}-1}. \quad} \tag{2.1} \]

In particular, if

\[ r(A)\le \log_2(\sqrt N+1), \]

then

\[ \min_\theta\sum_{a\in A}\cos(a\theta)\le-\sqrt N. \]

This proves the conjectured order, with room for any strict constant \(c<1\), throughout this concrete regime.

If \(0\in A\) and \(A\ne\{0\}\), applying (2.1) to \(A\setminus\{0\}\) gives instead

\[ \min_\theta f_A(\theta) \le 1-\frac{N-1}{2^{r(A\setminus\{0\})}-1}. \tag{2.2} \]

Proof

For \(k\ge0\), define

\[ a_k=\#\{a\in A:v_2(|a|)=k\},\qquad T_{>k}=\sum_{j>k}a_j, \]

and let

\[ \Theta_k= \left\{\frac{(2j+1)\pi}{2^k}:0\le j<2^k\right\}. \]

For any nonzero integer \(a\), geometric-series orthogonality gives

\[ \frac1{2^k}\sum_{\theta\in\Theta_k}e^{ia\theta} = \begin{cases} 0,&2^k\nmid a,\\ (-1)^{a/2^k},&2^k\mid a. \end{cases} \]

Taking real parts and summing over \(A\),

\[ \frac1{2^k}\sum_{\theta\in\Theta_k}f_A(\theta) =T_{>k}-a_k. \]

Consequently

\[ -\min_\theta f_A(\theta) \ge D:=\max_k(a_k-T_{>k}). \tag{2.3} \]

List the \(r=r(A)\) nonempty valuation levels increasingly, and call their sizes \(b_1,\ldots,b_r\). Set

\[ R_i=b_i+\cdots+b_r,\qquad R_{r+1}=0. \]

By the definition of \(D\),

\[ b_i-R_{i+1}\le D, \quad\text{so}\quad R_i\le2R_{i+1}+D. \]

Backward induction gives

\[ N=R_1\le(2^r-1)D. \]

Combining this with (2.3) proves (2.1). A zero frequency contributes the constant \(1\), proving (2.2). \(\square\)

What this reduction says

(a) Any sequence of nonzero sets that could violate a uniform \(c\sqrt N\) bound must eventually occupy more than \(\tfrac12\log_2N+O(1)\) distinct \(2\)-adic valuation levels. This is a necessary structural condition, not a solution for sets with many levels. I did not find this exact lemma in the targeted sources, but make no publication-level novelty claim.

3. Elementary progress II: an additive-energy reduction

For this section use the standard positive-integer formulation \(A\subset\mathbb Z_{>0}\), \(|A|=N\), and put

\[ f_A(\theta)=\sum_{a\in A}\cos(a\theta),\qquad K(A)=-\min_\theta f_A(\theta). \]

Let

\[ S=A\cup(-A) \]

and define its ordered additive energy by

\[ E(S)= \#\{(s_1,s_2,s_3,s_4)\in S^4:s_1+s_2=s_3+s_4\}. \]

Lemma

(a)

\[ \boxed{\quad K(A)\ge\frac{N^{3/2}}{\sqrt{2E(S)}}. \quad} \tag{3.1} \]

Hence, whenever \(E(S)\le C N^2\),

\[ K(A)\ge\frac1{\sqrt{2C}}\sqrt N. \tag{3.2} \]

Proof

All integrals below use normalized measure \(d\theta/(2\pi)\). Since \(\int f_A=0\), writing \(f_A^-= \max(-f_A,0)\) gives

\[ \|f_A\|_1=2\int f_A^-\le2K(A). \tag{3.3} \]

Hölder interpolation gives

\[ \int |f_A|^2 \le \left(\int|f_A|\right)^{2/3} \left(\int|f_A|^4\right)^{1/3}, \]

and therefore

\[ \|f_A\|_1 \ge \frac{\left(\int f_A^2\right)^{3/2}} {\left(\int f_A^4\right)^{1/2}}. \tag{3.4} \]

Now

\[ f_A(\theta)=\frac12\sum_{s\in S}e^{is\theta}. \]

Orthogonality gives, exactly,

\[ \int f_A^2=\frac N2,\qquad \int f_A^4=\frac{E(S)}{16}. \tag{3.5} \]

Substitution of (3.5) into (3.4), followed by (3.3), yields (3.1).

\(\square\)

What this reduction says

(a) If \(K(A)=o(\sqrt N)\) along a putative counterexample sequence, then necessarily

\[ \frac{E(A\cup-A)}{N^2}\longrightarrow\infty. \tag{3.6} \]

Thus the low-energy case is completely resolved. This is a standard moment-type reduction, included because it precisely identifies another regime that cannot contain a counterexample; no novelty claim is made.

Combining Sections 2 and 3, a genuinely hard family must simultaneously have many \(2\)-adic levels and superquadratic signed additive energy. That is a clean necessary-condition reduction, but it does not cover all sets.

4. Exact finite computation through frequency 24

Define the finite extremal quantity

\[ \Lambda_M(n):= \min_{\substack{A\subset\{1,\ldots,M\}\\|A|=n}} \left(-\min_\theta\sum_{a\in A}\cos(a\theta)\right). \tag{4.1} \]

Certified table

(d) The standalone checker proves:

\[ \begin{array}{c|r|c|c} n&\#\text{ sets checked}&\text{exact certified bracket for }\Lambda_{24}(n) &\text{upper witness}\\ \hline 4&10\,626&1.519557\le\Lambda_{24}(4)<1.519558& \{1,2,3,4\}\\ 5&42\,504&1.627460\le\Lambda_{24}(5)<1.627461& \{1,2,4,5,6\}\\ 6&134\,596&1.591832\le\Lambda_{24}(6)<1.591833& \{1,2,4,6,7,8\}. \end{array} \tag{4.2} \]

This rigorously extends Mercer's reported exploratory cutoff from maximum frequency \(20\) to \(24\), and it makes the bounded computation exact. It does not prove the global conjectured values \(K(4),K(5),K(6)\): there is no theorem reducing arbitrary frequencies to \(M\le24\).

Why the computation is exact

Put \(x=\cos\theta\). Then

\[ \sum_{a\in A}\cos(a\theta)=P_A(x):=\sum_{a\in A}T_a(x), \qquad -1\le x\le1, \tag{4.3} \]

where \(T_a\) is the Chebyshev polynomial with integer coefficients.

For each of the \(187\,726\) sets:

  1. floating-point Chebyshev roots are used only to locate a promising

critical point;

  1. that point is rounded to \(p/q\), \(q\le10^9\);
  2. the checker evaluates \(q^{\deg P_A}P_A(p/q)\) with integers and accepts

the set only if the desired lower inequality is exact.

Thus floating point can cause a failed search, but cannot cause a false certificate.

For the other direction, the witness polynomials are

\[ \begin{aligned} P_4(x)&=8x^4+4x^3-6x^2-2x,\\ P_5(x)&=32x^6+16x^5-40x^4-20x^3+12x^2+6x-1,\\ P_6(x)&=128x^8+64x^7-224x^6-112x^5+120x^4+56x^3-20x^2-6x. \end{aligned} \]

For each rational upper endpoint \(U\) in (4.2), the checker constructs the Sturm sequence of \(P_n+U\) over \(\mathbb Q\), proves it has zero roots in \((-1,1)\), and checks positivity at \(-1,0,1\). Hence \(P_n(x)+U>0\) throughout \([-1,1]\), which is the strict upper certificate.

Reproduction

Smoke test:

python runs/erdos510_wavew042_verify.py --smoke

Full exact run:

/usr/bin/time -f 'elapsed=%e cpu=%U maxrss_kb=%M' \
  python runs/erdos510_wavew042_verify.py

Observed full output:

numpy=2.4.4
elementary checks: PASS (moment identities and 31179 valuation histograms)
n=4: PASS; checked 10626 sets; 1.519557 <= Lambda_24(4) < 1.519558; upper witness=(1, 2, 3, 4); 8.49s
n=5: PASS; checked 42504 sets; 1.627460 <= Lambda_24(5) < 1.627461; upper witness=(1, 2, 4, 5, 6); 62.36s
n=6: PASS; checked 134596 sets; 1.591832 <= Lambda_24(6) < 1.591833; upper witness=(1, 2, 4, 6, 7, 8); 196.24s
bounded search: PASS (187726 sets, checksum=337635717)
ALL EXACT CHECKS PASSED
elapsed=267.59 cpu=129.35 maxrss_kb=32404

Checker SHA-256:

24e502c62846163270021b6b3f3e172ba3409d209cae2d2615c206de7148d31b

The script also independently checks the fourth-moment counting identity on explicit sets and exhausts \(31\,179\) valuation histograms as a regression test for the numerical inequality in Section 2. Those tests are sanity checks; the proofs in Sections 2 and 3 do not depend on finite exhaustion.

5. Exact analytic wall

The current \(1/5\) bottleneck

(b) In Bedert v3's symmetric-frequency normalisation, let

\[ K=-\min\widehat{1_A},\qquad B_t=(A\cap(A+t))\setminus(A-t). \]

Proposition 7.3 proves

\[ |B_t|\ll K^4, \tag{5.1} \]

while Lemma 7.4 produces a nonzero \(t\) with

\[ |B_t|\gg\frac{N}{K(\log N)^4}. \tag{5.2} \]

Combining them gives

\[ K^5\gg \frac{N}{(\log N)^4}, \]

which is the \(N^{1/5-o(1)}\) result.

Within this exact proof architecture, a sufficient missing lemma for the \(1/2\) exponent would be an improvement of (5.1) from \(K^4\) to roughly

\[ |B_t|\ll K^{1+o(1)}, \tag{5.3} \]

together with control of the logarithmic loss in (5.2). More generally, an upper bound \(K^\alpha\) paired with (5.2) yields only exponent \(1/(\alpha+1)\). Thus the present \(\alpha=4\) cannot reach \(1/2\). I have not proved (5.3), and it may require a different invariant or an entirely different method. This is the precise missing analytic step, not a hand-waved claim that “better estimates” are needed.

Why a larger finite search does not close anything

Mercer's global \(n=4,5,6\) question already lacks a finite-reduction theorem. Extending \(M\) only checks a larger box. With the present exact algorithm, extrapolating its measured per-case cost and the roughly cubic degree cost of root location gives:

These are engineering estimates, not theorem costs, and neither run would supply the missing uniformity step. They were not attempted.

Honest terminal state

and for \(O(N^2)\)-energy signed spectra.

\(K(N)\gg N^{1/5-o(1)}\).

globally, but this computation does not promote them to theorems.

many-\(2\)-adic-level regime was found.

PARTIAL: Proved the sharp-order bound for low 2-adic-level and quadratic-energy regimes and exactly certified all 4–6 term spectra through frequency 24; the general \(N^{1/2}\) conjecture remains open, with Bedert’s \(N^{1/5-o(1)}\) the verified frontier.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger