Sharp finite cases of the Erdős–Surányi interval-product problem: g(4) = 5 and g(5) = 6

Primarily AI-generated textHuman understanding: no partsmath.NT — Number Theorymath.CO — Combinatorics

Contributed by John Tripodo ↗

Version 1 / Nov 20, 2026 / CC BY 4.0

Abstract

Let g(n)g(n) be the Erdős–Surányi function of Erdős Problem #708: the least kk such that, for every set AA of nn distinct integers at least 22 and every interval II of max⁡A\max A consecutive integers, some set of at most kk elements of II has product divisible by ∏a∈Aa\prod_{a\in A} a. We prove g(4)=5g(4)=5 and g(5)=6g(5)=6. The lower bound g(n)≥n+1g(n)\ge n+1 for n≥3n\ge 3 is due to Erdős and Surányi (1959). Our contribution is the matching universal upper bounds g(4)≤5g(4)\le 5 and g(5)≤6g(5)\le 6; to our knowledge these are the first exact values beyond g(3)=4g(3)=4. 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 (4,1)(4,1) 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 g(n)≤2ng(n)\le 2n remains open.

Author comments: First 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.

Provenance statement

Most of the prose, the development of the proofs, the Lean 4 formalization and the testing were produced or revised with OpenAI ChatGPT/Codex and Anthropic Claude, under the direction of John Tripodo, who chose the problem and scope and is the sole human contributor. The author does not claim personal understanding or line-by-line verification of the mathematical arguments. The evidence for correctness is the machine-checked Lean formalization of the stated theorems (Palomar registry entry PALOMAR-2026-11-19-000019, source https://github.com/jjtripodo-lgtm/erdos-708-g4-g5 at commit 00fbb23c3084daa88ea420aa9c74177127d5283f), together with elementary verifications of the two extremal instances. The written arguments received AI-assisted adversarial review, not human peer review.

Formalizations

Tools used

Lean
LeanVersion Lean 4 v4.35.0-rc2 with Mathlib
OpenAI
ChatGPT
Anthropic
Claude Opus
OpenAI
Codex

References

  1. T. F. Bloom, Erdős Problem #708 , Erdős Problems, accessed 19 November 2026. https://www.erdosproblems.com/708.link
  2. H. Chen, Explicit upper bounds for the Erdős--Surányi function g(n)g(n) , 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
  3. 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
  4. 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
  5. P. Hall, On representatives of subsets , J. London Math. Soc. 10 (1935), 26--30.
  6. 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
  7. 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.
  8. 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.
  9. Palomar registry, entry , version 1, Erdős Problem 708 for four and five moduli: g(4)=5g(4)=5 and g(5)=6g(5)=6 , 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
  10. P. White (with Claude, Anthropic), Erdős #708: Haoyu Chen's g(n)≤12ng(n)\le12n 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

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