The Erdős minimum overlap problem

Split the numbers $1,\dots,2N$ into two halves $A$ and $B$ and look at all differences $a-b$. Some difference must occur many times; Erdős asked for the best constant $c$ such that one difference always occurs at least $cN$ times. The answer is known to lie between $0.379$ and $0.381$, and both bounds come from optimisation problems that computers can attack.

Problem

For a partition $\{1,\dots,2N\}=A\sqcup B$ with $\lvert A\rvert=\lvert B\rvert=N$, let

$$M(A,B)=\max_{x\in\mathbb{Z}}\ \#\{(a,b)\in A\times B : a-b=x\},$$

and let $M(N)$ be the minimum of $M(A,B)$ over all such partitions. Find the optimal (largest) constant $c$ such that $M(N)\ge cN$ for all sufficiently large $N$.

Background

Erdős posed the problem in the 1950s. Taking $A=\{N/2+1,\dots,3N/2\}$ (for even $N$) shows $c\le 1/2$, and Erdős first conjectured that $1/2$ is the answer; it is not. The trivial lower bound is $1/4$, and Scherk improved it to $1-1/\sqrt2\approx0.293$. Following Swinnerton-Dyer, upper bounds are obtained by exhibiting step functions that describe the density of $A$ along $[1,2N]$, so improving them is a finite-dimensional optimisation problem; lower bounds come from Fourier-analytic arguments that reduce to convex programs. The problem is C17 in Guy's Unsolved Problems in Number Theory.

What is known

• Lower bound. $c>0.379005$ (White, 2023), via elementary Fourier analysis and a convex optimisation program. Two claims listed on the problem's proof-claims page in 2026 raise this to $0.3805547$ (July) and $0.3805634$ (September), each with a certificate; neither has been independently checked.
• Upper bound. Haugland (2016) gave a step function showing $c\le 0.380926\ldots$. Small improvements followed from computer-assisted searches: $0.380924$ (Georgiev, Gómez-Serrano, Tao and Wagner, 2025), $0.380876$ (Yuksekgonul et al., 2026) and $0.380868$ (Ye et al., 2026). A step function with $3584$ steps giving $0.3808586$ was posted on the Einstein Arena leaderboard in August 2026 and re-checked in exact arithmetic by a forum user.

What would count as progress

• A step function (or explicit partition) giving a smaller upper bound, with exact rational arithmetic or interval arithmetic so that the bound can be verified independently.
• A larger lower bound with a complete proof, or a certified solution of a sharper dual program.
• Any structural result about optimal partitions, for example a proof that optimal density functions are step functions with a bounded number of steps.
• A formal proof against the Lean statement in formal-conjectures.

References

1. J. K. Haugland, The minimum overlap problem revisited (2016). arXiv:1609.08000
2. E. P. White, A new bound for Erdős' minimum overlap problem, Acta Arith. 208 (2023), 235–255. doi:10.4064/aa220728-7-6
3. B. Georgiev, J. Gómez-Serrano, T. Tao and A. Z. Wagner, Mathematical exploration and discovery at scale (2025). arXiv:2511.02864
4. M. Yuksekgonul et al., Learning to discover at test time (2026). PDF
5. H. Ye et al., Structured scaling of AI discovery across diverse scientific domains (2026). arXiv:2604.19341
6. Einstein Arena, Erdős minimum overlap leaderboard. einsteinarena.com
7. R. K. Guy, Unsolved Problems in Number Theory, 3rd ed., Springer (2004), problem C17. doi:10.1007/978-0-387-26677-0

Source

Imported from Erdős Problems 36, 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.