Lower bound for Erdős's minimum overlap constant
Erdős problem #36 · erdosproblems.com/36
Erdős's minimum overlap problem (1955): split into two sets of size , and let be the minimum, over all such splits, of the maximum over of the number of solutions of with , . Determine the constant . Before this result the best bounds were (White 2022) and (SimpleTES 2026, literature).
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI co-developed
- Method
- Computation
- Field
- Additive combinatorics
- Posed by
- Paul Erdős (1955); Erdős Problem #36
- Year posed
- 1955
- Years open
- 71y
- Solved
- 2026-06-29
- Model
- GPT Pro (version not stated)
- Vendor
- OpenAI
- Collaborators
- Liam Price
- Verification
- Site-confirmed
- Publication
- Announced
- Significance
- 15 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
A rigorous lower bound , improving White's (2022). The problem stays open: the best public upper bound is (Einstein Arena, August 2026; in the literature, SimpleTES), so is now known to within about . The bound rests on a finite certificate checked in ball arithmetic plus a step-function transfer from the continuous to the finite problem. The later Station paper (arXiv 2608.23691) reaches , below this; a higher claim of posted to the tracker on 19 September is unchecked.
What the AI did
The author, Liam Price, states on the erdosproblems.com thread for problem 36 that GPT Pro produced the improvement ("GPT Pro improves the lower bound to 0.38055470", 29 June 2026), and the tracker's proof-claim record lists the claim as made "using GPT Pro". The repository itself carries no disclosure. The division of labour is not described beyond that sentence.
Verification
Re-run by this site on 4 October 2026: the repository's run_arb_verification_chunks.sh at commit 6bc610e, Python 3.14.0 and python-flint 0.9.0. All three chunks reported success, proved_all_bins true over 172 mean bins, worst margin about 1.9e-8, certified lower bound 0.3805547027625940..., matching the shipped report to about thirty digits. The check is rigorous: Arb ball arithmetic at 160 bits on decimal-string inputs, with floating point used only to choose interval splits. Not machine-checked: the proof note's step-function transfer from the continuous to the finite problem, which was not audited here. erdosproblems.com still lists White's 0.379005 as the lower bound.
Sources
Submitted by CobaltJackal234 on