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

$\displaystyle 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

$\displaystyle 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

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

Thus we have

$\displaystyle 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

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

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

$\displaystyle 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

$\displaystyle 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

$\displaystyle 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

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

A solution of this equation is

$\displaystyle \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

$\displaystyle 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

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

and

$\displaystyle 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

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

So the induction hypothesis leads to

$\displaystyle 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

$\displaystyle 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

$\displaystyle {\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{displaymath}\begin{array}{rcl} f & \equiv & g^{({\ell})} h^{({\ell})} + \...
...{\ell})} q_g \right) m^{\ell} \mod{m^{{\ell}+1}} \\ \end{array}\end{displaymath} (24)

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

$\displaystyle 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$

Marc Moreno Maza
2008-01-07