Remembering Bill Tutte

One of the greatest mathematicians and codebreakers of the 20th century, William (Bill) Tutte, was born a century ago on Sunday, May 14, 2017.

His wartime work enabled the British to break into the communications of the highest levels of the Nazi regime, motivated the development of a special-purpose electronic codebreaking computer, shortened World War II and saved countless lives.

Tutte, who died aged 84 in Canada in 2002, went on to do far-reaching work in mathematics but few people have heard of him and his contributions.

First breakthrough

Tutte’s origins were humble. He was born in Newmarket, a market town in England north of London, the son of a gardener and a housekeeper.

He excelled at school and entered Trinity College, Cambridge, in 1935, where he majored in chemistry.

While still an undergraduate he became close friends with three mathematics students: Leonard Brooks, Cedric Smith and Arthur Stone. Together, these four threw themselves into mathematical problem-solving and research.

They were attracted to a simple recreational puzzle, on whether it is possible to divide a square up into smaller squares, all of different sizes, known as Squaring the Square.

The prevailing belief was that it could not be done. But they managed to do it, partly by discovering an unexpected link with the mathematics of electrical circuits.

The theoretical framework they developed has had a lasting influence. A German mathematician, Roland Sprague, working independently, just pipped them to a solution to the puzzle, but not the theory behind it.

The work of Tutte and his friends was published in an academic journal in 1940. It got Tutte noticed at Cambridge, and from there he joined Britain’s wartime codebreaking operation at Bletchley Park in 1941.

The codebreakers

Other Cambridge mathematicians were there before Tutte. Among them was Alan Turing, who had worked out how to break the version of the Enigma code used by the German navy.

The Enigma code was already so difficult that even there, at Bletchley Park – the best codebreaking operation of the War – it had sat in the too-hard basket until Turing’s arrival. It was a very tough problem, even for him.

Tutte worked on different cypher machine, known as the Lorenz cypher. This was the one used by the Nazi High Command, including Hitler himself.

It was much more complex than Enigma, and on top of that, the British knew very little about how it worked, whereas with Enigma they knew everything.

So it was a harder problem with less information, and yet Tutte solved it. It was a staggering achievement.

Tutte’s breakthrough was based on careful analysis of intercepted encrypted traffic to identify some periodic behaviour that indicated the size of a “wheel” component in the machine.

Tutte’s attack on Lorenz needed to be automated. This led to the design and construction of the Colossus machines, led by Tommy Flowers.

These are sometimes regarded as the world’s first computers, having most of the fundamental characteristics that the term “computer” is taken to embrace today.

They were so successful at breaking into the encoded messages of the Nazi regime’s high command that they were often able to decode the messages at the same time as the intended German recipients were reading them.

This gave an incalculable advantage to the Allies in the later years of the war, including their preparations for invading Normandy.

Tutte’s work on Lorenz has been described as the greatest intellectual achievement of the second world war. As a result, he was given a fellowship at Cambridge and went on to do his PhD there.

From codes to networks

Another big effect of the Squaring the Square puzzle was to turn Tutte’s attention more to mathematics, while he was majoring in chemistry, and in particular to the theory of graphs.

These are not the simple graphs you would use to chart things such as daily temperatures over time. Rather, they are abstract networks, consisting of objects (called vertices or nodes), and interactions between them (called edges or links).

Think of the network of train stations, together with the rail lines between them. Or we might have web pages, with hyperlinks between them, making the graph we know as the World Wide Web. We might have people, with friendships between them. And so on.

One of Tutte’s major contributions was to determine the exact place of graphs among some other mathematical objects for which more theory was known.

In mathematics, the simplest objects to deal with are those that are straight and flat – for example, lines and planes. We call such things linear.

Much of mathematics is about taking things that are non-linear – meaning that they are curved or bent rather than straight or flat – and trying to make them linear, or nearly linear, or to replace them with something linear.

For example, mathematicians can study curves by zooming in so that they look straight, or close to it.

Now, graphs – or networks – are much more complex objects than simple straight lines or planes. Nevertheless, it turns out that there are linear ways of looking at them.

Extra dimensions

But these come at a price. You have to work in many many dimensions, not just the three dimensions of space that we are used to. It’s hard for us to imagine these extra dimensions, as they represent directions that are so weird, so outside our universe, that we can’t even point in them.

In these vast multidimensional worlds, it’s not so easy to tell graphs apart from other linear objects you find. This is what Tutte showed us how to do. He pinpointed exactly what was special about graphs.

This theory brought a new depth to the subject, and related this new field to older and more developed parts of mathematics.

So it was that a purely recreational problem, a source of mathematical fun for undergraduates, sowed seeds that grew into a major contribution to overthrowing the Nazi regime, and raised up a new branch of mathematics that is now used to understand the complex networks that permeate the modern world.

More than a decade after Tutte’s death a memorial was erected in his former home town of Newmarket.

This article is based on a talk by the author at The LaboraStory. For information on any Tutte Centenary events, including an event at Bletchley Park on Sunday May 14, see the Bill Tutte Memorial Fund.

Graham Farr, Professor, Faculty of IT, Monash University

This article was originally published on The Conversation and republished here with permission. Read the original article.