Erdős Problem #408
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, iterated functions.
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
Start with Euler's totient function \(\phi(n)\), the number of integers from \(1\) through \(n\) that are coprime to \(n\). Apply it repeatedly: \(\phi_1(n)=\phi(n)\) and \(\phi_k(n)=\phi(\phi_{k-1}(n))\). Since the values decrease until they reach \(1\), define
Erdős Problem 408 asks three related questions. Does the normalized quantity \(f(n)/\log n\) have a limiting distribution as \(n\) ranges over the positive integers? Is it concentrated near one constant for almost all \(n\), in the natural-density sense? And, after about \(\log\log n\) iterations, how large can the largest prime factor of \(\phi_k(n)\) still be?
The first question means asking for a nondecreasing function \(F\) whose values are the limiting densities of the sets where \(f(n)/\log n\leq c\). The precise modern formulation uses continuity points of \(F\), because a distribution function need not have a density value that behaves continuously at a jump. The second asks whether some constant \(\alpha\) satisfies \(|f(n)/\log n-\alpha|<\varepsilon\) for a density-one set of \(n\), for every \(\varepsilon>0\). The third is deliberately less formal: “\(k=\log\log n\)” is not an integer for every \(n\), and the intended asymptotic comparison needs a convention.
A small example
Here is an exact calculation that can be checked using only the totient formula. For \(n=72\),
Indeed, factoring \(72=2^3\cdot3^2\) gives \(\phi(72)=72(1-1/2)(1-1/3)=24\); then \(\phi(24)=8\), \(\phi(8)=4\), \(\phi(4)=2\), and \(\phi(2)=1\). Thus the exact finite certificate is \(f(72)=5\). The same calculation gives \(f(32)=5\) from \(32\mapsto16\mapsto8\mapsto4\mapsto2\mapsto1\).
More generally, \(\phi(2^j)=2^{j-1}\) for \(j\geq1\), so the chain from \(2^j\) reaches \(1\) after exactly \(j\) steps. This is a useful warning about informal logarithmic bounds: any asserted strict upper bound of the form \(f(n)<\log_2 n\) fails on powers of two under the convention \(k\geq1\). The finite calculation verifies neither a limiting distribution nor an “almost always” statement. It only checks the definition and exposes an endpoint normalization that matters in later theorem statements.
What is known
Pillai's iterates paper gives, for every \(n\geq2\), the corrected bounds recorded by the formal source,
The maintained problem page instead displays the shorter asymptotic-looking inequalities \(\log_3 n<f(n)<\log_2 n\) and its bibliography labels Pillai as pages 832–836. The primary iterates reference is identified elsewhere, and in the formal source, as Bull. Amer. Math. Soc. 35 (1929), pages 837–841. The discrepancy should remain visible until a coordinator reconciles the catalogue metadata against the paper.
Erdős, Granville, Pomerance, and Spiro's primary paper On the normal behavior of the iterates of some arithmetic functions (1990) gives the central positive evidence. Its Theorem 2.2, printed page 171, says that the iteration length has normal order \(\alpha\log n\) for some \(\alpha>0\), under the paper's strong hypothesis \(B_\varepsilon\), a form of the Elliott–Halberstam conjecture. This conditional result supports the second question and, in the usual interpretation, the first as well; it is not an unconditional solution.
For the largest-prime-factor direction, Ford, Konyagin, and Luca's primary paper Prime chains and Pratt trees, Theorem 5, proves that for every \(\varepsilon,\delta>0\) there is an integer \(k\) such that, for all sufficiently large \(x\), at least \((1-\delta)x\) integers \(n\leq x\) satisfy \(P^+(\phi_k(n))\leq x^\varepsilon\). This is a genuine unconditional result, but its quantifiers do not directly settle the particular choice \(k=\log\log n\). The maintained page's “likely true” sentence is therefore best described as an open extrapolation, not as a theorem supplied by that paper.
GCL's current state
The original issue #1678 freezes the catalogue evidence at teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, entry 408, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. That entry says open, with informal and overall status last updated 2025-08-31, formal status unformalized, and statement formalized: no. It also assigns number-theory and iterated-function topics and no prize metadata.
The live page, retrieved 2026-10-13, says it was last edited 30 September 2025 and now links FormalConjectures/ErdosProblems/408.lean. The file was added upstream in commit bfd33d9d6f4ed21ee50a6fba6d581608c4ac9df1; its blob is bb413365e3f84f792725123638e85722235e960c. It formalizes the first two questions, Pillai's bounds, and the Ford–Konyagin–Luca interface, but the research theorem bodies are by sorry. The admitted GCL provider snapshot FC-GDM-85F86371 is an older read-only metadata snapshot and contains no admitted statement file for this problem. These are dated source surfaces, not a contradiction to be silently erased.
Accordingly, the V2 ledger alone decides accepted coverage. This article records a source audit, not GCL mathematical certification, Lean replay, publication authority, or a decision that Problem 408 is solved.
What remains
A bounded successor should first reconcile the four interfaces: the frozen catalogue entry, the live page, the EGPS90 scan, and the exact FormalConjectures file. Its input is those pinned bytes and the cited primary papers. Its target is a clause-by-clause table giving the quantifiers, density convention, hypotheses, theorem/page locations, and status date for each of the three questions.
Acceptance should require that every conditional word in the EGPS90 statement is retained, that the Pillai page range and endpoint convention are resolved or explicitly left unresolved, and that the third question is not replaced by the weaker theorem for fixed \(k\) proved by Ford–Konyagin–Luca. Falsification is immediate if the primary scan contradicts the reported theorem/page or if the formal statement changes a quantifier or ambient domain. Stop when the table is complete or when the required primary page cannot be read; do not spend this bounded task on a full Lean build or a new asymptotic proof.
Sources and claim boundaries
The source packet and assignment are in issue #1678. The frozen catalogue is the pinned problems.yaml, entry 408, blob 4e60263a80af6207aca494d2e1388e44fa372889. The maintained page is erdosproblems.com/408. The primary EGPS90 paper is available as the authors' PDF, retrieved here with SHA-256 7e95622ae683439cb31ef12949ab35a744cf3e1d32bc14d4d28d4b6deaff81fd; the FKL10 primary source is arXiv:0904.0473, whose downloaded PDF had SHA-256 4541e110be591685a05ed0f63ba7055ccbcc93c0e11503a3ba7e1926fc4c2e2e.
The formal source is the exact 408.lean commit. It is a theorem interface with sorry-filled proof obligations, not an independently checked proof. The original SOURCE RESULT/1 citation is authenticated original RESULT/1. No claim here relies on that future citation, and no claim of mathematical certification is supplied.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1678 — 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.