The minimum overlap problem: pin down Erdős's constant $c$, now trapped in $(0.379005, 0.380876)$ (Erdős #36)
Statement
Find the optimal constant $c>0$ such that the following holds: for all sufficiently large $N$, if $A\sqcup B=\{1,\ldots,2N\}$ is a partition into two equal parts, so that $\lvert A\rvert=\lvert B\rvert=N$, then there is some integer $x$ such that the number of solutions to $a-b=x$ with $a\in A$ and $b\in B$ is at least $cN$.
Acceptance. FULLY RESOLVES: an exact determination of the minimum overlap constant $c$ (closed form or proven equality with a characterized extremal construction), with a complete proof — machine-checkable (Lean/Coq) preferred, otherwise a full written proof. ADVANCES: strictly improve either record stated in the background: (a) a new upper bound, via an explicit construction (a partition family or limiting density function) together with an exact, independently re-runnable computation of its overlap value in rational or rigorously bounded arithmetic; or (b) a new lower bound, via a proof or a rigorous computer-assisted certificate (e.g. an LP/SDP dual certificate with verified numerics). Any claimed record must state the value to enough precision to compare against the bounds in the background and beat the relevant one strictly. Deliver the construction plus verification code, or the proof/certificate file.
Background
The minimum overlap problem, posed by Erdős [Er55, Er56, Er61, Er92c]; listed as open on erdosproblems.com/36 (fetched 2026-07-13, status 'open', tagged 'number theory | additive combinatorics'), and discussed as problem C17 of Guy's collection [Gu04]. Erdős initially conjectured $c=1/2$; the interval example $A=\{N/2+1,\ldots,3N/2\}$ (for even $N$) shows $c\leq 1/2$. The trivial lower bound is $c\geq 1/4$, improved by Scherk to $1-1/\sqrt{2}\approx 0.293$. The current records bracket the constant as $0.379005<c<0.380876$: the lower bound is due to White [Wh22], and the upper bound was found by the TTT-Discover LLM system [YKLBMWKCZGS26], slightly improving constructions from AlphaEvolve [GGTW25] and, before that, Haugland [Ha16]. Notably, the upper-bound record has twice in a row been set by automated/LLM-driven search over constructions, and the remaining gap is under $0.002$. OEIS A393584 is listed by the site as a related sequence. The attacker's tools: the standard continuous relaxation — optimize over limiting density functions (step functions) for $A$, computing the max-correlation objective exactly in rational arithmetic — for new upper-bound constructions; and rigorous LP-duality/analytic arguments or certified numerics for lower bounds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #36 (T. F. Bloom) | website |
| REF-02 | OEIS A393584 — sequence related to the minimum overlap problem (Erdős #36) | website |
| REF-03 | Wikipedia — Minimum overlap problem | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.