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 no es posible: puesto 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 ayudar mucho; reducir el mod. $2$ ¡ya no podemos distinguir polinomios!

Answer 1

Tu problema es difícil, ¡pero aquí tienes algunas cosas que sí se pueden demostrar!

Sea $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 garantía par (b). Para garantizar (c), restrinja la atención a $f$ cuyo primer $100$ Los coeficientes son $+1$ y utilizar el teorema de Rouch'e para demostrar que $f$ tiene el mismo número de ceros que $|z|<3/2$ al igual que $x^d+x^{d-1}+\cdots+1$ es decir, todos $d$ de ellos. Los valores de estos $f$ en $2$ son los números enteros Impares en un intervalo determinado, por lo que el teorema de los números primos da el número necesario de $f$ satisfaciendo (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 tal primo, entonces $x^d+x^{d-1}+\cdots+1$ es irreducible mod $2$ por lo que cada $f \in S_d$ será irreducible sobre $\mathbf{Z}$ . $\square$

3) Existen infinitas $d$ para el 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 observación final: 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 artículo de Konyagin . Es probable que ocurra lo mismo 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 puesto a prueba esta cuestión con Sage, y el experimento sugiere un claro patrón asintótico. La mayoría de los polinomios son irreducibles. De los reducibles, un tercio son, por supuesto, divisibles por $x$ ( Edita: 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 números enteros, y lo mismo para $x-1$ . De los demás de grado $d$ , an $O(1/d)$ fracción 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 foto así, aunque realmente no lo sé. Hay una imagen similar para matrices enteras con entradas acotadas: Hay una secuencia de explicaciones de por qué pueden ser singulares, empezando por que dos filas pueden ser proporcionales. Sigue siendo un gran problema demostrar que estas explicaciones dan la asíntota correcta para el número de matrices singulares de este tipo, aunque hay grandes resultados parciales de Tao-Vu y Rudelson-Vershynin.

---

Dado que se solicitó el código de Sage, he aquí 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ó factorizaciones más excepcionales de lo 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 fallos crece lo suficientemente rápido, habrá que ajustar la asíntota que he sugerido, y el problema estadístico será probablemente 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 está permitido, 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 todavía está allí en el historial de edición. (Personalmente creo que la cuestión ternaria es al menos igual de interesante.) En particular, si el grado es uno menos que un primo, entonces como Mark Meckes sugiere a continuación, el polinomio $p$ sólo puede ser divisible por un polinomio ciclotómico siendo 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 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 divisor de $d+1$ . Si $d$ es impar, esta fracción es del orden de $d^{-1/2}$ . Si $d$ es par, he deducido 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.

Evidentemente, todo esto está estrechamente relacionado con las observaciones de la respuesta de Greg.

Edita: Corregidos algunos efectos de teclear sin pensar/leer.