1
$\begingroup$

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

$\endgroup$
2

5 Answers 5

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thanks Eric, but for calculations what's o(1) ? $\endgroup$
    – pranay
    Oct 13, 2012 at 8:04
3
$\begingroup$

See also my recent paper "Computing the (number or sum of) inverses of Euler's totient and other multiplicative functions", which presents a generic dynamic programming algorithm for finding the inverses of a multiplicative function for a given integer value.

Please let me know if something is unclear.

$\endgroup$
4
  • 1
    $\begingroup$ I liked your preprint. I would like it more if you gave a gentler introduction to your main equation (the one with the big O symbols) and defined or set up more components before displaying the equation. One way that might work is to claim and write down an equation for Min, then say Min is a context and that the Min example is a special case of, and then present the general form. My mind appreciates a graspable example just before a syntactically similar generalization. $\endgroup$ Jan 24, 2014 at 17:34
  • $\begingroup$ @The Masked Avenger: Thank you for insightful comments. This preprint was composed in rush (for a conference submission) and I plan to improve it significantly in further revisions. $\endgroup$ Jan 24, 2014 at 17:45
  • $\begingroup$ This impresses me as a (potentially very instructive) example of applied category theory. Even if it turns out to be an instance of something that (say) Michael Barr wrote up some time ago, I could see this as motivation to learn more category theory. $\endgroup$ Jan 24, 2014 at 18:17
  • $\begingroup$ I've just posted an updated version to arxiv. Please let me know if it addresses your concerns. $\endgroup$ Apr 22, 2014 at 0:30
2
$\begingroup$

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
$\endgroup$
2
  • $\begingroup$ I've tested invphi.gp on PARI/GP 2.6.2 and it works fine. Could you please tell me what exactly the problem you are experiencing with my code? Thanks! $\endgroup$ Jan 21, 2014 at 18:27
  • $\begingroup$ @MaxAlekseyev I suppose I backported it to older pari/gp for backwards compatibility (pari/gp versions are not fully compatible and the code didn't work for me at the time). Your code indeed works on new pari/gp. $\endgroup$
    – joro
    Jan 21, 2014 at 18:48
1
$\begingroup$

Of course you should also take a look at This OEIS entry, and to the references within.

$\endgroup$
0
$\begingroup$

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.

Gerhard "Ask Me About System Design" Paseman, 2012.10.12

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.