Next: Symbolic Newton Iteration
Up: Advanced Computer Algebra: From Newton
Previous: Division with remainder using Newton
The goal of this section is to formalize in an algebraic
point of view the notions of expansions and approximations
well known in numerical analysis.
Definition 6
Let
R be an Euclidean domain and let
p R be a prime
element.
Let
a E be an element.
We say that
a has
degree zero w.r.t. p and we write
deg(
a,
p) = 0 if for every positive integer
k
the quotient of
a w.r.t.
p^{k} is zero.
Assume from now on that
a does not have degree zero w.r.t.
p.
If for every positive integer
there exists a
positive integer
k >
such that
the quotient of
a w.r.t.
p^{k} is not zero,
then we say
a has
infinite degree w.r.t. p and we write
deg(
a,
p) = +
,
otherwise we say that
a has
finite degree w.r.t. p and we write
deg(
a,
p) < +
.
Assume furthermore that
deg(
a,
p) < +
holds.
The largest positive integer
k
such that the quotient of
a w.r.t.
p^{k} is not zero
is called the
degree of a w.r.t. p and
is denoted by
deg(
a,
p).
Definition 7
The Euclidean size
of an Euclidean domain
R
is said
regular if for every
a,
b R with
b 0
there exists a couple
(
q,
r)
E×
E such that

a = bq + r,

r 0 (r) < (b),

q 0 (q) < (a) and (b) (a).
Proposition 8
Let
R be an Euclidean domain with a regular
Euclidean size
.
Let
p be a prime element.
Then for every nonzero
a E there exists
an integer
d N and elements
a_{0},
a_{1},...,
a_{d} E such that

a = a_{d}p^{d} + ^{ ... } + a_{1}p + a_{0},

a_{d} 0,
 for every
i = 0^{ ... }d we have
deg(a_{i}, p) = 0.
The sequence
(
a_{0},
a_{1},...,
a_{d}) is called
a
p
adic expansion of
a w.r.t.
p.
Proof.
Let (
q_{0},
a_{0}) be a couple quotientremainder
given as in
Definition
7
when dividing
a w.r.t.
p.
First we prove that a_{0} must have degree 0 w.r.t. p.
This is obvious if a_{0} = 0.
So let us assume that
a_{0} 0 holds.
This implies
(p) > (a_{0}).
If a_{0} would have positive degree k w.r.t. p,
then, by the properties of a regular Euclidean size,
we would have
(a_{0}) (p^{k}).
Since
(p^{k}) (p) holds (by definition
of an Euclidean domain) we would have a contradiction
with
(p) > (a_{0}).
Therefore in any case we have
deg(a_{0}, p) = 0.
Next, let us prove the proposition for those elements a
which have quotient 0 w.r.t. p.
Observe that if one quotient of a w.r.t. p is zero
then we have
(a) < (p).
Hence every quotient of a w.r.t. p is null.
(Otherwise we would have
(p) (a)
by the properties of a regular Euclidean size.)
Since a = a_{0} and since a_{0} has degree 0 w.r.t. p,
the element a has degree 0 w.r.t. p and (a_{0})
is a padic expansion of a w.r.t. p.
Therefore the proposition is proved in the case
of the elements a which have quotient 0 w.r.t. p.
We can assume now that a does not have quotient 0 w.r.t. p
and thus
q_{0} 0 and
(q_{0}) < (a) hold.
Then let
(q_{1}, a_{1}) be a couple quotientremainder
given as in
Definition 7
when dividing q_{0} w.r.t. p.
If
q_{1} 0 then we have
(q_{1}) < (q_{0})
and let
(q_{2}, a_{2}) be a couple quotientremainder
given as in
Definition 7
when dividing q_{1} w.r.t. p.
Continuing in this manner we obtain a finite sequence
a_{0}, a_{1},..., a_{d} R and a finite sequence
q_{0}, q_{1},..., q_{d} R such that we have
a 
= 
q_{0}p + a_{0} 
with 
q_{0} 

0 
q_{0} 
= 
q_{1}p + a_{1} 
with 
q_{1} 

0 
q_{1} 
= 
q_{2}p + a_{2} 
with 
q_{2} 

0 







q_{d2} 
= 
q_{d1}p + a_{d1} 
with 
q_{d1} 

0 
q_{d1} 
= 
q_{d}p + a_{d} 
with 
q_{d} 
= 
0 


This process stops since we have
(a) > (q_{0}) > (q_{1}) > (q_{2}) > ^{ ... } > (q_{d1}) 
(83) 
and since the Euclidean size of an element has value
in
{ 
}.
Clearly we have
a = a_{d}p^{d} + ^{ ... } + a_{1}p + a_{0}. 

Moreover
a_{d} =
q_{d1} 0 holds.
In addition, for every
i = 0
^{ ... }d we have
deg(
a_{i},
p) = 0
by the first part of this proof.
Proposition 9
Let
R be a commutative ring with identity element.
Let
R[
y] be a polynomial of degree
n
and let
g R be an element.
We define
p =
y 
g.
There exists a unique sequence
,
,...,
R
such that we have
= + p + ^{ ... } + p^{n}. 
(84) 
The above expression is called the
Taylor expansion
of
at
g,
Proof.
By induction on
n.
If
n = 0, the result is clear.
Otherwise let
q and
r be the quotient and the remainder
in the division of
by
p. We have
= qp + r and r R. 

Since
r =
(
g) the conclusion
(existence and unicity) follows by the induction hypothesis.
Remark 16
We can characterize the Taylor expansion
of at g by means of the notion
of a formal derivative.
Definition 8
Let
R be a commutative ring with identity element.
For
= + y + y^{2} + ^{ ... } + y^{n} 

we define the
formal derivative of
by
^{} = + 2y + ^{ ... } + ny^{n1}. 
(85) 
Remark 17
The terminology formal derivative comes
from the fact that we do not make use of the notion
of a limit to define this derivative.
Indeed, if R is a finite ring, then this would
not make clear sense.
However we retrieve the usual properties of derivatives.
Proof.
See Lemma 9.19 in [
vzGG99].
Proposition 11
Let
R be a commutative ring with identity element.
Let
R[
y] and let
g R.
There exists a polynomial
R[
y] such that we have
(y) = (g) + ^{}(g)(y  g) + (y)(y  g)^{2}. 
(86) 
Proof.
Follows easily from
Proposition
9.
Remark 18
Proposition 9
admits several generalizations.
First one can use a monic polynomial p
of degree d > 1.
In this case the coefficients
,,...,
are polynomials of degree less than d.
Another generalization,
given by
Proposition 12,
is for multivariate polynomials.
To understand this generalization, it is important
to make the following three observations.
 First, in
Proposition 11,
one can consider g as a new indeterminate,
and then the result holds for a polynomial
R[y, g].
 Secondly, the notion of a formal derivative
of a univariate polynomial (over a commutative ring
with identity element) leads
naturally to the notion of a partial derivative
of a multivariate polynomial w.r.t. a variable.
We will not detail this here,
since this is quite straightforward
 The quantity
(y  g)^{2}
in Relation (86)
lies in the ideal
yg.
Proposition 12
Let
R be a commutative ring with identity element.
We consider the ring of multivariate polynomials
P =
R[
x_{1},...,
x_{r}][
y_{1},...,
y_{r}].
We define
= (
x_{1},...,
x_{r})
and
= (
y_{1},...,
y_{r}).
For every polynomial
R[
]
there exists a polynomial
P
lying in the ideal
y_{1},...,
y_{r}
such that
(x_{1} + y_{1},..., x_{r} + y_{r}) = () + ()y_{j} + . 
(87) 
Remark 19
Using the vocabulary of numerical analysis,
Propositions 11
and 12
provides a Taylor expansion of of order 2.
This leads to the following definition.
Definition 9
Let
R be a commutative ring with identity element
and let
be an ideal of
R.
Let
a,
b R be elements and
k be a positive integer.
We say that
a is an

adic approximation
of
b at order
k if we have
a b mod^{k}. 
(88) 
Remark 20
We conclude by two useful properties of idealadic approximations.
Proposition 13
Let
R be an Euclidean domain with a regular
Euclidean size
.
Let
p R be a prime element.
Let
a R be an element and let
(
a_{0},
a_{1},...,
a_{d})
be a
padic expansion of
a w.r.t.
p.
For every positive integer
k d + 1 we define
a^{(k)} = a_{0} + a_{1}p + ^{ ... }a_{k1}p^{k1} 
(89) 
Then
a^{(k)} is a
p
adic approximation of
a at order
k,
that is
a^{(k)} a modp^{k}. 
(90) 
Proof.
Indeed, we have
a  a^{(k)} = a_{k}p^{k} + a_{k+1}p^{k+1} + ^{ ... } + a_{d}p^{d} = (a_{k} + a_{k+1}p + ^{ ... } + a_{d}p^{dk})p^{k} 

Proposition 14
Let
R be a commutative ring with identity element
and let
be an ideal of
R.
Let
a,
b R be elements, let
k be a positive integer
and let
R[
y] be a polynomial.
Then we have
a b mod^{k} (a) (b)mod^{k} 
(91) 
That is, if
a is an
adic approximation
of
b at order
k, then
(
a) is an
adic approximation
of
(
b) at order
k.
Proof.
This is simply because of the ringhomomorphism between
R and
R/
.
Next: Symbolic Newton Iteration
Up: Advanced Computer Algebra: From Newton
Previous: Division with remainder using Newton
Marc Moreno Maza
20040427