Squarefree Partes de los Números de Mersenne

Question

El $n$-ésimo de Mersenne número es $M_n=2^n-1$. Escribir $M_n=a_n b_n^2$ donde $a_n$ es positivo y squarefree.

Pregunta 1: ¿Qué límite inferior puede ser demostrado por $a_n$?

Deje $A$ ser el conjunto de todas las posibles $a_n$. El natural de la densidad de $A$ se define como $$ \delta_A=\lim_{X \rightarrow \infty} \frac{\# \{a \en Un | a \le X\}}{X}. $$

Pregunta 2: ¿Qué puede ser demostrado acerca de la $\delta_A$? Es posible demostrar que $\delta_A=0$?

Nota: estoy interesado en incondicional respuestas a las preguntas anteriores. Es fácil dar respuestas condicionadas a la conjetura ABC. De hecho, la conjetura ABC muestra que para cualquier $\epsilon>0$ hay algo de $K_\epsilon>0$ tal que $$ a_n \ge K_\epsilon \cdot 2^{n(1-\epsilon)}. $$ Por lo tanto $\# \{ a \in A | a \le X\}=O(\log(X))$, lo que da $\delta_A=0$.

Answer 1

Yo puedo demostrar que el natural, la densidad es $0$ pero yo quería mencionar algunos hechos bien conocidos que podría parecer a una promesa para una prueba.

La idea es que tal vez podemos restringir el posible primer divisores de $b_n$ suficiente para forzar $a_n$ a crecer demasiado rápido positivos densidad (digamos más rápido que $\frac{2^n}{n^2}$.)

$7 \mid M_n$ exactamente si $3 \mid n$ pero $7^2 \mid M_n$ exactamente si $3\cdot 7=21 \mid n$. Podemos registrar esta información como $[7,3,3 \cdot 7].$ Luego de los primeros números primos de la información es $$[3,2, 2\cdot 3],[5, 4 , 4\cdot 5], [7, 3 , 3\cdot 7], [11, 10 , 10\cdot 11], [13, 12 , 12\cdot 13],$$$$ [17, 8 , 8\cdot 17], [19, 18 , 18\cdot 19], [23, 11 , 11\cdot 23], [29, 28 , 28\cdot 29], [31, 5 , 5\cdot 31]$$

Así, durante estos primos, necesaria (pero no suficiente) condición para $p^2$ a dividir $M_n$ es que el $p$ brecha $n$. Esto es cierto para todos los números primos $p \ge 3$? No hay menos de las dos excepciones $1093$ e $3511$ cuyos datos se $[1093,364,364],[3511,1755,1755]$, sin embargo esas son las únicas excepciones al menos tan lejos como $1.2 \times 10^{17}.$ Esto significa que el primer divisores de $b_n$ forma un subconjunto de los primos divisores de $n$ (al menos para los números primos hasta que se une con los dos mencionados excepciones). Que sería difícil para $b_n$ a ser grande en comparación con $M_n.$

En poco más de detalle:

Deje $\ell=\mathrel{ord}_m(2)$ ser el más pequeño entero positivo con $M_{\ell}$ un varios de $m.$ Entonces $\ell$ es un divisor de $\varphi(m)$, el número de enteros $1 \le i \le m-1$ relativamente primer a $m,$ a continuación, $M_n$ es un múltiplo de $m$ exactamente al $n$ es un múltiplo de $\mathrel{ord}_m(2)$.

Los números primos $p=1093$ e $p=3511$ son primos de Wieferich en que $\mathrel{ord}_p(2)=\mathrel{ord}_{p^2}(2).$ Es conocido (de acuerdo a La Wikipedia) que no son otros primos de Wieferich al menos hasta como $1.2 \times 10^{17}.$ Algunas personas creen que el número de Los primos de Wieferich a a $N$ crece como $\log (\log (N)).$ tan lejos Como yo saben, no hay ninguna prueba de que, definitivamente, reglas que no pueden ser sólo los dos ni que descarta la posibilidad de que todos, pero un número finito de números primos son primos de Wieferich .

Cualquiera de las $\mathrel{ord}_{p^{e+1}}(2)=p \cdot\mathrel{ord}_{p^{e}}(2)$ o $\mathrel{ord}_{p^{e+1}}(2)= \mathrel{ord}_{p^{e}}(2)$ Sólo en los casos por encima de $e=1$ e $p=1093$ o $3511$ se sabe que $\mathrel{ord}_{p^{e+1}}(2)= \mathrel{ord}_{p^{e}}(2)$

---

Más detalles:

• Para $p=1093$ si $p \mid M_n$ también $p^2 \mid M_n$ , esto sucede cuando $364 \mid n.$ sin Embargo todavía es posible tener $a_n$ divisible por $1093$: Si $n$ es un múltiplo de $364\cdot 1093$, pero no de $364 \cdot 1093^2$ entonces $M_n$ es un múltiplo de $1093^3$, pero no de $1093^4.$

• Para cada entero $n \ge 1$ el cyclotomic polinomios $\Phi_n(x)$ es monic de grado $\varphi(n)$ e irreductible (sobre $\mathbb{Z}$). Estos polinomios son definidas implícitamente por $x^n-1=\prod_{d|n}\Phi_d(x).$ por lo tanto

• $$M_n=\prod_{d|n}\Phi_n(2).$$

• Esto significa que si $\ell=\mathrel{ord}_m(n)$, entonces no sólo no se $m \mid M_{\ell}$, en el hecho de $m \mid \Phi_{\ell}(2)$

• $\gcd(M_a,M_b)=M_{\gcd(a,b)}$

• Así que el único momento en que $M_q$ podría ser el primer es al $q$ es primo. Sin embargo la mayoría de los números de Mersenne $M_q$ con el primer índice no son primos Mersenne. Sin embargo, en todos los casos conocidos $M_q$ es de planta cuadrada gratis al $q$ es el primer (una excepción sería requieren de un primer índice de $q$ y un divisor $p |M_q$ que es un Wieferich prime. Dado que ninguno de $364,1755$ es uno menos que en un primer esta sería una nueva, aún desconocido, Wieferich prime.

• Para $q$ qrime, cada divisor de $M_q$ es de la forma $2qk+1.$

• Para factorizations de $M_n$ a a $n=1199$ uno puede ir a la 2-Menos de las tablas de la Cunningham Proyecto.

Answer 2

He aquí una prueba simple de usar user43383 la idea y un resultado reciente de Andrew Granville: http://arxiv.org/abs/1212.6306

De acuerdo con el Teorema 1 de ese artículo, $2^n-1$ siempre tiene una primitiva el primer factor de $p$ que se produce a un exponente impar, excepto cuando se $n=1$ o $n=6$ (donde no hay primitivo factores primos en todos). Primitivo aquí significa que $2$ tiene orden de $n$ modulo $p$. En particular, $p\equiv 1\pmod{n}$. Claramente, $p \mid a_n$. Así que si $q_n$ denota el más pequeño primer congruente a $1$ modulo $n$,, a continuación, $a_n \geq q_n$ por cada $n \neq 1, 6$. Y de hecho, por un directo de verificación, $a_6 = 7 = q_6$, lo $a_n \geq q_n$ por cada $n > 1$.

Trivialmente, $q_n \geq n+1$ por cada $n$. De hecho, es generalmente mucho más grande. El simple hecho de que los números primos han densidad igual a cero implica que para cada entero positivo $K$, uno ha $q_n > Kn$, aparte de un conjunto de $n$ de densidad cero. (Para ver esto, observe que si esta desigualdad se produce un error, uno de $n+1$, $2n+1$, $\dots$, o $(K-1)n+1$ es primo, y cada una de estas condiciones pone a $n$ en un conjunto de densidad cero.)

Por lo tanto: $a_n \geq n+1$ para todos los $n > 1$, y para todos los fijos $K$, $a_n > Kn$ para todos los $n$ fuera de un conjunto de densidad cero. Estos dos hechos son suficientes para implicar que $\{a_n\}$ sí tiene una densidad de cero.

(La prueba de que el último bit: Fix $K$. Dado que un gran $x$ si $a_n \leq x$, entonces la desigualdad de $a_n \geq n+1$ fuerzas de $n \leq x$. Si $n \leq x$ e $a_n \leq x$, entonces cualquiera de las $n < x/K$ o $a_n \leq Kn$. El ex depara, en la mayoría de las $x/K$ valores de $n$, y la segunda sostiene sólo por $o(x)$ valores de $n$, como $x\to\infty$. Por lo tanto, el número de los distintos $a_n$ con $a_n \leq x$ es en la mayoría de las $x(1/K+o(1))$; de modo que la parte superior de la densidad de $\{a_n\}$ es en la mayoría de las $1/K$. Pero esto vale para todos los $K$.)

Answer 3

Creo que se puede demostrar la enlazado $a_n> \prod 2^{\alpha_i}p_i^{\frac{(\alpha_i)(\alpha_i+1)}{2}}$ si $n=\prod p_i^{\alpha_i}$. Es, ciertamente, muy lejos de la real $a_n$, pero es más que suficiente para demostrar $\delta_A=0$.

Primero un lema:

$\frac{2^{p^d}-1}{2^{p^{d-1}}-1}$ nunca es un cuadrado

Prueba: Si $p=2$ es obviamente cierto. Wlog $p$ es impar. En realidad queremos analizar el polinomio $f(x)=\frac{x^p-1}{x-1}$ para $x=2^{p^{d-1}}$. Vamos a demostrar realmente que este polinomio es nunca una plaza para las "grandes" $x$. La idea es aproximar $\sqrt{f(x)}$ por un polynomal con coeficientes racionales. Observe que $\sqrt{f(x)}<\sqrt{\frac{x^p}{x-1}}=x^{\frac{p-1}{2}}\sqrt{\frac{x}{x-1}}=x^{\frac{p-1}{2}}\sum\limits_{k=1}^{\infty} x^{-k}\frac{\binom{2k}{k}}{4^k}$ (por la generalizada binomal teorema).

Por lo $\sqrt{f(x)}-x^{\frac{p-1}{2}}\sum\limits_{k=1}^{\frac{p-1}{2}} x^{-k}\frac{\binom{2k}{k}}{4^k} < x^{\frac{p-1}{2}}\sum\limits_{k=\frac{p+1}{2}}^{\infty} x^{-k}\frac{\binom{2k}{k}}{4^k}<\frac{\binom{p+1}{\frac{p+1}{2}}}{2^{p+1}}\frac{1}{x-1}$ (sustituyendo todos los denominadores para el primero, el que sea mayor).

También, el lado izquierdo no puede ser cero, porque todos los coeficientes de $(x^{\frac{p-1}{2}}\sum\limits_{k=1}^{\frac{p-1}{2}} x^{-k}\frac{\binom{2k}{k}}{4^k})^2$ son en la mayoría de las $1$ (los primeros son exactamente $1$, mientras que las últimas son estrictamente menor que $1$).

Así que si $\sqrt{f(x)}$ es un número entero, el lado izquierdo será de al menos $\frac{1}{2^{p-1}}$ (debido a que todos los denominadores se dividen $2^{p-1}$). Por lo tanto, si $f(x)$ es un cuadrado perfecto, $x-1<\frac{\binom{p+1}{\frac{p+1}{2}}}{2}<2^{p}-1$.

De hecho no sucede por $x=2^{p^{d-1}}$ para $d>1$. Para $x=2$, $f(2)$ está claro que no es un cuadrado porque $f(2) \equiv 3$ mod $4$.

Ahora, de vuelta a la enlazado.

Deje $p^d$ un primer factor de potencia de $n$. Observe que $gcd (\frac{2^{p^d}-1}{2^{p^{d-1}}-1},2^{p^{d-1}}-1)$ debe dividir $p$, (en general $gcd(\frac{x^p-1}{x-1},x-1)|p$, debido a $\frac{x^p-1}{x-1}=x^{p-1}+x^{p-2}+...+1 \equiv p \,(mod \,(x-1))$) por lo tanto, esta dpc es $1$ (porque claramente $p \nmid 2^{p^{d-1}}-1$).

Ahora tomamos un primer $q$ con exponente impar en $\frac{2^{p^d}-1}{2^{p^{d-1}}-1}$ (tales prime existe porque esta expresión no es un cuadrado). Desde $q$ no divide $2^{p^{d-1}}-1$ (por la anterior $gcd$ condición), $q$ satisface $ord_q(2)=p^d \Rightarrow 2p^d|q-1 \Rightarrow q>2p^d$. Aviso que este primer $q$ es un factor de $a_{p^d}$.

Para repetir $d-1$, $d-2$, ..., $1$ tenemos que $2^{p^d}-1$ tiene al menos $d$ distintos factores primos que lo dividen con exponente impar, cuyo producto es, al menos,$2^d p^{\frac{d(d+1)}{2}}$. Desde $2^{p_i^{\alpha_i}}-1|2^n-1$ y todos los $2^{p_i^{\alpha_i}}-1$ son parejas coprime, hemos demostrado que el obligado se ha indicado anteriormente. (observe que el factor de $2^{\alpha_1}$ realmente no aparece para $i=1$ ($p_1=2$), pero no va a hacer una gran diferencia).

Ahora, para la prueba de que $\delta_A=0$, vamos a utilizar que el obligado se demostró da $a_n>n 2^{\omega(n)-1}$. Esto es debido a que $2^{\alpha_i}p_i^{\frac{(\alpha_i)(\alpha_i+1)}{2}}\ge 2 p_i^{\alpha_i}$ (para $i=1$, ya que no tienen el factor de $p_i^{\alpha_i}$ sólo utilizamos $p_1^{\frac{(\alpha_1)(\alpha_1+1)}{2}}\ge p_1^{\alpha_1}$, lo que explica la $-1$ después $\omega(n)$)

Ahora, algunas fija $t$:

\delta_A=$\lim\limits_{n \to \infty} \frac{\#\{ a_k \in A | a_k<n\}}{n} = \lim\limits_{n \to \infty} \frac{\#\{a_k \in A | a_k<n, \omega(k)<t\}}{n} + \frac{\#\{a_k \in A | a_k<n, \omega(k)\ge t\}}{n}$

Por http://en.wikipedia.org/wiki/Hardy%E2%80%93Ramanujan_theorem, $\frac{\#\{a_k \in A | a_k<n, \omega(k)<t\}}{n}$ va a cero, debido a que por nuestra obligado, si $a_k<n$,, a continuación,$k<n$, y una de las consecuencias del teorema que se presenta es que el conjunto de los números con las $\omega(k)<t$ natural de densidad igual a cero.

Por nuestra enlazado $\#\{a \in A | a<n, \omega(a)\ge t\}$ es en la mayoría de las $\frac{n}{2^{t-1}}$, porque no tiene elementos $a_k$ con $k>\frac{n}{2^{t-1}}$ lo contrario $a_k>k2^{\omega(k)-1}>\frac{n}{2^{t-1}}2^{t-1}=n $.

Por lo tanto, para cada uno de ellos fijo $t$, $\delta_A\le\frac{1}{2^{t-1}}$, así que vamos a comprobar que, efectivamente,$\delta_A=0$.

(observe que el factor de $2^{\alpha_i}$ en $2^{\alpha_i}p_i^{\frac{(\alpha_i)(\alpha_i+1)}{2}}$ es muy importante, de lo contrario no seríamos capaces de manejar squarefree $n$)

Answer 4

Le Maohua, "En los Números de Mersenne" [en China], Diario de Jishou de la Universidad (Ciencias Naturales Edition) 20(1) (Marzo de 1999): 17-19, muestra que la squarefree parte de $2^p - 1$, con $p \ge 11$ prime, es mayor que $(\pi{}p/log\thinspace{}p)^2$.