It seems that as $n$ increases, the ratio $$\frac{\varphi(2^n-1)}{2^n-1},$$ where $\varphi$ denotes the Euler totient function, takes on values reasonably often in the interval $(.3,.4)$.

Is there anything known about $$\lim \inf_{n \rightarrow \infty}\frac{\varphi(2^n-1)}{2^n-1}?$$

  • $\begingroup$ Pardon my ignorance, but what is $\varphi$? $\endgroup$ – Dirk Oct 16 '17 at 7:15
  • $\begingroup$ @Dirk The Euler Totient function. $\varphi(n)$ is the number of numbers smaller than $n$ that are coprime to $n$. So $\varphi(n)/n$ is close to 1 for $n$ prime and and smaller if $n$ has more divisors. $\endgroup$ – Vincent Oct 16 '17 at 7:55
  • $\begingroup$ Note that $2^{12} -1$ is a multiple of 105, giving that the ratio above is at most $16/35$ or about $0.457$. I would expect many small $n$ producing ratios in $(0.3,0.4)$ to be multiples of 12. I imagine the first $n$ to do so that isn't a multiple of 12 would have three or more decimal digits. Gerhard "Primitive Factors Grow Pretty Fast" Paseman, 2017.10.16. $\endgroup$ – Gerhard Paseman Oct 16 '17 at 16:29

Let $n \in \mathbf N^+$ and $a \in \mathbf N_{\ge 2}$. Every prime $\le n+1$ that doesn't divide $a$, is a divisor of $a^{n!} - 1$ (by Fermat's little theorem). So we have $$\frac{\varphi(a^{n!} - 1)}{a^{n!} - 1} = \prod_{p \,\mid\, a^{n!} - 1} \left(1 - \frac{1}{p}\right) \le \prod_{a < p \le n+1} \left(1 - \frac{1}{p}\right)\! \stackrel{n \to \infty}{\longrightarrow} 0,$$ where $p$ is always a prime and for the first equality we have used Euler's product formula. In particular, this shows that the limit inferior in the OP is $0$.

  • $\begingroup$ Nice. I presume from your proof that a lower bound of $c \cdot \log n$ could be obtained in the equation above, thus implying $$\lim \inf \log n \frac{\varphi(a^{(2n)!}-1)}{a^{(2n)!}-1}>0$$ $\endgroup$ – kodlu Oct 17 '17 at 23:43
  • $\begingroup$ @kodlu Maybe you're right, but how so? It's (well) known, see, e.g., Theorem 328 in (the 1979 edition of) Hardy & Wright's An Introduction to the Theory of Numbers, that $\liminf \frac{\varphi(n)}{n} \log \log n = e^{-\gamma}$, where $\gamma$ is Euler's constant. This, combined with Stirling's formula, yields $\liminf \frac{\varphi(a^{n!} - 1)}{a^{n!}-1} n \log n > 0$, which, however, looks much weaker than the inequality you're suggesting. By the way, I'm editing the answer above, because I don't see the reason why I used $(2n)!$ as an exponent instead of $n!$. $\endgroup$ – Salvo Tringali Oct 18 '17 at 10:10
  • $\begingroup$ @kodlu On a closer look, your conclusion is correct (at least for $a=2$, but this shouldn't make any real difference): Erdős showed in Israel J. Math. 9 (1971), 43-48 that there is a constant $c > 0$ s.t. $\sigma(2^n-1)/(2^n-1)\le c \log\log n$ for all $n$, where $\sigma$ is the sum-of-divisors function. On the other hand, it is not difficult to prove that $\varphi(n)\sigma(n)>\frac{6}{\pi^2}n^2$ for all $n$. So, putting it all together, we have $\liminf \frac{\varphi(2^n-1)}{2^n-1}\log \log n > 0$, which implies your inequality, since $\log \log n! \sim \log n$ by Stirling's formula. $\endgroup$ – Salvo Tringali Oct 18 '17 at 11:15
  • $\begingroup$ It is more economical to use $\prod_{p\leq n+1} p$ instead of $n!$ in the exponent. The former product is $(e+o(1))^n$ by the prime number theorem, so much smaller than $n!$. Of course when you take $\log\log$, it does not matter. $\endgroup$ – GH from MO Oct 18 '17 at 21:14
  • 1
    $\begingroup$ @SalvoTringali: Let me correct myself. Consider $N:=\prod_{a<p\leq n+1}(p-1)$, where $p$ runs through primes. Then, on the one hand, $N<\prod_{p\leq n+1}p=(e+o(1))^n$. One the other hand, for any prime $a<p\leq n+1$, we have that $p\mid a^{p-1}-1\mid a^N-1$. So $\varphi(a^N-1)/(a^N-1)$ is at most $\prod_{a< p\leq n+1}(1-p^{-1})$, which tends to zero as in your post. The point is that $N$ is much smaller than $n!$, namely $\log N\sim n$, while $\log n!\sim n\log n$. Of course, $\log\log N$ is asymptotically $\log\log n$, just like $\log\log n!$. $\endgroup$ – GH from MO Oct 20 '17 at 0:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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