Exercise 10.2.9. (This requires some experience with probability.) Write

Yij = 1 if Si and Sj intersect [i = j], Yij = 0, otherwise. What is EYij ?

What is E 1¤j<i¤N Yij ? If q is small show that E 1¤j<i¤N Yij is large.

What does this tell you about the number of intersecting balls?

If the balls intersect, then, even if less than qn errors are made, in trans-

mission, the received message may belong to two or more balls. In such a

case we simply agree that our system has failed. How probable is such a

failure? Suppose we transmit y1 and receive z = y1 + e. Since the remaining

yj with 2 ¤ j ¤ N , have been chosen at random, independently of yj , the

probability that z lies in N Sj has nothing to do with how we de¬ned z

j=2

and is just

Vol( N Sj ) N

Vol Sj

j=2 j=2

¤ ≈ ·.

Vol X Vol X

Thus the probability of failure of the type discussed in this paragraph can

be kept at any speci¬ed level · whilst still allowing roughly · Vol S1 / Vol X

code words.

Exercise 10.2.10. How can you reconcile this last result with Exercise 10.2.9?

We have thus obtained the full Shannon™s theorem.

241

Please send corrections however trivial to twk@dpmms.cam.ac.uk

Theorem 10.2.11. (Shannon.) Consider our noisy channel. If p, the

probability of error in a single bit, is less than 1/2, then, choosing p < p <

1/2, we can transmit, with error rate as small as we please, so that informa-

tion is passed at a rate of 1 ’ H(p ) times that of our original channel.

Exercise 10.2.12. (For the knowledgeable only.) The statement ˜We have

thus obtained the full Shannon™s theorem™ is a bit optimistic since there are

quite a lot of loose ends to tie up. Tie them up.

In the 50 or so years since Shannon proved his theorem, no one has

produced non-random codes to match his random codes for long code words.

However, non-random methods are beginning to catch up. For our ¬rst

problem of sphere packing in Rn , the best known packings in high dimensions

are lattice (so very highly ordered) packings. The experts believe that this

re¬‚ects our ignorance rather than the truth.

10.3 Metric spaces

We discovered our proof of Shannon™s theorem (at least in the form of

Lemma 10.2.8) by drawing heavily on analogies with distance and volume in

Rn . Many proofs in analysis and elsewhere have been discovered by exploit-

ing analogies between the usual distance in Rn and ˜things that look more

or less like distance™.

Recalling that ˜once is a trick, twice is a method, thrice a theorem and

four times a theory™, we seek to codify this insight.

Our ¬rst try is to model the properties of Euclidean distance set out in

Lemma 4.1.4.

De¬nition 10.3.1. Let V be a real vector space and N : V ’ R a function.

We write x = N (x) and say that is a norm if the following conditions

hold.

(i) x ≥ 0 for all x ∈ V ,

(ii) If x = 0, then x = 0,

(iii) If » ∈ R and x ∈ V , then »x = |»| x .

(iv) (The triangle inequality) If x, y ∈ V , then x + y ¤ x + y .

·

Note that some mathematicians prefer to write instead of . The

˜·™ acts as a placeholder.

Exercise 10.3.2. Check that the usual Euclidean norm on Rm is indeed a

norm.

242 A COMPANION TO ANALYSIS

The appropriate de¬nition when V is a vector space over C, rather than

R, runs similarly.

De¬nition 10.3.3. Let V be a complex vector space and N : V ’ R a

function. We write x = N (x) and say that is a norm if the following

conditions hold.

(i) x ≥ 0 for all x ∈ V ,

(ii) If x = 0, then x = 0,

(iii) If » ∈ C and x ∈ V , then »x = |»| x .

(iv) (The triangle inequality) If x, y ∈ V , then x + y ¤ x + y .

We say that (V, ) is a normed space.

However, we wish to have a notion of distance which applies to spaces

which do not have a vector space structure. We seek a de¬nition modelled

on those properties of Euclidean distance which do not refer to vector space

structures. (Thus you should both compare and contrast De¬nition 10.3.1.)

De¬nition 10.3.4. We say that (X, d) is a metric space if X is a set and

d : X 2 ’ R is a function with the following properties:-

(i) d(x, y) = 0 if and only if x = y.

(ii) d(x, y) = d(y, x) for all x, y ∈ X.

(iii) (The triangle inequality) d(x, z) ¤ d(x, y)+d(y, z) for all x, y, z ∈ X.

Exercise 10.3.5. Show that, if (X, d) is a metric space, then d(x, y) ≥ 0 for

all x, y ∈ X.

It is a remarkable fact that the general notion of a metric space was ¬rst

introduced by Fr´chet in 1906 and the general notion of a normed space by

e

Banach in 1932! (We shall see one reason for the late emergence of the notion

of a norm in Theorem 10.4.6.)

Exercise 10.3.6. If is a norm over the (real or complex) vector space

V and we set d(x, y) = x ’ y , show that (V, d) is a metric space.

The conditions of De¬nition 10.3.4 are sometimes called the axioms for

metric space. However, they are not axioms in the same sense as the Funda-

mental Axiom of Analysis which asserts a fundamental principle of argument

which is to be accepted without further proof3 . Instead they try to isolate the

common properties of an interesting class of mathematical objects. (Com-

pare the de¬nition of birds as ˜oviparous, warm-blooded, amniotic vertebrates

which have their anterior extremities transformed into wings. Metacarpus

3

Within the context of a particular system. The axioms of one system may be theorems

in a another. We shall discuss this further in Section 14.3.

243

Please send corrections however trivial to twk@dpmms.cam.ac.uk

and ¬ngers carry feathers or quills. There is an intertarsal joint and not

more than 4 toes, of which the ¬rst is a hallux.™ Thus penguins are and

dodos were birds but dragon¬‚ies and bats are not.)

At ¬rst sight, axiom systems like that for metric systems seem merely

methods for economising on the number of theorems we have to prove. A

theorem which applies to all metric spaces will not need to be proved for

each individually. However, a successful axiom system should be a powerful

research tool by suggesting appropriate questions. (You will learn more about

a penguin by comparing it to a hawk than by comparing it to a frog.) Thus

if we have a ˜space on which we do analysis™ we can ask ˜can we make it into

a metric space?™. If it is a metric space we can then compare and contrast

it with other metric spaces that we know and this may well suggest new

theorems.

Although concepts like metric space are intended to apply to important

natural systems, we often study ˜toy examples™ in order to gain insight into

what can happen in such a system. Here is such a ˜toy example™.

Exercise 10.3.7. We work in Rm with the usual Euclidean norm. Show that

if d(x, y) = x + y when x = y and d(x, x) = 0, then (R m , d) is a metric

space.

This metric is called the British Railway non-stop metric. To get from A

to B in the fastest time, we travel via London (the origin). Here is another

version of the same idea which we call the British Railway stopping metric.

Exercise 10.3.8. We work in Rm with the usual Euclidean norm. If there

exists a real » such that »x = y, we write d(x, y) = x ’ y . Otherwise, we

set d(x, y) = x + y . Show that (Rm , d) is a metric space.

Much of the ˜mere algebra™ which we did for the Euclidean metric car-

ries over with hardly any change to the general metric case. Compare the

following de¬nition with De¬nition 4.1.8.

De¬nition 10.3.9. Let (X, d) be a metric space. If an ∈ X for each n ≥ 1

and a ∈ X, then we say that an ’ a if, given > 0, we can ¬nd an n0 ( )

such that

for all n ≥ n0 ( ).

d(an , a) <

We call a the limit of an .

Exercise 10.3.10. (i) Let d1 be the British Railway non-stop metric on Rm

de¬ned in Exercise 10.3.7. Show that xn ’ x in (Rm , d1 ) if and only if

244 A COMPANION TO ANALYSIS

(A) there exists an N such that xn = x for all n ≥ N , or

(B) x = 0 and xn ’ 0 as n ’ ∞.

(ii) Find and prove the corresponding result for the British Railway stop-

ping metric of Exercise 10.3.8.

If (V, ) is a normed space, we say that xn ’ x in (V, ) if xn ’ x in

the derived metric. The following result on limits in such spaces is an easy

generalisation of Lemma 4.1.9.

Lemma 10.3.11. Let V be a real vector space and a norm on V .

(i) The limit is unique. That is, if an ’ a and an ’ b as n ’ ∞, then

a = b.

(ii) If an ’ a as n ’ ∞ and n(1) < n(2) < n(3) . . . , then an(j) ’ a as

j ’ ∞.

(iii) If an = c for all n, then an ’ c as n ’ ∞.

(iv) If an ’ a and bn ’ b as n ’ ∞, then an + bn ’ a + b.

(v) Suppose that an ∈ V , a ∈ V , »n ∈ R, and » ∈ R. If an ’ a and

»n ’ », then »n an ’ »a.

Proof. Left to the reader. The reader who looks for the proof of Lemma 4.1.9

will ¬nd herself referred backwards to the proof of Lemma 1.2.2, but will ¬nd

the proofs for a general norm on a general vector space just as easy as the

proofs for the Euclidean norm in one-dimension.

Exercise 10.3.12. What changes are necessary (if any) in the statements

and proofs of Lemma 10.3.11 if we make V be a complex vector space?

If we consider a general metric, then we have no algebraic structure and

the result corresponding to Lemma 10.3.11 has far fewer parts.

Lemma 10.3.13. Let (X, d) be a metric space.

(i) The limit is unique. That is, if an ’ a and an ’ b as n ’ ∞, then

a = b.

(ii) If an ’ a as n ’ ∞ and n(1) < n(2) < n(3) . . . , then an(j) ’ a as

j ’ ∞.

(iii) If an = c for all n, then an ’ c as n ’ ∞.

The proof is again left to the reader.

The material on open and closed sets from Section 4.2 goes through es-

sentially unchanged (and proofs are therefore left to the reader).

De¬nition 10.3.14. Let (X, d) be a metric space. A set F ⊆ X is closed if

whenever xn ∈ F for each n and xn ’ x as n ’ ∞ then x ∈ F .

A set U ⊆ X is open if, whenever x ∈ U , there exists an > 0 such that,

whenever d(x, y) < , we have y ∈ U .

245

Please send corrections however trivial to twk@dpmms.cam.ac.uk

Example 10.3.15. Let (X, d) be a metric space. Let x ∈ X and r > 0.

(i) The set B(x, r) = {y ∈ X : d(x, y) < r} is open.

¯

(ii) The set B(x, r) = {y ∈ X : d(x, y) ¤ r} is closed.

¯

We call B(x, r) the open ball of radius r and centre x. We call B(x, r)

the closed ball of radius r and centre x.

Lemma 10.3.16. Let (X, d) be a metric space. A subset U of X is open if

and only if each point of U is the centre of an open ball lying entirely within

U.

Exercise 10.3.17. Find the open balls for the two British rail metrics. (For

all but one point there is a di¬erence between balls of small and large ra-

dius.) Show that the open sets for the British Railway stopping metric of

Exercise 10.3.8 consist of sets of the form A ∪ B where A is empty or

A = {x : x < δ} (here is the Euclidean norm and δ > 0) and B

is the union of sets of the form {»u : a < » < b} where 0 < a < b and

u = 0.

Find the open sets for the British Railway non-stop metric of Exercise 10.3.7.

De¬nition 10.3.18. The set N is a neighbourhood of the point x if we can

¬nd an r > 0 such that B(x, r) ⊆ N .

Lemma 10.3.19. Let (X, d) be a metric space. A subset U of X is open if

and only if its complement X \ U is closed.

Lemma 10.3.20. Let (X, d) be a metric space. Consider the collection „ of

open sets in X.

(i) … ∈ „ , X ∈ „ .

(ii) If U± ∈ „ for all ± ∈ A, then ±∈A U± ∈ „ .

(iii) If U1 , U2 , . . . , Un ∈ „ , then n Uj ∈ „ .

j=1

Lemma 10.3.21. Let (X, d) be a metric space. Consider the collection F

of closed sets in X.

(i) … ∈ F, X ∈ F.

(ii) If F± ∈ F for all ± ∈ A, then ±∈A F± ∈ F.

(iii) If F1 , F2 , . . . , Fn ∈ F, then n Fj ∈ F.

j=1

The new de¬nition of continuity only breaks the chain of translations

slightly because it involves two metric spaces.

De¬nition 10.3.22. Let (X, d) and (Z, ρ) be metric spaces. We say that a

function f : X ’ Z is continuous at some point x ∈ X if, given > 0, we

can ¬nd a δ( , x) > 0 such that, if y ∈ X and d(x, y) < δ( , x), we have

ρ(f (x), f (y)) < .

246 A COMPANION TO ANALYSIS

If f is continuous at every point x ∈ X, we say that f is a continuous

function on X.

The reader may feel that De¬nition 4.2.14 is more general than De¬ni-

tion 10.3.22 because it involves a set E. The following remark shows that

this is not so.

Lemma 10.3.23. Let (X, d) be a metric space and let E ⊆ X. Let dE :

E 2 ’ R be given by dE (u, v) = d(u, v) whenever u, v ∈ E. Then (E, dE ) is a

metric space.

We conclude this section with more results taken directly from Section 4.2

Lemma 10.3.24. Let (X, d) and (Z, ρ) be metric spaces and suppose that

the function f : X ’ Z is continuous at x ∈ X. Then, if xn ∈ E and

xn ’ x, it follows that f (xn ) ’ f (x).

Lemma 10.3.25. Let (X, d) and (Z, ρ) be metric spaces. The function f :

X ’ Z is continuous if and only if f ’1 (O) is open whenever O is open.

Lemma 10.3.26. Let (X, d), (Y, θ) and (Z, ρ) be metric spaces. If f : X ’

Y and g : Y ’ Z are continuous, then so is their composition g —¦ f .

10.4 Norms and the interaction of algebra

and analysis

Starting from one metric we can produce a wide variety of ˜essentially equiv-

alent metrics™.

Exercise 10.4.1. Let (X, d) be a metric space.

(i) If we de¬ne d1 (x, y) = min(1, d(x, y)), show that (X, d1 ) is a metric

space. Show further that, if xn ∈ X [n ≥ 0], then d1 (xn , x0 ) ’ 0 as n ’ ∞

if and only if d(xn , x0 ) ’ 0.

(ii) If we de¬ne d2 (x, y) = d(x, y)2 , show that (X, d2 ) is a metric space.

Show further that, if xn ∈ X [n ≥ 0], then d2 (xn , x0 ) ’ 0 as n ’ ∞ if and

only if d(xn , x0 ) ’ 0.

(iii) Let ± > 0 and de¬ne d± (x, y) = d(x, y)± . For which values of ± is

(X, d± ) always a metric space? For those values of ±, is it always true that,

if xn ∈ X [n ≥ 0], then d± (xn , x) ’ 0 as n ’ ∞ if and only if d(xn , x) ’ 0?

Prove your statements.

(iv) (This is trivial but explains why we had to be careful in the statement

of (iii).) Give an example of metric space (X, d) with X an in¬nite set such

that (X, d± ) is a metric space for all ± > 0.

247

Please send corrections however trivial to twk@dpmms.cam.ac.uk

Because norms re¬‚ect an underlying vector space structure they are much

more constrained.

Lemma 10.4.2. Let 1 and 2 be norms on a vector space V . Then the

following two statements are equivalent.

(a) There exist K, L > 0 such that K x 1 ≥ x 2 ≥ L x 1 for all

x∈V.

(b) If xn ∈ V [n ≥ 0], then xn ’ x0 1 ’ 0 as n ’ ∞ if and only if

xn ’ x0 2 ’ 0.

Proof. It is easy to see that (a) implies (b), since, for example, if xn ’x0 ’

2

0, then

¤ L’1 xn ’ x0

xn ’ x0 ’ 0,

1 2

and so xn ’ x0 1 ’ 0 as n ’ ∞.

To see that (b) implies (a), suppose that (a) is false. Without loss of

generality, suppose that there is no K > 0 such that K x 1 ≥ x 2 for all

x ∈ V . Then we can ¬nd yn ∈ V such that

> n2 y n 1 .

yn 2

’1

Setting x0 = 0 and xn = n’1 yn for n ≥ 1, we obtain

1 yn

xn ’ x0 = 1/n ’ 0

= xn

1 1

and

xn ’ x0 = xn > n,

2 2

so xn ’ x0 0 as n ’ 0. Thus (b) is false if (a) is false

2

Exercise 10.4.3. Let d1 and d2 be metrics on a space X. Consider the

following two statements.

(a) There exist K, L > 0 such that Kd1 (x, y) ≥ d2 (x, y) ≥ Ld1 (x, y) for

all x, y ∈ X.

(b) If xn ∈ X [n ≥ 0] then d1 (xn , x0 ) ’ 0 as n ’ ∞ if and only if

d2 (xn , x0 ) ’ 0.

Show that (a) implies (b) but that (b) does not imply (a).

Although we shall not make much use of this, the concepts just introduced

have speci¬c names.

248 A COMPANION TO ANALYSIS

De¬nition 10.4.4. (i) Let K ≥ 0. If (X, d) and (Y, ρ) are metric spaces, we

say that a function f : X ’ Y is Lipschitz with constant K if ρ(f (x), f (y)) ¤

Kd(x, y) for all x, y ∈ X.

(ii) We say that two metrics d1 and d2 on a space X are Lipschitz equiv-

alent if there exist K, L > 0 such that Kd1 (x, y) ≥ d2 (x, y) ≥ Ld1 (x, y) for

all x, y ∈ X.

Exercise 10.4.5. (i) If (X, d) and (Y, ρ) are metric spaces, show that any

Lipschitz function f : X ’ Y is continuous. Give an example to show that

the converse is false.

(ii) Show that Lipschitz equivalence is indeed an equivalence relation be-

tween metric spaces.

The following result is a less trivial example of the interaction between

algebraic and metric structure.

Theorem 10.4.6. All norms on Rn are Lipschitz equivalent.

Proof. We consider the standard Euclidean norm given by

1/2

n

x2

x= j

j=1

and show that it is equivalent to an arbitrary norm —.

One of the required inequalities is easy to obtain. If we write ei for the

unit vector along the xi axis we have,

n n

¤ |xj | ej

x = xj ej

— —

j=1 j=1

—

¤ n max |xr | max er ¤ (n max er — ) x .

—

1¤r¤n 1¤r¤n 1¤r¤n

We have thus shown the existence of a K such that K x ≥ x — .

To obtain the other inequality we use an argument from analysis4 . Ob-

serve that, if we give Rn and R the usual Euclidean metric and de¬ne

f : Rn ’ R by

f (x) = x — ,

then, using the triangle inequality for and the result of the previous

—

paragraph,

|f (x) ’ f (y)| = | x ’ y —| ¤ x ’ y ¤K x’y ,

— —

4

Experts may be interested in Exercises K.184 and K.185. Non-experts should ignore

this footnote.

249

Please send corrections however trivial to twk@dpmms.cam.ac.uk

and so f is continuous. Now the unit sphere

S(0, 1) = {x ∈ Rn : x = 1}

is closed and bounded for the usual Euclidean metric and so, by Theo-

rem 4.3.4, f is bounded on S(0, 1). In particular, we can ¬nd k ∈ S(0, 1)

where f attains its minimum, that is to say,

f (k) ¤ f (x)