Level A · Machine-checkable Combinatorics P-erdos-minimum-overlap

Erdős minimum overlap problem

Improve the numerical upper or lower bounds for the limiting constant in Erdős' minimum overlap problem.

Status (as of 2026-11-08): Open. 0.379005 ≤ lim M(n)/n ≤ 0.3808585504 (lower: White 2022, and a June 2026 preprint by Kim and Pilanci claims a certified 0.37912; upper: an exact step construction by Atris, 2026, independently replayed, after SimpleTES 0.380868 and AlphaEvolve 0.380924).

Current state (tracked automatically)

Best known bounds for constant 1b: 0.379005 ≤ C ≤ 0.3808585504. Upper bound ([A2026], Atris); lower bound ([W2022]).
erdosproblems.com lists Erdős problem #36 as open (status updated 31 August 2025).

All tracked facts and sources

Fact	Value	Source
Status of Erdős problem #36 on erdosproblems.com	open 2025-08-31	erdosproblems.com
Best lower bound with an explicit value (constant 1b)	0.379005 [W2022]	Tao's optimization constants
Best upper bound with an explicit value (constant 1b)	0.3808585504 [A2026] — Atris.	Tao's optimization constants

Read twice a day from public sources by deterministic collectors (no AI; the sentences above are filled-in templates): erdosproblems.com (checked 2026-11-12), Tao's optimization constants (checked 2026-11-12). How it works.

Try it with your chatbot Submit a claim Follow (RSS)

Cite

@misc{cairn-erdos-minimum-overlap,
  title        = {Erdős minimum overlap problem},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/erdos-minimum-overlap}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
}

Also: CITATION.cff · Atom feed of results

Status badge for a README (shields.io):

[![Cairn Commons](https://img.shields.io/endpoint?url=https%3A%2F%2Fcairn-commons.com%2Fbadge%2Fproblem%2Ferdos-minimum-overlap.json)](https://cairn-commons.com/problems/erdos-minimum-overlap)

Claims: 4
Verified: 1
Disputed: 1
Refuted: 0
On the literature board: 0

Work on this problem with your chatbot

Your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.

Get a task — one click
Your chatbot works on it — 5–10 minutes, in its own tab
Paste its answer here — check it and publish it under your name

What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.

or , ,

ChatGPT opens in a new tab and starts on the task right away; Claude opens with it filled in.

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

Split {1, …, 2n} into two sets A and B of size n and let M_k be the number of pairs (a, b) with a − b = k; let M(n) be the minimum over all splits of max_k M_k. The limit of M(n)/n exists, and determining it is a problem of Erdős. Upper bounds come from explicit step functions; lower bounds from analytic arguments.

Progress: an explicit step function (piecewise-constant density) giving a better upper bound, verified with exact rational arithmetic (checker planned; until then reviewed and reproduced); or an improved lower-bound argument (preferably with the numerical part certified).

Known status (October 2026). 0.379005 ≤ lim M(n)/n ≤ 0.380868: the lower bound is White's (2022); the upper bound came from AI-assisted search (AlphaEvolve 0.380924 in 2025, then SimpleTES 0.380868 in 2026), see Tao's optimization-constants page.

Update (8 November 2026). The best recorded upper bound is now 0.3808585504 (Atris, 2026): an explicit step construction with exact rational value 0.38085855031…, refined from an earlier leaderboard construction and independently replayed (Tao's optimization-constants page, constant 1b). On the lower side, Kim and Pilanci (arXiv 2606.31182, June 2026) claim a certified bound of 0.37912 from a dual-feasible certificate checked in interval arithmetic; it is not yet listed on the constants page.

History of the bounds

Year	Result	By
1956	M ≤ 0.4	Motzkin, Ralston, Selfridge
1959	M ≥ 0.356393	Moser
2016	M ≤ 0.380926	Haugland
2022	M ≥ 0.379005	White
2025	M ≤ 0.380924	AlphaEvolve
2026	M ≤ 0.380868	SimpleTES
2026	M ≤ 0.3808585504	Atris (exact step construction)
2026	M ≥ 0.37912 (preprint)	Kim & Pilanci