On a group theoretic generalization of the Morse-Hedlund theorem

Abstract: In their 1938 seminal paper on symbolic dynamics, Morse and Hedlund proved that every aperiodic infinite word

x i n A^{N},

over a non empty finite alphabet

A,

contains at least

n + 1

distinct factors of each length

n .

They further showed that an infinite word

x

has exactly

n + 1

distinct factors of each length

n

if and only if

x

is binary, aperiodic and balanced, i.e.,

x

is a Sturmian word. In this paper we obtain a broad generalization of the Morse-Hedlund theorem via group actions. Given a subgroup

G

of the symmetric group

S_{n},

let

1 l e q e p s i l o n (G) l e q n

denote the number of distinct

G

-orbits of

1, 2, l d o t s, n .

Since

G

is a subgroup of

S_{n},

it acts on

A^{n} = a_{1} a_{2} c d o t s a_{n}, |, a_{i} i n A

by permutation. Thus, given an infinite word

x i n A^{N}

and an infinite sequence

o m e g a = (G_{n})_{n g e q 1}

of subgroups

G_{n} s u b s e t e q S_{n},

we consider the complexity function

p_{o m e g a, x} : N i g h t a r r o w N

which counts for each length

n

the number of equivalence classes of factors of

x

of length

n

under the action of

G_{n} .

We show that if

x

is aperiodic, then

p_{o m e g a, x} (n) g e q e p s i l o n (G_{n}) + 1

for each

n g e q 1,

and moreover, if equality holds for each

n,

then

x

is Sturmian. Conversely, let

x

be a Sturmian word. Then for every infinite sequence

o m e g a = (G_{n})_{n g e q 1}

of Abelian subgroups

G_{n} s u b s e t e q S_{n},

there exists

o m e g a^{'} = ({G_{n}}^{'})_{n g e q 1}

such that for each

n g e q 1 :

{G_{n}}^{'} s u b s e t e q S_{n}

is isomorphic to

G_{n}

and

p_{o m e g a^{'}, x} (n) = e p s i l o n (G'_{n}) + 1.

Applying the above results to the sequence

(I d_{n})_{n g e q 1},

where

I d_{n}

is the trivial subgroup of

S_{n}

consisting only of the identity, we recover both directions of the Morse-Hedland theorem.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: On a group theoretic generalization of the Morse-Hedlund theorem