Skip to content

Erdős Problem #378

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 378 asks about squarefree entries in a row of Pascal's triangle. An integer is squarefree when no prime square divides it. For a fixed integer \(n\), look at the binomial coefficients

\[ \binom{n}{k}, \qquad 1\leq k<n. \]

The endpoints \(k=0\) and \(k=n\) are deliberately omitted from the question: both coefficients are \(1\), so they would contribute two automatic examples. Let \(S(n)\) be the number of squarefree coefficients in this internal part of row \(n\). For each fixed integer \(r\geq0\), the problem asks whether the set

\[ \{n\in\mathbb N:S(n)\geq r\} \]

has a natural density, and whether that density is positive. “Density” here means the limiting proportion among the first \(N\) integers as \(N\) tends to infinity.

The distinction between internal entries and the whole row is the key normalization. Since the two endpoints are always squarefree, saying that the whole row has exactly \(2m+2\) squarefree entries is equivalent to saying that \(S(n)=2m\). The primary theorem below is phrased using the whole row, while the Erdős question is phrased using internal entries.

A small example

Take \(n=10\). Exact arithmetic gives the internal row

\[ 10,\ 45,\ 120,\ 210,\ 252,\ 210,\ 120,\ 45,\ 10. \]

The factorizations relevant to squarefreeness are

\[ 10=2\cdot5,\qquad 210=2\cdot3\cdot5\cdot7, \]

while \(45=3^2\cdot5\), \(120=2^3\cdot3\cdot5\), and \(252=2^2\cdot3^2\cdot7\) are not squarefree. Therefore the squarefree internal positions are exactly \(k=1,4,6,9\), and \(S(10)=4\). Including the two endpoint \(1\)'s gives six squarefree entries, which is \(2m+2\) with \(m=2\).

This check is reproducible without floating-point computation:

from math import comb
from sympy import factorint

n = 10
squarefree = []
for k in range(1, n):
    factors = factorint(comb(n, k))
    if all(exponent == 1 for exponent in factors.values()):
        squarefree.append(k)
print(squarefree, len(squarefree))

The verified output is [1, 4, 6, 9] 4. It illustrates the indexing and checks one finite row only; it neither proves an asymptotic density nor supplies the analytic estimates needed for the general result.

What is known

The relevant primary source is Andrew Granville and Olivier Ramaré, “Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients,” Mathematika 43 (1996), 73–107, DOI 10.1112/S0025579300011608. The accessible author-hosted PDF has SHA-256 2fc57e71c90e5246a661464b82a3bd7e33514660e3cf1bb0d6bdadb2ff3fad63.

Their introduction records the central-binomial result as Theorem 1. In displayed form, the claim is

\[ \forall n\in\mathbb{N},\quad n>4\implies \neg\mathrm{Squarefree}\left(\binom{2n}{n}\right). \]

More directly relevant here, Theorem 5 on printed p. 75 states that the sequence of integers \(n\) for which row \(n\) of Pascal's triangle has exactly \(2m+2\) squarefree entries has an asymptotic density, denoted by \(\eta_m\). It also states that, for a constant \(\tau_4>0\) and \(m\geq1\),

\[ 0<\eta_m\ll\exp\left(-\frac{\tau_4\sqrt m}{\log(2m)}\right). \]

For the original question, internal count at least \(r\) means the full row has at least \(r+2\) squarefree entries. The complementary exact-count cases are therefore \(2m+2<r+2\), equivalently \(0\leq m\leq\lfloor(r-1)/2\rfloor\). Thus the live problem page records the resulting density as

\[ 1-\sum_{0\leq m\leq\lfloor(r-1)/2\rfloor}\eta_m. \]

It is positive because \(\eta_{r+1}>0\) gives a positive-density class with more than enough squarefree internal entries. This is the source-level resolution of the question, not a claim that GCL has independently certified the paper's proof.

The live Erdős Problems entry for #378, accessed 2026-10-13, attributes the original question to Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 72, and identifies Granville–Ramaré as the resolving source. Its two discussion comments likewise point to Theorem 5, but the page warns that comments are user contributions and are not proof verification.

GCL's current state

The source-audit issue is MATH-PROGRAMME #1648, assignment ERDOS-CATALOGUE-0378-S01. It is a direct-editorial, cooperative task. At the zero-context preflight it was open, labelled available, had no comments, and had no existing RESULT/1; the original SOURCE RESULT/1 citation is authenticated original RESULT/1.

The frozen catalogue source is teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry number: "378", Git blob 4e60263a80af6207aca494d2e1388e44fa372889. It reports proved, with informal and catalogue updates dated 2025-08-31, formal_status: unformalized, and formalized: no. The live page has later editorial metadata, including its 2025-10-28 page-edit date, but agrees that the Granville–Ramaré paper resolves the question.

The maintained GCL registry classifies #378 as OUTSIDE_STRICT_OPEN_TRIAGE, with no protected FormalConjectures source. This is a routing and evidence classification, not a mathematical certification. The protected V2 ledger alone decides accepted documentary coverage; this article does not decide admission.

What remains

The main mathematical question is externally resolved by the cited Theorem 5, but several documentary and formal tasks remain distinct. The complete proof should be read and normalized against the original statement, especially the convention that the two endpoint coefficients are included in the paper's \(2m+2\) count. A later formalization would also need a precise definition of squarefree natural numbers, binomial coefficients, and asymptotic density, followed by a proof of the analytic theorem; none of that is supplied here.

The bounded successor task is a source-to-interface audit: transcribe Theorem 5 and the preceding definition of \(\eta_m\) into a small machine-readable record, then verify the endpoint-count bridge and reproduce the \(n=10\) calculation. Acceptance would require matching the printed theorem and the exact internal/full-row equivalence. Falsification would be a source passage using a different row convention, a counterexample to the stated finite calculation, or a mismatch in the density index. Stop after the theorem text, page reference, normalization, and finite check are locked; do not begin an exhaustive Lean build.

Sources and claim boundaries

The paper's theorem, catalogue status, live-page commentary, finite arithmetic, and any future Lean declaration are different evidence classes. This audit reports the externally published theorem and its normalization, but supplies no GCL mathematical certification, no verified Lean proof, and no unsupported claim about formal availability.

Catalogue and evidence provenance

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