OPEN
This is open, and cannot be resolved with a finite computation.
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$.
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].
View the LaTeX source
This page was last edited 12 January 2026.
Additional thanks to: Terence Tao
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #36, https://www.erdosproblems.com/36, accessed 2026-01-14
