W. T. Tutte
Encyclopedia
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
code system, which had a significant impact on the Allied invasion of Europe. He also had a number of significant mathematical accomplishments, including foundation work in the fields of combinatorics
and graph theory
.
, 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.
, his tutor suggested he join the Government Code and Cypher School at Bletchley Park
.
Originally rejected in interview by Alan Turing
for a message code breaking team, he was recruited by John Tiltman for the research section in May 1941, 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 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". 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 (TIMC) in his honour in 2011.
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 group
s and regular matroids, about which he proved deep results.
. In 2001 he was inducted as an Officer of the Order of Canada
and won the CRM-Fields-PIMS prize
.
Order of Canada
The Order of Canada is a Canadian national order, admission into which is, within the system of orders, decorations, and medals of Canada, the second highest honour for merit...
, FRS
Royal Society
The Royal Society of London for Improving Natural Knowledge, known simply as the Royal Society, is a learned society for science, and is possibly the oldest such society in existence. Founded in November 1660, it was granted a Royal Charter by King Charles II as the "Royal Society of London"...
, known as Bill Tutte, (May 14, 1917 – May 2, 2002) was a British
United Kingdom
The United Kingdom of Great Britain and Northern IrelandIn the United Kingdom and Dependencies, other languages have been officially recognised as legitimate autochthonous languages under the European Charter for Regional or Minority Languages...
, later Canadian, codebreaker
Cryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
and mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
. During World War II
World War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
he made a brilliant and fundamental advance in Cryptanalysis of the Lorenz cipher
Cryptanalysis of the Lorenz cipher
Cryptanalysis of the Lorenz cipher was the process that enabled the British to read secret German military messages during World War II. The British Government Code and Cypher School at Bletchley Park decrypted many communications between the German High Command in Berlin and their army commands...
, a major German
Nazi Germany
Nazi Germany , also known as the Third Reich , but officially called German Reich from 1933 to 1943 and Greater German Reich from 26 June 1943 onward, is the name commonly used to refer to the state of Germany from 1933 to 1945, when it was a totalitarian dictatorship ruled by...
code system, which had a significant impact on the Allied invasion of Europe. He also had a number of significant mathematical accomplishments, including foundation work in the fields of combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
and graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
.
Early life and education
Tutte was born in Newmarket in SuffolkSuffolk
Suffolk is a non-metropolitan county of historic origin in East Anglia, England. It has borders with Norfolk to the north, Cambridgeshire to the west and Essex to the south. The North Sea lies to the east...
, the son of a gardener. At the age of 18, he studied chemistry
Chemistry
Chemistry is the science of matter, especially its chemical reactions, but also its composition, structure and properties. Chemistry is concerned with atoms and their interactions with other atoms, and particularly with the properties of chemical bonds....
and mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
at Trinity College
Trinity College, Cambridge
Trinity College is a constituent college of the University of Cambridge. Trinity has more members than any other college in Cambridge or Oxford, with around 700 undergraduates, 430 graduates, and over 170 Fellows...
, Cambridge University
University of Cambridge
The University of Cambridge is a public research university located in Cambridge, United Kingdom. It is the second-oldest university in both the United Kingdom and the English-speaking world , and the seventh-oldest globally...
. As a student he (along with three of his friends) became the first to solve the problem of squaring the square
Squaring the square
Squaring the square is the problem of tiling an integral square using only other integral squares. The name was coined in a humorous analogy with squaring the circle. Squaring the square is an easy task unless additional conditions are set...
. Together the four created the pseudonym Blanche Descartes
Blanche Descartes
Blanche Descartes was a collaborative pseudonym used by the English mathematicians R. Leonard Brooks, Arthur Harold Stone, Cedric Smith, and W. T. Tutte. The four mathematicians met in 1935 as undergraduate students at Trinity College, Cambridge, where they joined the Trinity Mathematical Society...
, under which Tutte published occasionally for years.
World War II
On the outbreak of World War IIWorld War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
, his tutor suggested he join the Government Code and Cypher School at Bletchley Park
Bletchley Park
Bletchley Park is an estate located in the town of Bletchley, in Buckinghamshire, England, which currently houses the National Museum of Computing...
.
Originally rejected in interview by Alan Turing
Alan Turing
Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
for a message code breaking team, he was recruited by John Tiltman for the research section in May 1941, 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 used for high-level German Army
Wehrmacht
The Wehrmacht – from , to defend and , the might/power) were the unified armed forces of Nazi Germany from 1935 to 1945. It consisted of the Heer , the Kriegsmarine and the Luftwaffe .-Origin and use of the term:...
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
Baudot code
The Baudot code, invented by Émile Baudot, is a character set predating EBCDIC and ASCII. It was the predecessor to the International Telegraph Alphabet No 2 , the teleprinter code in use until the advent of ASCII. Each character in the alphabet is represented by a series of bits, sent over a...
, 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". Using his breakthrough, bulk Cryptanalysis of the Lorenz cipher
Cryptanalysis of the Lorenz cipher
Cryptanalysis of the Lorenz cipher was the process that enabled the British to read secret German military messages during World War II. The British Government Code and Cypher School at Bletchley Park decrypted many communications between the German High Command in Berlin and their army commands...
became possible.
Because of this work, Canada's Communications Security Establishment
Communications Security Establishment
The Communications Security Establishment Canada is the Canadian government's national cryptologic agency. Administered under the Department of National Defence , it is charged with the duty of keeping track of foreign signals intelligence , and protecting Canadian government electronic...
named an internal organisation aimed at promoting research into cryptology, the Tutte Institute for Mathematics and Computing (TIMC) in his honour in 2011.
Doctorate and career
Tutte completed a doctorate in mathematics from CambridgeUniversity of Cambridge
The University of Cambridge is a public research university located in Cambridge, United Kingdom. It is the second-oldest university in both the United Kingdom and the English-speaking world , and the seventh-oldest globally...
in 1948 under the supervision of Shaun Wylie
Shaun Wylie
Shaun Wylie was a British mathematician and World War II codebreaker.-Early life:Wylie was born in Oxford, England, the fourth son of Sir Francis Wylie, later the first Warden of Rhodes House in Oxford. He was educated at Dragon School and then Winchester College...
, who had also worked at Bletchley Park on TUNNY. The same year, invited by Harold Scott MacDonald Coxeter
Harold Scott MacDonald Coxeter
Harold Scott MacDonald "Donald" Coxeter, was a British-born Canadian geometer. Coxeter is regarded as one of the great geometers of the 20th century. He was born in London but spent most of his life in Canada....
, he accepted a position at the University of Toronto
University of Toronto
The University of Toronto is a public research university in Toronto, Ontario, Canada, situated on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution of higher learning in Upper Canada...
. In 1962, he moved to the University of Waterloo
University of Waterloo
The University of Waterloo is a comprehensive public university in the city of Waterloo, Ontario, Canada. The school was founded in 1957 by Drs. Gerry Hagey and Ira G. Needles, and has since grown to an institution of more than 30,000 students, faculty, and staff...
in Waterloo
Waterloo, Ontario
Waterloo is a city in Southern Ontario, Canada. It is the smallest of the three cities in the Regional Municipality of Waterloo, and is adjacent to the city of Kitchener....
, Ontario
Ontario
Ontario is a province of Canada, located in east-central Canada. It is Canada's most populous province and second largest in total area. It is home to the nation's most populous city, Toronto, and the nation's capital, Ottawa....
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
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, especially graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, 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
Hamiltonian path
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle in an undirected graph that visits each vertex exactly once and also returns to the starting vertex...
and non-Hamiltonian graphs. He disproved Tait's conjecture
Tait's conjecture
In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle through all its vertices". It was proposed by and disproved by , who constructed a counterexample with 25 faces, 69 edges and 46 vertices...
using the construction known as Tutte's fragment. The eventual proof of the four color theorem
Four color theorem
In mathematics, the four color theorem, or the four color map theorem states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color...
made use of his earlier work. The graph polynomial he called the "dichromate" has become famous and influential under the name Tutte polynomial
Tutte polynomial
The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a polynomial in two variables which plays an important role in graph theory, a branch of mathematics and theoretical computer science...
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 group
Matroid
In combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
s 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 CanadaRoyal Society of Canada
The Royal Society of Canada , may also operate under the more descriptive name RSC: The Academies of Arts, Humanities and Sciences of Canada , is the oldest association of scientists and scholars in Canada...
. In 2001 he was inducted as an Officer of the Order of Canada
Order of Canada
The Order of Canada is a Canadian national order, admission into which is, within the system of orders, decorations, and medals of Canada, the second highest honour for merit...
and won the CRM-Fields-PIMS prize
CRM-Fields-PIMS prize
The CRM-Fields prize was given annually by the Centre de recherches mathématiques and the Fields Institute from 1994 to 2005. From 2006the Pacific Institute for the Mathematical Sciences joined the other two institutes awarding the prize, making the CRM-Fields-PIMS Prize.The prize is given for...
.
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.See also
- BEST theoremBEST theoremIn graph theory, a part of discrete mathematics, the BEST theorem gives a product formula for the number of Eulerian circuits in directed graphs. The name is an acronym of the names of people who discovered it: de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte.- Precise statement :Let...
- Tutte matrixTutte matrixIn graph theory, the Tutte matrix A of a graph G = is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once....
- Tutte theoremTutte theoremIn the mathematical discipline of graph theory the Tutte theorem, named after William Thomas Tutte, is a characterization of graphs with perfect matchings...
- Tutte-Berge formulaTutte-Berge formulaIn the mathematical discipline of graph theory the Tutte–Berge formula, named after William Thomas Tutte and Claude Berge, is a characterization of the size of a maximum matching in a graph...
- Tutte graphTutte graphIn the mathematical field of graph theory, the Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte. It has chromatic number 3, chromatic index 3, girth 4 and diameter 8....
, Tutte–Coxeter graph and Tutte 12-cageTutte 12-cageIn the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges named after W. T. Tutte....
. - Systolic geometry
External links
- Professor William T. Tutte
- William Tutte, 84, Mathematician and Code-breaker, Dies - Obituary from The New York TimesThe New York TimesThe New York Times is an American daily newspaper founded and continuously published in New York City since 1851. The New York Times has won 106 Pulitzer Prizes, the most of any news organization...
- William Tutte: Unsung mathematical mastermind - Obituary from The GuardianThe GuardianThe Guardian, formerly known as The Manchester Guardian , is a British national daily newspaper in the Berliner format...
- 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