41 votos

Menor polinomios irreducibles sobre $\Bbb F_p$ de grado $n$

Para cualquier prime $p$, uno puede darse cuenta de cualquier campo finito $\Bbb F_{p^n}$ como el cociente del anillo $\Bbb F_p[X]$ por la máxima ideal generado por un polinomio irreducible de $f$ de grado $n$. Dividiendo por el coeficiente inicial, podemos muy bien suponer que $f$ es monic, en cuyo caso se puede escribir 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$ denotar una raíz de $f$, entonces $\Bbb F_{p^n} \cong \Bbb F_p[X] / \langle f \rangle \cong \Bbb F_p[\zeta]$, y para el cómputo de la multiplicación en este campo y escribir 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.$$

Manualmente la multiplicación de los elementos en este campo es ingenuamente más eficiente, entonces, cuando uno elige un polinomio de $f$, con menos distinto de cero de los coeficientes.

Así que, naturalmente, nos podemos preguntar lo eficaz que nos puede ser:

Para cualquier prime $p$ y cualquier entero positivo de $n$, ¿cuál es el número mínimo de $\lambda(p, n)$ de un valor distinto de cero los coeficientes de un polinomio irreducible de grado $n$ sobre $\Bbb F_p$ puede tener?

Algunos trivial fácil observaciones:

  • El único polinomio de grado $$ n con exactamente un coeficiente distinto de cero es de $X^n$, y este es reducible iff $n > 1$, entonces $\lambda(p, 1) = 1$ y $\lambda(p, n) > 1$ para $n > 1$.
  • Por $p \neq 2$, el cuadrado es el mapa en $\Bbb F_p^{\times}$ es $2$a$1$, por lo que siempre hay nonsquares $$ modulo $p$, y por el $a$ el polinomio $x^2 - a$ es irreductible, y por lo que $\lambda(p, 2) = 2$. El único polinomio irreducible de grado $2$ más de $\Bbb F_2$ $X^2 + X + 1$, entonces $\lambda(2, 2) = 3$.
  • Cualquier polinomio irreducible de grado $> 1$ ha distinto de cero término constante. En particular, el único polinomio de más de $\Bbb F_2$ con exactamente dos a cero los coeficientes es de $X^n + 1$, pero esto siempre ha root $1$ y así ha $X + 1$ como un factor; por lo tanto, $\lambda(2, n) \geq 3$ para $n > 1$.
  • La única (monic) los polinomios de más de $\Bbb F_3$ con exactamente dos a cero los coeficientes, el término constante entre ellos, son de $X^n \pm 1$. Ahora, $X^n - 1$ de nuevo, siempre ha root $1$. Si $n$ no es una potencia de 2$$, digamos, $n = 2^m p$ para $q > 1$, uno puede factor $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 de $2$ (de hecho, cualquier múltiplo de $4$), podemos factor $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 lo que $\lambda(3, n) \geq 3$. Por otro lado $X^2 + 1$ es irreducible, entonces $\lambda(3, 2) = 2$.
  • Para $n = p$, esta pregunta muestra que $X^p - X + a$ es irreductible para todo $a \neq 0$, entonces $\lambda(p, p) \leq 3$. Entonces, el uso que el Frobenius mapa de $\phi: X \mapsto X^p$ es un automorphism vemos que cada polinomio $X^p + a$ es reducible---de hecho, factores como $(X - b)^p$, donde $b := \phi^{-1} (-)$---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$.

Algunos de los más observaciones de las respuestas:

  • Harry Altman da una prueba (la generalización de una observación) por debajo de $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 mano, todo $\lambda(p, n)$, $n \leq 3$, se resuelven.

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

Sin embargo, 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]$ (ver cita más abajo). Una de estas condiciones, en particular, implica que todos estos trinomios son reducible cuando $n \equiv 0 \bmod 8$ y por tanto $\lambda(2, 8) > 3$. Más detalles se pueden encontrar en $\S$40.9 de Jörg Arndt la Materia Computacional (pdf advertencia, $>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, un par de ingenuos Arce scripts de rendimiento de la siguiente tabla que incluye la totalidad de los $(p, n)$ tal que $p < 2^5, n \leq 2^4$. (La tabla se incluye una columna para $n = 49$, ya que este es el valor más pequeño para el que $\lambda(p, n) = 4$ para algunos pequeños $p$, y posiblemente $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 & \tc\\ 31 & \co & \ct & \ct & \ch & \ct & \ct & \ch & \ch & \ct & \ct & \ch & \ch & \ch & \ch & \ct & \ch & \cdots & \ch\\ \end{array}

Algunos datos:

  • Después de la computación $\lambda(n, p)$ para $p \leq 11, n \leq 2^8$ y $p \leq 97, n \leq 20$, los únicos valores de $\lambda$ he visto expuesto (junto con aparentemente mínima representantes) 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 $n \leq 2^8$ que $\lambda (2, n) > 3$ tenemos $\lambda(2, n) = 5$. Para todos $p = 3, 5, 7, 11$ y $n \leq 2^8$ que $\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 absolutamente irreductible trinomios, es decir, los números $n$ que $x^n + x^m + 1$ es factorable [modulo $2$] para todos los $m$ entre $1$ y $n$," es decir, una lista de $n > 1$ tal que $\lambda(2, n) > 3$.

  • Cabe destacar que, recientemente, se ha demostrado que $\lambda(2, 57885161) > 3$. (Que no es ajeno el hecho de que $2^{57885161}-1$ es un Mersenne prime, aunque no sé el alcance de esta relación.)

También se puede determinar los valores de lo suficientemente pequeño como $p,$ n, mediante la consulta de estas tablas.

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

Mathieu Ciet, Jean-Jacques Quisquater, Francesco Sica, "Una Breve Nota sobre Irreductible Trinomios en Campos Binarios", (2002).

Richard G. Swan, "Factorización de polinomios sobre campos finitos", Pacific Journal of Mathematics, (12) 3, pp 1099-1106, (1962).

9voto

seanyboy Puntos 3170

Aquí es un útil teorema:

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

Esto nos dice exactamente donde todos la 2 aparecen en la tabla. Con un poco de Mathematica código, podemos llenar la 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}

La prueba: La prueba es una generalización de esta respuesta por Lubin. Deje que $p$ ser una de las primeras y dejar $n\geq 2$.

Nota: primero que si $p\mediados de n$, entonces $x^n-\beta = (x^{n/p}-\beta)^p$ para todo $\beta\in\mathbb{F}_p$ y por tanto $\lambda(p,n)>2$. Por lo tanto, podemos suponer que $p\nmid$n.

Deje que $\alpha$ ser un elemento primitivo de $\mathbb{F}_p$, y dejar que $k=n(p-1)$. Entonces $\alpha$ es una primitiva de $(p-1)$'st raíz de la unidad, por lo que el polinomio $x^n-\alpha$ tiene al menos una raíz $r$ es una primitiva de $k$'th raíz de la unidad. Pretendemos que los siguientes son equivalentes:

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

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

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

  4. $p$ es de orden $n$ modulo $k$.

$(1) \Rightarrow (2)$ Supongamos que $\lambda(p,n)=2$. Entonces $x^n - \beta$ debe ser irreductible $\beta \in\mathbb{F}_n$. Desde $\alpha$ es primitivo, sabemos que $\alpha^j = \beta$ $j$. Entonces $r^j$ es una raíz de $x^n-\beta$, por lo 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 inmediatos.

$(2) \Leftrightarrow (4)$ Let $m\geq 1$. Entonces $\mathbb{F}_{p^m}$ contiene el primitivo $k$'th raíces de la unidad si y sólo si $k \a mediados de p^m - 1$, es decir, si y sólo si $p^m \equiv 1\;(\text{mod }k)$. En particular, el menor valor de $m$ que $\mathbb{F}_{p^m}$ contiene el primitivo $k$'th raíces de la unidad es del orden de $p$ modulo $k$. Mus $[\mathbb{F}_p(r):\mathbb{F}_p]=n$ si y sólo si $p$ es de orden $n$ modulo $k$.$\quad\square$

5voto

jcoby Puntos 2389

He aquí una prueba de que el patrón de alrededor de $\lambda(p,3)$: Como con grado $2$, un polinomio de grado $3$ es irreducible si no tiene raíces, y existe una noncube 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 cúbico polinomio irreducible mod $p$, ya que $p\ne 3$, se puede realizar una traducción, de modo que el coeficiente de $X^2$ es $0$ (deprimente el polinomio). Esto muestra que $\lambda(p,3)\le 3$ y por lo que $\lambda(p,3)=3$.

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

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X