## Linear Newton Iteration

Theorem 1   Let be an Euclidean domain with a regular Euclidean size . Let be a prime element. Let and let such that
1. ,
2. ,
3. .
If is unknown, but and are known then we can compute a -adic expansion of . Therefore we can compute exactly.

Proof. Let be a -adic expansion of w.r.t. . Let be a positive integer. By Proposition 6, the element

 (12)

is a -adic approximation of at order . By Proposition 4 there exists a polynomial such that

 (13)

Since we have

we deduce from Proposition 7

 (14)

Since this shows that is in the ideal generated by . Similarly, is in the ideal generated by . Therefore we can divide and by , leading to

 (15)

Now observe that

 (16)

Let us denote by the canonical homomorphism from to . Then we obtain

 (17)

Now, since holds we have

 (18)

Since holds we can solve Equatiion 17 for . Finally, from Theorem 1, we have such that we can view as . This is straightforward if or if where is a field, since we can choose for the remainder of modulo .

Theorem 2   Let be a commutative ring with identity element and let be a finitely generated ideal of . Let be a positive integer. Let be multivariate polynomials in the variables . Let be elements. Let be the Jacobian matrix of evaluated at . That is, is the matrix defined by

 (19)

We assume that the following properties hold
1. for every we have .
2. the Jacobian matrix is left-invertible modulo .
Then, for every positive integer we can compute such that
1. for every we have ,
2. for every we have .

Proof. We proceed by induction on . For the claim follows from the hypothesis of the theorem. So let be such that the claim is true. Hence there exist such that

 (20)

and

 (21)

Since is finitely generated, then so is and let such that

 (22)

Therefore, for every , there exist such that

 (23)

For each we want to compute such that

 (24)

is the desired next approximation. We impose so let be such that

 (25)

Using Proposition 5 we obtain

 (26)

where is the Jacobian matrix of at .

Hence, solving for such that

leads to solving the system of linear equations:

 (27)

for and .

Now using for we obtain

 (28)

Therefore the linear system equations given by Relation (27) has solutions.

Marc Moreno Maza
2008-01-07