Linear Hensel Lifting

Theorem 3   Let $R$ be a commutative ring with identity element. Let $f,g_0,h_0$ be univariate polynomials in $R[x]$ and let $m \in R$ . We assume that the following relation holds

$$f \ \equiv \ g_0 \, h_0 \ \mod{ m}$$ (8)

We assume also that $g_0$ and $h_0$ are relatively prime modulo $m$ , that is there exists $s,t \in R$ such that

$$s g_0 + t h_0 \ \equiv \ 1 \ \mod{ m}$$ (9)

Then, for every integer ${\ell}$ there exist $g^{({\ell})}, h^{({\ell})} \in R[x]$ such that we have

1. $f \ \equiv \ g^{({\ell})} h^{({\ell})} \mod{m^{\ell}}$ ,
2. $g_0 \ \equiv \ g^{({\ell})} \mod{ m}$ .

Proof. We apply Theorem  with

$${\cal I} = \langle m \rangle, \ n = 1, \ r = 2, \ f_1(x_1, x_2) = x_1 x_2 - f.$$ (10)

Thus we have

$$U \ = \ \left( u_{11} \ u_{12} \right) \ = \ \left(g_0 \ h_0 \right)$$ (11)

Observe that this matrix is left-invertible modulo $m$ if and only if $g_0, h_0$ are relatively prime modulo $m$ . Indeed, the matrix $U$ is left-invertible modulo $m$ iff there exists a matrix

$$U^{-1} = \left( \begin{array}{c} s \\ t \end{array} \right)$$

such that $U \, U^{-1} \ \equiv \ \left( 1 \right) \mod{ m}$ , that is

$$s g_0 + t h_0 \ \equiv \ 1 \ \mod{ m}$$ (12)

We prove now the claim of the theorem. Assume we have computed $g^{({\ell})}, h^{({\ell})} \in R$ such that $f \ \equiv \ g^{({\ell})} h^{({\ell})} \mod{m^{\ell}}$ and $g \ \equiv \ g^{({\ell})} \mod{ m}$ hold. We want to compute $g^{({\ell}+1)}, h^{({\ell}+1)} \in R$ . Let $v$ be such that

$$f_1(g^{({\ell})}, h^{({\ell})}) = g^{({\ell})} h^{({\ell})} -f = v m^{\ell}$$ (13)

We look for $g_{\ell}, h_{\ell} \in R$ such that

$$g^{({\ell}+1)} = g^{({\ell})} + g_{\ell} m^{{\ell}} \ \ {\rm and} \ \ h^{({\ell}+1)} = h^{({\ell})} + h_{\ell} m^{{\ell}}$$ (14)

Following the proof of Theorem  we are led to solve the equation

$$v + g_{\ell} h_0 + h_{\ell} g_0 \equiv \ 0 \ \mod{ m}$$ (15)

A solution of this equation is

$$\left(\begin{array}{c} g_{\ell} \\ h_{\ell} \end{array} \right) = \left( \begin{array}{c} - s v\\ - t v \end{array} \right)$$ (16)

This proves the claim of the theorem. $\qedsymbol$

Remark 1   The proof of Theorem 3 provides a solution $(g_{\ell}, h_{\ell})$ to Equation (15). It is desirable to add constraints such that Equation (15) has a unique soulution. In particular, one would like to guarantee that for every integer ${\ell}$ the polynomials $g^{({\ell})}$ and $g_0$ have the same degree. As we shall see now, this problem was solved, in fact, by our preliminary study of Linear Diophantine Equations.

Theorem 4   Let $R$ be a commutative ring with identity element. Let $f,g_0,h_0$ be univariate monic polynomials in $R[x]$ . Let $m \in R$ be such that $R/m$ is a field. We assume that the following relation holds

$$f \ \equiv \ g_0 \, h_0 \ \mod{ m}$$ (17)

and that $g_0$ and $h_0$ are relatively prime modulo $m$ . Then, for every integer ${\ell}$ there exist unique monic polynomials $g^{({\ell})}, h^{({\ell})} \in R[x]$ such that we have

1. $f \ \equiv \ g^{({\ell})} h^{({\ell})} \mod{m^{\ell}}$ ,
2. $g_0 \ \equiv \ g^{({\ell})} \mod{ m}$ ,
3. $h_0 \ \equiv \ h^{({\ell})} \mod{ m}$ .

Proof. By induction on ${\ell} \geq 1$ . The clain is clear for ${\ell} = 1$ . So let us assume it is true for ${\ell} \geq 1$ and consider monic polynomials $g^{({\ell}+1)}, h^{({\ell}+1)} \in R[x]$ satisfying

$$f \ \equiv \ g^{({\ell}+1)} h^{({\ell}+1)} \mod{m^{{\ell}+1}}$$ (18)

and

$$g_0 \ \equiv \ g^{({\ell}+1)} \mod{ m} \ \ {\rm and} \ \ h_0 \ \equiv \ h^{({\ell}+1)} \mod{ m}.$$ (19)

Such polynomials $g^{({\ell}+1)}, h^{({\ell}+1)}$ exist by Theorem 3. (The fact that they can be chosen monic is left to the reader as an exercise.) Observe that we have

$$f \ \equiv \ g^{({\ell}+1)} h^{({\ell}+1)} \mod{m^{{\ell}}}$$ (20)

So the induction hypothesis leads to

$$g^{({\ell})} \ \equiv \ g^{({\ell}+1)} \mod{m^{\ell}} \ \ {\rm and} \ \ h^{({\ell})} \ \equiv \ h^{({\ell}+1)} \mod{m^{\ell}}$$ (21)

Hence there exist polynomials $q_g, q_h \in (R/m)[x]$ such that

$$g^{({\ell}+1)} = g^{({\ell})} + m^{\ell} q_g \ \ {\rm and} \ \ h^{({\ell}+1)} = h^{({\ell})} + m^{\ell} q_h.$$ (22)

Since $f,g_0,h_0$ are given to be monic, it is easy to prove that for $k \geq 1$ we have

$${\deg} q_g < {\deg} g_0 \ \ {\rm and} \ \ {\deg} q_h < {\deg} h_0$$ (23)

In addition, observe that combining Equation (18) and Equation (22) we obtain

$$\begin{array}{rcl} f & \equiv & g^{({\ell})} h^{({\ell})} + \... ...{\ell})} q_g \right) m^{\ell} \mod{m^{{\ell}+1}} \\ \end{array}$$ (24)

The induction hypothesis shows that $f - g^{({\ell})} h^{({\ell})}$ is a multiple of $m^{\ell}$ . Then we obtain

$$g_0 q_h + h_0 q_g \ \equiv \ \frac{f - g^{({\ell})} h^{({\ell})} }{m^{\ell}} \mod{ m}.$$ (25)

By Theorem 1 and Equation (23), the Equation (25) has a unique solution. $\qedsymbol$