thumb|upright=1.2|class=skin-invert-image|The [[Fibonacci word is an example of a Sturmian word. The start of the cutting sequence shown here illustrates the start of the word 0100101001.]]
In mathematics, more specifically in combinatorics on words, a Sturmian word (Sturmian sequence or billiard sequence) is a certain kind of infinitely long sequence of characters. The concept is named after Jacques Charles François Sturm.
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. 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.
Combinatorial 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 contiguous subwords (factors) in w of length n. Then 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 <math>s\in X</math> |s|<sub>1</sub> = k or |s|<sub>1</sub> = k where |s|<sub>1</sub> is the number of 1s in s.
Let w be an infinite sequence of 0s and 1s and let <math>\mathcal L_n(w)</math> denote the set of all length-n subwords of w. The sequence w is Sturmian if <math>\mathcal L_n(w)</math> is balanced for all n and w is not eventually periodic.
Geometric definitions
Cutting sequence of irrational
Let w be an infinite sequence of 0s and 1s. The sequence w is Sturmian if for some <math>x\in[0,1)</math> and some irrational <math>\theta\in(0,\infty)</math>, w is realized as the cutting sequence of the line <math>f(t)=\theta t+x</math>.
Difference of Beatty sequences
Let w = (w<sub>n</sub>) be an infinite sequence of 0s and 1s. The sequence w is Sturmian if it is the difference of non-homogeneous Beatty sequences, that is, for some <math>x\in[0,1)</math> and some irrational <math>\theta\in(0,1)</math>
:<math>w_n = \lfloor n\theta + x\rfloor - \lfloor (n-1)\theta + x \rfloor </math>
for all <math>n</math> or
:<math>w_n = \lceil n\theta + x\rceil - \lceil (n-1)\theta + x \rceil </math>
for all <math>n</math>.
Coding of irrational rotation
thumb|upright=0.7|class=skin-invert-image|Animation showing the Sturmian sequence generated by an irrational rotation with θ ≈ 0.2882 and x ≈ 0.0789
For <math>\theta\in [0,1)</math>, define <math>T_\theta:[0,1)\to[0,1)</math> by <math>t\mapsto t+\theta\bmod 1</math>. For <math>x\in[0,1)</math> define the θ-coding of x to be the sequence (x<sub>n</sub>) where
:<math>x_n= \begin{cases} 1 & \text{if } T_\theta^n(x)\in [0,\theta), \\ 0 & \text{else}. \end{cases}</math>
Let w be an infinite sequence of 0s and 1s. The sequence w is Sturmian if for some <math>x\in[0,1)</math> and some irrational <math>\theta\in(0,\infty)</math>, w is the θ-coding of x.
Discussion
Example
A famous example of a (standard) Sturmian word is the Fibonacci word; its slope is <math>1/\phi</math>, where <math>\phi</math> is the golden ratio.
Balanced aperiodic sequences
A set S of finite binary words is balanced if for each n the subset S<sub>n</sub> of words of length n has the property that the Hamming weight of the words in S<sub>n</sub> 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. 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. Thus a Sturmian word provides a discretization of the straight line with slope <math>\alpha</math> and intercept ρ. Without loss of generality, we can always assume <math>0<\alpha<1</math>, because for any integer k we have
: <math>\lfloor(\alpha + k)(n + 1) + \rho\rfloor - \lfloor(\alpha+k)n + \rho\rfloor - \lfloor\alpha + k\rfloor = a_n.</math>
All the Sturmian words corresponding to the same slope <math>\alpha</math> have the same set of factors; the word <math>c_\alpha</math> corresponding to the intercept <math>\rho=0</math> is the standard word or characteristic word of slope <math>\alpha</math>. and locally Sturmian if it maps some Sturmian word to a Sturmian word. The Sturmian endomorphisms form a submonoid of the monoid of endomorphisms of B<sup>∗</sup>. and the Sturmian endomorphisms of B<sup>∗</sup> are precisely those endomorphisms in the submonoid of the endomorphism monoid generated by {I,φ,ψ}.
A morphism is Sturmian if and only if the image of the word 10010010100101 is a balanced sequence; that is, for each n, the Hamming weights of the subwords of length n take at most two distinct values.
History
Although the study of Sturmian words dates back to Johann III Bernoulli (1772), in honor of the mathematician Jacques Charles François Sturm due to the relation with the Sturm comparison theorem.