Erdős Problem #435

Erdős Problem #435: the semigroup of binomial coefficients

Partial proof of the candidate threshold and an exact example, 24 September 2026.

1) Statement

Let $n$ have at least two distinct prime factors. Determine the largest integer not of the form \[\sum_{i=1}^{n-1}c_i\binom ni,\qquad c_i\in\mathbb Z_{\ge0}. \] Write $n=\prod_{p\mid n}p^{a_p}$ and define \[W=\sum_{p\mid n}(p-1)\sum_{d=1}^{a_p}\binom n{p^d}. \] The known answer is $W-n$. This attempt proves, without importing that answer, that every integer greater than $W-n$ is representable. It also proves equality for $n=6$. The general nonrepresentability of $W-n$ is the remaining gap.

2) Valuations of the prime-power-indexed generators

Put $b_{p,d}=\binom n{p^d}$. These are among the allowed generators, because $p^d\le p^{a_p}<n$. We claim \[v_p(b_{p,d})=a_p-d,\qquad v_q(b_{p,d})\ge a_q\quad(q\mid n,\ q\ne p).\tag{1}\] Use $\binom nk=(n/k)\binom{n-1}{k-1}$. For $k=p^d$, the second factor has $p$-adic valuation zero: in its product formula \[\binom{n-1}{p^d-1}=\prod_{j=1}^{p^d-1}\frac{n-j}{j}, \] each numerator $n-j$ has the same $p$-adic valuation as $j$, since $v_p(j)<d\le a_p$. This proves the first equality. For $q\ne p$, the factor $n/p^d$ has $q$-adic valuation $a_q$ and the remaining binomial coefficient is an integer, proving the inequality.

In particular the gcd of all the allowed generators is one. Any common prime divisor would divide $\binom n1=n$, but for each $p\mid n$ the generator $b_{p,a_p}$ is not divisible by $p$.

3) A complete residue system made of nonnegative combinations

Consider the $n$ coefficient arrays \[0\le e_{p,d}\le p-1\qquad(p\mid n,\ 1\le d\le a_p), \] and their sums $R=\sum e_{p,d}b_{p,d}$. There are exactly $\prod_p p^{a_p}=n$ arrays. Their residues modulo $n$ are all distinct.

To prove distinctness, suppose two arrays give the same residue. Fix $p\mid n$. Terms associated with other primes vanish modulo $p^{a_p}$ by $1$. If the $p$-arrays differ, choose the largest $d$ at which they differ. The corresponding term of the difference has valuation exactly $a_p-d$, since its nonzero coefficient has absolute value at most $p-1$. All earlier terms have valuation at least $a_p-d+1$, and later terms cancel. Their sum cannot be divisible by $p^{a_p}$, a contradiction. Thus the arrays agree for every prime.

These sums therefore supply one representative $R\in[0,W]$ for every residue modulo $n$, and every representative belongs to the semigroup generated by the original binomial coefficients.

4) All integers above the proposed threshold are representable

Let $x>W-n$, and choose the representative $R$ with $R\equiv x\pmod n$. If $x<R$, then $x\le R-n\le W-n$, a contradiction. Hence $x=R+tn$ with $t\ge0$. Since $n=\binom n1$ is an allowed generator, $x$ is representable. This proves \[G\!\left(\binom n1,\ldots,\binom n{n-1}\right)\le W-n.\tag{2}\] The proof establishes eventual representability directly, rather than deducing it only from gcd one.

5) An exact case and the missing lower inequality

For $n=6$, the distinct generators are $6,15,20$. The formula gives $W=15+2\cdot20=55$, so $2$ shows that every integer at least 50 is representable. To exclude 49, suppose $49=6u+15v+20w$. Reduction modulo 3 gives $w\equiv2\pmod3$, while $20w\le49$ forces $w=2$. The remaining equation is $2u+5v=3$, impossible for nonnegative integers $u,v$. Thus the largest missing integer is exactly 49 in this case.

For general $n$, residue uniqueness among the bounded coefficient arrays does not prove that their values are the least semigroup elements in their residues. Other binomial generators, or coefficients exceeding the specified digit ranges, might in principle produce a smaller representative. Ruling that out requires a nonnegative normalization argument. Without it, the fact that $W$ is the largest displayed representative does not establish that $W-n$ is absent.

6) Outcome and source

UNRESOLVED at the general lower-bound step in this attempt. The valuation lemma, complete residue system, full upper threshold and the exact $n=6$ case are proved. Hwang and Song's Theorem 0.1 identifies this residue system as the Apéry set and supplies the missing minimality in the literature; that difficult identification is not silently assumed here.

Sources: https://www.erdosproblems.com/435, checked 24 September 2026; W. Hwang and K. Song, The Frobenius problem for Numerical Semigroups generated by binomial coefficients, https://arxiv.org/abs/2412.17882, version 3. The known formula and structural approach are attributed to that work. No novelty or independent Lean verification is claimed.

The estimate describes proof coverage toward the exact formula, not a probability.

7) COMPLETION ESTIMATE

COMPLETION: 70%