El uso de Hensel del Lema para factorizar un Polinomio sobre $\mathbb{Z}_4[x]$

Question

Recientemente hemos aprendido acerca de los códigos de más de $\mathbb{Z}_4$, y Hensel del Lexema. El lema es el siguiente:

Deje $f(x) \in \mathbb{Z}_4[x]$. Supongamos $\mu(f(x)) = h_1(x)h_2(x) \cdots h_k(x)$ donde $h_1(x), h_2(x), \ldots , h_k(x)$ son parejas coprime polinomios en $\mathbb{F}_2[x]$. Entonces, no existe $g_1(x),g_2(x), \ldots , g_k(x)$ $\mathbb{Z}_4[x]$ tal forma que:

(i)$\mu(g_i(x)) = h_i(x)$$1 \leq i \leq k$,

(ii) $g_1(x), g_2(x), \ldots , g_k(x)$ son parejas coprime, y

(iii) $f(x) = g_1(x)g_2(x) \cdots g_k(x)$.

El mapa de $\mu: \mathbb{Z}_4[x] \rightarrow \mathbb{F}_2[x]$ está definido por $\mu(f(x)) = f(x)(\mbox{mod } 2)$. También es conocido en la reducción de la homomorphism.

Estoy interesado en probar a factor de $x^7 + 2x^6 + 2x^4 + 2x + 3$ como un producto básico de polinomios irreducibles en $\mathbb{Z}_4[x]$. Estoy tratando de seguir la prueba de este teorema, el cual puede ser encontrado en los Fundamentos de los Códigos de Corrección de Errores por Huffman y Pless, en la página 477.

Hasta ahora, me di cuenta de que $\mu(f(x)) = x^7 + 1$, que puede ser factorizado en: $$(x + 1)(x^3 + x^2 + 1)(x^3 + x + 1).$$ Ahora, yo sé que estos son pares coprime en $\mathbb{F}_2[x]$, pero estoy teniendo problemas para encontrar los pares coprime polinomios $g_1(x), g_2(x),$ $g_3(x)$ tal que $f(x) = g_1(x)g_2(x)g_3(x)$ e $\mu(g_i(x)) = h_i(x)$ $i=1,2,3$.

He estado jugando con esto, pero no puedo llegar a ninguna parte. Cualquier ayuda sería muy apreciada.

EDITAR

Después de jugar con diferentes combinaciones de $x+1$, $x^3 + 2x^2 + x + 1$, y $x^3 + x^2 + 2x + 1$ en WolframAlpha, de algún modo me topé con una combinación en $Z_4[x]$ que funciona, pero no estoy seguro de cómo descifrarlo utilizando una más concreta método.

$$g_1(x) = x+1,$$ $$g_2(x) = x^3 + 3 x^2 - 1,$$ $$g_3(x) = x^3 - 2x^2 + x + 1.$$

• Estos son pares coprime

• $\mu(g_1(x)) = x+1$, $\mu(g_2(x)) = x^3 + x^2 + 1$, $\mu(g_3(x)) = x^3 + x + 1$

• $g_1(x)g_2(x)g_3(x) = x^7+2 x^6-4 x^5-2 x^4+8 x^3+4 x^2-2 x-1 = x^7 + 2x^6 + 2x^4 + 2x + 3 = f(x)$.

Answer 1

Así, el levantamiento de la lineal factor es fácil, porque el ascensor de $h_1(x)=x+1$ sólo puede ser $x+1$ o $x+3=x-1$. Se observa que el $f(-1)\equiv0\pmod4$, lo que vamos a utilizar $x+1$. El otro factor se obtiene haciendo la división larga (la habitual algoritmo de la división por un monic polinomio funciona también en $\mathbb{Z}_4[x]$), y después de este paso que hemos $$ f(x)=(x+1)(x^6+x^5-x^4-x^3+x^2-x-1). $$

Entonces necesitamos para levantar los factores de $h_2(x)=x^3+x+1$$h_3(x)=x^3+x^2+1$. Siempre podemos seleccionar los ascensores para ser monic, por lo que debemos tener $$ g_2(x)=h_2(x)+2r_2(x),\qquad g_3(x)=h_3(x)+2r_3(x), $$ con $r_2(x)$ $r_3(x)$ en la mayoría de los cuadrática. Aquí estoy ligeramente abusando de la notación, como yo "identificar" los elementos $0,1\in\mathbb{Z}_2$ $0,1\in\mathbb{Z}_4$ e, igualmente, identificar los polinomios de $\mathbb{Z}_2[x]$ con sus homólogos en $\mathbb{Z}_4[x]$.

De todos modos, cuando vemos a $h_2(x)$ $h_3(x)$ como polinomios en $\mathbb{Z}_4[x]$, su producto es (nota: $3\equiv-1\pmod4$) $$ h_2(x)h_3(x)=x^6+x^5+x^4-x^3+x^2+x+1. $$

Queremos $g_2(x)g_3(x)$ a ser igual a la sextic factor de $\tilde{f}(x)=x^6+x^5-x^4-x^3+x^2-x-1$ desde el anterior factorización de $f(x)$. Como $(2r_2(x))(2r_3(x))\equiv 0\pmod4$, se obtiene el siguiente restricción en la polinomios $r_2$$r_3$: $$ \tilde{f}(x)=g_2(x)g_3(x)=h_2(x)h_3(x)+2r_2(x)h_3(x)+2r_3(x)h_2(x). $$ Sabemos que tanto $\tilde{f}(x)$$h_2(x)h_3(x)$, por lo que el resto de la ecuación es $$ \tilde{f}(x)-h_2(x)h_3(x)=2x^4+2x+2=2r_3(x)h_2(x)+2r_2h_3(x). $$ Dividiendo esto por dos, nos permite volver a escribir como una ecuación en el ring $\mathbb{Z}_2[x]$: $$ x^4+x+1=r_3(x)(x^3+x+1)+r_2(x)(x^3+x^2+1). $$ En este punto todas las buenas propiedades de $\mathbb{Z}_2[x]$ patada en. Más en particular, es un dominio Euclídeo. Como $\gcd(x^3+x+1,x^3+x^2+1)=1$, podemos escribir el polinomio constante $1$ como su combinación lineal (la identidad de Bezout). Una de ejecutar el algoritmo de Euclides (o jugando) muestra que hemos $$ x h_2(x)+(x+1)h_3(x)=1. $$ Multiplicando esto por $x^4+x+1$ da $$ (x^5+x^2+x)h_2(x)+(x^5+x^4+x^2+1)h_3(x)=x^4+x+1.\qquad(*) $$ Queremos que los multiplicadores a ser en la mayoría de los cuadrática, por lo que tenemos que hacer algo sobre eso. El truco habitual es que podemos agregar el mismo múltiplo de $h_2(x)h_3(x)$ a ambos términos (característico dos ahora!). Ese primer multiplicador $x^5+x^2+x$ es igual a $$ x^5+x^2+x=x^2 h_3(x)+x^4+x=(x^2+x)h_3(x)+x^3=(x^2+x+1)h_3(x)+(x^2+1), $$ así que restar el polinomio $q(x)=(x^2+x+1)h_2(x)h_3(x)$ a partir de los dos términos de la l.h.s. de $(*)$. Como $(x^2+x+1)h_2(x)=x^5+x^4+1$,$q(x)=(x^5+x^4+1)h_3(x)$. Por lo tanto la ecuación de $(*)$ puede escribirse como $$ (x^2+1)h_2(x)+x^2h_3(x)=x^4+x+1, $$ que también podemos verificar directamente. Finalmente podemos ver que $r_3(x)=x^2+1$ $r_2(x)=x^2$ va a trabajar. Así $$ g_2(x)=h_2(x)+2r_2(x)=x^3+2x^2+x+1 $$ y $$ g_3(x)=h_3(x)+2r_3(x)=x^3+3x^2+3=x^3-x^2-1. $$ En este punto me animo a comprobar que tenemos $$ g_2(x)g_3(x)=\tilde{f}(x) $$ en el ring $\mathbb{Z}_4[x]$ como se requiere. (Yo lo hice, así que, también!)

El final de la factorización es así $$ f(x)=(x+1)(x^3+2x^2+x+1)(x^3-x^2-1). $$

Arriba, yo un poco arbitrariamente, saltó de $\mathbb{Z}_4$ $\mathbb{Z}_2$y la espalda. Usted necesita para mantener un seguimiento de los cambios para que todo sentido!

Answer 2

El truco es tomar tus tres factores que trabajo modulo $2$, consideran como los polinomios de más de $\mathbb Z/(4)$, llame a la resultante de las cosas $H_1$, $H_2$, y $H_3$. Ahora a cada uno de estos tres polinomios $H_i$ agregar un ajuste $2h_i$ con coeficientes indeterminados. Luego multiplique todas las $\mathbb Z/(4)$-polinomios $H_i+2h_i$ juntos, el abandono de todos los coeficientes que son divisibles por $4$, y ver cuáles son las condiciones en los coeficientes de las $h_i$'s son los que garantizan que el producto que usted calculada es igual a $x^7 +2(x^6+x^4+x)+3$. Confieso que no he trabajado esto a mí, y me temo que el cálculo puede obtener peludo.

Tal vez debo decir también que el estándar de prueba en un libro de texto sería de sólo dos factores, en lugar de tres, y es mucho más claro qué hacer computacionalmente.

Answer 3

Vamos a levantar la $\mathbb{F}_2$-factorización $$\bar{f} = (\underbrace{x^3 + x + 1}_{=:g})(\underbrace{x^4 + x^2 + x + 1}_{=:h})$$ to $\mathbb{Z}dimm_4$. That is, considering $g$ and $h$ as polynomials in $\mathbb{Z}dimm_4[x]$, we look for lift-polynomials $a,b\in\mathbb{F}_2[x]$, $\deg(a)\leq 2$, $\deg(b)\leq 3$ such that $$f = (g + 2a)(h + 2b).$$ Desde $2\cdot 2 = 0$, obtenemos $$f = gh + 2(ah + gb)$$ Con $gh = x^7 + 2x^5 + 2x^4 + 2x^3 + 2x^2 + 2x + 1$ esto implica $$2(ah + gb) = 2x^6 + 2x^5 + 2x^3 + 2x^2 + 2.$$ De forma equivalente, en $\mathbb{F}_2[x]$ $$ah + gb = x^6 + x^5 + x^3 + x^2 + 1.$$ Escrito $a = a_2x^2 + a_1x + a_0$$b = b_3x^3 + b_2x^2 + b_1x + b_0$, ampliando el lado izquierdo da $$(a_2 + b_3)x^6 + (a_1 + b_2)x^5 + (a_0 + a_2 + b_3)x^4 + (a_1 + a_2 + b_0 + b_2 + b_3)x^3 + (a_0 + a_1 + a_2 + b_1 + b_2)x^2 + (a_0 + a_1 + b_0 + b_1)x + (a_0 + b_0)\\ = x^6 + x^5 + x^3 + x^2 + 1.$$ La reescritura de este como un sistema de $\mathbb{F}_2$-ecuaciones lineales: $$\begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ b_0 \\ b_1 \\ b_2 \\ b_3 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \end{pmatrix}. $$ Tenga en cuenta que el sistema de ecuaciones de la matriz es la matriz de Sylvester $g$$h$. Es invertible, ya que su determinante es la resultante de $g$ $h$ que es distinto de cero desde $g$ $h$ son coprime. Así que no hay una única solución $(a_0,a_1,a_2,b_0,b_1,b_2,b_3) = (0,0,1,1,1,1,0)$ que finalmente da el $\mathbb{Z}_4$-factorización $$f = (x^3 + 2x^2 + x + 1)(x^4 + 3x^2 + 3x + 3)$$

Usted puede hacer lo mismo otra vez para encontrar la $\mathbb{Z}_4[x]$-factorización de $x^4 + 3x^2 + 3x + 3$. El resultado final es $$f = (x^3 + 2x^2 + x + 1)(x+1)(x^3 + 3x^2 + 3).$$