Sharp finite cases of the Erdős–Surányi interval-product problem: g(4) = 5 and g(5) = 6
Version 1 / Nov 20, 2026 / CC BY 4.0
Abstract
Let be the Erdős–Surányi function of Erdős Problem #708: the least such that, for every set of distinct integers at least and every interval of consecutive integers, some set of at most elements of has product divisible by . We prove and . The lower bound for is due to Erdős and Surányi (1959). Our contribution is the matching universal upper bounds and ; to our knowledge these are the first exact values beyond . The four-modulus proof combines a Hall-matching reduction with gcd/lcm collision repair and an anchored proper-divisor lemma. The five-modulus proof classifies a maximal antichain-admissible assignment of the moduli to interval multiples by its occupancy shape; the hardest shapes are a squarefree four-prime exception and a configuration controlled by a propagation invariant. Both values, in the exact-cardinality reading of the original problem and in the at-most reading used by later work, are machine-checked in Lean 4. The formalization is registered in the Palomar registry as PALOMAR-2026-11-19-000019. The general question whether remains open.
Provenance statement
Formalizations
Tools used
- Lean
- LeanVersion Lean 4 v4.35.0-rc2 with Mathlib
- OpenAI
- ChatGPT
- Anthropic
- Claude Opus
- OpenAI
- Codex
References
- T. F. Bloom, Erdős Problem #708 , Erdős Problems, accessed 19 November 2026. https://www.erdosproblems.com/708.link
- H. Chen, Explicit upper bounds for the Erdős--Surányi function , Zenodo, version 14, 8 September 2026, https://doi.org/10.5281/zenodo.22267395; source code https://github.com/chy4pro/erdos-708-explicit-upper-bounds.DOI
- P. Erdős, Some of my forgotten problems in number theory , Hardy--Ramanujan Journal 15 (1992), 34--50. https://hrj.episciences.org/125/pdf.link
- P. Erdős and J. Surányi, Megjegyzések egy versenyfeladathoz (Bemerkungen zu einer Aufgabe eines mathematischen Wettbewerbs), Matematikai Lapok 10 (1959), 39--48. https://users.renyi.hu/~p_erdos/1959-07.pdf.link
- P. Hall, On representatives of subsets , J. London Math. Soc. 10 (1935), 26--30.
- J. Marchetto, feat(ErdosProblems): 708 , Google DeepMind Formal Conjectures, pull request #4388, open as of 19 November 2026. https://github.com/google-deepmind/formal-conjectures/pull/4388.link
- The mathlib Community, The Lean mathematical library , in: Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), ACM, 2020, 367--381.
- L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language , in: Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci. 12699 , Springer, 2021, 625--635.
- Palomar registry, entry , version 1, Erdős Problem 708 for four and five moduli: and , registered 19 November 2026. https://palomar-registry.org/entry?id=PALOMAR-2026-11-19-000019&version=1; verification run https://github.com/PalomarRegistry/PalomarSubmission/actions/runs/44442073024.link
- P. White (with Claude, Anthropic), Erdős #708: Haoyu Chen's checks out and replays here , Erdős Problem a Day, entry dated 12 November 2026, read 19 November 2026; its referee checks were performed by AI instances, not human referees. https://www.erdosproblemaday.com/day/708-chen-12n-refereed-and-a-k2t-window-at-every-size.link
Version history
- v1 · 19 pagesSubmitted by John TripodoFirst version. The lower bounds are due to Erdős and Surányi (1959); the contribution is the matching upper bounds. Both values are formalized in Lean 4 and registered in the Palomar registry as PALOMAR-2026-11-19-000019. The written arguments have had AI-assisted review only, not human refereeing. The general conjecture remains open.CurrentNov 20, 2026