12
$\begingroup$

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)$?

  • 0
    It can't be true because $\lim\inf\frac{\varphi(n)}{n}= 0$. See http://en.wikipedia.org/wiki/Euler's_totient_function#Growth_of_the_function for estimates of how $\varphi$ grows.2012-01-23

3 Answers 3

14

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

  • 0
    You are right . Can you find counterexample for : $\phi(n) > \frac{n}{6}$ ?2012-01-23
  • 6
    Yes, for example $2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23$ :)2012-01-23
26

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
    +1 for giving a proper, easy to understand explanation for the general case2012-01-23
  • 0
    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.$2012-01-23
  • 2
    Geoff: Yes, this is what I meant. The terminology is that infinite products _diverge_ to 0.2012-01-23
  • 0
    No, it's a the related sum $\sum\frac{1}{p}$ that diverges. The terminology is the same for products.2012-01-23
  • 0
    bgins: See lead of [Wikipedia on infinite product](https://en.wikipedia.org/wiki/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$.2012-01-23
22

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 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^*

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.

  • 0
    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))$?2013-11-21
  • 1
    @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.2015-05-14
  • 0
    Sorry to bump an old topic, but I *think* something doesn't add up (though by my lack of experience, I might be mistaken). The inequality $\varphi(n)\geq \frac{n}{e^{\gamma}\log \log n}$ follows from the theorem you stated, assuming $O(\cdot)$ is positive. But [Nicolas](https://en.wikipedia.org/wiki/Jean-Louis_Nicolas) proved that this inequality does not hold for infinitely many $n$'s. The correct form of the theorem seems to be $\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}$, see https://en.wikipedia.org/wiki/Euler%27s_totient_function#Growth_rate.2016-03-19
  • 0
    @M.S.Dousti: That's capture by the big-$O$ term in the expression I give above.2016-03-20
  • 0
    @EricNaslund: Thanks for the response. As I wrote in my comment, I built up my argument around the assumption that "$O(\cdot)$ is positive." If $O\left(\frac{n}{(\log \log n)^2}\right)$ is meant to capture a negative quantity (which is allowed under the definition of big-$O$), then everything adds up.2016-03-20
  • 0
    @M.S.Dousti: It does capture a negative quantity2016-03-21