Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. 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}