Mathematics in the 20th century: Chaos, codes and colouring

THE 20TH CENTURY: CHAOS, CODES AND COLOURING

Professor Robin Wilson

Introduction
Before I describe some 20th-century mathematics, I’d like to tell you a story about a young Swiss alpenhorn player.  He was madly in love with a young lady in his tiny Alpine village and he decided to serenade her with his finest and longest alpenhorn ― in fact, it was infinitely long, being obtained by rotating the hyperbola y = 1/x (where x goes from 1 to infinity) around the x-axis.  Unfortunately, when he tried to play it, he wouldn’t work ― it had become rusty and he needed to paint its inside.  But when he calculated how much paint would be needed, he found that an infinite amount would be required.  In desperation he went to the village mathematician for help.  The mathematician calculated the volume inside the alpenhorn and found it to be finite.  His solution was now simple ― pour this finite amount of paint into the alpenhorn, and then pour the remainder away, leaving a coating of paint on the inside.  The young alpenhornist did so, the young lady was delighted ― and they lived happily ever after.

Fractals
What’s the relevance of this story?  To answer this I’ll ask the question:how long is the coastline of Britain?  If you try to measure it with a ruler, or if you look at the country from far above, you can estimate the length of the coastline.  But as you measure more accurately, or get closer to Earth, you become aware of more and more inlets and bays, and the length increases accordingly.  In fact, the closer you get, the longer the coastline seems to become ― imagine walking around it with a pedometer ― and then with a six-inch ruler, and so on.  In fact, the coastline of Britain has infinite length, even though it encloses a finite area.  It’s rather like the inside of the alpenhorn, which has infinite surface area but encloses a finite volume.
A similar situation occurred with the blancmange function I showed you last time ― the curve Ian Stewart described as a ‘trifle unorthodox’.  This curve is continuous (it’s all ‘joined up’), but every point is a ‘corner’ (you can’t measure its slope anywhere).  It also has other interesting properties: it has infinite length, yet encloses a finite area (like the coastline of Britain), and it’s also self-similar ― parts of it have the same shape (though smaller) as you look at it in closer detail.
This property is a standard feature of fractal patterns, a topic of great interest in the 20th century.  In 1906 the Swedish mathematician Helge von Koch described his snowflake curve.  To construct it you take an equilateral triangle, and then replace the middle third of each side (which we can think of as the base of a smaller equilateral triangle) by the other two sides of the triangle, giving a ‘peak’ on each side of the original triangle.  Now repeat this process with each of the lines in the resulting picture.  If we carry this on for ever, we obtain the snowflake curve.  Like the blancmange graph it has infinite length, encloses a finite area, and exhibits self-similarity. 
Another fractal pattern is obtained by taking an equilateral triangle, splitting it into four smaller equilateral triangles and removing the inner one.  If we do this repeatedly, we end up with the Sierpinski gasket(named after the Polish mathematician Waclaw Sierpinski), a curve of infinite length which encloses zero area.
A new way of obtaining fractal patterns was discovered by Benoit Mandelbrot.  Consider a transformation in which we take a complex number (one of the form a + bi, where i is √–1), square it to give a new number, and continually repeat the process.  For example, if c = 0 and we start with the point 2, we get successively 4, 16, 256, … going off to infinity, whereas if we start with the point ½, we get successively ¼, 1/16, 1/256, … tending to 0.  Any point inside the circle with centre 0 and radius 1 stays inside the circle, while any point outside the circle goes to infinity; those points on the circle stay on the circle.  We call this boundary circle the Julia set corresponding to c = 0 (after the French mathematician Gaston Julia), and its inside is the keep set (because we keep its points in sight).
Different values for c give a wide range of different boundary curves (Julia sets): for example, c = 0.25 gives us a ‘cauliflower’, while c = –0.123 + 0.745i gives us a shape rather like a rabbit.  The Julia sets for some values of c are in one piece, while others are in several pieces.  If we draw a picture of all the complex numbers c for which the Julia set is in one piece, we obtain a bizarre picture called the Mandelbrot set.  This fascinating set arises in the study of chaos theory and has given rise to a whole range of beautiful designs under the heading of fractal art.

The mathematics of symmetry
Another area that was greatly studied in the 20th century is that of symmetry.  This area of mathematics, known as group theory, has its origins in the work of Lagrange, Cauchy, Galois and others in the 18th and 19th centuries.  To introduce the idea, let’s look at the English art ofbell-ringing. 
The method known to bell-ringers as Plain Bob Minimus involves the ringing of four bells (which we’ll call 1, 2, 3, 4) in such a way as to include all twenty-four possible permutations of these four numbers.  Because bells are heavy, we can interchange only bells that are consecutive, so if we start with the bells in the order 1234, we could interchange both outer pairs of bells 12 and 34 (giving 2143) or the inner pair 23 (giving 1324).  Thus, we could start with
1234 → 2143 → 2413 → 4231 → 4321 → 3412 → 3142 → 1324.
If we now interchanged the middle bells we’d get back to the starting point, so instead we interchange just the last two, giving 1342, and then proceed as before with 3124, 3214, and so on.  Eventually we obtain all 24 permutations of 1, 2, 3, 4.
More generally, we can look at all the permutations on 1, 2, 3, 4, 5 (there are 120 of these), or of any collection of symbols.  Some permutations are even, in that they are obtained by switching an even number of pairs (such as the pairs 12 and 34), while others are odd (such as switching the single pair 23).  We combine two permutations by carrying out one after the other, or we can form the inverse of a permutation by undoing it (for example, switching the bells back). 
A different type of example gives rise to similar conclusions.  Suppose we look at all the rotations of a cube lying on a table.  There are 24 of these, since each of the six faces can be in contact with the table and can be in any of four different positions: these 24 rotations consist of the ‘identity’ (where we leave the cube as it is), 9 face-rotations (three rotations about each of the three opposite pairs of faces), 8 vertex-rotations (two rotations about a line joining each of the four opposite pairs of corners) and 6 edge-rotations (one about a line joining the midpoints of each of the six opposite pairs of edges).  In fact, if we consider the four diagonals of the cube, we can check that each permutation of these diagonals corresponds exactly to one of the bell-ringing permutations we had earlier. 
Similarly, we can look at the rotations of other geometrical figures, such as a dodecahedron (with twelve pentagonal faces); this gives 60 rotations.
What do all these examples have in common?  In each case we have a set of objects (such as permutations, or rotations) which we can combine in pairs to give another object of the same type, and they satisfy three further properties: there’s an identity element (where we ‘do nothing’), each rotation or permutation has an inverse (it can be ‘undone’), and combinations are associative (if we do the first two followed by the third, it’s the same as doing the first followed by the second and third).  These give rise to the following axioms for an abstract group:
Take a set G of elements, and a rule (denoted by □) for combining them.  For a group:

Closure: if a and b are in G, then so is a □ b.
Associativity: if a, b and c are in G, then (a □ b) □ c = a □ (b □ c).
Identity: there is an element e such that a □ e = e □ a = a for all ain G.
Inverses: for each a in G, there is an inverse a–1 such that a □ a–1 = a–1 □ a = e. 

For many groups (but not these), we get the same result when we combine elements in either order:

Abelian-ness (or Commutativity): if a and b are in G, then a □ b =b □ a.

An example of an Abelian group is the addition of integers …, –2, –1, 0, 1, 2, 3, … ; the identity element is 0 and the inverse of a is –a.  As an example of associativity we have (3 + 4) + 5 = 3 + (4 + 5), and the group is Abelian ― for example, 3 + 4 = 4 + 3.
We next consider the rotation of regular polygons.  If we rotate a square through 0, 1, 2 or 3 right angles, it ends up in the same position.  We can ‘add’ these rotations:  2 right angles + 3 right angles = 1 right angle, and so on; this is the same as adding the integers 0, 1, 2, 3 ‘modulo 4’ ― that is, we add, and then subtract off multiples of 4 to get back to 0, 1, 2 or 3, so 3 + 3 = 2, 1 + 3 = 0, etc.  We get a group called the cyclic group C4.  Similarly, we can rotate a regular pentagon through multiples of 72 degrees to get the cyclic group C5, consisting of the integers 0, 1, 2, 3, 4, which we add modulo 5. More generally, starting with a regular n-sided polygon we get the cyclic group Cn. 
In the 20th century, algebraists were concerned with classifying groups of various types.  An example of this involves the classification of Abelian groups.  Amazingly, we can obtain any Abelian group by taking cyclic groups and combining them in a simple fashion ― this is called the classification theorem for Abelian groups.
The ultimate goal is to classify all groups by showing how they can be constructed from basic ‘building blocks’ ― just as all natural numbers can be formed by multiplying prime numbers, and all Abelian groups can be formed by combining cyclic groups.  The basic building blocks for groups in general are called simple groups ― these are groups that essentially contain no smaller groups inside them (technically, they have no non-trivial ‘normal subgroups’ ― a concept introduced around 1830 by Evariste Galois). 
But which groups are simple?  Much of the 20th century was spent in trying to classify all the simple groups, and this quest was ultimately successful ― a major achievement involving thousands of pages of detailed work!  To cut a long story short, there are several infinite classes of simple groups ― such as all the cyclic groups with a prime number of elements (for example, C5, C37, C101, …), or the rotations of a dodecahedron, or the set of all even permutations of a set of five or more elements, or various groups of ‘Lie type’ arising from matrices ― together with 26 individual so-called ‘sporadic groups’ that don’t fit into any of these infinite categories.  The largest of these sporadic groups is called ‘the Monster group’, which has 808,017,424,794,512,875,886,459,904,061,710,757,005,754,368,000,000,000 elements!       
  
Different infinities
A famous result of Georg Cantor in the 19th century was the truly revolutionary idea that some infinities are larger than others.  This idea had its origins in the musings of Galileo over 300 years earlier, who had noticed that there are far fewer perfect squares 1, 4, 9, 16, … than natural numbers 1, 2, 3, … , and yet we can match them up exactly:
1 ↔ 1,  2 ↔ 4,  3 ↔ 9,  4 ↔ 16,  ...
We can also match the natural numbers with some larger sets, such as the integers.  We simply list them in the order:
0,  1,  –1,  2,  –2,  3,  –3,  4,  ...
Notice that every integer occurs somewhere in the list ― none is omitted.
Cantor’s first amazing discovery was that we can also list all the rational numbers in order, so that the set of all rational numbers has ‘the same size’ as the set of all natural numbers, even though it seems so much bigger.  However, as Cantor proved, the set of all real numbers cannot be made to match up with the natural numbers, and so must be a ‘bigger’ infinite set.  It follows that some infinite sets are genuinely bigger than others: not all infinities are the same.  Indeed, to take his idea further, there are infinitely many infinities, all of different sizes.
We can construct an ‘arithmetic of infinities’.  The size of the set of all integers (or of all rationals) is called aleph-0 (aleph is a Hebrew letter), and we can write ‘infinite equations’ such as aleph-0 + 5 = aleph-0, and aleph-0 + aleph-0 = aleph-0.  The size of the set of all real numbers is called aleph-1 (which is larger than aleph-0).  A question arises, is there an infinite set whose size lies between these two infinite numbers?  This problem became known as Cantor’s continuum problem.
The answer was unexpected.  In 1902 Bertrand Russell upset the set theory apple-cart by producing a famous logical paradox that seemed to have no answer.  One version of this paradox is that of the barber in a village who shaves everyone who doesn’t shave themselves, but who obviously doesn’t shave those who do shave themselves; the question is:who shaves the barber?  (Whatever answer you give must be false, as you’ll see after a moment’s thought.)  The paradox was eventually overcome by Zermelo and Fraenkel who produced a system of logic that could deal with it ― this logical system became universally accepted and used.  Then, in the 1930s, Kurt Gödel produced another bombshell: in any axiomatic system that one can construct, there are true results that cannot be proved, and there are statements that are undecidable ― they cannot be proved true or false.        
In 1963 Paul Cohen stunned the mathematical world by proving that Cantor’s continuum problem cannot be decided within the Zermelo-Fraenkel logical system ― it is undecidable. 

Codes                 
In the latter half of the 20th century, security became a major preoccupation ― whether for military secrets or for the security of our bank accounts or credit cards.  Surprisingly, the tool that provides this security is the topic of prime numbers which had previously seemed to have no practical uses whatever.
The reason that prime numbers are relevant is that there are now many methods for determining whether a given large number is prime, but if it is not, then it is much harder to find out what its prime factors are.  For example, we can now tell fairly quickly on a computer whether a given 200-digit number is prime, but it would take many years to find its prime factors.     
In early codes, both the sender and the receiver of a message needed to know the secret code in order for the sender to encode the message and the receiver to decode it.  In the 1970s a new method of encoding secret messages was devised by Ronald Rivest, Adi Shamir and Leonard Adleman, and became known as the RSA method, or public-key cryptography. 
Here is an example of how it works, for a message sent by Alice to Bob.  Alice chooses two large prime numbers p and q (say, of 150 digits each) and keeps them secret, but makes public their product n = pq.  She then chooses two other numbers v and s, each less than n, so that sv = 1 (modulo (p – 1)(q – 1)) ― that is, the remainder on dividing sv by (p – 1)(q – 1) is 1; she keeps s secret and makes the number v public.  For example (with much smaller numbers), if she chooses p = 5 and q = 11, and then chooses v = 3, she can calculate s to be 27 (since sv = 81, whose remainder on division by (5 – 1)(11 – 1) is 1).  Alice then converts her message into a number b smaller than n, and calculates the number h= bs (modulo n) (so if b = 49, then h = 4927 (modulo 55) = 14).  She sends the number h to Bob, who looks up the public numbers n and v and calculates hv (modulo n) ― this always equals b, as required.  For example, with b = 49 and h = 14, Bob calculates 143 (modulo 55), which is 49.
This method has proved to be secure and is now of widespread use.

Surfaces
We are all familiar with surfaces such as the sphere and the bagel-shaped torus.  Slightly more complicated are ‘pretzels’, which are like toruses except that they have several holes; an example is the double-torus with two holes.  These surfaces are orientable ― they have an inside and an outside ― and each can be obtained from a sphere by attaching a number of ‘handles’ to it. 
Other surfaces are non-orientable ― these include the Möbius strip, which has only one side and is obtained by twisting one end of a long strip of paper through 180 degrees and glueing the ends, and objects called theprojective plane and the Klein bottle which cannot be constructed in three-dimensional space.  To obtain a non-orientable surface, take an orientable one, cut some circular holes in it, and stick on Möbius strips along their common boundary (this cannot be done in three dimensions!) ― this is called adding a cross-cap. 
One project in the 20th century was to classify all surfaces, and this turned out to have a surprisingly simple answer.  For the orientable case, every surface is essentially a sphere with a number of handles attached.  For the non-orientable case, every surface is essentially a sphere with a number of cross-caps attached. 
Further classifications were obtained by drawing diagrams on the surface, counting the number of vertices (V), the number of edges (E) and the number of faces (F), and calculating the number V – E + F.  If we draw diagrams on a sphere, we always get the answer 2, whatever diagram we choose.  If we draw diagrams on a torus we always get the answer 0, and if we do it for a torus with k holes we get the answer 2 – 2k.  For non-orientable surfaces, we obtain similar results: for a Klein bottle we always get the answer 0, and for a non-orientable surface with k cross-caps we get the answer 2 – k, whatever diagram we draw.

Colouring maps
Many people are familiar with the four-colour problem ― to prove that we can colour the countries of any map on a plane or a sphere with only four colours in such a way that neighbouring countries are coloured differently.  This problem was first posed in 1852, but was not proved until 1976. 
The solution involved looking at configurations of countries, and seekingan unavoidable set of reducible configurations: an unavoidable set is a set of configurations, at least one of which must appear in any map ― for example, every map must contain at least one triangle, quadrilateral of pentagon.  The first two of these are fairly easy to deal with ― they are ‘reducible’, in that no map that contains either of these needs five colours, and so can be coloured with four colours or fewer, but the case of the pentagon is much more difficult.  The problem was eventually solved by Kenneth Appel and Wolfgang Haken by using a computer to help them to obtain a set of 1482 reducible configurations: every map must contain one of these, and none of them can occur in a map that needs five colours ― so no such map can exist.
Surprisingly, the corresponding problem for maps on a surface was settled earlier.  On a torus, every map can be coloured with seven colours, and there are such maps that need this number.  On a projective plane, every map can be coloured with six colours, and there are such maps that need this number.  But in general, the problem is much harder ― we can find the ‘right’ number of colours, but to show that some maps need this number of colours in general took over 70 years.  It was eventually solved in 1952 by Gerhard Ringel for non-orientable surfaces, and by Gerhard Ringel and Ted Youngs for orientable surfaces in 1968.

© Professor Robin Wilson, Gresham College, 15 November 2006