The distribution of totients

Ford, Kevin¹

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

Electronic research announcements of the American Mathematical Society, Tome 04 (1998), pp. 27-34.

Résumé

This paper is an announcement of many new results concerning the set of totients, i.e. the set of values taken by Euler’s $\phi$-function. The main functions studied are $V(x)$, the number of totients not exceeding $x$, $A(m)$, the number of solutions of $\phi (x)=m$ (the “multiplicity” of $m$), and $V_{k}(x)$, the number of $m\le 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\ge 1$, if there is a totient with multiplicity $k$, then $V_{k}(x) \gg V(x)$. We further show that every multiplicity $k\ge 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 $\le x$ is $c\log \log x$, where $c\approx 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.

Détail

DOI : 10.1090/S1079-6762-98-00043-2

Bibliographie

[1] Erdös, P., Grünwald, T. On polynomials with only real roots Ann. of Math. (2) 1939 537 548

[2] Erdős, P. Some remarks on Euler’s 𝜑 function Acta Arith. 1958 10 19

[3] Erdős, P., Hall, R. R. On the values of Euler’s 𝜙-function Acta Arith. 1973 201 206

[4] Erdős, P., Hall, R. R. Distinct values of Euler’s 𝜙-function Mathematika 1976 1 3

[5] Erdős, Paul, Pomerance, Carl On the normal number of prime factors of 𝜙(𝑛) Rocky Mountain J. Math. 1985 343 352

[6] Hall, Richard R., Tenenbaum, Gérald Divisors 1988

[7] Birkhoff, Garrett, Ward, Morgan A characterization of Boolean algebras Ann. of Math. (2) 1939 609 610

[8] Maier, Helmut, Pomerance, Carl On the number of distinct values of Euler’s 𝜙-function Acta Arith. 1988 263 275

[9] Masai, P., Valette, A. A lower bound for a counterexample to Carmichael’s conjecture Boll. Un. Mat. Ital. A (6) 1982 313 316

[10] Pomerance, Carl On the distribution of the values of Euler’s function Acta Arith. 1986 63 70

[11] Arf, Cahit Untersuchungen über reinverzweigte Erweiterungen diskret bewerteter perfekter Körper J. Reine Angew. Math. 1939 1 44

[12] Schinzel, A. Remarks on the paper “Sur certaines hypothèses concernant les nombres premiers” Acta Arith. 1961/62 1 8

[13] Schinzel, A., Sierpiński, W. Sur certaines hypothèses concernant les nombres premiers Acta Arith. 1958

[14] Schlafly, Aaron, Wagon, Stan Carmichael’s conjecture on the Euler function is valid below 10^{10,000,000} Math. Comp. 1994 415 419