Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It's well-known that $$ \liminf_n\frac{\varphi(n)\log\log n}{n}=e^{-\gamma} $$ and there exists an effective version $$ \varphi(n)>\frac {n}{e^\gamma\log\log n+\frac{3}{\log\log n}} $$ valid for $n\ge3.$ Of course the RHS is increasing and so has an inverse, but I would like to know if there is an explicit formula (giving a tight bound) with $$ \varphi(f(n))>n. $$

Is this too much to ask?

share|improve this question
1  
Would you mind and tell up what $\varphi$ is? –  Dirk Jul 17 '12 at 15:35
    
Euler's totient function, oeis.org/A000010. –  Charles Jul 17 '12 at 15:36
    
Are you asking whether there is readily available (non-asymptotic) inverse bound? Or are you looking for something tighter than what can be extracted from the lower bound on $\phi(n)$? –  Erick Wong Jul 17 '12 at 18:06
1  
@ErickWong: Something more explicit than "the inverse of n/(e^gamma ...)" but hopefully not much weaker than that. Something that's asymptotically the right size, at least -- $e^\gamma n\log\log n.$ –  Charles Jul 17 '12 at 18:57
    
The function is tabulated at oeis.org/A139795 but no estimates are given. It is closely related to oeis.org/A137315 and maybe the references at that sequence would be helpful. –  Gerry Myerson Jul 18 '12 at 1:17

1 Answer 1

up vote 1 down vote accepted

Assume we're going to find a bound of the form $n<f(n) < n\log n$ (at least for $n$ large enough) so $$ \begin{align} \log n < \log f & < \log n+\log\log n\\ \log\log n < \log \log f & < \log(\log n + \log\log n)\\ \end{align} $$ Then from your bound $\phi(f)<n$ requires that $$ f < n \left(e^\gamma\log\log f+3/\log\log f\right) \\ f < n \log\log f (e^\gamma+3/(\log\log f)^2) \\ f < n\log(\log n + \log\log n)\left(e^\gamma+3/(\log\log n)^2\right) $$ So $$ N>n\log(\log n + \log\log n)\left(e^\gamma+3/(\log\log n)^2\right) \Rightarrow \phi(N)>n $$ I guess there may be a slightly better version, since the bound for $n=10^7$ gives $6.38\times 10^7$, whereas the last $N$ with $\phi(N)\le 10^7$ seems to be $58198540$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.