NY Times obituary
William Tutte, 84, Who Broke German Code
William Tutte, a theoretical mathematician who contributed substantially to breaking codes in World War II, died on May 2 in Kitchener-Waterloo, Ontario. He was 84.
The cause was congestive heart failure complicated by cancer of the spleen, the University of Waterloo announced. He was distinguished professor emeritus of combinatorics and optimization and honorary director of the university's Center for Cryptographic Research.
A chemistry graduate student at Cambridge in 1941, young Mr. Tutte was sent to the now-fabled Bletchley Park, where a secret code-breaking operation had been set up. There, applying solely his mind and logic, he deciphered a key part of the German military code that others, equipped with a model of the German Enigma encrypting machine, had failed to break.
After settling in Canada, he went to the fledgling University of Waterloo in 1962 and helped build its faculty of mathematics into a magnet for theoreticians and students alike. He became a leader in the evolution of combinatorics, the science of counting separate objects, which he first broached in his doctoral thesis more than 50 years ago.
William Tutte (pronounced tut) was born in Newmarket, Suffolk, near Cambridge. At Cambridge, he and several friends tackled a seemingly straightforward geometry problem: dividing a square into smaller squares. It is trivial to cut a square into four smaller, identical squares. But mathematicians had not figured out whether it was possible to cut a square into smaller squares where no two were the same size.
The Cambridge students not only showed that it is possible, but they also came up with an ingenious solution: they showed that the problem was equivalent to calculating the electrical resistance in a network of circuits. Throughout his career, he was able to perceive subtle connections that others might not even have thought to look for.
''He looks at it in a way which is totally more fundamental than you can imagine,'' said Dr. Daniel Younger, a professor of mathematics at the University of Waterloo.
His problem-solving ability was key to his code-breaking success.
When he joined the Enigma code-breakers, they had succeeded in reading the communications of the German Navy and Air Force. But the army version proved more elusive, particularly the machine-cipher FISH, used only by the army high command.
The code-breakers had one crucial piece of data. A German radio operator had sent the same message of about 4,000 letters twice, with only a few changes. That produces two long strands of gibberish, but gibberish that looked tantalizingly similar.
Examining them for four months, Mr. Tutte saw patterns in the seemingly random string of characters. One of the components of the message encoder, he deduced, was a wheel with exactly 41 sprockets. He also deduced that the first wheel was connected to a second wheel of 31 sprockets.
Together with other code-breakers, he figured out the structure of all 12 wheels of the encoding machine, without ever seeing the original German device.
Last October, when he was inducted as an Officer of the Order of Canada in Ottawa, the citation hailed that as ''one of the greatest intellectual feats of World War II.''
He returned to Cambridge and, switching to mathematics, received his doctorate in 1948. His thesis mixed combinatorics with the more abstract field of algebra and spun them into a new field of study called matroid theory.
Immediately after graduation, he began teaching at the University of Toronto, then moved to Waterloo, about 60 miles from Toronto.
One practical reason for the interest in combinatorics was the graph theory, in which graphs can serve as abstract models for many different kinds of relations among sets of varying objects. A simple example of graph theory is the four-color map problem, or determining how many colors are needed to color in the countries on a map so that no two countries of the same color touch. With the development of computer technology, graph theory has found uses in chemistry, physics, demographics, economics and other fields.
When mathematicians finally definitively proved in the 1970's that four colors are enough for any map to avoid two touching colors, they used methods pioneered by Dr. Tutte and another mathematician, Hassler Whitney.
''He was the leading mathematician in combinatorics for three decades,'' Dr. Younger said.
Dr. Tutte was editor in chief of The Journal of Combinatorial Theory in its early years and was on the editorial boards of several other research journals. He was a fellow of the Royal Society of Canada and the Royal Society of London.
He left no immediate survivors. His wife, Dorothea, died in 1994.
By WOLFGANG SAXON, May 10, 2002 © The New York Times Company