Skip to content

Erdős Problem #376

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

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

Let \(C_n=\binom{2n}{n}\) be the central binomial coefficient. Erdős Problem #376 asks whether there are infinitely many nonnegative integers \(n\) for which \(C_n\) is coprime to \(105=3\cdot5\cdot7\). Equivalently, none of \(3\), \(5\), or \(7\) divides \(C_n\). Restricting to positive \(n\) makes no difference to an infinitude question; the formal file uses \(ℕ\) and therefore includes \(0\).

The useful translation is into digit restrictions. Kummer's theorem says that the exponent of a prime \(p\) in \(\binom{2n}{n}\) equals the number of carries when \(n+n\) is performed in base \(p\). For odd \(p\), there is no carry precisely when each digit in base \(p\) is at most \((p-1)/2\). Thus #376 asks whether infinitely many \(n\) have only digits \(0,1\) in base \(3\), only \(0,1,2\) in base \(5\), and only \(0,1,2,3\) in base \(7\). This is a striking example of one question having both a multiplicative form, involving divisibility of factorial ratios, and an additive form, involving simultaneous restrictions on positional expansions.

A small example

Take \(n=10\). Exact integer arithmetic gives

\[ \binom{20}{10}=184756, \qquad 184756\bmod 3=1, \qquad 184756\bmod 5=1, \qquad 184756\bmod 7=5. \]

Therefore \(\gcd(184756,105)=1\). The same check is visible in the base expansions

\[ 10=(101)_3=(20)_5=(13)_7. \]

Every displayed digit is within the allowed range, so Kummer's criterion predicts exactly the three nonzero residues above. This is a reproducible finite certificate: one can compute the binomial coefficient and three remainders using integer arithmetic alone. It proves that the solution set is nonempty, but it says nothing about whether the set is finite or infinite. Even a very large list of examples would remain a finite computation unless accompanied by a uniform argument.

What is known

The primary two-prime result is Erdős, Graham, Ruzsa, and Straus, “On the Prime Factors of \(\binom{2n}{n}\),” Mathematics of Computation 29 (1975), 83–92. Their main result includes that for any two odd primes \(p\) and \(q\), infinitely many \(n\) satisfy \(\gcd(\binom{2n}{n},pq)=1\); the relevant restricted-digit argument is in Theorem 1 and its proof on pp. 85–86. It does not supply the simultaneous three-prime conclusion for \(3\), \(5\), and \(7\).

The maintained page records the same boundary and identifies the allowed-digit formulation and OEIS A030979. Croot, Mousavi, and Schmidt (2024) construct infinitely many \(n\) with unusually small, but not zero, valuations at each prime in a fixed set of small primes. Bloom and Croot (2025) obtain an “almost all digits small” theorem for sufficiently large primes; their stated three-base threshold is far above \(3,5,7\), and allowing a small exceptional part is weaker than coprimality. These are relevant advances, not solutions to #376. In particular, a bound saying that the forbidden prime part is at most \(n^\epsilon\) does not imply that this part equals \(1\).

A 2010 preprint by Robert Betts advertises a three-prime extension. Its HTML Theorem 3 requires digit bounds \(A\ge p/2\), \(B\ge q/2\), and \(C\ge r/2\), whereas the no-carry condition requires \(A=(p-1)/2\), \(B=(q-1)/2\), and \(C=(r-1)/2\). That visible hypothesis mismatch prevents the theorem, as stated, from proving #376. This is a source-level diagnosis, not a claim about every argument in the preprint.

GCL's current state

The original issue #1646 supplies a frozen catalogue snapshot: teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, catalogue blob 4e60263a80af6207aca494d2e1388e44fa372889. At that revision, the informal and maintained status is open, last updated 2025-08-31, with formal status unformalized and statement metadata present. The live page was checked on 2026-10-13; it remains open, was last edited 2025-12-28, and reports no proof exposition or proof claim.

The pinned FormalConjectures source is google-deepmind/formal-conjectures commit 85f863718beeec7b58a3a1926ee92e3472bc2020, file FormalConjectures/ErdosProblems/376.lean, blob 57c99965ce509ec09e9bf9d8a367d3c17550f31b. Its main theorem formalizes the infinitude statement but ends with by sorry; its two-odd-prime variant also ends with by sorry. Presence of a formal statement is not a checked proof or a certification that the informal and formal versions have been proved equivalent.

What remains

The central unresolved task is a theorem about the intersection of three restricted-digit sets, or a proof that this intersection is finite. The two-prime theorem does not automatically iterate: satisfying two base restrictions gives no independent control of the third. Heuristics about the apparent density of the intersection are useful for orientation but are not lower bounds.

A bounded successor task could first formalize and independently check the equivalence between the three no-carry conditions and coprimality with \(105\), then produce a finite, reproducible census up to an explicitly fixed bound. Acceptance should require exact arithmetic, a completeness argument for the finite search, and separate reporting of the resulting certificate from any infinitude claim. A failed completeness proof or a discovered mismatch in the formal quantifiers would falsify the task without changing the mathematical status of #376.

Sources and claim boundaries

The mathematical statement and live status are given by Erdős Problems #376, including its discussion thread. The primary paper is Erdős–Graham–Ruzsa–Straus (1975); its downloaded source was checked as a ten-page PDF, SHA-256 711dfea72b5dce7a284f0f21563e5de6c35aefb87eb1613b294e83395b877caa. Related primary documents are Croot–Mousavi–Schmidt (2024), Bloom–Croot (2025), and Betts (2010).

This article reports source facts, an exact finite check, and explicit limits on what those facts establish. It does not certify the open problem, validate a Lean proof, or promote any external claim. The original SOURCE RESULT/1 citation is authenticated original RESULT/1.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1646 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • 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