Linear Hensel Lifting

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

$$\equiv$$ (121)

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

$$\equiv$$ (122)

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$)modm^$\ell$,
2. g₀  $\equiv$  g^($\ell$)modm.

Proof. We apply Theorem 13 with

$$\cal {I} \langle \rangle$$ (123)

Thus we have

$$\left(\vphantom{ u_{11} \ u_{12} }\right. \left.\vphantom{ u_{11} \ u_{12} }\right) \left(\vphantom{g_0 \ h_0 }\right. \left.\vphantom{g_0 \ h_0 }\right)$$ (124)

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

$$\left(\vphantom{ \begin{array}{c} s \\ t \end{array} }\right. \begin{array}{c} s \\ t \end{array} \left.\vphantom{ \begin{array}{c} s \\ t \end{array} }\right)$$

such that U U^-1  $\equiv$  $\left(\vphantom{ 1 }\right.$1$\left.\vphantom{ 1 }\right)$modm, that is

$$\equiv$$ (125)

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$)modm^$\ell$ and g  $\equiv$  g^($\ell$)modm hold. We want to compute g^($\ell$+1), h^($\ell$+1) $\in$ R. Let v be such that

$$\ell \ell \ell \ell \ell$$ (126)

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

$$\ell \ell \ell \ell \ell \ell \ell \ell$$ (127)

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

$$\ell \ell \equiv$$ (128)

A solution of this equation is

$$\left(\vphantom{\begin{array}{c} g_{\ell} \\ h_{\ell} \end{array} }\right. \begin{array}{c} g_{\ell} \\ h_{\ell} \end{array} \left.\vphantom{\begin{array}{c} g_{\ell} \\ h_{\ell} \end{array} }\right) \left(\vphantom{ \begin{array}{c} - s v\\ - t v \end{array} }\right. \begin{array}{c} - s v\\ - t v \end{array} \left.\vphantom{ \begin{array}{c} - s v\\ - t v \end{array} }\right)$$ (129)

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

Remark 23   The proof of Theorem 15 provides a solution (g_$\ell$, h_$\ell$) to Equation (128). It is desirable to add constraints such that Equation (128) has a unique soulution. In particular, one would like to guarantee that for every integer $\ell$ the polynomials g^($\ell$) and g₀ have the same degree. This problem is solved in the following sub-section where we study Linear Diophantine Equations.

Definition 10   Let R be a commutative ring with identity element. A linear Diophantine equation over R is an equation of the form

f₁s₁ + ^... + f_ns_n = a (130)

where f₁,..., f_n, a are given in R and where s₁,..., s_n are unknowns in R.

Theorem 16   Let R be an Euclidean domain and let f, g, h, a $\in$ R such that h = gcd(f, g). We consider the linear Diophantine equation

sf + tg = a. (131)

Then the following hold

(i)

Equation (131) has a solution if and only if h divides a.

(ii)

If h $\neq$ 0 and if (s₀, t₀) $\in$ R² is a solution of Equation (131) then every other solution is of the form

$${\frac{{g}}{{h}}} {\frac{{f}}{{h}}} \in$$ (132)

(iii)

If R = F[x] where F is a field, h $\neq$ 0, and if Equation (131) is solvable, where

degf + degg - degh > dega (133)

then there is a unique solution (s₀, t₀) $\in$ R² of Equation (131) such that

degs < degg - degh  and  degt < degf - degh. (134)

Proof. First we prove (i). If (s₀, t₀) $\in$ R² is a solution of Equation (131), then h which divides s₀f + t₀g, divides also a. Conversly, we assume that h = gcd(f, g) divides a. The claim is trivial if h = 0. (Indeed, this implies f = g = 0 and also a = 0.) Otherwise, let (s₀, t₀) $\in$ R² be computed by the Extended Euclidean Algorithm applied to (f, g), such that we have s₀f + t₀g = h. Then (s, t) = (s₀a/h, t₀a/h) is a solution of Equation (131).

Now we prove (ii). Assume h $\neq$ 0 and let (s₀, t₀) $\in$ R² is a solution of Equation (131). Since h $\neq$ 0, then f /h and g/h are coprime. Let (s, t) be in R². Then we have

sf + tg = a	$$\iff$$	(s - s0)f + (t - t0)g = 0
	$$\iff$$	(s - s0)(f /h) = - (t - t0)(g/h)
	$$\iff$$	(s - s0)(f /h) = (t0 - t)(g/h)
	$$\iff$$	(g/h) | (s - s0)  and  (f /h) | (t0 - t)
	$$\iff$$	($$\exists$$r $$\in$$ R) (s - s0) = r(g/h)  and  (t0 - t) = r(f /h)
	$$\iff$$	($$\exists$$r $$\in$$ R) s = s0 + r(g/h)  and  t = t0 - r(f /h).

Finally, we prove (iii). Let (s₁, t₁) $\in$ R² be a solution of Equation (131). Let q and t₀ be the quotient and the remainder of t₁ w.r.t. f /h. Hence we have

t₁ = f /hq + t₀  and  degt₀ < degf - degh. (135)

We define

s₀ = s₁ + qg/h. (136)

Observe that

solves Equation (131) too. By Relation (135) and by hypothesis we have

leading to

Therefore we have

This proves the existence. Let us prove the unicity. Let (s, t) be a solution of Equation (131). We know that there exists r $\in$ R such that s = s₀ + rg/h. Since degs₀ < degg - degh holds, if r $\neq$ 0, we have

$$\geq$$

This implies the uniquemess. $\qedsymbol$

Theorem 17   Let R be a commutative ring with identity element. Let f, g₀, h₀ 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

$$\equiv$$ (137)

and that g₀ and h₀ 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$)modm^$\ell$,
2. g₀  $\equiv$  g^($\ell$)modm,
3. h₀  $\equiv$  h^($\ell$)modm.

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

$$\equiv \ell \ell \ell$$ (138)

and

$$\equiv \ell \equiv \ell$$ (139)

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

$$\equiv \ell \ell \ell$$ (140)

So the induction hypothesis leads to

$$\ell \equiv \ell \ell \ell \equiv \ell \ell$$ (141)

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

$$\ell \ell \ell \ell \ell \ell$$ (142)

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

degq_g < degg₀  and  degq_h < degh₀ (143)

In addition, observe that combining Equation (138) and Equation (142) we obtain

f

$$\equiv$$

g($\ell$)h($\ell$) + $$\left(\vphantom{g^{({\ell})} q_h + h^{({\ell})} q_g }\right.$$g($\ell$)qh + h($\ell$)qg$$\left.\vphantom{g^{({\ell})} q_h + h^{({\ell})} q_g }\right)$$m$\ell$modm$\ell$+1

(144)

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

$$\equiv {\frac{{f - g^{({\ell})} h^{({\ell})} }}{{m^{\ell}}}}$$ (145)

By Theorem 16 and Equation (143), the Equation (145) has a unique solution. $\qedsymbol$