The p-adic number field as an ‘ultrametric completion’ of the rationals

I have repeatedly bumped up against p-adic numbers and p-adic analysis in my reading and have wanted to delve more deeply into them for ages. In this first (rather long) note about them I wanted to explore some of the details involved in the close analogy between

A). the way Cantor constructed the real number field as the completion of the rationals using Cauchy sequences with the usual Euclidean metric, and

B). the way the p-adic number field can be similarly constructed as the completion of the rationals, but using Cauchy sequences with a different metric (known as an ultrametric).

I have found that exploring this analogy in some detail has allowed me to get quite a good foothold on some of the key features of p-adic analysis.

1. A basic initial characterisation of p-adic numbers

A lot flows from the basic observation that given a prime number p and a rational number x = a/b, it is always possible to factor out the powers of p in x as in the equation

x = \frac{a}{b} = p^{n_0}\frac{a_1}{b_1}        with  p \nmid a_1b_1

The exponent n_0, known as the p-adic valuation in the literature, can be negative, zero or positive depending on how the prime p appears (or not) as a factor in the numerator and denominator of the rational number x = a/b.

Example: Suppose we specify the prime p = 7. Then we can factor out the powers of 7 in the rational numbers 56/12, 177553, and 3/686 as

\frac{56}{12} = 7^1 \times \frac{2}{3}

177553 = 7^0 \times 177553

\frac{3}{686} = 7^{-3} \times \frac{3}{2}

respectively. END

For each prime number p, we can write any positive rational number x = a/b in the power series form

x = \frac{a}{b} = \sum_{n \ge n_0} a_np^n

where n_0 is the p-adic valuation of x and the coefficients a_n come from the set of least positive residues of p. (These coefficients will always exhibit a repeating pattern in the power series of a rational number). This power series form is called the p-adic expansion of x. In the case b = 1, i.e., when x is a positive integer, the p-adic expansion is just the expansion of x in base p.

If the rational number x = a/b is negative rather than positive, its p-adic expansion can be obtained from the positive version above as

x = \frac{a}{b} = \sum_{n \ge n_0} b_np^n

where b_{n_0} = p - a_{n_0} and b_n = (p - 1) - a_n for n > n_0.

We can obtain the p-adic expansion for any rational number x = a/b by the following algorithm. Let the p-adic expansion we want to find be

x = \frac{a}{b} = a_{n_0}p^{n_0} + a_{n_1}p^{n_0+1} + a_{n_2}p^{n_0+2} + \cdots

= p^{n_0}(a_{n_0} + a_{n_1}p + a_{n_2}p^2 + a_{n_3}p^3 + \cdots)

= p^{n_0}\frac{a_1}{b_1}

where all fractions are always given in their lowest terms. We deduce that the p-adic expansion of a_1/b_1 is then

\frac{a_1}{b_1} = a_{n_0} + a_{n_1}p + a_{n_2}p^2 + a_{n_3}p^3 + \cdots

so, since the right hand side equals a_{n_0} mod p, we can compute a_{n_0} as

a_{n_0} \equiv a_1b_1^{-1}   (mod p)

Next, we see that

\frac{a_1}{b_1} - a_{n_0} = a_{n_1}p + a_{n_2}p^2 + a_{n_3}p^3 + \cdots

= p(a_{n_1} + a_{n_2}p + a_{n_3}p^2 + a_{n_4}p^3 + \cdots)

= p\frac{a_2}{b_2}

We deduce that the p-adic expansion of a_2/b_2 is then

\frac{a_2}{b_2} = a_{n_1} + a_{n_2}p + a_{n_3}p^2 + a_{n_4}p^3 + \cdots

so, since the right hand side equals a_{n_1} mod p, we can compute a_{n_1} as

a_{n_1} \equiv a_2b_2^{-1}   (mod p)

We continue this process until the repeating pattern in the coefficients is spotted.

Example: Suppose we specify the prime to be p = 5 and consider the rational number 2/15. The p-adic valuation of this rational number is -1 since we can write

\frac{2}{15} = 5^{-1} \cdot \frac{2}{3}

Therefore we expect the p-adic expansion for 2/15 to have p^{-1} in its first term. Following the steps of the algorithm we compute the first coefficient as

a_{n_0} \equiv 2 \times 3^{-1} \equiv 12 \times 3^{-1} \equiv 4      (mod 5)

Then we have

\frac{2}{3} - 4 = \frac{-10}{3} = 5 \cdot \frac{-2}{3}

so we can compute the second coefficient as

a_{n_1} \equiv -2 \times 3^{-1} \equiv 3 \times 3^{-1} \equiv 1      (mod 5)

Then we have

\frac{-2}{3} - 1 = \frac{-5}{3} = 5 \cdot \frac{-1}{3}

so we can compute the third coefficient as

a_{n_2} \equiv -1 \times 3^{-1} \equiv 9 \times 3^{-1} \equiv 3      (mod 5)

Then we have

\frac{-1}{3} - 3 = \frac{-10}{3} = 5 \cdot \frac{-2}{3}

so we see immediately that the fourth coefficient will be the same as the second, and the pattern will repeat from this point onwards. Therefore we have obtained the p-adic expansion of 2/15 as

\frac{2}{15} = 4p^{-1} + 1 + 3p + p^2 + 3p^3 + p^4 + 3p^5 + \cdots  END

It can be shown that the set of all p-adic expansions is an algebraic field. This is called the field of p-adic numbers and is usually denoted by \mathbb{Q}_p in the literature. In the rest of this note I will explore some aspects of the construction of the field \mathbb{Q}_p by analogy with the way Cantor constructed the field of real numbers from the field of rationals. The next section reviews Cantor’s construction of the reals.

2. Cantor’s construction of the real number field

In Cantor’s construction of the real numbers from the rationals, we regard the latter as a metric space (\mathbb{Q}, d) where the metric d is defined in terms of the ordinary Euclidean absolute value function:

d(x, y) = \mid x - y \mid              (1)

The central problem in constructing the real number field \mathbb{R} from the field of rationals \mathbb{Q} is that of defining irrational numbers only in terms of rationals. This can be done in alternative ways, e.g., using Dedekind cuts, but Cantor’s approach achieves it using the concept of a Cauchy sequence. A Cauchy sequence in a metric space is a sequence of points which become arbitrarily ‘close’ to each other with respect to the metric, as we move further and further out in the sequence. More formally, in the context of the metric space (\mathbb{Q}, d), a sequence \{q_n\} of rationals is a Cauchy sequence if for each \epsilon > 0 (where \epsilon \in \mathbb{Q}) there is an N \in \mathbb{N} such that

d(q_i, q_j) = \mid q_i - q_j \mid < \epsilon    for all i, j \ge N

Example: So, for example, if I set \epsilon = 10^{-6}, then I can be sure that there is a certain point in the Cauchy sequence \{q_n\} beyond which all the terms of the sequence will always be within a millionth of each other in absolute value. If instead I set \epsilon = 10^{-9} I might have to go further out in the sequence, but I can still be sure that beyond a certain point all the terms of the sequence from then on will be within a billionth of each other in absolute value. And so on. END

Cantor’s approach to constructing the reals is based on the idea that any irrational number can be regarded as the limit of Cauchy sequences of rationals, so we can actually define the irrationals as sets of Cauchy sequences of rationals.

Example: To illustrate, consider the irrational number \sqrt{2}. Define three sequences of rationals \{a_n\}, \{b_n\}, \{x_n\} as follows:

a_0 = 1      b_0 = 2

x_n = \frac{1}{2}(a_n + b_n)   for all  n \ge 1

a_{n+1} = x_n  if x_n^2 < 2, otherwise a_{n+1} = a_n

b_{n+1} = b_n  if x_n^2 < 2, otherwise b_{n+1} = x_n

For each n \ge 1, x_n lies between a_n and b_n, and at each iteration the closed interval [a_n, b_n] has length

b_n - a_n = (\frac{1}{2})^n

(To see this, note that from the definitions of the three sequences above we find that

b_{n+1} - a_{n+1} = \frac{1}{2}(b_n - a_n)

so we get the result from this by a simple induction). Also, each closed interval [a_n, b_n] contains \sqrt{2}. Therefore the closed interval [a_n, b_n]  is increasingly ‘closing in’ around \sqrt{2}, i.e., we have

[a_{n+1}, b_{n+1}] \subseteq [a_n, b_n]

So for each of the sequences \{a_n\}, \{b_n\}, \{x_n\} of rationals, the terms of the sequence are getting closer and closer to each other, and closer to \sqrt{2}. Cantor’s idea was basically to define an irrational such as \sqrt{2} to be the set containing all Cauchy sequences like \{a_n\}, \{b_n\}, and \{x_n\}  which converge to that irrational. END

Formally, the process involves defining equivalence classes of Cauchy sequences in the metric space (\mathbb{Q}, d), so that two Cauchy sequences \{a_n\} and \{b_n\} belong to the same equivalence class, denoted \{a_n\} \thicksim \{b_n\}, if for each \epsilon > 0 (where \epsilon \in \mathbb{Q}) there is an N \in \mathbb{N} such that

d(a_n, b_n) = \mid a_n - b_n \mid < \epsilon    for all n \ge N

It is straightforward to show that \thicksim is an equivalence relation in the sense that it is reflexive (i.e. \{a_n\} \thicksim \{a_n\} for all Cauchy sequences \{a_n\}), symmetric (i.e., if \{a_n\} \thicksim \{b_n\} then \{b_n\} \thicksim \{a_n\} for all Cauchy sequences \{a_n\} and \{b_n\}), and transitive (i.e., if \{a_n\} \thicksim \{b_n\} and \{b_n\} \thicksim \{c_n\} then \{a_n\} \thicksim \{c_n\} for all Cauchy sequences \{a_n\}\{b_n\} and \{c_n\}).

Cantor defined a real number to be any equivalence class arising from \thicksim, i.e., any set of the form

\big\{\{b_n\}: \{b_n\} \thicksim \{a_n\}\big\}

where \{a_n\} is a Cauchy sequence in the metric space (\mathbb{Q}, d). Rational numbers are, of course, subsumed in this since any rational number q belongs to the (constant) Cauchy sequence \{q_n\} defined by q_n = q for all n.

It is now possible to define all the standard relations and arithmetic operations on the real numbers constructed in this way, and it can also be shown that the set of reals constructed in this way is isomorphic to the set of reals defined by alternative means, such as Dedekind cuts.

The set of reals constructed in this way can be regarded as the completion of the set of rationals in the sense that it is obtained by adding to the set of rationals all the limits of all possible Cauchy sequences in (\mathbb{Q}, d) which are irrational. In general, a metric space is said to be complete if every Cauchy sequence in that metric space converges to a point within that metric space. Clearly, therefore, the metric space (\mathbb{Q}, d) is not complete since, for example, we found Cauchy sequences of rationals above which converge to \sqrt{2} \notin \mathbb{Q}. However, it is a basic result of elementary real analysis that the metric space (\mathbb{R}, d) is complete. It is also a basic result that the completion of a field gives another field, so since \mathbb{Q} is a field it must also be the case that \mathbb{R} is a field.

3. Archimedian vs. non-archimedian absolute values and ultrametric spaces

In constructing the p-adic number field it becomes important to distinguish between two types of absolute value function on a field, namely archimedian and non-archimedian absolute values. All absolute values on a field by definition have the properties that they assign the value 0 only to the field element 0, they assign the positive value \mid x \mid to each non-zero field element x, and they satisfy \mid xy \mid = \mid x \mid \mid y \mid and the usual triangle inequality

\mid x + y \mid \le \mid x \mid + \mid y \mid

The usual Euclidean absolute value function used in (1) above on \mathbb{Q}, of course, satisfies these conditions, and is called archimedian because it has the property that there is no limit to the size of the absolute values that can be assigned to integers. We can write this as

sup\{\mid n \mid : n \in \mathbb{Z}\} = +\infty

Non-archimedian absolute values do not have this property. In addition to the basic conditions that all absolute values must satisfy, non-archimedian absolute values must also satisfy the additional condition

\mid x + y \mid \le max\{\mid x \mid, \mid y \mid \}      (2)

which is known as the ultrametric triangle inequality. It is obviously the case that the archimedian absolute value function used in (1) does not satisfy (2), e.g.,

\mid 1 + 1 \mid \nleq max\{\mid 1 \mid, \mid 1 \mid \}

In fact it follows from (2) that non-archimedian absolute values of integers can never exceed 1, because if (2) is to hold for the absolute value function then we can write for any integer n:

\mid n + 1 \mid \leq max \{\mid n \mid, 1\}

and so by induction we must have

\mid n^2 \mid \leq max \{ \mid n \mid, 1 \}

Then if \mid n \mid \geq 1 we would have \mid n^2 \mid \leq \mid n \mid which implies \mid n \mid \leq 1, and so \mid n \mid = 1 in this case. It is not possible for \mid n \mid to exceed 1, so in the case of non-archimedian absolute values we have

sup\{\mid n \mid : n \in \mathbb{Z}\} = 1

Any absolute value function which does not satisfy (2) is called archimedian, and these are the only two possible types of absolute values. To see that these are the only two possible types, suppose we have an absolute value function such that

sup\{\mid n \mid : n \in \mathbb{Z}\} = C

where C > 1. Then there must exist an integer m whose absolute value exceeds 1, and so \mid m^k \mid = \mid m \mid^k gets arbitrarily large as k grows, so C cannot be finite. The absolute value function must be archimedian in this case. Otherwise, we must have C \leq 1, but since for all absolute values it must be the case that \mid 1 \mid = 1, it must be the case that C = 1 if C is finite. Thus we must have a non-archimedian absolute value in this case and there are no other possibilities.

The trick in constructing the p-adic number field from the rationals is to use a certain non-archimedian absolute value function satisfying (2) to define the metric over \mathbb{Q}, rather than the usual archimedian absolute value function in (1). In this regard we have the following:

Theorem 1. Define a metric on a field by d(x, y) = \mid x - y \mid. Then the absolute value function in this definition is non-archimedian if and only if for all field elements x, y, z we have

d(x, y) \le max\{d(x, z), d(z, y)\}

Proof: Suppose first that the absolute value function is non-archimedian. Applying it to the equation

(x - y) = (x - z) + (z - y)

immediately gives

d(x, y) \le max\{d(x, z), d(z, y)\}

Conversely, suppose the given metric inequality holds. Then setting y = -w and z = 0 in the metric inequality we get

d(x, -w) \le max\{d(x, 0), d(0, -w)\}

which is equivalent to

\mid x + w \mid \leq max \{\mid x \mid, \mid w \mid \}

thus proving that the absolute value function is non-archimedian. QED

A metric for which the inequality in Theorem 1 is true is called an ultrametric, and a space endowed with an ultrametric is called an ultrametric space. Such spaces have curious properties which have been studied extensively. In some ways, however, using a non-archimedian absolute value makes analysis much easier than in the usual archimedian case. In this regard we have the following result pertaining to Cauchy sequences with respect to a non-archimedian absolute value function, which is NOT true for archimedian absolute values:

Theorem 2. A sequence \{x_n\} of rational numbers is a Cauchy sequence with respect to a non-archimedian absolute value if and only if we have

\lim_{n \rightarrow \infty} \mid x_{n+1} - x_n \mid = 0

Proof: Letting m = n + r > n, we have

\mid x_m - x_n \mid = \mid x_{n+r} - x_{n+r-1} + x_{n+r-1} - x_{n+r-2} + \cdots + x_{n+1} - x_n \mid

\leq max\{\mid x_{n+r} - x_{n+r-1} \mid, \mid x_{n+r-1} - x_{n+r-2} \mid, \dots, \mid x_{n+1} - x_n \mid \}

= \mid x_{n+1} - x_n \mid

because the absolute value is non-archimedian. We then have that if \{x_n\} is Cauchy then the terms get arbitrarily closer as n \rightarrow \infty so we must have \lim_{n \rightarrow \infty} \mid x_{n+1} - x_n \mid = 0. Conversely, if \lim_{n \rightarrow \infty} \mid x_{n+1} - x_n \mid = 0 is true, then we must also have \lim_{n \rightarrow \infty} \mid x_m - x_n \mid = 0 for any m > n, so the conditions of a Cauchy sequence are satisfied. QED

It is important to note that Theorem 2 is false for archimedian absolute values. The classic counterexample involves the partial sums of the harmonic series (which is divergent in terms of Euclidean absolute values). Consider the following three partial sums in particular:

x_n = 1 + \frac{1}{2} + \cdots \frac{1}{n}

x_{n+1} = 1 + \frac{1}{2} + \cdots \frac{1}{n} + \frac{1}{n+1}

x_{2n} = 1 + \frac{1}{2} + \cdots \frac{1}{n} + \frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n}

Then we have

\lim_{n \rightarrow \infty} \mid x_{n+1} - x_n \mid = \lim_{n \rightarrow \infty} \frac{1}{n+1} = 0

so the condition of Theorem 2 is satisfied. However,

\mid x_{2n} - x_n \mid = \frac{1}{n+1} + \frac{1}{n+2} + \cdots + \frac{1}{2n}

\geq \frac{1}{2n} + \frac{1}{2n} + \cdots + \frac{1}{2n}

= \frac{n}{2n} = \frac{1}{2}

Therefore it is not true in this case that \lim_{n \rightarrow \infty} \mid x_m - x_n \mid = 0 for any m > n, so the conditions of a Cauchy sequence are not satisfied here. It’s only in the context of non-archimedian absolute values that this works.

4. Constructing the p-adic number field as the completion of the rationals

To obtain the p-adic number field as the completion of the field of rationals in a way analogous to how Cantor obtained the reals from the rationals, we use an ultrametric based on a non-archimedian absolute value known as the p-adic absolute value.

For each prime p there is an associated p-adic absolute value on \mathbb{Q} obtained by factoring out the powers of p in any given rational q \in \mathbb{Q} to get

q = p^{n_0}\frac{a}{b}         p \nmid ab

With this factorisation in hand, the p-adic absolute value of q is then defined as

\mid q \mid_p = p^{-n_0}

if q \neq 0, and we set \mid 0 \mid_p = 0. (As mentioned earlier, the number n_0 is called the p-adic valuation of q).

It is straightforward to verify that this is a non-archimedian absolute value on \mathbb{Q}. It has some surprising features. For example, unlike the usual Euclidean absolute value function on \mathbb{Q} which can take any non-negative value on a continuum, the p-adic absolute value function can only take values in the discrete set

\{p^{-n_0} : n_0 \in \mathbb{Z}\} \cup \{0\}

Examples: In the case of the 7-adic absolute value we have

\mid 35 \mid_7 = \mid 7 \times 5 \mid_7 = \frac{1}{7}

\mid \frac{56}{12} \mid_7 = \mid 7 \times \frac{2}{3} \mid_7 = \frac{1}{7}

\mid 177553 \mid_7 = \mid 7^0 \times 177553 \mid_7 = 1

\mid \frac{3}{686} \mid_7 = \mid 7^{-3} \times \frac{3}{2} \mid_7 = 7^3 = 343

Note that the 7-adic absolute value of 3/686 is large, while that of 35 is small. END

Now consider the metric space (\mathbb{Q}, d_p) where d_p is defined as

d_p(x, y) = \mid x - y \mid_p

By virtue of Theorem 1, d_p is an ultrametric and (\mathbb{Q}, d_p) is an ultrametric space. Since the p-adic absolute value function has some counterintuitive features, it is not surprising that d_p also gives some counterintuitive results. For example, the numbers 1627 and 2 are much ‘closer’ to each other with regard to this ultrametric than the numbers 3 and 2, because

d_p(1627, 2) = \mid 1627 - 2 \mid_p = \mid 1625 \mid_p = \mid 5^3 \times 13\mid_p = \frac{1}{125}

whereas

d_p(3, 2) = \mid 3 - 2 \mid_p = \mid 1 \mid_p = 1

In addition, we can use it to show that the sequence \{x_n\} where

x_n = 1 + p + p^2 + p^3 + \cdots + p^n

is Cauchy with respect to d_p, whereas it is violently non-Cauchy with respect to the usual Euclidean absolute value. We have

\lim_{n \rightarrow \infty} \mid x_{n+1} - x_n \mid_p = \lim_{n \rightarrow \infty} \mid p^{n+1}\mid_p = \lim_{n \rightarrow \infty}p^{-(n+1)} = 0

It follows from Theorem 2 in the previous section that the sequence \{x_n\} is Cauchy with respect to the p-adic absolute value. In fact, the infinite series

x_n = 1 + p + p^2 + p^3 + \cdots

has the sum \frac{1}{1-p} in the ultrametric space (\mathbb{Q}, d_p) (this formula can be derived in the usual way for geometric series) but its sum is undefined in (\mathbb{Q}, d).

The following Theorem proves that the ultrametic space (\mathbb{Q}, d_p) is not complete in a way which is analogous to how (\mathbb{Q}, d) is not complete.

Theorem 3. The field \mathbb{Q} of rational numbers is not complete with respect to the p-adic absolute value.

Proof: To prove this, we will create a Cauchy sequence with respect to the p-adic absolute value function whose limit does not belong to \mathbb{Q}.

Let 1 < a \leq p-1 be an integer. Recall that a property of the Euler totient function is that for any prime p and any integer n \geq 1 we have

\phi(p^{n+1}) = p^n(p - 1)

Also recall the Euler-Fermat Theorem which says that if gcd(a, m) = 1 then

a^{\phi(m)} \equiv 1  (mod m)

With these in hand, consider the sequence \{x_n\} = \{a^{p^n}\}. Then since we have gcd(a, p^{n+1}) = 1, the Euler-Fermat Theorem tells us that

a^{p^n(p-1)} \equiv 1  (mod p^{n+1})

Therefore

x_{n+1} - x_n = a^{p^{n+1}} - a^{p^n} = a^{p^n}(a^{p^n(p-1)} - 1)

must be divisible by p^n, so we have

\mid x_{n+1} - x_n \mid_p \leq p^{-n}

and so the sequence \{x_n\} = \{a^{p^n}\} is Cauchy with respect to the p-adic absolute value, by virtue of Theorem 2. If we call the limit of this sequence

x = \lim_{n \rightarrow \infty} x_n

we can write the following:

\lim_{n \rightarrow \infty} x_{n+1} = \lim_{n \rightarrow \infty} x_n

\lim_{n \rightarrow \infty} a^{p^{n+1}} = \lim_{n \rightarrow \infty} a^{p^n}

\lim_{n \rightarrow \infty} (a^{p^n})^p = \lim_{n \rightarrow \infty} a^{p^n}

(\lim_{n \rightarrow \infty} a^{p^n})^p = \lim_{n \rightarrow \infty} a^{p^n}

x^p = x

x^{p-1} = 1

Therefore since a \neq 1, the limit of the sequence must be a nontrivial (p-1)-th root of unity, so it cannot belong to \mathbb{Q}. This proves that the ultrametric space (\mathbb{Q}, d_p) is not complete. QED

Although \mathbb{Q} is not complete with regard to the p-adic absolute value, we can construct the p-adic completion \mathbb{Q}_p  in a manner analogous to Cantor’s construction of \mathbb{R} as a completion of \mathbb{Q}. Investigating the fine details of this and the properties of \mathbb{Q}_p then lead one into the rich literature on p-adic analysis, which I will explore in future notes.