Multiple Discoveries of the Thue-Morse Sequence

It is common practice in science to name important advances after the first discoverer or inventor. However, this process often goes awry. A humorous principle called Stigler’s Law holds that no scientific result is named after its original discoverer. This law was formulated by Professor Stephen Stigler of the University of Chicago in his publication “Stigler’s law of eponymy”. He pointed out that his “law” had been proposed by others before him so it was, in a sense, self-verifying. [TM157 or search for “thatsmaths” at irishtimes.com].

Axel Thue (1863-1922) and Marston Morse (1892-1977)

The Calculus Wars

Occasionally, mathematical inventions are made simultaneously by more than one person. Perhaps the greatest example is the formulation of calculus by Isaac Newton and Gottfried Wilhelm Leibniz.

Gottfried Wilhelm Leibniz and Isaac Newton.

The ensuing controversy over priority was described in a book by Jason Bardi, The Calculus Wars. The conflict between British and European mathematicians raged for decades before joint credit for independent discovery was accepted.

A remarkable numerical sequence that has been discovered several times by different mathematicians in different circumstances illustrates Stigler’s Law. It was originally called the Morse sequence when, in 1921, it was popularised by the American mathematician Marston Morse, who applied it in differential geometry. Today, it is usually called the Thue-Morse sequence: the Norwegian mathematician Axel Thue discovered the sequence while studying combinatorics on words; this was in 1906, well before Morse. But more recently, the name Prouhet has been prefixed to the title of the sequence, which was first studied by Eugène Prouhet in 1851.

The Dutch mathematician Max Euwe defeated Alexander Alekhine in 1935, becoming the fifth World Chess Champion. In 1929, Euwe analysed the game of chess from a mathematical perspective and showed that the rules in place at that time did not exclude the possibility of infinite games. In his analysis he re-discovered the Thue–Morse sequence.

Constructing the Sequence

So what is the Thue-Morse sequence? It is a binary sequence, an infinite list of 0s and 1s. We start with 0. At each stage, we replace 0 by 01 and 1 by 10. At the first stage, 0 becomes 01. Then 01 becomes 01 10. Continuing, we get 01 10 10 01, then 01 10 10 01 10 01 01 10 and so on ad infinitum, the length doubling at each stage.

But what use is the Thue-Morse sequence? It arises in a remarkably wide variety of contexts. It is valuable in number theory, combinatorics, computer graphics, fractal geometry and equitable sharing. Let’s look at the last of these.

A pattern constructed using the Thue-Morse sequence.

Suppose that Aodh and Bea are divorcing. They have to divide up their possessions. They agree on the value of each item. They toss for first choice and Aodh wins. The order of choice is then ABABABAB and so on. This is unfair: Aodh always gets the better of each pair of items. Better to start ABBA so that Bea gets the advantage for the second pair.

But how to continue? The answer is in the Thue-Morse sequence. Writing A for 0 and B for 1, the sequence begins ABBA BAAB, continuing according to the pattern above. If Aodh and Bea choose in this manner, a fair division of property is guaranteed.

Sequencing is important in sports: penalty shoot-outs in football, service-order in tennis tie-breaks and choice of colour in chess matches. Normally, they are based on the ABABAB pattern, but this gives undue advantage to the winner of the toss. Are we ready for a fairer but mathematically more complex solution?


Last 50 Posts

Categories