Using Hensel's Lemma to Factor a Polynomial over $\mathbb{Z}_4[x]$

Question

We recently learned about codes over $\mathbb{Z}_4$, and Hensel's Lemma. The lemma is as follows:

Let $f(x) \in \mathbb{Z}_4[x]$. Suppose $\mu(f(x)) = h_1(x)h_2(x) \cdots h_k(x)$, where $h_1(x), h_2(x), \ldots , h_k(x)$ are pairwise coprime polynomials in $\mathbb{F}_2[x]$. Then, there exist $g_1(x),g_2(x), \ldots , g_k(x)$ in $\mathbb{Z}_4[x]$ such that:

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

(ii) $g_1(x), g_2(x), \ldots , g_k(x)$ are pairwise coprime, and

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

The map $\mu: \mathbb{Z}_4[x] \rightarrow \mathbb{F}_2[x]$ is defined by $\mu(f(x)) = f(x)(\mbox{mod } 2)$. It is also known at the reduction homomorphism.

I am interested in trying to factor $x^7 + 2x^6 + 2x^4 + 2x + 3$ as a product of basic irreducible polynomials in $\mathbb{Z}_4[x]$. I'm trying to follow the proof of this theorem, which can be found in Fundamentals of Error Correcting Codes by Huffman and Pless, on page 477.

So far, I figured out that $\mu(f(x)) = x^7 + 1$, which can be factored into: $$(x + 1)(x^3 + x^2 + 1)(x^3 + x + 1).$$ Now, I know these are pairwise coprime in $\mathbb{F}_2[x]$, but I am having trouble finding the pairwise coprime polynomials $g_1(x), g_2(x),$ and $g_3(x)$ such that $f(x) = g_1(x)g_2(x)g_3(x)$ and $\mu(g_i(x)) = h_i(x)$ for $i=1,2,3$.

I've been messing around with this, but I can't get anywhere. Any help would be greatly appreciated.

EDIT

After messing around with various combinations of $x+1$, $x^3 + 2x^2 + x + 1$, and $x^3 + x^2 + 2x + 1$ on WolframAlpha, I somehow stumbled across a combination in $Z_4[x]$ that works, but I'm not sure how to figure it out using a more concrete method.

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

• These are pairwise 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

Well, lifting the linear factor is easy, because the lift of $h_1(x)=x+1$ can only be either $x+1$ or $x+3=x-1$. We observe that $f(-1)\equiv0\pmod4$, so let's use $x+1$. The other factor we get by long division (the usual division algorithm by a monic polynomial works also in $\mathbb{Z}_4[x]$), and after this step we have $$ f(x)=(x+1)(x^6+x^5-x^4-x^3+x^2-x-1). $$

Then we need to lift the factors $h_2(x)=x^3+x+1$ and $h_3(x)=x^3+x^2+1$. We can always select the lifts to be monic, so we must have $$ g_2(x)=h_2(x)+2r_2(x),\qquad g_3(x)=h_3(x)+2r_3(x), $$ with $r_2(x)$ and $r_3(x)$ at most quadratic. Here I am slightly abusing the notation, as I "identify" the elements $0,1\in\mathbb{Z}_2$ with $0,1\in\mathbb{Z}_4$, and similarly identify polynomials of $\mathbb{Z}_2[x]$ with their counterparts in $\mathbb{Z}_4[x]$.

Anyway, when we view $h_2(x)$ and $h_3(x)$ as polynomials in $\mathbb{Z}_4[x]$, their product is (note: $3\equiv-1\pmod4$) $$ h_2(x)h_3(x)=x^6+x^5+x^4-x^3+x^2+x+1. $$

We want $g_2(x)g_3(x)$ to be equal to the sextic factor $\tilde{f}(x)=x^6+x^5-x^4-x^3+x^2-x-1$ from the above factorization of $f(x)$. As $(2r_2(x))(2r_3(x))\equiv 0\pmod4$, we get the following constraint on the polynomials $r_2$ and $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). $$ We know both $\tilde{f}(x)$ and $h_2(x)h_3(x)$, so the remaining equation is $$ \tilde{f}(x)-h_2(x)h_3(x)=2x^4+2x+2=2r_3(x)h_2(x)+2r_2h_3(x). $$ Dividing this by two allows us to rewrite it as an equation in the ring $\mathbb{Z}_2[x]$: $$ x^4+x+1=r_3(x)(x^3+x+1)+r_2(x)(x^3+x^2+1). $$ At this point all the good properties of $\mathbb{Z}_2[x]$ kick in. Most notably it is a Euclidean domain. As $\gcd(x^3+x+1,x^3+x^2+1)=1$, we can write the constant polynomial $1$ as their linear combination (Bezout's identity). A run of Euclid's algorithm (or tinkering) shows that we have $$ x h_2(x)+(x+1)h_3(x)=1. $$ Multiplying this by $x^4+x+1$ gives $$ (x^5+x^2+x)h_2(x)+(x^5+x^4+x^2+1)h_3(x)=x^4+x+1.\qquad(*) $$ We want those multipliers to be at most quadratic, so we need to do something about that. The usual trick is that we can add the same multiple of $h_2(x)h_3(x)$ to both terms (characteristic two now!). That first multiplier $x^5+x^2+x$ is equal to $$ 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), $$ so we subtract the polynomial $q(x)=(x^2+x+1)h_2(x)h_3(x)$ from both terms of the l.h.s. of $(*)$. As $(x^2+x+1)h_2(x)=x^5+x^4+1$, we have $q(x)=(x^5+x^4+1)h_3(x)$. Hence equation $(*)$ can be rewritten as $$ (x^2+1)h_2(x)+x^2h_3(x)=x^4+x+1, $$ which we can also verify directly. Finally we can see that $r_3(x)=x^2+1$ and $r_2(x)=x^2$ will work. Thus $$ g_2(x)=h_2(x)+2r_2(x)=x^3+2x^2+x+1 $$ and $$ g_3(x)=h_3(x)+2r_3(x)=x^3+3x^2+3=x^3-x^2-1. $$ At this point I encourage you to check that we have $$ g_2(x)g_3(x)=\tilde{f}(x) $$ in the ring $\mathbb{Z}_4[x]$ as required. (I did it, so you have to, too!)

The final factorization is thus $$ f(x)=(x+1)(x^3+2x^2+x+1)(x^3-x^2-1). $$

Above I somewhat wantonly jumped from $\mathbb{Z}_4$ to $\mathbb{Z}_2$ and back. You need to keep track of the changes for everything to make sense!

Answer 2

The trick is to take your three factors that work modulo $2$, consider them as polynomials over $\mathbb Z/(4)$, call the resulting things $H_1$, $H_2$, and $H_3$. Now to each of these three polynomials $H_i$ add an adjustment $2h_i$ with undetermined coefficients. Next multiply all the $\mathbb Z/(4)$-polynomials $H_i+2h_i$ together, dropping out all the coefficients that are divisible by $4$, and see what the conditions on the coefficients of the $h_i$'s are that guarantee that the product you calculated is equal to $x^7 +2(x^6+x^4+x)+3$. I confess that I haven’t worked this out myself, and I fear that the computation may get hairy.

Maybe I should also say that the standard proof in a textbook would be for just two factors rather than three, and there it is far clearer what to do computationally.

Answer 3

We are going to lift the $\mathbb{F}_2$-factorization $$\bar{f} = (\underbrace{x^3 + x + 1}_{=:g})(\underbrace{x^4 + x^2 + x + 1}_{=:h})$$ to $\mathbb{Z}_4$. That is, considering $g$ and $h$ as polynomials in $\mathbb{Z}_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).$$ Since $2\cdot 2 = 0$, we get $$f = gh + 2(ah + gb)$$ With $gh = x^7 + 2x^5 + 2x^4 + 2x^3 + 2x^2 + 2x + 1$ this implies $$2(ah + gb) = 2x^6 + 2x^5 + 2x^3 + 2x^2 + 2.$$ Equivalently, in $\mathbb{F}_2[x]$ $$ah + gb = x^6 + x^5 + x^3 + x^2 + 1.$$ Writing $a = a_2x^2 + a_1x + a_0$ and $b = b_3x^3 + b_2x^2 + b_1x + b_0$, expanding the left hand side gives $$(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.$$ Rewriting this as a system of $\mathbb{F}_2$-linear equations: $$\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}. $$ Note that the equation system matrix is the Sylvester matrix of $g$ and $h$. It is invertible, because its determinant is the resultant of $g$ and $h$ which is nonzero since $g$ and $h$ are coprime. So there is a unique solution $(a_0,a_1,a_2,b_0,b_1,b_2,b_3) = (0,0,1,1,1,1,0)$ which finally gives the $\mathbb{Z}_4$-factorization $$f = (x^3 + 2x^2 + x + 1)(x^4 + 3x^2 + 3x + 3)$$

You can do the same again to find the $\mathbb{Z}_4[x]$-factorization of $x^4 + 3x^2 + 3x + 3$. The final result is $$f = (x^3 + 2x^2 + x + 1)(x+1)(x^3 + 3x^2 + 3).$$