Polinomios irreducibles más cortos sobre $\Bbb F_p$ de grado $n$

Question

Para cualquier primo $p$ se puede realizar cualquier campo finito $\Bbb F_{p^n}$ como el cociente del anillo $\Bbb F_p[X]$ por el ideal máximo generado por un polinomio irreducible $f$ de grado $n$ . Al dividir por el coeficiente principal, también podemos suponer $f$ es mónico, en cuyo caso podemos escribirlo como $$f(X) = X^n + a_{n - 1} X^n + \cdots + a_1 X + a_0. \def\co{\color{#00bf00}{1}} \def\ct{\color{#0000ff}{2}} \def\ch{\color{#bf00bf}{3}} \def\cf{\color{#ff0000}{4}} \def\ci{\color{#ff7f00}{5}} $$

Si dejamos que $\zeta$ denotan una raíz de $f$ entonces $\Bbb F_{p^n} \cong \Bbb F_p[X] / \langle f \rangle \cong \Bbb F_p[\zeta]$ y, por tanto, al calcular la multiplicación en este campo y escribir los elementos como polinomios en $\zeta$ de grado $< n$ de una forma u otra utilizamos de forma iterativa la identidad $$\zeta^n = -a_{n - 1} \zeta^{n - 1} - \cdots - a_1 \zeta - a_0.$$

La multiplicación manual de elementos en este campo es ingenuamente más eficiente, entonces, cuando se elige un polinomio $f$ con menos coeficientes no nulos.

Así que, naturalmente, podemos preguntarnos cuán eficientes podemos ser:

Para cualquier primo $p$ y un número entero positivo cualquiera $n$ , cuál es el menor número $\lambda(p, n)$ de coeficientes no nulos un polinomio irreducible de grado $n$ en $\Bbb F_p$ puede tener?

Algunas observaciones entre triviales y fáciles:

• El único polinomio de grado $n$ con exactamente un coeficiente distinto de cero es $X^n$ y esto es reducible si $n > 1$ Así que $\lambda(p, 1) = 1$ y $\lambda(p, n) > 1$ para $n > 1$ .
• Para $p \neq 2$ el mapa de cuadratura en $\Bbb F_p^{\times}$ es $2$ -a- $1$ , por lo que siempre hay no-cuadrados $a$ modulo $p$ y para ello $a$ el polinomio $x^2 - a$ es irreducible, por lo que $\lambda(p, 2) = 2$ . El único polinomio irreducible de grado $2$ en $\Bbb F_2$ es $X^2 + X + 1$ Así que $\lambda(2, 2) = 3$ .
• Cualquier polinomio irreducible de grado $> 1$ tiene un término constante no nulo. En particular, el único polinomio sobre $\Bbb F_2$ con exactamente dos coeficientes no nulos y un término constante no nulo es $X^n + 1$ , pero esto siempre tiene raíz $1$ y así lo ha hecho $X + 1$ como factor; así, $\lambda(2, n) \geq 3$ para $n > 1$ .
• Los únicos polinomios (mónicos) sobre $\Bbb F_3$ con exactamente dos coeficientes no nulos, el término constante entre ellos, son $X^n \pm 1$ . Ahora, $X^n - 1$ de nuevo siempre tiene raíz $1$ . Si $n$ no es un poder de $2$ digamos, $n = 2^m q$ para $q > 1$ se puede factorizar $X^n + 1 = (X^{2^m} + 1)(X^{2^m (q - 1)} - X^{2^m (q - 2)} + \cdots + X^{2^m})$ y si $n$ es una potencia de $2$ más grande que $2$ (de hecho, cualquier múltiplo de $4$ ), podemos factorizar $X^n + 1 = (X^{n / 2} - X^{n / 4} - 1)(X^{n / 2} + X^{n / 4} - 1)$ . En resumen, si $n > 2$ entonces $X^n \pm 1$ es reducible y por tanto $\lambda(3, n) \geq 3$ . Por otro lado $X^2 + 1$ es irreducible, por lo que $\lambda(3, 2) = 2$ .
• Para $n = p$ , esta pregunta muestra que $X^p - X + a$ es irreducible para todo $a \neq 0$ Así que $\lambda(p, p) \leq 3$ . Entonces, utilizando que el mapa de Frobenius $\phi: X \mapsto X^p$ es un automorfismo vemos que todo polinomio $X^p + a$ es reducible de hecho, es un factor como $(X - b)^p$ , donde $b := \phi^{-1}(-a)$ ---y así (de nuevo ya que el término constante de cualquier polinomio irreducible de grado $n > 1$ es distinto de cero) $\lambda(p, p) = 3$ .

Algunas observaciones más de las respuestas:

• Harry Altman da una prueba (generalizando una observación) a continuación que para $p > 3$ tenemos $\lambda(p, 3) = 2$ para $p \equiv 1 \bmod 3$ y $\lambda(p, 3) = 3$ para $p \equiv 2 \bmod 3$ . Con esto en la mano, todos $\lambda(p, n)$ , $n \leq 3$ se resuelven.

• La respuesta de Jim Belk muestra de forma más general que podemos caracterizar rápidamente el $(p, n)$ para el que existe un polinomio irreducible de la forma $X^n + a$ es decir, para los que $\lambda(p, n) = 2$ .

Más resultados:

• Swan ha dado varias condiciones suficientes para la reducibilidad de un trinomio $x^n + x^k + 1$ en $\Bbb F_2[x]$ (véase la cita más abajo). Una de estas condiciones en particular implica que todos estos trinomios son reducibles cuando $n \equiv 0 \bmod 8$ y por lo tanto $\lambda(2, 8m) > 3$ . Puede encontrar más detalles en $\S$ 40,9 de Jörg Arndt Materia Computacional (advertencia en pdf, $>5$ MB).

• Ciet, Quiscater y Siet mostró igualmente que $\lambda(2, n) > 3$ si $n \equiv 13 \bmod 24$ o $n \equiv 19 \bmod 24$ .

Junto con lo anterior, unos cuantos guiones ingenuos de Maple dan como resultado la siguiente tabla que incluye todos los $(p, n)$ tal que $p < 2^5, n \leq 2^4$ . (La tabla incluye una columna para $n = 49$ porque este es el valor más pequeño para el que $\lambda(p, n) = 4$ para algunos pequeños $p$ y posiblemente cualquier $p$ .) \begin{array}{c|cccccccc} \lambda & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & \cdots & 49\\ \hline 2 & \co & \ch & \ch & \ch & \ch & \ch & \ch & \ci & \ch & \ch & \ch & \ch & \ci & \ch & \ch & \ci & \cdots & \ch\\ 3 & \co & \ct & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \cdots & \cf\\ 5 & \co & \ct & \ch & \ct & \ch & \ch & \ch & \ct & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ct & \cdots & \ch\\ 7 & \co & \ct & \ct & \ch & \ch & \ch & \ch & \ch & \ct & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \cdots & \ch\\ 11 & \co & \ct & \ch & \ch & \ct & \ch & \ch & \ch & \ch & \ct & \ch & \ch & \ch & \ch & \ch & \ch & \cdots & \ch\\ 13 & \co & \ct & \ct & \ct & \ch & \ct & \ch & \ct & \ct & \ch & \ch & \ct & \ch & \ch & \ch & \ct & \cdots & \ch\\ 17 & \co & \ct & \ch & \ct & \ch & \ch & \ch & \ct & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ct & \cdots & \ch\\ 19 & \co & \ct & \ct & \ch & \ch & \ct & \ch & \ch & \ct & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \cdots & \ch\\ 23 & \co & \ct & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ch & \ct & \ch & \ch & \ch & \ch & \ch & \cdots & \ch\\ 29 & \co & \ct & \ch & \ct & \ch & \ch & \ct & \ct & \ch & \ch & \ch & \ch & \ch & \ct & \ch & \ct & \cdots & \ct\\ 31 & \co & \ct & \ct & \ch & \ct & \ct & \ch & \ch & \ct & \ct & \ch & \ch & \ch & \ch & \ct & \ch & \cdots & \ch\\ \end{array}

Algunos datos:

• Los únicos valores de $\lambda(n, p)$ que se producen para $p \leq 11, n \leq 2^8$ o $p \leq 97, n \leq 20$ son $1, 2, 3, 4, 5$ . Al parecer, los ejemplos mínimos son: $\lambda(2, 1) = 1$ , $X$ ; $\lambda(3, 2) = 2$ , $X^2 + 1$ ; $\lambda(2, 2) = 3$ , $X^2 + X + 1$ ; $\lambda(3, 49) = 4$ , $X^{49} + X^{14} + X + 2$ ; $\lambda(2, 8) = 5$ , $X^8 + X^7 + X^2 + X + 3$ . Para todos los $106$ valores de $n \leq 2^8$ para lo cual $\lambda (2, n) > 3$ tenemos $\lambda(2, n) = 5$ . Para todos los $p = 3, 5, 7, 11$ y $n \leq 2^8$ para lo cual $\lambda(p, n) > 3$ (hay $23$ , $14$ , $2$ y $1$ de estos, resp.) tenemos $\lambda(p, n) = 4$ .

• OEIS A057486 es la secuencia de "Grados de trinomios absolutamente reducibles, es decir, números $n$ tal que $x^n + x^m + 1$ es factorizable [módulo $2$ ] para todos $m$ entre $1$ y $n$ es decir, una lista de $n > 1$ tal que $\lambda(2, n) > 3$ .

• Notablemente, recientemente se ha demostrado que $\lambda(2, 57885161) > 3$ . (No es ajeno el hecho de que $2^{57885161}-1$ es un primo de Mersenne, aunque desconozco el alcance de esta relación).

También se pueden determinar los valores para un tamaño suficientemente pequeño $p, n$ mediante la consulta estas tablas .

Jörg Arndt, Materia Computacional (advertencia en pdf, $>5$ MB)

Mathieu Ciet, Jean-Jacques Quisquater, Francesco Sica, "A Short Note on Irreducible Trinomials in Binary Fields", (2002).

Richard G. Swan, "Factorización de polinomios sobre campos finitos", Revista de Matemáticas del Pacífico , (12) 3, pp. 1099-1106, (1962).

Answer 1

He aquí un teorema útil:

Teorema. $\lambda(p,n) = 2$ si y sólo si $p \nmid n$ y $p$ tiene orden $n$ modulo $n(p-1)$ .

Esto nos dice exactamente dónde aparecen todos los 2 en la tabla. Usando un poco de Mathematica podemos rellenar el código que falta $2$ 's:

\begin{array}{c|cccccccc} \lambda & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20\\ \hline 2 & 1 & 3 & 3 & 3 & 3 & 3 & 3 & 5 & 3 & 3 & 3 & 3 & 5 & 3 & 3 & 5 & 3 & 3 & 5 & 3 \\ 3 & 1 & 2 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\ 5 & 1 & 2 & 3 & 2 & 3 & 3 & 3 & 2 & & & & & & & & 2 & \\ 7 & 1 & 2 & 2 & 3 & 3 & 2 & 3 & & 2 & & & & & & & & & 2 & \\ 11 & 1 & 2 & 3 & 3 & 2 & & & & & 2 & 3 \\ 13 & 1 & 2 & 2 & 2 & 3 & 2 & & 2 & 2 & & & 2 & 3 & & & 2 & & 2 &\\ 17 & 1 & 2 & 3 & 2 & & & & 2 & & & & & & & & 2 & 3 \\ 19 & 1 & 2 & 2 & 3 & & 2 & & & 2 & & & & & & & & & 2 & 3 \\ 23 & 1 & 2 & 3 & 3 & & & & & & & 2 \\ 29 & 1 & 2 & 3 & 2 & & & 2 & 2 & & & & & & 2 & & 2\\ 31 & 1 & 2 & 2 & 3 & 2 & 2 & & & 2 & 2 & & & & & 2 & & & 2 \\ \end{array}

Prueba: La prueba es una generalización de esta respuesta por Lubin. Dejemos que $p$ sea un primo y que $n\geq 2$ .

Tenga en cuenta, en primer lugar, que si $p\mid n$ entonces $x^n-\beta = (x^{n/p}-\beta)^p$ para todos $\beta\in\mathbb{F}_p$ y por lo tanto $\lambda(p,n)>2$ . Por lo tanto, podemos suponer que $p\nmid n$ .

Dejemos que $\alpha$ sea un elemento primitivo de $\mathbb{F}_p$ y que $k=n(p-1)$ . Entonces $\alpha$ es una primitiva $(p-1)$ raíz de la unidad, por lo que el polinomio $x^n-\alpha$ tiene al menos una raíz $r$ que es una primitiva $k$ La raíz de la unidad. Afirmamos que las siguientes son equivalentes:

1. $\lambda(p,n)=2$

2. $[\mathbb{F}_p(r):\mathbb{F}_p] = n$ .

3. $x^n - \alpha$ es irreducible.

4. $p$ tiene orden $n$ modulo $k$ .

$(1) \Rightarrow (2)$ Supongamos que $\lambda(p,n)=2$ . Entonces $x^n - \beta$ debe ser irreducible para algún $\beta \in\mathbb{F}_n$ . Desde $\alpha$ es primitivo, sabemos que $\alpha^j = \beta$ para algunos $j$ . Entonces $r^j$ es una raíz de $x^n-\beta$ Así que $$[\mathbb{F}_p(r):\mathbb{F}_p] \;\geq\; [\mathbb{F}_p(r^j):\mathbb{F}_p] \;=\; n, $$ y por lo tanto $[\mathbb{F}_p(r):\mathbb{F}_p] = n$ .

$(2) \Rightarrow (3)$ y $(3) \Rightarrow (1)$ son inmediatas.

$(2) \Leftrightarrow (4)$ Dejemos que $m\geq 1$ . Entonces $\mathbb{F}_{p^m}$ contiene la primitiva $k$ raíces de la unidad si y sólo si $k \mid p^m - 1$ es decir, si y sólo si $p^m \equiv 1\;(\text{mod }k)$ . En particular, el valor más pequeño de $m$ para lo cual $\mathbb{F}_{p^m}$ contiene la primitiva $k$ Las raíces de la unidad es el orden de $p$ modulo $k$ . Así, $[\mathbb{F}_p(r):\mathbb{F}_p]=n$ si y sólo si $p$ tiene orden $n$ modulo $k$ . $\quad\square$

Answer 2

Aquí hay una prueba del patrón sobre $\lambda(p,3)$ : Al igual que con el grado $2$ un polinomio de grado $3$ es irreducible si no tiene raíces, y existe un no cubo mod $p$ si y sólo si $p\equiv 1 \pmod{3}$ . Así que en este caso debemos tener $\lambda(p,3)=2$ .

Por el contrario, si $p\equiv 2\pmod{3}$ , entonces debemos tener $\lambda(p,3)\ge3$ . Pero dado un polinomio cúbico irreducible mod $p$ ya que $p\ne 3$ podemos realizar una traslación para que el coeficiente de $X^2$ es $0$ (deprimiendo el polinomio). Esto demuestra que $\lambda(p,3)\le 3$ y así $\lambda(p,3)=3$ .

Este último argumento demuestra de forma más general que si $p\nmid n$ entonces $\lambda(p,n)\le n$ aunque esto parece ser un atado bastante cutre.