Skip to content

Erdős Problem #434

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: number theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

A numerical semigroup is the collection of all nonnegative sums formed from specified positive integer denominations, with repetitions allowed. If the denominations have greatest common divisor \(1\), every sufficiently large integer is attainable, but finitely many smaller positive integers may not be attainable. Such unattainable numbers are called gaps.

Erdős Problem 434 asks how to make the number of gaps as large as possible when we may choose exactly \(k\) distinct denominations from \(\{1,\dots,n\}\). The natural candidate is simply to use the \(k\) largest allowable numbers:

\[ A_*=\{n-k+1,n-k+2,\ldots,n\}. \]

The conjecture is that \(A_*\) maximizes the number of nonrepresentable positive integers among all sets with \(k\) elements \(A\subseteq[1,n]\) with \(\gcd(A)=1\). The assertion is now a published theorem, due to Géza Kiss.

This problem is closely related to #433, but the optimization target is different. Problem #433 maximizes the largest nonrepresentable integer, the Frobenius number. Problem #434 maximizes the total count of nonrepresentable integers, sometimes called the genus. Two sets may have the same largest gap but different numbers of gaps.

A small example

Take \(n=10\) and \(k=3\). The proposed extremal set is \(A_*=\{8,9,10\}\). Every representable positive integer is a sum of some number of copies of \(8\), \(9\) and \(10\). The first reachable positive values are \(8,9,10,16,17,18,19,20,\ldots\).

Exact enumeration finds precisely sixteen positive gaps:

\[ \{1,2,3,4,5,6,7,11,12,13,14,15,21,22,23,31\}. \]

The largest gap is \(31\). Every integer from \(32\) through \(39\) can be formed: for example, \(32=4\cdot8\), \(33=3\cdot8+9\), \(34=2\cdot8+2\cdot9\), \(35=8+3\cdot9\), \(36=4\cdot9\), \(37=8+9+10+10\), \(38=8+3\cdot10\) and \(39=9+3\cdot10\). Adding copies of \(8\) then constructs all higher integers, so the gap enumeration is complete.

An independent exact-integer search through all three-element subsets of \(\{1,\dots,10\}\) whose gcd is one finds that sixteen is indeed the maximum. The set \(\{5,9,10\}\) also has sixteen gaps, showing that the interval construction need not be the unique maximizer. The claim is that the indicated interval is a maximizer, not that no other set can attain the maximum.

The set \(\{4,7\}\) provides a contrasting smaller fixture. Its Frobenius number is \(17\), but its gaps are \(1,2,3,5,6,9,10,13,17\), only nine in total. These examples reinforce the distinction between largest gap and gap count.

What is known

The original problem is posed in P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), printed p. 86, available in the historical scan. It concerns extremal representations with repeated summands and an allowed set of denominations of fixed cardinality.

Géza Kiss proved the conjecture in On the extremal Frobenius problem in a new aspect, Annales Universitatis Scientiarum Budapestinensis, Sectio Mathematica 45 (2002), pp. 139–142. The maintained Erdős Problems #434 page attributes the result to Kiss and labels the problem PROVED (LEAN). The mathematical answer is affirmative: for \(2\leq k\leq n\), the interval of \(k\) largest integers maximizes the number of gaps under the gcd-one condition.

The restriction \(k\geq2\) is important. If \(k=1\) and \(n>1\), the proposed singleton \(\{n\}\) has gcd \(n\neq1\), making it ineligible; the admissible singleton \(\{1\}\) has no gaps. Thus the theorem cannot be stated without specifying the valid cardinality range.

The maintained discussion also describes later work formalizing the theorem in Lean with input from the related Dixmier Frobenius bounds. An earlier formal proof route assumed a version of Kneser's addition theorem as an axiom; a May 2026 comment claims a later fully unconditional Lean development. These are meaningfully different trust assumptions. A readable theorem statement and a purported machine-checked proof must be compared at exact source revisions before claiming formal verification.

GCL's current state

The original GCL source issue #1704 pins the teorth catalogue at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml Git blob 4e60263a80af6207aca494d2e1388e44fa372889. The frozen status is proved.

The pinned FormalConjectures 434.lean, Git blob b414e86165d0b754a69875a75a84ee94edaa59c7, formalizes the number of unrepresentable natural numbers and an extremal cardinality assertion, with \(k\geq2\). Its theorem statements are placeholders with by sorry in this frozen version, despite links to later external proof work. The formal statement's cardinality conventions must be matched against the original positive-integer gap count.

The authenticated original issue audit is RESULT/1 comment #6157575578. The article documents an established external result and independent finite checks; it does not confer GCL mathematical certification or V2 editorial admission.

What remains

The bounded next task is to enumerate the genus for all admissible sets with \(2\leq k\leq5\) and \(n\leq14\), using two independent exact algorithms: direct numerical-semigroup reachability and shortest-path computation of representable residue classes modulo the smallest denomination. Check that the set \(\{8,9,10\}\) has exactly sixteen gaps and that no allowed three-element set in \([1,10]\) has more.

The primary source task is to read Kiss's four-page 2002 proof and compare its exact range of \(k\), gcd assumption and representation convention with the pinned Lean theorem. If relying on newer Lean work, identify the exact commit, Mathlib toolchain and assumptions, especially whether Kneser's theorem remains an external axiom. The bounded task succeeds when both finite methods agree and the theorem-to-source mapping is explicit. It fails if the maximum largest gap is substituted for the maximum number of gaps, or if an axiomatized development is described as unconditional. Stop after these checks; the classical mathematical solution already exists.

Sources and claim boundaries

Original historical question: Erdős–Graham (1980), printed p. 86. Resolving publication: Kiss (2002), On the extremal Frobenius problem in a new aspect, pp. 139–142, referenced on the maintained #434 page. Related distinct problem: #433. Frozen GCL source: issue #1704, catalogue, pinned formal file, and authenticated source audit.

The small gap counts are reproducible exact arithmetic. The extremal theorem is credited to Kiss, with external Lean status separated from independent GCL verification. This article reports no new theorem, protected merge or editorial admission.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1704 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction