Problem 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 $x$ such that the number of solutions to $a-b=x$ with $a\in A$ and $b\in B$ is at least $cN$.
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 $x$ such that the number of solutions to $a-b=x$ with $a\in A$ and $b\in B$ is at least $cN$.
Categories:
Number Theory Additive Combinatorics
Progress
The minimum overlap problem. The example (with $N$ even) $A=\{N/2+1,\ldots,3N/2\}$ shows that $c\leq 1/2$ (indeed, Erdős initially conjectured that $c=1/2$). The lower bound of $c\geq 1/4$ is trivial, and Scherk improved this to $1-1/\sqrt{2}=0.29\cdots$. The current records are\[0.379005 < c < 0.380924,\]the lower bound due to White [Wh22] and the upper bound due to AlphaEvolve [GGTW25], improving slightly on an upper bound due to Haugland [Ha16].This is discussed in problem C17 of Guy's collection [Gu04].
Source: erdosproblems.com/36 | Last verified: January 13, 2026