Problem 36

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$ .

Source: erdosproblems.com/36

Number theory
Additive combinatorics

Wiki page

Status

Open

No claim settles this problem.

Open, the site's label (OPEN; page last edited 23 January 2026). The site's commentary gives the records $0.379005<c<0.380876$ , the lower bound due to White [Wh22] and the upper bound to the TTT-Discover LLM [YKLBMWKCZGS26], improving on AlphaEvolve [GGTW25] and Haugland [Ha16]. The record bounds and the later bounds with library cards have partial claim pages: White's refereed lower bound (claim page (White, 2022), accepted on the refereed publication), the TTT-Discover upper bound (claim page (Yuksekgonul Et Al, 2026), claimed), Kim and Pilanci's lower bound $0.37912$ of June 2026 (claim page (Kim and Pilanci, 2026), claimed) and Russell's certified upper bound $0.38085906$ of July 2026 (claim page (Russell, 2026), claimed). The site's proof-claims tab carries two partial proof claims, each raising the lower bound for the constant: one submitted by Liam Price on 2026-07-20 and credited to GPT Pro, claiming $c\ge0.38055470$ (claim page (Price, 2026)), and one submitted by the forum user Drynshock on 2026-09-19 and credited to GPT 6 Pro, claiming $c>0.3805634$ through a subadditivity inequality for the overlap function added to the convex relaxation (claim page (Drynshock, 2026)); neither claim had comments on its thread as of 2026-10-06, and this page records them without adopting them. The superseded bounds, the trivial $1/4$ , Scherk's $1-1/\sqrt2$ , Moser's $\sqrt{4-\sqrt{15}}\approx0.3564$ , Haugland's upper bounds of 1996 and 2016 and AlphaEvolve's $0.380924$ , are history recorded in the references and get no claim page.

GGTW25: B. Georgiev, J. Gómez-Serrano, T. Tao, and A. Wagner, Mathematical exploration and discovery at scale. arXiv:2511.02864 (2025).
Gu04: Guy, Richard K., Unsolved problems in number theory. 3rd ed., Problem Books in Mathematics, Springer, New York (2004), xviii+437 pp. Section C17 "The minimum overlap problem", printed p. 199: the definition of $M$ as $\min\max_kM_k$ over the partitions of $\{1,\ldots,2n\}$ , Erdős's $M>n/4$ with the improvements of Scherk, Świerczkowski and Leo Moser, the Motzkin--Ralston--Selfridge examples with $M<2n/5$ "contrary to Erdős's conjecture that $M=\frac12n$ ", the question "Is there a number $c$ such that $M\sim cn$ ?", the table of $M(n)$ for $n\le15$ , and Haugland's $\lim M(n)/n\le0.38200298812318988\ldots$ . Library home: Guy 2004.
Ha16: Haugland, J. K., The minimum overlap problem revisited. arXiv:1609.08000 (2016).
Wh22: White, E. P., Erdős' minimum overlap problem. arXiv:2201.05704 (2022). Published as A new bound for Erdős' minimum overlap problem, Acta Arith. 208 (2023), no. 3, 235-255, doi:10.4064/aa220728-7-6. Library home: White 2022.
YKLBMWKCZGS26: M. Yuksekgonul, D. Koceja, X. Li, F. Bianchi, J. McCaleb, X. Wang, J. Kautz, Y. Choi, J. Zou, C. Guestrin, and Y. Sun, Learning to Discover at Test Time. https://test-time-training.github.io/discover.pdf (2026).

Problem 36

Status

Proof claims

Discussion