Skip to content

Erdős Problem #684

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, primes, 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

For a binomial coefficient \(\binom nk\), separate its prime factors into those at most \(k\) and those larger than \(k\). Multiply the complete prime powers in the first group to obtain \(u(n,k)\). How far must the index \(k\) grow before this small-prime part becomes bigger than \(n^2\)? Erdős #684 defines \(f(n)\) as the least such \(k\) and asks for its growth. This is an asymptotic number-theory question; small \(n\) need not have any qualifying \(k\).

A small example

Take \(n=10,k=7\). Since \(\binom{10}{7}=120=2^3\cdot3\cdot5\), every prime in the coefficient is at most \(7\), so \(u(10,7)=120>10^2=100\). Checking \(k<7\) shows \(f(10)=7\). But at \(n=20\), exact evaluation for every \(0\leq k\leq20\) gives \(\max_k u(20,k)=240<20^2=400\). There is no value of \(f(20)\) under the literal finite \(n\) definition. This is not a counterexample to theorems that assert a bound only for sufficiently large \(n\); it is a necessary convention for an honest explanation.

What is known

For each prime \(p\), the exponent with which it divides the binomial coefficient is exactly \(v_p\!\left(\binom nk\right)=\sum_{j\geq1}(\lfloor n/p^j\rfloor-\lfloor k/p^j\rfloor-\lfloor(n-k)/p^j\rfloor)\) (Legendre's formula). Thus \(u(n,k)=\prod_{p\leq k}p^{v_p(\binom nk)}\), with all powers included. The maintained catalogue cites Mahler's classical result implying \(f(n)\to\infty\), though its proof is ineffective. A major later improvement appears in Alexeev, Putterman, Sawhney, Sellke and Valiant, Short proofs in combinatorics and number theory, Section 2, Theorem 2.1. The authors establish for sufficiently large \(n\) a polylogarithmic upper bound, reported by the maintained catalogue as \(f(n)\ll(\log n)^2\), and an infinite sequence on which \(f(n)\geq(1/2-o(1))\log n\). The paper explicitly credits its proofs to an internal OpenAI model. Here the mathematical source remains the named author paper, not this editorial draft or any claim of GCL originality. The gap between logarithmic and squared-logarithmic growth remains of interest.

GCL's current state

The authenticated original RESULT/1 source return retains its original BOUNDED_TASK_DESIGNED disposition and mathematical qualifications. This source-grounded explanation is editorially reviewed through the exact-hash EC-BULK-005-R8 protected transaction, effective on protected merge. It is not a fresh proof of the attributed mathematical theorem or an internally replayed Lean certificate.

Critical source-scope distinction: u(n,k) full small-prime powers; f(n) undefined at some small n; distinguish reported model-assisted bounds from verified proof.

What remains

A bounded source-replay task is to inspect the full published proof of the squared-log upper bound, verify each approximation and quantifier, and reconcile the older power-law bounds with the stronger 2026 theorem. Adopt either a partial function \(f(n)\) for finite \(n\) or an explicit sufficiently-large \(n\) domain before formalizing the result. Exact prime valuations can check finite examples but cannot establish uniform asymptotic bounds. Complete critical editorial review, protected publication, deployed MathJax inspection and separate V2 admission remain outstanding.

Sources and claim boundaries

Maintained Erdős #684; Alexeev et al., Short proofs in combinatorics and number theory, author arXiv HTML Section 2/Theorem 2.1 directly inspected; original issue source return. Original Erdős 1979 primary passage and entire theorem proof not independently replayed. The primary theorem proof and formal certificate remain external.

Editorial provenance: protected R8 source-critical review. Original issue-level source and research-proof holds remain. Status: REVIEWED explanatory article; full historical theorem proofs, unresolved conjectures and external Lean proofs are not newly certified.

Catalogue and evidence provenance

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