Definition Sturmian word

1 definition

1.1 combinatoric definitions

1.1.1 sequences of low complexity
1.1.2 balanced sequences


1.2 geometric definitions

1.2.1 cutting sequence of irrational
1.2.2 difference of beatty sequences
1.2.3 coding of irrational rotation

definition

sturmian sequences can defined strictly in terms of combinatoric properties or geometrically cutting sequences lines of irrational slope or codings irrational rotations. traditionally taken infinite sequences on alphabet of 2 symbols 0 , 1.

combinatoric definitions
sequences of low complexity

for infinite sequence of symbols w, let σ(n) complexity function of w; i.e., σ(n) = number of distinct subwords in w of length n. w sturmian if σ(n)=n+1 n.

balanced sequences

a set x of binary strings called balanced if hamming weight of elements of x takes @ 2 distinct values. is,



s
∈
x


{\displaystyle s\in x}

|s|1=k or |s|1=k |s|1 number of 1s in s.

let w infinite sequence of 0s , 1s , let






l



n


(
w
)


{\displaystyle {\mathcal {l}}_{n}(w)}

denote set of length-n subwords of w. sequence w sturmian if






l



n


(
w
)


{\displaystyle {\mathcal {l}}_{n}(w)}

balanced n , w not periodic.

geometric definitions
cutting sequence of irrational

let w infinite sequence of 0s , 1s. sequence w sturmian if



x
∈
[
0
,
1
)


{\displaystyle x\in [0,1)}

, irrational



θ
∈
(
0
,
∞
)


{\displaystyle \theta \in (0,\infty )}

, w realized cutting sequence of line



f
(
t
)
=
θ
t
+
x


{\displaystyle f(t)=\theta t+x}

.

difference of beatty sequences

let w=(wn) infinite sequence of 0s , 1s. sequence w sturmian if difference of non-homogeneous beatty sequences, is,



x
∈
[
0
,
1
)


{\displaystyle x\in [0,1)}

, 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



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



n


{\displaystyle n}

.

coding of irrational rotation

enlarge animation showing sturmian sequence generated irrational rotation θ≈0.2882 , x≈0.0789

for



θ
∈
[
0
,
1
)


{\displaystyle \theta \in [0,1)}

, define




t

θ


:
[
0
,
1
)
→
[
0
,
1
)


{\displaystyle t_{\theta }:[0,1)\to [0,1)}





t
↦
t
+
θ

mod


1


{\displaystyle t\mapsto t+\theta \mod 1}

.



x
∈
[
0
,
1
)


{\displaystyle x\in [0,1)}

define θ-coding of x sequence (xn) where

x

n


=

{




1



 if 


t

θ


n


(
x
)
∈
[
0
,
θ
)




0



 else









{\displaystyle x_{n}=\left\{{\begin{array}{cl}1&{\text{ if }}t_{\theta }^{n}(x)\in [0,\theta )\\0&{\text{ else}}\end{array}}\right.}

.

let w infinite sequence of 0s , 1s. sequence w sturmian if



x
∈
[
0
,
1
)


{\displaystyle x\in [0,1)}

, irrational



θ
∈
(
0
,
∞
)


{\displaystyle \theta \in (0,\infty )}

, w θ-coding of x.