5
$\begingroup$

Trying to derive an elementary bound for Euler totient function $\varphi(n)$ to be $\mathcal{O}(\frac n{\log(\log(n))})$, I thought to prove a weak version of the well-known inequality $${\displaystyle \varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}\quad {\text{for }}n>2}$$ for large integers $n\in\mathbb{N}$.
Simplest modification of the theorem would be considering $$n>e^{e^3} \implies 2\log(\log(n))>e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}$$ And hence deriving $\varphi(n)>\frac{n}{2\log(\log(n))}$.
I was then stuck trying to prove this.
I've reached bounds of other orders in non-analytic methods (such as $\varphi(n)>\frac{6n}{\pi^2(1+\log(n))}$ and $\varphi(n)>\frac n{4\log(n)}$ ) but I've had no progress trying to prove bounds of this order. (Proving the bound with any other constant would also count, so it's basically enough to prove that $\varphi(n)\ge\frac n{c\log(\log(n))}$ for some $c\in\mathbb{R}^+$ for all $n>N$ where $N$ is a fixed positive integer, $e^{e^3}$ in my case)

Any hints or ideas would be appreciated!

$\endgroup$
3
  • $\begingroup$ See here. It relies on Mertens' theorems, but are not exactly elementary due to their relations to PNT. $\endgroup$
    – TheSimpliFire
    Jul 28, 2022 at 8:14
  • $\begingroup$ I've checked it out before but I need something that fully relies on elementary number theory. Merten's theorem itself is not an elementary theorem $\endgroup$
    – Aryan
    Jul 28, 2022 at 9:36
  • $\begingroup$ @TheSimpliFire Mertens' theorems are themselves elementary, and proofs of them do not require PNT. $\endgroup$
    – TravorLZH
    Jul 28, 2022 at 15:22

1 Answer 1

3
$\begingroup$

By elementary, I mean "without the use of complex analysis." Using elementary methods (not as deep as PNT), it is possible to show that $$ \prod_{p\le x}\left(1-\frac1p\right)={e^{-\gamma}\over\log x}\left\{1+O\left(1\over\log x\right)\right\}. $$ This indicates that when $1\le t\le n$, there is \begin{aligned} {\varphi(n)\over n} &\ge\prod_{p\le t}\left(1-\frac1p\right)\prod_{\substack{p|n\\p>t}}\left(1-\frac1p\right) \\ &\ge{e^{-\gamma}\over\log t}\left(1-\frac1t\right)^s\left\{1+O\left(1\over\log t\right)\right\}, \end{aligned} where $s$ denotes the number of prime divisors of $n$ that are greater than $t$, which satisfies $$ s=\sum_{\substack{p|n\\p>t}}1\le\sum_{p|n}{\log p\over\log t}\le{\log n\over\log t} $$ Thus, we see that when $t=\log n$, there is $$ -\log\left(1-\frac1t\right)^s=\frac st\left\{1+O\left(\frac1t\right)\right\}\le{\log n\over t\log t}\left\{1+O\left(\frac1t\right)\right\}=O\left(1\over\log\log n\right). $$ Plugging this result back gives us the lower bound as follows $$ {\varphi(n)\over n}\ge{e^{-\gamma}\over\log\log n}+O\left(1\over(\log\log n)^2\right).\tag1 $$ To see why this is the best bound possible, set $n_k$ to be the product of the first $k$ primes. Then we have $$ {\varphi(n_k)\over n_k}=\prod_{1\le i\le k}\left(1-{1\over p_i}\right)={e^{-\gamma}\over\log p_k}\left\{1+O\left(1\over\log p_k\right)\right\}. $$ Because Chebyshev's bounds ensures that there exists $c_2>c_1>0$ such that $c_1p_k<\log n_k<c_2p_k$ for large $k$, we have $$ \log\log n_k=\log p_k\left\{1+O\left(1\over\log p_k\right)\right\}=\log p_k\left\{1+O\left(1\over\log\log n_k\right)\right\}, $$ which indicates that (1) holds with equality if $n=n_k$.

$\endgroup$
8
  • $\begingroup$ Thanks for noting this out but do you know how I can achieve explicit non-asymptotic bounds like the ones I asked for (not in big O forms) since I'm trying to fing explicit numerical bounds for a function and this wouldn't help much $\endgroup$
    – Aryan
    Jul 29, 2022 at 12:23
  • $\begingroup$ There's not going to be any method much easier than taking a proof like this and doing every step with explicit constants. $\endgroup$ Jul 29, 2022 at 20:22
  • 1
    $\begingroup$ And what elementary methods are these, that produce the first equation? $\endgroup$
    – FShrike
    Jul 29, 2022 at 20:40
  • $\begingroup$ @GregMartin I guess you got it the wrong way. It doesn't matter if the solution is complicated, I just need it to be "elementary" (not using analytic/algebraic number theory methods) Let's say I have a function $f(n)=g(n)\cdot\varphi(n)$ and I need to find a positive integer $n_0$ such that $f(n)>k$ for all $n\ge n_0$ where $k$ is an arbitrary integer. And I got a non-asymptotic lower bound for $g(n)$. That's why I need a non-asymptotic lower bound for totient function. $\endgroup$
    – Aryan
    Jul 29, 2022 at 21:53
  • $\begingroup$ @FShrike Look up Hardy & Wright's An Introduction to the Theory of Numbers, where the authors proved a variety of number-theoretic theorems via elementary methods. $\endgroup$
    – TravorLZH
    Jul 30, 2022 at 3:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .