Fermat's Last Theorem

by Simon Singh

  Gödel’s work, compounded by Cohen’s undecidable statements, sent a disturbing message to all those mathematicians, professional and amateur, who were persisting in their attempts to prove Fermat’s Last Theorem – perhaps Fermat’s Last Theorem was undecidable! What if Pierre de Fermat had made a mistake when he claimed to have found a proof? If so, then there was the possibility that the Last Theorem was undecidable. Proving Fermat’s Last Theorem might be more than just difficult, it might be impossible. If Fermat’s Last Theorem were undecidable, then mathematicians had spent centuries in search of a proof that did not exist.

  Curiously if Fermat’s Last Theorem turned out to be undecidable, then this would imply that it must be true. The reason is as follows. The Last Theorem says that there are no whole number solutions to the equation

  If the Last Theorem were in fact false, then it would be possible to prove this by identifying a solution (a counter-example). Therefore the Last Theorem would be decidable. Being false would be inconsistent with being undecidable. However, if the Last Theorem were true, there would not necessarily be such an unequivocal way of proving it so, i.e. it could be undecidable. In conclusion, Fermat’s Last Theorem might be true, but there may be no way of proving it.

  The Compulsion of Curiosity

  Pierre de Fermat’s casual jotting in the margin of Diophantus’ Arithmetica had led to the most infuriating riddle in history. Despite three centuries of glorious failure and Gödel’s suggestion that they might be hunting for a non-existent proof, some mathematicians continued to be attracted to the problem. The Last Theorem was a mathematical siren, luring geniuses towards it, only to dash their hopes. Any mathematician who got involved with Fermat’s Last Theorem risked wasting their career, and yet whoever could make the crucial breakthrough would go down in history as having solved the world’s most difficult problem.

  Generations of mathematicians were obsessed with Fermat’s Last Theorem for two reasons. First, there was the ruthless sense of one-upmanship. The Last Theorem was the ultimate test and whoever could prove it would succeed where Cauchy, Euler, Kummer, and countless others had failed. Just as Fermat himself took great pleasure in solving problems which baffled his contemporaries, whoever could prove the Last Theorem could enjoy the fact that they had solved a problem which had confounded the entire community of mathematicians for hundreds of years. Second, whoever could meet Fermat’s challenge could enjoy the innocent satisfaction of solving a riddle. The delight derived from solving esoteric questions in number theory is not so different from the simple joy of tackling the trivial riddles of Sam Loyd. A mathematician once said to me that the pleasure he derived from solving mathematical problems is similar to that gained by crossword addicts. Filling in the last clue of a particularly tough crossword is always a satisfying experience, but imagine the sense of achievement after spending years on a puzzle, which nobody else in the world has been able to solve, and then figuring out the solution.

  These are the same reasons why Andrew Wiles became fascinated by Fermat: ‘Pure mathematicians just love a challenge. They love unsolved problems. When doing maths there’s this great feeling. You start with a problem that just mystifies you. You can’t understand it, it’s so complicated, you just can’t make head nor tail of it. But then when you finally resolve it, you have this incredible feeling of how beautiful it is, how it all fits together so elegantly. Most deceptive are the problems which look easy, and yet they turn out to be extremely intricate. Fermat is the most beautiful example of this. It just looked as though it had to have a solution and, of course, it’s very special because Fermat said that he had a solution.’

  Mathematics has its applications in science and technology, but that is not what drives mathematicians. They are inspired by the joy of discovery. G.H. Hardy tried to explain and justify his own career in a book entitled A Mathematician’s Apology:

  I will only say that if a chess problem is, in the crude sense, ‘useless’, then that is equally true of most of the best mathematics … I have never done anything ‘useful’. No discovery of mine has made, or is likely to make, directly or indirectly, for good or ill, the least difference to the amenity of the world. Judged by all practical standards, the value of my mathematical life is nil; and outside mathematics it is trivial anyhow. I have just one chance of escaping a verdict of complete triviality, that I may be judged to have created something worth creating. And that I have created something is undeniable: the question is about its value.

  The desire for a solution to any mathematical problem is largely fired by curiosity, and the reward is the simple but enormous satisfaction derived from solving any riddle. The mathematician E.C. Titchmarsh once said: ‘It can be of no practical use to know that π is irrational, but if we can know, it surely would be intolerable not to know.’

  In the case of Fermat’s Last Theorem there was no shortage of curiosity. Gödel’s work on undecidability had introduced an element of doubt as to whether the problem was soluble, but this was not enough to discourage the true Fermat fanatic. What was more dispiriting was the fact that by the 1930s mathematicians had exhausted all their techniques and had little else at their disposal. What was needed was a new tool, something that would raise mathematical morale. The Second World War was to provide just what was required – the greatest leap in calculating power since the invention of the slide-rule.

  The Brute Force Approach

  When in 1940 G.H. Hardy declared that the best mathematics is largely useless, he was quick to add that this was not necessarily a bad thing: ‘Real mathematics has no effects on war. No one has yet discovered any warlike purpose to be served by the theory of numbers.’ Hardy was soon to be proved wrong.

  In 1944 John von Neumann co-wrote the book The Theory of Games and Economic Behavior, in which he coined the term game theory. Game theory was von Neumann’s attempt to use mathematics to describe the structure of games and how humans play them. He began by studying chess and poker, and then went on to try and model more sophisticated games such as economics. After the Second World War the RAND corporation realised the potential of von Neumann’s ideas and hired him to work on developing Cold War strategies. From that point on, mathematical game theory has become a basic tool for generals to test their military-strategies by treating battles as complex games of chess. A simple illustration of the application of game theory in battles is the story of the truel.

  A truel is similar to a duel, except there are three participants rather than two. One morning Mr Black, Mr Grey and Mr White decide to resolve a conflict by truelling with pistols until only one of them survives. Mr Black is the worst shot, hitting his target on average only one time in three. Mr Grey is a better shot hitting his target two times out of three. Mr White is the best shot hitting his target every time. To make the truel fairer Mr Black is allowed to shoot first, followed by Mr Grey (if he is still alive), followed by Mr White (if he is still alive), and round again until only one of them is alive. The question is this: Where should Mr Black aim his first shot? You might like to make a guess based on intuition, or better still based on game theory. The answer is discussed in Appendix 9.

  Even more influential in wartime than game theory is the mathematics of code breaking. During the Second World War the Allies realised that in theory mathematical logic could be used to unscramble German messages, if only the calculations could be performed quickly enough. The challenge was to find a way of automating mathematics so that a machine could perform the calculations, and the Englishman who contributed most to this code-cracking effort was Alan Turing.

  In 1938 Turing returned to Cambridge having completed a stint at Princeton University. He had witnessed first-hand the turmoil caused by Gödel’s theorems of undecidability and had become involved in trying to pick up the pieces of Hilbert’s dream. In particular he wanted to know if there was a way to define which questions were and were not decidable, and tried to develop a methodical way of answering this question. At the time calculating devi
ces were primitive and effectively useless when it came to serious mathematics, and so instead Turing based his ideas on the concept of an imaginary machine which was capable of infinite computation. This hypothetical machine, which consumed infinite amounts of imaginary ticker-tape and could compute for an eternity, was all that he required to explore his abstract questions of logic. What Turing was unaware of was that his imagined mechanisation of hypothetical questions would eventually lead to a breakthrough in performing real calculations on real machines.

  Despite the outbreak of war, Turing continued his research as a fellow of King’s College, until on 4 September 1939 his contented life as a Cambridge don came to an abrupt end. He had been commandeered by the Government Code and Cypher School, whose task it was to unscramble the enemy’s coded messages. Prior to the war the Germans had devoted considerable effort to developing a superior system of encryption, and this was a matter of grave concern to British Intelligence who had in the past been able to decipher their enemy’s communications with relative ease. The HMSO’s official war history British Intelligence in the Second World War describes the state of play in the 1930s:

  By 1937 it was established that, unlike their Japanese and Italian counterparts, the German army, the German navy and probably the air force, together with other state organisations like the railways and the SS used, for all except their tactical communications, different versions of the same cypher system – the Enigma machine which had been put on the market in the 1920s but which the Germans had rendered more secure by progressive modifications. In 1937 the Government Code and Cypher School broke into the less modified and less secure model of this machine that was being used by the Germans, the Italians and the Spanish nationalist forces. But apart from this the Enigma still resisted attack, and it seemed likely that it would continue to do so.

  The Enigma machine consisted of a keyboard connected to a scrambler unit. The scrambler unit contained three separate rotors and the positions of the rotors determined how each letter on the keyboard would be enciphered. What made the Enigma code so difficult to crack was the enormous number of ways in which the machine could be set up. First, the three rotors in the machine were chosen from a selection of five, and could be changed and swapped around to confuse the code-breakers. Second, each rotor could be positioned in one of twenty-six different ways. This means that the machine could be set up in over a million different ways. In addition to the permutations provided by the rotors, plugboard connections at the back of the machine could be changed by hand to provide a total of over 150 million million million possible setups. To increase security even further, the three rotors were continually changing their orientation, so that every time a letter was transmitted, the set-up for the machine, and therefore the encipherment, would change for the next letter. So typing ‘DODO’ could generate the message ‘FGTB’ – the ‘D’ and the ‘O’ are sent twice, but encoded differently each time.

  Enigma machines were given to the German army, navy and air force, and were even operated by the railways and other government departments. As with all code systems used during this period, a weakness of the Enigma was that the receiver had to know the sender’s Enigma setting. To maintain security the Enigma settings had to be changed on a daily basis. One way for senders to change settings regularly and keep receivers informed was to publish the daily settings in a secret code-book. The risk with this approach was that the British might capture a U-boat and obtain the code-book with all the daily settings for the following month. The alternative approach, and the one adopted for the bulk of the war, was to transmit the daily settings in a preamble to the actual message, encoded using the previous day’s settings.

  When the war started, the British Cypher School was dominated by classicists and linguists. The Foreign Office soon realised that number theorists had a better chance of finding the key to cracking the German codes and, to begin with, nine of Britain’s most brilliant number theorists were gathered at the Cypher School’s new home at Bletchley Park, a Victorian mansion in Bletchley, Buckinghamshire. Turing had to abandon his hypothetical machines with infinite ticker-tape and endless processing time and come to terms with a practical problem with finite resources and a very real deadline.

  Cryptography is an intellectual battle between the code-maker and the code-breaker. The challenge for the code-maker is to shuffle and scramble an outgoing message to the point where it would be indecipherable if intercepted by the enemy. However, there is a limit on the amount of mathematical manipulation possible because of the need to dispatch messages quickly and efficiently. The strength of the German Enigma code was that the coded message underwent several levels of encryption at very high speed. The challenge for the code-breaker was to take an intercepted message and to crack the code while the contents of the message were still relevant. A German message ordering a British ship to be destroyed had to be decoded before the ship was sunk.

  Turing led a team of mathematicians who attempted to build mirror-images of the Enigma machine. Turing incorporated his pre-war abstract ideas into these devices, which could in theory methodically check all the possible Enigma machine set-ups until the code was cracked. The British machines, over two metres tall and equally wide, employed electromechanical relays to check all the potential Enigma settings. The constant ticking of the relays led to them being nicknamed bombes. Despite their speed it was impossible for the bombes to check every one of the 150 million million million possible Enigma settings within a reasonable amount of time, and so Turing’s team had to find ways to significantly reduce the number of permutations by gleaning whatever information they could from the sent messages.

  One of the greatest breakthroughs made by the British was the realisation that the Enigma machine could never encode a letter into itself, i.e. if the sender tapped ‘R’ then the machine could potentially send out any letter, depending on the settings of the machine, apart from ‘R’. This apparently innocuous fact was all that was needed to drastically reduce the time required to decipher a message. The Germans fought back by limiting the length of the messages they sent. All messages inevitably contain clues for the team of code-breakers, and the longer the message, the more clues it contains. By limiting all messages to a maximum of 250 letters, the Germans hoped to compensate for the Enigma machine’s reluctance to encode a letter as itself.

  In order to crack codes Turing would often try to guess keywords in messages. If he was right it would speed up enormously the cracking of the rest of the code. For example, if the code-breakers suspected that a message contained a weather report, a frequent type of coded report, then they would guess that the message contained words such as ‘fog’ or ‘windspeed’. If they were right they could quickly crack that message, and thereby deduce the Enigma settings for that day. For the rest of the day, other, more valuable, messages could be broken with ease.

  When they failed to guess weather words, the British would try and put themselves in the position of the German Enigma operators to guess other keywords. A sloppy operator might address the receiver by a first name or he might have developed idiosyncrasies which were known to the code-breakers. When all else failed and German traffic was flowing unchecked, it is said that the British Cypher School even resorted to asking the RAF to mine a particular German harbour. Immediately the German harbour-master would send an encrypted message which would be intercepted by the British. The code-breakers could be confident that the message contained words like ‘mine’, ‘avoid’ and ‘map reference’. Having cracked this message, Turing would have that day’s Enigma settings and any further German traffic was vulnerable to rapid decipherment.

  On 1 February 1942 the Germans added a fourth wheel to Enigma machines which were employed for sending particularly sensitive information. This was the greatest escalation in the level of encryption during the war, but eventually Turing’s team fought back by increasing the efficiency of the bombes. Thanks to the Cypher School, the Allies knew more about their enemy than th
e Germans could ever have suspected. The impact of German U-boats in the Atlantic was greatly reduced and the British had advanced warning of attacks by the Luftwaffe. The code-breakers also intercepted and deciphered the exact position of German supply ships, allowing British destroyers to be sent out to sink them.

  At all times the Allied forces had to take care that their evasive actions and uncanny attacks did not betray their ability to decipher German communications. If the Germans suspected that Enigma had been broken then they would increase their level of encryption, and the British might be back to square one. Hence there were occasions when the Cypher School informed the Allies of an imminent attack, and the Allies chose not to take extreme countermeasures. There are even rumours that Churchill knew that Coventry was to be targeted for a devastating raid, yet he chose not to take special precautions in case the Germans became suspicious. Stuart Milner-Barry who worked with Turing denies the rumour, and states that the relevant message concerning Coventry was not cracked until it was too late.