Skip to content

Erdős Problem #416

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(m)\) counts the integers from \(1\) through \(m\) that share no common factor with \(m\) other than \(1\). Its image is the set of totients. Let \(V(x)\) be the number of distinct totient values that are at most \(x\); equivalently, it counts the positive integers \(n\le x\) for which the equation \(\phi(m)=n\) has at least one solution \(m\).

Erdős Problem #416 asks two related questions. First, does

\[ \frac{V(2x)}{V(x)}\longrightarrow 2 \]

as \(x\) tends to infinity? Second, is there an asymptotic formula for \(V(x)\), meaning a formula whose ratio to \(V(x)\) tends to \(1\)? The first question would follow from a sufficiently regular asymptotic formula, but a good estimate up to a bounded multiplicative factor is not enough.

The distinction between distinct values and preimages matters. If many different \(m\) have the same value of \(\phi(m)\), they contribute only once to \(V(x)\). The problem is therefore about the shape of the image of \(\phi\), not about how many integers map into it.

A small example

The finite calculation behind the definition is concrete. For \(m=15\), the integers in \(\{1,\ldots,15\}\) coprime to \(15\) are

\[ 1,2,4,7,8,11,13,14, \]

so \(\phi(15)=8\). Thus \(8\) is counted by \(V(10)\). Exact evaluation also gives the witnesses \(\phi(1)=1\), \(\phi(3)=2\), \(\phi(5)=4\), \(\phi(7)=6\), \(\phi(15)=8\), and \(\phi(11)=10\).

As a reproducibility check, direct integer enumeration of \(1\le m\le200\), using \(\phi(m)=\#\{a:1\le a\le m,\gcd(a,m)=1\}\), returns the distinct values at most \(10\) as

\[ \{1,2,4,6,8,10\}. \]

This verifies a finite set of exact counts and witnesses; it does not by itself prove that no larger \(m\) supplies another value at most \(10\), and it says nothing about the limiting ratio. Finite enumeration can test implementations and small cases, but it cannot decide a statement quantified over all sufficiently large real \(x\).

What is known

The maintained Erdős Problems #416 page records the problem as open and says that it cannot be resolved by finite computation. It reports that Pillai proved \(V(x)=o(x)\) and that Erdős obtained \(V(x)=x(\log x)^{-1+o(1)}\). Those historical claims are also discussed in the primary literature cited below.

Maier and Pomerance proved a much sharper scale in On the number of distinct values of Euler's \(\phi\) function, Acta Arithmetica 49 (1988), 263–275. Their theorem, stated on p. 264, is

\[ V(x)=\frac{x}{\log x}\exp\!\left\{(C+o(1))(\log\log\log x)^2\right\}, \]

with an explicit positive constant \(C\). This determines the principal growth scale but leaves a substantial subleading factor unresolved.

Kevin Ford's primary paper, The distribution of totients, Ramanujan Journal 2 (1998), 67–151, gives a more precise result. Theorem 1 on p. 68, also available in the corrected arXiv version, states that

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

Here \(\log_j\) denotes the iterated logarithm applied \(j\) times, and Ford gives explicit constants \(C\) and \(D\). The theorem is a two-sided order statement because the exponent has an \(O(1)\) remainder. In the introduction, Ford explicitly notes that his method falls short of proving \(V(cx)\sim cV(x)\) for fixed \(c>1\); this includes the question with \(c=2\).

GCL's current state

The source packet is bound to original issue #1686, assignment ERDOS-CATALOGUE-0416-S01. The issue has no comments and no existing RESULT/1, so there is no issue-local proof return to summarize. Its pinned catalogue source is teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry number: "416", whose Git blob is 4e60263a80af6207aca494d2e1388e44fa372889. That snapshot records informal status open, last update 2025-08-31, formal status unformalized, and statement-formalized metadata yes.

The pinned FormalConjectures file is at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob 8ed39af482236b4182f8b945fce82e80965c6adc. It defines \(V\) using a finite interval up to the natural-number floor of a real input and formalizes the ratio limit, an unspecified asymptotic-formula interface, and several reported results. Every declaration ends with by sorry; these are formal statements, not checked proofs. The Ford declaration also asks for existential positive constants and a \(\Theta\) estimate, so it should not be read as a formal proof of Ford's exact constants or exact published formula.

The current live page was read on 13 October 2026. Its displayed last-edit date is 30 September 2025 and its prose agrees with the pinned snapshot. Direct readers differed in access response, so the live-page date and wording should be treated as an observed revision, not as a cryptographic source lock. The Programme's V2 ledger alone decides accepted coverage.

What remains

The central unresolved target is sharper than the already-known order of magnitude: either prove an asymptotic formula with a sufficiently controlled remainder to imply \(V(2x)/V(x)\to2\), or find a genuine obstruction to that ratio. A bounded-factor estimate, including Ford's theorem, does not decide it.

A bounded successor task should first normalize the analytic target. It can extract from Ford's Theorem 1 the exact constants, domains, and meaning of the \(O(1)\) term, then prove a conditional implication: a specified remainder bound on the exponent would imply the ratio limit. The acceptance test is symbolic and quantitative, with every uniformity assumption written explicitly. Falsification is a counterexample to that implication's hypotheses or a source mismatch. It should stop after the source comparison and implication check, without attempting a full analytic proof or a Lean build.

Sources and claim boundaries

The primary references are Maier and Pomerance (1988) and Ford (1998), with corrected arXiv text. The original problem URL is erdosproblems.com/416. The exact original SOURCE RESULT/1 citation is authenticated original RESULT/1.

This article reports external theorems, a finite exact check, pinned source identities, and a proposed research interface. It does not certify any theorem, convert sorry into a proof, decide the live status independently of the source ledger, or claim that the open ratio question has been solved. Editorial coverage and mathematical certification remain separate decisions.

Catalogue and evidence provenance

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