A Cartographic Conundrum

by Nicholas Mee on September 10, 2018

In the Victorian era the British were fond of watching the pink of their empire spread outwards across maps of the world. A rather perceptive young student Francis Guthrie noticed something rather surprising while colouring the counties on a map of England. It seemed that no more than four colours were ever required to colour the regions on a map so that no border separated two regions of the same colour. Even when he drew maps with the most convoluted boundaries four colours were always enough. But he could find no explanation for why this was true. Guthrie later became Professor of Mathematics at the University of Cape Town. A four-colour map of the United States is shown here.

A four-coloured map of the United States.

Francis mentioned this cartographic conundrum to his brother Frederick who told Augustus de Morgan, Professor of Mathematics at University College, London. Francis’s simple observation is known as the four colour problem. It can be stated succinctly as:

Can every map be coloured with at most four colours, in such a way that neighbouring countries are coloured differently?

The oldest surviving account of the puzzle is in a letter of 23 October 1852 from de Morgan to the Irish mathematician Sir William Rowan Hamilton. The problem sounds so simple that we might expect it should be quite easy to prove. However, finding a water-tight proof turned out to be incredibly difficult. The four colour problem became notorious because on several occasions eminent mathematicians supplied ingenious proofs only for other mathematicians to shoot holes through them. The London barrister and amateur mathematician Alfred Bray Kemp published his proof in 1879 and it was believed correct for eleven years until Percy John Heawood found its flaws in 1890.

Topology

A Klein Bottle

If it were possible to prove the four colour problem on a sphere, this would automatically solve the problem on the plane, as a map on a sphere can always be projected onto a plane and vice versa.

But one curious feature of the problem is that it is much easier to determine the maximum number of colours for maps on other surfaces.

It might seem that any problem on a sphere or a plane must be much simpler than the equivalent problem on a surface as strange as a Klein bottle shown here, but not in this case. We know that six colours are required to colour every map on a Klein bottle.

The Torus

The torus, which is shaped like a car tyre, is another example. If we take a rectangular strip of paper and glue one pair of opposite edges we can form a cylinder. If we then bend the cylinder round and glue it two circular ends together we obtain a torus, as shown in the image on the right.

Heawood proved in 1890 that any map on a torus can be coloured with at most seven colours.

Another way to think of the torus is to consider it as a rectangle with opposite edges identified, which means that if an object, such as a line or even a spaceship, crosses the top edge of the rectangle it reappears across the bottom edge, just like in old video arcade games such as Asteroids.

We can use this idea to see a seven-colour map on a torus. The image below shows such a map on a square with opposite edges identified. The animation shows the torus that is produced by gluing the opposite edges of the square together.

A square with opposite edges identified representing a torus. This is a map on a torus that requires seven colours.

By the 1970s mathematicians had solved the problem on every surface apart from the sphere and plane.

A seven-coloured map on a torus.

Computer Aided Mathematics

About 120 years passed between the initial interest in the map-colouring problem and its eventual conquest. Kenneth Appel, Wolfgang Haken and John Koch finally demonstrated that four colours are sufficient, but their proof is one of the most controversial in the whole of mathematics. This is because only part of the proof was completed in the traditional fashion with pencil and paper. Appel and Haken actually showed that all maps can either be coloured with four colours or they are equivalent to almost two thousand ‘irreducible’ maps. They then turned the problem over to a computer. With the assistance of John Koch, they programmed the computer to check through these irreducible cases. On 21 June 1976 they announced the four colour problem had been solved. No one doubts the computer analysis shows the truth of the four colour theorem, but some mathematicians remain uncomfortable about a proof so unwieldy that a machine is required to scrutinize many more exceptional cases than a human could check. Following the original proof, the number of irreducible cases has been reduced, but the proof still requires a computer to test these cases.

Since Plato, many mathematicians have regarded themselves as intrepid explorers of an abstract realm of ideal mathematical objects. Computer aided proofs raise important philosophical questions about the nature of mathematical proof and challenge the status of pure mathematics.

Further Information

For more information about the four colour theorem, see Four Colours Suffice by Robin Wilson (Penguin 2002).

 

{ 2 comments }

The Generation Game

by Nicholas Mee on June 10, 2018

In 2012 CERN announced the discovery of the Higgs boson, the final missing fundamental particle of the standard model. But many mysteries remain.

The matter particles of the standard model.

Atoms consist of a tiny nucleus composed of protons and neutrons surrounded by a swarm of orbiting electrons. Protons are formed of two up quarks and one down quark bound together, whereas neutrons are formed of two down quarks and one up quark. In stars the nucleus of one type of atom may be transformed into the nucleus of another type of atom and in the process neutrinos are emitted. These four particles: the up and down quarks, the electron and the electron neutrino complete the first column of the standard model table of matter particles shown to the right. Collectively they are known as the first generation.

The four particles of the first generation are sufficient to form all ordinary matter, so it is rather mysterious that the table includes two more columns containing two more generations of matter particles. The particles of the second and third generations seem to be just heavier replicas of the corresponding particles of the first generation.

As yet there is no explanation of why fundamental matter particles come in triplicate. But if string theory is correct, and that is a very big if, it might all come down to the most intimate properties of space.

The Euler Number

In 1752 the great Swiss mathematician Leonhard Euler (pronounced Oiler) discovered a surprising property of the Platonic solids. If we count the number of faces F of a polyhedron and subtract the number of its edges E, then add the number of vertices V, we always obtain the same answer: 2. Take the cube; it has six faces, twelve edges and eight vertices, so we obtain the sum

F – E + V = 6 – 12 + 8 = 2 .

Now take a dodecahedron, which has twelve faces, thirty edges and twenty vertices. In this case we obtain

F – E + V = 12 – 30 + 20 = 2 .

Euler was not the first to discover this property of polyhedra. It had been noted by René Descartes a century earlier, but it is Euler whose name is attached to it.

The buckyball molecule is shaped like a truncated icosahedron.

And the formula does not only apply to regular polyhedra. Take the truncated icosahedron, which is famously the shape of the buckyball molecule shown above, named after Buckminster Fuller as a tribute to the shape of his geodesic dome. In this case F = 32, E = 90, V = 60, so we again obtain 2. This property is, in fact, shared by all polyhedra, or at least all polyhedra that are topologically equivalent to a sphere, and that is the key to what follows.

Inflatable Polyhedra

Imagine inflating a polyhedron until all its corners and edges are smoothed out and we obtain a sphere. The sphere and the polyhedron are topologically equivalent, so it is reasonable to say that the sphere has Euler number 2, just like the polyhedron. (There are ways of calculating the Euler number directly from the properties of a sphere, but we don’t need to go into that.)

Henri Poincaré realised the Euler number is not simply a fixed quantity that is always equal to two. It is more than that. It is a formula that encapsulates some of the deepest properties of a shape; properties that do not change when the shape is stretched and distorted. The Euler number encodes topological information about the shape—it is a topological invariant.

Now consider a square. It has four edges, four vertices and one face—the square itself. So we can calculate the Euler number as before. In this case

F – E + V = 1 – 4 + 4 = 1.

Polygons always have an equal number of edges and vertices and a single face, so they all have Euler number 1. Polygons are topologically equivalent to a disc, which is what we obtain if we increase the number of edges of the polygon indefinitely or inflate the polygon until its edges are smoothed out. So it is reasonable to conclude that the Euler number of a disc is 1.

Holey Geometry

What about other shapes?

No amount of stretching a sphere will transform it into a torus. This is because the torus has a hole through it. Topologists refer to the number of holes as the genus of the surface. So a torus has genus one, whereas a sphere has genus zero.

So what is the Euler number of the torus? One way to find out is to make a polyhedron that is topologically equivalent to a torus, as shown in the image below. It is easy to count the number of faces. There are four around the outside, four on the front surface, four on the back surface and four around the hole in the middle, making a total of sixteen. The vertices are also easy to count: there are eight around the outside and eight around the inner hole, making a total of sixteen. The edges are less easy to count, but we can deduce the total by noting there are two vertices at the end of each edge and four edges emanate from each vertex, so there are twice as many edges as vertices. There are therefore thirty-two edges. Now if we calculate the Euler number we find

F – E + V = 16 – 32 + 16 = 0.

So the Euler number of the polyhedron is 0. All polyhedra that are topologically equivalent to a torus have Euler number 0, so this is the Euler number of a torus.

A polyhedron with a hole through the middle. Topologically this polyhedron is equivalent to a torus.

Cut and Paste

Although the topology of a shape is unchanged by any amount of stretching and warping, it may be changed by cutting and pasting. We can form a new surface by taking two tori, cutting out a disc from each torus and pasting the two circular openings together. This gives us a surface known as a double torus or genus two surface, as shown below.

Forming a double-torus. Top: Two tori with discs removed. Bottom: The open edges of the two tori have been glued to form a double-torus.

We started with two tori, so initially the Euler number was zero. Each disc has Euler number 1, so by removing and discarding the two discs we reduce the Euler number by two. The Euler number of the double torus is therefore two less than the pair of tori we started with, so it equals -2. In general increasing the genus by one decreases the Euler number by two.

Surfaces of different genus. The sphere has genus zero. The torus has genus one. The other surfaces have genus two, three, four and five.

The Euler number can be defined in higher dimensions. The relationship between the Euler number and the holes is quite similar, even though there are many more strange and exotic ways for a surface to curl up in higher dimensions.

Topology with a Pinch of Salt

String theory’s hidden dimensions might explain why the Large Hadron Collider sees several generations of fundamental matter particles. String theory predicts there are six extra hidden dimensions in the form of a six-dimensional hypersurface. Strings wrap around holes in the hypersurface and this affects how they vibrate. These vibrating strings correspond to the spectrum of particles that seen in particle physics experiments and listed in the standard model table above. One rather mind-bending implication is that the number of generations of matter particles could be due to the topology of the hidden hypersurface. The mathematical wizardry of string theory shows that, if this is true, then the number of generations of fundamental particles must equal half the Euler number of the hypersurface.

So what is the Euler number of the hypersurface? The extra dimensions of string theory can curl up in innumerable ways to form a minuscule hidden hypersurface and theorists have trawled through these possibilities in search of some promising candidates. One of the first to be studied was the quintic hypersurface whose three-dimensional projection is shown above. This hypersurface has an Euler number of 200, so it cannot be the correct shape of the hidden dimensions, as this would result in 100 generations of matter particles, which misses the mark by a rather large margin.

The quintic hypersurface is the starting point for a more promising hypersurface. Two distinct five-fold symmetries can be glimpsed in the animation. There is a pentagonal symmetry around the centre of the image and also smaller pentagonal openings within the projection of the hypersurface. If these symmetries are used to fold up and glue the quintic hypersurface to create a new hypersurface with fewer holes. The Euler number of this new hypersurface is just 200/(5×5) = 200/25 = 8, so it would result in real world physics with just four generations of matter particles. This is still too many, as we know there are three generations and no more, but it is encouragingly close. Other Calabi-Yau hypersurfaces have been found with an Euler number of six that would lead to three generations, just as we see in the standard model.

Although the possibility of explaining features of particle physics with a dose of topology is certainly intriguing, string theory remains highly conjectural. As yet there is no direct experimental evidence that it plays a role in particle physics.

 

Further Information

There is more about strings and things in my book Gravity: Cracking the Cosmic Code.

 

 

{ 2 comments }

Burning Down the House

May 21, 2018

In 1998 two students, Larry Page and Sergey Brin, studying for PhDs in computer science at Stanford University, California founded a new tech company called Google. The company was based on an algorithm they had invented and incorporated into a new search engine—the Google browser. Less than two decades later Google is valued at well […]

Read the full article →

The Chamber of Secrets

April 29, 2018

By the mid-1930s, just five fundamental particles were known. This concise collection of building blocks revealed the true nature of matter and light. Three types of particle: electrons, protons and neutrons, form the wide array of atoms known to chemistry, and the whole electromagnetic spectrum including light is composed of photons. The fifth particle is […]

Read the full article →

The Cosmic Mystery Tour

April 6, 2018

My new book The Cosmic Mystery Tour will be published by Oxford University Press later this year. It is a short, easy read offering a lightning trip around some of the greatest mysteries of our universe with lots of attractive illustrations. The trip is interwoven with brief tales of the colourful characters who created modern science, […]

Read the full article →

Hawking Crosses the Event Horizon

March 22, 2018

Stephen Hawking died on 14 March 2018. As a student in the 1960s he was diagnosed with motor neurone disease and given just two years to live. Confounding these predictions, he lived to become the world’s most famous scientist since Einstein. His incredible determination to succeed in the face of any obstacle and his drive to […]

Read the full article →

Hawking Radiation

March 19, 2018

What is the connection between a steam engine and a collapsed star? Not much, you might think. There is, however, a very deep and subtle connection that is still not completely understood. Brewing Up New Theories of Physics James Prescott Joule, the son of a wealthy Manchester brewer, was taught physics by John Dalton, famous […]

Read the full article →

The Pale Blue Dot

March 7, 2018

Voyager I was launched by NASA in September 1977, on course for the outer solar system and beyond. Carl Sagan realised the mission was an opportunity to highlight the immensity of the cosmos and acquire a new perspective on our place within it. After some persuasion, NASA agreed and in 1990 Voyager’s cameras were directed […]

Read the full article →

All for One and One for All

February 10, 2018

In days of old, when knights were bold, it was essential that a knight should bear an elegant mathematical symbol on his coat of arms. Well, perhaps not, but at least the Borromeo family used a design that is well known to mathematicians. The coat of arms of the Borromeo family of merchants and bankers […]

Read the full article →

The Wheel of Fortune

November 7, 2017

We never stray far from devices that chop up our days into hours, minutes and seconds. We are now all synchronized and no-one is out of step with the rest of the world. It is difficult to imagine how different life must have been when days came and went and the passage of time was […]

Read the full article →