An arithmetic function arising from Carmichael’s conjecture

Florian Luca[1]; Paul Pollack[2]

  • [1] Instituto de Matemáticas Universidad Nacional Autónoma de México C.P. 58089, Morelia, Michoacán, México
  • [2] University of Illinois at Urbana-Champaign Department of Mathematics Urbana, Illinois 61801, USA

Journal de Théorie des Nombres de Bordeaux (2011)

  • Volume: 23, Issue: 3, page 697-714
  • ISSN: 1246-7405

Abstract

top
Let φ denote Euler’s totient function. A century-old conjecture of Carmichael asserts that for every n , the equation φ ( n ) = φ ( m ) has a solution m ≠ n . This suggests defining F ( n ) as the number of solutions m to the equation φ ( n ) = φ ( m ) . (So Carmichael’s conjecture asserts that F ( n ) ≥ 2 always.) Results on F are scattered throughout the literature. For example, Sierpiński conjectured, and Ford proved, that the range of F contains every natural number k ≥ 2 . Also, the maximal order of F has been investigated by Erdős and Pomerance. In this paper we study the normal behavior of F . Let K ( x ) : = ( log x ) ( log log x ) ( log log log x ) . We prove that for every fixed ϵ > 0 , K ( n ) 1 / 2 - ϵ < F ( n ) < K ( n ) 3 / 2 + ϵ for almost all natural numbers n . As an application, we show that φ ( n ) + 1 is squarefree for almost all n . We conclude with some remarks concerning values of n for which F ( n ) is close to the conjectured maximum size.

How to cite

top

Luca, Florian, and Pollack, Paul. "An arithmetic function arising from Carmichael’s conjecture." Journal de Théorie des Nombres de Bordeaux 23.3 (2011): 697-714. <http://eudml.org/doc/219801>.

@article{Luca2011,
abstract = {Let $\phi $ denote Euler’s totient function. A century-old conjecture of Carmichael asserts that for every $n$, the equation $\phi (n)=\phi (m)$ has a solution $m \ne n$. This suggests defining $F(n)$ as the number of solutions $m$ to the equation $\phi (n)=\phi (m)$. (So Carmichael’s conjecture asserts that $F(n) \ge 2$ always.) Results on $F$ are scattered throughout the literature. For example, Sierpiński conjectured, and Ford proved, that the range of $F$ contains every natural number $k \ge 2$. Also, the maximal order of $F$ has been investigated by Erdős and Pomerance. In this paper we study the normal behavior of $F$. Let\[ K(x) := (\log \{x\})^\{(\log \log \{x\})(\log \log \log \{x\})\}. \]We prove that for every fixed $\epsilon &gt; 0$,\[ K(n)^\{1/2-\epsilon \} &lt; F(n) &lt; K(n)^\{3/2+\epsilon \} \]for almost all natural numbers $n$. As an application, we show that $\phi (n)+1$ is squarefree for almost all $n$. We conclude with some remarks concerning values of $n$ for which $F(n)$ is close to the conjectured maximum size.},
affiliation = {Instituto de Matemáticas Universidad Nacional Autónoma de México C.P. 58089, Morelia, Michoacán, México; University of Illinois at Urbana-Champaign Department of Mathematics Urbana, Illinois 61801, USA},
author = {Luca, Florian, Pollack, Paul},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {Carmichael's conjecture; Euler's function; shifted totients},
language = {eng},
month = {11},
number = {3},
pages = {697-714},
publisher = {Société Arithmétique de Bordeaux},
title = {An arithmetic function arising from Carmichael’s conjecture},
url = {http://eudml.org/doc/219801},
volume = {23},
year = {2011},
}

TY - JOUR
AU - Luca, Florian
AU - Pollack, Paul
TI - An arithmetic function arising from Carmichael’s conjecture
JO - Journal de Théorie des Nombres de Bordeaux
DA - 2011/11//
PB - Société Arithmétique de Bordeaux
VL - 23
IS - 3
SP - 697
EP - 714
AB - Let $\phi $ denote Euler’s totient function. A century-old conjecture of Carmichael asserts that for every $n$, the equation $\phi (n)=\phi (m)$ has a solution $m \ne n$. This suggests defining $F(n)$ as the number of solutions $m$ to the equation $\phi (n)=\phi (m)$. (So Carmichael’s conjecture asserts that $F(n) \ge 2$ always.) Results on $F$ are scattered throughout the literature. For example, Sierpiński conjectured, and Ford proved, that the range of $F$ contains every natural number $k \ge 2$. Also, the maximal order of $F$ has been investigated by Erdős and Pomerance. In this paper we study the normal behavior of $F$. Let\[ K(x) := (\log {x})^{(\log \log {x})(\log \log \log {x})}. \]We prove that for every fixed $\epsilon &gt; 0$,\[ K(n)^{1/2-\epsilon } &lt; F(n) &lt; K(n)^{3/2+\epsilon } \]for almost all natural numbers $n$. As an application, we show that $\phi (n)+1$ is squarefree for almost all $n$. We conclude with some remarks concerning values of $n$ for which $F(n)$ is close to the conjectured maximum size.
LA - eng
KW - Carmichael's conjecture; Euler's function; shifted totients
UR - http://eudml.org/doc/219801
ER -

References

top
  1. R. C. Baker and G. Harman, Shifted primes without large prime factors. Acta Arith. 83 (1998), 331–361. Zbl0994.11033MR1610553
  2. W. D. Banks, J. B. Friedlander, F. Luca, F. Pappalardi, and I. E. Shparlinski, Coincidences in the values of the Euler and Carmichael functions. Acta Arith. 122 (2006), 207–234. Zbl1195.11128MR2239915
  3. R. D. Carmichael, On Euler’s φ -function. Bull. Amer. Math. Soc. 13 (1907), 241–243. Zbl38.0236.01MR1558451
  4. —, Note on Euler’s φ -function. Bull. Amer. Math. Soc. 28 (1922), 109–110. Zbl48.0158.04MR1560520
  5. N. G. de Bruijn, Asymptotic methods in analysis. Third ed., Dover Publications Inc., New York, 1981. Zbl0556.41021MR671583
  6. R. E. Dressler, A density which counts multiplicity. Pacific J. Math. 34 (1970), 371–378. Zbl0181.05302MR271057
  7. P. Erdős, On the normal number of prime factors of p - 1 and some related problems concerning Euler’s φ -function. Quart. J. Math. 6 (1935), 205–213. Zbl0012.14905
  8. —, Some remarks on Euler’s φ -function and some related problems. Bull. Amer. Math. Soc. 51 (1945), 540–544. Zbl0061.08005MR12634
  9. P. Erdős, A. Granville, C. Pomerance, and C. Spiro, On the normal behavior of the iterates of some arithmetic functions. Analytic number theory (Allerton Park, IL, 1989), Progr. Math., vol. 85, Birkhäuser Boston, Boston, MA, 1990, pp. 165–204. Zbl0721.11034MR1084181
  10. P. Erdős and J.-L. Nicolas, Sur la fonction: nombre de facteurs premiers de N . Enseign. Math. (2) 27 (1981), 3–27. Zbl0466.10037MR630957
  11. P. Erdős and C. Pomerance, On the normal number of prime factors of φ ( n ) . Rocky Mountain J. Math. 15 (1985), 343–352. Zbl0617.10037MR823246
  12. K. Ford, The distribution of totients. Ramanujan J. 2 (1998), 67–151. Zbl0914.11053MR1642874
  13. —, The number of solutions of φ ( x ) = m . Ann. of Math. (2) 150 (1999), 283–311. MR1715326
  14. A. Granville, Smooth numbers: computational number theory and beyond. Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 267–323. Zbl1230.11157MR2467549
  15. G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number n . Quart. J. Math. 58 (1917), 76–92. Zbl46.0262.03
  16. G. H. Hardy and E. M. Wright, An introduction to the theory of numbers. Fifth ed., Oxford University Press, New York, 1979. Zbl1159.11001MR568909
  17. F. Luca and C. Pomerance, On some problems of Mąkowski-Schinzel and Erdős concerning the arithmetical functions φ and σ . Colloq. Math. 92 (2002), 111–130. Zbl1027.11007MR1899242
  18. —, Irreducible radical extensions and Euler-function chains. Combinatorial number theory, de Gruyter, Berlin, 2007, pp. 351–361. MR2337059
  19. P. Pollack, On the greatest common divisor of a number and its sum of divisors. Michigan Math. J. 60 (2011), 199–214. Zbl1286.11152MR2785871
  20. C. Pomerance, Popular values of Euler’s function. Mathematika 27 (1980), 84–89. Zbl0437.10001MR581999
  21. —, On the distribution of pseudoprimes. Math. Comp. 37 (1981), 587–593. Zbl0511.10002MR628717
  22. —, Two methods in elementary analytic number theory. Number theory and applications (Banff, AB, 1988), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 265, Kluwer Acad. Publ., Dordrecht, 1989, pp. 135–161. MR1123073
  23. G. Robin, Estimation de la fonction de Tchebychef θ sur le k -ième nombre premier et grandes valeurs de la fonction ω ( n ) nombre de diviseurs premiers de n . Acta Arith. 42 (1983), 367–389. Zbl0475.10034MR736719

NotesEmbed ?

top

You must be logged in to post comments.