Erdős Problem #392
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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 a positive integer \(n\), look at the number \(n! = 1\cdot2\cdot\ldots\cdot n\). We may split it into a product of positive integer factors, all no larger than \(n^2\). Let \(A(n)\) be the smallest possible number of factors. Reordering factors never changes a product, so we may write them in nondecreasing order:
Erdős and Graham ask whether, as \(n\) grows, the optimal number of factors is
The leading term has a simple explanation: a factor is at most \(n^2\), while \(n!\) has logarithm approximately \(n\log n-n\). Thus one needs about half as many factors as the analogous problem with factors bounded by \(n\). The negative correction measures the saving obtained by packing factors efficiently rather than using \(n\) repeatedly.
The original source uses a slightly broader parameterization: it first allows \(a_k\leq n f(n)\) and then asks for the case \(f(n)=n\). That is exactly the \(n^2\) bound above. The source passage does not impose an order on the factors; the displayed monotone version is an equivalent normalization.
A small example
Take \(n=5\). Then \(5!=120\) and the permitted factor bound is \(5^2=25\). The exact factorization
has two ordered factors, both at most \(25\). One factor cannot work, because the only one-factor representation is \(120\) itself, which exceeds \(25\). Therefore the finite value is exactly \(A(5)=2\).
This calculation was checked with integer arithmetic: \(5!=120\), \(5\cdot24=120\), \(5\leq24\leq25\), and \(120>25\). It illustrates the bounded-factor optimization and verifies one instance of the definition. It says nothing about the asymptotic formula: a statement involving \(o(n/\log n)\) concerns the behavior of all sufficiently large \(n\), not a short table of values.
What is known
The primary historical source is P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, L’Enseignement Mathématique, Monographie 28 (1980). In the scanned copy, the relevant discussion is on printed pages 75–76: page 75 records the already-known \(a_k\leq n\) estimate, and page 76 asks whether relaxing the limit to \(n^2\) gives the displayed half-sized asymptotic. The source is available as a scanned copy; the retrieved PDF has SHA-256 0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3.
The maintained Erdős Problems entry, accessed 2026-10-13, reproduces the normalized question, cites [ErGr80,p.75], and reports PROVED (LEAN). Its linked discussion records a constructive route: first build a balanced factorization with factors at most \(n\) and about \(n-n/\log n\) terms, then pair consecutive factors. Pairing preserves the product and changes a factor bound of \(n\) into one of \(n^2\), while halving the count up to a negligible rounding error. The matching lower scale follows from the size bound and Stirling’s estimate. These are source-reported mathematical claims here, not a new certification by this article.
A relevant modern source is Alexeev, Conway, Rosenfeld, Sutherland, Tao, Uhr, and Ventullo, “Decomposing a factorial into large factors,” arXiv:2503.20170, revised version 4 dated 2026-04-03. Its abstract treats a closely related factorial factorization problem and states that its methods answer a question of Erdős and Graham. The current PNT+ source file contains Solution_1 and Solution_2, including the pairing interface with bound \(n^2\), at repository commit c39a751132c88b6e8080b74c74023fd95b3d8be0 and Git blob 61ffe123a7c8e292532d60d89faa666ce6484d6d. Text inspection found no sorry in that file; no Lean build or replay was performed.
GCL's current state
Issue #1662, assignment ERDOS-CATALOGUE-0392-S01, is the source-audit record. It labels the protected triage class OUTSIDE_STRICT_OPEN_TRIAGE; that is a routing and evidence classification, not a mathematical verdict. The issue’s frozen catalogue packet points to teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, file blob 4e60263a80af6207aca494d2e1388e44fa372889. At that revision, problem 392 is marked informal proved, formal status Lean, and formalized yes, with the status update dated 2026-02-22.
The live catalogue repository revision read during this audit is commit 76848eddd25687dfc69bb26bec740c35c4a9c6b4; its data/problems.yaml blob is 97ae243a7fc056bb9c6413ce665b575eadd27ff3. The entry retains the same status and dates, so no catalogue-status drift was observed, although the live file is not byte-identical to the frozen file. The live web page is the maintained presentation, while the frozen commit remains the issue-specific source lock.
The pinned FormalConjectures file exists at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, Git blob 331ce7651ba5e058002649c018beccaeddb0956f, and states the main theorem and variants with the expected quantifier shape. Its theorem bodies are by sorry, however. It is therefore useful evidence about a formal interface and normalization, not evidence of a checked proof.
What remains
The key remaining documentary task is to preserve the distinction between three layers: the 1980 primary statement, the maintained site’s solved-status report, and the external Lean source that appears to implement a proof. A specialist mathematical review would need to compare every hypothesis and asymptotic quantifier in the external development with the primary statement, inspect the lower-bound argument as well as the pairing upper bound, and run the exact declared Lean environment if certification is sought. This audit does not supply that certification.
The formal file also encodes the minimum through a set of values t + 1 for functions on Fin (t + 1), with monotonicity and a last-factor bound. For positive \(n\), the product equation rules out zero factors, and sorting supplies the monotonicity convention. Those equivalences should still be checked in a dedicated semantic review rather than inferred from the catalogue label. The original SOURCE RESULT/1 citation is authenticated original RESULT/1.
Sources and claim boundaries
This account uses the original issue, the frozen catalogue commit and blob named above, the live catalogue commit and blob, the 1980 primary source, the maintained problem page, the pinned formal statement, and the PNT+ development. The arXiv paper is a relevant modern primary research source, but its stated factorial problem should not be silently identified with every detail of #392.
The finite calculation above is independently reproducible exact arithmetic, not an asymptotic proof. The maintained site and catalogue report a solved status; the formal-conjecture theorem is sorry-dependent; and the PNT+ file was inspected but not replayed here. No claim of GCL mathematical certification, publication authority, priority, or novelty is made. V2 ledger evidence alone decides accepted compendium coverage.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1662 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- 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.