# Substitution invariant Sturmian words and binary trees

###### Abstract.

We take a global view at substitution invariant Sturmian sequences. We show that homogeneous substitution invariant Sturmian sequences can be indexed by two binary trees, associated directly to Johannes Kepler’s tree of harmonic fractions from 1619. We obtain similar results for the inhomogeneous sequences and .

Key words. Sturmian word; morphism; substitution; Sturm numbers; binary tree; harmonic fraction; Kepler.

Delft University of Technology,

Faculty EEMCS, P.O. Box 5031,

2600 GA Delft, The Netherlands.

Email: F.M.D

## 1. Introduction

A Sturmian word is an infinite word , in which occur only subwords of length for . It is well known (see, e.g. [12]) that the Sturmian words can be directly derived from rotations on the circle as

(1) |

or as

(2) |

Here and are real numbers, is the floor function, and is the ceiling function.

Sturmian words have been named after Jacques Charles François Sturm, who never studied them. A whole chapter is dedicated to them in Lothaire’s book ‘Algebraic combinatorics on words’ ([12]). There is a huge literature, in particular on the *homogeneous* Sturmian words

which have been studied since Johann III Bernoulli. The homogeneous Sturmian words are also known as *characteristic words* see Chapter 9 in [2].

Interestingly, for certain and the Sturmian word is a fixed point of a morphism^{1}^{1}1We interchangeably use the terms morphisms and substitutions. of the monoid of words over the alphabet . For example, for one obtains the Fibonacci word , fixed point of the Fibonacci morphism given by , . Another example is the Pell word obtained for , with morphism given by .

It is well known for which one obtains a morphism invariant . This was first obtained in [11], and an extensive treatment can be found in [12, Section 2.3.6]. The result is that gives a fixed point if and only if there exists a natural number such that has continued fraction expansion

(3) |

and gives a fixed point if and only if there exists a natural number such that has continued fraction expansion

(4) |

The Fibonacci word is obtained for , and the Pell word for .

Any that gives a substitution invariant is called a *Sturm number*. In terms of their continued fraction expansions these are characterized in equations (3) and (4). There is however a simple algebraic way to describe them, given in [1]:

an irrational number is a Sturm number if and only if it is a quadratic irrational number whose algebraic conjugate , defined by the equation , satisfies

A simple manipulation shows that for the number has an expansion as in equation (4) with the same and . Moreover, the Sturmian word is equal to the word , where is the ‘exchange’ morphism

The latter is shown in the proof of Theorem 2.3.25 in [12]. Note that this implies that if generates , then generates . Because of this duality we will confine ourselves often to with in the sequel.

The first question we will consider is: what are the morphisms that leave a homogeneous Sturmian sequence invariant? The answer in [11] is: they are compositions of the infinitely many morphisms and . The answer in [2] is: they are compositions of the infinitely many morphisms (actually only for ’s with a purely periodic continued fraction expansion). See [19] for yet another infinite family of morphisms.

In the paper [9] the authors call the inhomogeneous sequence a characteristic sequence, and do actually derive a result close to our Theorem 3, using completely different techniques with continued fractions and extensive matrix multiplications.

More satisfactory is the answer in the book [12] or the paper [5], where only two generating morphisms are used, namely the exchange morphism and the morphism given by What we propose are also only two generators, which we denote by and , given by

Note that , and that , the Fibonacci morphism. Obviously, this proposal is very close to the one in [12], but what we gain is a natural way to index all the morphisms that leave homogeneous Sturmian words invariant by a binary tree (actually two binary trees, one for , and a dual version for ). In Section 2.1 we treat some preliminaries to give in Section 2.2 our main result.

We remark that a similar tree associated to the rational numbers appears in the work of de Luca [13, 14]. The labeling there is not with morphisms, but with words.

The second question we will consider is: what are the substitution invariant Sturmian words that can only be obtained via the ceiling function, i.e., the Sturmian words that can only be obtained as in equation (2)? In this respect the homogeneous Sturmian words are regular, in that for all

So these ‘strictly ceiling’ Sturmian words have to be sought among the inhomogeneous Sturmian words, what we do in Section 3.

The short Section 4 is more or less independent of the remainder of the paper, but its contents have been very useful in our research.

## 2. Homogeneous Sturmian words

### 2.1. The binary tree of harmonic fractions

The binary tree is a graph with nodes at level for , where the are 0 or 1. At level 0 there is the root node .