The number of solutions of $\varphi (x)=m$

Kevin Ford

Review from Zentralblatt MATH:

Let $A(m)$ denote the number of integers $n$ for which $\phi(n)=m$, let $V_k(x)$ denote the number of $m\leq x$ for which $A(m)=k$ and let $V(x)=\sum_{k\geq 1} V_k(x)$. Carmichael conjectured that $A(m)\ne 1$ for all $m$ (that is, $V_1(x)=0$); Sierpinski conjectured that for every integer $k\ge 2$, there does exist $m$ with $A(m)=k$. In this delightful paper, Ford proves Sierpinski's long elusive conjecture, even proving the surprising result that $V_k(x)\gg_k V(x)$ for $x>x_k$, whenever $k\geq 2$. He had already proved extraordinarily strong estimates for $V(x)$ in [MR 99m:11106]. Ford and Konyagin [MR 2000d:11120] had already proved Sierpinski's conjecture for even $k$, but the odd $k$ case seems to be considerably more difficult. The starting point for Ford's method is an easy proof of Sierpinski's conjecture under the assumption of the prime triplets conjecture; for if $A(m)=k$ and $p$ is a large prime such that $dp+1$ is prime for $d$ dividing $2m$ only when $d=2$ or $2m$, then $A(2mp)=k+2$. Of course we do not know whether the prime triplets conjecture is true, but we do know, from sieve methods, that we can determine $k$-tuples of ``almost primes'', that is integers with few and only large prime factors. Thus Ford suitably modifies the above construction to incorporate such $k$-tuples. This requires considerable ingenuity and technical prowess, making this proof an impressive achievement.

Reviewed by A.Granville

Classification (MSC2000): 11A25

Full text of the article:

• PDF file (265 kilobytes)