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.
Showing $\tau(n)/\phi(n)\to 0$ as $n\to \infty$
-
0Just use the formula for both in terms of the prime factorization and the fact that $(a+1)$ is much less than $p^{a-1}(p-1)$ for large $p$ and all $a$, and for large $a$ and all $p$. Close? – 2011-12-20
3 Answers
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}} $
Here's a hint: let $Q(n)$ denote the largest prime power that divides $n$. Then prove:
- $\displaystyle \frac{\tau(n)}{\phi(n)} \le 2 \frac{\tau(Q(n))}{\phi(Q(n))} \le \frac4{\log2} \frac{\log Q(n)}{Q(n)}$;
- $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.
-
1Never mind, I found a proof (there might be a simpler way) : given $M \in \mathbb{N}^*$ there is a finite number of prime powers lower than $M$ and $Q(n) \le M$ implies that $n$ is lower than their product. It means there's a finite number of integers $n$ with $Q(n) \le M$. – 2011-12-20
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
-
0Haha, I hadn't seen the URL... Google images, I swear! – 2011-12-20