Polinomios irreducibles con coeficientes restringidos

Question

En el Café, después de leer sobre TWF 285, yo preguntó más o menos

Aproximadamente cuántos polinomios con coeficientes en $\{\pm 1\}$ y de grado $d$ son irreducibles?

y eso es lo que quiero preguntar aquí.

El primer análisis de no ir: ya que si $P$ es reducible, entonces es reducible mod $3$ obtenemos que el número de tales reducibles es $O(\frac{d-1}{d}3^d)$ pero está claro que ya es demasiado grande para que sirva de mucho; reducir el mod $2$ ya no podemos distinguir los polinomios.

Answer 1

Su problema es difícil, pero aquí hay algunas cosas que se pueden probar.

Dejemos que $S_d$ sea el conjunto de polinomios de grado $d$ con todos $d+1$ coeficientes en $\{\pm 1\}$ .

1) $|S_d| \gg 2^d/d$ como $d \to \infty$ a través de números enteros pares.

Prueba: Por el teorema 2 de un artículo de Brillhart, Filaseta y Odlyzko , $f$ será irreducible si

(a) $f(2)$ es primo,

(b) $f(1) \ne 0$ y

c) todos los ceros complejos de $f$ tienen un valor absoluto inferior a $3/2$ .

La condición de que $d$ es par garantiza (b). Para garantizar (c), restringir la atención a $f$ cuya primera $100$ Los coeficientes son $+1$ y utilizar el teorema de Rouch'e para demostrar que $f$ tiene el mismo número de ceros que satisfacen $|z|<3/2$ al igual que $x^d+x^{d-1}+\cdots+1$ es decir, todos los $d$ de ellos. Los valores de estos $f$ en $2$ son los enteros Impares en un determinado intervalo, por lo que el teorema del número primo da el número necesario de $f$ que satisfaga (a). $\square$

2) La Hipótesis de Riemann Generalizada implica que hay infinitas $d$ para el que cada $f$ en $S_d$ es irreducible.

Prueba: GRH implica que hay infinitos primos $p$ para lo cual $2$ es una raíz primitiva. Si $d+1$ es un primo de este tipo, entonces $x^d+x^{d-1}+\cdots+1$ es irreducible mod $2$ Así que cada $f \in S_d$ será irreducible sobre $\mathbf{Z}$ . $\square$

3) Existen infinitas $d$ para los que al menos $50\%$ de los polinomios en $S_d$ son irreducibles.

Prueba: Sea $d=2^n-1$ para cualquier $n \ge 1$ . Si $f \in S_d$ entonces $f(x+1) \equiv x^d \pmod{2}$ . Así, $f(x+1)$ es Eisenstein en $2$ la mitad del tiempo. $\square$

Una última observación: Se conjetura que la fracción de polinomios irreducibles entre los de grado $d$ con coeficientes 0,1 tiende a $1$ como $d \to \infty$ : ver este documento de Konyagin . Es probable que lo mismo ocurra con tu problema, como sugiere Greg, pero también parece que lo mejor que puedes esperar por el momento son resultados parciales como los anteriores.

Answer 2

He probado esta cuestión con Sage, y el experimento sugiere un claro patrón de asintótica. La mayoría de los polinomios son irreducibles. De los reducibles, un tercio son, por supuesto, divisibles por $x$ ( Editar: Si se admiten coeficientes 0; véase más adelante). Un $O(1/\sqrt{d})$ fracción son cada una divisible por $x+1$ y $x-1$ . Eso es porque si $p$ es un polinomio de este tipo, entonces $p(x) \bmod x+1$ se entiende como un paseo aleatorio en los enteros, y lo mismo para $x-1$ . De los otros de grado $d$ , un $O(1/d)$ son divisibles por ciertos polinomios cuadráticos como $x^2+x+1$ . El resto $p(x) \bmod x^2+x+1$ puede interpretarse como un paseo aleatorio en la red triangular del plano. Adenda: En realidad, los únicos polinomios que pueden comportarse así son los polinomios ciclotómicos. La divisibilidad por cualquier polinomio específico no ciclotómico es exponencialmente rara.

Podría ser muy difícil probar una imagen como esta, aunque realmente no lo sé. Hay una imagen similar para las matrices enteras con entradas acotadas: Hay una secuencia de explicaciones de por qué pueden ser singulares, empezando por que dos filas pueden ser proporcionales. Todavía es un gran problema abierto demostrar que estas explicaciones dan la asintótica correcta para el número de matrices singulares de este tipo, aunque hay grandes resultados parciales de Tao-Vu y Rudelson-Vershynin.

---

Ya que el código de Sage fue solicitado, aquí hay una versión mejorada:

maxdegree = 16
maxcyclo = 400
displayother = 11

R.<x> = ZZ[]
cyclos = {}
for k in xrange(1,maxcyclo+1):
    c = cyclotomic_polynomial(k,x)
    if c.degree() <= maxdegree: cyclos[k] = c

def tally(key):
    if not key in counts: counts[key] = 0
    counts[key] += 1

for degree in xrange(1,maxdegree+1):
    print
    counts = {}
    total = 0
    for n in xrange(2^degree):
        total += 1
        p = x^degree
        for k in xrange(degree):
            choice = (int(n)>>k)%2
            p += (2*choice-1)*x^k
        cdiv = False
        for k in cyclos:
            if not p%cyclos[k]:
                tally('div by C(%2d)' % k)
                cdiv = True
        if cdiv: continue
        f = factor(p)
        if len(f) > 1:
            if degree <= displayother: print p,'=',f
            tally('other reducible')
        else: tally('irreducible')
    counts['total'] = total
    print '\nDegree',degree
    for key in sorted(counts): print '%s: %d' % (key,counts[key])

Es claramente cierto que la fracción de estos polinomios que son divisibles por un polinomio ciclotómico de grado $c$ decae como una ley de potencia, de hecho como $O(1/d^{c/2})$ . También es claramente cierto que la fracción divisible por cualquier otro polinomio fijo decae exponencialmente. Sin embargo, el experimento más cuidadoso encontró más factorizaciones excepcionales de las que pensaba. Hay muchos polinomios cuyas raíces están cerca del círculo unitario aunque no estén en el círculo unitario. Por ejemplo $x^3+x+1$ es así y viene en 8 versiones (como también $x^3-x^2+1$ ). Si el número de estos cuasi-errores crece lo suficientemente rápido, entonces la asintótica que sugerí tiene que ser ajustada, y el problema estadístico es probablemente entonces aún más difícil.

---

Según el comentario de JSE más arriba, entendí mal la pregunta original en el sentido de que los coeficientes están en $\{-1,0,1\}$ . Si $0$ no se permite, entonces se desarrollan condiciones de congruencia que hacen mucho más probable que un polinomio aleatorio sea irreducible. He sustituido el código para reflejar la pregunta real, aunque si alguien está interesado el código antiguo sigue ahí en el historial de ediciones. (Personalmente creo que la pregunta ternaria es al menos igual de interesante). En particular, si el grado es uno menos que un primo, entonces, como sugiere Mark Meckes más abajo, el polinomio $p$ sólo puede ser divisible por un polinomio ciclotómico por ser un polinomio ciclotómico.

A continuación se muestra una salida típica del código:

Degree 14
div by C( 3): 1126
div by C( 5): 244
div by C( 6): 1126
div by C(10): 244
div by C(15): 19
div by C(30): 19
irreducible: 13310
other reducible: 378
total: 16384

(El total no se suma porque un polinomio puede ser divisible por más de un polinomio ciclotómico).

Answer 3

Secuencia http://www.oeis.org/A087481 enumera el número de tales polinomios irreducibles hasta el grado 18.

Answer 4

Consideré una cuestión relacionada en el Teorema 6 de este documento . Aunque está formulado de forma diferente (en términos de matrices circulantes aleatorias), mi resultado estima la fracción de $\pm 1$ polinomios de grado $d$ que son divisibles por algún polinomio ciclotómico de orden que divide a $d+1$ . Si $d$ es impar, esta fracción es del orden $d^{-1/2}$ . Si $d$ es par, derivé dos límites superiores diferentes que implican que la fracción es menor que en el caso par; en particular, si $d+1$ es primo entonces $\pm \sum_{k=0}^d x^k$ son (de forma bastante obvia) los únicos polinomios de este tipo.

Está claro que todo esto está estrechamente relacionado con las observaciones de la respuesta de Greg.

Editar: Se han corregido algunos efectos de escribir sin pensar/leer.