P-adic Expansions and Approximations

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 $\in$ R be a prime element. Let a $\in$ 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 $\in$ $\mbox{${\mathbb N}$}$ 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 $\ell$ there exists a positive integer k > $\ell$ 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) = + $\infty$, otherwise we say that a has finite degree w.r.t. p and we write deg(a, p) < + $\infty$. Assume furthermore that deg(a, p) < + $\infty$ holds. The largest positive integer k $\in$ $\mbox{${\mathbb N}$}$ 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 $\delta$ of an Euclidean domain R is said regular if for every a, b $\in$ R with b $\neq$ 0 there exists a couple (q, r) $\in$ E×E such that

1. a = bq + r,
2. r $\neq$ 0  $\Rightarrow$   $\delta$(r) < $\delta$(b),
3. q $\neq$ 0  $\Rightarrow$   $\delta$(q) < $\delta$(a)  and  $\delta$(b) $\leq$ $\delta$(a).

Proposition 8   Let R be an Euclidean domain with a regular Euclidean size $\delta$. Let p be a prime element. Then for every non-zero a $\in$ E there exists an integer d $\in$ N and elements a₀, a₁,..., a_d $\in$ E such that

1. a = a_dp^d + ^... + a₁p + a₀,
2. a_d $\neq$ 0,
3. for every i = 0 ^... d we have deg(a_i, p) = 0.

The sequence (a₀, a₁,..., a_d) is called a p-adic expansion of a w.r.t. p.

Proof. Let (q₀, a₀) be a couple quotient-remainder given as in Definition 7 when dividing a w.r.t. p.

First we prove that a₀ must have degree 0 w.r.t. p. This is obvious if a₀ = 0. So let us assume that a₀ $\neq$ 0 holds. This implies $\delta$(p) > $\delta$(a₀). If a₀ would have positive degree k w.r.t. p, then, by the properties of a regular Euclidean size, we would have $\delta$(a₀) $\geq$ $\delta$(p^k). Since $\delta$(p^k) $\geq$ $\delta$(p) holds (by definition of an Euclidean domain) we would have a contradiction with $\delta$(p) > $\delta$(a₀). Therefore in any case we have deg(a₀, 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 $\delta$(a) < $\delta$(p). Hence every quotient of a w.r.t. p is null. (Otherwise we would have $\delta$(p) $\leq$ $\delta$(a) by the properties of a regular Euclidean size.) Since a = a₀ and since a₀ has degree 0 w.r.t. p, the element a has degree 0 w.r.t. p and (a₀) is a p-adic 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₀ $\neq$ 0 and $\delta$(q₀) < $\delta$(a) hold. Then let (q₁, a₁) be a couple quotient-remainder given as in Definition 7 when dividing q₀ w.r.t. p. If q₁ $\neq$ 0 then we have $\delta$(q₁) < $\delta$(q₀) and let (q₂, a₂) be a couple quotient-remainder given as in Definition 7 when dividing q₁ w.r.t. p. Continuing in this manner we obtain a finite sequence a₀, a₁,..., a_d $\in$ R and a finite sequence q₀, q₁,..., q_d $\in$ R such that we have

a	=	q0p + a0	with	q0	$$\neq$$	0
q0	=	q1p + a1	with	q1	$$\neq$$	0
q1	=	q2p + a2	with	q2	$$\neq$$	0
$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$	$$\vdots$$
qd2	=	qd-1p + ad-1	with	qd-1	$$\neq$$	0
qd-1	=	qdp + ad	with	qd	=	0

This process stops since we have

$$\delta \delta \delta \delta \delta$$ (83)

and since the Euclidean size of an element has value in $\mbox{${\mathbb N}$}$  $\cup$  { - $\infty$}. Clearly we have

Moreover a_d = q_d-1 $\neq$ 0 holds. In addition, for every i = 0 ^... d we have deg(a_i, p) = 0 by the first part of this proof. $\qedsymbol$

Remark 15   Proposition 8 applies in the ring $\mathbb {Z}$ of integers and the ring $\bf k$[x] of univariate polynomials over a field $\bf k$. It extends also for the ring R[y] of univariate polynomials over an Euclidean domain R with a regular Euclidean size $\delta$ and a prime element p $\in$ R. Indeed, one can apply Proposition 8 to each coefficient of a polynomial $\phi$ $\in$ R[y].

As we shall see now, it extends to a ring R[y] of univariate polynomials over a commutative ring with identity element and to the element p = y - g where g is an element of R.

Proposition 9   Let R be a commutative ring with identity element. Let $\phi$ $\in$ R[y] be a polynomial of degree n and let g $\in$ R be an element. We define p = y - g. There exists a unique sequence $\phi_{{0}}^{{}}$,$\phi_{{1}}^{{}}$,...,$\phi_{{n}}^{{}}$ $\in$ R such that we have

$$\phi \phi_{{0}}^{{}} \phi_{{1}}^{{}} \phi_{{n}}^{{}}$$ (84)

The above expression is called the Taylor expansion of $\phi$ 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 $\phi$ by p. We have

$$\phi \in$$

Since r = $\phi$(g) the conclusion (existence and unicity) follows by the induction hypothesis. $\qedsymbol$

Remark 16   We can characterize the Taylor expansion of $\phi$ at g by means of the notion of a formal derivative.

Definition 8   Let R be a commutative ring with identity element. For

$$\phi \phi_{{0}}^{{}} \phi_{{1}}^{{}} \phi_{{2}}^{{}} \phi_{{n}}^{{}}$$

we define the formal derivative of $\phi$ by

$$\phi \prime \phi_{{1}}^{{}} \phi_{{2}}^{{}} \phi_{{n}}^{{}}$$ (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.

Proposition 10   Let R be a commutative ring with identity element. Let $\phi$,$\psi$ $\in$ R[y] and let a, b $\in$ R. Then the following properties hold

1. (a$\phi$ + b$\psi$)' = a$\phi$^$\prime$ + b$\phi$^$\prime$,
2. ($\phi$$\psi$)' = $\phi$^$\prime$$\psi$ + $\phi$$\psi$^$\prime$,
3. ($\phi$($\psi$))' = $\psi$^$\prime$$\phi$^$\prime$($\psi$).

Proof. See Lemma 9.19 in [vzGG99]. $\qedsymbol$

Proposition 11   Let R be a commutative ring with identity element. Let $\phi$ $\in$ R[y] and let g $\in$ R. There exists a polynomial $\psi$ $\in$ R[y] such that we have

$$\phi \phi \phi \prime \psi$$ (86)

Proof. Follows easily from Proposition 9. $\qedsymbol$

Remark 18   Proposition 9 admits several generalizations. First one can use a monic polynomial p of degree d > 1. In this case the coefficients $\phi_{{0}}^{{}}$,$\phi_{{1}}^{{}}$,...,$\phi_{{n}}^{{}}$ 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 $\phi$ $\in$ 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 $\psi$(y - g)² in Relation (86) lies in the ideal $\langle$y-g$\rangle^{{2}}_{{}}$.

Proposition 12   Let R be a commutative ring with identity element. We consider the ring of multivariate polynomials P = R[x₁,..., x_r][y₁,..., y_r]. We define $\bf x$ = (x₁,..., x_r) and $\bf y$ = (y₁,..., y_r). For every polynomial $\phi$ $\in$ R[$\bf x$] there exists a polynomial $\psi$ $\in$ P lying in the ideal $\langle$y₁,..., y_r$\rangle^{{2}}_{{}}$ such that

$$\phi \phi \bf x \Sigma_{{{j=1}}}^{{{j=r}}} {\frac{{{\partial}{\phi}}}{{{\partial} x_j}}} \bf x \psi$$ (87)

Remark 19   Using the vocabulary of numerical analysis, Propositions 11 and 12 provides a Taylor expansion of $\phi$ of order 2. This leads to the following definition.

Definition 9   Let R be a commutative ring with identity element and let $\cal {I}$ be an ideal of R. Let a, b $\in$ R be elements and k be a positive integer. We say that a is an $\cal {I}$-adic approximation of b at order k if we have

$$\equiv \cal {I}$$ (88)

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

Proposition 13   Let R be an Euclidean domain with a regular Euclidean size $\delta$. Let p $\in$ R be a prime element. Let a $\in$ R be an element and let (a₀, a₁,..., a_d) be a p-adic expansion of a w.r.t. p. For every positive integer k $\leq$ d + 1 we define

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

Then a^(k) is a p-adic approximation of a at order k, that is

$$\equiv$$ (90)

Proof. Indeed, we have

$\qedsymbol$

Proposition 14   Let R be a commutative ring with identity element and let $\cal {I}$ be an ideal of R. Let a, b $\in$ R be elements, let k be a positive integer and let $\phi$ $\in$ R[y] be a polynomial. Then we have

$$\equiv \cal {I} \Rightarrow \phi \equiv \phi \cal {I}$$ (91)

That is, if a is an $\cal {I}$-adic approximation of b at order k, then $\phi$(a) is an $\cal {I}$-adic approximation of $\phi$(b) at order k.

Proof. This is simply because of the ring-homomorphism between R and R/$\cal {I}$. $\qedsymbol$