Kind of infinitely long sequence of characters
In mathematics, a Sturmian word (Sturmian sequence or billiard sequence), 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. 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 formula_1 |"s"|1 = "k" or |"s"|1 = "k"' where |"s"|1 is the number of 1s in "s".
Let "w" be an infinite sequence of 0s and 1s and let formula_2 denote the set of all length-"n" subwords of "w". The sequence "w" is Sturmian if formula_2 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 formula_4 and some irrational formula_5, "w" is realized as the cutting sequence of the line formula_6.
Difference of Beatty sequences.
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 formula_4 and some irrational formula_8
formula_9
for all formula_10 or
formula_11
for all formula_10.
Coding of irrational rotation.
For formula_13, define formula_14 by formula_15. For formula_4 define the "θ"-coding of "x" to be the sequence ("x""n") where
formula_17
Let "w" be an infinite sequence of 0s and 1s. The sequence "w" is Sturmian if for some formula_4 and some irrational formula_5, "w" is the "θ"-coding of "x".
Discussion.
Example.
A famous example of a (standard) Sturmian word is the Fibonacci word; its slope is formula_20, where formula_21 is the golden ratio.
Balanced aperiodic sequences.
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". 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". A sequence is Sturmian if and only if it is balanced and aperiodic.
Slope and intercept.
A sequence formula_22 over {0,1} is a Sturmian word if and only if there exist two real numbers, the "slope" formula_23 and the "intercept" formula_24, with formula_23 irrational, such that
formula_26
for all formula_10. Thus a Sturmian word provides a discretization of the straight line with slope formula_23 and intercept "ρ". Without loss of generality, we can always assume formula_29, because for any integer "k" we have
 formula_30
All the Sturmian words corresponding to the same slope formula_23 have the same set of factors; the word formula_32 corresponding to the intercept formula_33 is the standard word or characteristic word of slope formula_23. Hence, if formula_29, the characteristic word formula_32 is the first difference of the Beatty sequence corresponding to the irrational number formula_23.
The standard word formula_32 is also the limit of a sequence of words formula_39 defined recursively as follows:
Let formula_40 be the continued fraction expansion of formula_23, and define
where the product between words is just their concatenation. Every word in the sequence formula_45 is a prefix of the next ones, so that the sequence itself converges to an infinite word, which is formula_32.
The infinite sequence of words formula_39 defined by the above recursion is called the standard sequence for the standard word formula_32, and the infinite sequence "d" = ("d"1, "d"2, "d"3, ...) of nonnegative integers, with "d"1 ≥ 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 0"w" and 1"w" are Sturmian.
Frequencies.
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").
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.
Non-binary words.
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. They can be described in terms of cutting sequences for "k"-dimensional space. An alternative definition is as words of minimal complexity subject to not being ultimately periodic.
Associated real numbers.
A real number for which the digits with respect to some fixed base form a Sturmian word is a transcendental number.
Sturmian endomorphisms.
An endomorphism of the free monoid "B"∗ on a 2-letter alphabet "B" is Sturmian if it maps every Sturmian word to a Sturmian word 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"∗.
Define endomorphisms φ and ψ of "B"∗, where "B" = {0,1}, by φ(0) = 01, φ(1) = 0 and ψ(0) = 10, ψ(1) = 0. Then "I", φ and ψ are Sturmian, and the Sturmian endomorphisms of "B"∗ 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), it was Gustav A. Hedlund and Marston Morse in 1940 who coined the term "Sturmian" to refer to such sequences, in honor of the mathematician Jacques Charles François Sturm due to the relation with the Sturm comparison theorem.
References.
 ;templatestyles src="Reflist/styles.css" / ;