Sturmian word#Discussion

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. That is, for any $s\backslash in\; X$ |s|₁ = k or |s|₁ = k' where |s|₁ is the number of 1s in s.

Let w be an infinite sequence of 0s and 1s and let $\backslash mathcal\; L\_n(w)$ denote the set of all length-n subwords of w. The sequence w is Sturmian if $\backslash mathcal\; L\_n(w)$ is balanced for all n and w is not eventually periodic.

Let w be an infinite sequence of 0s and 1s. The sequence w is Sturmian if for some $x\backslash in[0,1)$ and some irrational $\backslash theta\backslash in(0,\backslash infty)$, w is realized as the cutting sequence of the line $f(t)=\backslash theta\; t+x$.

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 $x\backslash in[0,1)$ and some irrational $\backslash theta\backslash in(0,1)$

:$w\_n\; =\; \backslash lfloor\; n\backslash theta\; +\; x\backslash rfloor\; -\; \backslash lfloor\; (n-1)\backslash theta\; +\; x\; \backslash rfloor$

for all $n$ or

:$w\_n\; =\; \backslash lceil\; n\backslash theta\; +\; x\backslash rceil\; -\; \backslash lceil\; (n-1)\backslash theta\; +\; x\; \backslash rceil$

for all $n$.

File:Sturmian-sequence-from-irrational-rotation.gif

For $\backslash theta\backslash in\; [0,1)$, define $T\_\backslash theta:[0,1)\backslash to[0,1)$ by $t\backslash mapsto\; t+\backslash theta\backslash bmod\; 1$. For $x\backslash in[0,1)$ define the θ-coding of x to be the sequence (x_n) where

:

Let w be an infinite sequence of 0s and 1s. The sequence w is Sturmian if for some $x\backslash in[0,1)$ and some irrational $\backslash theta\backslash in(0,\backslash infty)$, w is the θ-coding of x.

A famous example of a (standard) Sturmian word is the Fibonacci word;{{cite journal | journal=Information Processing Letters | year=1995 | pages=307–312 | doi=10.1016/0020-0190(95)00067-M | title=A division property of the Fibonacci word | first=Aldo | last=de Luca | volume=54 | issue=6 }} its slope is $1/\backslash phi$, where $\backslash phi$ is the golden ratio.

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.{{cite book | last = Lothaire | first = M. | author-link = M. Lothaire | title = Algebraic Combinatorics on Words | url = https://archive.org/details/algebraiccombina0000loth | access-date = 2007-02-25 | year = 2002 | publisher = Cambridge University Press | location = Cambridge | isbn = 0-521-81220-8 | chapter = Sturmian Words | zbl = 1001.68093 | chapter-url = http://www-igm.univ-mlv.fr/%7Eberstel/Lothaire/ChapitresACW/C2.ps | url-access = registration }}{{rp|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.{{rp|43}} A sequence is Sturmian if and only if it is balanced and aperiodic.{{rp|43}}

A sequence $(a\_n)\_\{n\backslash in\backslash mathbb\{N\}\}$ over {0,1} is a Sturmian word if and only if there exist two real numbers, the slope $\backslash alpha$ and the intercept $\backslash rho$, with $\backslash alpha$ irrational, such that

:$a\_n=\backslash lfloor\backslash alpha(n+1)+\backslash rho\backslash rfloor\; -\backslash lfloor\backslash alpha\; n+\backslash rho\backslash rfloor-\backslash lfloor\backslash alpha\backslash rfloor$

for all $n$.{{cite book | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | isbn = 978-0-521-82332-6 | publisher = Cambridge University Press | title = Automatic Sequences: Theory, Applications, Generalizations | year = 2003 | zbl=1086.11015 }}{{rp|284}}{{cite book | last=Pytheas Fogg | first=N. | editor1-first=Valérie | editor1-last = Berthé |editor1-link = Valérie Berthé| editor2-last = Ferenczi | editor2-first= Sébastien | editor3-last= Mauduit | editor3-first= Christian | editor4-last= Siegel | editor4-first= A. | title=Substitutions in dynamics, arithmetics and combinatorics | series=Lecture Notes in Mathematics | volume=1794 | location=Berlin | publisher=Springer-Verlag | year=2002 | isbn=3-540-44141-7 | zbl=1014.11015 }}{{rp|152}} Thus a Sturmian word provides a discretization of the straight line with slope $\backslash alpha$ and intercept ρ. Without loss of generality, we can always assume , because for any integer k we have

: $\backslash lfloor(\backslash alpha\; +\; k)(n\; +\; 1)\; +\; \backslash rho\backslash rfloor\; -\; \backslash lfloor(\backslash alpha+k)n\; +\; \backslash rho\backslash rfloor\; -\; \backslash lfloor\backslash alpha\; +\; k\backslash rfloor\; =\; a\_n.$

All the Sturmian words corresponding to the same slope $\backslash alpha$ have the same set of factors; the word $c\_\backslash alpha$ corresponding to the intercept $\backslash rho=0$ is the standard word or characteristic word of slope $\backslash alpha$.{{rp|283}} Hence, if , the characteristic word $c\_\backslash alpha$ is the first difference of the Beatty sequence corresponding to the irrational number $\backslash alpha$.

The standard word $c\_\backslash alpha$ is also the limit of a sequence of words $(s\_n)\_\{n\; \backslash ge\; 0\}$ defined recursively as follows:

Let $[0;\; d\_1+1,\; d\_2,\; \backslash ldots,\; d\_n,\; \backslash ldots]$ be the continued fraction expansion of $\backslash alpha$, and define

• $s\_0=1$
• $s\_1=0$
• $s\_\{n+1\}=s\_n^\{d\_n\}s\_\{n-1\}\backslash 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\_\backslash alpha$.

The infinite sequence of words $(s\_n)\_\{n\; \backslash ge\; 0\}$ defined by the above recursion is called the standard sequence for the standard word $c\_\backslash alpha$, 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 Sturmian word w over {0,1} is characteristic if and only if both 0w and 1w are Sturmian.

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).{{rp|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.{{rp|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.{{rp|6}} They can be described in terms of cutting sequences for k-dimensional space.{{rp|84}} An alternative definition is as words of minimal complexity subject to not being ultimately periodic.{{rp|85}}

A real number for which the digits with respect to some fixed base form a Sturmian word is a transcendental number.{{rp|64,85}}

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{{harvtxt|Lothaire|2011|p=83}}{{harvtxt|Pytheas Fogg|2002|p=197}} and locally Sturmian if it maps some Sturmian word to a Sturmian word.{{harvtxt|Lothaire|2011|p=85}} 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,{{harvtxt|Lothaire|2011|p=84}} and the Sturmian endomorphisms of B^∗ are precisely those endomorphisms in the submonoid of the endomorphism monoid generated by {I,φ,ψ}.{{cite journal | last1=Berstel | first1=J. | last2=Séébold | first2=P. | title=A remark on morphic Sturmian words | journal=RAIRO, Inform. Théor. Appl. 2| volume=8 | number=3–4 | pages=255–263 | year=1994 | issn=0988-3754 | zbl=0883.68104 | doi=10.1051/ita/1994283-402551 | doi-access=free }}

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.{{citation | chapter=A characterization of Sturmian morphisms | first1=Jean | last1=Berstel | first2=Patrice | last2=Séébold | title=Mathematical Foundations of Computer Science 1993. 18th International Symposium, MFCS'93 Gdańsk, Poland, August 30–September 3, 1993 Proceedings | editor1-first=Andrzej M. | editor1-last=Borzyszkowski | editor2-first=Stefan | editor2-last=Sokołowski | pages=281–290 | year=1993 | doi=10.1007/3-540-57182-5_20 | isbn=978-3-540-57182-7 | series=Lecture Notes in Computer Science | volume=711 | zbl=0925.11026 }}

Although the study of Sturmian words dates back to Johann III Bernoulli (1772),J. Bernoulli III, Sur une nouvelle espece de calcul, Recueil pour les Astronomes, vol. 1, Berlin, 1772, pp. 255–284{{rp|295}} it was Gustav A. Hedlund and Marston Morse in 1940 who coined the term Sturmian to refer to such sequences,{{rp|295}}{{Cite journal | last1 = Morse | first1 = M. | author-link = Marston Morse| last2 = Hedlund | first2 = G. A. | author-link2 = Gustav A. Hedlund| title = Symbolic Dynamics II. Sturmian Trajectories | journal = American Journal of Mathematics | volume = 62 | issue = 1 | pages = 1–42 | doi = 10.2307/2371431 | jstor = 2371431| year = 1940 }} in honor of the mathematician Jacques Charles François Sturm due to the relation with the Sturm comparison theorem.{{rp|114}}

• Cutting sequence
• Word (group theory)
• Morphic word
• Lyndon word

{{Reflist}}

• {{cite book | last=Bugeaud | first=Yann | title=Distribution modulo one and Diophantine approximation | series=Cambridge Tracts in Mathematics | volume=193 | location=Cambridge | publisher=Cambridge University Press | year=2012 | isbn=978-0-521-11169-0 | zbl=1260.11001}}
• {{cite book | last=Lothaire | first=M. | author-link=M. Lothaire | title=Algebraic combinatorics on words | others=With preface by Jean Berstel and Dominique Perrin | edition=Reprint of the 2002 hardback | series=Encyclopedia of Mathematics and Its Applications | volume=90| publisher=Cambridge University Press | year=2011 | isbn=978-0-521-18071-9 | zbl=1221.68183 }}

Category:Combinatorics on words

Category:Sequences and series