Skip to content

Erdős Problem #400

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

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 an integer parameter satisfying \(k\geq 2\), look at tuples of length \(k\) made from nonnegative integers whose factorials multiply to a divisor of \(n!\). The quantity

\[ g_k(n)=\max\{a_1+\cdots+a_k-n:a_1!\cdots a_k!\mid n!\} \]

measures how much larger the sum of the factorial indices can be than \(n\), while the factorial divisibility constraint still holds. Erdős Problem 400 asks two typical-size questions. First, does the sum of \(g_k(n)\) up to \(x\) have an asymptotic constant \(c_k\)?

\[ \sum_{n\leq x}g_k(n)\sim c_kx\log x. \]

Second, for almost every \(n<x\), does \(g_k(n)\) itself behave like \(c_k\log x\), up to a smaller-order error? The same symbol \(c_k\) is used in both questions in the original wording. The problem is recorded in Erdős and Graham’s 1980 monograph, p. 77, and in the maintained Erdős Problems entry.

The quantifiers matter: \(k\) is fixed when discussing the growth in \(n\), and the issue packet asks that this be checked rather than inferred from a numerical experiment. The source says “integers”; factorials conventionally force nonnegative indices, but the exact ambient domain should remain explicit.

A small example

Take \(n=5\) and \(k=2\). Since \(5!=120\) and \(6!>120\), any admissible index is in \(\{0,1,2,3,4,5\}\). Exact enumeration gives the feasible pairs with nonnegative excess as

\[ (0,5),(1,4),(1,5),(2,3),(3,2),(4,1),(5,0),(5,1). \]

Their excesses \(a+b-5\) are respectively \(0,0,1,0,0,0,0,1\). For example, \((1,5)\) and \((5,1)\) work because \(1!5!=120\mid120\), while \((4,2)\) fails because \(4!2!=48\) does not divide \(120\). Thus the exact finite value is \(g_2(5)=1\).

This calculation is reproducible using only integer factorials and divisibility; it checks the definition and the boundary convention, not the asymptotics. A finite maximum cannot establish the existence of \(c_k\), a density-one statement, or even the eventual order of magnitude.

What is known

The maintained page attributes the elementary pointwise estimate \(g_k(n)\ll_k\log n\) to Erdős and Graham and says that the best possible constant was unknown in the cited source. The original reference is Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory, Monographie 28, 1980, p. 77; the live page identifies it as [ErGr80,p.77]. A bibliographic record and the author’s publication list are also available from Ron Graham’s publications page.

A relevant primary result is Carl Pomerance’s “Remarks on the Middle Binomial Coefficient”, Integers 26 (2026), article A47, Theorem 1 on p. 1. For every fixed \(\eta<1/\log 4\), it proves that for a density-one set of \(m\), every positive integer \(r\leq\eta\log m\) satisfies

\[ \frac{(m+r)!}{m!}\mid\binom{2m}{m}. \]

Consequently, for the Problem 400 quantity, choose \(n=2m\), indices \(m+r\), \(m\), and \(k-2\) copies of \(1\). This gives \(g_k(2m)\geq r+k-2\) on that density-one set. It is a real lower-bound interface, but it does not identify the asymptotic constant or prove either question. The PDF retrieved for this audit has SHA-256 b28e39128d5fe30f0c54bdde172ecff621ac74eb97a6b420186c1077f7be7724.

The live discussion also contains a 2026 preprint report by Eric Li claiming stronger bounds. It is useful evidence to locate, but this article does not independently certify that report or any claimed resolution.

The distinction between a lower bound and an asymptotic is especially important here. Pomerance’s theorem supplies many admissible tuples and therefore forces \(g_k(n)\) to be large on a controlled set of inputs. It says nothing by itself about whether other admissible tuples are larger, whether the normalized values concentrate, or whether the summatory ratio converges. Even a sharp pointwise upper bound would leave the existence and value of a limiting average unresolved unless the two bounds meet at the right scale.

GCL's current state

The frozen catalogue record is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, blob 4e60263a80af6207aca494d2e1388e44fa372889. Its entry marks the informal status open, with last update 2025-08-31, formal status unformalized, and statement-formalized metadata updated 2026-03-19. The live page, accessed 2026-10-13, retains the same two questions, links [ErGr80,p.77], reports zero proof expositions and zero proof claims, and links a formal statement; it also has eleven discussion comments. These are dated source observations, not a new mathematical disposition.

The pinned FormalConjectures file is at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob 56af919a30b4ed2f4b3c0baaa05b8736d1808c77. It defines g on Nat, uses Fin k → Nat, and uses natural-number subtraction inside a supremum. Parts (i) and (ii) have answer(sorry) bodies; the upper-bound variant is labelled solved but also has sorry. The test theorem for positivity contains proof script, but is not a proof of the two open parts.

What remains

The smallest useful successor is to reconcile the exact source semantics before attempting a theorem: positive versus nonnegative indices, ordinary integer subtraction versus truncated natural subtraction, and the formal ∀ᵉ (k ≥ 2) binder versus the prose “for any \(k\geq2\)”. Then record Pomerance’s divisibility theorem as a conditional lower-bound lemma for fixed \(k\), and separately test the finite values of \(g_2(n)\) by exact prime-valuation arithmetic. Acceptance should require the stated hypotheses, exact divisibility, and a falsifiable comparison with the formal g; a failed comparison stops the task and opens a semantic correction, not a claim about the original problem.

No finite computation, sorry-bearing Lean declaration, live forum comment, or lower-bound construction decides the limiting constant. The V2 ledger alone decides accepted coverage; documentary prose does not certify mathematics.

Sources and claim boundaries

The source boundary is original issue #1670, whose requested original SOURCE RESULT/1 citation is authenticated original RESULT/1. The frozen catalogue and FormalConjectures commit/blob identities above are exact. The primary book citation is historical source evidence; its full page scan was not independently hash-locked in this worktree. Pomerance’s paper is a readable primary theorem source and is hash-locked above. Li’s preprint and the live forum comments are unverified external reports here. No Lean replay, mathematical certification, publication decision, or accepted-coverage decision is supplied by this article.

Catalogue and evidence provenance

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