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.
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.
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.
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.
, w is realized as the cutting sequence of the line
A set S of finite binary words is balanced if for each n the subset Sn of words of length n has the property that the Hamming weight of the words in Sn takes at most two distinct values.
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.
over {0,1} is a Sturmian word if and only if there exist two real numbers, the slope
[5]: 284 [6]: 152 Thus a Sturmian word provides a discretization of the straight line with slope
, because for any integer k we have All the Sturmian words corresponding to the same slope
is the first difference of the Beatty sequence corresponding to the irrational number
, and define where the product between words is just their concatenation.
is a prefix of the next ones, so that the sequence itself converges to an infinite word, which is
, and the infinite sequence d = (d1, d2, d3, ...) of nonnegative integers, with d1 ≥ 0 and dn > 0 (n ≥ 2), is called its directive sequence.
[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 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 A real number for which the digits with respect to some fixed base form a Sturmian word is a transcendental number.
Then I, φ and ψ are Sturmian,[11] and the Sturmian endomorphisms of B∗ are precisely those endomorphisms in the submonoid of the endomorphism monoid generated by {I,φ,ψ}.
[9][10][7] 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.
[9][12] Although the study of Sturmian words dates back to Johann III Bernoulli (1772),[13][5]: 295 it was Gustav A. Hedlund and Marston Morse in 1940 who coined the term Sturmian to refer to such sequences,[5]: 295 [14] in honor of the mathematician Jacques Charles François Sturm due to the relation with the Sturm comparison theorem.
