Discussion Sturmian word

1 discussion

1.1 example
1.2 balanced aperiodic sequences
1.3 slope , intercept
1.4 frequencies

discussion
example

a famous example of (standard) sturmian word fibonacci word; slope



1

/

ϕ


{\displaystyle 1/\phi }

,



ϕ


{\displaystyle \phi }

golden ratio.

balanced aperiodic sequences

a set s of finite binary words balanced if each n subset sn of words of length n has property hamming weight of words in sn takes @ 2 distinct values. balanced sequence 1 set of factors balanced. balanced sequence has @ n+1 distinct factors of length n. aperiodic sequence 1 not consist of finite sequence followed finite cycle. aperiodic sequence has @ least n+1 distinct factors of length n. sequence sturmian if , if balanced , aperiodic.

slope , intercept

a sequence



(

a

n



)

n
∈

n





{\displaystyle (a_{n})_{n\in \mathbb {n} }}

on {0,1} sturmian word if , if there exist 2 real numbers, slope



α


{\displaystyle \alpha }

, intercept



ρ


{\displaystyle \rho }

,



α


{\displaystyle \alpha }

irrational, such that

a

n


=
⌊
α
(
n
+
1
)
+
ρ
⌋
−
⌊
α
n
+
ρ
⌋
−
⌊
α
⌋


{\displaystyle a_{n}=\lfloor \alpha (n+1)+\rho \rfloor -\lfloor \alpha n+\rho \rfloor -\lfloor \alpha \rfloor }

for



n


{\displaystyle n}

. sturmian word provides discretization of straight line slope



α


{\displaystyle \alpha }

, intercept ρ. without loss of generality, can assume



0
<
α
<
1


{\displaystyle 0<\alpha <1}

, because integer k have

⌊
(
α
+
k
)
(
n
+
1
)
+
ρ
⌋
−
⌊
(
α
+
k
)
n
+
ρ
⌋
−
⌊
α
+
k
⌋
=

a

n


.


{\displaystyle \lfloor (\alpha +k)(n+1)+\rho \rfloor -\lfloor (\alpha +k)n+\rho \rfloor -\lfloor \alpha +k\rfloor =a_{n}.}

all sturmian words corresponding same slope



α


{\displaystyle \alpha }

have same set of factors; word




c

α




{\displaystyle c_{\alpha }}

corresponding intercept



ρ
=
0


{\displaystyle \rho =0}

standard word or characteristic word of slope



α


{\displaystyle \alpha }

. hence, if



0
<
α
<
1


{\displaystyle 0<\alpha <1}

, characteristic word




c

α




{\displaystyle c_{\alpha }}

first difference of beatty sequence corresponding irrational number



α


{\displaystyle \alpha }

.

the standard word




c

α




{\displaystyle c_{\alpha }}

limit of sequence of words



(

s

n



)

n
≥
0




{\displaystyle (s_{n})_{n\geq 0}}

defined recursively follows:

let



[
0
;

d

1


+
1
,

d

2


,
…
,

d

n


,
…
]


{\displaystyle [0;d_{1}+1,d_{2},\ldots ,d_{n},\ldots ]}

continued fraction expansion of



α


{\displaystyle \alpha }

, , define

s

0


=
1


{\displaystyle s_{0}=1}







s

1


=
0


{\displaystyle s_{1}=0}







s

n
+
1


=

s

n



d

n





s

n
−
1



 for 

n
>
0


{\displaystyle s_{n+1}=s_{n}^{d_{n}}s_{n-1}{\text{ }}n>0}

where product between words concatenation. every word in sequence



(

s

n



)

n
>
0




{\displaystyle (s_{n})_{n>0}}

prefix of next ones, sequence converges infinite word,




c

α




{\displaystyle c_{\alpha }}

.

the infinite sequence of words



(

s

n



)

n
≥
0




{\displaystyle (s_{n})_{n\geq 0}}

defined above recursion called standard sequence standard word




c

α




{\displaystyle c_{\alpha }}

, , infinite sequence d = (d1, d2, d3, ...) of nonnegative integers, d1 ≥ 0 , dn > 0 (n ≥ 2), called directive sequence.

a sturmian word w on {0,1} characteristic if , if both 0w , 1w sturmian.

frequencies

if s infinite sequence word , w finite word, let μn(w) denote number of occurrences of w factor in prefix of s of length n+|w|-1. if μn(w) has limit n→∞, call frequency of w, denoted μ(w).

for sturmian word s, every finite factor has frequency. three-distance theorem states factors of fixed length n have @ 3 distinct frequencies, , if there 3 values 1 sum of other two.