W. T. Tutte
William Thomas Tutte OC FRS FRSC, known as Bill Tutte (/tʌt/; May 14, 1917 – May 2, 2002), was a British, later Canadian, codebreaker and mathematician. During World War II he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a major German cipher system, which was used for topsecret communications within the Wehrmacht High Command. The highlevel, strategic nature of the intelligence obtained from Tutte's breakthroughs in the bulk decrypting of Lorenzenciphered messages specifically, contributed significantly and perhaps even decisively, to the defeat of Nazi Germany.^{[2]}^{[3]} He also had a number of significant mathematical accomplishments, including foundation work in the fields of graph theory and matroid theory.^{[4]}^{[5]}
Tutte’s research in the field of graph theory proved to be of remarkable importance. At a time when graph theory was still a primitive subject, Tutte commenced the study of matroids and developed them into a theory by expanding from the work that Hassler Whitney had first developed around the mid 1930s.^{[6]} Even though Tutte’s contributions to graph theory have been influential to modern graph theory and many of his theorems have been used to keep making advances in the field, most of his terminology was not in agreement with their conventional usage and thus his terminology is not used by graph theorists today.^{[7]} "Tutte advanced graph theory from a subject with one text (D. König’s) toward its present extremely active state."^{[7]}
Contents
Early life and education
Tutte was born in Newmarket in Suffolk, the son of a gardener. He completed an undergraduate degree in chemistry at Trinity College, Cambridge with first class honours in 1938. He continued with physical chemistry as a graduate student, gaining an MSc in 1941, but transferred to mathematics at the end of 1940. As a student he (along with three of his friends) became one of the first to solve the problem of squaring the square, and the first to solve the problem without a squared subrectangle. Together the four created the pseudonym Blanche Descartes, under which Tutte published occasionally for years.^{[8]}
World War II
Soon after the outbreak of World War II, Tutte's tutor, Patrick Duff, suggested him for war work at the Government Code and Cypher School at Bletchley Park (BP). He was interviewed and sent on a training course in London before going to Bletchley Park, where he joined the Research Section. At first he worked on the Hagelin cipher that was being used by the Italian Navy. This was a rotor cipher machine that was available commercially, so the mechanics of enciphering was known, and decrypting messages only required working out how the machine was set up.^{[10]}
In the summer of 1941, Tutte was transferred to work on a teleprinter cipher system that had been dubbed "Tunny".^{[11]} Telegraphy used the 5bit International Telegraphy Alphabet No. 2 (ITA2). Other than that messages were preceded by a 12letter indicator, which implied a 12wheel rotor cipher machine, nothing was known about the mechanism of enciphering. The first step, therefore, had to be to diagnose the machine by establishing the logical structure and hence the functioning of the machine. Tutte played a pivotal role in achieving this, and it was not until shortly before the allied victory in Europe in 1945, that Bletchley Park acquired a Tunny Lorenz cipher machine.^{[12]} Tutte's breakthroughs led eventually to bulk decrypting of Tunnyenciphered messages between German High Command (OKW) in Berlin and their army commands throughout occupied Europe and contributed—perhaps decisively—to the defeat of Germany.^{[2]}^{[3]}
Diagnosing the cipher machine
On 31 August 1941, two versions of the same message were sent using identical keys which constituted a "depth". This allowed John Tiltman, Bletchley Park's veteran and remarkably gifted cryptanalyst, to deduce that it was a Vernam cipher which uses the Exclusive Or (XOR) function (symbolised by "⊕"), and to extract the two messages and hence obtain the obscuring key. After a fruitless period of Research Section cryptanalysts trying to work out how the Tunny machine worked, this and some other keys were handed to Tutte who was asked to "see what you can make of these".^{[13]}
At his training course, Tutte had been taught the Kasiski examination technique of writing out a key on squared paper, starting a new row after a defined number of characters that was suspected of being the frequency of repetition of the key.^{[14]} If this number was correct, the columns of the matrix would show more repetitions of sequences of characters than chance alone. Tutte knew that the Tunny indicators used 25 letters (excluding J) for 11 of the positions, but only 23 letters for the other. He therefore tried Kasiski's technique on the first impulse of the key characters, using a repetition of 25 × 23 = 575. He did not observe a large number of column repetitions with this period, but he did observe the phenomenon on a diagonal. He therefore tried again with 574, which showed up repeats in the columns. Recognising that the prime factors of this number are 2, 7 and 41, he tried again with a period of 41 and "got a rectangle of dots and crosses that was replete with repetitions".^{[15]}
It was clear, however, that the first impulse of the key was more complicated than that produced by a single wheel of 41 key impulses. Tutte called this component of the key _{1} (chi_{1}). He figured that there was another component, which was XORed with this, that did not always change with each new character, and that this was the product of a wheel that he called _{1} (psi_{1}). The same applied for each of the five impulses (_{1}_{2}_{3}_{4}_{5} and _{1}_{2}_{3}_{4}_{5}). So for a single character, the whole key K consisted of two components:



 K = ⊕


At Bletchley Park mark impulses were signified by x and space impulses by •.^{[16]} For example, the letter "H" would be coded as ••x•x.^{[17]} Tutte's derivation of the chi and psi components was made possible by the fact that dots were more likely than not to be followed by dots, and crosses more likely than not to be followed by crosses. This was a product of a weakness in the German key setting, which they later eliminated. Once Tutte had made this breakthrough, the rest of the Research Section joined in to study the other impulses, and it was established that the five chi wheels all advanced with each new character and that the five psi wheels all moved together under the control of two mu or "motor" wheels. Over the following two months, Tutte and other members of the Research Section worked out the complete logical structure of the machine with its set of wheels bearing cams that could either be in a position (raised) that added x to the stream of key characters, or in the alternative position that added in •.^{[18]}
Diagnosing the functioning of the Tunny machine in this way was a truly remarkable cryptanalytical achievement which, in the citation for Tutte's induction as an Officer of the Order of Canada, was described as:
one of the greatest intellectual feats of World War II^{[5]}
Tutte's statistical method
To decrypt a Tunny message required knowledge not only of the logical functioning of the machine, but the start positions of each rotor for the particular message. The search was on for a process that would manipulate the ciphertext or key to produce a frequency distribution of characters that departed from the uniformity that the enciphering process aimed to achieve. While on secondment to the Research Section in July 1942, Alan Turing worked out that the XOR combination of the values of successive characters in a stream of ciphertext and key, emphasised any departures from a uniform distribution. The resultant stream (symbolised by the Greek letter "delta" Δ) was called the difference because XOR is the same as modulo 2 subtraction.
The reason that this provided a way into Tunny was that although the frequency distribution of characters in the ciphertext could not be distinguished from a random stream, the same was not true for a version of the ciphertext from which the chi element of the key had been removed. This was the case because where the plaintext contained a repeated character and the psi wheels did not move on, the differenced psi character (Δ) would be the null character ('/ ' at Bletchley Park). When XORed with any character, this character has no effect. Repeated characters in the plaintext were more frequent both because of the characteristics of German (EE, TT, LL and SS are relatively common),^{[19]} and because telegraphists frequently repeated the figuresshift and lettersshift characters^{[20]} as their loss in an ordinary telegraph message could lead to gibberish.^{[21]}
To quote the General Report on Tunny:
Turingery introduced the principle that the key differenced at one, now called ΔΚ, could yield information unobtainable from ordinary key. This Δ principle was to be the fundamental basis of nearly all statistical methods of wheelbreaking and setting.^{[9]}
Tutte exploited this amplification of nonuniformity in the differenced values^{[22]} and by November 1942 had produced a way of discovering wheel starting points of the Tunny machine which became known as the "Statistical Method".^{[23]} The essence of this method was to find the initial settings of the chi component of the key by exhaustively trying all positions of its combination with the ciphertext, and looking for evidence of the nonuniformity that reflected the characteristics of the original plaintext.^{[24]}^{[25]} Because any repeated characters in the plaintext would always generate •, and similarly ∆_{1} ⊕ ∆_{2} would generate • whenever the psi wheels did not move on, and about half of the time when they did – some 70% overall.
As well as applying differencing to the full 5bit characters of the ITA2 code, Tutte applied it to the individual impulses (bits).^{[26]} The current chi wheel cam settings needed to have been established to allow the relevant sequence of characters of the chi wheels to be generated. It was totally impracticable to generate the 22 million characters from all five of the chi wheels, so it was initially limited to 41 × 31 = 1271 from the first two. After explaining his findings to Max Newman, Newman was given the job of developing an automated approach to comparing ciphertext and key to look for departures from randomness. The first machine was dubbed Heath Robinson but the much faster Colossus computer soon took over.^{[27]}
Doctorate and career
Tutte completed a doctorate in mathematics from Cambridge in 1948 under the supervision of Shaun Wylie, who had also worked at Bletchley Park on Tunny. The same year, invited by Harold Scott MacDonald Coxeter, he accepted a position at the University of Toronto. In 1962, he moved to the University of Waterloo in Waterloo, Ontario, where he stayed for the rest of his academic career. He officially retired in 1985 but remained active as an emeritus professor. Tutte was instrumental in helping to found the Department of Combinatorics and Optimization at the University of Waterloo.
His mathematical career concentrated on combinatorics, especially graph theory, which he is credited as having helped create in its modern form, and matroid theory, to which he made profound contributions; one colleague described him as "the leading mathematician in combinatorics for three decades". He was editor in chief of The Journal of Combinatorial Theory when it was started, and served on the editorial boards of several other mathematical research journals.
His work in graph theory includes the structure of cycle and cut spaces, size of maximum matchings and existence of kfactors in graphs, and Hamiltonian and nonHamiltonian graphs. He disproved Tait's conjecture using the construction known as Tutte's fragment. The eventual proof of the four colour theorem made use of his earlier work. The graph polynomial he called the "dichromate" has become famous and influential under the name Tutte polynomial and serves as the prototype of combinatorial invariants that are universal for all invariants that satisfy a specified reduction law.
The first major advances in matroid theory were made by Tutte in his 1948 Cambridge Ph.D. thesis which formed the basis of an important sequence of papers published over the next two decades. Tutte's work in graph theory and matroid theory has been profoundly influential on the development of both the content and direction of these two fields.^{[7]} In matroid theory he discovered the highly sophisticated homotopy theorem as well as founding the studies of chain groups and regular matroids, about which he proved deep results.
In addition, Tutte developed an algorithm for determining whether a given binary matroid is graphic. The algorithm makes use of the fact that a planar graph is simply a graph whose circuitmatroid, the dual of its bondmatroid, is graphic.^{[28]}
Tutte wrote a paper entitled How to Draw a Graph in which he proves that any face in a 3connected graph is enclosed by a peripheral cycle. Using this fact, Tutte developed an alternative proof to show that every Kuratowski graph is nonplanar by showing thatK_{5} and K_{3,3} each have three distinct peripheral cycles with a common edge. In addition to using peripheral cycles to prove that the Kuratowski graphs are nonplanar, Tutte proved that there exists a convex embedding of any simple 3connected graph and devised an algorithm which constructs the plane drawing by solving a linear system. This algorithm makes use of the barycentric mappings of the peripheral circuits of a simple 3connected graph.^{[29]} The findings published in this paper have proved to be of much significance because the algorithms that Tutte developed have become popular planar graph drawing methods. In 1997, Michael S. Floater published a paper entitled Parameterization and smooth approximation of surface triangulations which extends Tutte’s original theorem on the existence of a plane drawing of a 3connected graph bounded by a convex polygon. Floater shows that a plane drawing of a 3connected graph can be drawn without the boundary necessarily being a convex polygon.^{[30]}
One of the reasons for which Tutte’s embedding is popular is that the necessary computations that are carried out by his algorithms are simple and guarantee a onetoone correspondence of a graph and its embedding onto the Euclidean plane which is of importance when parameterizing a threedimensional mesh to the plane in geometric modeling. “Tutte's theorem is the basis for solutions to other computer graphics problems, such as morphing^{[31]}
Tutte was mainly responsible for developing the theory of enumeration of planar graphs, which has close links with chromatic and dichromatic polynomials. This work involved some highly innovative techniques of his own invention, requiring considerable manipulative dexterity in handling power series (whose coefficients count appropriate kinds of graphs) and the functions arising as their sums, as well as geometrical dexterity in extracting these power series from the graphtheoretic situation.^{[32]}
Positions, honours and awards
Tutte's work in WW2 and subsequently in combinatorics brought him various positions, honours and awards:
 1958, Fellow of the Royal Society of Canada (FRSC);
 1971, JefferyWilliams Prize by the Canadian Mathematical Society;
 1975, Henry Marshall Tory Medal by the Royal Society of Canada;
 1977, A conference on Graph Theory and Related Topics was held at the University of Waterloo in his honour on the occasion of his sixtieth birthday;
 1982, IsaakWaltonKillam Award by the Canada Council;
 1987, Fellow of the Royal Society (FRS);
 19901996, First President of the Institute of Combinatorics and its Applications;^{[33]}
 1998, Appointed honorary director of the Centre for Applied Cryptographic Research at the University of Waterloo;^{[34]}
 2001, Officer of the Order of Canada (OC);
 2001, CRMFieldsPIMS prize.
Tutte served as Librarian for the Royal Astronomical Society of Canada in 19591960, and asteroid 14989 Tutte (1997 UB7) was named after him.^{[35]}
Because of Tutte's work at Bletchley Park, Canada's Communications Security Establishment named an internal organisation aimed at promoting research into cryptology, the Tutte Institute for Mathematics and Computing (TIMC), in his honour in 2011. ^{[36]}
In September 2014, Tutte was celebrated in his hometown of Newmarket, England, with the unveiling of a sculpture, after a local newspaper started a campaign to honour his memory.^{[37]}
Personal life and death
The opportunity to work at the University of Waterloo appealed to Tutte because it offered the possibility of advancement. It also happened that both William and Dorothea enjoyed natural settings and the overall rural environment that was offered by Waterloo was of interest to Tutte and his wife. Tutte accepted the position and he and Dorothea bought a house in the nearby village of West Montrose, Ontario. Both Bill and Dorothea enjoyed spending time in their garden and allowing others to enjoy the beautiful scenery that was contained within their property. They also had an extensive knowledge of all the birds in their garden, they could name every bird they encountered. Dorothea was a keen hiker and Bill organized hiking trips. Even near the end of his life Bill still was an avid walker, he could outwalk colleagues 20 years younger.^{[7]}^{[38]} After his wife died in 1994, he returned to live in Newmarket, but then returned to Waterloo in 2000, where he died two years later.^{[39]} He is buried in West Montrose United Cemetery.^{[40]}
Books
 Tutte, W. T. (1966), Connectivity in graphs, Mathematical expositions, 15, Toronto, Ontario: University of Toronto Press, Zbl 0146.45603
 Tutte, W. T. (1966), Introduction to the theory of matroids, Santa Monica, Calif.: RAND Corporation report R446PR. Also Tutte, W. T. (1971), Introduction to the theory of matroids, Modern analytic and computational methods in science and mathematics, 37, New York: American Elsevier Publishing Company, ISBN 9780444000965, Zbl 0231.05027
 Tutte, W. T., ed. (1969), Recent progress in combinatorics. Proceedings of the third Waterloo conference on combinatorics, May 1968, New YorkLondon: Academic Press, pp. xiv+347, ISBN 9780127051505, Zbl 0192.33101
 Tutte, W. T. (1979), McCarthy, D.; Stanton, R. G., eds., Selected papers of W.T. Tutte, Vols. I, II., Winnipeg, Manitoba: Charles Babbage Research Centre, St. Pierre, Manitoba, Canada, pp. xxi+879, Zbl 0403.05028
 Volume I: ISBN 9780969077817
 Volume II: ISBN 9780969077824
 Tutte, W. T. (1984), Graph theory, Encyclopedia of mathematics and its applications, 21, Menlo Park, California: AddisonWesley Publishing Company, ISBN 9780201135206, Zbl 0554.05001 Reprinted by Cambridge University Press 2001, ISBN 9780521794893
 Tutte, W. T. (1998), Graph theory as I have known it, Oxford lecture series in mathematics and its applications, 11, Oxford: Clarendon Press, ISBN 9780198502517, Zbl 0915.05041 Reprinted 2012, ISBN 9780199660551
See also
References
 ↑ ^{1.0} ^{1.1} ^{1.2} W. T. Tutte at the Mathematics Genealogy Project
 ↑ ^{2.0} ^{2.1} Hinsley 1993, p. 8
 ↑ ^{3.0} ^{3.1} (Brzezinski 2005, p. 18)
 ↑ Younger 2012
 ↑ ^{5.0} ^{5.1} O'Connor & Robertson 2003
 ↑ Johnson, Will. "Matroids" (PDF). Retrieved 16 October 2014.
 ↑ ^{7.0} ^{7.1} ^{7.2} ^{7.3} Hobbs, Arthur M.; James G. Oxley (March 2004). "William T. Tutte (1917–2002)" (PDF). Notices of the American Mathematical Society. 51 (3): 322.
 ↑ Smith, Cedric A. B.; Abbott, Steve (March 2003), "The Story of Blanche Descartes", The Mathematical Gazette, 87 (508): 23–33, ISSN 00255572, JSTOR 3620560
 ↑ ^{9.0} ^{9.1} Good, Michie & Timms 1945, p. 6 in 1. Introduction: German Tunny
 ↑ Tutte 2006, pp. 352–353
 ↑ Tutte 2006, p. 355
 ↑ Sale, Tony, The Lorenz Cipher and how Bletchley Park broke it, retrieved 21 October 2010
 ↑ Tutte 2006, p. 354
 ↑ Bauer 2006, p. 375
 ↑ Tutte 2006, pp. 356–357
 ↑ In more recent terminology, each impulse would be termed a "bit" with a mark being binary 1 and a space being binary 0. Punched paper tape had a hole for a mark and no hole for a space.
 ↑ Copeland 2006, pp. 348, 349
 ↑ Tutte 2006, p. 357
 ↑ Singh, Simon, The Black Chamber, retrieved 28 April 2012
 ↑ Newman c. 1944 p. 387
 ↑ Carter 2004, p. 3
 ↑ For this reason Tutte's 1 + 2 method is sometimes called the "double delta" method.
 ↑ Tutte 1998, pp. 7–8
 ↑ Good, Michie & Timms 1945, pp. 321–322 in 44. Hand Statistical Methods: Setting  Statistical Methods
 ↑ Budiansky 2006, pp. 58–59
 ↑ The five impulses or bits of the coded characters are sometimes referred to as five levels.
 ↑ Copeland 2011
 ↑ W.T Tutte. An algorithm for determining whether a given binary matroid is graphic, Proceedings of the London Mathematical Society, 11(1960)905917
 ↑ W.T. Tutte. How to draw a graph. Proceedings of the London Mathematical Society, 13(3):743768, 1963.
 ↑ M.S. Floater. Parameterization and smooth approximation of surface triangulations. Computer Aided Geometric Design, 14:231–250, 1997.
 ↑ Steven J. Gortle; Craig Gotsman; Dylan Thurston. Discrete OneForms on Meshes and Applications to 3D Mesh Parameterization, Computer Aided Geometric Design, 23(2006)83112
 ↑ C. St. J. A. NashWilliams, A Note on Some of Professor Tutte's Mathematical Work, Graph Theory and Related Topics (eds. J.A Bondy and U. S. R Murty), Academic Press, New York, 1979, p. xxvii.
 ↑ "The Institute of Combinatorics & Its Applications". ICA. Retrieved 28 September 2013.
 ↑ "Tutte honoured by cryptographic centre". University of Waterloo. Retrieved 28 September 2013.
 ↑ "Asteroid (14989) Tutte". Royal Astronomical Society of Canada. 14 June 2011. Retrieved 25 September 2014.
 ↑ Freeze, Colin (7 September 2011). "Top secret institute comes out of the shadows to recruit top talent". Globe and Mail. Toronto. Retrieved 25 September 2014.
 ↑ "The Bill Tutte Memorial". Bill Tutte Memorial Fund. Retrieved 13 December 2014.
 ↑ "Bill Tutte". Telegraph Group Limited.
 ↑ van der Vat, Dan (10 May 2002), Obituary: William Tutte, London: The Guardian, retrieved 28 April 2013
 ↑ http://geneofun.on.ca/names/photo/858001
Sources
 Bauer, Friedrich L. (2006), The Tiltman Break Appendix 5 in Copeland 2006, pp. 370–377
 Copeland, B. Jack, ed. (2006), Colossus: The Secrets of Bletchley Park's Codebreaking Computers, Oxford: Oxford University Press, ISBN 9780192840554
 Copeland, B. Jack, Colossus and the Dawning of the Computer Age in Erskine & Smith 2011, pp. 305–327
 Erskine, Ralph; Smith, Michael, eds. (2011) [2001], The Bletchley Park Codebreakers, Biteback Publishing Ltd, ISBN 9781849540780 Updated and extended version of Action This Day: From Breaking of the Enigma Code to the Birth of the Modern Computer Bantam Press 2001
 Good, Jack; Michie, Donald; Timms, Geoffrey (1945), General Report on Tunny: With Emphasis on Statistical Methods, UK Public Record Office HW 25/4 and HW 25/5, retrieved 15 September 2010 That version is a facsimile copy, but there is a transcript of much of this document in '.pdf' format at: Sale, Tony (2001), Part of the "General Report on Tunny", the Newmanry History, formatted by Tony Sale (PDF), retrieved 20 September 2010, and a web transcript of Part 1 at: Ellsbury, Graham, General Report on Tunny With Emphasis on Statistical Methods, retrieved 3 November 2010
 Good, Jack (1993), Enigma and Fish in Hinsley & Stripp 1993, pp. 149–166
 Hinsley, F.H.; Stripp, Alan, eds. (1993) [1992], Codebreakers: The inside story of Bletchley Park, Oxford: Oxford University Press, ISBN 9780192801326
 O'Connor, J J; Robertson, E F (2003), MacTutor Biography: William Thomas Tutte, University of St Andrews, retrieved 28 April 2013
 Tutte, W. T. (19 June 1998), Fish and I (PDF), retrieved 7 April 2012 Transcript of a lecture given by Prof. Tutte at the University of Waterloo
 Tutte, William T. (2006), My Work at Bletchley Park Appendix 4 in Copeland 2006, pp. 352–369
 Ward, Mark (27 May 2011), Codecracking machine returned to life, BBC News, retrieved 28 April 2013
 Younger, D. H. (2012), Biographical Memoirs of Fellows of the Royal Society: William Thomas Tutte. 14 May 1917 — 2 May 2002, The Royal Society, doi:10.1098/rsbm.2012.0036, retrieved 28 April 2013
External links
 Brooks, R. L.; Smith, C. A. B.; Stone, A. H.; Tutte, W. T. (1940). "The Dissection of Rectangles into Squares". Duke Math. J. 7: 312–340. doi:10.1215/s0012709440007189.
 Professor William T. Tutte
 Hobbs, Arthur; Oxley, James (March 2004), "William T. Tutte (19172002)" (PDF), Notices of the American Mathematical Society, Providence, RI: American Mathematical Society, 51 (3): 320–330, ISSN 10889477
 W. T. Tutte at the Mathematics Genealogy Project
 William Tutte, 84, Mathematician and Codebreaker, Dies  Obituary from The New York Times
 William Tutte: Unsung mathematical mastermind  Obituary from The Guardian
 CRMFieldsPIMS Prize  2001  William T. Tutte
 "60 Years in the Nets"  a lecture (audio recording) given at the Fields Institute on October 25, 2001 to mark the receipt of the 2001 CRMFields Prize
 Tutte's paper on the Fish cipher
 Tutte's disproof of Tait's conjecture
 "Bletchley's forgotten heroes", Ian Douglas, The Telegraph, 25 December 2012
 1917 births
 2002 deaths
 People from Newmarket, Suffolk
 Alumni of Trinity College, Cambridge
 People associated with Bletchley Park
 British cryptographers
 Ciphermachine cryptographers
 English mathematicians
 Canadian mathematicians
 20thcentury mathematicians
 Graph theorists
 Graph drawing people
 Combinatorialists
 University of Toronto faculty
 University of Waterloo faculty
 Officers of the Order of Canada
 British expatriate academics in Canada
 Fellows of the Royal Society
 Fellows of the Royal Society of Canada