ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 4, Pages 27–34 (April 27, 1998) S 1079-6762(98)00043-2

THE DISTRIBUTION OF TOTIENTS

KEVIN FORD

(Communicated by Hugh Montgomery)

Abstract. This paper is an announcement of many new results concerning the set of totients, i.e. the set of values taken by Euler’s ϕ-function. The main functions studied are V (x), the number of totients not exceeding x, A(m), the number of solutions of ϕ(x) = m (the “multiplicity” of m), and V_{k}(x), the number of m ≤ x with A(m) = k. The first of the main results of the paper is a determination of the true order of V (x). It is also shown that for each k ≥ 1, if there is a totient with multiplicity k, then V_{k}(x) ≫ V (x). We further show that every multiplicity k ≥ 2 is possible, settling an old conjecture of Sierpiński. An older conjecture of Carmichael states that no totient has multiplicity 1. This remains an open problem, but some progress can be reported. In particular, the results stated above imply that if there is one counterexample, then a positive proportion of all totients are counterexamples. Determining the order of V (x) and V_{k}(x) also provides a description of the “normal” multiplicative structure of totients. This takes the form of bounds on the sizes of the prime factors of a pre-image of a typical totient. One corollary is that the normal number of prime factors of a totient ≤ x is c log log x, where c ≈ 2.186. Lastly, similar results are proved for the set of values taken by a general multiplicative arithmetic function, such as the sum of divisors function, whose behavior is similar to that of Euler’s function.

Let V denote the set of values taken by Euler’s ϕ-function (totients), i.e.

V = {1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 28, 30, … }.

Let

\begin{aligned}V(x) & = V ∩ [1, x], \\ V (x) & = |V(x)|, \\ A(m) & = |\{n : ϕ(n) = m\}|, \\ V_{k}(x) & = |\{m ≤ x : A(m) = k\}|. \end{aligned} (1)

We will refer to A(m) as the multiplicity of m. This paper summarizes recent work on the following questions.

1. What is the order of V (x)?

2. What is the order of V_{k}(x) when the multiplicity k is possible?

3. What multiplicities are possible?

4. What is the normal multiplicative structure of totients?

Received by the editors August 13, 1997. 1991 Mathematics Subject Classification. Primary 11A25, 11N64; Secondary 11N35. Key words and phrases. Euler’s function, totients, distributions, Carmichael’s conjecture,

Sierpiński’s conjecture.

\begin{matrix}c \\ ◯ \end{matrix}1998 American Mathematical Society

1. The Prime Number Theorem implies V (x) ≫ x/ log x, since ϕ(p) = p − 1 for primes p. Pillai [Pi] gave the first non-trivial bound on V (x), namely

V (x) ≪ \frac{x}{(log x)^{(log 2)/e}} .

Using sieve methods, Erdös [E1] improved this to

V (x) ≪_{ε} \frac{x}{(log x)^{1−ε}}

and later in [E2] showed that

V (x) ≫ \frac{x log_{2} x}{log x}.

Here and throughout this paper log_{k} x denotes the kth iterate of the logarithm. Further sharpening of the upper and lower bounds were found by Erdös and Hall [EH1], [EH2], Pomerance [P1], and Maier and Pomerance [MP]. The last result is

(2) V (x) = \frac{x}{log x} exp\{(C + o(1))(log_{3} x)^{2}\},

where C is a constant defined as follows. Let

F (x) = ∑_{n=1}^{∞} a_{n}x^{n}, a_{n} = (n + 1) log(n + 1) − n log n − 1.

Since a_{n} ∼ log n and a_{n} > 0, it follows that F (x) is defined and strictly increasing on [0, 1), F (0) = 0 and F (x) → ∞ as x → 1^{−}. Thus, there is a unique number ϱ such that

F (ϱ) = 1 (ϱ = 0.542598586098471021959 …)

and we set

C = \frac{1}{2| log ϱ|} = 0.81781464640083632231 ….

Our first major result is a determination of the true order of V (x). First define

\begin{aligned}D & = 2C(1 + log F′(ϱ) − log(2C)) − 3/2 \\ & = 2.17696874355941032173 …. \end{aligned}

Theorem 1 ([F1, Theorem 1]). We have

V (x) = \frac{x}{log x} exp\{C(log_{3} x − log_{4} x)^{2} + D log_{3} x − (D + 1/2 − 2C) log_{4} x + O(1)\}.

2. Erdös [E3] showed by sieve methods that if A(m) = k, then for most primes p, A(m(p − 1)) = k. If the multiplicity k is possible, it follows immediately that V_{k}(x) ≫ x/ log x. Applying the machinery used to prove Theorem 1, we show that for each k, either V_{k}(x) = 0 for all x, or V_{k}(x) is the same order as V (x).

Theorem 2 ([F1, Theorem 2]). If there is a number d with A(d) = k, then

V_{k}(x) ≫_{ε} d^{−1−ε}V (x) (x ≥ x_{0}(k)).

In other words, a positive fraction of totients have multiplicity k if the multiplicity k is possible. This suggests that the multiplicity of “most” totients is bounded.

Theorem 3 ([F1, Theorem 3]). We have

\frac{|\{m ∈ V(x) : A(m) ≥ N\}|}{V (x)} = ∑_{k≥N} \frac{V_{k}(x)}{V (x)} ≪ N^{−1} exp\{O(\sqrt{log N})\}.

3. In 1907, Carmichael [C1] announced that for every m, the equation ϕ(x) = m has either no solutions x or at least two solutions. In other words, no totient can have multiplicity 1. His proof of this assertion was flawed, however, but he did show in [C2] that no number m < 10^{37} has multiplicity 1, and conjectured that no such m exists (this is now known as Carmichael’s Conjecture). Improved lower bounds for a possible counterexample have been found by Klee [K], Masai and Valette [MV], and recently by Schlafly and Wagon [SW], who showed that a counterexample must exceed 10^{10,000,000}. Carmichael’s Conjecture, however, remains an open problem.

An immediate and important corollary of Theorems 1 and 2 is

Theorem 4 ([F1, Theorem 5]). We have

lim sup_{x→∞} \frac{V_{1}(x)}{V (x)} < 1.

Furthermore, Carmichael’s Conjecture is equivalent to the bound

lim inf_{x→∞} \frac{V_{1}(x)}{V (x)} = 0.

Although this is a long way from proving Carmichael’s Conjecture, Theorem 4 shows that the set of counterexamples cannot be a “thin” subset of V. Either there are no counterexamples or a positive fraction of totients are counterexamples.

The basis for the computations of lower bounds for a possible counterexample is a lemma of Carmichael, generalized by Klee, which allows one to show that if A(m) = 1, then x must be divisible by the squares of many primes. Using the method outlined in [SW] and modern computer hardware, we push the lower bound for a counterexample to an aesthetically pleasing bound.

Theorem 5 ([F1, Theorem 6]). If A(m) = 1, then m exceeds 10^{10^{10}}.

Aside from computations, the only other non-trivial result concerning the behavior of V_{1}(x) is the bound

lim inf_{x→∞} \frac{V_{1}(x)}{V (x)} ≤ \frac{1}{2},

proved by elementary methods in an unpublished note of Pomerance (see [P2]). A modification of his argument combined with the computations giving Theorem 5 yields

Theorem 6 ([F1, Theorem 7]). We have

lim inf_{x→∞} \frac{V_{1}(x)}{V (x)} ≤ 10^{−5,000,000,000}.

In the 1950’s, Sierpiński conjectured that all multiplicities k ≥ 2 are possible (see [S1] and [E3]), and in 1961, Schinzel [S2] deduced this conjecture from his wellknown Hypothesis H. Schinzel’s Hypothesis H [SS], a generalization of Dickson’s Prime k-tuples Conjecture [D], states that any set of polynomials F_{1}(n), …, F_{k}(n), subject to natural restrictions, are simultaneously prime for infinitely many n. Using the modern theory of “almost primes” (numbers with few prime factors) together with an iterative approach, we provide an unconditional proof of Sierpiński’s Conjecture.

Theorem 7 ([F2, Theorem 1]). For each k ≥ 2, there is a number d with A(d) = k.

Therefore, by Theorem 2, V_{k}(x) ≫ V (x) for k ≥ 2. The computations leading to Theorems 5 and 6 motivate another classification of totients. Let V (x; k) be the number of totients up to x, all of whose pre-images are divisible by k. A corollary of the proof of Theorem 2 is

Theorem 8 ([F1, Theorem 8]). If d is a totient, all of whose pre-images are divisible by k, then

V (x; k) ≫_{ε} d^{−1−ε}V (x).

Thus, for each k, either V (x; k) = 0 for all x or V (x; k) ≫_{k} V (x).

It is natural to ask for which k do there exist totients, all of whose pre-images are divisible by k. A short search reveals examples for each k ≤ 11 except k = 6 and k = 10. For k = 2, 4 and 8, take d = 2^{18} ·257, for k = 3 or 9 take d = 54 = 2·3^{3}, for k = 5 take d = 12500 = 4 · 5^{5}, for k = 7, take d = 294 = 6 · 7^{2} and for k = 11, take d = 110. It appears that there might not be any totient, all of whose pre-images are divisible by 6, but I cannot prove this.

Conjecture. There is no totient, all of whose pre-images are divisible by 6.

In particular, any totient with a unique pre-image must have that pre-image divisible by 6, so the non-existance of such numbers implies Carmichael’s Conjecture.

4. Establishing Theorems 1 and 2 requires a determination of what a “normal” totient looks like. This will initially take the form of a series of linear inequalities in the prime factors of a pre-image of a totient. An analysis of these inequalities reveals the normal sizes of the prime factors of a pre-image of a typical totient.

To state our results, we first define

L_{0} = L_{0}(x) = [2C(log_{3} x − log_{4} x)].

In a simplified form, we show that for all but o(V (x)) totients m ≤ x, every preimage n satisfies

log_{2} q_{i}(n) ∼ ϱ^{i}(1 − i/L_{0}) log_{2} x (0 ≤ i ≤ L_{0}), (3)

where q_{i}(n) denotes the (i + 1)st largest prime factor of n. Let ω(m) denote the number of distinct prime factors of m and let Ω(m) denote the number of prime factors of m counted with multiplicity. Then we have

Theorem 9 ([F1, Theorem 11]). Suppose g(x) is an increasing function of x satisfying g(x) = o(log_{3} x). For a given x, set L_{0} = L_{0}(x) and β_{i} = ϱ^{i}(1 − i/L_{0}) for 0 ≤ i ≤ L_{0}. Then the number of totients m ≤ x with a pre-image n not satisfying

(4) |\frac{log_{2} q_{i}(n)}{β_{i} log_{2} x} − 1| ≤ \sqrt{\frac{i}{L_{0}(L_{0} − i)}} log(L_{0} − i) log g(x) (1 ≤ i ≤ L_{0} − g(x))

and

L_{0}(x) − g(x) ≤ ω(n) ≤ Ω(n) ≤ L_{0}(x) + 30g(x)ϱ^{−g(x)}

is

≪ V (x) (e^{− log^{2} g(x)} + e^{− \frac{1}{4} log_{4} x log g(x)}) .

In essence, Theorem 9 says that the set of n ≤ x having about L_{0}(x) prime factors distributed according to (4) generates almost all totients. It also says that for most totients, all of its pre-images are “virtually” square-free. The function g(x) need not tend to infinity. Notice that the intervals in (4) are not only disjoint, but the gaps between them are rather large. In particular, this “discreteness phenomenon” means that for most totients m ≤ x, no pre-image n has any prime factors in the intervals

0.999 ≥ \frac{log_{2} p}{log_{2} x} ≥ 0.543, 0.542 ≥ \frac{log_{2} p}{log_{2} x} ≥ 0.295, etc.

This should be compared to the distribution of the prime factors of a normal integer n ≤ x (e.g. Theorem 12 of [HT]).

We also deduce the normal order of Ω(m) and ω(m) for totients m. If each prime q_{i}(n) of a pre-image n is “normal” and (3) holds, then Ω(m) should be about

(1 + ϱ + ϱ^{2} + ⋯) log_{2} x = \frac{log_{2} x}{1 − ϱ}.

Theorem 10 ([F1, Theorem 12]). Suppose ε = ε(x) satisfies 0 ≤ ε ≤ 0.8. Then

# \{m ∈ V(x) : |\frac{Ω(m)}{log_{2} x} − \frac{1}{1 − ϱ}| ≥ ε\} ≪ V (x) exp\{−Kε log_{3} x + O(\sqrt{ε log_{3} x})\},

where

K = \frac{2Ca_{1}(1 − ϱ)}{1 − (1 + a_{1})ϱ} = 1.166277 ….

Consequently, if g(x) → ∞ as slowly as desired, then almost all totients m ≤ x satisfy

|\frac{Ω(m)}{log_{2} x} − \frac{1}{1 − ϱ}| ≤ \frac{g(x)}{log_{3} x}.

Moreover, the theorem holds with Ω(m) replaced by ω(m).

Corollary 11 ([F1, Corollary 13]). If either h(m) = ω(m) or h(m) = Ω(m), then

∑_{m∈V(x)} h(m) = \frac{V (x) log_{2} x}{1 − ϱ} (1 + O (\frac{1}{log_{3} x})) .

By contrast, Erdös and Pomerance [EP] showed that the average of Ω(ϕ(n)), where the average is taken over all n ≤ x, is \frac{1}{2}(log_{2} x)^{2} + O((log_{2} x)^{3/2}).

The details of the proofs of these results are extremely complex and require very delicate estimating, but the central ideas are fairly simple. First, for most integers m, the prime divisors of m are “nicely distributed”, meaning the number of prime factors of m lying between a and b is about log_{2} b − log_{2} a. This is a more precise version of the classical result of Hardy and Ramanujan [HR] that most numbers m have about log_{2} m prime factors. Take an integer n with prime factorization p_{0}p_{1} ⋯, where for simplicity we assume n is square-free, and p_{0} > p_{1} > · · ·. By sieve methods it can be shown that for most primes p, the prime divisors of p − 1 have the same “nice” distribution. If p_{0}, p_{1}, … are such “normal” primes, it follows that ϕ(n) = (p_{0} − 1)(p_{1} − 1) ⋯ has about log_{2} n − log_{2} p_{1} prime factors in [p_{1}, n], about 2(log_{2} p_{1} − log_{2} p_{2}) prime factors in [p_{2}, p_{1}], and in general, ϕ(n) will have k(log_{2} p_{k−1} − log_{2} p_{k}) prime factors in [p_{k}, p_{k−1}]. That is, n has k times as many prime factors in the interval [p_{k}, p_{k−1}] as does a “normal” integer of its size. If n has many “large” prime divisors, then the prime factors of m = ϕ(n) will be much denser than normal, and the number, N_{1}, of such integers m will be “small”. On the other hand, the number, N_{2}, of integers n with relatively few “large” prime factors is also “small”. Our objective then is to precisely define these concepts of “large” and “small” so as to minimize N_{1} + N_{2}.

The argument in [MP] is based on the heuristic that a normal totient is generated from a number n satisfying

log_{2} q_{i}(n) ≈ ϱ^{i} log_{2} x (5)

for each i (compare with (3)). As an alternative to this heuristic, assuming all prime factors of a pre-image n of a totient are normal leads to consideration of a series of inequalities among the prime factors of n. Specifically, let x be large, x/2 < n ≤ x and let q_{0} ≥ q_{1} ≥ ⋯ denote the prime factors of n. Fix L and map n to the point (x_{1}, …, x_{L}), where x_{i} = log_{2} q_{i}/ log_{2} x if i < Ω(n), and q_{i} ≥ 3, x_{i} = 0 otherwise. Consider the following inequalities:

0 ≤ x_{L} ≤ ⋯ ≤ x_{1} ≤ 1,
a_{1}x_{1} + ⋯ + a_{L}x_{L} ≤ 1,
a_{1}x_{2} + ⋯ + a_{L−1}x_{L} ≤ x_{1},
a_{1}x_{3} + ⋯ + a_{L−2}x_{L} ≤ x_{2},
⋮
a_{1}x_{L−1} + a_{2}x_{L} ≤ x_{L−2}.

We show that such n generate “most” totients and then reduce the problem of counting such n to the problem of finding the volume of the region in ℝ^{L} defined by these inequalities, denoted S_{L}. What we show is essentially

(6) V (x) ≈ \frac{x}{log x} max_{L} Vol(S_{L})(log_{2} x)^{L}.

With the estimate

Vol(S_{L}) ≈ \frac{ϱ^{L(L+3)/2}}{L!} (F′(ϱ))^{L},

the maximum in (6) occurs at about L = L_{0}(x) and Theorem 1 follows. Careful analysis of these inequalities reveals that the bulk of S_{L} is concentrated near the point (β_{1}, …, β_{L}), where β_{i} = (1 − \frac{i}{L})ϱ^{i}. It follows that “most” of the integers n mapping into S_{L} satisfy (3). Thus, the heuristic (5) gives numbers n whose smaller prime factors are too large. In particular, with L = L_{0}(x), we have log_{2} p_{L−1} ≈ \frac{1}{L}ϱ^{L−1} log_{2} x ≈ 1, an important observation for determining the true order of V (x).

Lastly, most of these results may be easily extended to more general multiplicative arithmetic functions such as σ(n), the sum of divisors function. Defining analogous functions V_{f}, V_{f}(x), V_{f,k}(x) and A_{f}(m), we prove Theorem 12 ([F1, Theorem 14]). Suppose f : ℕ → ℕ is a multiplicative function satisfying

{f(p) − p : p prime} is a finite set not containing 0,

∑_{h≥16 h square-full} \frac{ε(h)}{f(h)} ≪ 1, ε(h) = exp\{log_{2} h(log_{3} h)^{20}\}.

Then the analogs of Theorems 1–3, 7 and 9–11 hold with f(n) replacing ϕ(n), with the exception of the dependence on d in Theorems 2 and 3, which may be different.

The possible set of multiplicities for each f, however, depends on the particular function, since the values of f(p^{k}) for k ≥ 2 play a more important role. In particular, the proof of Theorem 7 relies on the property that ϕ(p^{2}) = pϕ(p) for primes p. However, when f = σ, the analog of Theorem 7 has been proved ([FK, Theorem 1]) and the method extends to many other functions satisfying the hypotheses of Theorem 12 for which A_{f}(m) = 1 has a solution.

References

[C1] R. D. Carmichael, On Euler’s ϕ-function, Bull. Amer. Math. Soc. 13 (1907), 241–243.

[C2] , Note on Euler’s ϕ-function, Bull. Amer. Math. Soc. 28 (1922), 109–110.

[D] L. E. Dickson, A new extension of Dirichlet’s theorem on prime numbers, Messenger of Math. 33 (1904), 155–161.

[E1] P. Erdös, On the normal number of prime factors of p − 1 and some related problems concerning Euler’s ϕ-function, Quart. J. Math. Oxford (1935), 205–213.

[E2] , Some remarks on Euler’s ϕ-function and some related problems, Bull. Amer. Math. Soc. 51 (1945), 540–544. MR 7:49f

[E3] , Some remarks on Euler’s ϕ-function, Acta Arith. vol 4 (1958), 10–19. MR 22:1539 [EH1] P. Erdös and R. R. Hall, On the values of Euler’s ϕ-function, Acta Arith. 22 (1973),

201-206. MR 53:13143

[EH2] , Distinct values of Euler’s ϕ-function, Mathematika 23 (1976), 1–3. MR 54:2603 [EP] P. Erdös and C. Pomerance, On the normal number of prime factors of ϕ(n), Rocky

Mountain J. of Math. 15 (1985), 343–352. MR 87e:11112

[F1] K. Ford, The distribution of totients, The Ramanujan J. 2 (1998), no. 1-2 (to appear).

[F2] , The number of solutions of ϕ(x) = m, Annals of Math. (to appear).

[FK] K. Ford and S. Konyagin, On a conjecture of Sierpiński concerning the sum of divisors function, Proceedings of the International Number Theory Conference dedicated to Professor Andrzej Schinzel, Zakopane, Poland (to appear).

[HT] R. R. Hall and G. Tenenbaum, Divisors, Cambridge University Press, 1988. MR 90a:11107 [HR] G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number n,

Quart. J. Math. 48 (1917), 76–92.

[K] V. Klee, On a conjecture of Carmichael, Bull. Amer. Math. Soc. 53 (1947), 1183–1186. MR 9:269d

[MP] H. Maier and C. Pomerance, On the number of distinct values of Euler’s ϕ-function, Acta Arith. 49 (1988), 263–275. MR 89d:11083

[MV] P. Masai and A. Valette, A lower bound for a counterexample to Carmichael’s Conjecture, Boll. Un. Mat. Ital. A (6) 1 (1982), 313–316. MR 84b:10008

[Pi] S. Pillai, On some functions connected with ϕ(n), Bull. Amer. Math. Soc. 35 (1929), 832– 836.

[P1] C. Pomerance, On the distribution of the values of Euler’s function, Acta Arith. 47 (1986), 63–70. MR 88b:11060

[P2] , Problem 6671, Amer. Math. Monthly 98 (1991), 862.

[S1] A. Schinzel, Sur l’équation ϕ(x) = m, Elem. Math. 11 (1956), 75–78. MR 18:194c

[S2] , Remarks on the paper “Sur certaines hypothèses concernant les nombres premiers”, Acta Arith. 7 (1961/62), 1–8. MR 24:A70 [SS] A. Schinzel and W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers,

Acta Arith. 4 (1958), 185–208. MR 21:4936

[SW] A. Schlafly and S. Wagon, Carmichael’s conjecture on the Euler function is valid below 10^{10,000,000}, Math. Comp. 63 (1994), 415–419. MR 94i:11008

Department of Mathematics, University of Texas at Austin, Austin, TX 78712

   E-mail address: ford@math.utexas.edu