Skip to content

Erdős Problem #379

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

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

Erdős Problem 379 asks whether the middle entries of some rows of Pascal's triangle can all have a large prime-power divisor, with the prime allowed to depend on the entry. More precisely, for a positive integer \(n\), let \(S(n)\) be the largest exponent \(r\) for which every \(C(n,k)\), with \(1 ≤ k < n\), is divisible by \(p^r\) for at least one prime \(p\) that may depend on \(k\). The question is whether

\[ \limsup_{n\to\infty} S(n) = \infty. \]

This is much weaker than asking for one prime to divide an entire row. It also does not ask for the same exponent to be the exact prime-adic valuation of every entry: each entry only needs some prime whose power with exponent \(r\) divides it. The original assignment and source packet are issue #1649.

The original source is Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), printed p. 72 in the scanned source. There the problem is phrased with \(S(n)\) as the largest integer for which, for every \(k\) in the interior range through \(n-1\), the binomial coefficient is divisible by the corresponding power of some prime. The maintained version's range \(1 ≤ k < n\) is the same quantifier, written with a strict inequality.

A small example

The construction used in the resolution has a small checkable instance. Take \(p=3\), \(r=2\), and \(n=2^{φ(3^2)}=2^6=64\). An exact-integer enumeration of all \(k=1,\ldots,63\) verifies

\[ 4 ∣ C(64,k) ∨ 9 ∣ C(64,k). \]

The recorded check found 62 values divisible by 4, 37 divisible by 9, 36 divisible by both, and no values divisible by neither. For concrete audit points, \(C(64,1)=64\) has 2-adic valuation 6; \(C(64,2)=2016\) is divisible by both 4 and 9; and \(C(64,32)=1832624140942590534\) is not divisible by 4 but is divisible by 9. These are ordinary integer divisions, not probabilistic tests.

This establishes the finite lower bound \(S(64) ≥ 2\), and illustrates why the prime may change with \(k\). It does not establish the exact value of \(S(64)\), and one finite row cannot establish an unbounded limsup. The value of the example is that it is a reproducible sanity check for the quantifiers and for the proposed family of rows.

What is known

The public resolution is a first-hand proof comment by Terence Tao in the Problem 379 discussion, dated 28 August 2025. It identifies the key proposition

\[ S(2^{φ(p^r)}) ≥ r. \]

This holds whenever \(r ≥ 2\) and \(p\) is prime with \(p > 2^{r-1}\). Since there are arbitrarily large primes, this gives the required unbounded limsup.

The mechanism is short but has several quantifiers worth preserving. Put \(m=φ(p^r)\) and \(n=2^m\). From \(C(n,k)k=C(n-1,k-1)n\), either \(2^r\) already divides \(C(n,k)\), or \(k\) contains a large power of 2. In the latter case both \(k\) and \(n-k\) are small odd-prime multiples after removing that power of 2, so neither is divisible by \(p\), because \(p>2^{r-1}\). Euler's theorem gives \(p^r ∣ n-1\). A second identity, \(C(n,k)k(k-1)=C(n-2,k-2)n(n-1)\), then forces \(p^r ∣ C(n,k)\). This handles every \(1 ≤ k < n\), not merely typical or central entries.

The proof is available in full at Analysis/Misc/erdos_379.lean in the pinned teorth/analysis commit 4f623b0f4cacdb967f1f8132db0becaee0f1fb3d, file blob 764c2ecb0bc6f99147ed91a2fe37e94b0bcc9f84. No separate refereed resolution paper was located in this bounded inquiry; Tao's dated discussion proof is therefore cited as the primary public resolution source, not silently upgraded to a journal publication.

GCL's current state

The frozen catalogue record is number 379 in teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, YAML blob 4e60263a80af6207aca494d2e1388e44fa372889. It records informal state proved, formal state Lean, proved (Lean), and formalized: yes, all last updated 2025-08-31. The live Erdős Problems entry, read during this audit, says PROVED (LEAN), attributes the affirmative solution to Cambie, Kovač, and Tao, and reports the page last edited 12 January 2026.

The pinned FormalConjectures file is at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, file blob cc789bab60d7d6367b5583d0d973d7a8387f47bd. Its definition uses Finset.Ico 1 n, matching \(1 ≤ k < n\), and its theorem has the correct extended-natural limsup target, but its proof is literally by sorry. The complete proof in the teorth analysis file is separate evidence. The V2 ledger alone decides accepted coverage; this article supplies no GCL mathematical certification.

What remains

The mathematical resolution is externally documented, but provenance still needs careful handling. A bounded successor task should compare the printed p. 72 statement, Tao's comment, the complete teorth proof, and the pinned FormalConjectures definition line by line. In particular, it should record the dependence of \(p\) on \(k\), the strict interior range, the use of Euler's theorem, the choice \(n=2^{φ(p^r)}\), and the coercion from natural-valued \(S\) to an extended-natural limsup. It should also explain that the FormalConjectures file is a statement carrier with by sorry, not an independently replayed proof.

No claim here is made about a newer paper, a prize, novelty, or independent formal certification. The live page's additional remark about constructions such as \(3^{2^C}\) is an unneeded secondary observation for this audit and is not treated as the primary proof.

Sources and claim boundaries

The source chain is: the original issue #1649; the Erdős–Graham scan at printed p. 72; Tao's 28 August 2025 primary resolution comment; the pinned complete Lean proof at teorth/analysis commit 4f623b0f4cacdb967f1f8132db0becaee0f1fb3d; the frozen catalogue commit and blob above; and the pinned FormalConjectures commit and blob above. The finite \(n=64\) calculation is an audit check performed for this article, not a proof of the asymptotic statement. An external proof and a compilable theorem source are distinct from GCL's acceptance decision.

Original SOURCE RESULT/1 citation: authenticated original RESULT/1. No future comment, acceptance, publication, or certification link is fabricated here. The appropriate status language is therefore that the source lock is strong and the external resolution is documented, while formal replay, semantic adjudication, and accepted coverage remain claims for their respective accountable controls.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1649 — 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