Showing $\tau(n)/\phi(n)\to 0$ as $n\to \infty$

Question

I was wondering how to show that $\tau(n)/\phi(n)\to 0$, as $n\to \infty$. Here $\tau(n)$ denotes the number of positive divisors of n, and $\phi(n)$ is Euler's phi function.

Answer 1

Note that for an odd integer $n>1$, we have $\tau(n)/\varphi(n)<1$ (first note it for an odd prime-power, then by multiplicativity to all odd $n$).

For each $\epsilon>0$, consider the set $S_\epsilon$ of those odd $n$'s with $\tau(n)/\varphi(n)>\epsilon$. Write $n=p_1^{\alpha_1}\dots p_k^{\alpha_k}$, where $p_1, \dots, p_k$ are odd. Then

$$\frac{\alpha_1+1}{p_1^{\alpha_1}} \dots \frac{\alpha_1+1}{p_1^{\alpha_1}}>\epsilon$$

and since each term of the product is $<1$, each term must itself be $>\epsilon$. Hence, for each $i$,

$$\frac{1+\alpha_i}{p_i^{\alpha_i}}>\epsilon.$$

Clearly there are finitely combinations of $p$ and $\alpha$ which satisfy this. Hence $S_\epsilon$ is finite. Now for a general integer $n=2^mn'$ where $n'$ is odd and with $\tau(n)/\varphi(n)> \epsilon$, note that $\tau(n)/\varphi(n)<2\tau(n')/\varphi(n')$, so there are finitely many choices for $n'$, and $\tau(n)/\varphi(n)<\frac{m+1}{2^m}$ so there are finitely many choices for $m$.

Hence, for every $\epsilon>0$, there are finitely many integers $n$ with $\tau(n)/\varphi(n)>\epsilon$.

Here is a plot of $\tau(n)/\varphi(n)$ for $n<10^5$:

And also, here is a picture of a baby bear

Answer 2

Here's a hint: let $Q(n)$ denote the largest prime power that divides $n$. Then prove:

1. $\displaystyle \frac{\tau(n)}{\phi(n)} \le 2 \frac{\tau(Q(n))}{\phi(Q(n))} \le \frac4{\log2} \frac{\log Q(n)}{Q(n)}$;
2. $Q(n) \to \infty$ as $n\to \infty$. For #1, you'll want to use the fact that $\tau(n)/\phi(n)$ is multiplicative, as well as the explicit evaluations of them on prime powers.

Answer 3

There is methodology for dealing separately with numerator and denominator, initiated by Ramanujan. The construction of "superior highly composite" numbers gives:

$$ \tau(n) \; \leq \; \; 24 \; \; \left( \frac{n}{315} \right)^{(1/3)} $$

The related argument, with a certain type of optima at the primorials, gives

$$ \phi(n) \geq \frac{2 n^{2/3}}{6^{2/3}},$$

and together we get

$$ \frac{\tau(n)}{\phi(n)} \leq \frac{12 \; \cdot \; 4^{1/3}}{ 35^{1/3} \; \; n^{1/3}} \; = \; \frac{5.823426...}{n^{1/3}} $$

EDIT, Tuesday, 20 December: very little machinery is required to describe how to get very small values of $\phi(n)$ relative to the size of $n,$ then derive useful inequalities from that information. Given some $1 \geq \delta > 0,$ we wish to find the number $N_\delta$ that gives the smallest value of $$ f(n) = \frac{\phi(n)}{n^{1-\delta}}.$$ We see that $f(1) = 1.$ Furthermore, if we have some $n$ that is not divisible by a prime $p,$ then $f(np) = f(n) f(p),$ and we shrink the result if we multiply by $p$ when $f(p) < 1.$ At the same time, if $n$ is already divisible by $p,$ multiplying by $p$ always increases $f,$ so $N_\delta$ will be squarefree in any case. So that is the recipe, $N_\delta$ is the (finite) product of the primes $p$ for which $$ p^{1-\delta} \geq p-1.$$ The derivative of $x^{1-\delta} - x + 1$ is $(1-\delta) x^{-\delta} -1,$ and this is negative for $x \geq 1,$ while the second derivative $-\delta (1-\delta) x^{-1-\delta}$ is also negative there, so at some point $x^{1-\delta} - x + 1$ becomes $0$ and then negative thereafter. As a result, $N_\delta$ is the product of the consecutive primes up to some point. These are called primorials.

Meanwhile the first (largest) $\delta$ that includes a prime $p$ is $$ \delta_p = \frac{\log \left( 1 + \frac{1}{p-1} \right)}{\log p} $$

Taking $\delta = 1/3,$ we get $N_{1/3}=6$ and $1 -\delta = 2/3,$ so we always have $$ \frac{\phi(n)}{n^{2/3}} \geq \frac{\phi(6)}{6^{2/3}} = \frac{2}{6^{2/3}} $$