Skip to content

Erdős Problem #396

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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

Let \(k\) be a nonnegative integer. Erdős Problem 396 asks whether one can always find a positive integer \(n\) for which every integer in the descending block \(n,n-1,\ldots,n-k\) contributes to a single divisor of the central binomial coefficient. In formulas, the intended question is whether, for every \(k\), there is an \(n>k\) such that

\[ \prod_{i=0}^{k}(n-i) \mid \binom{2n}{n}. \]

The condition \(n>k\) is the natural normalization: it keeps every factor positive and makes the product an ordinary positive integer. The right side counts the ways to choose \(n\) objects from a set of \(2n\) objects. The problem asks whether that count can absorb the whole consecutive product, not merely each factor separately. The issue-bound statement is Erdős Problem 396.

The product is deliberately consecutive, so shared prime factors matter. Knowing that each factor divides the binomial coefficient does not automatically show that their product does: the same prime power may be needed by several factors. This is why the exact quantifiers and the joint divisibility condition must be kept visible.

A small example

The case \(k=2\) has a nontrivial finite witness at \(n=2480\). Direct exact arithmetic gives

\[ 2480\cdot2479\cdot2478=15\,234\,545\,760, \]

and

\[ \binom{4960}{2480}\bmod 15\,234\,545\,760=0. \]

This can be reproduced without floating-point arithmetic by running:

from math import comb

k, n = 2, 2480
d = n * (n - 1) * (n - 2)
assert comb(2 * n, n) % d == 0
print(d, comb(2 * n, n) % d)

The calculation verifies one finite instance only. It does not prove the universal assertion in \(k\), establish that \(2480\) is the smallest witness, or explain why witnesses should exist for every larger \(k\). It is a useful regression check for the normalization and for any future computational certificate, not a substitute for a proof.

What is known

The maintained live problem entry, accessed 2026-10-13, gives the same question and records the problem as open. It points to Carl Pomerance’s paper, “Divisors of the Middle Binomial Coefficient,” The American Mathematical Monthly 122 (2015), 636–644, primary PDF and DOI record. The site’s short key Po14 and bibliography year “2014” do not match the paper’s journal volume, page footer, and PDF presentation, which identify the published article as 2015; that bibliographic drift is retained rather than silently repaired. The original attribution is Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), cited by the live page as ErGr80.

Pomerance’s Theorem 2, on pp. 638–640, proves that for every fixed positive \(k\), almost all positive integers \(n\) satisfy

\[ (n+1)(n+2)\cdots(n+k)\mid\binom{2n}{n}. \]

That is a forward product and is not the falling product in Problem 396. His Theorem 3, on p. 640, proves that for every fixed \(k\geq0\), infinitely many \(n>k\) satisfy \(n-k\mid\binom{2n}{n}\), while those \(n\) have upper asymptotic density less than \(1/3\). This is a strong one-factor result, but it does not combine the factors \(n,n-1,\ldots,n-k\) into one divisor. The proof uses p-adic valuations and Kummer’s carry criterion, a promising interface for a bounded successor task.

GCL's current state

The frozen catalogue evidence supplied with the issue is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, with data/problems.yaml blob 4e60263a80af6207aca494d2e1388e44fa372889. Its entry marks the informal status and general status as open with last update 2025-08-31, records no prize, and labels the topics number theory and binomial coefficients. It also records OEIS sequence A375077 and statement-formalized metadata, while its formal-solution field remains unformalized.

The pinned formal source is FormalConjectures/ErdosProblems/396.lean at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, file blob 1ebbaf866b7477674b8a8eeda7b216f03ef3137b. It states ∀ k : ℕ, ∃ n : ℕ, descFactorial n (k + 1) ∣ centralBinom n, but the theorem is proved by sorry; a nearby TODO says that additional material is not formalized. The Lean statement has no explicit n>k hypothesis. Its descending-factorial and natural-number divisibility definitions should therefore be checked when comparing it with the conventional positive-integer statement. Presence of a theorem source is not proof, semantic-equivalence certification, or accepted coverage.

What remains

The clean mathematical gap is simultaneous control of the prime-power valuations in the whole block \(n(n-1)\cdots(n-k)\). A bounded investigation could fix one small \(k\), compute exact witnesses and non-witnesses, factor the divisor, and compare each required valuation with the valuation of \(\binom{2n}{n}\) as computed from factorial valuations or carries. A useful first target is a checked lemma for \(k=2\) or \(k=3\) under an explicit congruence or prime-factor hypothesis, with a finite range large enough to catch normalization errors. Any claimed generalization must separately address overlapping prime factors and cannot be inferred from Pomerance’s forward-product density theorem.

The V2 ledger, not this editorial article, decides accepted coverage. This article supplies source mapping and a bounded research interface only; it does not certify a proof, settle the open problem, or authorize a publication status.

Sources and claim boundaries

The primary mathematical evidence used here is Pomerance’s readable article, especially Theorems 2 and 3 on pp. 638–641. The original Erdős–Graham book is cited as the source of the question, but no claim here depends on an unread page-level quotation from that book. The live page is a maintained secondary catalogue and status surface, not sole authority for mathematical acceptance. The frozen catalogue and formal-file commit/blob identities above are the reproducibility anchors.

Original SOURCE RESULT/1 citation: authenticated original RESULT/1. No future comment, proof, Lean replay, or certification is being implied. The exact finite calculation is independently reproducible, but remains finite evidence. No claim is made that the formal theorem is correct beyond its displayed proposition, and no GCL mathematical certification is supplied.

Catalogue and evidence provenance

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