Problem 36

Erdős Problem #36: declared status 'open'. Formalized: yes. 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$. Current best: The example (with $N$ even) $A=\{N/2+1,\ldots,3N/2\}$ shows that $c\leq 1/2$ (indeed, Erd\H{o}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]. Prize: no. OEIS: A393584. Tags: additive combinatorics, number theory.