Timeline for How Composite can $2^n-1$ be, infinitely often?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 20, 2017 at 0:42 | comment | added | GH from MO | @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!$. | |
| Oct 19, 2017 at 22:10 | comment | added | Salvo Tringali | @GHfromMO If I get it correctly, you are suggesting to replace $n!$ with $(n+1)\# := \prod_{p \le n+1} p$ in the above proof. If so, how do you show that $\prod_{p \,\mid\, a^{(n+1)\#} - 1} (1 - 1/p) \to 0$ as $n \to \infty$? This is essentially an infinite product over the set $\mathcal{SQF}(a)$ of all primes $\ge a+1$ whose multiplicative order to the base $a$ is squarefree, and in principle this set may be too sparse for $\prod_{p \in \mathcal{SQF}(a)} (1 - 1/p)$ to converge to $0$ (though I don't know if this is really the case). | |
| Oct 18, 2017 at 21:14 | comment | added | GH from MO | 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. | |
| Oct 18, 2017 at 11:15 | comment | added | Salvo Tringali | @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. | |
| Oct 18, 2017 at 10:15 | history | edited | Salvo Tringali | CC BY-SA 3.0 |
replaced 2n with n (no real reason for having the former in the exponent)
|
| Oct 18, 2017 at 10:10 | comment | added | Salvo Tringali | @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!$. | |
| Oct 17, 2017 at 23:43 | comment | added | kodlu | 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$$ | |
| Oct 16, 2017 at 7:52 | vote | accept | kodlu | ||
| Oct 16, 2017 at 7:51 | vote | accept | kodlu | ||
| Oct 16, 2017 at 7:51 | |||||
| Oct 16, 2017 at 7:27 | history | edited | Salvo Tringali | CC BY-SA 3.0 |
added 134 characters in body
|
| Oct 16, 2017 at 7:12 | history | answered | Salvo Tringali | CC BY-SA 3.0 |