DYNAMICS OF SOFIC SHIFTS

ALI AKBAR K.

Department of Mathematics, Central University of Kerala, Kasaragod (India).

E-mail: aliakbar.pkd@gmail.com, aliakbar@cukerala.ac.in

ORCID: https://orcid.org/0000-0003-3542-3727

Reception: 13/08/2022 Acceptance: 28/08/2022 Publication: 29/12/2022

Suggested citation:

Ali A. K. (2022). Dynamics of Soﬁc Shifts. 3C Tecnología. Glosas de innovación aplicada a la pyme,11 (2), 13-23.

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed. 42 Vol. 11 N.º 2 August - December 2022

ABSTRACT

In this paper, we provide a characterization for the subshifts of ﬁnite type (

SFT

) in terms of Cellular

automata (CA). In addition, we prove that

1. The following are equivalent for a non-singleton subshift of ﬁnite type XF.

a) XFis transitive and P er(XF), the set of periodic points of XF, is coﬁnite

b) XFis weak mixing

c) XFis mixing.

2. For non-singleton soﬁc shifts, only the statements (a)and (b)are equivalent.

KEYWORDS

subshift of ﬁnite type, soﬁc shifts, mixing, strongly connected digraph, labeled digraph, cellular automata

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

1 INTRODUCTION AND PRELIMINARIES

A dynamical system is a pair (

X, f

), where

is a metric space and

is a continuous self map. For

each dynamical system (

X, f

), the period set

Per

(

{n∈N

∃x∈X

such that

(

x

(

)

∀m<n}

consisting of the lengths of the cycles there, is a subset of the set

of positive integers.

We say that a point

x∈X

is periodic if

fnx

for some

n∈N

, where

is the composition of

with itself

times. The smallest such positive integer

is called the period of

. Two dynamical

systems (

X, f

),(

Y,g

)are said to be topological conjugate if there exists a homeomorphism

X→Y

such that

h◦f

g◦h

. If there is a continuous surjection

X→Y

such that

h◦f

g◦h

then

we say that (

Y,g

)is a factor of (

X, f

). A dynamical system (

X, f

)is said to be transitive if for any

non-empty open sets

U, V

there exists

n∈N

such that

(

)

∩V

∅

and is said to be mixing if

for any non-empty open sets

U, V

there exists

n∈N

such that

(

)

∩V

∅

for all

m≥n

dynamical system (

X, f

)is said to be weak mixing, if given any four nonempty open sets

U1,V

1,U

2,V

in Xthere exists m∈Nsuch that fm(U1)∩V1and fm(U2)∩V2are non-empty.

The subshifts form an important class of dynamical systems, because almost all dynamical systems

are factor of some subshifts. There are plenty of books that explain how their study would throw light on

still larger classes of dynamical systems (see [7], [10] and [14]). There are some dynamical systems such

that the notions transitivity together with coﬁniteness, weak mixing, and mixing which are equivalent

(See [5], [8] for interval maps, See [2] for topological graph maps). It is natural to ask on which spaces a

similar result will be true. We ﬁnd that the same result is true in the class of non-singleton

SFT

s, and in

the class of continuous 2-dimensional toral automorphisms. Note that

SFT

s, continuous 2-dimensional

toral automorphisms and topological graph maps are diﬀerent kinds of dynamical systems, and we

cannot hope to have a similarity of proofs. In this paper, we concentrate on two-sided shifts. The case

of one-sided shifts is similar.

Let

be a non-empty ﬁnite set (called alphabet) with discrete topology and consider the set

which denotes the set of doubly-inﬁnite sequences (

)

i∈Z

where each

xi∈A

, with product topology. It

is compact and metrizable. The shift is the homeomorphism

AZ→A

given by

(

)

xi+1

for all

i∈Z

. A subset

A⊂A

is called

-invariant if

(

)

⊂A

. The pair (

AZ,σ

)forms a dynamical system

called a full shift. A subshift is a

- invariant non-empty closed subset

of a full shift, together with

the restriction of

. We denote the set of periods of all periodic points of

P er

(

). We

call

P er

(

)the period set of

. A word

is a concatenation

w1w2...wk

, where each

wi∈A

and (

)

whenever

n≡r

(

mod k

). A subshift

is said to be a subshift of ﬁnite type (SFT) if

{x∈A

:no word in

occurs in

for some ﬁnite set of words

. A subshift

X⊂A

called soﬁc if it is a factor of an SFT.

The notion of strongly connected digraphs is well known. For every SFT, there is an associated

digraph and an associated matrix as described in [7]. This may or may not be strongly connected. Let

V,E

)be any directed graph (digraph) with vertex set

and edge set

. A subgraph

G′

V′,E′

)

is said to be a full subgraph if

E′

E∩{

(

v1,v

2∈V′}

. A digraph is said to be simple if

from every vertex

to a vertex

there is atmost one edge and it is said to be strongly connected if for

every pair of vertices there exists a directed path. It is to be noted that a connected digraph may not

be strongly connected. The SFT associated for a digraph

is denoted as

and the SFT associated

for an

m×m

matrix

with entries 0or 1is denoted as

. Let

V′

{v∈V

:there exists a cycle

through this

. Consider a full subgraph of a simple digraph

with vertex set

V′

, say

G′

V′,E′

Deﬁne a relation

V′

in such a way that

xRy

if there is a directed path from

and from

. Then

is an equivalence relation on the set of vertices

V′

. Let

G′

be the full subgraph of

G′

with [

], equivalence class of

, as the vertex set. This

G′

is strongly connected simple digraph and

G′

can be written as a ﬁnite union of such strongly connected simple digraphs, say

n

i=1 Gi

. The SFT

associated for a simple digraph Gis denoted as XG. Note that P er(XG)=P er(XG′).

Let

be an alphabet having atleast two elements. Let

r∈N0

. A function

A2r+1 →A

is called a

local rule. It induces a function F:AZ→A

Zby the rule

(

))

(

xn−r,x

n−r−1, ..., xn−1,x

n,x

n+1, ..., xn+r−1,x

n+r

)for all

n∈Z

. The pair (

AZ,F

)(sim-

ply the map

AZ→A

) is called a cellular automaton (abbreviated as

). A map

AZ→A

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed. 42 Vol. 11 N.º 2 August - December 2022

ABSTRACT

In this paper, we provide a characterization for the subshifts of ﬁnite type (

SFT

) in terms of Cellular

automata (CA). In addition, we prove that

1. The following are equivalent for a non-singleton subshift of ﬁnite type XF.

a) XFis transitive and P er(XF), the set of periodic points of XF, is coﬁnite

b) XFis weak mixing

c) XFis mixing.

2. For non-singleton soﬁc shifts, only the statements (a)and (b)are equivalent.

KEYWORDS

subshift of ﬁnite type, soﬁc shifts, mixing, strongly connected digraph, labeled digraph, cellular automata

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

1 INTRODUCTION AND PRELIMINARIES

A dynamical system is a pair (

X, f

), where

is a metric space and

is a continuous self map. For

each dynamical system (

X, f

), the period set

Per

(

{n∈N

∃x∈X

such that

(

x

(

)

∀m<n}

consisting of the lengths of the cycles there, is a subset of the set

of positive integers.

We say that a point

x∈X

is periodic if

fnx

for some

n∈N

, where

is the composition of

with itself

times. The smallest such positive integer

is called the period of

. Two dynamical

systems (

X, f

),(

Y,g

)are said to be topological conjugate if there exists a homeomorphism

X→Y

such that

h◦f

g◦h

. If there is a continuous surjection

X→Y

such that

h◦f

g◦h

then

we say that (

Y,g

)is a factor of (

X, f

). A dynamical system (

X, f

)is said to be transitive if for any

non-empty open sets

U, V

there exists

n∈N

such that

(

)

∩V

∅

and is said to be mixing if

for any non-empty open sets

U, V

there exists

n∈N

such that

(

)

∩V

∅

for all

m≥n

dynamical system (

X, f

)is said to be weak mixing, if given any four nonempty open sets

U1,V

1,U

2,V

in Xthere exists m∈Nsuch that fm(U1)∩V1and fm(U2)∩V2are non-empty.

The subshifts form an important class of dynamical systems, because almost all dynamical systems

are factor of some subshifts. There are plenty of books that explain how their study would throw light on

still larger classes of dynamical systems (see [7], [10] and [14]). There are some dynamical systems such

that the notions transitivity together with coﬁniteness, weak mixing, and mixing which are equivalent

(See [5], [8] for interval maps, See [2] for topological graph maps). It is natural to ask on which spaces a

similar result will be true. We ﬁnd that the same result is true in the class of non-singleton

SFT

s, and in

the class of continuous 2-dimensional toral automorphisms. Note that

SFT

s, continuous 2-dimensional

toral automorphisms and topological graph maps are diﬀerent kinds of dynamical systems, and we

cannot hope to have a similarity of proofs. In this paper, we concentrate on two-sided shifts. The case

of one-sided shifts is similar.

Let

be a non-empty ﬁnite set (called alphabet) with discrete topology and consider the set

which denotes the set of doubly-inﬁnite sequences (

)

i∈Z

where each

xi∈A

, with product topology. It

is compact and metrizable. The shift is the homeomorphism

AZ→A

given by

(

)

xi+1

for all

i∈Z

. A subset

A⊂A

is called

-invariant if

(

)

⊂A

. The pair (

AZ,σ

)forms a dynamical system

called a full shift. A subshift is a

- invariant non-empty closed subset

of a full shift, together with

the restriction of

. We denote the set of periods of all periodic points of

P er

(

). We

call

P er

(

)the period set of

. A word

is a concatenation

w1w2...wk

, where each

wi∈A

and (

)

whenever

n≡r

(

mod k

). A subshift

is said to be a subshift of ﬁnite type (SFT) if

{x∈A

:no word in

occurs in

for some ﬁnite set of words

. A subshift

X⊂A

called soﬁc if it is a factor of an SFT.

The notion of strongly connected digraphs is well known. For every SFT, there is an associated

digraph and an associated matrix as described in [7]. This may or may not be strongly connected. Let

V,E

)be any directed graph (digraph) with vertex set

and edge set

. A subgraph

G′

V′,E′

)

is said to be a full subgraph if

E′

E∩{

(

v1,v

2∈V′}

. A digraph is said to be simple if

from every vertex

to a vertex

there is atmost one edge and it is said to be strongly connected if for

every pair of vertices there exists a directed path. It is to be noted that a connected digraph may not

be strongly connected. The SFT associated for a digraph

is denoted as

and the SFT associated

for an

m×m

matrix

with entries 0or 1is denoted as

. Let

V′

{v∈V

:there exists a cycle

through this

. Consider a full subgraph of a simple digraph

with vertex set

V′

, say

G′

V′,E′

Deﬁne a relation

V′

in such a way that

xRy

if there is a directed path from

and from

. Then

is an equivalence relation on the set of vertices

V′

. Let

G′

be the full subgraph of

G′

with [

], equivalence class of

, as the vertex set. This

G′

is strongly connected simple digraph and

G′

can be written as a ﬁnite union of such strongly connected simple digraphs, say

n

i=1 Gi

. The SFT

associated for a simple digraph Gis denoted as XG. Note that P er(XG)=P er(XG′).

Let

be an alphabet having atleast two elements. Let

r∈N0

. A function

A2r+1 →A

is called a

local rule. It induces a function F:AZ→A

Zby the rule

(

))

(

xn−r,x

n−r−1, ..., xn−1,x

n,x

n+1, ..., xn+r−1,x

n+r

)for all

n∈Z

. The pair (

AZ,F

)(sim-

ply the map

AZ→A

) is called a cellular automaton (abbreviated as

). A map

AZ→A

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed. 42 Vol. 11 N.º 2 August - December 2022

a cellular automaton if and only if it is continuous and commutes with the shift (see [13]).

Our main results prove that:

Let (

AZ,F

)be any

. Then

F ix

(

)is an

SFT

or empty set. Conversely given any

SFT X

there exists a CA Fsuch that F ix(F)=X.

2. The following are equivalent for a subset Sof N.

a) S=Per(X)for some mixing subshift of ﬁnite type X.

b) Either S={1}or N\Ffor some ﬁnite subset Fof N.

3. a) The following are equivalent for a non-singleton SFT X.

i. Xis transitive and P er(X)is coﬁnite

ii. Xis weak mixing

iii. Xis mixing.

In general, in the case of non-singleton soﬁc shifts, only the statements 3(a)ii and 3(a)iii are

equivalent.

The results are intuitive in nature and provide a basic understanding of the dynamics of shift spaces.

This review article will be useful to any reader interested in understanding basics of dynamics of shift

spaces.

SUBSHIFTS OF FINITE TYPE AND SOFIC SHIFTS: TRANSITIVITY, WEAK

MIXING, MIXING

One of the result in this paper is motivated by the following two known theorems.

Theorem 1. The following are equivalent for a topological graph map

G→G

(See [5], [8] for

interval maps, See [2] for topological graph maps).

1. fis transitive and P er(f)is coﬁnite (ie., N\P er(f)is ﬁnite)

2. fis weak mixing

3. fis mixing.

Theorem 2. The following are equivalent for a continuous toral automorphism T:T2→T2.

1. Tis transitive and P er(T)is coﬁnite (ie., N\P er(T)is ﬁnite)

2. Tis weak mixing

3. Tis mixing.

Proof. Proof follows from the main results of [16] and [17].

2.1 SUBSHIFTS OF FINITE TYPE

Let

be a

k×k

adjacency matrix (i.e., the matrix with entries 0or 1). We call the matrix primitive if

there exists N∈Nsuch that AN>0. Now we consider the following known proposition.

Proposition 1. [7] An

SFT

induced by a matrix

with non-zero rows and columns is mixing if and

only if Ais primitive.

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

Next we state the following known theorem. We denote any ﬁnite subset

A⊂⊂ N

, and

gcd for the greatest common divisor.

Theorem 3. [1] The following are equivalent for a subset Sof N.

1. S

Per

(

)for some strongly connected simple digraph

containing cycles of lengths

m1, ..., mk

such that gcd(m1,m

2, ..., mk)=1.

2. Either S={1}or S=N\Ffor some F⊂⊂ N.

Next we have:

Theorem 4. A strongly connected simple digraph

induced by an adjacency matrix

Ak×k

with non

zero rows and columns contains cycles of lengths

m1,m

2, ..., mk

such that

gcd

(

m1,m

2, ..., mk

)=1if

and only if Ais primitive.

Proof. Suppose that

is a strongly connected simple digraph, and contains cycles of lengths

m1,m

2, ..., mk

such that

gcd

(

m1,m

2, ..., mk

)=1. Without loss of generality we can assume that

these are simple cycles of

that contain all vertices. By a basic number theory result, there exists

n0∈N

F⊂⊂ N

such that for all

n≥n0

n∈N\F

there exist

a1,a

2, ..., ak∈N

such that

a1m1

a2m2

...

akmk

. Therefore, given any vertex

there exists a cycle of length

for all

n≥n0

. Let

diam

(

Max{l

(

x, y

x, y ∈V

(

)

}

where

(

x, y

)denotes the length of a directed

path from

. Let

. Hence

AN>

0since for every

x, y ∈V

(

)there exists a path of

length

for all

p≤m

and for every

x∈V

(

)there exists a cycle of length

for all

n≥n0

. Write

N=n0+m−p+p. Hence Ais primitive.

Conversely, suppose that

is primitive and

gcd

(

m1,m

2, ..., ml

1for all cycles of length

≤i≤p

p∈N

. Let

gcd

of lengths of all cycles of

. Then there exist cycles of length

m1,m

2, ..., ml

such that

gcd

(

m1,m

2, ..., ml

. Then

divides the lengths of all cycles. Also, there

exists

s∈N

such that

As>

0, and for every

x, y ∈V

(

)there exists a path of length

from

since

is primitive and

is strongly connected. Therefore

divides

and

+1, which implies

=1.

A contradiction. Hence the proof.

Corollary 1. A strongly connected simple digraph

contains cycles of length

m1, ..., mk

such that

gcd(m1,m

2, ..., mn)=1if and only if XGis mixing.

Proof. This follows from Proposition 1, Theorems 3 and 4.

Corollary 2. The following are equivalent for a subset Sof N.

1. S=Per(X)for some mixing subshift of ﬁnite type X.

2. Either S={1}or N\Ffor some ﬁnite subset Fof N.

Proof. Proof follows from Theorems 3, 4, and Corollary 1.

The proof of the following theorem relies mostly on the proof of Proposition 1, as given in [7].

Lemma 1. An

SFT XA

is weak mixing if and only if for every 1

≤i1,j

1,i

2,j

2≤k

there exists

n∈N

such that An(i1,j

1)>0and An(i2,j

2)>0where Adenotes a k×kadjacency matrix.

Proof. Assume that XAis weak mixing. Let U1={(xn)n∈Z∈XA:x0=i1},V1={(xn)n∈Z∈XA:

j1}

{

(

)

n∈Z∈XA

i2}

and

{

(

)

n∈Z∈XA

j2}

where 1

≤i1,j

1,i

2,j

2≤k

These sets are open. Then there exists

n∈N

such that

σn

(

)

∩Vi

∅

2. Hence

i1,y

i2,x

and

. Note that

(

i, j

k

r1=1 ... k

rN−1=1 A

(

i, r1

)

(

r1,r

)

...A

(

rN−2,r

N−1

)

(

rN−1,j

)

for all

N∈N

. But

(

i1,x

(

x1,x

(

x2,x

...

(

xn−1,j

)=1and

(

i2,y

A(y1,y

2)=A(y2,y

3)=... =A(yn−1,j

2)=1. Therefore An(i1,j

1)>0and An(i2,j

2)>0.

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed. 42 Vol. 11 N.º 2 August - December 2022

a cellular automaton if and only if it is continuous and commutes with the shift (see [13]).

Our main results prove that:

Let (

AZ,F

)be any

. Then

F ix

(

)is an

SFT

or empty set. Conversely given any

SFT X

there exists a CA Fsuch that F ix(F)=X.

2. The following are equivalent for a subset Sof N.

a) S=Per(X)for some mixing subshift of ﬁnite type X.

b) Either S={1}or N\Ffor some ﬁnite subset Fof N.

3. a) The following are equivalent for a non-singleton SFT X.

i. Xis transitive and P er(X)is coﬁnite

ii. Xis weak mixing

iii. Xis mixing.

In general, in the case of non-singleton soﬁc shifts, only the statements 3(a)ii and 3(a)iii are

equivalent.

The results are intuitive in nature and provide a basic understanding of the dynamics of shift spaces.

This review article will be useful to any reader interested in understanding basics of dynamics of shift

spaces.

SUBSHIFTS OF FINITE TYPE AND SOFIC SHIFTS: TRANSITIVITY, WEAK

MIXING, MIXING

One of the result in this paper is motivated by the following two known theorems.

Theorem 1. The following are equivalent for a topological graph map

G→G

(See [5], [8] for

interval maps, See [2] for topological graph maps).

1. fis transitive and P er(f)is coﬁnite (ie., N\P er(f)is ﬁnite)

2. fis weak mixing

3. fis mixing.

Theorem 2. The following are equivalent for a continuous toral automorphism T:T2→T2.

1. Tis transitive and P er(T)is coﬁnite (ie., N\P er(T)is ﬁnite)

2. Tis weak mixing

3. Tis mixing.

Proof. Proof follows from the main results of [16] and [17].

2.1 SUBSHIFTS OF FINITE TYPE

Let

be a

k×k

adjacency matrix (i.e., the matrix with entries 0or 1). We call the matrix primitive if

there exists N∈Nsuch that AN>0. Now we consider the following known proposition.

Proposition 1. [7] An

SFT

induced by a matrix

with non-zero rows and columns is mixing if and

only if Ais primitive.

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

Next we state the following known theorem. We denote any ﬁnite subset

A⊂⊂ N

, and

gcd for the greatest common divisor.

Theorem 3. [1] The following are equivalent for a subset Sof N.

1. S

Per

(

)for some strongly connected simple digraph

containing cycles of lengths

m1, ..., mk

such that gcd(m1,m

2, ..., mk)=1.

2. Either S={1}or S=N\Ffor some F⊂⊂ N.

Next we have:

Theorem 4. A strongly connected simple digraph

induced by an adjacency matrix

Ak×k

with non

zero rows and columns contains cycles of lengths

m1,m

2, ..., mk

such that

gcd

(

m1,m

2, ..., mk

)=1if

and only if Ais primitive.

Proof. Suppose that

is a strongly connected simple digraph, and contains cycles of lengths

m1,m

2, ..., mk

such that

gcd

(

m1,m

2, ..., mk

)=1. Without loss of generality we can assume that

these are simple cycles of

that contain all vertices. By a basic number theory result, there exists

n0∈N

F⊂⊂ N

such that for all

n≥n0

n∈N\F

there exist

a1,a

2, ..., ak∈N

such that

a1m1

a2m2

...

akmk

. Therefore, given any vertex

there exists a cycle of length

for all

n≥n0

. Let

diam

(

Max{l

(

x, y

x, y ∈V

(

)

}

where

(

x, y

)denotes the length of a directed

path from

. Let

. Hence

AN>

0since for every

x, y ∈V

(

)there exists a path of

length

for all

p≤m

and for every

x∈V

(

)there exists a cycle of length

for all

n≥n0

. Write

N=n0+m−p+p. Hence Ais primitive.

Conversely, suppose that

is primitive and

gcd

(

m1,m

2, ..., ml

1for all cycles of length

≤i≤p

p∈N

. Let

gcd

of lengths of all cycles of

. Then there exist cycles of length

m1,m

2, ..., ml

such that

gcd

(

m1,m

2, ..., ml

. Then

divides the lengths of all cycles. Also, there

exists

s∈N

such that

As>

0, and for every

x, y ∈V

(

)there exists a path of length

from

since

is primitive and

is strongly connected. Therefore

divides

and

+1, which implies

=1.

A contradiction. Hence the proof.

Corollary 1. A strongly connected simple digraph

contains cycles of length

m1, ..., mk

such that

gcd(m1,m

2, ..., mn)=1if and only if XGis mixing.

Proof. This follows from Proposition 1, Theorems 3 and 4.

Corollary 2. The following are equivalent for a subset Sof N.

1. S=Per(X)for some mixing subshift of ﬁnite type X.

2. Either S={1}or N\Ffor some ﬁnite subset Fof N.

Proof. Proof follows from Theorems 3, 4, and Corollary 1.

The proof of the following theorem relies mostly on the proof of Proposition 1, as given in [7].

Lemma 1. An

SFT XA

is weak mixing if and only if for every 1

≤i1,j

1,i

2,j

2≤k

there exists

n∈N

such that An(i1,j

1)>0and An(i2,j

2)>0where Adenotes a k×kadjacency matrix.

Proof. Assume that XAis weak mixing. Let U1={(xn)n∈Z∈XA:x0=i1},V1={(xn)n∈Z∈XA:

j1}

{

(

)

n∈Z∈XA

i2}

and

{

(

)

n∈Z∈XA

j2}

where 1

≤i1,j

1,i

2,j

2≤k

These sets are open. Then there exists

n∈N

such that

σn

(

)

∩Vi

∅

2. Hence

i1,y

i2,x

and

. Note that

(

i, j

k

r1=1 ... k

rN−1=1 A

(

i, r1

)

(

r1,r

)

...A

(

rN−2,r

N−1

)

(

rN−1,j

)

for all

N∈N

. But

(

i1,x

(

x1,x

(

x2,x

...

(

xn−1,j

)=1and

(

i2,y

A(y1,y

2)=A(y2,y

3)=... =A(yn−1,j

2)=1. Therefore An(i1,j

1)>0and An(i2,j

2)>0.

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed. 42 Vol. 11 N.º 2 August - December 2022

Conversely, assume that for every 1

≤i1,j

1,i

2,j

2≤k

there exists

N∈N

such that

(

i1,j

)

0and

(

i2,j

)

0. Given non-empty open sets

U1,V

1,U

2,V

we can choose (

i(l)

)

n∈Z∈Ul

and (

j(l)

)

n∈Z∈Vl

such that for

0suﬃciently large; and

Ul⊃{

(

)

n∈Z∈XA

i(l)

k,−M≤k≤M}

Vl⊃{

(

)

n∈Z∈XA

j(l)

k,−M≤k≤M}

for

2(It is possible since the set of symmetric

cylinders form a base for the topology on AZ).

By hypothesis, there exists

0such that

(

i(l)

M,j(l)

−M

)

0for

2. This means we can ﬁnd

a word xl

1...xl

N−1such that A(i(l)

M,x

1)=A(xl

1,x

2)=... =A(xl

N−1,j(l)

−M)=1.

Deﬁne x(l)

n=









i(l)

nif n≤M

n−Mif M+1≤n≤M+N−1

j(l)

n−(2M+N)if M+N≤n

Then σ2M+N(Ul)∩Vl=∅for l=1,2. Hence XAis weak mixing.

Next we have:

Theorem 5. An SFT is weak mixing if and only if it is mixing.

Proof. Let

be an adjacency matrix of order

. Assume that

is weak mixing. We have to prove

that there exist cycles of lengths

m1,m

2, ..., mp

such that

gcd

(

m1,m

2, ..., mp

)=1. Suppose not. Then

there exists

s∈N\{

}

such that

divides the lengths of all cycles (let

gcd

of lengths all cycles).

Let 1

≤v1,w

1,v

2≤k

be such that

v1w1

is a block in

for some

x∈XA

. Then there exist a cycle of

length

through

and a path of length

from

, which implies

divides

and

+1. Hence

s=1. A contradiction. Hence XAis mixing. Converse part is easy.

Hence we have:

Theorem 6. The following are equivalent for a non-singleton SFT XF.

(i)XFis transitive and Per(XF)is coﬁnite.

1. XFis weak mixing.

2. XFis mixing.

Proof. We ﬁrst observe that the period set

Per

(

)of a ﬁnite

SFT XF

is ﬁnite. So

Per

(

)is not

coﬁnite. Except singleton

SFT

s all other ﬁnite

SFT

s are not weak mixing and hence not mixing. Hence

the theorem follows from Theorems 3, 4 and 5, and Proposition 1.

Remark 1. Suppose some rows of

or columns of

is of full of zeros, say

th row and

th column.

Then remove

th row and

th column. Doing this for all such

and

, we obtain another matrix

smaller size. Then

and

X˜

are in a sense one and the same. Therefore the equivalence of (2) and

(3) is true for all subshifts induced by adjacency matrices.

Next we consider:

Theorem 7. (see [15]) (Blokh, Barge-Martin) Let

I→I

be an interval map such that the periodic

points are dense in

. Then the interval

decomposes into transitive components

in the following

way.

1. Cn

is a closed non-degenerate interval or

is the union of two disjoint closed non degenerate

intervals,

2. f|Cnis transitive,

3. the complement set of Cnis included in {x∈X:f2(x)=x}.

In addition, the number of transitive components

is ﬁnite or countable and their interiors are

pairwise disjoint.

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

As similar to Theorem 7, now we have:

Theorem 8. Let

be an

SFT

for some ﬁnite set of words

over an alphabet

with dense set of

periodic points. Then there exists some ﬁnite set of words

G⊃F

, and an

SFT XG

with dense set of

periodic points and it is a ﬁnite union of transitive SFTs, and Per(XF)=Per(XG).

Proof. Let

denotes the subshift of ﬁnite type associated for a simple digraph

such that

. Let

be the set of all vertices of

. For

v1,v

2∈V

, we say that

v1∼v2

whenever there is a

path from

and vice-versa. Then

∼

forms an equivalence relation on

. Each equivalence class

corresponds to a strongly connected simple digraphs. Let

G′

be the union of all such strongly connected

simple digraphs. Observe that

P er

(

P er

(

XG′

). Now consider

G⊃F

such that

XG′

. Hence

the proof.

Consider a countable set

{

, ...}

. With the discrete topology it is a non-compact metrizable space.

Let



{

, ...}Z

. With product topology



is a totally disconnected, perfect and non-compact

metric space. As in the ﬁnite case, the cylinder sets form a countable basis of clopen sets. The shift,

, is a homeomorphism of the space to itself. The dynamical system (

,σ

)is the full shift on the

symbols. If

is a countable, zero-one matrix, then as in the ﬁnite case, we use transition rules to

deﬁne a shift-invariant subset of the full shift on countably many symbols, denoted by

A

. Then the

subspace

A



is non-compact, metrizable and

A→A

is the countable state Markov shift

deﬁned by A.

Next consider the following two known propositions.

Proposition 2. [12] A countable state Markov shift

A

is topologically transitive if and only if

irreducible.

Proposition 3. [12] A countable state Markov shift

A

is topologically mixing if and only if

primitive.

Now we have:

Theorem 9. [12] The following are equivalent for countable Markov shift σ:A→A.

(i)σ:A→Ais transitive and Per(σ)is coﬁnite.

(ii)σ:A→Ais weak mixing.

(iii)σ:A→Ais mixing.

Proof. The proof follows from Propositions 2 and 3.

2.2 SOFIC SHIFTS

The notion of labeled digraph is well known (see [14], [7]). For every soﬁc shift there is a labeled digraph

and vice versa (see [7]). As similar to digraphs, we can deﬁne simple labeled digraph and strongly

connected labeled digraph. First we have to deﬁne it for corresponding digraphs. Then consider the

corresponding labeled digraphs. As similar to digraphs, for every labeled digraph Γthere exists another

labeled digraph Γ

′

such that

Per

(

XΓ

Per

(

XΓ′

)and Γ

′

is a ﬁnite union of strongly connected simple

labeled digraphs where

XΓ

denotes the subshift induced by Γ. Let Γbe a ﬁnite labeled digraph, the

edges of Γare labeled by an alphabet

{

, ..., m}

. Note that we do not assume that the diﬀerent

edges of Γare labeled diﬀerently. Let

(Γ) denotes the set of all edges of Γ. The subset

XΓ⊂A

consisting of all inﬁnite directed paths in Γis closed and shift invariant. If a subshift

is topologically

conjugate to XΓfor some labeled digraph Γ, then we say that Γis a presentation of X.

Proposition 4. [7] A subshift

X⊂A

is soﬁc if and only if it admits a presentation by a ﬁnite

labeled digraph.

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed. 42 Vol. 11 N.º 2 August - December 2022

Conversely, assume that for every 1

≤i1,j

1,i

2,j

2≤k

there exists

N∈N

such that

(

i1,j

)

0and

(

i2,j

)

0. Given non-empty open sets

U1,V

1,U

2,V

we can choose (

i(l)

)

n∈Z∈Ul

and (

j(l)

)

n∈Z∈Vl

such that for

0suﬃciently large; and

Ul⊃{

(

)

n∈Z∈XA

i(l)

k,−M≤k≤M}

Vl⊃{

(

)

n∈Z∈XA

j(l)

k,−M≤k≤M}

for

2(It is possible since the set of symmetric

cylinders form a base for the topology on AZ).

By hypothesis, there exists

0such that

(

i(l)

M,j(l)

−M

)

0for

2. This means we can ﬁnd

a word xl

1...xl

N−1such that A(i(l)

M,x

1)=A(xl

1,x

2)=... =A(xl

N−1,j(l)

−M)=1.

Deﬁne x(l)

n=









i(l)

nif n≤M

n−Mif M+1≤n≤M+N−1

j(l)

n−(2M+N)if M+N≤n

Then σ2M+N(Ul)∩Vl=∅for l=1,2. Hence XAis weak mixing.

Next we have:

Theorem 5. An SFT is weak mixing if and only if it is mixing.

Proof. Let

be an adjacency matrix of order

. Assume that

is weak mixing. We have to prove

that there exist cycles of lengths

m1,m

2, ..., mp

such that

gcd

(

m1,m

2, ..., mp

)=1. Suppose not. Then

there exists

s∈N\{

}

such that

divides the lengths of all cycles (let

gcd

of lengths all cycles).

Let 1

≤v1,w

1,v

2≤k

be such that

v1w1

is a block in

for some

x∈XA

. Then there exist a cycle of

length

through

and a path of length

from

, which implies

divides

and

+1. Hence

s=1. A contradiction. Hence XAis mixing. Converse part is easy.

Hence we have:

Theorem 6. The following are equivalent for a non-singleton SFT XF.

(i)XFis transitive and Per(XF)is coﬁnite.

1. XFis weak mixing.

2. XFis mixing.

Proof. We ﬁrst observe that the period set

Per

(

)of a ﬁnite

SFT XF

is ﬁnite. So

Per

(

)is not

coﬁnite. Except singleton

SFT

s all other ﬁnite

SFT

s are not weak mixing and hence not mixing. Hence

the theorem follows from Theorems 3, 4 and 5, and Proposition 1.

Remark 1. Suppose some rows of

or columns of

is of full of zeros, say

th row and

th column.

Then remove

th row and

th column. Doing this for all such

and

, we obtain another matrix

smaller size. Then

and

X˜

are in a sense one and the same. Therefore the equivalence of (2) and

(3) is true for all subshifts induced by adjacency matrices.

Next we consider:

Theorem 7. (see [15]) (Blokh, Barge-Martin) Let

I→I

be an interval map such that the periodic

points are dense in

. Then the interval

decomposes into transitive components

in the following

way.

1. Cn

is a closed non-degenerate interval or

is the union of two disjoint closed non degenerate

intervals,

2. f|Cnis transitive,

3. the complement set of Cnis included in {x∈X:f2(x)=x}.

In addition, the number of transitive components

is ﬁnite or countable and their interiors are

pairwise disjoint.

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

As similar to Theorem 7, now we have:

Theorem 8. Let

be an

SFT

for some ﬁnite set of words

over an alphabet

with dense set of

periodic points. Then there exists some ﬁnite set of words

G⊃F

, and an

SFT XG

with dense set of

periodic points and it is a ﬁnite union of transitive SFTs, and Per(XF)=Per(XG).

Proof. Let

denotes the subshift of ﬁnite type associated for a simple digraph

such that

. Let

be the set of all vertices of

. For

v1,v

2∈V

, we say that

v1∼v2

whenever there is a

path from

and vice-versa. Then

∼

forms an equivalence relation on

. Each equivalence class

corresponds to a strongly connected simple digraphs. Let

G′

be the union of all such strongly connected

simple digraphs. Observe that

P er

(

P er

(

XG′

). Now consider

G⊃F

such that

XG′

. Hence

the proof.

Consider a countable set

{

, ...}

. With the discrete topology it is a non-compact metrizable space.

Let



{

, ...}Z

. With product topology



is a totally disconnected, perfect and non-compact

metric space. As in the ﬁnite case, the cylinder sets form a countable basis of clopen sets. The shift,

, is a homeomorphism of the space to itself. The dynamical system (

,σ

)is the full shift on the

symbols. If

is a countable, zero-one matrix, then as in the ﬁnite case, we use transition rules to

deﬁne a shift-invariant subset of the full shift on countably many symbols, denoted by

A

. Then the

subspace

A



is non-compact, metrizable and

A→A

is the countable state Markov shift

deﬁned by A.

Next consider the following two known propositions.

Proposition 2. [12] A countable state Markov shift

A

is topologically transitive if and only if

irreducible.

Proposition 3. [12] A countable state Markov shift

A

is topologically mixing if and only if

primitive.

Now we have:

Theorem 9. [12] The following are equivalent for countable Markov shift σ:A→A.

(i)σ:A→Ais transitive and Per(σ)is coﬁnite.

(ii)σ:A→Ais weak mixing.

(iii)σ:A→Ais mixing.

Proof. The proof follows from Propositions 2 and 3.

2.2 SOFIC SHIFTS

The notion of labeled digraph is well known (see [14], [7]). For every soﬁc shift there is a labeled digraph

and vice versa (see [7]). As similar to digraphs, we can deﬁne simple labeled digraph and strongly

connected labeled digraph. First we have to deﬁne it for corresponding digraphs. Then consider the

corresponding labeled digraphs. As similar to digraphs, for every labeled digraph Γthere exists another

labeled digraph Γ

′

such that

Per

(

XΓ

Per

(

XΓ′

)and Γ

′

is a ﬁnite union of strongly connected simple

labeled digraphs where

XΓ

denotes the subshift induced by Γ. Let Γbe a ﬁnite labeled digraph, the

edges of Γare labeled by an alphabet

{

, ..., m}

. Note that we do not assume that the diﬀerent

edges of Γare labeled diﬀerently. Let

(Γ) denotes the set of all edges of Γ. The subset

XΓ⊂A

consisting of all inﬁnite directed paths in Γis closed and shift invariant. If a subshift

is topologically

conjugate to XΓfor some labeled digraph Γ, then we say that Γis a presentation of X.

Proposition 4. [7] A subshift

X⊂A

is soﬁc if and only if it admits a presentation by a ﬁnite

labeled digraph.

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed. 42 Vol. 11 N.º 2 August - December 2022

Theorem 10. [1] The following are equivalent for a subset Sof N.

(1)

Per

(

XΓ

)for some strongly connected labeled digraph Γcontaining cycles of length

m1,m

2, ..., mk

such that gcd(m1,m

2, ..., mk)=1.

(2) Either S={1}or S=N\Ffor some F⊂⊂ N.

From the deﬁnition of transitivity, mixing, weak mixing and by using some ideas from Lemma 1, we

can prove the following lemma for any directed labeled graph Γ. Recall that for every non-empty open

set

XΓ

we can choose (

)

n∈Z∈U

such that for

0suﬃciently large;

U⊃{

(

)

n∈Z

ik,−M≤k≤M}.

Lemma 2. Let Γbe a labeled digraph. Then the following are true.

1. XΓ

is transitive if and only if for every

i, j ∈E

(Γ) there exists a directed path of length

from

to jfor some n∈N.

2. XΓ

is weak mixing if and only if for every

i1,j

1,i

2,j

2∈E

(Γ) there exist directed paths of length

nfrom i1to j1and from i2to j2for some n∈N.

3. XΓ

is mixing if and only if for every

i, j ∈E

(Γ) there exists

N∈N

such that for all

n≥N

there

is a directed path of length nfrom ito j.

Theorem 11. Let Γbe a strongly connected labeled digraph. Then Γcontains cycles of lengths

m1,m

2, ..., mksuch that gcd(m1,m

2, ..., mk)=1if and only if XΓis mixing.

Proof. We can provide a proof similar to that of Theorem 4. Here while proceeding the proof without

loss of generality it is not possible to assume the cycles are simple. Still the conclusion is true.

Corollary 3. The period set of a mixing SFT is

either {1}or N\Ffor some F⊂⊂ N.

Proof. Proof follows from Theorems 10 and 11.

Theorem 12. A soﬁc shift is weak mixing if and only if it is mixing.

Proof. Because of Lemma 2 and Theorem 11, we can provide a proof similar to that of Theorem 5.

Remark 2. There exists a soﬁc shift

XΓ

which is transitive and its period set is coﬁnite, but it is not

Mixing.

Proof. Let

XΓ

be the soﬁc shift based on the directed graph Γwith vertices 0and 1, arcs labeled

a, b, c

from 0to 1, and arcs labeled

a, b, d

from 1to 0. Then

XΓ

is the image of the topologically

transitive subshift of ﬁnite type, based on Γbut with distinctly labeled edges. The period set of

XΓ

N. But XΓis not topologically mixing by Theorems 11. Hence the remark follows.

Remark 3. If

XΓ

is a transitive non-singleton soﬁc shift, then the set of periodic points of

XΓ

dense in

XΓ

. But a compact dynamical system which is totally transitive and has a dense set of periodic

points is weak mixing (See [4]). Therefore

XΓ

is totally transitive if and only if

XΓ

is weak mixing. In

general, for a subshift, the conclusion of Theorem 12 need not be true. There is a subshift which is weak

mixing but not mixing (Chacon shift, See [11]).

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

3 A CHARACTERIZATION OF AN SFT

The cellular automata play an important role in various contexts such as computer graphics, parallel

computing and cell biology. It is natural to ask for a neat description of the sets of periodic points of

cellular automata, unfortunately we do not have a complete answer. There have been some papers that

discussed about the sets of periodic points for continuous self maps (See [3], [7], [9]). It is natural to

ask: Which sets will arise as the set of all periodic points of continuous self maps? This question is too

abstract. If we ask the same question in the class of some nice class of maps then we can expect a nice

answer. In this section, we consider in the case of

. Characterization of the sets of periodic points

for a continuous self map of an interval is incomplete. J.-P. Delahaye gave partial results in this context

(see Propositions 5, 6). This is our ﬁrst motivation for considering

. We completely solved in the

case of a continuous 2-dimensional toral automorphism in [16] (see Theorem 13). This is our second

motivation for considering

. In this section we give a partial answer in the case

. Our result is

similar to the following propositions 5 and 6, and Theorem 13. It characterizes an

SFT

in terms of a

CA.

Proposition 5. [9] (i) The set of ﬁxed points of a continuous function from [0

1] to [0

1] is a closed

subset of [0,1].

(ii) For every closed subset

of [0

1] there exists a continuous function

whose ﬁxed point set is

Deﬁnition 1. A subset Fof [0,1] is symmetric if for x∈[0,1],1

2+x∈F⇔1

2−x∈F.

Proposition 6. [9] (

)The set of periodic points of period 1or 2of a continuous function from [0

to [0,1] is a closed subset of [0,1].

(

)For every symmetric closed subset of [0

1] there exists a continuous function from [0

→

whose set of periodic points period 1or 2is F∪{1

2}.

Theorem 13. [16]

For any continuous toral automorphism

, the set

(

)of periodic points of

is one of the following:

1. Q1×Q1, where Q1denotes the set of all rational points in [0,1).

2. Srfor some r∈Q∪ {∞}; where Sr={(x, y)∈T2:rx +yis rational }.

3. T2.

Deﬁnition 2. A dynamical system (

X, f

)has the shadowing property, if for any

ϵ>

0there exists

δ>

0such that any ﬁnite

-chain is

-shadowed by some point. A point

x∈Xϵ

-shadows a ﬁnite

sequence

x0,x

1, ..., xn

, if for all

i≤n

(

)

<ϵ

. A (ﬁnite or inﬁnite) sequence (

)

n≥0

is a

δ-chain, if d(F(xn),x

n+1)<ϵfor all n.

ie., ∀ϵ>0,∃δ>0,∀x0, ..., xn,(∀i, d(F(xi),x

i+1)<δ =⇒∃x, ∀i, d(Fi(x),x

i)<ϵ).

Deﬁnition 3. A dynamical system (X, f)is open, if f(U)is open for any open U⊂X.

There are two distinct topological characterization of SFT known in literature as follows.

Theorem 14. [13] A subset X⊂A

Nis an SFT if and only if Xhas the shadowing property.

Theorem 15. [13] A subset X⊂A

Nis an SFT if and only if Xis an open subset of AN.

Next we have:

Lemma 3. For every

SFT X

, there exists a ﬁnite set of words

having odd length such that

Proof. Let

be a

-step

SFT

. Then there exists a ﬁnite set of words

having length atmost

such that

. If

is odd then consider

{x∈Wk

(

is a subword of

for some

y∈F}

If kis even then consider G={x∈Wk+1(AZ):yis a subword of xfor some y∈F}.

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed. 42 Vol. 11 N.º 2 August - December 2022

Theorem 10. [1] The following are equivalent for a subset Sof N.

(1)

Per

(

XΓ

)for some strongly connected labeled digraph Γcontaining cycles of length

m1,m

2, ..., mk

such that gcd(m1,m

2, ..., mk)=1.

(2) Either S={1}or S=N\Ffor some F⊂⊂ N.

From the deﬁnition of transitivity, mixing, weak mixing and by using some ideas from Lemma 1, we

can prove the following lemma for any directed labeled graph Γ. Recall that for every non-empty open

set

XΓ

we can choose (

)

n∈Z∈U

such that for

0suﬃciently large;

U⊃{

(

)

n∈Z

ik,−M≤k≤M}.

Lemma 2. Let Γbe a labeled digraph. Then the following are true.

1. XΓ

is transitive if and only if for every

i, j ∈E

(Γ) there exists a directed path of length

from

to jfor some n∈N.

2. XΓ

is weak mixing if and only if for every

i1,j

1,i

2,j

2∈E

(Γ) there exist directed paths of length

nfrom i1to j1and from i2to j2for some n∈N.

3. XΓ

is mixing if and only if for every

i, j ∈E

(Γ) there exists

N∈N

such that for all

n≥N

there

is a directed path of length nfrom ito j.

Theorem 11. Let Γbe a strongly connected labeled digraph. Then Γcontains cycles of lengths

m1,m

2, ..., mksuch that gcd(m1,m

2, ..., mk)=1if and only if XΓis mixing.

Proof. We can provide a proof similar to that of Theorem 4. Here while proceeding the proof without

loss of generality it is not possible to assume the cycles are simple. Still the conclusion is true.

Corollary 3. The period set of a mixing SFT is

either {1}or N\Ffor some F⊂⊂ N.

Proof. Proof follows from Theorems 10 and 11.

Theorem 12. A soﬁc shift is weak mixing if and only if it is mixing.

Proof. Because of Lemma 2 and Theorem 11, we can provide a proof similar to that of Theorem 5.

Remark 2. There exists a soﬁc shift

XΓ

which is transitive and its period set is coﬁnite, but it is not

Mixing.

Proof. Let

XΓ

be the soﬁc shift based on the directed graph Γwith vertices 0and 1, arcs labeled

a, b, c

from 0to 1, and arcs labeled

a, b, d

from 1to 0. Then

XΓ

is the image of the topologically

transitive subshift of ﬁnite type, based on Γbut with distinctly labeled edges. The period set of

XΓ

N. But XΓis not topologically mixing by Theorems 11. Hence the remark follows.

Remark 3. If

XΓ

is a transitive non-singleton soﬁc shift, then the set of periodic points of

XΓ

dense in

XΓ

. But a compact dynamical system which is totally transitive and has a dense set of periodic

points is weak mixing (See [4]). Therefore

XΓ

is totally transitive if and only if

XΓ

is weak mixing. In

general, for a subshift, the conclusion of Theorem 12 need not be true. There is a subshift which is weak

mixing but not mixing (Chacon shift, See [11]).

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

3 A CHARACTERIZATION OF AN SFT

The cellular automata play an important role in various contexts such as computer graphics, parallel

computing and cell biology. It is natural to ask for a neat description of the sets of periodic points of

cellular automata, unfortunately we do not have a complete answer. There have been some papers that

discussed about the sets of periodic points for continuous self maps (See [3], [7], [9]). It is natural to

ask: Which sets will arise as the set of all periodic points of continuous self maps? This question is too

abstract. If we ask the same question in the class of some nice class of maps then we can expect a nice

answer. In this section, we consider in the case of

. Characterization of the sets of periodic points

for a continuous self map of an interval is incomplete. J.-P. Delahaye gave partial results in this context

(see Propositions 5, 6). This is our ﬁrst motivation for considering

. We completely solved in the

case of a continuous 2-dimensional toral automorphism in [16] (see Theorem 13). This is our second

motivation for considering

. In this section we give a partial answer in the case

. Our result is

similar to the following propositions 5 and 6, and Theorem 13. It characterizes an

SFT

in terms of a

CA.

Proposition 5. [9] (i) The set of ﬁxed points of a continuous function from [0

1] to [0

1] is a closed

subset of [0,1].

(ii) For every closed subset

of [0

1] there exists a continuous function

whose ﬁxed point set is

Deﬁnition 1. A subset Fof [0,1] is symmetric if for x∈[0,1],1

2+x∈F⇔1

2−x∈F.

Proposition 6. [9] (

)The set of periodic points of period 1or 2of a continuous function from [0

to [0,1] is a closed subset of [0,1].

(

)For every symmetric closed subset of [0

1] there exists a continuous function from [0

→

whose set of periodic points period 1or 2is F∪{1

2}.

Theorem 13. [16]

For any continuous toral automorphism

, the set

(

)of periodic points of

is one of the following:

1. Q1×Q1, where Q1denotes the set of all rational points in [0,1).

2. Srfor some r∈Q∪ {∞}; where Sr={(x, y)∈T2:rx +yis rational }.

3. T2.

Deﬁnition 2. A dynamical system (

X, f

)has the shadowing property, if for any

ϵ>

0there exists

δ>

0such that any ﬁnite

-chain is

-shadowed by some point. A point

x∈Xϵ

-shadows a ﬁnite

sequence

x0,x

1, ..., xn

, if for all

i≤n

(

)

<ϵ

. A (ﬁnite or inﬁnite) sequence (

)

n≥0

is a

δ-chain, if d(F(xn),x

n+1)<ϵfor all n.

ie., ∀ϵ>0,∃δ>0,∀x0, ..., xn,(∀i, d(F(xi),x

i+1)<δ =⇒∃x, ∀i, d(Fi(x),x

i)<ϵ).

Deﬁnition 3. A dynamical system (X, f)is open, if f(U)is open for any open U⊂X.

There are two distinct topological characterization of SFT known in literature as follows.

Theorem 14. [13] A subset X⊂A

Nis an SFT if and only if Xhas the shadowing property.

Theorem 15. [13] A subset X⊂A

Nis an SFT if and only if Xis an open subset of AN.

Next we have:

Lemma 3. For every

SFT X

, there exists a ﬁnite set of words

having odd length such that

Proof. Let

be a

-step

SFT

. Then there exists a ﬁnite set of words

having length atmost

such that

. If

is odd then consider

{x∈Wk

(

is a subword of

for some

y∈F}

If kis even then consider G={x∈Wk+1(AZ):yis a subword of xfor some y∈F}.

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed. 42 Vol. 11 N.º 2 August - December 2022

Claim: XF=XG.

Let

x∈XF

. Suppose

x/∈XG

. Then for some

y∈F

is a subword of

. A contradiction. Therefore

x∈XG

. Next, let

x∈XG

. Which implies

is not a subword of

for all

y∈F

. Then

x∈XF

. Hence

the claim.

Next we have:

Theorem 16. Let (

AZ,F

)be any

. Then

F ix

(

)is an

SFT

or an empty set. Conversely given any

SFT Xthere exists a CA Fsuch that F ix(F)=X.

Proof. Let (

AZ,F

)be a

deﬁned by the local rule

A2r+1 →A

. Let

{w∈A

2r+1

(

)



=the middle term of

. Note that

is ﬁnite (it may be empty or

A2r+1

). First, let

x∈XF

Which implies (

(

))

for all

. ie.,

(

. Next, let

x∈A

such that

(

. Then

f(xi−rxi−r+1...x0...xi+r−1xi+r)=xifor all i. ie., x∈XF. Hence F ix(F)=XF.

Conversely, given any

SFT XF

without loss of generality assume that

contains words of same

length (odd length) because of Lemma 3.

Deﬁne f:A2r+1 →Asuch that

f(w)=the middle term of w if w is forbidden

some other alphabet otherwise

Then F ix(F)=XF.

Remark 4. In the statement of Theorem 16, we can replace F ix(F)by F ix(Fn).

Proof. Let

A2r+1 →A

be the local rule of a

CA F

AZ→A

. The local rule

A2r+1 →A

induces a function

A2s+2r+1 →A

2s+1

for all

. Then by inductively, deﬁne

A2nr+1 →A

such

that

(

fn−1

(

)) where

A2r+2(m−1)r+1 →A

2r+1

denotes the induced function of

for

. Note that the length of

(

)is equal to the diﬀerence between the length of

and 2

. Let

Fn={w:fn(w)=the middle term of w}. Then F ix(Fn)=XFn.

Converse part follows easily.

Remark 5. Let (

AZ,F

)be any

. Then

F ix

(

)is an

SFT

for each

n∈N

. Conversely, given any

SFT X there exists CA Fn:AZ→A

Zsuch that F ix(Fn

n)=X.

4 CONCLUSIONS

For each self-map

on a set

, we associate a subset of

namely,

P er

(

). If

belongs to a certain

nice class of functions, then not all subsets of

may arise as the set of periods. Which subsets of N

will come in this class? We answer this question for mixing SFT?s, and for mixing soﬁc shifts.

It is natural to ask: On which class of dynamical systems the following statements are equivalent?

1. fis transitive and P er(f)is coﬁnite.

2. fis weak mixing

3. fis mixing.

We have proved that the above statements are equivalent in the case of non-singleton SFT’s but not

true in the case of soﬁc shifts. Also we have obtained a characterization for

SFT

’s in terms of Cellular

automata.

ACKNOWLEDGMENT

The author is very thankful to the referee for giving valuable suggestions.

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

REFERENCES

[1]

K. Ali Akbar and V. Kannan (2018), Set of periods of subshifts, Pro. Indian Acad. Sci. (Math.

Sci.), 128:63.

[2]

LL. Alseda,M.A. Del Rio and J. A. Rodrigues (2003), A survey on the Relation Between

Transitivity and Dense periodicity for graph maps, Journal of Diﬀerence equations and Applications,

Vol.9(3/4), 281-288.

[3]

I.N. Baker (1964), Fixpoints of polynomials and rational functions, J. London Math. Soc., 39,

615-622.

[4]

J. Banks (1997), Regular Periodic decomposition for topologically transitive maps, Ergodic Theory

and Dynamical Systems, 17, 505-529.

[5]

L.S. Block and W.A. Coppel (1992), Dynamics in One Dimension, Springer-Verlag, Berline,

Volume 1513 of Lecture Notes in Mathematics.

[6]

J.A. Bondy and U.S.R. Murty (1982), Graph theory with application, Elsevier science publishing

Co., Inc, New York.

[7]

M. Brin and G. Stuck (2002), Introduction to Dynamical Systems, Cambridge University Press.

[8]

E.M. Coven and M.C. Hidalgo (1991), On the topological entropy of transitive maps of the

interval, Bull. Aust. Math. Soc., 44, 207-213.

[9] J.-P. Delahaye (1981), The set of periodic points, Amer. Math. Monthly., 88, 646-651.

[10]

R.L. Devaney(1989), An Introduction to Chaotic Dynamical Systems, Addison-wesley Publishing

Company Advanced Book Program., Redwood City, CA, second edition.

[11]

Eli Glasner (2003), Ergodic Theory Via Joinigs, American Mathematical Society, Mathematical

surveys and monographs, Vol 101.

[12] B.P. Kitchens (1997), Symbolic Dynamics, Springer.

[13] P. Kurka (2003), Topological and symbolic dynamics, Societe Mathematique de France, Paris.

[14]

D.A. Lind and B. Marcus (1995), An introduction to symbolic dynamics and coding, Cambridge

University Press., New York, NY, USA.

[15]

Sylvie Ruette (2003), Chaos for continuous interval maps, A survey of relationship between the

various forms of chaos.

[16]

I. Subramania Pillai,K. Ali Akbar,V. Kannan and B. Sankararao (2010), The set of

periodic points of a toral automorphism, Journal of Mathematical Analysis and Applications., 366,

367-371.

[17]

I. Subramania Pillai,K. Ali Akbar,V. Kannan and B. Sankararao (2011), The set of

periods of periodic points of a toral automorphism, Topology Procedings, Volume 37, 1-14.

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed. 42 Vol. 11 N.º 2 August - December 2022

Claim: XF=XG.

Let

x∈XF

. Suppose

x/∈XG

. Then for some

y∈F

is a subword of

. A contradiction. Therefore

x∈XG

. Next, let

x∈XG

. Which implies

is not a subword of

for all

y∈F

. Then

x∈XF

. Hence

the claim.

Next we have:

Theorem 16. Let (

AZ,F

)be any

. Then

F ix

(

)is an

SFT

or an empty set. Conversely given any

SFT Xthere exists a CA Fsuch that F ix(F)=X.

Proof. Let (

AZ,F

)be a

deﬁned by the local rule

A2r+1 →A

. Let

{w∈A

2r+1

(

)



=the middle term of

. Note that

is ﬁnite (it may be empty or

A2r+1

). First, let

x∈XF

Which implies (

(

))

for all

. ie.,

(

. Next, let

x∈A

such that

(

. Then

f(xi−rxi−r+1...x0...xi+r−1xi+r)=xifor all i. ie., x∈XF. Hence F ix(F)=XF.

Conversely, given any

SFT XF

without loss of generality assume that

contains words of same

length (odd length) because of Lemma 3.

Deﬁne f:A2r+1 →Asuch that

f(w)=the middle term of w if w is forbidden

some other alphabet otherwise

Then F ix(F)=XF.

Remark 4. In the statement of Theorem 16, we can replace F ix(F)by F ix(Fn).

Proof. Let

A2r+1 →A

be the local rule of a

CA F

AZ→A

. The local rule

A2r+1 →A

induces a function

A2s+2r+1 →A

2s+1

for all

. Then by inductively, deﬁne

A2nr+1 →A

such

that

(

fn−1

(

)) where

A2r+2(m−1)r+1 →A

2r+1

denotes the induced function of

for

. Note that the length of

(

)is equal to the diﬀerence between the length of

and 2

. Let

Fn={w:fn(w)=the middle term of w}. Then F ix(Fn)=XFn.

Converse part follows easily.

Remark 5. Let (

AZ,F

)be any

. Then

F ix

(

)is an

SFT

for each

n∈N

. Conversely, given any

SFT X there exists CA Fn:AZ→A

Zsuch that F ix(Fn

n)=X.

4 CONCLUSIONS

For each self-map

on a set

, we associate a subset of

namely,

P er

(

). If

belongs to a certain

nice class of functions, then not all subsets of

may arise as the set of periods. Which subsets of N

will come in this class? We answer this question for mixing SFT?s, and for mixing soﬁc shifts.

It is natural to ask: On which class of dynamical systems the following statements are equivalent?

1. fis transitive and P er(f)is coﬁnite.

2. fis weak mixing

3. fis mixing.

We have proved that the above statements are equivalent in the case of non-singleton SFT’s but not

true in the case of soﬁc shifts. Also we have obtained a characterization for

SFT

’s in terms of Cellular

automata.

ACKNOWLEDGMENT

The author is very thankful to the referee for giving valuable suggestions.

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

REFERENCES

[1]

K. Ali Akbar and V. Kannan (2018), Set of periods of subshifts, Pro. Indian Acad. Sci. (Math.

Sci.), 128:63.

[2]

LL. Alseda,M.A. Del Rio and J. A. Rodrigues (2003), A survey on the Relation Between

Transitivity and Dense periodicity for graph maps, Journal of Diﬀerence equations and Applications,

Vol.9(3/4), 281-288.

[3]

I.N. Baker (1964), Fixpoints of polynomials and rational functions, J. London Math. Soc., 39,

615-622.

[4]

J. Banks (1997), Regular Periodic decomposition for topologically transitive maps, Ergodic Theory

and Dynamical Systems, 17, 505-529.

[5]

L.S. Block and W.A. Coppel (1992), Dynamics in One Dimension, Springer-Verlag, Berline,

Volume 1513 of Lecture Notes in Mathematics.

[6]

J.A. Bondy and U.S.R. Murty (1982), Graph theory with application, Elsevier science publishing

Co., Inc, New York.

[7]

M. Brin and G. Stuck (2002), Introduction to Dynamical Systems, Cambridge University Press.

[8]

E.M. Coven and M.C. Hidalgo (1991), On the topological entropy of transitive maps of the

interval, Bull. Aust. Math. Soc., 44, 207-213.

[9] J.-P. Delahaye (1981), The set of periodic points, Amer. Math. Monthly., 88, 646-651.

[10]

R.L. Devaney(1989), An Introduction to Chaotic Dynamical Systems, Addison-wesley Publishing

Company Advanced Book Program., Redwood City, CA, second edition.

[11]

Eli Glasner (2003), Ergodic Theory Via Joinigs, American Mathematical Society, Mathematical

surveys and monographs, Vol 101.

[12] B.P. Kitchens (1997), Symbolic Dynamics, Springer.

[13] P. Kurka (2003), Topological and symbolic dynamics, Societe Mathematique de France, Paris.

[14]

D.A. Lind and B. Marcus (1995), An introduction to symbolic dynamics and coding, Cambridge

University Press., New York, NY, USA.

[15]

Sylvie Ruette (2003), Chaos for continuous interval maps, A survey of relationship between the

various forms of chaos.

[16]

I. Subramania Pillai,K. Ali Akbar,V. Kannan and B. Sankararao (2010), The set of

periodic points of a toral automorphism, Journal of Mathematical Analysis and Applications., 366,

367-371.

[17]

I. Subramania Pillai,K. Ali Akbar,V. Kannan and B. Sankararao (2011), The set of

periods of periodic points of a toral automorphism, Topology Procedings, Volume 37, 1-14.

https://doi.org/10.17993/3ctecno.2022.v11n2e42.13-23

3C Tecnología. Glosas de innovación aplicadas a la pyme. ISSN: 2254-4143

Ed. 42 Vol. 11 N.º 2 August - December 2022