The distribution of totients
Author:
Kevin Ford
Journal:
Electron. Res. Announc. Amer. Math. Soc. 4 (1998), 2734
MSC (1991):
Primary 11A25, 11N64; Secondary 11N35
Published electronically:
April 27, 1998
MathSciNet review:
1617448
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
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 , the number of totients not exceeding , , the number of solutions of (the ``multiplicity'' of ), and , the number of with . The first of the main results of the paper is a determination of the true order of . It is also shown that for each , if there is a totient with multiplicity , then . We further show that every multiplicity is possible, settling an old conjecture of Sierpinski. 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 and 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 preimage of a typical totient. One corollary is that the normal number of prime factors of a totient is , where . 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.
 [C1]
R. D. Carmichael, On Euler's function, Bull. Amer. Math. Soc. 13 (1907), 241243.
 [C2]
, Note on Euler's function, Bull. Amer. Math. Soc. 28 (1922), 109110.
 [D]
L. E. Dickson, A new extension of Dirichlet's theorem on prime numbers, Messenger of Math. 33 (1904), 155161.
 [E1]
P. Erdös, On the normal number of prime factors of and some related problems concerning Euler's function, Quart. J. Math. Oxford (1935), 205213.
 [E2]
Paul
Erdös, Some remarks on Euler’s
𝜑function and some related problems, Bull. Amer. Math. Soc. 51 (1945), 540–544. MR 0012634
(7,49f), http://dx.doi.org/10.1090/S000299041945083906
 [E3]
P.
Erdős, Some remarks on Euler’s 𝜙
function, Acta Arith. 4 (1958), 10–19. MR 0110664
(22 #1539)
 [EH1]
P.
Erdős and R.
R. Hall, On the values of Euler’s 𝜑function,
Acta Arith. 22 (1973), 201–206. MR 0409388
(53 #13143)
 [EH2]
P.
Erdős and R.
R. Hall, Distinct values of Euler’s 𝜑function,
Mathematika 23 (1976), no. 1, 1–3. MR 0414502
(54 #2603)
 [EP]
Paul
Erdős and Carl
Pomerance, On the normal number of prime factors of
𝜑(𝑛), Rocky Mountain J. Math. 15
(1985), no. 2, 343–352. Number theory (Winnipeg, Man., 1983). MR 823246
(87e:11112), http://dx.doi.org/10.1216/RMJ1985152343
 [F1]
K. Ford, The distribution of totients, The Ramanujan J. 2 (1998), no. 12 (to appear).
 [F2]
, The number of solutions of , Annals of Math. (to appear).
 [FK]
K. Ford and S. Konyagin, On a conjecture of Sierpinski concerning the sum of divisors function, Proceedings of the International Number Theory Conference dedicated to Professor Andrzej Schinzel, Zakopane, Poland (to appear).
 [HT]
Richard
R. Hall and Gérald
Tenenbaum, Divisors, Cambridge Tracts in Mathematics,
vol. 90, Cambridge University Press, Cambridge, 1988. MR 964687
(90a:11107)
 [HR]
G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number , Quart. J. Math. 48 (1917), 7692.
 [K]
V.
L. Klee Jr., On a conjecture of
Carmichael, Bull. Amer. Math. Soc. 53 (1947), 1183–1186. MR 0022855
(9,269d), http://dx.doi.org/10.1090/S000299041947089400
 [MP]
Helmut
Maier and Carl
Pomerance, On the number of distinct values of Euler’s
𝜑function, Acta Arith. 49 (1988),
no. 3, 263–275. MR 932525
(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),
no. 2, 313–316 (English, with Italian summary). MR 663298
(84b:10008)
 [Pi]
S. Pillai, On some functions connected with , Bull. Amer. Math. Soc. 35 (1929), 832836.
 [P1]
Carl
Pomerance, On the distribution of the values of Euler’s
function, Acta Arith. 47 (1986), no. 1,
63–70. MR
866903 (88b:11060)
 [P2]
, Problem 6671, Amer. Math. Monthly 98 (1991), 862.
 [S1]
André
Schinzel, Sur l’équation
𝜑(𝑥)=𝑚, Elem. Math. 11
(1956), 75–78 (French). MR 0080114
(18,194c)
 [S2]
A.
Schinzel, Remarks on the paper “Sur certaines
hypothèses concernant les nombres premiers”, Acta Arith.
7 (1961/1962), 1–8. MR 0130203
(24 #A70)
 [SS]
A.
Schinzel and W.
Sierpiński, Sur certaines hypothèses concernant les
nombres premiers, Acta Arith. 4 (1958), 185–208; erratum
5 (1958), 259 (French). MR 0106202
(21 #4936)
 [SW]
Aaron
Schlafly and Stan
Wagon, Carmichael’s conjecture on the
Euler function is valid below 10^{10,000,000}, Math. Comp. 63 (1994), no. 207, 415–419. MR 1226815
(94i:11008), http://dx.doi.org/10.1090/S00255718199412268153
 [C1]
 R. D. Carmichael, On Euler's function, Bull. Amer. Math. Soc. 13 (1907), 241243.
 [C2]
 , Note on Euler's function, Bull. Amer. Math. Soc. 28 (1922), 109110.
 [D]
 L. E. Dickson, A new extension of Dirichlet's theorem on prime numbers, Messenger of Math. 33 (1904), 155161.
 [E1]
 P. Erdös, On the normal number of prime factors of and some related problems concerning Euler's function, Quart. J. Math. Oxford (1935), 205213.
 [E2]
 , Some remarks on Euler's function and some related problems, Bull. Amer. Math. Soc. 51 (1945), 540544. MR 7:49f
 [E3]
 , Some remarks on Euler's function, Acta Arith. vol 4 (1958), 1019. MR 22:1539
 [EH1]
 P. Erdös and R. R. Hall, On the values of Euler's function, Acta Arith. 22 (1973), 201206. MR 53:13143
 [EH2]
 , Distinct values of Euler's function, Mathematika 23 (1976), 13. MR 54:2603
 [EP]
 P. Erdös and C. Pomerance, On the normal number of prime factors of , Rocky Mountain J. of Math. 15 (1985), 343352. MR 87e:11112
 [F1]
 K. Ford, The distribution of totients, The Ramanujan J. 2 (1998), no. 12 (to appear).
 [F2]
 , The number of solutions of , Annals of Math. (to appear).
 [FK]
 K. Ford and S. Konyagin, On a conjecture of Sierpinski 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 , Quart. J. Math. 48 (1917), 7692.
 [K]
 V. Klee, On a conjecture of Carmichael, Bull. Amer. Math. Soc. 53 (1947), 11831186. MR 9:269d
 [MP]
 H. Maier and C. Pomerance, On the number of distinct values of Euler's function, Acta Arith. 49 (1988), 263275. 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), 313316. MR 84b:10008
 [Pi]
 S. Pillai, On some functions connected with , Bull. Amer. Math. Soc. 35 (1929), 832836.
 [P1]
 C. Pomerance, On the distribution of the values of Euler's function, Acta Arith. 47 (1986), 6370. MR 88b:11060
 [P2]
 , Problem 6671, Amer. Math. Monthly 98 (1991), 862.
 [S1]
 A. Schinzel, Sur l'équation , Elem. Math. 11 (1956), 7578. MR 18:194c
 [S2]
 , Remarks on the paper ``Sur certaines hypothèses concernant les nombres premiers'', Acta Arith. 7 (1961/62), 18. MR 24:A70
 [SS]
 A. Schinzel and W. Sierpinski, Sur certaines hypothèses concernant les nombres premiers, Acta Arith. 4 (1958), 185208. MR 21:4936
 [SW]
 A. Schlafly and S. Wagon, Carmichael's conjecture on the Euler function is valid below , Math. Comp. 63 (1994), 415419. MR 94i:11008
Similar Articles
Retrieve articles in Electronic Research Announcements of the American Mathematical Society
with MSC (1991):
11A25,
11N64,
11N35
Retrieve articles in all journals
with MSC (1991):
11A25,
11N64,
11N35
Additional Information
Kevin Ford
Affiliation:
Department of Mathematics, University of Texas at Austin, Austin, TX 78712
Email:
ford@math.utexas.edu
DOI:
http://dx.doi.org/10.1090/S1079676298000432
PII:
S 10796762(98)000432
Keywords:
Euler's function,
totients,
distributions,
Carmichael's conjecture,
Sierpi\'{n}ski's conjecture
Received by editor(s):
August 13, 1997
Published electronically:
April 27, 1998
Communicated by:
Hugh Montgomery
Article copyright:
© Copyright 1998 American Mathematical Society
