The completion of a field with respect to a norm.

Let r Î Q. Write r = a/b where gcd (a,b)=1. Let ||   || be a norm on Q.
That means that ||   || is a function:

||   ||Q ®Q ³ 0

that satisfies certain properties:

|| a+b || £ ||a|| + ||b||  for all a,b    and   || a || = 0 Û a = 0.

This gives rise to a distance function

d(a,b) = ||a - b||

that satisfies the triangle inequality:

d(a,c) £ d(a,b) + d(b,c)

We use a norm to decide which elements of Q are thought of as small, i.e. close to 0. If two norms give rise to the same notion of small-ness then we will call them equivalent. So two norms ||   ||1 and ||   ||2 are equivalent when:

 "e > 0 \$d > 0 "r Î Q ( ||r||1 < d Þ ||r||2 < e  and    ||r||2 < d Þ ||r||1 < e )
So for example if || r ||¢ = 17|| r || + || r ||2 for all r then the norms  ||   || and ||   ||¢ are equivalent, that is, r is very small in the ||   ||-norm if and only if it is very small in the ||   ||¢-norm.

The most familiar norm is the absolute value norm which we shall denote as ||   ||¥  (the reason for using a subscript in this notation is so we can distinguish it from other norms). When r=a/b is not zero, then r is very small in the in the absolute value norm if and only if r=0 or b has a lot more digits than a.

When a is a nonzero integer and p is a prime number, define the p-adic valuation as follows.

vp(a) =  largest  n  for  which a º 0  mod pn

If a=0 then vp(a) is defined to be ¥. If r = a/b Î Q then define

vp(r) = vp(a) - vp(b).

Now define the p-adic valuation norm ||   ||p as follows. Take a number C > 1 and define:

|| r ||p = C-vp(r) for all r Î Q.

It is customary to take C=p in this defintion. Note that it does not matter which C you take, if you change C you get a different (but equivalent) norm as long as C > 1. Notice that: The valuation is high if and only if the norm is small.

Now || 0 ||p = 0  (this is why vp(0) was defined to be infinity). The p-adic valuation norm ||   ||p satisfies what is called the strong triangle inequality:

|| a+b ||p £ max( ||a||p, ||b||p )   in other words:   d(a,c) £ max( d(a,b), d(b,c) ).

This will turn out to be very convenient for estimating errors when we work with approximations, because in the p-adic valuation norm, if we have two roundoff errors e1,e2 then the sum of the two errors e1+e2 is in the ||   ||p-norm no greater than the maximum of the two errors.

Let  (ri)i=1,2,¼ with ri Î Q be an infinite sequence of rational numbers. If ||   || is a norm, then this sequence is called a  Cauchy sequence with respect to ||   || when

"e > 0 \$N > 0 "i,j > N   || ri - rj || < e

Two Cauchy sequences (r)i and (s)i are called ||   ||-equivalent when:

"e > 0 \$N > 0 "i > N   || ri - si || < e

We can now define the completion of Q with respect to a norm ||   || as follows:

Qc is the set of all Cauchy sequences modulo ||   ||-equivalence.

Note that any Cauchy sequence r1,r2,¼ Î Q has a limit in Qc, namely this limit is:

 lim i ®  ¥ ri   =   (r)i mod ||   ||-equivalence
The reason that we only defined the p-adic valuation norm ||  ||p when p is a prime is because if p is for example 10 then the completion is not a field. In fact, the following is true:

Theorem.

Denote R as the completion of Q with respect to the absolute value norm.
Denote Qp as the completion of Q with respect to the p-adic valuation norm.
If we consider any norms on Q, then the only completions of Q that are fields are the following:

R, Q2, Q3,Q5, Q7, Q11, ¼

In other words:  The absolute value norm, and the p-adic valuation norms  for all prime numbers p give a completion Qc of Q that is a field, and all such completions that are fields are obtained in this way.

If we took say p=10 then in the completion of the integers Z one would have zero-divisors (construct an element a that is divisible by arbitrarily high powers of 2, and construct b that is divisible by arbitrarily high powers of 5, and then ab is divisible by arbitrarily high powers of 10, so its valuation is infinity so ab must be 0, and hence a and b are zerodivisors). Because of this we will not use 10-adic numbers in the algorithms. Notice that if we want to work in a completion of Q then there are infinitely many choices; there is R and furthermore there are infinitely many primes p. In many algorithms in computer algebra it is possible to use either R or Qp but very often it is more convenient to use Qp . Notice that since there are infinitely many primes p we can always avoid finitely many primes that are inconvenient (like primes that appear for example in the denominator, if we avoid those primes then we never have to worry about negative valuations ||r||p which makes the algorithms much easier).

Completions of other fields.

We will look at another example.  Consider the ring Q[x]. Define the x-adic valuation as follows:

vx(f) = largest n such that f º 0 mod xn.

Again, if f=0 then the valuation is infinity. Now extend vx to the field Q(x) by setting vx(a/b) = vx(a) - vx(b). We can now define a norm ||   ||x in the same way as before:

|| f ||x = C-vx(f)

where C is chosen as some number greater than 1. So again: high valuation Û small norm.
Then we can define the completion of the ring Q[x] with respect to this norm. The result is denoted as:

Q[[x]] = the ring of formal power series in x.

The word formal refers to the fact that these power series do not need to be convergent. If we take the completion of the field Q(x) with respect to the norm ||   ||x then we get a field denoted as:

Q((x)) = the field of formal Laurent series in x.

This field is the field of fractions of Q[[x]]. We have:

 Q[[x] = { ¥å n=0 ri xi | ri Î Q }  and   Q((x)) = { ¥å n=N ri xi| ri Î Q, N Î Z }
So the elements of both are infinite power series. In Q[[x]] you don't allow negative exponents (so you don't have negative valuations). In Q((x)) you do allow negative exponents, but only finitely many. So the valuation may also be negative, but not infinite negative.