Erdős Problem #417
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.
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
Euler's totient function \(\phi(n)\) counts the integers from \(1\) through \(n\) that are coprime to \(n\). Problem 417 compares two ways of counting distinct totient values. The first count is
It only sees inputs \(m\) up to \(x\). The second is the global count
Thus \(V(x)\) counts all totient values lying below the height \(x\), even when their first preimage occurs above \(x\). The exact questions are whether \(V(x)/V'(x)\) has a limit as \(x\) tends to infinity, and whether that limit is greater than \(1\). The inequality \(V'(x)\leq V(x)\) is immediate from \(\phi(m)\leq m\): every value produced by an input \(m\leq x\) is itself at most \(x\).
A small example
At \(x=10\), direct evaluation of \(\phi(m)\) for \(1\leq m\leq10\) gives
The distinct values are \(\{1,2,4,6\}\), so \(V'(10)=4\). A separate exact enumeration of the global values at most \(10\) gives \(\{1,2,4,6,8,10\}\), so \(V(10)=6\) and the finite ratio is \(6/4=3/2\).
This second list can be checked without guessing a large search bound. From \(\phi(p^a)=p^{a-1}(p-1)\) and multiplicativity, the condition \(\phi(n)\leq10\) leaves exactly
as possible inputs; their totient values are all in the displayed set. I verified this list by exact greatest-common-divisor counting and by the prime-power formula. The calculation shows how values such as \(8\) and \(10\) can be globally present before their first displayed preimages \(15\) and \(11\), respectively. It says nothing about the eventual ratio: one finite \(x\) cannot establish existence, divergence, or a limiting value.
What is known
The maintained Erdős Problems page gives the original wording and says that Erdős's 1998 chapter suggests that the limit may be infinite. That is a useful historical report, not a proof of divergence. The catalogue links the earlier references [Er79e] and [ErGr80] as well as [Er98]. The full text of the 1998 chapter was not available in the bounded inquiry: the publisher page supplies bibliographic metadata and the chapter's page range, but not readable theorem text. Consequently, no page-specific assertion from that chapter is promoted here.
A readable primary source for the surrounding counting theory is Kevin Ford, The distribution of totients, Ramanujan Journal 2 (1998), 67–151. The author's revised copy states in Theorem 1 that the global count of totients \(V(x)\) has a detailed asymptotic of the form
with explicit constants. This is a substantive theorem about the global range count used here. It is not a theorem about the restricted-input count \(V'(x)\), and therefore does not by itself answer the ratio question. The live discussion also mentions Maier–Pomerance and other literature, but those comments are user-authored and explicitly not verified proof expositions; they remain reports rather than accepted evidence in this article.
An exact reformulation helps locate the missing comparison. Define the least preimage of a totient value by \(M(v)=\min\{m\geq1:\phi(m)=v\}\). Then, by separating global values according to whether their least preimage is at most \(x\),
Controlling these “late first appearances” is the central unresolved interface.
GCL's current state
The frozen catalogue evidence is teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry number: "417", Git blob 4e60263a80af6207aca494d2e1388e44fa372889. It records informal state open, last update 2025-08-31, formal-solution state unformalized, and statement-formalized metadata yes.
The live page was read on 2026-10-13. It still presents the problem as open, reports no proof exposition, and displays five discussion comments. Those comments include proposed constructions and a correction of a notation confusion between the two counting sequences; the site warns that comments are not verified for correctness. They do not change the source status.
The pinned formal provider is google-deepmind/formal-conjectures at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob 4511e83df6645cf13dd828a6aaa69ba75a85f042. Its two declarations use sorry; they express existence of a limit for the inverse fraction \(V'(x)/V(x)\) and the variant with limit less than \(1\). This is a formal statement interface, not a checked proof or a certification of equivalence with an external theorem.
What remains
The smallest documentary gap is a readable, page-pinned copy of the original Erdős source, followed by a line-by-line comparison of its definitions with the catalogue and formal declarations. The comparison must preserve whether “limit” permits divergence to infinity, the domain of \(x\), and whether the second question concerns a strict finite inequality or an extended-real interpretation.
Mathematically, a bounded successor could first verify the least-preimage identity above and compute \(M(v)\) for a fixed, explicitly recorded range, then test a stated finite hypothesis about late first appearances. A successful finite result would be a lemma or counterexample for that range only; a failed search would falsify only the tested finite conjecture. Any asymptotic conclusion still requires a proof controlling \(M(v)\) as \(x\) grows.
Sources and claim boundaries
- Original GCL issue #1687, assignment ERDOS-CATALOGUE-0417-S01; original SOURCE RESULT/1 citation: authenticated original RESULT/1.
- Erdős Problems #417, live page read 2026-10-13, with its discussion; the discussion is not proof-certified.
- Erdős catalogue frozen entry, commit and blob recorded above.
- Erdős, “Some of my new and almost new problems and results in combinatorial number theory,” in Number Theory (Eger, 1996), 1998, pp. 169–180, publisher record. The primary text was unavailable here, so its page-level claims remain unverified.
- Ford, “The distribution of totients,” Ramanujan Journal 2 (1998), 67–151, DOI and readable revised source, Theorem 1, PDF p. 2.
- Pinned formal statement, with the exact commit and blob above.
This article distinguishes established external theorems, unverified website comments, finite exact checks, and Lean declarations containing sorry. It supplies no mathematical certification; accepted coverage is decided only by the applicable V2 ledger and protected evidence.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1687 — 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.