r Î Q. Write
r = a/b where gcd
|| || be a norm on
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:
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:
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
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
Q then there are infinitely many choices; there
R and furthermore there are infinitely many primes
In many algorithms in computer algebra it is possible to use either
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)
C is chosen as some number greater than
1. So again: high
Û 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: