Matching works

1 work

math.NT — Number Theory

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

Contributed by John Tripodo

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.

Primarily AI-generated textHuman understanding: no partsErdős Problem 708Erdős–Surányi functionHall's theoremLean 4divisibility antichainsformal verificationinterval product-cover
Nov 20, 202619 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations