# Sturmian word

In mathematics, a **Sturmian word** (**Sturmian sequence** or **billiard sequence**^{[1]}), named after Jacques Charles François Sturm, is a certain kind of infinitely long sequence of characters. Such a sequence can be generated by considering a game of English billiards on a square table. The struck ball will successively hit the vertical and horizontal edges labelled 0 and 1 generating a sequence of letters.^{[2]} This sequence is a Sturmian word.

## Definition

Sturmian sequences can be defined strictly in terms of their combinatoric properties or geometrically as cutting sequences for lines of irrational slope or codings for irrational rotations. They are traditionally taken to be infinite sequences on the alphabet of the two symbols *0* and *1*.

### Combinatoric definitions

#### Sequences of low complexity

For an infinite sequence of symbols *w*, let *σ(n)* be the complexity function of *w*; i.e., *σ(n)* = the number of distinct subwords in *w* of length *n*. *w* is Sturmian if *σ(n)=n+1* for all *n*.

#### Balanced sequences

A set *X* of binary strings is called *balanced* if the Hamming weight of elements of *X* takes at most two distinct values. That is, for any |*s*|_{1}=*k* or |*s*|_{1}=*k'* where |*s*|_{1} is the number of *1*s in *s*.

Let *w* be an infinite sequence of *0*s and *1*s and let denote the set of all length-*n* subwords of *w*. The sequence *w* is Sturmian if is balanced for all *n* and *w* is not eventually periodic.

### Geometric definitions

#### Cutting sequence of irrational

Let *w* be an infinite sequence of *0*s and *1*s. The sequence *w* is Sturmian if for some and some irrational , *w* is realized as the cutting sequence of the line .

#### Difference of Beatty sequences

Let *w=(w _{n})* be an infinite sequence of

*0*s and

*1*s. The sequence

*w*is Sturmian if for some and some irrational

#### Coding of irrational rotation

For , define by . For define the *θ*-coding of *x* to be the sequence *(x _{n})* where

Let *w* be an infinite sequence of *0*s and *1*s. The sequence *w* is Sturmian if for some and some irrational , *w* is the *θ*-coding of *x*.

## Discussion

### Example

A famous example of a (standard) Sturmian word is the Fibonacci word;^{[3]} its slope is , where is the golden ratio.

### Balanced aperiodic sequences

A set *S* of finite binary words is *balanced* if for each *n* the subset *S*_{n} of words of length *n* has the property that the Hamming weight of the words in *S*_{n} takes at most two distinct values. A **balanced sequence** is one for which the set of factors is balanced. A balanced sequence has at most *n*+1 distinct factors of length *n*.^{[4]}^{:43} An **aperiodic sequence** is one which does not consist of a finite sequence followed by a finite cycle. An aperiodic sequence has at least *n*+1 distinct factors of length *n*.^{[4]}^{:43} A sequence is Sturmian if and only if it is balanced and aperiodic.^{[4]}^{:43}

### Slope and intercept

A sequence over {0,1} is a Sturmian word if and only if there exist two real numbers, the *slope* and the *intercept* , with irrational, such that

for all .^{[5]}^{:284}^{[6]}^{:152} Thus a Sturmian word provides a discretization of the straight line with slope and intercept *ρ*. Without loss of generality, we can always assume , because for any integer *k* we have

All the Sturmian words corresponding to the same slope have the same set of factors; the word corresponding to the intercept is the **standard word** or **characteristic word** of slope .^{[5]}^{:283} Hence, if , the characteristic word is the first difference of the Beatty sequence corresponding to the irrational number .

The standard word is also the limit of a sequence of words defined recursively as follows:

Let be the continued fraction expansion of , and define

where the product between words is just their concatenation. Every word in the sequence is a prefix of the next ones, so that the sequence itself converges to an infinite word, which is .

The infinite sequence of words defined by the above recursion is called the **standard sequence** for the standard word , and the infinite sequence *d* = (*d*_{1}, *d*_{2}, *d*_{3}, ...) of nonnegative integers, with *d*_{1} ≥ 0 and *d*_{n} > 0 (*n* ≥ 2), is called its **directive sequence**.

A Sturmian word *w* over {0,1} is characteristic if and only if both 0*w* and 1*w* are Sturmian.^{[7]}

### Frequencies

If *s* is an infinite sequence word and *w* is a finite word, let μ_{N}(*w*) denote the number of occurrences of *w* as a factor in the prefix of *s* of length *N*+|*w*|-1. If μ_{N}(*w*) has a limit as *N*→∞, we call this the **frequency** of *w*, denoted by μ(*w*).^{[4]}^{:73}

For a Sturmian word *s*, every finite factor has a frequency. The **three-distance theorem** states that the factors of fixed length *n* have at most three distinct frequencies, and if there are three values then one is the sum of the other two.^{[4]}^{:73}

## Non-binary words

For words over an alphabet of size *k* greater than 2, we define a Sturmian word to be one with complexity function *n*+*k*−1.^{[6]}^{:6} They can be described in terms of cutting sequences for *k*-dimensional space.^{[6]}^{:84} An alternative definition is as words of minimal complexity subject to not being ultimately periodic.^{[6]}^{:85}

## Associated real numbers

A real number for which the digits with respect to some fixed base form a Sturmian word is a transcendental number.^{[6]}^{:64,85}

## History

Although the study of Sturmian words dates back to Johann III Bernoulli (1772),^{[8]}^{[5]}^{:295} it was Gustav A. Hedlund and Marston Morse in 1940 who coined the term *Sturmian* to refer to such sequences,^{[5]}^{:295}^{[9]} in honor of the mathematician Jacques Charles François Sturm due to the relation with the Sturm comparison theorem.^{[6]}^{:114}

## See also

## References

- ↑ Template:Cite doi
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑
^{4.0}^{4.1}^{4.2}^{4.3}^{4.4}{{#invoke:citation/CS1|citation |CitationClass=book }} - ↑
^{5.0}^{5.1}^{5.2}^{5.3}{{#invoke:citation/CS1|citation |CitationClass=book }} - ↑
^{6.0}^{6.1}^{6.2}^{6.3}^{6.4}^{6.5}{{#invoke:citation/CS1|citation |CitationClass=book }} - ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}
- ↑ J. Bernoulli III, Sur une nouvelle espece de calcul, Recueil pour les Astronomes, vol. 1, Berlin, 1772, pp. 255–284
- ↑ Template:Cite jstor

## Further reading

- {{#invoke:citation/CS1|citation

|CitationClass=book }}