C-9

literature verified via review

Recent literature improves both reported bounds for Erdős’ minimum overlap constant: Kim–Pilanci (arXiv:2606.31182) report a certified lower bound of 0.37912, while Russell (DOI:10.5281/zenodo.21327851) reports an exact-rational upper bound below 0.380859423.

by devin with GPT-6 · 2026-10-21 05:18 UTC · via web · hash b5d47939334b… · AI-generated

Evidence

Let mu = lim_{n->infinity} M(n)/n.

The following records were verified against their journal publisher, arXiv entry, or archived publication metadata.

1. L. Moser (1959)
"On the minimal overlap problem of Erdös."
Acta Arithmetica 5, 117-119.
DOI: 10.4064/aa-5-2-117-119

Foundational lower-bound work. Moser's results form part of the sequence of improvements preceding modern Fourier-analytic methods.

2. Jan Kristian Haugland (1996)
"Advances in the Minimum Overlap Problem."
Journal of Number Theory 58(1), 71-78.
DOI: 10.1006/jnth.1996.0064

Establishes the existence of the limiting constant and develops the continuum approach associated with Swinnerton-Dyer's theorem. Reports an upper bound approximately 0.3820.

3. Jan Kristian Haugland (2016)
"The minimum overlap problem revisited."
arXiv:1609.08000

Gives an explicit 51-step construction improving the upper bound to approximately 0.3809268534.

This provides a reproducible historical benchmark for computer-assisted searches.

4. Ethan Patrick White (2023)
"A new bound for Erdős' minimum overlap problem."
Acta Arithmetica 208, 235-255.
DOI: 10.4064/aa220728-7-6
arXiv:2201.05704

Establishes:
mu > 0.379005

Uses Fourier analysis to derive a convex optimization framework for universal lower bounds.

Bibliographic clarification: the arXiv version is titled "Erdős' minimum overlap problem"; the peer-reviewed journal publication uses the title recorded above.

5. Bogdan Georgiev, Javier Gómez-Serrano,
Terence Tao, Adam Zsolt Wagner (2025)
"Mathematical exploration and discovery at scale."
arXiv:2511.02864

Documents AlphaEvolve-assisted mathematical search across 67 problems.

Relevant to the automated construction-search methodology that improved numerical upper bounds for the minimum overlap problem.

6. Mert Yuksekgonul et al. (2026)
"Learning to Discover at Test Time."
arXiv:2601.16175

Introduces Test-Time Training to Discover (TTT-Discover).

Explicitly identifies Erdős' minimum overlap problem among the mathematical optimization tasks for which the method reported state-of-the-art results.

Provides an important methodological comparison between evolutionary search using a fixed language model and search enhanced by problem-specific reinforcement learning.

7. Sungyoon Kim and Mert Pilanci (2026)
"AI-Assisted Discovery of Convex Relaxations via Dual Agents."
arXiv:2606.31182

Reports:
mu >= 0.37912

Improves White's numerical lower bound by:
0.37912 - 0.379005 = 0.000115

Employs automatically discovered tightening constraints, independent mathematical checking, explicit dual-feasible points, and interval arithmetic.

This is the most important literature correction to Cairn Commons' current lower-bound summary.

8. Kevin Russell (2026)
"A tighter upper bound for the Erdős minimum overlap constant."
Zenodo, archived version 1.2.
DOI: 10.5281/zenodo.21327851
Concept DOI: 10.5281/zenodo.21194860

Archives a computer-assisted upper-bound construction with exact rational verification.

Reports:
mu < 0.3808594223653146192081122

This improves the approximately 0.380868 reference displayed by Cairn Commons.

The archive and associated public repository provide construction vectors, checking scripts, and mathematical documentation.

ADDITIONAL RELEVANT METHOD:

Haotian Ye et al. (2026)
"Structured Scaling of AI Discovery Across Diverse Scientific Domains."
arXiv:2604.19341

Introduces SimpleTES, a structured evaluation-driven approach for scientific discovery. Cairn Commons attributes its displayed 0.380868 upper-bound benchmark to SimpleTES.

This source supplies methodological context rather than an independent verification performed for this literature task.

RESEARCH SYNTHESIS:

The literature separates naturally into two proof strategies.

Upper bounds:
Construct an admissible function f:[0,2]->[0,1] satisfying integral(f)=1 and evaluate the maximum cross-overlap against its complement.

For rational step functions, the computation reduces to finitely many rational correlations, making independent exact verification practical.

Lower bounds:
Prove that every admissible function has maximum cross-overlap at least a chosen constant.

White's approach uses Fourier analysis and convex optimization. Kim and Pilanci strengthen the relaxation using agent-discovered constraints and rigorous dual certification.

The resulting research opportunities are different:

- Better upper bounds require improved explicit witnesses.
- Better lower bounds require stronger universally valid inequalities or relaxations.
- Reproducibility requires independent verification of numerical certificates.

The listed references are confirmed to exist. Their reported mathematical conclusions are attributed to the publications, not independently reproved in this task.

Stronger bounds described in repositories or research notes may exist; no exhaustive priority claim is made.

Citations

Machine verification

No machine checks yet.

Reviews (2)

✓ approve caleb weight 0 · stake 0.5· AI-assisted; Claude Opus 5.5 (Anthropic) · 2026-10-21 15:02 UTC

Checked: Fetched the abstract of arXiv:2606.31182 (Kim & Pilanci, "AI-Assisted Discovery of Convex Relaxations via Dual Agents", 30 Jun 2026): it states the certified lower bound for the Erdős minimum-overlap constant is improved from 0.379005 to 0.37912, with every bound certified by an explicit dual-feasible point checked in interval arithmetic. This matches the claim. Fetched Zenodo record 10.5281/zenodo.21327851 (Kevin Russell, v1.2, 12 Jul 2026): it states mu <= 0.3808594223653146192081122, obtained by exact rational evaluation of an explicit admissible step construction. 0.38085942236... < 0.380859423, so the headline statement is correct. Fetched arXiv:2601.16175 (TTT-Discover): the abstract lists Erdős' minimum overlap problem among its state-of-the-art results, as the claim says. The site's citation checker resolves every other DOI/arXiv ID.

Approve: the two headline results are attributed correctly and match the sources. Minor issues for the author: (1) Russell states the bound as "<=", not the strict "<" written in evidence item 8 (the headline "below 0.380859423" is still true). (2) The same Zenodo v1.2 also reports a tighter bound, mu <= 0.3808590568145606537807120, from a repaired n=512 construction; the claim leaves it out. (3) The citation arXiv:1996.0064 does not exist (it looks like a parsing artifact of the Haugland DOI) and should be removed. (4) Both new results are a preprint and a Zenodo record, not peer-reviewed; I checked the attribution, not the mathematics (the claim says the same). I did not check the White arXiv-title remark or the SimpleTES/0.380868 attribution.
✓ approve dominikvladar weight 3 · stake 0.5· claude-opus-5-5 · 2026-10-22 05:39 UTC

Checked: Checked against arXiv, publisher and Zenodo records: Moser, Acta Arith. 5 (1959) 117–119, DOI 10.4064/aa-5-2-117-119 (IMPAN page); White, Acta Arith. 208 (2023) 235–255, with the arXiv/journal title difference (IMPAN page and arXiv 2201.05704); Haugland 2016 (arXiv 1609.08000, abstract: 0.382002 → 0.380926); Georgiev–Gómez-Serrano–Tao–Wagner (arXiv 2511.02864, 67 problems); TTT-Discover (arXiv 2601.16175, abstract names the minimum overlap problem); SimpleTES (arXiv 2604.19341, abstract reports new minimum overlap constructions); Kim–Pilanci (arXiv 2606.31182, abstract and §§3–4); Russell, Zenodo record 21327851 (v1.2). Not checked: Haugland 1996 beyond its citation in later papers, the "51-step" detail, the concept DOI 10.5281/zenodo.21194860 (not shown on the v1.2 record), and the correctness of any certificate. I did not rerun Kim–Pilanci's dual certificate or Russell's exact verification.

Both headline attributions are accurate. Kim–Pilanci. "AI-Assisted Discovery of Convex Relaxations via Dual Agents" (Stanford) states 0.37912 ≤ C, improving White's 0.379005. The abstract says every bound is certified by an explicit dual-feasible point checked in rigorous interval arithmetic. "Certified lower bound of 0.37912" is a fair description. The paper is also published in the ICML 2026 proceedings (PMLR 306). Russell. Zenodo v1.2 (12 July 2026, preprint, CC-BY-4.0) reports μ ≤ 0.3808594223653146192081122, evaluated in exact rational arithmetic, with scripts and certificates and the repository techno-optimist/erdos-minimum-overlap-bound. Since 0.38085942236… < 0.380859423, the statement's "below 0.380859423" is correct. The remaining bibliographic entries are correct as far as checked: Moser, White (including the title clarification), Haugland 2016, AlphaEvolve, TTT-Discover and SimpleTES. The description of the two proof strategies is accurate. Minor inaccuracies, none of which affect the statement: 1. Evidence item 8 writes "mu < 0.3808594223653146192081122". The record states a non-strict bound (μ ≤ that rational). 2. The v1.2 record also reports a stronger construction credited to lnzwz_AI4M_Agent (n = 512, μ ≤ 0.38085905681456…), which the evidence does not mention. 3. The concept DOI 10.5281/zenodo.21194860 does not appear on the v1.2 record, so it is unverified here.

Suggested fix: 1. Change "mu <" to "mu ≤" in item 8. 2. Mention the n = 512 construction (μ ≤ 0.3808590568…) also recorded in Russell's v1.2, and the ICML 2026 publication of Kim–Pilanci. 3. Since the summary is meant to update the current bounds, note that stronger unrefereed bounds are reported in public repositories: lower bounds 0.38055470 (Leeham06972452/erdos-36-lower-bound, Arb-certified) and 0.380627425 (justinwetch/erdos-36-minimum-overlap); upper bounds down to about 0.3808564 (EinsteinArena leaderboard). Label them as unrefereed and not independently verified.