Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$.

share|improve this question
    
When you write $\,\Bbb Z_4[x]\,$ , do you mean the polynomial ring over the non-field ring $\,\Bbb Z_4\,$ , or you actually meant the field with four elements $\,\Bbb F_4\,$ ...? –  DonAntonio Mar 7 '13 at 20:30
4  
@DonAntonio Quite possibly $Z_4$: codes over that ring are so popular they have an entire chapter in Fundamentals of Error-Correcting Codes by Huffman, and Pless (Chapter 12). –  rschwieb Mar 7 '13 at 20:35
    
Oh, actually now I see that the OP cited Huffman and Pless... then this is certainly the situation. –  rschwieb Mar 7 '13 at 20:36
    
Thanks, @rschwieb . –  DonAntonio Mar 7 '13 at 20:41
    
Yes, by $\mathbb{Z}_4[x]$, I mean the polynomial ring. –  josh Mar 7 '13 at 21:01

3 Answers 3

up vote 4 down vote accepted

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!

share|improve this answer
2  
The $\mathbb{Z}_4$-codes were a topic of intense research in the 90s. Yours truly has the pleasure of playing a small part in that activity. Therefore I cherish this opportunity to refresh some of the algebra. Planning a comeback? I'm off to bed now (12.45 a.m. here), so I can answer the eventual question only tomorrow. –  Jyrki Lahtonen Mar 7 '13 at 22:44
    
Thanks for the wonderful explanation! Your reasoning followed the proof of Hensel's lemma more, and it was easy to follow. –  josh Mar 8 '13 at 0:58

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.

share|improve this answer

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).$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.