Is the Euler phi function bounded below?

Question

I am working on a question for my number theory class that asks:

Prove that for every integer $n \geq 1$, $\phi(n) \geq \frac{\sqrt{n}}{\sqrt{2}}$.

However, I was searching around Google, and on various websites I have found people explaining that the phi function has a defined upper bound, but no lower bound. Am I reading these sites incorrectly, or am I missing something in the problem itself?

Answer 1

Let me begin with the explicit lower bound at LOWER, $$ \phi(n) > \frac{n}{e^\gamma \log \log n + \frac{3}{\log \log n}} $$ for $n>2.$

and then do your easier result separately. It is a procedure due to Ramanujan, in that we can explicitly find, for any $1 > \delta > 0,$ the integer that gives the minimum of $$ \frac{\phi(n)}{n^{1-\delta}} $$ My memory is that the optima always occur at primorials, but I will need to check. Oh, before I forget, it is theorem 327 on page 267 of Hardy and Wright that the fraction goes to infinity as $n$ goes to infinity, so it does attain a minimum.

Alright, checked, the minimum occurs at the primorial $2 \cdot 3 \cdot 5 \cdots p,$ the product of consecutive primes, where the $p$ is that largest prime that satisfies $$ p - 1 \leq p^{1 - \delta}. $$ So, with $\delta = 1/2,$ we find $2 - 1 \leq \sqrt 2,$ but $3-1 > \sqrt 3,$ so the minimum of $$ \frac{\phi(n)}{\sqrt n} $$ occurs at $n=2$ and $$ \phi(n) \geq \sqrt{ \frac{n}{ 2} }. $$

With $\delta = \log (3/2) / \log 3 = 0.36907\ldots,$ we find $3 - 1 \leq 3^{1-\delta},$ so the minimum of $$ \frac{\phi(n)}{n^{0.63092975\ldots}} $$ occurs at $n=2 \cdot 3 = 6$ and $$ \frac{\phi(n)}{n^{0.63092975\ldots}} \geq \frac{2}{6^{0.63092975\ldots}} = 0.645760\ldots. $$

It is not quite optimal, but prettier. Take $\delta = 1/3,$ we get $$ \frac{\phi(n)}{n^{2/3}} \geq \frac{2}{6^{2/3}}. $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

We already had, with $\delta = 1/2,$ $$ \phi(n) \geq \sqrt{ \frac{n}{ 2} }. $$

With $\delta = 1/3,$ we get $$ \phi(n) \geq 2 \cdot \left( \frac{n}{6} \right)^{2/3}. $$

Take $\delta = 1/8,$ we get $$ \phi(n) \geq 8 \cdot \left( \frac{n}{30} \right)^{7/8}. $$

Take $\delta = 1/13,$ we get $$ \phi(n) \geq 48 \cdot \left( \frac{n}{210} \right)^{12/13}. $$

Take $\delta = 1/26,$ we get $$ \phi(n) \geq 480 \cdot \left( \frac{n}{2310} \right)^{25/26}. $$

Take $\delta = 1/33,$ we get $$ \phi(n) \geq 5760 \cdot \left( \frac{n}{30030} \right)^{32/33}. $$

Take $\delta = 1/47,$ we get $$ \phi(n) \geq 92160 \cdot \left( \frac{n}{510510} \right)^{46/47}. $$

This is exactly the same procedure used in Ramanujan's Superior Highly Composite numbers and Alaoglu and Erdos' Colossally Abundant numbers, but I'm not sure I know anywhere that shows how you get the primorials. EDIT: I put a proof as a separate answer, also give reference for the relationship to the Riemann Hypothesis, due to Jean-Louis Nicolas.

Answer 2

You’ll find a complete proof of the result in the appendix of this paper. Here’s a hint to give you a start on doing it yourself.

First show that if $n$ is odd or a multiple of $4$, then $\varphi(n)\ge\sqrt n$; for this you’ll use the prime factorization of $n$ and the multiplicativity of $\varphi$. Then handle the case $n=2m$ with $m$ odd by using the multiplicativity of $\varphi$ to write $\varphi(n)=\varphi(2)\varphi(m)$.

Answer 3

EEDDIITT: this gives a proof of my main claim in my first answer, that a certain function takes its minimum value at a certain primorial. I actually put that information, with a few examples, into the wikipedia article, but it was edited out within a minute as irrelevant. No accounting for taste.

ORIGINAL: We take as given Theorem 327 on page 267 of Hardy and Wright, that for some fixed $0 < \delta < 1,$ the function $$ g(n) = \frac{\phi(n)}{n^{1-\delta}} $$ goes to infinity as $n$ goes to infinity.

Note that $g(1) = 1$ but $g(2) < 1.$ For some $N_\delta,$ whenever $ n > N_\delta$ we get $g(n) > 1.$ It follows that, checking all $1 \leq n \leq N_\delta,$ the quantity $g(n)$ assumes a minimum which is less than 1. Perhaps it assumes this minimum at more than one point. If so, we are taking the largest such value of $n.$

Here we are going to prove that the value of $n$ at which the minimum occurs is the primorial created by taking the product of all the primes $p$ that satisfy $$ p^{1-\delta} \geq p-1. $$ As I mentioned, in case two the minimum occurs at two different $n,$ this gives the larger of the two.

So, the major task of existence is done by Hardy and Wright. We have the minimum of $g$ at some $$ n = p_1^{a_1} p_2^{a_2} p_3^{a_3} \cdots p_r^{a_r}, $$ with $$ p_1 < p_2 < \cdots < p_r. $$

First, ASSUME that one or more of the $a_i > 1.$ Now, $$ \frac{ g(p_i)}{g(p_i^{a_i})} = p^{\delta - a_i \delta} = p^{\delta (1 - a_i)} < 1. $$ As a result, if we decrease that exponent to one, the value of $g$ is lowered, contradicting minimality. So all exponents are actually 1.

Second, ASSUME that there is some gap, some prime $q < p_r $ such that $q \neq p_j$ for all $j,$ that is $q$ does not divide $n.$ Well, for real variable $x > 0,$ the function $$ \frac{x-1}{x^{1-\delta}} $$ is always increasing, as the first derivative is $$ x^{\delta - 2} (\delta x +(1-\delta)). $$ It follows that, in the factorization of $n,$ if we replace $p_r$ by $q,$ the value of $g$ is lowered, contradicting minimality. So the prime factors of $n$ are consecutive, beginning with 2, and $n$ is called a primorial.

Finally, what is the largest prime factor of $n?$ Beginning with 2, multiplying by any prime $p$ with $$ \frac{p-1}{p^{1-\delta}} \leq 1 $$ shrinks the value of $g$ or keeps it the same, so in demanding the largest $n$ in case there are two attaining the minimum of $g,$ we take $n$ to be the product of all primes $p$ satisfying $$ p - 1 \leq p^{1-\delta}, $$ or $$ p^{1-\delta} \geq p-1 $$ as I first wrote it.

Examples are given in my first answer to this same question.

EEDDIITTTT: Jean-Louis Nicolas showed, in 1983, that the Riemann Hypothesis is true if and only if, for all primorials $P,$ $$ \frac{e^\gamma \phi(P) \log \log P}{P} < 1. $$ Alright, the exact reference is: Petites valeurs de la fonction d'Euler. Journal of Number Theory, volume 17 (1983), number 3, pages 375-388.

On the other hand, if RH is false, the inequality is true for infinitely many primorials and false for infinitely many. So, either way, it is true for infinitely many primorials (once again, these are $P = 2 \cdot 3 \cdot 5 \cdots p$ the product of consecutive primes beginning with 2).

For whatever reason, the criterion of Guy Robin, who was a student of Nicolas, got to be better known.

Answer 4

Firstly: the function $\phi(n)$ does not have the lower limit in the form of a straight line with a positive slope.
This follows from the formula $$\dfrac{\phi(n)}n = \prod\limits_{p\,|\, n}\dfrac{p-1}p,$$ formula, which illustrates non-increasing of $\dfrac{\phi(n)}n$.

Analysis of the formula leads to the following conclusions for : $$\dfrac{\phi(np^k)}{np^k} = \begin{cases}\dfrac{\phi(n)}{n},\text{ if }p\,|\,n\\\dfrac{\phi(n)}{n}\dfrac{p-1}p,\text{ if }p\!\not|\:n\end{cases}$$ These findings can be illustrated by a simple table:

So, not difficult to prove that $$\dfrac{\phi(n)}n \geq H(n),$$ where $H(n)$ is a step function $$H(n) = \begin{cases} \dfrac12,\text{ if } n \in [2,6)\\ \dfrac13,\text{ if } n \in [6,30)\\ \dots\\ r_k,\text{ if } n \in [p_k\#, p_{k+1}\#)\\ \dots, \end{cases}$$
$\qquad p_k\# = \prod\limits_{i=1}^{k}p_i$ is primorial, $$\left\{p_k\#\right\}=\{2,6,30,210,2310,30030,510510,96996900,223092870,6469693230,\dots\}$$ $$r_k = \dfrac1{p_k\#}\prod\limits_{i=1}^{k}(p_i-1),\dots, \quad \{r_k\}=\left\{\dfrac12,\dfrac13,\dfrac4{15},\dfrac8{35},\dfrac{16}{77},\dfrac{192}{1001},\dfrac{3072}{17017},\dfrac{55396}{323323},\dfrac{110592}{676039},\dfrac{442368}{2800733},\dots\right\}$$ $$\{p_i\}=\{2,3,5,\dots\}.$$ This function is susceptible to various approximations.

As $p_i\geq i,$ then for not increasing consequence $R_k$ is valid ratio $$r_k = \prod\limits_{i=1}^k\left(1-\dfrac1{p_i}\right)\geq \prod\limits_{i=1}^k\left(1-\dfrac1{i+1}\right) = \dfrac1{k+1}.$$ On the other hand, is not difficult to prove that $$p_k\#\geq k(k+1).$$ So for $(k-1)k < n \leq k(k+1):$ $$\sqrt{n}>k-1,$$ $$\dfrac{\phi(n)}n \geq\dfrac1{k(k+1)}\phi\left(k(k+1)\right) \geq \dfrac {\phi(p_k\#)}{p_k\#}=r_k \geq \dfrac1{k+1} > \dfrac1{\sqrt n +2}.$$ $$\boxed{\phi(n) \geq \dfrac n{\sqrt n+2}},$$