In mathematics, more specifically in combinatorics on words, a Sturmian word (Sturmian sequence or billiard sequence) is a certain kind of infinitely long sequence of characters. The concept is named after Jacques Charles François Sturm. 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 s ∈ X {\displaystyle s\in X} |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 L n ( w ) {\displaystyle {\mathcal {L}}_{n}(w)} denote the set of all length-n subwords of w. The sequence w is Sturmian if L n ( w ) {\displaystyle {\mathcal {L}}_{n}(w)} 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 x ∈ [ 0 , 1 ) {\displaystyle x\in [0,1)} and some irrational θ ∈ ( 0 , ∞ ) {\displaystyle \theta \in (0,\infty )} , w is realized as the cutting sequence of the line f ( t ) = θ t + x {\displaystyle f(t)=\theta t+x} .
Difference of Beatty sequences 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 x ∈ [ 0 , 1 ) {\displaystyle x\in [0,1)} and some irrational θ ∈ ( 0 , 1 ) {\displaystyle \theta \in (0,1)}
w n = ⌊ n θ + x ⌋ − ⌊ ( n − 1 ) θ + x ⌋ {\displaystyle w_{n}=\lfloor n\theta +x\rfloor -\lfloor (n-1)\theta +x\rfloor }
for all n {\displaystyle n} or
w n = ⌈ n θ + x ⌉ − ⌈ ( n − 1 ) θ + x ⌉ {\displaystyle w_{n}=\lceil n\theta +x\rceil -\lceil (n-1)\theta +x\rceil }
for all n {\displaystyle n} .
Coding of irrational rotation
For θ ∈ [ 0 , 1 ) {\displaystyle \theta \in [0,1)} , define T θ : [ 0 , 1 ) → [ 0 , 1 ) {\displaystyle T_{\theta }:[0,1)\to [0,1)} by t ↦ t + θ mod 1 {\displaystyle t\mapsto t+\theta {\bmod {1}}} . For x ∈ [ 0 , 1 ) {\displaystyle x\in [0,1)} define the θ-coding of x to be the sequence (xn) where
x n = { 1 if T θ n ( x ) ∈ [ 0 , θ ) , 0 else . {\displaystyle x_{n}={\begin{cases}1&{\text{if }}T_{\theta }^{n}(x)\in [0,\theta ),\\0&{\text{else}}.\end{cases}}}
Let w be an infinite sequence of 0s and 1s. The sequence w is Sturmian if for some x ∈ [ 0 , 1 ) {\displaystyle x\in [0,1)} and some irrational θ ∈ ( 0 , ∞ ) {\displaystyle \theta \in (0,\infty )} , w is the θ-coding of x.
Discussion
… excerpt ends here. Continue reading the full article.
