W. T. Tutte

William Thomas Tutte, OC, FRS, known as Bill Tutte, (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 had a significant impact on the Allied victory in Europe. He also had a number of significant mathematical accomplishments, including foundation work in the fields of combinatorics and graph theory.[1]

Early life and education

Tutte was born in Newmarket in Suffolk, the son of a gardener. At the age of 18, he studied chemistry and mathematics at Trinity College, Cambridge University. As a student he (along with three of his friends) became the first to solve the problem of squaring the square. Together the four created the pseudonym Blanche Descartes, under which Tutte published occasionally for years.
World War II

On the outbreak of World War II, his tutor suggested that he join the Government Code and Cypher School at Bletchley Park.

Originally rejected in interview by Alan Turing for a message-codebreaking team, he was recruited in May 1941 by John Tiltman for the research section, which actually turned out to be the best choice. Tutte's work there allowed him, from basic mathematical analysis, to deduce the structure of the German Lorenz SZ 40/42 encryption machine (codenamed Tunny), that was used for high-level German Army communications. On 30 August 1941, the German high command sent a single message twice (a "depth"), allowing Tiltman to break the message code by deducing the obscuring key. Tiltman then handed it and some other Tunny keys to Tutte, who after writing out by hand the original teleprinter 5-character Baudot code, made an initial breakthrough by recognising a 41-character repeat. Over the following two months, Tutte and other members of the Research section worked out the complete logical structure of the cipher machine. This achievement was later described as "one of the greatest intellectual feats of World War II".[2] Using his breakthrough, bulk Cryptanalysis of the Lorenz cipher became possible.

Because of this work, Canada's Communications Security Establishment named an internal organisation aimed at promoting research into cryptology, the Tutte Institute for Mathematics and Computing[3] (TIMC) in his honour in 2011.[4]
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 k-factors in graphs, and Hamiltonian and non-Hamiltonian graphs. He disproved Tait's conjecture using the construction known as Tutte's fragment. The eventual proof of the four color 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.

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.
Positions and award

He was a Fellow of the Royal Society of London, and of the Royal Society of Canada. In 2001 he was inducted as an Officer of the Order of Canada and won the CRM-Fields-PIMS prize.
Personal life and death

Tutte met his wife Dorothea in Canada, and decided hence to base himself there. 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.[5]
See also

BEST theorem
Tutte matrix
Tutte theorem
Tutte-Berge formula
Tutte graph, Tutte–Coxeter graph and Tutte 12-cage.
Systolic geometry

References

Brooks, R. L.; Smith, C. A. B.; Stone, A. H.; and Tutte, W. T. "The Dissection of Rectangles into Squares." Duke Math. J. 7, 312-340, 1940

^ Code-cracking machine returned to life, BBC News, 27 May 2011.
^ "The Lorenz Cipher and how Bletchley Park broke it". Codesandciphers.org.uk. 1941-08-30. Retrieved 2011-10-26.
^ The Tutte Institute for Mathematics and Computing. Canada.
^ Freeze, Colin (7 September 2011). "Top secret institute comes out of the shadows to recruit top talent". Globe and Mail (Toronto). Retrieved 7 September 2011.
^ Dan van der Vat (2002-07-05). "Obituary: William Tutte". London: The Guardian. Retrieved 2011-10-26.

External links

Professor William T. Tutte
Hobbs, Arthur; Oxley, James (March 2004), "William T. Tutte (1917-2002)" (PDF), Notices of the American Mathematical Society (Providence, RI: American Mathematical Society) 51 (3): 320–330, ISSN 1088-9477
W. T. Tutte at the Mathematics Genealogy Project
O'Connor, John J.; Robertson, Edmund F., "W. T. Tutte", MacTutor History of Mathematics archive, University of St Andrews.
William Tutte, 84, Mathematician and Code-breaker, Dies - Obituary from The New York Times
William Tutte: Unsung mathematical mastermind - Obituary from The Guardian
CRM-Fields-PIMS 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 CRM-Fields Prize
Tutte's paper on the Fish cipher
Tutte's disproof of Tait's conjecture