Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 7

Problem 36

claims/: The 6 claim pages of Problem 36, one per claimant's result; the problem's standing derives from them.

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

Status. 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, accepted on the refereed publication), the TTT-Discover upper bound (claim page, claimed), Kim and Pilanci's lower bound $0.37912$ of June 2026 (claim page, claimed) and Russell's certified upper bound $0.38085906$ of July 2026 (claim page, 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), 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); 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.

Source. erdosproblems.com/36, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #36, https://www.erdosproblems.com/36.

References.

[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_unsolved_problems_number_theory.
[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_erdos_minimum_overlap_problem.
[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).

Formalization. Statement in formal-conjectures at its revision of 2026-10-06, the one linked, which states the limit as erdos_36 with answer(sorry) and a sorry body and carries no formal_proof attribute; its variants record the published lower and upper bounds and neither claimed bound above.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (31)

White's lower bound 0.379005 for the minimum overlap constant The TTT-Discover upper bound 0.380876 for the minimum overlap constant Kim and Pilanci's lower bound 0.37912 for the minimum overlap constant Russell's certified upper bound 0.38085906 for the minimum overlap constant Price's lower bound 0.38055470 for the minimum overlap constant Drynshock's lower bound 0.3805634 for the minimum overlap constant problems/additive_combinatorics/E0036/claims Sumsets and Arithmetic Progressions Sumsets and Arithmetic Progressions additive_combinatorics/erdos_1956_problems_results_additive_number_theory Problem (p. 135): the minimum overlap question, a shift with at least n solutions of a_i + x = b_j additive_combinatorics/georgiev_2025_mathematical_exploration_discovery_at_scale Haugland: Advances in the Minimum Overlap Problem Corollary 1 (p. 72): the limit of M(i)/i exists Corollary 2 (p. 72): the term -1 in Moser's estimate can be omitted The Crucial Conjecture (p. 73) and Swinnerton-Dyer's proof (pp. 74-78)Lemma (p. 71, unnumbered): one good partition bounds limsup M(i)/i Theorem (p. 74, unnumbered): lim M(n)/n <= 0.3820029881...additive_combinatorics/haugland_2016_minimum_overlap_problem_revisited 51-step density for the minimum overlap problem (p. 2)Kim–Pilanci: AI-Assisted Discovery of Convex Relaxations via Dual Agents Martos et al.: Minimun overlap problem on finite groups Moser: On the minimal overlap problem of Erdös Russell: A tighter upper bound for the Erdős minimum overlap constant additive_combinatorics/white_2022_erdos_minimum_overlap_problem Ye et al.: Structured Scaling of AI Discovery Across Diverse Scientific Domains Problem O.1 (p. 78): the paper's step-function task for the minimum overlap problem additive_combinatorics/yuksekgonul_2026_learning_discover_test_time number_theory/guy_2004_unsolved_problems_number_theory primes/erdos_1955_remarks_number_theory_hebrew Section 2, p. 47: a shift t with at least n/2 solutions of a_i + t = b_j, and the question whether n is reached

Graph