An asymptotic formula for the number of totients

The explanation

Take the number 9 and list the numbers from 1 to 9 that share no factor with it. They are 1, 2, 4, 5, 7 and 8. There are six, so the totient of 9 is 6. Euler's totient of a whole number counts exactly these numbers. Different starting numbers can give the same answer. The totients of 7, 9, 14 and 18 are all 6. Some numbers are never an answer. Up to 30, the totient values are 1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 28, 30. So 14 and 26 are skipped.

How many numbers up to some limit x are totient values? Call that count V(x). Up to 100 there are 38. Up to 1,000 there are 291. Up to one million there are 180,184. The share keeps falling, from 38% to 29% to about 18%. Pillai proved in 1929 that this share tends to zero.

Finding the exact size of V(x) took a long chain of work. A prime p has totient p − 1. So V(x) is at least about the count of primes up to x. Erdős, then Erdős and Hall, then Pomerance tightened the bounds. In 1988 Maier and Pomerance found the leading constant, 0.8178146…, in a rough formula. In 1998 Ford went further. His formula was right up to a bounded factor. That factor always stays between two fixed positive numbers. Nobody knew what it actually was.

That gap hid a simple question. If you double the limit x, does the count of totient values double too? Erdős and Hall asked this in 1976, for every fixed stretch factor c above 1. My own counts lean that way, slowly. Going from 1,000 to 2,000 multiplies the count by about 1.87. Going from 10,000 to 20,000 gives about 1.89. Going from 500,000 to one million gives about 1.94. Numbers like these settle nothing. Ford proved that the stretched range always adds a comparable number of new values. He could not pin down the limiting ratio.

This paper proves an asymptotic formula for V(x)Source 1. Asymptotic means the ratio of the two sides tends to 1 as x grows. The formula is Ford's scale times a coefficient. The coefficient depends on x only through a number between 0 and 1, called the phaseSource 2. It is built from finite sums over primes and whole numbers, followed by a limitSource 3. It always stays between two fixed positive bounds. From this, the paper proves that V(cx)/V(x) tends to c for every fixed c above 0Source 1. That answers Erdős and Hall's question with a yes.

The hard part is collisions. Counting numbers with a given pattern of prime factors is the standard tool. But that counts starting numbers, not distinct values. Since 7, 9, 14 and 18 all give 6, counting starting numbers overcounts the value 6. The paper lists a typical number's primes from largest to smallestSource 4. The large primes can be counted smoothly, like measuring a volume. The last few primes stay small, and different choices of them may give the same totient. The paper keeps these small tails exactly and counts each resulting value once. That bookkeeping produces the coefficient. The paper also shows that collisions among the long front parts are rare in totalSource 5.

The formula has limits a reader might miss. The coefficient is a limit of finite computations, not a single closed number. The paper does not claim the coefficient changes smoothly with the phaseSource 6. A companion result counts values whose smallest starting number lies in a given range. It gives positive counts for two such ranges and leaves the others openSource 7. An older Erdős question, whether that smallest starting number can be arbitrarily large relative to its value, remains unresolved hereSource 8.

How sure is this? A computer proof checker called Lean has checked a formal version of the main result. It covers the explicit formula, the doubling result for every fixed c, and the companion counts. No specialists have published a review yet.

What it doesn't show. This does not give the coefficient as one closed number or say how close the formula is at a given x.