Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Please avoid titles that are entirely in $\LaTeX$. –  J. M. Dec 19 '11 at 23:49
    
Just 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? –  fedja Dec 20 '11 at 0:00

3 Answers 3

up vote 4 down vote accepted

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$:

enter image description here

And also, here is a picture of a baby bear

share|improve this answer
3  
The gaygamer.net link is especially helpful :) –  Alex Youcis Dec 20 '11 at 3:23
    
Haha, I hadn't seen the URL... Google images, I swear! –  Bruno Joyal Dec 20 '11 at 3:42

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.
share|improve this answer
2  
That might be a naive question, but how do you show $Q(n) \to \infty$ ? –  Joel Cohen Dec 20 '11 at 0:10
1  
Never 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$. –  Joel Cohen Dec 20 '11 at 0:19

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}} $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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