Dado un polinomio entero, ¿hay un pequeño módulo primo que tenga una raíz?

Question

Estoy buscando en un papel por Pascal Koiran en la complejidad computacional de certificación de la solvencia de entero de ecuaciones polinómicas en varias variables. Con la ayuda de algunos de los más importantes teoremas en la geometría algebraica, Koiran reduce todo a la siguiente univariante pregunta: Supongamos que el $f \in \mathbb{Z}[x]$ es un polinomio de grado $D$, y supongamos que el $\ell_1$ norma de los coeficientes (o $\ell_\infty$ norma o de cualquier otra cosa; todos ellos son equivalentes para este propósito) está delimitado por $R$. Entonces es un teorema de Lagarias, Odlyzko, y Weinberger que hay un primer $$p = \exp(\text{poly}(\log D,\log R))$$ modulo que $f$ tiene una raíz. La única pega es que ellos asumen la generalización de la hipótesis de Riemann. Podría ser algo más fácil de demostrar que no es una fuente primaria de energía $q$ de este tamaño y de la raíz en $\mathbb{F}_q$. Que parece tan bueno en el contexto, pero en cualquier caso, hay un primer $p$ que hace el trabajo. Este teorema está estrechamente relacionada con la "eficaz Chebotarev densidad teorema" de Lagarias, Odlyzko, et al.

Koiran las necesidades de una amplia oferta de este tipo de números primos, pero mi pregunta es sobre la búsqueda de uno. Mi corazonada en el momento es que es todavía un problema abierto para encontrar una $p$ en el rango dado por encima incondicionalmente, en particular, sin GRH. ¿Cuál es el estado actual de la cuestión? Podría ser más fácil para encontrar una raíz de establecer completa existencial Chebotarev (en lugar de la densidad de resultado), o son estos resultados equivalentes? Es considerado como difícil por las mismas razones que GRH es difícil, o es GRH un posible enfoque?

(Por cierto, usted puede obtener un interesante pero insuficiente obligado incondicionalmente como sigue: $f(x)$ sólo alcanza un valor de unidad en la mayoría de las $2D$ de veces, así que elegir algún otro $x$ con $|x| \le D$ y, a continuación, elija un divisor primo de $f(x)$.)

Answer 1

Mi papel Chebyshev del método de número de campos, J. de Théorie des Nombres de Burdeos, 12 (2000) 81-85. tiene algunos primaria de los límites que puede ser eficaz y también algunas referencias. Lagarias y Odlysko también tiene una versión de su teorema, sin el uso de GRH que es, como se esperaba, mucho más débil que el de la versión con la GRH. No creo que este tipo de problema es equivalente a la GRH, pero es sin duda mucho más fácil con él.

Usted menciona de manera indirecta que podría ser suficiente para sus propósitos solo el primer poderes. Dependiendo de lo que usted está después, sería mucho más fácil el problema.

Answer 2

Lamento parásito de esta venerable pregunta con algo que es menos una respuesta de otra pregunta, pero es el teorema de Lagarias, Odlyzko, Weinberger de mencionar que incluso resultó en virtud de GRH ? (se pregunta si es cierto sin GRH).

Asumo el papel de Pascal Koiran al que te refieres es este uno. Uno encuentra de hecho en la sección 5 el teorema de estado, y la prueba es esencialmente un reducción Lema 3 de este artículo por Adleman y Odlyzko (y no por Lagarias y Odlyzko). Ahora no parece ser un problema en la prueba del Lema 3, ya en las seis primeras líneas de la prueba. Hay un primer función de recuento $S(x)$ (lo que cuenta es la de los números primos $p$ a a $x$ con multiplicidad $1$ si $P$ no tiene raíz mod $p$, $0$ si $P$ tiene una raíz mod $p$, $-1$ si $P$ tiene 2 raíces, etc.) y se dice sin más justificación que la enlazado $S(x) = x^{1/2} (n \log x + \log D_P)$ (donde $n$ es el grado de $P$ e $D_P$ su discriminante) sigue por el Teorema 1.1 de Lagarias-Odlyzko (que es el famoso eficaz Chebotarev bajo GRH). Pero no veo para que Galois de la extensión de los campos de número de este teorema se aplica. Tiene que ser una extensión de $\mathbb Q$ ya que el resultado es el conteo de los números primos, no el primer ideales en algunos de extensión. Deje $K$ indica que el campo generado por una raíz de $P$, e $L$ de su división de campo; entonces el teorema se da más o menos lo que se indica si se aplica a $K/\mathbb Q$, pero no se puede aplicar a la extensión, porque en general no es de Galois. Si en lugar de aplicado a $L/\mathbb Q$, que es de Galois, entonces el grado $n$ tiene que ser reemplazado por el grado de $L$ que mi ser tan grande como $n!$, arruinando la estimación.

Así que me estoy perplejo... Ya que hay al menos dos personas aquí haber pensado en este tipo de resultados, lo que me estoy perdiendo?