Sturmian word

From Wikipedia, the free encyclopedia

In mathematics, a Sturmian word is a certain kind of infinite word.

1 Definition
2 Discussion
3 History
4 References

[edit] Definition

A word is a (potentially) infinite sequence of symbols drawn from a finite alphabet. Call any finite contiguous subsequence of a word a factor. Then, a word w is Sturmian if, for all natural numbers n, w has exactly

n + 1

distinct factors of length n.

Note that there must then be two distinct factors of length 1, implying that word uses exactly 2 symbols from the alphabet (without loss of generality we can call these 0 and 1).

[edit] Discussion

A sequence $(a_n)_{n\in\mathbb{N}}$ over {0,1} is a Sturmian word if and only if there exist two real numbers $α$ and $ρ$ , with $α$ irrational, such that

$a_n=\lfloor\alpha(n+1)+\rho\rfloor -\lfloor\alpha n+\rho\rfloor-\lfloor\alpha\rfloor$

for all $n$ . Thus a Sturmian word provides a discretization of the straight line with slope $α$ and intercept $ρ$ . Since for any integer $k$ we have $\lfloor(\alpha+k)(n+1)+\rho\rfloor-\lfloor(\alpha+k)n+\rho\rfloor=a_n$ , we can always assume $0 < α < 1$ .

All the Sturmian words corresponding to the same slope $α$ have the same set of factors; the word $c α$ corresponding to the intercept $ρ = 0$ is the standard or characteristic word of slope $α$ . Hence, if $0 < α < 1$ , the characteristic word $c α$ is the first difference of the Beatty sequence corresponding to the irrational number $α$ . It can also be obtained in the following way. Let $[0; d_1+1, d_2, \ldots, d_n, \ldots]$ be the continued fraction expansion of $α$ , and define

$s 0 = 1$
$s 1 = 0$
$s_{n+1}=s_n^{d_n}s_{n-1}$ for $n > 0$

(remember that the product between words is just the concatenation). Every word in the sequence $(s n) n > 0$ is a prefix of the next ones, so that the sequence itself converges to an infinite word, which is $c α$ .

A famous example of (standard) Sturmian word is the Fibonacci word; its slope is $1 / φ 2$ , where $φ$ is the golden ratio.

[edit] History

Although the study of Sturmian words dates back to J. Bernoulli III (1772), the first comprehensive study of them was by G. A. Hedlund and Marston Morse in 1940. They introduced the term Sturmian, in honor of the mathematician Jacques Charles François Sturm.