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.[2] This sequence is a Sturmian word.

The Fibonacci word is an example of a Sturmian word. The start of the cutting sequence shown here illustrates the start of the word 0100101001.

DefinitionEdit

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.

Combinatoric definitionsEdit

Sequences of low complexityEdit

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 sequencesEdit

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   |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   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.

Geometric definitionsEdit

Cutting sequence of irrationalEdit

Let w be an infinite sequence of 0s and 1s. The sequence w is Sturmian if for some   and some irrational  , w is realized as the cutting sequence of the line  .

Difference of Beatty sequencesEdit

Let w = (wn) 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   and some irrational  

 

for all   or

 

for all  .

Coding of irrational rotationEdit

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

For  , define   by  . For   define the θ-coding of x to be the sequence (xn) where

 

Let w be an infinite sequence of 0s and 1s. The sequence w is Sturmian if for some   and some irrational  , w is the θ-coding of x.

DiscussionEdit

ExampleEdit

A famous example of a (standard) Sturmian word is the Fibonacci word;[3] its slope is  , where   is the golden ratio.

Balanced aperiodic sequencesEdit

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 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

Slope and interceptEdit

A sequence   over {0,1} is a Sturmian word if and only if there exist two real numbers, the slope   and the intercept  , with   irrational, such that

 

for all  .[5]:284[6]:152 Thus a Sturmian word provides a discretization of the straight line with slope   and intercept ρ. Without loss of generality, we can always assume  , because for any integer k we have

 

All the Sturmian words corresponding to the same slope   have the same set of factors; the word   corresponding to the intercept   is the standard word or characteristic word of slope  .[5]:283 Hence, if  , the characteristic word   is the first difference of the Beatty sequence corresponding to the irrational number  .

The standard word   is also the limit of a sequence of words   defined recursively as follows:

Let   be the continued fraction expansion of  , and define

  •  
  •  
  •  

where the product between words is just their concatenation. Every word in the sequence   is a prefix of the next ones, so that the sequence itself converges to an infinite word, which is  .

The infinite sequence of words   defined by the above recursion is called the standard sequence for the standard word  , and the infinite sequence d = (d1, d2, d3, ...) of nonnegative integers, with d1 ≥ 0 and dn > 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]

FrequenciesEdit

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

Non-binary wordsEdit

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

Associated real numbersEdit

A real number for which the digits with respect to some fixed base form a Sturmian word is a transcendental number.[6]:64,85

Sturmian endomorphismsEdit

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[8][9] and locally Sturmian if it maps some Sturmian word to a Sturmian word.[10] The Sturmian endomorphisms form a submonoid of the monoid of endomorphisms of B.[8]

Define endomorphisms φ and ψ of B, where B = {0,1}, by φ(0) = 01, φ(1) = 0 and ψ(0) = 10, ψ(1) = 0. 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 primitive substitution is Sturmian if the image of the word 10010010100101 is balanced.[clarification needed][9][12]

HistoryEdit

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.[6]:114

See alsoEdit

ReferencesEdit

  1. ^ Hordijk, A.; Laan, D. A. (2001). "Bounds for Deterministic Periodic Routing sequences". Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science. 2081. p. 236. doi:10.1007/3-540-45535-3_19. ISBN 978-3-540-42225-9.
  2. ^ Győri, Ervin; Sós, Vera (2009). Recent Trends in Combinatorics: The Legacy of Paul Erdős. Cambridge University Press. p. 117. ISBN 978-0-521-12004-3.
  3. ^ 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.
  4. ^ a b c d e Lothaire, M. (2002). "Sturmian Words". Algebraic Combinatorics on Words. Cambridge: Cambridge University Press. ISBN 0-521-81220-8. Zbl 1001.68093. Retrieved 2007-02-25.
  5. ^ a b c d Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
  6. ^ a b c d e f Pytheas Fogg, N. (2002). Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. 1794. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.
  7. ^ a b Berstel, J.; Séébold, P. (1994). "A remark on morphic Sturmian words". RAIRO, Inform. Théor. Appl. 2. 8 (3–4): 255–263. doi:10.1051/ita/1994283-402551. ISSN 0988-3754. Zbl 0883.68104.
  8. ^ a b Lothaire (2011, p. 83)
  9. ^ a b c Pytheas Fogg (2002, p. 197)
  10. ^ a b Lothaire (2011, p. 85)
  11. ^ Lothaire (2011, p. 84)
  12. ^ Berstel, Jean; Séébold, Patrice (1993), "A characterization of Sturmian morphisms", in Borzyszkowski, Andrzej M.; Sokołowski, Stefan (eds.), Mathematical Foundations of Computer Science 1993. 18th International Symposium, MFCS'93 Gdańsk, Poland, August 30–September 3, 1993 Proceedings, Lecture Notes in Computer Science, 711, pp. 281–290, doi:10.1007/3-540-57182-5_20, ISBN 978-3-540-57182-7, Zbl 0925.11026
  13. ^ J. Bernoulli III, Sur une nouvelle espece de calcul, Recueil pour les Astronomes, vol. 1, Berlin, 1772, pp. 255–284
  14. ^ Morse, M.; Hedlund, G. A. (1940). "Symbolic Dynamics II. Sturmian Trajectories". American Journal of Mathematics. 62 (1): 1–42. doi:10.2307/2371431. JSTOR 2371431.

Further readingEdit