Conjetura: Hay constantes $c,k$ de manera tal que todos los $(Z/nZ)^*$ es generado por sus elementos más pequeños que $k (\log n)^c$.
Donde $(Z/nZ)^*$ es el grupo multiplicativo de los números enteros mod $n$. Mi pregunta principal es: ¿qué tan "fuerte" es esta conjetura relativa a otros sin resolver conjeturas? Cómo "duro" hacer de los expertos creen que esto es demostrar (o refutar)? Cualquier referencia, de resumen de lo que se conoce actualmente, y además de la lectura, definitivamente se aprecia demasiado.
Creo que esto es interesante, pero a mi en particular la motivación viene de la de Miller–Rabin probabilística de primalidad algoritmo de prueba. Si la conjetura es verdadera para cualquier constante $c$, entonces podemos "derandomize" de Miller–Rabin en un determinista, polinomio de tiempo de algoritmo para la primalidad de pruebas (porque si $n$ es compuesto, un conjunto de generadores para $(Z/nZ)^*$ debe contener un "testigo", por lo que necesitamos de verificación sólo un polinomio de tamaño establecido para asegurar una respuesta correcta). Esto no sería un gran avance en ese sentido porque ya tenemos la queratosis actínicas de la prueba, pero sería interesante.
La página de Wikipedia de Miller–Rabin observa que la Generalizada de Riemann Hipótesis implica la conjetura es verdadera para $c=2,k=2$. Pero tengo curiosidad por ver si esta conjetura parece, por ejemplo, tan duro como la Hipótesis de Riemann, o mucho más débil.
Para aquellos familiarizados con la complejidad del cálculo, una interesante conjetura sería que $(Z/nZ)^*$ tiene un conjunto de generadores que es producible en el tiempo $poly(\log n)$ (por lo tanto también lo que implica que tiene el tamaño de $poly(\log n)$). Cualquier genérico generador pseudoaleatorio usado para demostrar BPP=P parece "casi" probar esto—se diría que existe un pequeño conjunto de genéricos entradas deterministas que son suficientes para el funcionamiento de Miller–Rabin sin todos los falsos positivos, de manera que si esta conjetura es decir, el equivalente a RH, entonces hace que la búsqueda de PRGs parece un poco más difícil. Alguna idea sobre esto también sería genial.
Respuesta
¿Demasiados anuncios?
Este problema no parece ser muy profundo. Para ilustrar esto consideremos el problema de calcular el mínimo cuadrática no-residuo $\pmod p$ para un primer $p$ -, obviamente, si los números hasta el punto de generar $({\Bbb Z}/p{\Bbb Z})^*$, a continuación, que debe contener una ecuación cuadrática no-residuo, por lo que este problema debe ser `más fácil". Vinogradov conjeturó que el mínimo cuadrática no-residuo es $\ll p^{\epsilon}$ cualquier $\epsilon >0$, pero esta sigue siendo desconocida. El mejor resultado conocido es que el mínimo cuadrática no-residuo es $\ll p^{1/(4\sqrt{e})}$, que sigue de Burgess encuadernado en carácter de sumas de dinero, además de un multiplicativo truco de Vinogradov. De manera incondicional, uno no debe esperar un resultado mejor que el de $n^{1/(4\sqrt{e})+\epsilon}$ para la generación de todos los de $({\Bbb Z}/n{\Bbb Z})^*$. Y el resultado de Harman muestra que los números hasta el $n^{1/(4\sqrt{e})+\epsilon}$ do en el hecho de generar todos los de $({\Bbb Z}/n{\Bbb Z})^*$; véase el Teorema 3 de su papel.
Más comentarios: demostrar un límite de $(\log p)^{A}$ para el mínimo cuadrática no-residuo parece requerir alguna versión de un cuasi hipótesis de Riemann: no hay ceros de Dirichlet $L$-funciones a la derecha de $1-1/A$. Una precisa relación entre cero regiones libres y el mínimo cuadrática no-residuo fue establecida primero por Rodosskii. Una manera de pensar en el grupo generado por los números por debajo de $y$ en $({\Bbb Z}/n{\Bbb Z})^*$ es para tener en cuenta la distribución de $y$liso de los números por debajo de $x$ en progresiones aritméticas $\pmod n$ -- este es el enfoque de Harman papel que se hace referencia ya, y para trabajar más en este sentido ver Soundararajan y Harper. Las ideas que aquí se dan más las relaciones entre cero regiones libres y cómo de grande $y$ tiene que ser para generar $({\Bbb Z}/n{\Bbb Z})^*$ (a lo largo de las líneas de Rodosskii de trabajo, el cual usted puede encontrar que se hace referencia no).
