Límites en las lagunas, en una variante de polylog liso de los números.

Question

Lo siento por la introducción de largo. Creo que la explicación que motiva la pregunta y la pone en contexto. Pero si desea omitir la historia, a continuación, acaba de pasar a las cajas de color gris; que debe contener suficiente información para hacer mi pregunta.

Esta pregunta está inspirada en Sadeq Dousti la pregunta en la producción de un factor entero de un pequeño intervalo: Factorización de un número entero en el intervalo dado. Para mayor comodidad, vamos a suponer que el problema es la producción de un factor entero del intervalo de $[x-G; x]$, y nuestra meta es hacer de $G = G(x)$ tan pequeño como sea posible. (Ten en cuenta que Sadeq la versión usa $N$ en lugar de mi $x$, y corrige $G(x)$ concretamente a $O(\log x)$.)

Se puede considerar que varios candidatos fácilmente-dijo algoritmos para este problema, todos los cuales funcionan de la siguiente manera general. Deje $S$ ser un conjunto de números enteros tales que

• Dado un número $N$, pruebas de si $N$ $S$ se puede hacer de manera eficiente. Por otra parte, cualquier $N \in S$ también puede ser un factor en el tiempo $\mathrm{poly}(\log N)$.
• Las brechas en $S$ son "pequeños": para todos lo suficientemente grande $x > 0$, existe $N \in S$, de tal manera que $x - G(x) \leq N \leq x$. (De ahí mi la notación $G$.)

A continuación, dado el problema puede ser resuelto por intervalos de longitud de $G(x)$: sólo la búsqueda de una $S$-elemento en el intervalo de salida y su factorización. Todo el problema se convierte entonces en cómo pequeños podemos hacer de la $G(x)$ a ser. Aquí están algunos candidatos establece:

1. Los poderes de $2$.
2. Los números primos.
3. El conjunto de los números $N$ de manera tal que todos los primos divisores de $N$ son en la mayoría de las $\log^A(N)$ para algunos absoluta constante $A < \infty$. Voy a llamar a estos polylog liso de los números. (Véase el fineprint al final de la pregunta.)
4. El conjunto de los números $N$ tal que a más de uno de sus primos divisores supera $\log^A(N)$ donde $A$ es como antes. Voy a llamar a estos casi polylog liso de los números.

Ok, suficiente con los nombres :-). Todos estos ejemplos de satisfacer el primer requisito de pruebas (+factoring) por diseño. (Por ejemplo, en el último caso, dividir todos los pequeños primos divisores de $N$ mediante la fuerza bruta, y nos quedaremos con $1$ o a un gran número primo, y así vamos a estar en buena forma.) La gran pregunta entonces es analizar las diferencias en estos conjuntos.

1. Las potencias de dos son muy dispersas. Tienen una brecha de $G(x) = O(x)$ y que esté firme.
2. Los números primos son sospechosos de tener un mejor lagunas (ver las Consecuencias de la hipótesis de Riemann y Cramér de la conjetura). En resumen, la brecha podría ser tan pequeño como $O(\log^2 x)$. Por otro lado, la mejor incondicional obligado es$O(x^{\theta})$$\theta < .53$.
3. No tengo suficientes antecedentes como para asimilar la cuestión de las lagunas para el polylog liso de los números. Sin embargo, me encontré con Andrés Granville encuesta sobre lisa números (Suave números: Computacional, Teoría de números y más allá) dice que incluso el promedio de la brecha es de alrededor de $x^{1/A}$. (Estoy citando Teorema 1.14 de la página 4/página 270 en el pdf que me han enlazado.) Esto puede ser bastante mala en comparación con la conjetura de la brecha para los números primos ejemplo, pero una gran mejora sobre los poderes de las $2$.

Ahora, lo que sobre el conjunto de casi polylog-suave números? Ellos son más densas que las de los números primos, por lo que definitivamente, al menos, tan pequeño como $O(\log^2 x)$ condicionalmente y $O(x^{\theta})$ incondicionalmente.

Pero teniendo una idea de la mejora que tenemos en ir de los poderes de la $2$ el buen números, creo que los problemas reales de la casi liso de los números debe ser incluso mejor que la de los números primos. Que es la motivación detrás de mi pregunta:

¿Cuál es actualmente el mejor de los límites sobre las brechas en la casi polylog-suave números (condicional e incondicional)? Específicamente, es posible que $G = O(\log x)$ para este caso?

Alguna ayuda?

Fineprint que moralmente no importa. Un número es $B$-suave si su primer divisores son en la mayoría de las $B$. A mí me parece que cuando la gente analizar las propiedades de la suave números de $\leq x$, se suele establecer la suavidad del parámetro $B$ a ser una función de la $x$, como $B = \log^A x$. He definido un suave número más "intrínsecamente" por establecimiento $B = \log^A N$. Supongo que esto es sólo un problema técnico, y ninguno de los límites que realmente va a cambiar mucho. Si estoy equivocado, entonces por favor hágamelo saber. En cualquier caso, no veo ninguna razón por la que una definición es mejor para esta aplicación que el otro.

Answer 1

Sólo quiero señalar que usted puede generalizar su casi polylog-suave números un poco más allá: no Se requiere que el resto de los factor es primo, solo se requiere que es fácil factor. Así, por ejemplo, si su límite de es $ln^A x$, usted puede tener el resto de factor de tamaño M donde $ln^A x = exp( (\frac{4}{9^{1/3}} + o(1)) (ln M)^{1/3} (ln ln M)^{2/3} )$ o $M = o( exp(\frac{9}{64} A^3 (ln ln x)^3) )$. La distancia promedio de casi polylog liso conjunto S en una vecindad de x es aproximadamente el promedio de la distancia de la polylog liso conjunto S' en una vecindad de x' = x/M. tenga en cuenta que esto sólo se da un límite inferior; $G_S(x) \geq G_{S'}(x')$.