A watershed proof in the history of mathematics
While growing up, we sometimes come across certain special mathematical problems which have the following three properties – they are easily stated, are simple enough to understand and are either unsolved or require the knowledge of advanced mathematics, certainly for that age, to be tackled. Such problems perform an especially important role of stimulating our young minds even as they provide us a fleeting glimpse of the beautiful world of mathematics that lies beyond our school texbooks. Prime examples of such problems are Fermat’s Last Theorem, the Goldbach Conjecture, the Seven Bridges of Königsberg and so on.
The Four Colour Theorem (4CT) falls in this unique category of problems.
The 4CT says that in any continuous map containing an arbitrary number of countries, the maximum number of colours needed to colour them such that no two adjoining countries are of the same colour, is four. If two countries meet at a point, then they are not considered to be adjoining.
The story starts in the middle of the nineteenth century in England with two Guthrie brothers – Francis and Frederick, the latter of whom was studying under the famed mathematician Augustus De Morgan, the formulator of the well-known De Morgan’s Laws of set theory.
Francis came up with the Four Colour Conjecture (now theorem) in late 1852 when he noticed that he only needed four colours to colour all the counties of England such that adjoining counties were of different colours. He discussed this with Frederick who then consulted De Morgan. Therefrom, there was no turning back.
The problem was not as popular among mathematicians in the initial decades, and it took another half a century before it started to be taken seriously by mathematicians on the other side of the Atlantic. Nevertheless, all this while, it continued to invoke the occasional public interest and draw in amateurs and non-mathematicians to dabble in it.
The 4CT was proven by contradiction and at its heart lay the idea of a “minimal criminal” – if the theorem is false, then there must exist a particular smallest possible map that necessarily requires at least five colours to be coloured. Two core ideas formed the bedrock of this method of attack – “unavoidable set”, which is a set of configurations of shapes such that at least one member of such a set must be present in every map, and “reducible configuration”, which is any arrangement of countries that cannot exist in a minimal criminal.
So, if we are able to find a non-empty “unavoidable set of reducible configurations”, which is a set of reducible configurations such that at least one member of the set must be present in every map, then that would prove that a minimal criminal could not exist, thereby proving the 4CT.
As the twentieth century progressed, much of the effort towards proving the theorem was done along these lines, and it was finally in the year 1976 that Kenneth Appel, an Assistant Professor, and Wolfgang Haken, a visiting professor at the University of Illinois at Urbana-Champaign, finally proved the 4CT, having extensively used the computing resources available at the university. They had come up with a candidate set of 1,482 possible configurations and it took over twelve hundred hours of computing time on the university’s supercomputer to verify them all, one by one.
The proof of the 4CT was a watershed moment in the history of mathematics as it was the first major theorem that was proved using a computer. This raised serious philosophical questions at the time regarding what is a proof, and whether something that couldn’t be verified by hand could be trusted.
In addition, the proof’s brute-force method was also criticised for lacking beauty and being inelegant, something even Appel accepted.
Robin Wilson does a pretty good job of preparing the mathematical foundation for the important ideas linked with the proof that come up in the second half and there are ample diagrams to help the reader visualise the arguments that are being presented. In fact, I cannot remember reading any other science book with as high a ratio of diagrams to text.
The first one third of the book is a breezy read that the reader will sail through, and it is only when the ideas start to come together from this point on that the book demands attention and careful reading to connect the dots. The brute force nature of the proof means that the reader does lose context a few times when the details are being discussed but, thankfully, Wilson refers to earlier parts of the text at a few important stages of the book to help the reader align his thoughts vis-à-vis the path they have taken to reach the final proof. In fact, barring some brief sections that may be difficult to understand (which is natural, considering the historical significance of the problem), I believe most of the book can be understood, with some effort, even by high school students who are even slightly mathematically inclined.
All in all, Four Colours Suffice is a welcome addition to one’s library.