An asymptotic formula for the number of totients

1 · The essentials

Euler’s totient function assigns a number to each positive integer. The question here is how many different numbers can occur as its outputs without exceeding a given cutoff. An output that occurs repeatedly is counted only once. The manuscript presents a formula describing this count with increasingly good relative accuracy as the cutoff grows. It also shows that multiplying the cutoff by a fixed positive constant multiplies the count of distinct outputs by that same constant in the limit. This last property answers a question of Erdős and Hall. The main result has a Lean formalization, although the supplied text does not specify its exact scope.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine listing the different prices in a catalogue, ignoring repetitions, and counting those within your budget. Here, prices are replaced by outputs of Euler’s totient function, and the question is how the number of accessible outputs changes as the budget grows.

Why it matters

The result gives more than a rough scale: it supplies an explicit asymptotic equivalent for the number of distinct values. It also establishes a simple scaling rule despite the presence of a phase-dependent coefficient in the asymptotic description.

2 · Going further

Let $V (x)$ count the distinct values of Euler’s totient function that are at most $x$ . This counts outputs, rather than the integers to which the function is applied. The problem is to describe $V (x)$ precisely as $x \to \infty$ .

The manuscript presents an explicit asymptotic equivalent for $V (x)$ . According to the repository summary, this equivalent contains a positive bounded factor that depends on a phase. The abstract states that the coefficient is a uniform limit of functions defined from finite arithmetic data. This is the construction mechanism described in the source: convergent arithmetic approximations determine the coefficient. The full formula and the steps of the argument are not supplied.

The manuscript also shows that $V (c x) / V (x) \to c$ for every fixed constant $c > 0$ , as $x \to \infty$ . It describes this conclusion as answering a question of Erdős and Hall. Only one manuscript appears in the supplied material, so no relationship to companion manuscripts can be described.

Useful notions

Euler’s totient function
Counting distinct values
Limits and ratios
Asymptotic equivalents
Uniform convergence

What was known before / what is new

Before

The source states that Erdős and Hall had asked about the behavior of $V (c x) / V (x)$ for a fixed positive constant. It does not describe earlier estimates for $V (x)$ or any previously known partial results.

New

The manuscript presents an explicit asymptotic equivalent for $V (x)$ , with a coefficient constructed as a uniform limit from finite arithmetic data. The repository summary describes a positive bounded phase-dependent factor. The manuscript also shows the limit $V (c x) / V (x) \to c$ for every fixed $c > 0$ .

Limits and assumptions

The conclusions are asymptotic: they concern $x \to \infty$ , not an exact equality at a finite cutoff. In the scaling statement, $c$ must be positive and fixed; the source gives no statement for a factor varying with $x$ . It supplies neither the full formula, a rate of convergence, nor a definition of the phase. The main result has a Lean formalization, but the exact scope of that verification is not specified in the supplied material, so it should not be taken to cover every claim. No remaining open question is identified.

Mini glossary

Euler’s totient function: Euler’s totient function assigns to a positive integer the number of positive integers no greater than it that are relatively prime to it.
Distinct values: These are the different outputs of a function, each counted once even if several inputs produce it.
Asymptotic equivalent: An expression is an asymptotic equivalent of a quantity if their ratio tends to 1 in the limit under consideration.
Uniform convergence: Convergence is uniform when the difference between the approximating functions and their limit becomes small simultaneously throughout the domain under consideration.
Lean formalization: A Lean formalization expresses a statement and its reasoning in a language that allows a proof assistant to check them.

Keywords : Euler’s totient · Asymptotic equivalent · Scaling

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Gives an asymptotic equivalent for the number $V (x)$ of distinct totient values up to x, with a positive bounded phase-dependent factor determined by convergent arithmetic approximations. In particular, $V (c x) / V (x) \to c$ for every fixed c > 0, answering Erdős and Hall’s scaling question.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/024.md

Manuscripts in this family

★

An asymptotic formula for the number of totients

25/09/2026

To be verified

Let $V (x)$ count the distinct values of Euler's totient function up to x. We give an explicit asymptotic equivalent for $V (x)$ . Its coefficient is a uniform limit of functions defined from finite arithmetic data. We also prove that $V (c x) / V (x) \to c$ as $x \to \infty$ for every fixed c > 0, answering a question of Erdős and Hall.

PDF GitHub folder