3
$\begingroup$

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?

  • 1
    Would you mind and tell up what $\varphi$ is?2012-07-17
  • 0
    Euler's totient function, https://oeis.org/A000010.2012-07-17
  • 0
    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)$?2012-07-17
  • 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.$2012-07-17
  • 0
    The function is tabulated at http://oeis.org/A139795 but no estimates are given. It is closely related to http://oeis.org/A137315 and maybe the references at that sequence would be helpful.2012-07-18
  • 0
    @GerryMyerson: I just need the smooth version, the much harder question solved at A139795 is too computationally intensive for my needs.2012-07-18

1 Answers 1

1

Assume we're going to find a bound of the form $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) 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$.