The Work of Dalia Krieger in Combinatorics on Words

My student Dalia Krieger recently defended her Ph. D. thesis successfully. She'll be leaving Waterloo soon to take up a postdoctoral position in Israel. That's a good excuse to talk about some topics in combinatorics on words.

Dalia's thesis focused on problems dealing with "critical exponents". To explain what she did, I first need to define the notion of powers in words. By a "word", I just mean a string of symbols. A square is a nonempty word of the form xx where x is a word. For example, the word murmur is a square in English (let x = mur). Similarly, we can define cubes, and more generally, n'th powers, where n is an integer ≥ 1.

We can even define fractional powers! We say that a word y is a p/q power if y is of length p, and consists of a word x of length q repeated some number of times, followed by some prefix of x. For example, alfalfa is a 7/3 power, because it can be written as (alf)²a. We say that the exponent of alfalfa is 7/3.

The critical exponent of an infinite word x is defined to be the supremum of the exponents of all subwords of x. (Here a subword is a contiguous block of letters; it is called a "factor" in Europe.) Of course, this supremum could be infinite. Given an infinite word, it is a very interesting and challenging problem to determine its critical exponent.

Now, there is a particular class of infinite words that is of particular interest: these are the word that are generated by iterating a morphism. A morphism is a map that sends every letter in some finite alphabet to a finite word. We can then apply the morphism to a word by applying it to each individual letter and concatenating the results together. Thus, a morphism is a map f that satisfies f(xy) = f(x)f(y). Provided the domain and range of a morphism are over the same alphabet, and the morphism is non-erasing (never maps a letter to the empty string), we can iterate a morphism, obtaining longer and longer words. If in addition f(a) = ax for some word x, then each iterate, starting with a will be a prefix of the next, so we can talk about the unique infinite word that has all the iterates as prefixes.

The simplest example of such an infinite word is the Fibonacci word, generated by iterating the map φ that sends a to ab and b to a. When we iterate this map, starting with a we get,
successively,

a, ab, aba, abaab, abaababa, abaababaabaab, abaababaabaababaababa, ...

Notice that each word is the concatenation of the previous two.

The Fibonacci word evidently contains cubes; for example, the cube (aba)^3 appears in the last word above. What is its critical exponent? In a beautiful paper in 1992, Mignosi and Pirillo showed that the critical exponent is

(5+√ 5)/2,

or about 3.618. (This is the "golden ratio" plus 2.)

On the other hand, the famous Thue-Morse word t is generated by iterating μ on 0, where μ sends 0 to 01 and 1 to 10. (Such a morphism is called "uniform" because each letter gets sent to a block of the same length.) The critical exponent of

t = 0110100110010110 ...

is 2, as was proved by Thue about a hundred years ago.

Dalia proved many results in her thesis, but here are some of the easiest to state: first, every real number > 1 can be the critical exponent of some infinite word. Second, if an infinite word is generated by a uniform morphism over the binary alphabet, then the critical exponent is always either infinite or rational. (She also gives a way to compute it.) Third, if an infinite word is generated by an arbitrary non-erasing morphism, then the critical exponent is always either infinite or algebraic. (An algebraic number is one that is the zero of a polynomial.) Furthermore, she can say which algebraic number field the critical exponent must lie in.

These are beautiful results, and the proofs are quite difficult. Before her work, computing the critical exponent of a word generated by a morphism was a kind of "black art", but now it can usually be done without too much work.

Congratulations to Dalia for a great thesis!