# Hensel lift of a monic polynomial over $F_{2}$ in $Z_{8}$

Define the map - : $\mathbb{Z}_{p^{s}}\rightarrow \mathbb{F}_{p}$. Let g(x) be a monic polynomial over $\mathbb{F}_{p}$. A monic polynomial f(x) over $\mathbb{Z}_{p^{s}}[x]$ is called a Hensel lift of g(x) if $\overline{f}(x)=g(x)$ and there is a positive integer n not divisible by p such that $f(x)|(x^{n}-1)$ in $\mathbb{Z}_{p^{s}}[x]$. Otherwise, a monic polynomial g(x) over $\mathbb{F}_{p}$ has a Hensel lift f(x) over $\mathbb{Z}_{p^{s}}[x]$ if and only if g(x) has no multiple roots and $x\nmid g(x)$ in $\mathbb{F}_{p}[x]$.

Could you help me to find Hensel lift f(x) over $\mathbb{Z}_{8}$, if i have a monic polynomial g(x) has no multiple roots and $x\nmid g(x)$ in $\mathbb{F}_{2}[x]$?

For example, $g(x)=x^{3}+x+1\in\mathbb{F}_{2}[x]$.

-
Maybe before you put up a new problem you should answer the questions that have been piling up in the comments to your previous question. –  Gerry Myerson Jul 21 '12 at 5:00
My experience with Galois rings suggests that the OP is looking for a polynomial $f(x)\in \mathbb{Z}_8[x]$ such that $$f(x)\equiv g(x)\pmod 2,$$ and that the order of the coset of $x$ in $\mathbb{Z}_8[x]/\langle f(x)\rangle$ is equal to that of the coset of $x$ in $\mathbb{F}_2[x]/\langle g(x)\rangle$. But I agree with @Gerry. You should try and explain exactly what you want. Even though I like to think I'm good at this kind of guessing games :-) –  Jyrki Lahtonen Jul 29 '12 at 10:33

As $g(x)=x^3+x+1$ is a factor of $x^7-1$ in the ring $\mathbb{F}_2[x]$, and seven is the least exponent with this property, I am guessing that you are asking for a monic polynomial $f(x)\in\mathbb{Z}_8[x]$ such that $f(x)\equiv g(x)\pmod 8$, and $f(x)\mid x^7-1$ in the ring $\mathbb{Z}_8[x].$

The Hensel lifting will do exactly this for you, but I will describe another algorithm for lifting a polynomial factor like this. It is, of course, equivalent to Hensel lifting, but it involves an IMHO neat trick I learned while playing with $\mathbb{Z}_4$-linear codes.

Let us first find a similar factorization modulo 4. We can view the polynomial $g(x)$ also as an element of the ring $\mathbb{Z}_4[x].$ Let us form the product $$(-1)^3g(x)g(-x)=(x^3+x+1)(x^3+x-1)=x^6+2x^4+x^2-1=g_2(x^2)$$ in that ring. As the resulting polynomial is obviously even, we see that the polynomial $g_2(x)=x^3+2x^2+x-1\in\mathbb{Z}_4[x]$ has the above property $g_2(x^2)=-g(x)g(-x)$. Furthermore, because $g(-x)\equiv g(x)\pmod 2$, it follows (by uniqueness of factorization in $\mathbb{F}_2[x]$ as well as the identity $p(x^2)=p(x)^2$ that holds for all polynomials in $\mathbb{F}_2[x]$) that $$g_2(x)\equiv g(x)\pmod 2.$$

At this point we record that $g_2(x)$ is the sought lifting in $\mathbb{Z}_4[x].$ Namely, you can easily verify that $$(x^3+2x^2+x-1)(x^4+2x^3-x^2+x+1)\equiv x^7-1 \pmod4.$$

To get a lifting modulo 8 we repeat the dose. View $g_2(x)$ as a polynomial in $\mathbb{Z}_8[x],$ and compute $$(-1)^3g_2(x)g_2(-x)=x^6-2x^4-3x-1=g_3(x^2),$$ where $g_3(x)=x^3-2x^2-3x-1\in\mathbb{Z}_8[x].$ By a direct observation $g_3(x)\equiv g_2(x)\pmod 4$. The polynomial $g_3(x)$ is the answer. You can verify this by checking that $$(x^3-2x^2-3x-1)(x^4+2x^3-x^2-3x+1)\equiv x^7-1 \pmod8.$$

How can I justify this method? Let $\mathcal{O}$ be the ring of $2$-adic integers. It follows from 2-adic theory that the quotient ring $\mathcal{O}[x]/\langle x^3+x+1\rangle$ is isomorphic to the ring of integers $R=\mathcal{O}[\zeta_7]$ of the unramified cubic extension of the field of 2-adic numbers. Here $\zeta_7$ is a suitably chosen primitive seventh root of unity in $R$. This is because the polynomial $g(x)=x^3+x+1$ splits into linear factors in $\mathbb{F}_8[x]$ and, by Hensel lifting, also in $R[x]$. So we can write $$g(x)=x^3+x+1=(x-u_1)(x-u_2)(x-u_3)$$ for some elements $u_1,u_2,u_3$ in $R$. Furthermore, reduction modulo two reveals that (with an appropriate choice of indices) $u_1\equiv \zeta_7\pmod{2R}$, $u_2\equiv \zeta_7^2\pmod{2R}$ and $u_3\equiv \zeta_7^4\pmod{2R}$.

By construction, the roots of $g_2(x)$ in $R$ are the squares of the roots of $g(x)$, i.e. $u_i^2,i=1,2,3,$. But squaring the equations $$u_i=\zeta_7^{2^{i-1}}+2r_i,$$ $r_i\in R, i=1,2,3,$ implies that $$u_i^2=\zeta_7^{2^i}+4r_i\zeta_7^{2^{i-1}}+4r_i^2\equiv\zeta_7^{2^i}\pmod{4R}.$$ In other words, the zeros of $g_2(x)$ in $R/4R$ are primitive seventh roots of unity.

Repeating this calculation shows that the roots of $g_3(x)$ in $R/8R$ are then also seventh roots of unity, which is basically what we wanted to achieve.

-
The justification part is very sketchy. Sorry about that. The answer is probably long enough as it is. If you want to ask about something I will do my best to make the presentation clearer. –  Jyrki Lahtonen Jul 29 '12 at 12:01