Skip to content

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

\[ V'(x)=\#\{\phi(m):1\leq m\leq x\}. \]

It only sees inputs \(m\) up to \(x\). The second is the global count

\[ V(x)=\#\{v: v=\phi(m)\text{ for some }m\geq1\text{ and }v\leq x\}. \]

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

\[ 1,1,2,2,4,2,6,4,6,4. \]

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

\[ 1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,22,24,30 \]

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

\[ V(x)=\frac{x}{\log x}\exp\!\left(C(\log_3x-\log_4x)^2+D\log_3x-(D+\tfrac12-2C)\log_4x+O(1)\right), \]

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\),

\[ V(x)-V'(x)=\#\{v\leq x:v\text{ is a totient and }M(v)>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

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.

Back to catalogue · Compendium introduction