MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

The Inverse of the Euler Totient Function

How can we calculate the cardinality of the inverse of Totient function of any positive integer n ? I tried going through this paper, but I couldn't understand the procedure.

Thanks

-

f you are interested in a computational approach, there is software that can compute $\varphi^{-1}(n)$.

PARI/GP Scripts for Miscellaneous Math Problems by Max Alekseyev check invphi.gp.

The original invphi.gp appears for quite old pari/gp and doesn't run on current pari, I ported it here.

Here is a sample session:

? \r invphi2.gp
? n=2*13*17;v=invphi(n);#v
%1 = 2
? v
%2 = [443, 886]
? eulerphi(v[1])==n
%3 = 1

-

Here is a naive attempt, which can be refined to give an upper bound on the cardinality. I will only look at the case that the inverse n is odd, the even case being mildly more complicated.

So given $p$, I want to find how many odd $n$ satisfy $\phi(n)=p$. Let $p=r2^w$ with $r$ odd. To make things interesting assume $w>0$. Pick $b \geq w$ and assume $n$ has at most $b$ factors. Place the $w$ 2's in $b$ buckets. If a prime factor $q$ of $r$ is not going into a bucket, then we must put in one bucket enough to make $q-1$. Otherwise, distribute the prime factors of $r$ into the buckets. Each bucket will contain those primes which multiply to form $q-1$, where $q$ is a factor of $n$. If $r$ has $c$ not necessarily distinct prime factors, there are then at most $c^{b+1}$ ways to distribute the factors of $r$, and not all of them will work.

A recursive version is to assume the least prime factor of $n$ is $q$, and then try to find solutions to $\phi(m)=p/[(q-1)q^s]$ for appropriate values of $s$. This may be quicker to implement but harder to analyze.

-

I assume you are asking about $N(m)$, the number of distinct integers $n$ which satisfy $\phi(n)=m$ where $\phi$ is the Euler Totient function.

There are many results regarding upper and lower bounds for the size of $N(m)$, as well as the mean and variance. In particular, Carmichael conjectured that $N(m)$ is never equal to $1$.

Pomerance gave the upper bound $$N(m)\leq m\exp{-(1+o(1))\log m \frac{\log \log \log m}{\log \log m}}$$ and also showed that there are infinitely many $m$ for which $$N(m)\geq m^{\frac{5}{9}}.$$

Bateman showed that $$\sum_{m\leq x} N(m)=\frac{\zeta(2)\zeta(3)}{\zeta(6)}x+O\left(xe^{-c\sqrt{\log x\log \log x}}\right),$$ and we also have that $$\sum_{m\leq x} N(m)-\frac{\zeta(2)\zeta(3)}{\zeta(6)}x=\Omega\left(x^\frac{5}{9}\right)$$

For more details, see the following paper of Pomerance: Popular Values of Euler's Function.

-
 thanks Eric, but for calculations what's o(1) ? – pranay Oct 13 at 8:04