Upper bound for Euler's totient function on composite numbers

Question

I've seen before the general bound $\phi(n) \leq n - n^{1/2}$ for composite $n$. Can this bound be improved at least for those $n$ when we don't have equality above? Say could we possibly have at least $\phi(n) \leq n - kn^{1/2}$ for some $k > 1$?

Answer 1

Let $n=p^2$. Then $\varphi(n)=p^2-p=n-\sqrt{n}$. So we have equality for infinitely many $n$.

If $n=p^e$ where $e\gt 2$, then $\varphi(n)=p^e-p^{e-1}=n-n^{1-1/e}$. Worst case is $e=3$, $p=2$. In this case we have $n^{2/3}\ge kn^{1/2}$ where $k=2^{1/6}$. Thus $\varphi(n)\le n-2^{1/6}n^{1/2}$.

If $n=ab$ where $a$ and $b$ are greater than $1$ and relatively prime, then $\varphi(n)=\varphi(ab)\le (a-1)(b-1)=n-(a+b)+1$. Note that $a+b\gt 2\sqrt{n}$, so we get $\varphi(n)\le n-2\sqrt{n}+1$ in this case.

Answer 2

Well, if $n$ is the product of consecutive primes you get $\phi(n) > n - 2 \sqrt n,$ but it gets close, and you can probably take your $k = 1.5$ for $n>8$ say

2   16 = 2^4
1.999437280176435   1333 = 31 * 43
1.999118949876075   7663 = 79 * 97
1.99871723147485   8383 = 83 * 101
1.998342529102684   2867 = 47 * 61
1.99824032638073   9523 = 89 * 107
1.998065959315103   5561 = 67 * 83
1.997420223212713   6497 = 73 * 89
1.996970389115528   3551 = 53 * 67
1.996107193636781   4307 = 59 * 73
1.99504678865167   2173 = 41 * 53
1.994932096041783   8051 = 83 * 97
1.994893666788084   9167 = 89 * 103
1.993950461300493   2773 = 47 * 59
1.993453519963639   8989 = 89 * 101
1.993124970314336   4189 = 59 * 71
1.993082580330997   4453 = 61 * 73
1.993073020359085   5893 = 71 * 83
1.993044773767945   5293 = 67 * 79
1.991741189771645   91 = 7 * 13
1.991626618969993   7031 = 79 * 89
1.991524132758911   1271 = 31 * 41
1.991274911100793   6059 = 73 * 83
1.991089847651314   8633 = 89 * 97
1.990896104916204   9991 = 97 * 103
1.990568850865158   4331 = 61 * 71
1.990344721501349   1739 = 37 * 47
1.990305174632736   9797 = 97 * 101
1.989992514114262   2279 = 43 * 53
1.989582997411111   7387 = 83 * 89
1.989498190165494   5609 = 71 * 79
1.988391837175112   5767 = 73 * 79
1.988260497982835   6557 = 79 * 83
1.988138364484967   3953 = 59 * 67
1.987540416848836   4891 = 67 * 73
1.987355637820889   3233 = 53 * 61
1.986558698771642   4087 = 61 * 67
1.986341843827027   4757 = 67 * 71
1.986302700472586   5183 = 71 * 73
1.984993267773272   3127 = 53 * 59
1.984865598623816   713 = 23 * 31
1.984328160336157   1073 = 29 * 37
1.983608853697701   3599 = 59 * 61
1.983573651759631   2491 = 47 * 53
1.981884747156589   1927 = 41 * 47
1.980578231727406   1591 = 37 * 43
1.979734037185575   2021 = 43 * 47
1.9783042944476   1147 = 31 * 37
1.976960238957923   1517 = 37 * 41
1.976750859152595   1763 = 41 * 43
1.974727886289034   667 = 23 * 29
1.974435545143253   187 = 11 * 17
1.972482765224911   247 = 13 * 19
1.972314775954277   391 = 17 * 23
1.967760170596957   899 = 29 * 31
1.963961012123931   21 = 3 * 7
1.961295980263253   437 = 19 * 23
1.950751102589306   221 = 13 * 17
1.9474520942613   323 = 17 * 19
1.937329799813845   77 = 7 * 11
1.923356623016309   143 = 11 * 13
1.897366596101028   10 = 2 * 5
1.859339360402736   35 = 5 * 7
1.807392228230128   15 = 3 * 5
1.732050807568877   27 = 3^3
1.632993161855452   6 = 2 * 3
1.414213562373095   8 = 2^3
jagy@phobeusjunior:~$ 
    jagy@phobeusjunior:~$ 

Answer 3

We have the formula $$ \phi(n)=n\prod_{\substack{p\mid n\\p\text{ prime}}}\left(1-\frac1p\right)\tag{1} $$ For a composite $n$, the smallest prime $p_0\mid n$ is at most $\sqrt{n}$, so $(1)$ implies $$ \begin{align} \phi(n) &\le n\left(1-\frac1{p_0}\right)\\ &\le n\left(1-\frac1{\sqrt{n}}\right)\\ &=n-\sqrt{n}\tag{2} \end{align} $$ Furthermore, for $n=p^2$, $$ \phi(p^2)=p^2-p\tag{3} $$ Thus, we can find an arbitrarily large composite $n$ so that $\phi(n)=n-\sqrt{n}$.

If we don't have equality as in $(3)$, we have either $n=p^k$ or $n$ has two distinct prime factors. $$ \phi(p^k)=p^k-p^{k-1}\tag{4} $$ Thus, for $k\ge3$ $$ \frac{n-\phi(n)}{\sqrt{n}}=\frac{p^{k-1}}{p^{k/2}}=p^{k/2-1}=n^{1/2-1/k}\ge n^{1/6}\tag{5} $$ so if we are looking for the smallest $\frac{n-\phi(n)}{\sqrt{n}}$, we need to look at $n=pq$. We get $$ \frac{pq-\phi(pq)}{\sqrt{pq}}=\frac{p+q-1}{\sqrt{pq}}=\frac{\sqrt{p}}{\sqrt{q}}+\frac{\sqrt{q}}{\sqrt{p}}-\frac1{\sqrt{pq}}\tag{6} $$ Since $x+\frac1x=2+\left(\sqrt{x}-\frac1{\sqrt{x}}\right)^2\ge2$, with equality only when $x=1$, we have that if $n$ has two distinct prime factors, $$ \frac{n-\phi(n)}{\sqrt{n}}\gt2-\frac1{\sqrt{n}}\implies\phi(n)\lt n-2\sqrt{n}+1\tag{7} $$ Furthermore, inequality $(5)$ guarantees that inequality $(7)$ holds if $n\ge39$ and $n$ is not a prime or the square of a prime.

---

Checking the integers less than $39$, we see that if $n$ is not a prime or the square of a prime and $n\ne8$ and $n\ne27$, then $(7)$ holds.