Thue-Morse L-system

 

As our next example of an L-system, we introduce the Thue-Morse system:

The sequence of generations starts as follows:

 

The number of organisms clearly doubles each generation, so that . The first question we might ask is what is the global process that emerges, if any.

To answer this question, we first observe that generation does appear at the beginning of . If we look at what follows, we eventually conclude that it resembles , except that each a has been replaced by a b and each b has been replaced by an a. For any word w in , we define R(w) to be the mirror image word where we replace a by b and b by a. Then the global process is

As a challenge, we ask the reader to supply a proof. (It's very similar to what one writes down for the Fibonacci process; there is one extra key point.)

Since is the beginning of , this L-system produces in the limit an infinite sequence of a's and b's that begins:

This sequence has many interesting properties and is known as the Thue-Morse sequence. Axel Thue came up with it in 1912 [Thu12] in his study of formal languages (not the term he used then). Marston Morse rediscovered the same sequence in 1917 [Mor21] in studying the dynamics of ``geodesics'' on surfaces. We can produce a very interesting formula for the terms in this sequence if we replace a by 1 and b by -1. In that case, the application of the flip map R is the same as multiplication by -1. Write the sequence as

where each is +1 or -1. The n-th generation is

Then the n+1 generation consists of this string followed by

This establishes the formula

for all . So to work out any given , this suggests we need to express m as a sum of powers of 2, that is, we need to find the binary expansion of m:

with . For example,

In binary digits, we would write . The number of powers of 2 occurring equals the number of 1's in the binary expansion. Then applying our formula we have

since . In general,

where t is the number of 1's in the binary expansion of m. Another example:

Thue proved a very interesting theorem about the Thue-Morse sequence.

THEOREM: (Thue-Morse is cube-free) There is no substring of the Thue-Morse sequence of the form www for some finite string w of a's and b's.

For instance, there is no substring aaa or ababab or babbabbab, etc. In fact, Morse proved a slightly stronger theorem stating that there is no string of the form EEe where E is a given string and e is the first symbol in E. This proof first appeared in a paper [MH44] that showed that under a certain set of rules for the ending of chess games it was still possible to have an infinite game of chess. On the other hand, the original reason (see [Mor21] that Morse introduced this sequence is that, without being periodic, it still has a large degree of redundancy.

THEOREM: (Morse; Thue-Morse is recurrent) Let n be a positive integer. There is another positive integer N (much bigger than n usually) such that, given any substring w of length n in the Thue-Morse sequence, we can guarantee that every substring W of length N contains a copy of the string w.

This means that every finite string that occurs in the Thue-Morse sequence occurs over and over without end, and rather frequently at that. An explicit estimate of N may be proved: if k is the smallest integer such that , then we may guarantee that any substring of length in the Thue-Morse sequence contains the given string w of length n.