Baja la delimitación de la probabilidad de que $\gcd(t,N)≤B$, para un random $t$ y fija (grande) $N$

Question

$\newcommand{\Prb}[1]{\mathcal{P}_{#1}}$ Tengo el siguiente número de la teoría del problema, relacionado con Odlyzko de mejora en Shor del algoritmo de factorización (ver este cstheory.sx pregunta para más detalles).

Deje $N$ ser un (gran) número entero y $1≤B≤N$ un salto. Si elegí el entero $1≤t≤N$ uniformemente al azar, puedo límite inferior de la probabilidad de $\Prb B$ que $\gcd(t,N)≤B$ ? ¿Cómo debería yo elegí el menos posible $B$ tal que $\Prb B$ se apartó de 0 ? O asintóticamente cerca de 1 ?

Por supuesto $$\begin{align}\Prb 1&=\frac{ϕ(N)}N>\frac{1}{e^γ\ln\ln N+\frac3{\ln\ln N}};& \Prb N&=1 \end{align}$$ donde $ϕ$ es de Euler totient función y $γ$ es el de Euler-Mascheroni constante. De manera más general, es fácil ver que $$ \Prb B=\frac{\sum_{d\vert N}^{d≤B}ϕ(\frac{N}{d})}N =1-\frac{\sum_{d'\vert N}^{d'<\frac{N}{B}}ϕ(d')}N, $$ pero yo no logran ir más allá.

Si tengo que interpretar el 1995 "comunicación privada" de Odlyzko a Shor (mencionado en el arXiv:quant-ph/9508027 y la cstheory.sx pregunta) correctamente, $∀ε>0$, $\Prb{(\log N)^{1+ε}}$ se apartó de 0. Sin embargo, no lograba encontrar una prueba de esto.

Answer 1

De hecho, uno puede demostrar un resultado más fuerte-es decir, la probabilidad se apartó de cero, tan largo como $B \ge (\log N)^\delta$ para algunos $\delta >0$. Este es el mejor posible, tomando $N$ a ser el producto de los primeros números primos. Desde $\phi(N/d) \ge \phi(N)/d$, nuestra probabilidad es acotada abajo por $$ \frac{\phi(N)}{N} \sum_{d|N, d\le B} \frac{1}{d}\ge \frac{\phi(N)}{N}\sum_{d|N, d\le B} \frac{\mu(d)^2}{d}, $$ donde en la última suma se ha restringido a la atención de la plaza libre de $d$ por la simplicidad.

Ahora me reclama que por lo suficientemente grande como $B$ (y cualquier $N$, independiente de $B$) uno tiene $$ \sum_{d|N, d\le B} \frac{\mu(d)^2}{d} \ge \frac{1}{4} \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big). \etiqueta{1} $$ Suponiendo que el reclamo, obtenemos una cota inferior para nuestra probabilidad de $$ \ge \frac 14 \frac{\phi(N)}{N} \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) \ge \frac{1}{4} \prod_{p} \Big(1-\frac 1{p^2}\Big) \prod_{p|N, p>\sqrt{B}} \Big(1-\frac 1p\Big)= \frac{3}{2\pi^2} \prod_{p|N, p>\sqrt{B}} \Big(1-\frac{1}{p}\Big). $$ Ahora si $B\ge (\log N)^{\delta}$ luego $$ \prod_{p|N, p>\sqrt{B}} \Big(1-\frac 1p\Big) \ge \prod_{(\log N)^{\delta/2}<p <(\log N)^2}\Big(1-\frac 1p\Big) \prod_{p>(\log N)^2, p|N} \Big(1-\frac 1p\Big), $$ y por Mertens del teorema de el primer factor de arriba es $\gg \delta$, y trivialmente el segundo factor es $1+o(1)$. Esto completa la prueba.

Queda por resolver la reclamación (1). Con $\alpha =1/\log B$ nota de que $$ \sum_{d|N, d\le B} \frac{\mu(d)^2}{d} \ge \sum_{\substack{d|N, d\le B \\ p|d \implica p\le \sqrt{B}}} \frac{\mu(d)^2}{d} \ge \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) - B^{-\alpha} \sum_{\substack{d|N\\ p|d\implica p\le \sqrt{B} }} \frac{\mu(d)^2 d^{\alpha}}{d}. $$ El segundo término de arriba es $$ e^{-1} \prod_{p|N, p\le \sqrt{B}} \Big(1 + \frac{p^{\alpha}}{p}\Big) \le e^{-1} \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) \exp\Big(\sum_{p|N, p\le \sqrt{B}} \frac{p^{\alpha}-1}{p}\Big). $$ Ahora lo suficientemente grande como $B$, (desde $(e^{t}-1)/t \le (\sqrt{e}-1)/(1/2)$ para $0\le t\le 1/2$) $$ \sum_{p\le \sqrt{B}} \frac{p^{1/\log B}-1}{p} \le\sum_{p\le \sqrt{B}} \frac{\log p}{p\log B} \Big(\frac{\sqrt{e}-1}{1/2}\Big) = \sqrt{e}-1 +o(1), $$ y el uso de este anterior, obtenemos $$ \sum_{d|N, d\le B} \frac{\mu(d)^2}{d} \ge \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big) \Big(1 - e^{-1} (e^{\sqrt{e}-1}+o(1)) \Big) \ge \frac 14 \prod_{p|N, p\le \sqrt{B}} \Big(1+\frac 1p\Big), $$ demostrar la afirmación (1).

Answer 2

Uno puede establecer la reclamación mediante un logarítmica versión de el momento en el método.

Si uno de los factores $N = \prod_{p|N} p^{\operatorname{ord}_p(N)}$,, a continuación,$\log \operatorname{gcd}(t,N) = \sum_{p|N} \log \operatorname{gcd}( t, p^{\operatorname{ord}_p(N)} )$. Teniendo expectativas, vemos de la linealidad de la expectativa de que

$$ {\mathbf E} \log \operatorname{gcd}(t,N) \leq \sum_{p|N} \sum_{1 \leq j \leq \operatorname{ord}_p(N)} \frac{j \log p}{p^j}$$ desde el evento de $\operatorname{gcd}(t,p^{\operatorname{ord}_p(N)}) = p^j$ se produce con la probabilidad en la mayoría de los $1/p^j$. Las contribuciones de $j \geq 2$ puede estar delimitado por $O( \sum_p \frac{\log p}{p^2} ) = O(1)$ después de sumar la primera en $j$, por lo tanto $$ {\mathbf E} \log \operatorname{gcd}(t,N) \leq \sum_{p|N} \frac{\log p}{p} + O(1).$$ Por Mertens teorema de la aportación de todos los números primos hasta el $\log N$ es en la mayoría de las $\log\log N + O(1)$. Como para los números primos mayores que $\log N$ que dividen $N$, hay en la mayoría de las $\frac{\log N}{\log\log N}$ de estos, y cada término es en la mayoría de las $\frac{\log N}{\log\log N}$, por lo que la contribución total es $O(1)$. Así $$ {\mathbf E} \log \operatorname{gcd}(t,N) \leq \log\log N + O(1).$$ Por la desigualdad de Markov, esto implica que $\log \operatorname{gcd}(t,N) \leq (1+\varepsilon)\log\log N$ con probabilidad apartó desde cero para $N$ suficientemente grande dependiendo $\varepsilon$, lo que le da la reclamación.

Answer 3

Justificación de la Odlyzko comentario ya ha sido proporcionada. Permítanme complementar esta diciendo que si desea que la probabilidad de que tienden a 1, usted debe tomar la $B = (\log{N})^{A}$ donde $A \to\infty$ con $N$.

Que esto es suficiente sigue de Terry, de la respuesta anterior. Para verlo es necesario, permítanme mostrar que si a es cualquier constante fija, a continuación, $\mathcal{P}_{(\log{N})^A}$ no tienden a $0$ as $N\to\infty$. Deje $N$ ser el producto de los números primos hasta el $z$ donde $z$ es un parámetro tiende a $\infty$. (Por lo $\log{N} \sim z$, por el teorema de los números primos.) Considerar los números de $t \le N$ construido como un producto de $de$ donde $d$ es squarefree, $z$-suave, $d \in ((\log{N})^{A},(\log{N})^{2A}]$, e $e$ no tiene factores primos de a $z$. A continuación,$\gcd(t,N) = d > (\log{N})^{A}$; vamos a mostrar a continuación hay $\gg N$ estos valores de $t \in [1,N]$.

Dado $d$, el número de posibilidades de $e$ es $\gg \frac{N}{d \log{z}} \gg \frac{N}{d \log\log{N}}$, por (por ejemplo) Brun tamiz. Ahora se nos suma en $d$. Para $T \le (\log{N})^{2A}$, el número de squarefree $z$-suave enteros $d \in [1,T]$ es $\gg T$. (La distribución de squarefree suave números se entiende en gama bastante amplia; por ejemplo, véase el trabajo de Naimi.) Ahora parcial suma da que la suma de $1/d$ es $\gg \log\log{N}$.