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

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

1 Answer 1

Reset to default
33
$\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$.

Improve this answer
$\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
    Commented 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$
    – Salvo Tringali
    Commented 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$
    – Salvo Tringali
    Commented 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
    Commented 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
    Commented Oct 20, 2017 at 0:42

You must log in to answer this question.

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