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

Solution 1:

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.