Sturmian word

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.

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 ${\displaystyle s\in X}$ |s|₁ = k or |s|₁ = k' where |s|₁ is the number of 1s in s.

Let w be an infinite sequence of 0s and 1s and let ${\displaystyle {\mathcal {L}}_{n}(w)}$ denote the set of all length-n subwords of w. The sequence w is Sturmian if ${\displaystyle {\mathcal {L}}_{n}(w)}$ is balanced for all n and w is not eventually periodic.

Let w be an infinite sequence of 0s and 1s. The sequence w is Sturmian if for some ${\displaystyle x\in [0,1)}$ and some irrational ${\displaystyle \theta \in (0,\infty )}$, w is realized as the cutting sequence of the line ${\displaystyle f(t)=\theta t+x}$.

Let w = (w_n) 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 ${\displaystyle x\in [0,1)}$ and some irrational ${\displaystyle \theta \in (0,1)}$

${\displaystyle w_{n}=\lfloor n\theta +x\rfloor -\lfloor (n-1)\theta +x\rfloor }$

for all ${\displaystyle n}$ or

${\displaystyle w_{n}=\lceil n\theta +x\rceil -\lceil (n-1)\theta +x\rceil }$

for all ${\displaystyle n}$.

Animation showing the Sturmian sequence generated by an irrational rotation with θ ≈ 0.2882 and x ≈ 0.0789

For ${\displaystyle \theta \in [0,1)}$, define ${\displaystyle T_{\theta }:[0,1)\to [0,1)}$ by ${\displaystyle t\mapsto t+\theta {\bmod {1}}}$. For ${\displaystyle x\in [0,1)}$ define the θ-coding of x to be the sequence (x_n) where

${\displaystyle x_{n}={\begin{cases}1&{\text{if }}T_{\theta }^{n}(x)\in [0,\theta ),\\0&{\text{else}}.\end{cases}}}$

Let w be an infinite sequence of 0s and 1s. The sequence w is Sturmian if for some ${\displaystyle x\in [0,1)}$ and some irrational ${\displaystyle \theta \in (0,\infty )}$, w is the θ-coding of x.

A famous example of a (standard) Sturmian word is the Fibonacci word;[3] its slope is ${\displaystyle 1/\phi }$, where ${\displaystyle \phi }$ is the golden ratio.

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

A sequence ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ over {0,1} is a Sturmian word if and only if there exist two real numbers, the slope ${\displaystyle \alpha }$ and the intercept ${\displaystyle \rho }$, with ${\displaystyle \alpha }$ irrational, such that

${\displaystyle a_{n}=\lfloor \alpha (n+1)+\rho \rfloor -\lfloor \alpha n+\rho \rfloor -\lfloor \alpha \rfloor }$

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

${\displaystyle \lfloor (\alpha +k)(n+1)+\rho \rfloor -\lfloor (\alpha +k)n+\rho \rfloor -\lfloor \alpha +k\rfloor =a_{n}.}$

All the Sturmian words corresponding to the same slope ${\displaystyle \alpha }$ have the same set of factors; the word ${\displaystyle c_{\alpha }}$ corresponding to the intercept ${\displaystyle \rho =0}$ is the standard word or characteristic word of slope ${\displaystyle \alpha }$.[5]^:283 Hence, if ${\displaystyle 0<\alpha <1}$, the characteristic word ${\displaystyle c_{\alpha }}$ is the first difference of the Beatty sequence corresponding to the irrational number ${\displaystyle \alpha }$.

The standard word ${\displaystyle c_{\alpha }}$ is also the limit of a sequence of words ${\displaystyle (s_{n})_{n\geq 0}}$ defined recursively as follows:

Let ${\displaystyle [0;d_{1}+1,d_{2},\ldots ,d_{n},\ldots ]}$ be the continued fraction expansion of ${\displaystyle \alpha }$, and define

• ${\displaystyle s_{0}=1}$
• ${\displaystyle s_{1}=0}$
• ${\displaystyle s_{n+1}=s_{n}^{d_{n}}s_{n-1}{\text{ for }}n>0}$

where the product between words is just their concatenation. Every word in the sequence ${\displaystyle (s_{n})_{n>0}}$ is a prefix of the next ones, so that the sequence itself converges to an infinite word, which is ${\displaystyle c_{\alpha }}$.

The infinite sequence of words ${\displaystyle (s_{n})_{n\geq 0}}$ defined by the above recursion is called the standard sequence for the standard word ${\displaystyle c_{\alpha }}$, and the infinite sequence d = (d₁, d₂, d₃, ...) of nonnegative integers, with d₁ ≥ 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 0w and 1w are Sturmian.[7]

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-gap theorem implies 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