# Lower bound for $\phi(n)$: Is $n/5 < \phi (n) < n$ for all $n > 1$?

Is it true that :

$\frac {n}{5} < \phi (n) < n$ for all $n > 1$

where $\phi (n)$ is Euler's totient function .

Since $\phi(n)$ has maximum value when $n$ is a prime it follows that maximum value of $\phi(n)$ in term of $n$ is $n-1$ , therefore $\phi(n)< n$ for all $n$.

What is the best lower bound for $\phi(n)$?

-
It can't be true because $\lim\inf\frac{\varphi(n)}{n}= 0$. See en.wikipedia.org/wiki/… for estimates of how $\varphi$ grows. –  lhf Jan 23 '12 at 15:11

The statement is false, with the first counterexample being 30030, for which $\phi(30030) = 5760 < \frac{30030}{5} = 6006$.

Also, if it's of any interest, all counterexamples below 10 million have at least 6 distinct prime divisors. For example, $30030 = 2 \times 3 \times 5 \times 7 \times 11 \times 13$.

-
You are right . Can you find counterexample for : $\phi(n) > \frac{n}{6}$ ? –  pedja Jan 23 '12 at 14:41
Yes, for example $2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23$ :) –  Sp3000 Jan 23 '12 at 14:44

Since $\phi(n)=n (1-\frac{1}{p_1}) \dots (1-\frac{1}{p_k})$ (where $n=p_1^{a_1} \dots p_k^{a_k}$), it is equivalent to asking if $(1-\frac{1}{p_1}) \dots (1-\frac{1}{p_k}) > \frac{1}{5}$, the minimal counterexample must be a product of first $k$ primes (because taking a smaller prime decreases the product); by direct calculation $2 \cdot 3 \cdot \dots \cdot 13 = 30030$ gives about 0.192. In general the product diverges to 0, which follows from this proof. So your inequality is not true even if you replace 5 with a larger, fixed number, and the smallest counterexample will be the product of $k$ first primes for some $k$.

-
+1 for giving a proper, easy to understand explanation for the general case –  Sp3000 Jan 23 '12 at 14:48
I think you mean the product $\prod_{k=1}^{\infty}( 1 - \frac{1}{p_k} )$ is $0$, that is the sequence of partial products converges to $0.$ –  Geoff Robinson Jan 23 '12 at 15:00
Geoff: Yes, this is what I meant. The terminology is that infinite products diverge to 0. –  sdcvvc Jan 23 '12 at 15:06
No, it's a the related sum $\sum\frac{1}{p}$ that diverges. The terminology is the same for products. –  bgins Jan 23 '12 at 15:12
bgins: See lead of Wikipedia on infinite product. The proof that $\sum \frac{1}{p}$ diverges uses that product (precisely, its inverse $\prod_p \frac{1}{1-p^{-1}}$), you can also show it via $\prod_{k=1}^{n} (1-\frac{1}{p_k}) \leq \prod_{k=1}^{n} \exp(-1/p_k)=\exp(-\sum_{k=1}^{n} 1/p_k) \to 0$. –  sdcvvc Jan 23 '12 at 15:20

As the other answers have pointed out, the answer is no, and this remains true if we replace $5$ with any larger integer. This raises the question, what is the optimal lower bound? The following theorem completely answers this:

Theorem: For all $n\geq 3$ we have $$\phi(n)\geq \frac{n}{e^{\gamma}\log \log n}+O\left(\frac{n}{(\log \log n)^2}\right),$$ where $\gamma$ is the Euler-Mascheroni Constant, and the above holds with equality infinitely often.

Remark: Note in particular that since $\log \log n\rightarrow \infty$ as $n$ grows large, we see that the result $\frac{n}{m}<\phi(n)$ cannot hold for any fixed integer $m$.

Proof: Consider $\mathcal{R}$, the set of all $n$ such that $m<n$ implies $\frac{\phi(n)}{n}<\frac {\phi(m)}{m}$. This set is then all of the "record breaking" $n$. If $n\in\mathcal{R}$ has $k$ prime factors, let $n^*$ be the product of the first $k$ prime factors. If $n\neq n^*$, then $n^*<n$ and $\frac{\phi(n^*)}{n^*}\leq \frac{\phi(n)}{n}$, which is impossible. Hence $\mathcal{R}$ consist entirely of $n$ of the form $n=\prod_{p\leq y}p$ for some $y$.

Now for $n\in \mathcal{R}$, we can choose $y$ so that $\log n=\sum_{p\leq y} \log p=\theta (y)$. Then using one of Mertens estimates we see that $$\frac{\phi(n)}{n}=\prod_{p\leq y}\left(1-\frac{1}{p}\right)=\frac{e^{-\gamma}}{\log y}+O\left(\frac{1}{(\log y)^2}\right).$$ Since $\log \log n =\log (\theta(y))=\log y+O(1)$ by Mertens estimates again, we have for $n\in\mathcal{R}$ $$\phi(n)=\frac{ne^{-\gamma}}{\log\log n}+O\left(\frac{1}{(\log \log n)^2}\right).$$ This along with the definition of $\mathcal{R}$ implies the desired result.

Edit: Added in the proof. This proof and statement of the result is Theorem 2.9 in Montgomery and Vaughn's multiplicative number theory.

-
Hi Eric. I know this is a very old answer, so please forgive me for asking a question on it. But I was wondering about some of the notation here, which I've noticed is very common in number theory. Firstly, what does the statement $f(n) \geq g(n) + O(h(n))$ mean? Is it the same as "$f(n) \geq k(n)$ for some function $k$ which has the property that $k(n) = g(n) + O(h(n))$"? In that case do we have enough information to determine whether $f(n) \geq g(n)$ or $f(n) \leq g(n)$? Secondly, what does it mean for equality to hold in an asymptotic inequality like $f(n) \geq g(n) + O(h(n))$? –  Antonio Vargas Nov 21 '13 at 15:03
@AntonioVargas Yes to your first question, and no, it is not quite strong enough to imply that $f(n) \ge g(n)$. For the last question, it means (in the context of the statement) that there is an infinite sequence of integers $n$ such that $f(n) = g(n) + O(h(n))$ for $n$ restricted to that sequence. You're right that equality at a particular integer doesn't hold much meaning for an asymptotic. –  Erick Wong May 14 at 23:19