An arithmetic function arising from Carmichael’s conjecture

Luca, Florian; Pollack, Paul

Journal de théorie des nombres de Bordeaux, Volume 23 (2011) no. 3, pp. 697-714.

Let $\phi$ denote Euler’s totient function. A century-old conjecture of Carmichael asserts that for every $n$, the equation $\phi \left(n\right)=\phi \left(m\right)$ has a solution $m\ne n$. This suggests defining $F\left(n\right)$ as the number of solutions $m$ to the equation $\phi \left(n\right)=\phi \left(m\right)$. (So Carmichael’s conjecture asserts that $F\left(n\right)\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\left(x\right):={(logx)}^{(loglogx)(logloglogx)}.$$

We prove that for every fixed $ϵ>0$,

$$K{\left(n\right)}^{1/2-ϵ}<F\left(n\right)<K{\left(n\right)}^{3/2+ϵ}$$

for almost all natural numbers $n$. As an application, we show that $\phi \left(n\right)+1$ is squarefree for almost all $n$. We conclude with some remarks concerning values of $n$ for which $F\left(n\right)$ is close to the conjectured maximum size.

Soit $\phi$ la fonction indicatrice d’Euler. Une conjecture de Carmichael qui a 100 ans affirme que pour chaque $n$, l’équation $\phi \left(n\right)=\phi \left(m\right)$ a au moins une solution $m\ne n$. Ceci suggère que l’on définisse $F\left(n\right)$ comme le nombre de solutions $m$ de l’équation $\phi \left(n\right)=\phi \left(m\right)$. (Donc, la conjecture de Carmichael est équivalente à l’inégalité $F\left(n\right)\ge 2$ pour tout $n$.) Les résultats sur $F$ sont répandus dans la littérature. Par exemple, Sierpiński a conjecturé, et Ford a démontré, que l’image de $F$ contient tous les nombres $k\ge 2$. Aussi, l’ordre maximal de $F$ a été recherché par Erdős et Pomerance. Dans notre article, nous étudions l’ordre normal de $F$. Soit

$$K\left(x\right):={(logx)}^{(loglogx)(logloglogx)}.$$

On démontre que pour chaque $\epsilon >0$, l’inégalité

$$K{\left(n\right)}^{1/2-\epsilon }<F\left(n\right)<K{\left(n\right)}^{3/2+\epsilon }$$

est vraie pour presque tous les entiers positifs $n$. Comme application, on montre que $\phi \left(n\right)+1$ est sans facteur carré pour presque tous les $n$. On conclut avec quelques remarques sur les valeurs de $n$ telles que $F\left(n\right)$ est proche de sa valeur maximale conjecturée.

[1] R. C. Baker and G. Harman, Shifted primes without large prime factors. Acta Arith. 83 (1998), 331–361. | EuDML | MR | Zbl

[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. | EuDML | MR | Zbl

[3] R. D. Carmichael, On Euler’s $\phi$-function. Bull. Amer. Math. Soc. 13 (1907), 241–243. | JFM | MR

[4] —, Note on Euler’s $\phi$-function. Bull. Amer. Math. Soc. 28 (1922), 109–110. | JFM | MR

[5] N. G. de Bruijn, Asymptotic methods in analysis. Third ed., Dover Publications Inc., New York, 1981. | MR | Zbl

[6] R. E. Dressler, A density which counts multiplicity. Pacific J. Math. 34 (1970), 371–378. | MR | Zbl

[7] P. Erdős, On the normal number of prime factors of $p-1$ and some related problems concerning Euler’s $\phi$-function. Quart. J. Math. 6 (1935), 205–213. | JFM

[8] —, Some remarks on Euler’s $\phi$-function and some related problems. Bull. Amer. Math. Soc. 51 (1945), 540–544. | MR | Zbl

[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. | MR | Zbl

[10] P. Erdős and J.-L. Nicolas, Sur la fonction: nombre de facteurs premiers de $N$. Enseign. Math. (2) 27 (1981), 3–27. | MR | Zbl

[11] P. Erdős and C. Pomerance, On the normal number of prime factors of $\phi \left(n\right)$. Rocky Mountain J. Math. 15 (1985), 343–352. | MR | Zbl

[12] K. Ford, The distribution of totients. Ramanujan J. 2 (1998), 67–151. | MR | Zbl

[13] —, The number of solutions of $\phi \left(x\right)=m$. Ann. of Math. (2) 150 (1999), 283–311. | EuDML | MR

[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. | MR | Zbl

[15] G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number $n$. Quart. J. Math. 58 (1917), 76–92. | JFM

[16] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers. Fifth ed., Oxford University Press, New York, 1979. | MR | Zbl

[17] F. Luca and C. Pomerance, On some problems of Mąkowski-Schinzel and Erdős concerning the arithmetical functions $\phi$ and $\sigma$. Colloq. Math. 92 (2002), 111–130. | EuDML | MR | Zbl

[18] —, Irreducible radical extensions and Euler-function chains. Combinatorial number theory, de Gruyter, Berlin, 2007, pp. 351–361. | MR

[19] P. Pollack, On the greatest common divisor of a number and its sum of divisors. Michigan Math. J. 60 (2011), 199–214. | MR | Zbl

[20] C. Pomerance, Popular values of Euler’s function. Mathematika 27 (1980), 84–89. | MR | Zbl

[21] —, On the distribution of pseudoprimes. Math. Comp. 37 (1981), 587–593. | MR | Zbl

[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. | MR | Zbl

[23] G. Robin, Estimation de la fonction de Tchebychef $\theta$ sur le $k$-ième nombre premier et grandes valeurs de la fonction $\omega \left(n\right)$ nombre de diviseurs premiers de $n$. Acta Arith. 42 (1983), 367–389. | EuDML | MR | Zbl