William T. Tutte
Groups
Additional Information
The following biographical sketch was written for the October 2002 issue of CMS Notes: W.T. Tutte (1917-2002). View the full William T. Tutte page to see additional information about Tutte and the impact he had on the world of mathematics.
Biography of Professor Tutte - (1917 - 2002)
William T. Tutte, Distinguished Professor Emeritus at the University of Waterloo, died May 2, 2002. The cause was congestive heart failure, complicated by lymphoma of the spleen, both diagnosed within six weeks of his death.
It was just a year previous, October 2001, that he was inducted as an Officer in the Order of Canada, in a ceremony held at Rideau Hall in Ottawa. The citation began "He is internationally renowned for his seminal work in the area of graph theory. As a young mathematician and codebreaker, he deciphered a series of German military encryption codes known as Fish". These two sentences speak to his place in history. His wartime codebreaking work, much emphasized in newspaper obituaries, was a secret by order of British security until 1993 and, indeed, is only described with detail in recent articles.
Beginnings
Bill Tutte was born May 14, 1917 at Fitzroy House in Newmarket, England. His father was the House gardener, his mother the caretaker. How he rose from this background to graduate from Trinity College, Cambridge, is as remarkable a chapter of his life as those that followed.
Fitzroy House is now, and was perhaps then, a horse racing stable. In Bill's first years, the family moved about with the vagaries of domestic employment until, when he was about three, they came to live in a house called Moorend, located high on the Yorkshire moor, in Aislaby, overlooking the Esk river, about three miles from Whitby and the east coast of England. His parents were the caretakers at Moorend. This is the place of first remembrances, where he first went to school. Then, only a few months after his beginning school, the family moved once again, back to the Newmarket area, to a little village Cheveley, three miles east of Newmarket centre. It so happens that the city of Cambridge lies fifteen miles to the west of Newmarket.
The family lived in a flint cottage, one half of a duplex, reached by a footpath adjacent to the 600 year old Anglican Church that dominates Cheveley. His father soon obtained the position of gardener at the Rutland Arms Hotel in Newmarket. This finally gave stability to family life: they lived in that cottage until his father's death in 1944.
Bill went to the village school, run by the Anglicans, from age six until eleven. He has spoken of the school as enlightened in its religious education and the possessor of a fine children's encyclopedia, which he frequently consulted. Aided by its contents, Bill developed a keen interest in astronomy.
He was a successful student: at age ten he took the scholarship examinations for secondary school. The schools in England were organized on a county basis and, through an ancient oddity of district boundaries, Cheveley lies in Cambridgeshire, even though Newmarket, in Suffolk, lies between Cheveley and the city of Cambridge. So when Tutte won a scholarship, it was to the distant school in Cambridge. Too distant, his parents judged, and he was kept at home. A year later he again took the examinations, with the same success. This time, at eleven, his parents took the headmaster's advice to enroll him at the Cambridge and County High School for Boys. It was to be for Bill a long daily commute, taking his bike into Newmarket and, if the weather was fair, on the further fifteen miles into Cambridge. Or, if it was foul, then take the train from Newmarket, with another mile's walk from the station at the far end.
In this school he further excelled in studies. A testament to this is a little shelf of books left in his office, each imprinted in gold on the cover with the school motto "Virtute et Fide" and with a plate inside inscribed by the headmaster. "Prize for Mathematics, Form VI", reads the inscription of "Shakespeare's Complete Works"; for "The Plays of John Galsworthy", it is "Prize for Chemistry, Form VI."
Trinity College
In 1935, he entered Trinity College, Cambridge. For his studies there he was, in his words, "adequately supported financially by a State Scholarship, a College Scholarship, and a grant from the County." As an undergraduate, Bill majored in chemistry. Indeed, he achieved First Class Honours therein, and went on to graduate study in that field. His first two publications describe experimental work in chemistry. But the evidence is clear that his primary interest, dating at least from his high school days, was in mathematics, though not perhaps in the fields most in vogue. From his first days at Cambridge, he participated regularly in the meetings of the Trinity Mathematical Society. There he met Cedric Smith, and then Leonard Brooks and Arthur Stone, like-minded undergraduates with whom he conducted researches in mathematics. They were mathematics majors; Bill formed a bond with these three that would remain close throughout their lives.
Not the first that they studied, but the one most remembered by history, was the problem of determining whether or not a square can be partitioned into smaller squares, all unequal in size. It arises from puzzle #40, Lady Isabel's Casket, in H.E. Dewdney's book "The Canterbury Puzzles".
It is, of course, not the puzzle but what they made of it that is remarkable. To begin they translated the problem to the language of electrical networks. In the 1940 paper that later described their work are formulas for electrical network functions, not just those found earlier by Kirchoff, but new ones for transfer functions. This paper became a standard reference for electrical network practitioners. The question of squaring the square, in electrical terms, became a study of rotational symmetry of a part of the network, and how reflection of the symmetric part can alter its currents without affecting potentials on its boundary. The level at which they conceived the problem is remarkably deep. Their method did succeed in finding partitions of squares into smaller unequal squares.
This was not the only memorable study that Tutte undertook in his initial period at Trinity, but the others were published later. For Tutte's academic career was put on hold by World War II.
Bletchley Park
In January 1941, upon invitation of his Tutor, Tutte went to Bletchley Park, the now legendary organization of code-breakers of Britain. It was later that year, in October, that Tutte encountered TUNNY, the first of a set of machine-ciphers named Fish. Now Fish is not Enigma. The Bletchley code-breakers, among whom Alan Turing was prominent, had had success in deciphering Enigma codes. But that success was with the naval and air force versions; the army version of Enigma proved to be resistant to analysis. That Bletchley could not read Army Enigma gave them incentive to attack Fish, which was used only by the Army. Moreover, Fish was used for high level communications between Berlin and the field commanders.
Tutte's great contribution was to uncover, from samples of the messages alone, the structure of the machines which generated these codes. This came about as follows. In August 1941, a German operator sent a Fish-enciphered teleprinter message of some 4000 letters from Athens to Berlin. For some reason, the message was not received properly and so it was resent. Against all guidelines, it was sent with the same setting. It was identical in content, but it differed slightly, in word spacing and punctuation. John Tiltman of Bletchley was able to use this blunder to find both the message and the obscuring string that was added to make up the enciphered message. But that seemed to be all that could be found, when Tutte was presented with the case in October.
Tutte began by observing the machine generated obscuring string carefully. Splitting it up into various lengths, he noticed signs of periodicity. For the first of the five teleprinter tape positions, the regularity he supposed arose from a wheel of 41 sprockets. And then at the last position, one of 23 sprockets. Over the next months, Tutte and colleagues worked out the complete internal structure, that it had twelve wheels, two for each of the five teleprinter positions, and two with an executive function. They determined the number of sprockets on each wheel, and how the advancement of the wheels was interrelated. They had completely recreated the machine without ever having seen one. Tony Sale, who first described this work in a 1997 article in New Scientist, characterized it as the "greatest intellectual feat of the whole war."
Knowing the structure of the enciphering machine is a necessity for code-breaking, but it is only the first step. Tutte then put himself to creating an algorithm to find from the enciphered messages the initial settings of the machine wheels. The algorithm that he created, the "Statistical Method", looked for certain types of resonances, but it had to consider far too many possibilities to be carried out by hand. So it was that, in 1943, the electronic computer COLOSSUS was designed and built by the British Post Office. It was to run the algorithms that Tutte; and his collaborators Max Newman and Ralph Tester; developed, that COLOSSUS was created. This man-machine combination was used to break Fish codes on a regular basis throughout the remainder of the War.
Acknowledgement from U.K. Prime Minister, David Cameron (PDF)
Resuming academic life
In late 1945, Tutte resumed his studies at Cambridge, now as a graduate student in mathematics. He published some work begun earlier, one a now famous paper that characterizes which graphs have a perfect matching, and another that constructs a non-Hamiltonian graph. He went on to create a ground-breaking PhD thesis, "An algebraic theory of graphs", in which he forges the subject now known as matroid theory.
Coming to Canada
Upon completing his degree, Tutte was invited by H.S.M. Coxeter to come to Canada, to join the Faculty of the University of Toronto. In his fourteen years at Toronto, beginning in 1948, he rose to preeminence in the field of combinatorics. One form of recognition in that period was his election as Fellow of the Royal Society of Canada.
It is difficult to describe in a summary way the many branches of research that Tutte pursued. Fortunately, Tutte has himself given such a summary, in his comments in the "Selected Papers of W.T. Tutte", published in 1979, and "Graph Theory as I have known it", in 1998. It is notable the degree to which these researches have their point of origin in squaring the square and matroids.
In 1962, Tutte joined the Faculty of the University of Waterloo. This was just five years after its creation. Tutte made a major contribution to establishing the identity and reputation of the University. His presence was a magnet for combinatorialists from all over the world. It was not only recognized stars of the field that came to Waterloo, but those of future prominence. Tutte was an important ingredient in the recipe that produced the Faculty of Mathematics in 1967, becoming one of the first members of the Department of Combinatorics and Optimization. He retired in 1985, but continued to be a significant member of the Faculty as Professor Emeritus. Until his retirement, he was Editor in Chief of the Journal of Combinatorial Theory.
Bill Tutte enjoyed hiking, and soon after his arrival in Canada became a member of the Canadian Youth Hostels Association. It was through the Hostel movement that he met Dorothea Mitchell, from Oakville: they were married in October 1949. Dorothea was lively and chatty, Bill more reserved in manner: they formed a lovely couple. When they moved to Waterloo, they lived out in the little village of West Montrose, just adjacent to the wooden covered bridge that is the signature of the region. Here the Tuttes managed an extensive garden, of mostly wild flora, on the banks of the Grand River. The neighbourhood is a pleasant place for hikes. Dorothea was an avid and skilled potter, well-known for her pivotal role in the founding of the Waterloo Potters workshop. For the Waterloo Combinatorics Conference of 1968, she made a personalized mug for each of the invited speakers, some thirty five in all. Dorothea died of cancer in 1994; they had no children.
Tutte's Impact
Paul Seymour of Princeton University writes:
Professor Tutte has been for many years the dominant figure in graph theory, and his contributions to the subject outweigh those of any other individual (in every sense except perhaps quantity). There are numerous instances when Tutte has found a beautiful result in a hitherto unexplored branch of graph theory, and in several cases this has been a ´breakthrough´, leading to the development of a major new subject.
Lászlo Lovász of Microsoft writes:
Few theorems in mathematics are honored by the general public by naming them after the mathematician who proved them. In Tutte's case, however, there are several such results: for somebody working in matching theory, Tutte's theorem is his characterization of graphs having a perfect matching - for a matroid theorist, it means his characterization of regular matroids - for somebody studying Hamiltonian cycles it means his result that 4-connected planar graphs have a Hamilton cycle. And there is also the Tutte polynomial of a graph (and a matroid), which is again a household word for many combinatorialists.
Tutte was a master of phrasing: here are some examples. To begin, there is the phrase "squaring the square". Next, the term "wheel" is an apt description of the structure that lies at the heart of his analysis of 3-connected graphs; its nongraphical analog in matroid theory is "whirl". The title of a seminar describing a fatal flaw he had found in a famous mathematician's paper on 3-colouring was "Et tu, Tut-té!" The title of his famous paper on the Reconstruction Conjecture for graphs is "All the king's horses". In his penetrating analysis and reformulation of the Birkhoff-Lewis equations, he declares some of those equations to be "of mysterious provenance." Finally, one of his last public lectures was "Sixty years in the nets."
Tutte was awarded the Tory Medal by the Royal Society of Canada in 1975. He won the Killam Prize in 1982. Last year he was awarded the CRC-Fields Institute Prize; receiving this became the occasion for two of his last public lectures, the one referred to above in Toronto, the other in Montreal.
In 1987 Tutte was named a Fellow of the Royal Society of London.
Dan Younger
August 2002