These pages are not updated anymore. They reflect the state of . For the current production of this journal, please refer to http://www.math.psu.edu/era/.
%_ ************************************************************************** %_ * The TeX source for AMS journal articles is the publisher's TeX code * %_ * which may contain special commands defined for the AMS production * %_ * environment. Therefore, it may not be possible to process these files * %_ * through TeX without errors. To display a typeset version of a journal * %_ * article easily, we suggest that you either view the HTML version or * %_ * retrieve the article in DVI, PostScript, or PDF format. * %_ ************************************************************************** % Author Package %% Translation via Omnimark script a2l, April 16, 1998 (all in one day!) \controldates{22-APR-1998,22-APR-1998,22-APR-1998,22-APR-1998} \documentclass{era-l} %% Declarations: \theoremstyle{plain} \newtheorem{thm}{Theorem} \newtheorem*{cnj}{Conjecture} \newtheorem{cor}[thm]{Corollary} %% User definitions: \newcommand{\ve}{\varepsilon } \newcommand{\om}{\Omega } \newcommand{\fancyV}{\mathcal{V}} \begin{document} \title{The distribution of totients } \author{Kevin Ford} \address{Department of Mathematics, University of Texas at Austin, Austin, TX 78712 } \email{ford@math.utexas.edu } \subjclass{Primary 11A25, 11N64; Secondary 11N35} \begin{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 $\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\'{n}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. \end{abstract} \keywords{Euler's function, totients, distributions, Carmichael's conjecture, Sierpi\'{n}ski's conjecture} \issueinfo{4}{05}{}{1998} \dateposted{April 27, 1998} \pagespan{27}{34} \PII{S 1079-6762(98)00043-2} \def\copyrightyear{1998} \copyrightinfo{1998}{American Mathematical Society} \commby{Hugh Montgomery} \date{August 13, 1997} \maketitle Let $\fancyV $ denote the set of values taken by Euler's $\phi $-function (totients), i.e. \begin{equation*}\fancyV = \{ 1,2,4,6,8,10,12,16,18,20,22,24,28,30, \dots \}. \end{equation*} Let \begin{equation}\label{eq:1}\begin{split} \fancyV (x) &= \fancyV \cap [1,x], \\ V(x) &= |\fancyV (x)|, \\ A(m) &= |\{n:\phi (n)=m\} |, \\ V_{k}(x) &= |\{m \le x : A(m)=k \}|. \end{split} \end{equation} We will refer to $A(m)$ as the multiplicity of $m$. This paper summarizes recent work on the following questions. 1. What is the order of $V(x)$? 2. What is the order of $V_{k}(x)$ when the multiplicity $k$ is possible? 3. What multiplicities are possible? 4. What is the normal multiplicative structure of totients? 1. The Prime Number Theorem implies $V(x) \gg x/\log x$, since $\phi (p)=p-1$ for primes $p$. Pillai \cite{Pi} gave the first non-trivial bound on $V(x)$, namely \begin{equation*}V(x) \ll \frac{x}{(\log x)^{(\log 2)/e}}. \end{equation*} Using sieve methods, Erd\"{o}s \cite{E1} improved this to \begin{equation*}V(x) \ll _{\ve }\frac{x}{(\log x)^{1-\ve }} \end{equation*} and later in \cite{E2} showed that \begin{equation*}V(x) \gg \frac{x\log _{2} x}{\log x}. \end{equation*} Here and throughout this paper $\log _{k} x$ denotes the $k$th iterate of the logarithm. Further sharpening of the upper and lower bounds were found by Erd\"{o}s and Hall \cite{EH1}, \cite{EH2}, Pomerance \cite{P1}, and Maier and Pomerance \cite{MP}. The last result is \begin{equation}\label{eq:2} V(x) = \frac{x}{\log x} \exp \{ (C+o(1))(\log _{3} x)^{2} \}, \end{equation} where $C$ is a constant defined as follows. Let \begin{equation*}F(x) = \sum _{n=1}^{\infty }a_{n}x^{n}, \qquad a_{n} = (n+1)\log (n+1)-n\log n-1. \end{equation*} Since $a_{n} \sim \log n$ and $a_{n}>0$, it follows that $F(x)$ is defined and strictly increasing on $[0,1)$, $F(0)=0$ and $F(x) \to \infty $ as $x \to 1^{-}$. Thus, there is a unique number $\varrho $ such that \begin{equation*}F(\varrho ) = 1 \qquad (\varrho = 0.542598586098471021959\ldots ) \end{equation*} and we set \begin{equation*}C = \frac{1}{2|\log \varrho |} = 0.81781464640083632231\ldots\,. \end{equation*} Our first major result is a determination of the true order of $V(x)$. First define \begin{equation*}\begin{split} D &= 2C(1+\log F'(\varrho ) - \log (2C)) - 3/2 \\ &= 2.17696874355941032173 \ldots\,. \end{split}\end{equation*} \begin{thm}[{\cite[Theorem 1]{F1}}]\label{thm:1} We have \begin{equation*}V(x) = \frac{x}{\log x} \exp \{ C(\log _{3} x-\log _{4} x)^{2} +D \log _{3} x - (D+1/2-2C)\log _{4} x + O(1) \}. \end{equation*} \end{thm} 2. Erd\"{o}s \cite{E3} showed by sieve methods that if $A(m)=k$, then for most primes $p$, $A(m(p-1))=k$. If the multiplicity $k$ is possible, it follows immediately that $V_{k}(x) \gg x/\log x$. Applying the machinery used to prove Theorem \ref{thm:1}, we show that for each $k$, either $V_{k}(x)=0$ for all $x$, or $V_{k}(x)$ is the same order as $V(x)$. \begin{thm}[{\cite[Theorem 2]{F1}}]\label{thm:2} If there is a number $d$ with $A(d)=k$, then \begin{equation*}V_{k}(x) \gg _{\ve }d^{-1-\ve } V(x) \qquad (x\ge x_{0}(k)). \end{equation*} \end{thm} In other words, a positive fraction of totients have multiplicity $k$ if the multiplicity $k$ is possible. This suggests that the multiplicity of ``most'' totients is bounded. \begin{thm}[{\cite[Theorem 3]{F1}}]\label{thm:3} We have \begin{equation*}\frac{| \{ m\in \fancyV (x) : A(m)\ge N \}| }{V(x)} = \sum _{k\ge N} \frac{V_{k}(x)}{V(x)} \ll N^{-1} \exp \{O(\sqrt { \log N}) \}. \end{equation*} \end{thm} 3. In 1907, Carmichael \cite{C1} announced that for every $m$, the equation $\phi (x)=m$ has either no solutions $x$ or at least two solutions. In other words, no totient can have multiplicity 1. His proof of this assertion was flawed, however, but he did show in \cite{C2} that no number $m<10^{37}$ has multiplicity 1, and conjectured that no such $m$ exists (this is now known as Carmichael's Conjecture). Improved lower bounds for a possible counterexample have been found by Klee \cite{K}, Masai and Valette \cite{MV}, and recently by Schlafly and Wagon \cite{SW}, who showed that a counterexample must exceed $10^{10,000,000}$. Carmichael's Conjecture, however, remains an open problem. An immediate and important corollary of Theorems \ref{thm:1} and \ref{thm:2} is \begin{thm}[{\cite[Theorem 5]{F1}}]\label{thm:4} We have \begin{equation*}\limsup _{x\to \infty } \frac{V_{1}(x)}{V(x)} < 1. \end{equation*} Furthermore, Carmichael's Conjecture is equivalent to the bound \begin{equation*}\liminf _{x\to \infty } \frac{V_{1}(x)}{V(x)} = 0. \end{equation*} \end{thm} Although this is a long way from proving Carmichael's Conjecture, Theorem \ref{thm:4} shows that the set of counterexamples cannot be a ``thin'' subset of $\fancyV $. Either there are no counterexamples or a positive fraction of totients are counterexamples. The basis for the computations of lower bounds for a possible counterexample is a lemma of Carmichael, generalized by Klee, which allows one to show that if $A(m)=1$, then $x$ must be divisible by the squares of many primes. Using the method outlined in \cite{SW} and modern computer hardware, we push the lower bound for a counterexample to an aesthetically pleasing bound. \begin{thm}[{\cite[Theorem 6]{F1}}]\label{thm:5} If $A(m)=1$, then $m$ exceeds $10^{10^{10}}$. \end{thm} Aside from computations, the only other non-trivial result concerning the behavior of $V_{1}(x)$ is the bound \begin{equation*}\liminf _{x\to \infty } \frac{V_{1}(x)}{V(x)} \le \frac{1}{2}, \end{equation*} proved by elementary methods in an unpublished note of Pomerance (see \cite{P2}). A modification of his argument combined with the computations giving Theorem \ref{thm:5} yields \begin{thm}[{\cite[Theorem 7]{F1}}]\label{thm:6} We have \begin{equation*}\liminf _{x\to \infty } \frac{V_{1}(x)}{V(x)} \le 10^{-5,000,000,000}. \end{equation*} \end{thm} In the 1950's, Sierpi\'{n}ski conjectured that all multiplicities $k\ge 2$ are possible (see \cite{S1} and \cite{E3}), and in 1961, Schinzel \cite{S2} deduced this conjecture from his well-known Hypothesis H. Schinzel's Hypothesis H \cite{SS}, a generalization of Dickson's Prime $k$-tuples Conjecture \cite{D}, states that any set of polynomials $F_{1}(n),\dots , F_{k}(n)$, subject to natural restrictions, are simultaneously prime for infinitely many $n$. Using the modern theory of ``almost primes'' (numbers with few prime factors) together with an iterative approach, we provide an unconditional proof of Sierpi\'{n}ski's Conjecture. \begin{thm}[{\cite[Theorem 1]{F2}}]\label{thm:7} For each $k \ge 2$, there is a number $d$ with $A(d)=k$. \end{thm} Therefore, by Theorem \ref{thm:2}, $V_{k}(x) \gg V(x)$ for $k\ge 2$. The computations leading to Theorems \ref{thm:5} and \ref{thm:6} motivate another classification of totients. Let $V(x;k)$ be the number of totients up to $x$, all of whose pre-images are divisible by $k$. A corollary of the proof of Theorem \ref{thm:2} is \begin{thm}[{\cite[Theorem 8]{F1}}]\label{thm:8} If $d$ is a totient, all of whose pre-images are divisible by $k$, then \begin{equation*}V(x;k) \gg _{\ve }d^{-1-\ve } V(x). \end{equation*} Thus, for each $k$, either $V(x;k)=0$ for all $x$ or $V(x;k)\gg _{k} V(x)$. \end{thm} It is natural to ask for which $k$ do there exist totients, all of whose pre-images are divisible by $k$. A short search reveals examples for each $k\le 11$ except $k=6$ and $k=10$. For $k=2,4$ and 8, take $d=2^{18} \cdot 257$, for $k=3$ or 9 take $d=54=2\cdot 3^{3}$, for $k=5$ take $d=12500=4\cdot 5^{5}$, for $k=7$, take $d=294=6\cdot 7^{2}$ and for $k=11$, take $d=110$. It appears that there might not be any totient, all of whose pre-images are divisible by 6, but I cannot prove this. \begin{cnj}\label{conj} There is no totient, all of whose pre-images are divisible by 6. \end{cnj} In particular, any totient with a unique pre-image must have that pre-image divisible by 6, so the non-existance of such numbers implies Carmichael's Conjecture. 4. Establishing Theorems \ref{thm:1} and \ref{thm:2} requires a determination of what a ``normal'' totient looks like. This will initially take the form of a series of linear inequalities in the prime factors of a pre-image of a totient. An analysis of these inequalities reveals the normal sizes of the prime factors of a pre-image of a typical totient. To state our results, we first define \begin{equation*}L_{0} = L_{0}(x) = [2C(\log _{3} x - \log _{4} x)]. \end{equation*} In a simplified form, we show that for all but $o(V(x))$ totients $m\le x$, every pre-image $n$ satisfies \begin{equation}\label{eq:3} \log _{2} q_{i}(n) \sim \varrho ^{i}(1-i/L_{0}) \log _{2} x \qquad (0\le i\le L_{0}), \end{equation} where $q_{i}(n)$ denotes the $(i+1)$st largest prime factor of $n$. Let $\omega (m)$ denote the number of distinct prime factors of $m$ and let $\om (m)$ denote the number of prime factors of $m$ counted with multiplicity. Then we have \begin{thm}[{\cite[Theorem 11]{F1}}]\label{thm:9} Suppose $g(x)$ is an increasing function of $x$ satisfying $g(x)=o(\log _{3} x)$. For a given $x$, set $L_{0}=L_{0}(x)$ and $\beta _{i} = \varrho ^{i} (1-i/L_{0})$ for $0\le i\le L_{0}$. Then the number of totients $m\le x$ with a pre-image $n$ not satisfying \begin{equation}\label{eq:4} \left | \frac{\log _{2} q_{i}(n)}{\beta _{i}\log _{2} x} - 1 \right | \le \sqrt {\frac{i}{L_{0}(L_{0}-i)}} \log (L_{0}-i) \log g(x) \qquad (1 \le i \le L_{0} - g(x)) \end{equation} and \begin{equation*}L_{0}(x)-g(x) \le \omega (n)\le \om (n) \le L_{0}(x) + 30 g(x) \varrho ^{-g(x)} \end{equation*} is \begin{equation*}\ll V(x) \left ( e^{-\log ^{2} g(x)} + e^{-\frac{1}{4} \log _{4} x\log g(x)} \right ). \end{equation*} \end{thm} In essence, Theorem \ref{thm:9} says that the set of $n\le x$ having about $L_{0}(x)$ prime factors distributed according to \eqref{eq:4} generates almost all totients. It also says that for most totients, all of its pre-images are ``virtually'' square-free. The function $g(x)$ need not tend to infinity. Notice that the intervals in \eqref{eq:4} are not only disjoint, but the gaps between them are rather large. In particular, this ``discreteness phenomenon'' means that for most totients $m\le x$, no pre-image $n$ has any prime factors in the intervals \begin{equation*}0.999\ge \frac{\log _{2} p}{\log _{2} x} \ge 0.543, \quad 0.542 \ge \frac{\log _{2} p}{\log _{2} x} \ge 0.295, \text{ etc.} \end{equation*} This should be compared to the distribution of the prime factors of a normal integer $n\le x$ (e.g. Theorem 12 of \cite{HT}). We also deduce the normal order of $\om (m)$ and $\omega (m)$ for totients $m$. If each prime $q_{i}(n)$ of a pre-image $n$ is ``normal'' and \eqref{eq:3} holds, then $\om (m)$ should be about \begin{equation*}(1+\varrho +\varrho ^{2}+\cdots )\log _{2} x = \frac{\log _{2} x}{1-\varrho }. \end{equation*} \begin{thm}[{\cite[Theorem 12]{F1}}]\label{thm:10} Suppose $\ve =\ve (x)$ satisfies $0\le \ve \le 0.8$. Then \begin{equation*}\# \left \{ m\in \fancyV (x) : \left | \frac{\om (m)}{\log _{2} x} - \frac{1}{1-\varrho } \right | \ge \ve \right \} \ll V(x) \exp \{-K\ve \log _{3} x + O(\sqrt {\ve \log _{3} x}) \}, \end{equation*} where \begin{equation*}K= \frac{2Ca_{1} (1-\varrho )}{1-(1+a_{1})\varrho } = 1.166277\ldots\,. \end{equation*} Consequently, if $g(x)\to \infty $ as slowly as desired, then almost all totients $m\le x$ satisfy \begin{equation*}\left | \frac{\om (m)}{\log _{2} x} - \frac{1}{1-\varrho } \right | \le \frac{g(x)}{\log _{3} x}. \end{equation*} Moreover, the theorem holds with $\om (m)$ replaced by $\omega (m)$. \end{thm} \begin{cor}[{\cite[Corollary 13]{F1}}]\label{thm:11} If either $h(m)=\omega (m)$ or $h(m)=\om (m)$, then \begin{equation*}\sum _{m\in \fancyV (x)} h(m) = \frac{V(x)\log _{2} x}{1-\varrho } \left ( 1 + O\left ( \frac{1}{\log _{3} x} \right ) \right ). \end{equation*} \end{cor} By contrast, Erd\"{o}s and Pomerance \cite{EP} showed that the average of $\om (\phi (n))$, where the average is taken over all $n\le x$, is $\frac{1}{2} (\log _{2} x)^{2} + O((\log _{2} x)^{3/2})$. The details of the proofs of these results are extremely complex and require very delicate estimating, but the central ideas are fairly simple. First, for most integers $m$, the prime divisors of $m$ are ``nicely distributed'', meaning the number of prime factors of $m$ lying between $a$ and $b$ is about $\log _{2} b - \log _{2} a$. This is a more precise version of the classical result of Hardy and Ramanujan \cite{HR} that most numbers $m$ have about $\log _{2} m$ prime factors. Take an integer $n$ with prime factorization $p_{0} p_{1} \cdots $, where for simplicity we assume $n$ is square-free, and $p_{0}>p_{1}> \cdots $. By sieve methods it can be shown that for most primes $p$, the prime divisors of $p-1$ have the same ``nice'' distribution. If $p_{0}, p_{1}, \ldots $ are such ``normal'' primes, it follows that $\phi (n) = (p_{0}-1)(p_{1}-1)\cdots $ has about $\log _{2} n - \log _{2} p_{1}$ prime factors in $[p_{1},n]$, about $2(\log _{2} p_{1} - \log _{2} p_{2})$ prime factors in $[p_{2},p_{1}]$, and in general, $\phi (n)$ will have $k(\log _{2} p_{k-1} - \log _{2} p_{k})$ prime factors in $[p_{k},p_{k-1}]$. That is, $n$ has $k$ times as many prime factors in the interval $[p_{k},p_{k-1}]$ as does a ``normal'' integer of its size. If $n$ has many ``large'' prime divisors, then the prime factors of $m=\phi (n)$ will be much denser than normal, and the number, $N_{1}$, of such integers $m$ will be ``small''. On the other hand, the number, $N_{2}$, of integers $n$ with relatively few ``large'' prime factors is also ``small''. Our objective then is to precisely define these concepts of ``large'' and ``small'' so as to minimize $N_{1}+N_{2}$. The argument in \cite{MP} is based on the heuristic that a normal totient is generated from a number $n$ satisfying \begin{equation}\label{eq:5} \log _{2} q_{i}(n) \approx \varrho ^{i} \log _{2} x \end{equation} for each $i$ (compare with \eqref{eq:3}). As an alternative to this heuristic, assuming all prime factors of a pre-image $n$ of a totient are normal leads to consideration of a series of inequalities among the prime factors of $n$. Specifically, let $x$ be large, $x/2< n \le x$ and let $q_{0} \ge q_{1} \ge \cdots $ denote the prime factors of $n$. Fix $L$ and map $n$ to the point $(x_{1},\dots , x_{L})$, where $x_{i} = \log _{2} q_{i}/\log _{2} x$ if $i< \Omega (n)$, and $q_{i}\ge 3$, $x_{i}=0$ otherwise. Consider the following inequalities: \begin{equation*}\begin{split} 0 \le x_{L} \le \cdots \le x_{1} &\le 1, \\ a_{1} x_{1} + \cdots + a_{L} x_{L} &\le 1, \\ a_{1} x_{2} + \cdots + a_{L-1} x_{L} &\le x_{1}, \\ a_{1} x_{3} + \cdots + a_{L-2} x_{L} &\le x_{2}, \\ &\vdots \\ a_{1} x_{L-1} + a_{2} x_{L} &\le x_{L-2}. \end{split}\end{equation*} We show that such $n$ generate ``most'' totients and then reduce the problem of counting such $n$ to the problem of finding the volume of the region in $\mathbb{R}^{L}$ defined by these inequalities, denoted $\mathcal{S}_{L}$. What we show is essentially \begin{equation}V(x)\label{eq:6} \approx \frac{x}{\log x} \max _{L} \text{Vol}(\mathcal{S}_{L}) (\log _{2} x)^{L}. \end{equation} With the estimate \begin{equation*}\text{Vol}(\mathcal{S}_{L}) \approx \frac{\varrho ^{L(L+3)/2}}{L!} (F'(\varrho ))^{L}, \end{equation*} the maximum in \eqref{eq:6} occurs at about $L=L_{0}(x)$ and Theorem \ref{thm:1} follows. Careful analysis of these inequalities reveals that the bulk of $\mathcal{S}_{L}$ is concentrated near the point $(\beta _{1}, \dots , \beta _{L})$, where $\beta _{i} = (1-\frac{i}{L}) \varrho ^{i}$. It follows that ``most'' of the integers $n$ mapping into $\mathcal{S}_{L}$ satisfy \eqref{eq:3}. Thus, the heuristic \eqref{eq:5} gives numbers $n$ whose smaller prime factors are too large. In particular, with $L=L_{0}(x)$, we have $\log _{2} p_{L-1} \approx \frac{1}{L}\varrho ^{L-1} \log _{2} x \approx 1$, an important observation for determining the true order of $V(x)$. Lastly, most of these results may be easily extended to more general multiplicative arithmetic functions such as $\sigma (n)$, the sum of divisors function. Defining analogous functions $\mathcal{V}_{f}$, $V_{f}(x)$, $V_{f,k}(x)$ and $A_{f}(m)$, we prove \begin{thm}[{\cite[Theorem 14]{F1}}]\label{thm:12} Suppose $f:\mathbb{N}\to \mathbb{N}$ is a multiplicative function satisfying \begin{align*} &\{ f(p)-p:p \text{ prime} \} \text{ is a finite set not containing $0$,} \\ &\sum _{_{\substack{h\ge 16 \\ h\textup{ square-full} }}} \frac{\ve (h)}{f(h)} \ll 1, \qquad \ve (h)=\exp \{ \log _{2} h (\log _{3} h)^{20} \}. \end{align*} Then the analogs of Theorems \ref{thm:1}--\ref{thm:3}, \ref{thm:7} and \ref{thm:9}--\ref{thm:11} hold with $f(n)$ replacing $\phi (n)$, with the exception of the dependence on $d$ in Theorems \ref{thm:2} and \ref{thm:3}, which may be different. \end{thm} The possible set of multiplicities for each $f$, however, depends on the particular function, since the values of $f(p^{k})$ for $k\ge 2$ play a more important role. In particular, the proof of Theorem \ref{thm:7} relies on the property that $\phi (p^{2})=p\phi (p)$ for primes $p$. However, when $f=\sigma $, the analog of Theorem \ref{thm:7} has been proved (\cite[Theorem~1]{FK}) and the method extends to many other functions satisfying the hypotheses of Theorem \ref{thm:12} for which $A_{f}(m)=1$ has a solution. \bibliographystyle{amsalpha} \begin{thebibliography}{9991} \bibitem[C1]{C1} R. D. Carmichael, {\em On Euler's $\phi $-function}, Bull. Amer. Math. Soc. {\bf 13} (1907), 241--243. \bibitem[C2]{C2} \bysame , {\em Note on Euler's $\phi $-function}, Bull. Amer. Math. Soc. {\bf 28} (1922), 109--110. \bibitem[D]{D} L. E. Dickson, {\em A new extension of Dirichlet's theorem on prime numbers}, Messenger of Math. {\bf 33} (1904), 155--161. \bibitem[E1]{E1} P. Erd\"{o}s, {\em On the normal number of prime factors of $p-1$ and some related problems concerning Euler's $\phi $-function}, Quart. J. Math. Oxford (1935), 205--213. \bibitem[E2]{E2} \bysame , {\em Some remarks on Euler's $\phi $-function and some related problems}, Bull. Amer. Math. Soc. {\bf 51} (1945), 540--544. \MR{7:49f} \bibitem[E3]{E3} \bysame , {\em Some remarks on Euler's $\phi $-function}, Acta Arith. vol 4 (1958), 10--19. \MR{22:1539} \bibitem[EH1]{EH1} P. Erd\"{o}s and R. R. Hall, {\em On the values of Euler's $\phi $-function}, Acta Arith. {\bf 22} (1973), 201-206. \MR{53:13143} \bibitem[EH2]{EH2} \bysame , {\em Distinct values of Euler's $\phi $-function}, Mathematika {\bf 23} (1976), 1--3. \MR{54:2603} \bibitem[EP]{EP} P. Erd\"{o}s and C. Pomerance, {\em On the normal number of prime factors of $\phi (n)$}, Rocky Mountain J. of Math. {\bf 15} (1985), 343--352. \MR{87e:11112} \bibitem[F1]{F1} K. Ford, {\em The distribution of totients}, The Ramanujan J. {\bf 2} (1998), no. 1-2 (to appear). \bibitem[F2]{F2} \bysame , {\em The number of solutions of $\phi (x)=m$}, Annals of Math. (to appear). \bibitem[FK]{FK} K. Ford and S. Konyagin, {\em On a conjecture of Sierpi\'{n}ski concerning the sum of divisors function}, Proceedings of the International Number Theory Conference dedicated to Professor Andrzej Schinzel, Zakopane, Poland (to appear). \bibitem[HT]{HT} R. R. Hall and G. Tenenbaum, {\em Divisors}, Cambridge University Press, 1988. \MR{90a:11107} \bibitem[HR]{HR} G. H. Hardy and S. Ramanujan, {\em The normal number of prime factors of a number $n$}, Quart. J. Math. {\bf 48} (1917), 76--92. \bibitem[K]{K} V. Klee, {\em On a conjecture of Carmichael}, Bull. Amer. Math. Soc. {\bf 53} (1947), 1183--1186. \MR{9:269d} \bibitem[MP]{MP} H. Maier and C. Pomerance, {\em On the number of distinct values of Euler's $\phi $-function}, Acta Arith. {\bf 49} (1988), 263--275. \MR{89d:11083} \bibitem[MV]{MV} P. Masai and A. Valette, {\em A lower bound for a counterexample to Carmichael's Conjecture}, Boll. Un. Mat. Ital. A (6) {\bf 1} (1982), 313--316. \MR{84b:10008} \bibitem[Pi]{Pi} S. Pillai, {\em On some functions connected with $\phi (n)$}, Bull. Amer. Math. Soc. {\bf 35} (1929), 832--836. \bibitem[P1]{P1} C. Pomerance, {\em On the distribution of the values of Euler's function}, Acta Arith. {\bf 47} (1986), 63--70. \MR{88b:11060} \bibitem[P2]{P2} \bysame , {\em Problem 6671}, Amer. Math. Monthly {\bf 98} (1991), 862. \bibitem[S1]{S1} A. Schinzel, {\em Sur l'\'{e}quation $\phi (x)=m$}, Elem. Math. {\bf 11} (1956), 75--78. \MR{18:194c} \bibitem[S2]{S2} \bysame , {\em Remarks on the paper ``Sur certaines hypoth\`{e}ses concernant les nombres premiers''}, Acta Arith. {\bf 7} (1961/62), 1--8. \MR{24:A70} \bibitem[SS]{SS} A. Schinzel and W. Sierpi\'{n}ski, {\em Sur certaines hypoth\`{e}ses concernant les nombres premiers}, Acta Arith. {\bf 4} (1958), 185--208. \MR{21:4936} \bibitem[SW]{SW} A. Schlafly and S. Wagon, {\em Carmichael's conjecture on the Euler function is valid below $10^{10,000,000}$}, Math. Comp. {\bf 63} (1994), 415--419. \MR{94i:11008} \end{thebibliography} \end{document}