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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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.

share|cite|improve this answer
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

Your Answer


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.