Linear Newton Iteration

Theorem 12   Let R be an Euclidean domain with a regular Euclidean size $\delta$. Let p $\in$ R be a prime element. Let $\phi$ $\in$ R[y] and let a, a₀ $\in$ R such that

1. $\phi$(a) = 0,
2. a $\equiv$ a₀modp,
3. $\phi$^$\prime$(a₀) $\neq$ 0 modp.

If a is unknown, but $\phi$ and a₀ are known then we can compute a p-adic expansion of a. Therefore we compute a exactly.

Proof. Let (a₀, a₁,..., a_d) be a p-adic expansion of a w.r.t. p. Let k < d + 1 be a positive integer. By Proposition 13, the element

a^(k) = a₀ + a₁p + ^... a_k-1p^k-1 (92)

is a p-adic approximation of a at order k. By Proposition 11 there exists a polynomial $\psi$ $\in$ R[y] such that

$$\phi \phi \phi \prime \psi$$ (93)

Since we have

$$\equiv$$

we deduce from Proposition 14

$$\phi \equiv \phi$$ (94)

Since $\phi$(a) = 0 this shows that $\phi$(a^(k) + a_kp^k) is in the ideal generated by p^k+1. Similarly, $\phi$(a^(k)) is in the ideal generated by p^k. Therefore we can divide $\phi$(a^(k) + a_kp^k) and $\phi$(a^(k)) by p^k, leading to

$${\frac{{{\phi}(a^{(k)} + a_k p^k)}}{{p^k}}} {\frac{{{\phi}(a^{(k)})}}{{p^k}}} \phi \prime \psi$$ (95)

Now observe that

$${\frac{{{\phi}(a^{(k)} + a_k p^k)}}{{p^k}}} \equiv \equiv \psi$$ (96)

Let us denote by $\Phi_{{p}}^{{}}$ the canonical homomorphism from R to R/$\langle$p$\rangle$. Then we obtain

$$\Phi_{{p}}^{{}} {\frac{{{\phi}(a^{(k)})}}{{p^k}}} \Phi_{{p}}^{{}} \phi \prime \Phi_{{p}}^{{}}$$ (97)

Now, since a $\equiv$ a₀modp holds we have

$$\Phi_{{p}}^{{}} \phi \prime \equiv \Phi_{{p}}^{{}} \phi \prime$$ (98)

Finally, since $\phi$^$\prime$(a₀) $\neq$ 0 modp holds we can solve Equatiion 97 for $\Phi_{{p}}^{{}}$(a_k). $\qedsymbol$

Theorem 13   Let R be a commutative ring with identity element and let $\cal {I}$ be a finitely generated ideal of R. Let r be a positive integer. Let f₁,..., f_n $\in$ R[x₁,..., x_r] be n multivariate polynomials in the r variables x₁,..., x_r. Let a₁,..., a_r $\in$ R be elements. Let U be the Jacobian matrix of f₁,..., f_n evaluated at (a₁,..., a_r). That is, U is the n×r matrix defined by

$${\frac{{{\partial} f_i}}{{{\partial} x_j}}}$$ (99)

We assume that the following properties hold

1. for every i = 1 ^... n we have f_i(a₁,..., a_r) $\equiv$ 0 mod$\cal {I}$.
2. the Jacobian matrix U is left-invertible.

Then, for every positive integer $\ell$ we can compute a^($\ell$)₁,..., a^($\ell$)_r $\in$ R such that

1. for every i = 1,..., n we have f_i(a^($\ell$)₁,..., a^($\ell$)_r) $\equiv$ 0 mod$\cal {I}$^$\ell$,
2. for every j = 1,..., r we have a^($\ell$)_j $\equiv$ a_jmod$\cal {I}$.

Proof. We proceed by induction on $\ell$ $\geq$ 1. For $\ell$ = 1 the claim follows from the hypothesis of the theorem. So let $\ell$ $\geq$ 1 be such that the claim is true. Hence there exist a^($\ell$)₁,..., a^($\ell$)_r $\in$ R such that

$$\ell \ell \equiv \cal {I} \ell$$ (100)

and

$$\ell \equiv \cal {I}$$ (101)

Since $\cal {I}$ is finitely generated, then so is $\cal {I}$^$\ell$ and let g₁,..., g_s $\in$ R such that

$$\cal {I} \ell \langle \rangle$$ (102)

Therefore, for every i = 1,..., n, there exist q_i1,...q_is $\in$ R such that

$$\ell \ell \Sigma_{{{k=1}}}^{{{k=s}}}$$ (103)

For each j = 1,..., r we want to compute B_j $\in$ R such that

$$\ell \ell$$ (104)

is the desired next approximation. We impose B_j $\in$ $\cal {I}$^$\ell$ so let b_j1,..., b_js $\in$ R be such that

$$\Sigma_{{{k=1}}}^{{{k=s}}}$$ (105)

Using Proposition 12 we obtain

fi(a($\ell$+1)1,..., a($\ell$+1)r)	=	fi(a($\ell$)1 + B1,..., a($\ell$)r + Br)
	$$\equiv$$	fi(a($\ell$)1,..., a($\ell$)r) + $$\Sigma_{{{j=1}}}^{{{j=r}}}$$u($\ell$)ijBjmod$$\cal {I}$$$\ell$+1
	$$\equiv$$	$$\Sigma_{{{k=1}}}^{{{k=s}}}$$qikgk + $$\Sigma_{{{j=1}}}^{{{j=r}}}$$u($\ell$)ijBjmod$$\cal {I}$$$\ell$+1
	$$\equiv$$	$$\Sigma_{{{k=1}}}^{{{k=s}}}$$qikgk + $$\Sigma_{{{j=1}}}^{{{j=r}}}$$u($\ell$)ij$$\left(\vphantom{{\Sigma}_{k=1}^{k=s} b_{jk} g_k }\right.$$$$\Sigma_{{{k=1}}}^{{{k=s}}}$$bjkgk$$\left.\vphantom{{\Sigma}_{k=1}^{k=s} b_{jk} g_k }\right)$$mod$$\cal {I}$$$\ell$+1
	$$\equiv$$	$$\Sigma_{{{k=1}}}^{{{k=s}}}$$$$\left(\vphantom{q_{ik} + {\Sigma}_{j=1}^{j=r} u^{({\ell})}_{ij} b_{jk} }\right.$$qik + $$\Sigma_{{{j=1}}}^{{{j=r}}}$$u($\ell$)ijbjk$$\left.\vphantom{q_{ik} + {\Sigma}_{j=1}^{j=r} u^{({\ell})}_{ij} b_{jk} }\right)$$gkmod$$\cal {I}$$$\ell$+1

(106)

where $\left(\vphantom{ u^{({\ell})}_{ij} }\right.$u^($\ell$)_ij$\left.\vphantom{ u^{({\ell})}_{ij} }\right)$ is the Jacobian matrix of (f₁,..., f_n) at (a^($\ell$)₁,..., a^($\ell$)_r).

Hence, solving for a^($\ell$+1)₁,..., a^($\ell$+1)_r $\in$ R such that

$$\ell \ell \equiv \cal {I} \ell$$

leads to solving the system of linear equations:

$$\Sigma_{{{j=1}}}^{{{j=r}}} \ell \equiv \cal {I}$$ (107)

for k = 1,..., s and i = 1,..., n.

Now using a^($\ell$)_j $\equiv$ a_jmod$\cal {I}$ for j = 1,..., r we obtain

$$\ell \equiv \cal {I}$$ (108)

Therefore the system linear equations given by Relation (107) has solutions. $\qedsymbol$