Sturmian word

In mathematics, a Sturmian word, named after Jacques Charles François Sturm, is a certain kind of infinite word.

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: that is, the complexity function of w is n + 1.

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). Also, a Sturmian word is necessarily infinite.

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 ρ. Without loss of generality, we can always assume 0 < α < 1, because for any integer k we have

$\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 α have the same set of factors; the word c_α corresponding to the intercept ρ = 0 is the standard word 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 α.

The standard word c_α is also the limit of a sequence of words $(s_n)_{n \ge 0}$ defined recursively as follows:

Let $[0; d_1+1, d_2, \ldots, d_n, \ldots]$ be the continued fraction expansion of α, and define

• s₀ = 1
• s₁ = 0
• $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 (s_n)_{n > 0} is a prefix of the next ones, so that the sequence itself converges to an infinite word, which is c_α.

The infinite sequence of words $(s_n)_{n \ge 0}$ defined by the above recursion is called the standard sequence for the standard word c_α, 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 famous example of (standard) Sturmian word is the Fibonacci word;^[1] its slope is 1 / ϕ², where ϕ is the golden ratio.

History

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

References

1. ^ de Luca, Aldo (1995). "A division property of the Fibonacci word". Information Processing Letters 54 (6): 307–312. doi:10.1016/0020-0190(95)00067-M. 

• Lothaire, M. (2002). "Sturmian Words". Algebraic Combinatorics on Words. Cambridge UK: Cambridge University Press. ISBN 0521812208. http://www-igm.univ-mlv.fr/%7Eberstel/Lothaire/ChapitresACW/C2.ps. Retrieved 2007-02-25. 

See also

• Cutting sequence