Erdős Problem #435
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 binomial coefficient counts the ways to choose a prescribed number of objects from a larger collection. For example, \(\binom63=20\). Fix an integer \(n\) and take the nontrivial coefficients
Erdős Problem 435 asks for the largest positive integer that cannot be written as a nonnegative integer combination of these coefficients, with repetitions permitted. In the language of numerical semigroups, this is their Frobenius number.
There is an essential restriction: \(n\) must not be a power of a prime. When \(n=p^a\), all the nontrivial coefficients \(\binom ni\) have common factor \(p\). Consequently infinitely many integers are not representable, so no finite greatest missing integer exists without first rescaling the generating set. For \(n\) having at least two different prime divisors, the coefficients instead have gcd one, and the Frobenius number is finite.
The problem connects elementary combinations, the distribution of prime factors in binomial coefficients and the structure of numerical semigroups. It is now solved by work of WonTae Hwang and Kyunghwan Song.
A small example
Take \(n=6=2\cdot3\), which is not a prime power. The nontrivial binomial coefficients in the sixth row of Pascal's triangle are
Thus the set of possible sums is generated by just the three denominations \(6,15,20\). The largest integer that cannot be formed is \(49\).
The assertion can be verified completely, rather than guessed from a partial search. The number \(49\) is not a sum of nonnegative multiples of \(6,15,20\): examining the possible numbers of coins with denomination \(20\), and then reducing the remaining amount modulo \(3\) and \(6\), rules out a representation. Conversely, every integer from \(50\) through \(55\) is representable:
Since \(6\) is an available denomination, adding further copies of \(6\) covers every integer greater than \(55\). Therefore \(49\) is exactly the Frobenius number, not just a large missing value in a finite test.
The published formula gives the same result: the prime factorization of \(6\) is \(2^1 3^1\), so the predicted answer is
This single exact check illustrates the theorem without establishing the formula in general.
What is known
The question appears in P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), printed p. 86 of the historical scan. It asks for the Frobenius number of a special family of binomial coefficients rather than arbitrary coin denominations.
WonTae Hwang and Kyunghwan Song solved the binomial semigroup problem in The Frobenius problem for Binomial Coefficients, first submitted December 23, 2024. Their Theorem 0.1 and Corollary 3.3 describe the numerical semigroup generated by the relevant binomial coefficients and yield a closed form for the greatest nonrepresentable integer. The maintained Erdős Problems #435 page records the result as PROVED (LEAN) and also notes independent work by Michael Peake and Stijn Cambie.
If
has at least two distinct prime factors, the reported formula is
The inner sum runs over powers of each prime appearing in the factorization of \(n\); replacing this by all positive integers \(j\) or by the exponents themselves would change the formula. The outer factor \(p-1\) is also essential. The expression agrees with the exact example at \(n=6\).
The same research develops additional numerical-semigroup invariants, including the Apéry set and the number of gaps. Those quantities provide structure behind the formula but are not the same as the single greatest missing integer. Prime powers require a different, normalized formulation and are excluded from the statement of the original Erdős question.
GCL's current state
The original source issue #1705 freezes the teorth catalogue at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, file data/problems.yaml, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. It records the status as proved, consistent with the research of Hwang and Song.
The source issue explicitly records no 435.lean file in the admitted FormalConjectures provider revision 85f863718beeec7b58a3a1926ee92e3472bc2020. That is a frozen-source fact; the maintained site's later formalization report has separate provenance. No GCL compiler replay, axiom report or mathematical proof certification is asserted from the status label.
The authenticated original issue audit is RESULT/1 comment #6157604149. It records the primary publication, precise prime-power restriction and independently verified small numerical-semigroup example. The V2 editorial ledger is the separate authority for accepted Compendium coverage.
What remains
The bounded next task is to calculate the Frobenius number for each \(n\leq30\) having at least two distinct prime factors. Generate every nontrivial coefficient \(\binom ni\) exactly, remove duplicates and calculate the numerical semigroup using a shortest-path method on residue classes modulo the smallest generator. Independently check the outcome with finite dynamic programming through a justified conductor. Compare the results with the displayed Hwang–Song formula.
The source-concordance component should match the exact hypotheses and prime-power exponents in Hwang–Song Theorem 0.1, Corollary 3.3 and Remark 0.2 to the original 1980 formulation. It should separately record what changes in the prime-power case. The bounded task succeeds only if exact computations agree and all index conventions are preserved. It fails if coefficients \(\binom n0=\binom nn=1\) are accidentally included, if prime powers are treated as having a finite unscaled Frobenius number, or if a formal proof is claimed from an unadmitted source. Stop after this arithmetic and source audit, because the broad mathematical theorem has already been published.
Sources and claim boundaries
Original question: Erdős–Graham (1980), p. 86. Primary resolving research: Hwang and Song, arXiv:2412.17882, including Theorem 0.1 and Corollary 3.3. Maintained status: Problem #435. Frozen GCL source: issue #1705, teorth catalogue, and authenticated source return.
The \(n=6\) Frobenius certificate is independently checked exact arithmetic. The general formula is attributed to Hwang and Song rather than presented as a new GCL proof. External formal-verification reports do not constitute a GCL Lean replay or protected editorial admission.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1705 — 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.