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 1   Let be an Euclidean domain and let be a prime element. Let be an element. We say that has degree zero w.r.t. and we write if for every positive integer the quotient of w.r.t. is zero. Assume from now on that does not have degree zero w.r.t. . If for every positive integer there exists a positive integer such that the quotient of w.r.t. is not zero, then we say has infinite degree w.r.t. and we write , otherwise we say that has finite degree w.r.t. and we write . Assume furthermore that holds. The largest positive integer such that the quotient of w.r.t. is not zero is called the degree of w.r.t. and is denoted by .

Definition 2   The Euclidean size of an Euclidean domain is said regular if for every with there exists a couple such that
1. ,
2. ,
3. ,
4. .

Example 1   The absolute value in the ring of integers and the degree in the ring of univariate polynomials over a field are regular Euclidean sizes.

Proposition 1   Let be an Euclidean domain with a regular Euclidean size . Let be a prime element. Then for every non-zero there exists an integer and elements such that
1. ,
2. ,
3. for every we have .
The sequence is called a -adic expansion of w.r.t. .

Proof. Let be a couple quotient-remainder given as in Definition 2 when dividing w.r.t. .

First we prove that must have degree 0 w.r.t. . This is obvious if . So let us assume that holds. This implies . If would have positive degree w.r.t. , then, by the properties of a regular Euclidean size, we would have . Since holds (by definition of an Euclidean domain) we would have a contradiction with . Therefore in any case we have .

Next, let us prove the proposition for those elements which have quotient 0 w.r.t. . Observe that if one quotient of w.r.t. is zero then we have . Hence every quotient of w.r.t. is null. (Otherwise we would have by the properties of a regular Euclidean size.) Since and since has degree 0 w.r.t. , the element has degree 0 w.r.t. and is a -adic expansion of w.r.t. . Therefore the proposition is proved in the case of the elements which have quotient 0 w.r.t. .

We can assume now that does not have quotient 0 w.r.t. . Then, two cases arise:

• Either both and hold, and this case we have ; then, we consider a couple quotient-remainder given as in Definition 2 when dividing w.r.t. .
• Or . Then, there exists a smallest integer such that the remainder in an division of w.r.t. is not zero. (This follows from the fact that is a Unique Factorization Domain and is a prime.) Let be a couple quotient-remainder in an division of w.r.t. with .
• If , then we stop.
• If , then ; then, we consider a couple quotient-remainder given as in Definition 2 when dividing w.r.t. .
In each case where we consider a couple quotient-remainder , we can repeat a similar discussion as we did for .

Continuing in this manner we obtain a finite sequence , a finite sequence and a finite sequence such that we have

This process stops since we have

 (1)

and since the Euclidean size of an element has value in . Clearly, there exitst such that writes

where are null or have degree 0 w.r.t. , by the first part of this proof. Moreover holds.

Remark 1   Proposition 1 applies in the ring of integers and the ring of univariate polynomials over a field . It extends also for the ring of univariate polynomials over an Euclidean domain with a regular Euclidean size and a prime element . Indeed, one can apply Proposition 1 to each coefficient of a polynomial .

As we shall see now, it extends to a ring of univariate polynomials over a commutative ring with identity element and to the element where is an element of .

Proposition 2   Let be a commutative ring with identity element. Let be a polynomial of degree and let be an element. We define . There exists a unique sequence such that we have

 (2)

The above expression is called the Taylor expansion of at ,

Proof. By induction on . If , the result is clear. Otherwise let and be the quotient and the remainder in the division of by . We have

Since the conclusion (existence and unicity) follows by the induction hypothesis.

Remark 2   We can characterize the Taylor expansion of at by means of the notion of a formal derivative.

Definition 3   Let be a commutative ring with identity element. For

we define the formal derivative of by

 (3)

Remark 3   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 is a finite ring, then this would not make clear sense. However we retrieve the usual properties of derivatives.

Proposition 3   Let be a commutative ring with identity element. Let and let . Then the following properties hold
1. ,
2. ,
3. .

Proof. See Lemma 9.19 in [GG99].

Proposition 4   Let be a commutative ring with identity element. Let and let . There exists a polynomial such that we have

 (4)

Proof. Follows Proposition 2 we have

 (5)

where . The division of by shows that . Similarly, from (Equation 3), we have . Plugging and in (Equation 5) leads to

 (6)

for a polynomial .

Remark 4   Proposition 2 admits several generalizations. First one can use a monic polynomial of degree . In this case the coefficients are polynomials of degree less than . Another generalization, given by Proposition 5, is for multivariate polynomials. To understand this generalization, it is important to make the following three observations.
• First, in Proposition 4, one can consider as a new indeterminate, and then the result holds for a polynomial .
• 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 in Relation (4) lies in the ideal .

Proposition 5   Let be a commutative ring with identity element. We consider the ring of multivariate polynomials . We define and . For every polynomial there exists a polynomial lying in the ideal such that

 (7)

Remark 5   Using the vocabulary of numerical analysis, Propositions 4 and 5 provides a Taylor expansion of of order 2. This leads to the following definition.

Definition 4   Let be a commutative ring with identity element and let be an ideal of . Let be elements and be a positive integer. We say that is an -adic approximation of at order if we have

 (8)

Remark 6   We conclude by two useful properties of ideal-adic approximations.

Proposition 6   Let be an Euclidean domain with a regular Euclidean size . Let be a prime element. Let be an element and let be a -adic expansion of w.r.t. . For every positive integer we define

 (9)

Then is a -adic approximation of at order , that is

 (10)

Proof. Indeed, we have

Proposition 7   Let be a commutative ring with identity element and let be an ideal of . Let be elements, let be a positive integer and let be a polynomial. Then we have

 (11)

That is, if is an -adic approximation of at order , then is an -adic approximation of at order .

Proof. This is simply because of the ring-homomorphism between and .

Marc Moreno Maza
2008-01-07