Skip to content

Erdős Problem #175

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

The central binomial coefficient counts ways to choose \(n\) objects from \(2n\):

\[ \binom{2n}{n}=\frac{(2n)!}{(n!)^2}. \]

A positive integer is squarefree when no square of a prime divides it. Erdős #175 asked for a proof that \(\binom{2n}{n}\) is not squarefree for every \(n\ge5\). Its numerical range and the choice of the central coefficient are essential.

A small example

For \(n=4\), \(\binom84=70=2\cdot5\cdot7\) is squarefree, so the threshold five cannot be replaced by four. For \(n=5\), \(\binom{10}5=252=2^2\cdot3^2\cdot7\), and for \(n=8\), \(\binom{16}8=12870\) is divisible by \(3^2\). The power-of-two input \(n=8\) illustrates why an argument relying only on \(4\mid\binom{2n}{n}\) is insufficient.

What is known

The original assertion is PROVED. Erdős and later authors noticed that \(4\mid\binom{2n}{n}\) unless \(n\) is a power of two. The remaining case was settled for all \(n\ge5\) independently by Velammal (1995) and Granville–Ramaré (1996), while Sárközy (1985) had covered sufficiently large \(n\).

The key elementary identity follows from Kummer's theorem: the 2-adic valuation of \(\binom{2n}{n}\) equals the number of ones in the binary expansion of \(n\). Hence every \(n\) that is not a power of two contributes at least two factors of two. If \(n\) is a power of two, the 2-adic valuation equals exactly one, and a proof must find the square of an odd prime.

A stronger, separate question asks about \(f(n)\), the largest valuation of a single prime in \(\binom{2n}{n}\). Sander proved \(f(n)\to\infty\); Erdős–Kolesnik improved its unconditional lower bound to \(f(n)\gg(\log n)^{1/4-o(1)}\). Whether \(f(n)\gg\log n\) for all \(n\) remains OPEN, although it holds for almost all \(n\). The settled squarefree statement does not settle this logarithmic question.

GCL's current state

The pinned and maintained Erdős #175, updated February 2026, classify the original assertion PROVED. Original issue: #1444. Reports of a Lean proof are external; GCL has not run its exact project or independently reconstructed the full odd-prime argument.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded arithmetic task computes \(\binom{2n}{n}\) and its prime valuations exactly for \(1\le n\le500\), checks Kummer's binary-popcount identity, and finds an explicit squared prime for all \(n\ge5\) in that range. Acceptance: \(n=4\) is correctly identified as an exception, and the power-of-two cases cannot be certified merely using the factor two. Stop at finite fixtures, not a proof for all \(n\).

Sources and claim boundaries

No new binomial-valuation theorem, independently certified Lean proof or editorial admission is claimed.

Catalogue and evidence provenance

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

Back to catalogue · Compendium introduction