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 1   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 2   The Euclidean size ${\delta}$ of an Euclidean domain $R$ is said regular if for every $a,b \in R$ with ${\delta}(b) \neq 0$ there exists a couple $(q,r) \in E \times E$ such that

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

Example 1   The absolute value in the ring ${\mathbb{Z}}$ of integers and the degree in the ring $k[x]$ of univariate polynomials over a field $k$ are regular Euclidean sizes.

Proposition 1   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_0, a_1, \ldots, a_d \in E$ such that

1. $a = a_d p^d + \cdots + a_1 p + a_0$ ,
2. $a_d \neq 0$ ,
3. for every $i = 0 \cdots d$ we have ${\deg}(a_i,p) = 0$ .

The sequence $(a_0, a_1, \ldots, a_d)$ is called a $p$ -adic expansion of $a$ w.r.t. $p$ .

Proof. Let $(q_0,a_0)$ be a couple quotient-remainder given as in Definition 2 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 \neq 0$ holds. This implies ${\delta}(p) > {\delta}(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 ${\delta}(a_0) \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_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 ${\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_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 $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$ . Then, two cases arise:

• Either both $q_0 \neq 0$ and $a_0 \neq 0$ hold, and this case we have ${\delta}(q_0) < {\delta}(a)$ ; then, we consider $(q_1, a_1)$ a couple quotient-remainder given as in Definition 2 when dividing $q_0$ w.r.t. $p$ .
• Or $a_0 = 0$ . Then, there exists a smallest integer $e_0 > 1$ such that the remainder in an division of $a$ w.r.t. $p^{e_0}$ is not zero. (This follows from the fact that $R$ is a Unique Factorization Domain and $p$ is a prime.) Let $(q_0,a_0)$ be a couple quotient-remainder in an division of $a$ w.r.t. $p^{e_0}$ with $a_0 \neq 0$ .
  • If $q_0 = 0$ , then we stop.
  • If $q_0 \neq 0$ , then ${\delta}(q_0) < {\delta}(a)$ ; then, we consider $(q_1, a_1)$ a couple quotient-remainder given as in Definition 2 when dividing $q_0$ w.r.t. $p$ .

In each case where we consider a couple quotient-remainder $(q_1, a_1)$ , we can repeat a similar discussion as we did for $(q_0,a_0)$ .

Continuing in this manner we obtain a finite sequence $a_0, a_1, \ldots, a_d \in R$ , a finite sequence $e_0, e_1, \ldots, e_d \in {\mbox{${\mathbb{N}}$}}$ and a finite sequence $q_0, q_1, \ldots, q_d \in R$ such that we have

$$\begin{array}{rclcrcl} a & = & q_0 p^{e_0} + a_0 & {\rm with}... ..._{\ell}} + a_{\ell} & {\rm with} & q_{\ell} & = & 0 \end{array}$$

This process stops since we have

$${\delta}(a) > {\delta}(q_0) > {\delta}(q_1) > {\delta}(q_2) > \cdots > {\delta}(q_{{\ell}-1})$$ (1)

and since the Euclidean size of an element has value in ${\mbox{${\mathbb{N}}$}} \ {\cup} \ \{-{\infty}\}$ . Clearly, there exitst $d \in {\mbox{${\mathbb{N}}$}}$ such that $a$ writes

$$a = a_d p^d + \cdots + a_1 p + a_0.$$

where $a_d, \ldots, a_1, a_0$ are null or have degree 0 w.r.t. $p$ , by the first part of this proof. Moreover $a_d \neq 0$ holds. $\qedsymbol$

Remark 1   Proposition 1 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 1 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 2   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, \ldots, {\phi}_n \in R$ such that we have

$${\phi} = {\phi}_0 + {\phi}_1 p + \cdots + {\phi}_n p^n.$$ (2)

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} = q p + r \ \ \ \ {\rm and} \ \ \ \ r \in R.$$

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

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

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

$${\phi} = {\phi}_0 + {\phi}_1 y + {\phi}_2 y^2 + \cdots + {\phi}_n y^n$$

we define the formal derivative of ${\phi}$ by

$${\phi}' = {\phi}_1 + 2 {\phi}_2 y + \cdots + n {\phi}_n y^{n-1}.$$ (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 $R$ is a finite ring, then this would not make clear sense. However we retrieve the usual properties of derivatives.

Proposition 3   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}' + b {\phi}'$ ,
2. $({\phi} {\psi})' = {\phi}' {\psi} + {\phi} {\psi}'$ ,
3. $({\phi}({\psi}))' = {\psi}' {\phi}'({\psi})$ .

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

Proposition 4   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}(y) = {\phi}(g) + {\phi}'(g) (y - g) + {\psi}(y) (y - g)^2.$$ (4)

Proof. Follows Proposition 2 we have

$${\phi} = {\phi}_0 + {\phi}_1 p + \cdots + {\phi}_n p^n$$ (5)

where $p = y - g$ . The division of ${\phi}(y)$ by $p$ shows that ${\phi}(g) = {\phi}_0$ . Similarly, from (Equation 3), we have ${\phi}'(g) = {\phi}_1$ . Plugging ${\phi}(g) = {\phi}_0$ and ${\phi}'(g) = {\phi}_1$ in (Equation 5) leads to

$${\phi} = {\phi}(g) + {\phi}'(g) (y-g) + {\psi}(y) (y-g)^2$$ (6)

for a polynomial ${\psi}$ . $\qedsymbol$

Remark 4   Proposition 2 admits several generalizations. First one can use a monic polynomial $p$ of degree $d > 1$ . In this case the coefficients ${\phi}_0, {\phi}_1, \ldots, {\phi}_n$ are polynomials of degree less than $d$ . 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 $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)^2$ in Relation (4) lies in the ideal ${\langle y -g \rangle}^2$ .

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

$${\phi}(x_1 + y_1, \ldots, x_r + y_r) = {\phi}({\bf x}) + {\Sigma}_{j=1}^{j=r} \frac{{\partial}{\phi}}{{\partial} x_j}({\bf x}) y_j + {\psi}.$$ (7)

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

Definition 4   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

$$a \equiv b \mod{{\cal I}^k}.$$ (8)

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

Proposition 6   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_0, a_1, \ldots, 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_0 + a_1 p + \cdots a_{k-1} p^{k-1}$$ (9)

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

$$a^{(k)} \equiv a \mod{ p^k }.$$ (10)

Proof. Indeed, we have

$$a - a^{(k)} = a_k p^k + a_{k+1} p^{k+1} + \cdots + a_d p^d = (a_k + a_{k+1} p + \cdots + a_d p^{d - k}) p^k$$

$\qedsymbol$

Proposition 7   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

$$a \equiv b \mod{{\cal I}^k} \ \ \Rightarrow \ \ {\phi}(a) \equiv {\phi}(b) \mod{{\cal I}^k}$$ (11)

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$