Erdős Problem #433
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
The Frobenius coin problem asks which amounts of money can be formed using a specified collection of coin denominations, with unlimited repetitions allowed. If the denominations have greatest common divisor \(1\), then every sufficiently large integer can be expressed as a nonnegative integer combination of them, but some smaller integers may remain unreachable. The greatest unreachable integer is called their Frobenius number.
Let \(G(A)\) be this largest missing integer for a finite set of denominations \(A\subseteq\{1,\dots,n\}\) with \(\gcd(A)=1\). Erdős Problem 433 considers the largest possible Frobenius number among all such sets of exactly \(k\) distinct denominations:
The question asked whether, for fixed \(k\geq2\) and \(n\to\infty\),
The fixed \(k\) qualification matters. An asymptotic formula proved for each fixed \(k\) does not automatically hold uniformly when \(k\) grows with \(n\).
For a set containing denomination \(1\), every positive integer is representable and the set of missing nonnegative values is empty. Therefore the definition needs an explicit convention, such as \(G(A)=-1\), in that degenerate case. The extremal problem's large maximizers are not affected by the convention.
A small example
Take the denominations \(A=\{8,9,10\}\). The integer \(31\) cannot be formed. Any sum of at most three coins is at most \(3\cdot10=30\), whereas a sum of four or more coins is at least \(4\cdot8=32\). Thus \(31\) is absent.
On the other hand, every integer from \(32\) through \(39\) can be formed:
Since the coin \(8\) is available, adding any further multiple of \(8\) extends these eight consecutive representations to every integer greater than \(39\). Hence \(G(\{8,9,10\})=31\), proved exactly without relying on a finite search horizon.
This example exposes a real defect in the formula printed on the maintained Erdős Problems page. Its displayed upper bound reads
At \(k=3,n=10\), it would give \(g(3,10)\leq29\). But the explicit set above shows \(g(3,10)\geq31\), so that printed inequality is false. The page's own discussion records the correction: the upper bound should use a ceiling, not a floor. Then the right-hand side is \(39\), consistent with the example. The typo is in the maintained transcription, not a counterexample to the published theorem of Dixmier.
An independent exhaustive exact-integer search over all three-element subsets of \(\{1,\dots,10\}\) with gcd \(1\) finds \(g(3,10)=31\), attained by \(\{8,9,10\}\) and \(\{5,9,10\}\).
What is known
Erdős and Graham studied this extremal Frobenius problem in On a linear diophantine problem of Frobenius, Acta Arithmetica (1972), pp. 399–408, and discussed it again in Old and New Problems and Results in Combinatorial Number Theory (1980), in the historical monograph. They proved an upper bound smaller than \(2n^2/k\) and constructed examples with lower bounds of the form \(n^2/(k-1)-5n\).
Jacques Dixmier proved the conjectured leading asymptotic in Proof of a conjecture by Erdős and Graham concerning the problem of Frobenius, Journal of Number Theory 34(2) (1990), pp. 198–209. The result establishes the proposed growth for each fixed \(k\) and provides more precise extremal inequalities for \(2\leq k<n\). Dixmier also identified exact extremal values when \(k-1\) divides \(n\), \(n-1\) or \(n-2\).
The maintained Erdős Problems #433 entry says PROVED (LEAN). Its remarks reproduce the historical bounds and Dixmier's conclusion, but the displayed sharp upper inequality contains the floor/ceiling transcription error demonstrated above. A November 2025 discussion comment by Stijn Cambie explicitly identifies this mistake and recommends the ceiling correction. That is stronger evidence of a concrete source defect than a merely stylistic editorial preference.
A related question, Erdős #434, concerns another extremal Frobenius formulation. Its claims and formalization status must be reviewed separately; a shared source paper does not make the problem statements interchangeable.
GCL's current state
The original source issue #1703 locks the teorth catalogue at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, file data/problems.yaml with Git blob 4e60263a80af6207aca494d2e1388e44fa372889. The frozen metadata reports the problem as proved, consistent with Dixmier's mathematical theorem.
That issue also records no Problem 433 statement file in GCL's admitted FormalConjectures provider snapshot 85f863718beeec7b58a3a1926ee92e3472bc2020. Later external formalization attempts, including ones described in maintained-page comments, have their own source identities and may depend on unadmitted auxiliary theorems. The page's “LEAN” label does not establish that a particular version has been compiled or axiom-audited by GCL.
The authenticated original-issue source audit #6157520575 records the exact \(k=3,n=10\) counterexample to the erroneous printed bound, the correct fixed \(k\) asymptotic scope and the source-correction requirement. This manuscript remains a documentary artifact until separately admitted through the V2 editorial ledger.
What remains
The leading-order mathematical question is already resolved by Dixmier. The nearest useful task is therefore to correct the maintained mathematical transcription from the actual 1990 journal theorem. Read the printed bound and its floor and ceiling symbols directly, then compare it with the known discussion correction and the small certificate above. Distinguish the lower and upper inequalities and the fixed \(k\) asymptotic from a hypothetical uniform-in \(k\) statement.
A bounded computational fixture should evaluate \(g(k,n)\) for \(2\leq k\leq5\) and \(n\leq14\) using independent algorithms: exhaustive subsets with gcd checks, and a numerical-semigroup residue shortest-path method for each \(G(A)\). The task succeeds if both algorithms agree, the regression at \(g(3,10)=31\) holds, and all printed inequalities match the primary source. It fails if the false floor bound survives, or if a set containing \(1\) is assigned a nonexistent largest missing positive integer without a stated convention. Stop after source repair and small exact enumeration. Any claim of formal proof replay needs separate compiler evidence.
Sources and claim boundaries
Historical sources: Erdős–Graham (1972), Acta Arithmetica pp. 399–408, and Erdős–Graham (1980). Resolving primary publication: Jacques Dixmier (1990), DOI 10.1016/0022-314X(90)90150-P. Current statement and the documented correction discussion: Erdős Problem #433. GCL provenance: issue #1703, frozen catalogue, and RESULT/1 comment #6157520575.
The \(31\) example and falsification of the printed floor inequality are independently proved. Dixmier's global asymptotic is an externally published theorem, not a new GCL discovery. No full Lean replay, mathematical certification or protected editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1703 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.