8
$\begingroup$

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}?$$

$\endgroup$
3
  • $\begingroup$ Pardon my ignorance, but what is $\varphi$? $\endgroup$
    – Dirk
    Oct 16, 2017 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, 2017 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$ Oct 16, 2017 at 16:29

1 Answer 1

32
$\begingroup$

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$.

$\endgroup$
6
  • $\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, 2017 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$ Oct 18, 2017 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$ Oct 18, 2017 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, 2017 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, 2017 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.