Linear Newton Iteration

Theorem 1   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_0 \in R$ such that

1. ${\phi}(a) = 0$ ,
2. $a \equiv a_0 \mod{p}$ ,
3. ${\phi}'(a_0) \neq 0 \mod{p}$ .

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

Proof. Let $(a_0, a_1, \ldots, a_d)$ be a $p$ -adic expansion of $a$ w.r.t. $p$ . Let $k < d + 1$ be a positive integer. By Proposition 6, the element

$$a^{(k)} = a_0 + a_1 p + \cdots a_{k-1} p^{k-1}$$ (12)

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

$${\phi}(a^{(k)} + a_k p^k) = {\phi}(a^{(k)}) + {\phi}'(a^{(k)}) a_k p^k + {\psi}(a^{(k)} + a_k p^k) (a_k p^k)^2.$$ (13)

Since we have

$$a \equiv a^{(k)} + a_k p^k \mod{p^{k+1}}$$

we deduce from Proposition 7

$${\phi}(a) \equiv {\phi}(a^{(k)} + a_k p^k) \mod{p^{k+1}}$$ (14)

Since ${\phi}(a) = 0$ this shows that ${\phi}(a^{(k)} + a_k p^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_k p^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}'(a^{(k)}) a_k + {\psi}(a^{(k)} + a_k p^k) (a_k )^2 p^k.$$ (15)

Now observe that

$$\frac{{\phi}(a^{(k)} + a_k p^k)}{p^k} \equiv 0 \equiv {\psi}(a^{(k)} + a_k p^k) (a_k )^2 p^k \mod{p}.$$ (16)

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}'(a^{(k)})) {\Phi}_p(a_k)$$ (17)

Now, since $a \equiv a_0 \mod{p}$ holds we have

$${\Phi}_p({\phi}'(a^{(k)})) \equiv {\Phi}_p({\phi}'(a_0)) \mod{p}$$ (18)

Since ${\phi}'(a_0) \neq 0 \mod{p}$ holds we can solve Equatiion 17 for ${\Phi}_p(a_k)$ . Finally, from Theorem 1, we have ${\deg}(a_k,p) = 0$ such that we can view ${\Phi}_p(a_k)$ as $a_k$ . This is straightforward if $R = {\mbox{${\mathbb{Z}}$}}$ or if $R = {\bf k}[x]$ where ${\bf k}$ is a field, since we can choose for ${\Phi}_p(x)$ the remainder of $x$ modulo $p$ . $\qedsymbol$

Theorem 2   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_1, \ldots, f_n \in R[x_1, \ldots, x_r]$ be $n$ multivariate polynomials in the $r$ variables $x_1, \ldots, x_r$ . Let $a_1, \ldots, a_r \in R$ be elements. Let $U$ be the Jacobian matrix of $f_1, \ldots, f_n$ evaluated at $(a_1, \ldots, a_r)$ . That is, $U$ is the $n \times r$ matrix defined by

$$U = (u_{ij}) \ \ {\rm where} \ \ u_{ij} = \frac{{\partial} f_i}{{\partial} x_j}(a_1, \ldots, a_r)$$ (19)

We assume that the following properties hold

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

Then, for every positive integer ${\ell}$ we can compute $a^{({\ell})}_1, \ldots, a^{({\ell})}_r \in R$ such that

1. for every $i = 1, \ldots, n$ we have $f_i(a^{({\ell})}_1, \ldots, a^{({\ell})}_r) \equiv 0 \mod {{\cal I}^{\ell}}$ ,
2. for every $j = 1, \ldots, r$ we have $a^{({\ell})}_j \equiv a_j \mod {{\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})}_1, \ldots, a^{({\ell})}_r \in R$ such that

$$f_i(a^{({\ell})}_1, \ldots, a^{({\ell})}_r) \equiv 0 \mod {{\cal I}^{\ell}}, \ \ i = 1, \ldots, n$$ (20)

and

$$a^{({\ell})}_j \equiv a_j \mod {{\cal I}}, \ \ i = 1, \ldots, r$$ (21)

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

$${\cal I}^{\ell} = \langle g_1, \ldots, g_s \rangle$$ (22)

Therefore, for every $i = 1, \ldots, r$ , there exist $q_{i1}, \ldots q_{is} \in R$ such that

$$f_i(a^{({\ell})}_1, \ldots, a^{({\ell})}_r) \ = \ {\Sigma}_{k=1}^{k=s} q_{ik} g_k$$ (23)

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

$$a^{({\ell}+1)}_j = a^{({\ell})}_j + B_j$$ (24)

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

$$B_j \ = \ {\Sigma}_{k=1}^{k=s} b_{jk} g_k$$ (25)

Using Proposition 5 we obtain

$$\begin{array}{rcl} f_i(a^{({\ell}+1)}_1, \ldots, a^{({\ell}+1... ... b_{jk} \right) g_k \mod{{ {\cal I}^{{\ell}+1}}} \\ \end{array}$$ (26)

where $\left( u^{({\ell})}_{ij} \right)$ is the Jacobian matrix of $(f_1, \ldots, f_n)$ at $(a^{({\ell})}_1, \ldots, a^{({\ell})}_r)$ .

Hence, solving for $a^{({\ell}+1)}_1, \ldots, a^{({\ell}+1)}_r \in R$ such that

$$f_i(a^{({\ell}+1)}_1, \ldots, a^{({\ell}+1)}_r) \equiv 0 \mod{{ {\cal I}^{{\ell}+1}}}$$

leads to solving the system of linear equations:

$$q_{ik} + {\Sigma}_{j=1}^{j=r} u^{({\ell})}_{ij} b_{jk} \equiv 0 \mod{{ {\cal I} }}$$ (27)

for $k = 1, \ldots, s$ and $i = 1, \ldots, n$ .

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

$$u^{({\ell})}_{ij} \equiv u_{ij} \mod{{\cal I}}$$ (28)

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