JACODESMATH / ISSN 2148-838X

J. Algebra Comb. Discrete Appl.
1(1) • 41-51

Received: 26 June 2014; Accepted: 3 September 2014

Journal of Algebra Combinatorics Discrete Structures and Applications

Some properties of topological pressure on cellular
automata∗

Research Article

Chih-Hung Chang ∗∗

Department of Applied Mathematics, National University of Kaohsiung, Kaohsiung 700, Taiwan, ROC

Abstract: This paper investigates the ergodicity and the power rule of the topological pressure of a cellular
automaton. If a cellular automaton is either leftmost or rightmost permutive (due to the terminology
given by Hedlund [Math. Syst. Theor. 3, 320-375, 1969]), then it is ergodic with respect to the uniform
Bernoulli measure. More than that, the relation of topological pressure between the original cellular
automaton and its power rule is expressed in a closed form. As an application, the topological pressure
of a linear cellular automaton can be computed explicitly.

2010 MSC: 37B10

Keywords: Cellular automata, Permutive, Ergodicity, Topological pressure

1. Introduction

Let A = {0, 1, . . . ,υ − 1} for some υ ≥ 2, and let X = AZ be the space of infinite sequences
x = (xi)i∈Z. A continuous map F : X → X satisfying F ◦σ = σ◦F is called a cellular automaton (CA),
where σ is the shift map defined by σ(x)i = xi+1, i ∈ Z. CA is a particular class of dynamical systems
introduced by S. Ulam [21] and J. von Neumann [23] as a model for self-production. It is widely studied
in a variety of contexts in physics, biology and computer science [6, 7, 10, 12, 16, 20, 22, 26, 27].

Greenberg and Hastings [13] transfer a reaction-diffusion equation into a CA and demonstrate that
such a simplified model can still generate spatial-temporal structures similar to the original system [11–
13]. In 1976, Hardy et al. [14] proposed the so-called HPP model for the study of hydrodynamics. Notably,
this model is a CA.

Since CA is widely applied in physics, it is also interesting to consider the role thermodynamics
plays in CA. The second law of thermodynamics says that the entropy of a system and its surroundings
(universe) do not decrease. However, this encounters with a paradox to Poincaré Recurrence Theorem.

∗ This work is partially supported by the Ministry of Science and Technology, ROC (Contract No MOST 103-
2115-M-390-004-).
∗∗ E-mail: chchang@nuk.edu.tw

41



Some properties of topological pressure on cellular automata

To overcome this difficulty, L. Boltzmann introduces “Ergodic Hypothesis". Reader may refer to [17].
This leads to the development of ergodic theory.

This elucidation studies two properties of CA. The first part investigates the ergodic property of CA.
Then the second part gives an application for ergodic CA by demonstrating the power rule of topological
pressure of CA.

One-dimensional CA consists of infinite lattice with finite states and an associated mapping, say local
rule. A systematic study of CA from purely mathematical point of view is discussed by Hedlund [15]. He
treats CA as a particular class of symbolic dynamics and discovers that a permutive CA (defined later)
implements many phenomena such as surjection. From the viewpoint of ergodic theory, it is interesting
to investigate whether a CA is surjective or not since a surjective CA preserves the uniform Bernoulli
measure [9]. Shereshevsky [18] demonstrates more ergodic properties for permutive CA, such as mixing,
Bernoulli automorphism, Kolmogorov automorphism, and so on. He also defines the power rule of a CA
and figures out many properties are preserved. Read is referred to Akın’s works [1, 2] for more results.

Shereshevsky and Rogers [19] conjecture that every surjective CA, except those of the form Fxi =
kxi, where g.c.d.(k,υ) = 1, is ergodic with respect to the uniform Bernoulli measure. This conjecture
does not hold in general. A counterexample is discussed in Section 3.

The first result of this paper is, if a CA is permutive, then it is ergodic. Besides, the permutivity
of CA is necessary for the ergodicity for a particular class of CA. Using this property, the power rule of
topological pressure of CA can be expressed in a closed form.

For T : Ω → Ω a continuous transformation defined on a compact metric space, it is well-known that
the power rule of topological entropy of T satisfying htop(Tn) = nhtop(T) for all n ∈ N. If, moreover,
(Ω,B,µ) is a probability space and T : Ω → Ω is also a measure-preserving transformation. Then
hµ(T

n) = nhµ(T) for all n ∈ N, where hµ(T) is the measure-theoretic entropy of T. Also, for the
topological pressure of T, P(T, ·) : C(Ω,R) → R, there is a similar expression

P(Tn,Sng) = nP(T,g), where Sng =
n−1∑
i=0

g ◦Ti.

In [5], the authors investigated the topological pressure of permutive CA. Theorem 4.4 indicates
that, if F is a permutive CA, then the topological pressure of F and its nth power rule can be presented
in a closed form:

P(Fn,g) = nP(F,g) − (n− 1)
∫
g dµ, (1)

for g continuous function, n ∈ N. Notably, this expression does not hold in general. A counterexample is
studied in Section 4. As an application, the topological pressure of linear CA can be formulated rigorously
(cf. [3]), which extends our previous result [4].

The materials of this elucidation are organized as follows. Section 2 states some definitions and
notations. Section 3 investigates the sufficient condition for the ergodic CA, and figures out a necessary
condition for the ergodicity for a particular class of CA. Section 4 studies the power rule of topological
pressure of a CA. A closed expression is given via a strong generator.

2. Preliminaries

Let A = {0, 1, . . . ,υ − 1} be a finite alphabet and let X = AZ be the space of infinite sequence
x = (xn)

∞
−∞. Whenever a local rule f : A2k+1 →A is given, there associates unique CA, say F : X → X,

defined by

F(x)i = f(xi−k, . . . ,xi+k),

42



C.-H. Chang

where

An = {a1a2 · · ·an : ai ∈A, 1 ≤ i ≤ n}, n ∈ N.

For any m ≥ 1, f can be extended to the mapping fm : A2k+m →Am by

fm(x−k, . . . ,xk+m−1) = (f(x−k, . . . ,xk), . . . ,f(x−k+m−1, . . . ,xk+m−1)),

where f1 = f. In addition, the nth power rule of f, denote by fn : A2nk+1 →A, is defined as

fn(x−nk, . . . ,xnk) = f(f
n−1(x−nk, . . . ,x(n−1)k), . . . ,f

n−1(x−(n−2)k, . . . ,xnk)),

for n ≥ 1.
Hedlund [15] shows a necessary and sufficient condition for the surjection of a CA.

Proposition 2.1 ([15]). Consider F a CA with local rule f : A2k+1 → A. Then F is surjective if and
only if card f−1m (y1, . . . ,ym) = (card A)2k for all m ∈ N and all (y1, . . . ,ym) ∈Am, where card S denotes
the cardinality of S.

The study of the local rule of a CA is essential for the understanding of this system. A particular
class of local rules, say permutive, is initially introduced by Hedlund [15].

Definition 2.2. The local rule f : A2k+1 → A for a given CA is said to be leftmost (respectively
rightmost) permutive in xi if there exists an integer i, −k ≤ i ≤−1 (respectively 1 ≤ i ≤ k), such that

(i) for (y1, . . . ,y2k) ∈A2k, g(xi) ≡ f(y1, . . . ,y2k; xi) : A→A is a permutation;

(ii) f does not depend on xj for j < i (respectively j > i),

where x = (xj)kj=−k ∈A
2k+1.

Definition 2.3. The local rule f is called bipermutive if it is not only rightmost permutive but also
leftmost permutive. f is called permutive if f is one of these three cases, i.e., f is either leftmost or
rightmost or bipermutive.

Hedlund demonstrates a permutive CA is also surjective.

Proposition 2.4 ([15]). If f is permutive, then F is surjective.

It is easily verified that the permutivity is preserved by power rule.

Lemma 2.5. If f is permutive, then so is fn for all n ∈ N. More precisely, fn preserves the type of
permutivity of f for all n ∈ N.

Proof. This follows immediately from the definition of fn.

Example 2.6. Consider the alphabet A = {0, 1, 2, 3} and local rule f : A3 →A defined by

f(x−1,x0,x1) = 2x−1 + x1 mod 4.

Then f is rightmost permutive.

Observe that the second and the third power rule of f are

f2 : A5 →A, f2(x−2, . . . ,x2) = x2,

and

f3 : A7 →A, f3(x−3, . . . ,x3) = 2x1 + x3,

respectively. It comes by induction that

fn : A2n+1 →A, fn(x−n, . . . ,xn) =
{
xn, n is even;
2xn−2 + xn, n is odd.

(2)

Hence fn is rightmost permutive for all n ∈ N.

43



Some properties of topological pressure on cellular automata

Let (X,B,µ) be a probability space and let T : X → X be a measure-preserving transformation. T
is called ergodic if the only elements A ∈B with T−1A = A satisfy µ(A) = 0 or µ(A) = 1. The following
theorem gives some equivalent conditions for the ergodicity of T .

Theorem 2.7 ([24]). If T : X → X is a measure-preserving transformation of the probability space
(X,B,µ), then the following statements are equivalent:

(i) T is ergodic.

(ii) If g is measurable and g ◦T = g a.e., then g is constant a.e.

(iii) For every A,B ∈B with µ(A) > 0,µ(B) > 0, there exists n ∈ N such that µ(T−nA∩B) > 0.

Define d : X ×X → R by

d(x,y) =

∞∑
i=−∞

|xi −yi|
υ|i|

, x,y ∈ X. (3)

It is easy to verify that d is a metric and (X,d) is a compact metric space.

Consider µ an invariant probability measure on (X,F). Let α and β be two finite measurable
partitions of X, define

α∨β = {A∩B : A ∈ α,B ∈ β}.

It is easily seen that α∨β is a refinement of α and β. We define the entropy of the partition α by

Hµ(α) = −
∑
A∈α

µ(A) log µ(A).

The entropy of the measure preserving transformation F with respect to the partition α is given by

hµ(F,α) = lim
n→∞

1

n
Hµ(

n−1∨
i=0

F−iα), (4)

reader may refer to [24] for the existence of the limit. And the measure-theoretic entropy of F is defined
by

hµ(F) = sup hµ(F,α), (5)

where the supremum is taken over all finite measurable partitions of X.

Let (X,F) be an endomorphism and let P be an open cover of X. Set

H(P) = inf{log cardP̂},

where the infimum is taken over the set of finite subcovers P̂ of P and cardA is the cardinality of A.
The topological entropy of the measure preserving transformation F with respect to the open cover P is
defined by

h(F,P) = lim
n→∞

1

n
H(

n−1∨
i=0

F−iP). (6)

For the existence of the limit, we refer reader to [24]. The topological entropy of F is defined by

htop(F) = sup h(F,P), (7)

where the supremum is taken over all finite open covers of X.

44



C.-H. Chang

In addition, for α an open cover of X and φ ∈ C(X,R) a continuous function from X to R, denote
by

pn(F,φ,α) = inf{
∑
B∈β

sup
x∈B

e(Snφ)(x) : β is a finite subcover of
n−1∨
i=0

F−iα},

where n ∈ N and Snφ =
∑n−1
i=0 φ◦F

i. Then limn→∞ 1n log pn(F,φ,α) exists [24]. For each δ > 0, define

P(F,φ,δ) = sup{ lim
n→∞

1

n
log pn(F,φ,α) : diam(α) ≤ δ}, (8)

and

P(F,φ) = lim
δ→0

P(F,φ,δ). (9)

The map P(F, ·) : C(X,R) → R∪{∞} is called the topological pressure of F. It comes immediately that
P(F, 0) = htop(F).

3. Ergodicity on Permutive Cellular Automata

This section studies the ergodicity of permutive CA. For simplicity, a local rule f : A2k+1 → A is
presumed that f only depends on xi, r ≤ i ≤ s, for some r ≤ s, r,s ∈ Z.

In the rest of this elucidation, we refer µ to the uniform Bernoulli measure unless otherwise stated.

Theorem 3.1. If f is permutive, then F is ergodic.

Proof. It suffices to show that F is ergodic if f is rightmost permutive. The case that f is leftmost
permutive can be demonstrated via the same argument, thus is omitted.

Denote by C(i,j) = i[ai, . . . ,aj]j a cylinder of X, i.e., for all x = (xn) ∈ X, xn = an, where i ≤ n ≤ j
and i ≤ j. First we show that, for any two cylinder C(i,j) = i[ci, . . . ,cj]j,D(m,l) = m[dm, . . . ,dl]l, there
exists N ∈ N such that µ(F−NC(i,j) ∩D(m,l)) > 0, where i ≤ j,m ≤ l.

Without loss of generality, we may assume that r = 0. The case that r 6= 0 can be done analogously.
We construct a scheme to demonstrate the ergodicity of F.

Since f is rightmost permutive, it comes immediately that F−nC(i,j) is a collection of cylinders
E(i,j + ns) with cardinality card F−nC(i,j) = νns, for n ∈ N. Therefore, if l < i or j < m−s, then the
permutivity of f demonstrates that µ(F−1C(i,j) ∩D(m,l)) > 0.

If m ≤ i ≤ l ≤ j. Let α ∈ Z+ be the smallest number such that l + α − i is a multiple of s,
say l + α − i = τs for some τ ∈ N. Pick D′(m,l + α) = m[dm, . . . ,dl, 0, . . . , 0]l+α ≡ [dm, . . . ,dl+α] a
subcylinder of D(m,l). Define κ1,1, . . . ,κ1,s,κ2,1, . . . by

κ1,` = f
τ−1(di+`−1, . . . ,di+`+(τ−1)s−1), 1 ≤ ` ≤ s,

κ2,` = f
τ−2(di+`−1, . . . ,di+`+(τ−2)s−1), 1 ≤ ` ≤ 2s,

...
κτ−1,` = f(di+`−1, . . . ,di+`+s−1), 1 ≤ ` ≤ (τ − 1)s.

Since f is rightmost permutive, there exist unique β1,1, . . . ,β1,j−i+1 such that F([κ1,1, . . . ,κ1,s,β1,1,
. . . ,β1,j−i+1]) = C(i,j), i.e.,

E1 ≡ i[κ1,1, . . . ,κ1,s,β1,1, . . . ,β1,j−i+1]j+s ⊂ F−1C(i,j).

45



Some properties of topological pressure on cellular automata

Similarly, there exist unique β2,1, . . . ,β2,j−i+1 such that

F([κ2,1, . . . ,κ2,2s,β2,1, . . . ,β2,j−i+1]) = E1,

i.e.,

E2 ≡ i[κ2,1, . . . ,κ2,2s,β2,1, . . . ,β2,j−i+1]j+2s ⊂ F−1E1 ⊂ F−2C(i,j).

Inductively we can conclude that D′(m,l + α) ⊂ F−τC(i,j). This implies µ(F−τC(i,j) ∩D(m,l)) > 0.
The other cases, such as m ≤ i ≤ j ≤ l, i ≤ m ≤ j ≤ l, and so on, can be done analogously. Hence,

for any two cylinders C(i,j) and D(m,l), there exists N ∈ N such that µ(F−1C(i,j) ∩D(m,l)) > 0.
For any two measurable sets A,B with positive measure and � > 0, there exist two collections of

pairwise disjoint cylinders A1, . . . ,Am, B1, . . . ,Bl such that

(i) ∪Ai ⊆ A and ∪Bj ⊆ B;

(ii) µ(A\∪Ai) < � and µ(B \∪Bj) < �.

It can be easily verified that the permutivity of F asserts F−1Ai∩F−1Aj = ∅ and F−1Bi∩F−1Bj = ∅
for all i 6= j. Moreover,

F−nA∩B ⊇ (F−n(∪Ai)) ∩ (∪Bj) = ∪i,j(F−nAi ∩Bj),

for all n ∈ N. Therefore, there exists N ∈ N such that µ(F−NA∩B) > 0.
The proof is completed.

Example 3.2. For A = {0, 1, . . . ,ν−1}, ν ≥ 2. Let σ : AZ →AZ be the shift map. Then σ is rightmost
permutive.

It is easy to see that σ is ergodic. For any two distinct cylinders C(i,j) and D(m,l), where i ≤
j,m ≤ l. There exists n ∈ N such that i + n > l. Thus σ−nC(i,j) ∩D(m,l) = C(i + n,j + n) ∩D(m,l)
is of positive measure. That is, σ is ergodic.

Example 3.3 (Continued). In Example 2.6, we consider the alphabet A = {0, 1, 2, 3} and local rule
f : A3 →A defined by

f(x−1,x0,x1) = 2x−1 + x1 mod 4.

Moreover,

fn : A2n+1 →A, fn(x−n, . . . ,xn) =
{
xn, n is even;
2xn−2 + xn, n is odd.

(10)

It is easily seen that if Fn is ergodic for some n ∈ N, then so is F. For all k ∈ N, f2k(x−2k, . . . ,x2k) =
x2k. This indicates F2k is kind of a “multiple-shift map", thus is ergodic. Therefore, F is ergodic.

If the cardinality of states A is a prime, then every additive CA is permutive except for those local
rules of the form f : A→A,f(x) = αx for some 0 ≤ α ≤ p− 1, where card A = p.

There is an example that, f is permutive in x0 but not ergodic since f is not rightmost permutive.

Proposition 3.4. Consider A = {0, 1} and local rule f : A3 →A defined by

f(x0,x1,x2) = x0 + x1(x2 + 1) mod 2.

Then F is not ergodic.

46



C.-H. Chang

Proof. It comes from [8] that F is not topologically transitive. Therefore, F is not ergodic.

However, the assumption of permutivity is the necessary condition for the ergodicity in a particular
class of CA.

Proposition 3.5. Consider A = {0, 1, . . . ,ν − 1} and F a CA satisfying the following conditions:

(i) f is additive, i.e., f : A2k+1 →A can be represented as f(x−k, . . . ,xk) =
∑k
i=−k aixi.

(ii) There exists unique `,−k ≤ ` ≤ k, such that a` = 1.

(iii) If f only depends on xi, r ≤ i ≤ s, for some −k ≤ r ≤ s ≤ k, then g.c.d.(am,ν) > 1 for
r < m < s,m 6= `.

Then F is ergodic if and only if f is either leftmost or rightmost permutive.

Proof. It suffices to show that, if f is neither leftmost nor rightmost permutive, then F is not ergodic.

Write f(xr, . . . ,xs) =
∑s
i=r aixi. There exists κ ∈ N,κ 6= 0 mod ν, such that κai = 0 mod ν for

all i 6= `. Then

κF(x)j = κ

s∑
i=r

aixi+j = κxj+`.

Define

g : AZ → R by g(x) =
∑

κxi,

it is easily seen that g is measurable and g ◦F = g on AZ. The fact that g is not constant demonstrates
F is not ergodic.

This completes the proof.

Example 3.6. Consider A = {0, 1, 2, 3} and local rule f : A3 →A defined by

f(x−1,x0,x1) = 2x−1 + x0 + 2x1 mod 4.

Then f is neither rightmost nor leftmost permutive.

Consider g : X → R defined by g(x) = 2x0. Then g is measurable and nonconstant, however,
g ◦F = g for all x ∈ X. This demonstrates F is not ergodic.

4. The Topological Pressure of Power Rule of CA

This section investigates the topological pressure via a strong generator.

Consider (X,F) an endomorphism and ξ a finite cover of X, we call ξ a strong generator if, for any
δ > 0, there exists N ∈ N such that ‖

∨m−1
i=0 F

−iξ ‖< δ for all m ≥ N, where ‖ A ‖ denotes the diameter
of A. In other words, ξ is a strong generator if and only if

‖
m−1∨
i=0

F−iξ ‖→ 0, as n →∞.

For a,b ∈ Z, a ≤ b, denote by a[sa, . . . ,sb]b = {x ∈ X : xa = sa, . . . ,xb = sb} a cylinder in X and
ξ(a,b) = {a[xa, . . . ,xb]b : xa, . . . ,xb ∈ S} a partition of X.

47



Some properties of topological pressure on cellular automata

Lemma 4.1. Let f be permutive and let ξ ≡ ξ(a,b) be a partition of X for a ≤ b, a,b ∈ Z. Then ξ(a,b)
is a strong generator.

Proof. We show the case that f is rightmost permutive, the other cases can be done similarly.

Assume that f is rightmost permutive in xs and does not depend on xj for all j < r, where
r < s. Denote by C(i,j) = i[ai, . . . ,aj]j a cylinder of X, i.e., for all x = (xm) ∈ X, xm = am, where
i ≤ m ≤ j and i ≤ j. It is easy to verify that F−1A ∩ F−1B = ∅ since f is rightmost permutive.
Moreover, for any cylinder C(i,j), F−1C(i,j) ⊂ ξ(i + r,j + s) with cardinality υs−r. In other words,
F−1ξ(a,b) = ξ(a + r,b + s).

Denote ξ ≡ ξ(a,b) for simplicity. It follows from the discussion above that

ξ ∨F−1ξ =
{
ξ(a,b + s), 0 ≤ r;
ξ(a + r,b + s), 0 ≥ r. (11)

Inductively,

ξ ∨F−1ξ ∨·· ·∨F−(m−1)ξ =
{
ξ(a,b + (m− 1)s), 0 ≤ r;
ξ(a + (m− 1)r,b + (m− 1)s), 0 ≥ r. (12)

This elucidates that

‖ ξ ∨F−1ξ ∨·· ·∨F−(m−1)ξ ‖→ 0, as m →∞,

i.e., ξ is a strong generator.

The proof is completed.

Example 4.2 (Continued). Consider A and f same as given in Example 2.6. Pick ξ(0) = {[0]0, [1]0,
[2]0, [3]0} the standard partition of X = AZ. Then

F−1[0]0 = {−1[0, ·, 0]1,−1[1, ·, 2]1,−1[2, ·, 0]1,−1[3, ·, 2]1},
F−1[1]0 = {−1[0, ·, 1]1,−1[1, ·, 3]1,−1[2, ·, 1]1,−1[3, ·, 3]1},
F−1[2]0 = {−1[0, ·, 2]1,−1[1, ·, 0]1,−1[2, ·, 2]1,−1[3, ·, 0]1},
F−1[3]0 = {−1[0, ·, 3]1,−1[1, ·, 1]1,−1[2, ·, 3]1,−1[3, ·, 1]1}.

It follows that

(i) F−1[i]0 ∩F−1[j]0 = ∅ for i 6= j;

(ii) for 0 ≤ i ≤ 3, A∩B = ∅ for A 6= B,A,B ∈ F−1[i]0;

(iii) F−1ξ(0) = ξ(−1, 1).

It is easily verified that

n−1∨
i=0

F−iξ(0) = ξ(−(n− 1),n− 1), and ‖
n−1∨
i=0

F−iξ(0) ‖→ 0,

as n → ∞. In other words, ξ(0) is a strong generator. In addition, it can be checked without difficulty
that ξ(a,b) is a strong generator for a ≤ b.

It is well-known that htop(Fn) = nhtop(F) and P(Fn,Sng) = nP(F,g) for all n ∈ N, where Sng =∑n−1
i=0 g ◦F

i and g ∈ C(X,R) [24]. There is an intuitive connection between Fn and the nth power rule
of local rule f.

48



C.-H. Chang

Lemma 4.3. Consider a CA F with local rule f. Then the nth power rule of F, Fn, is a CA with local
rule fn for n ∈ N.

Proof. This comes from the definition of Fn and fn, thus is omitted.

The main theorem of this section then follows.

Theorem 4.4. Consider F a CA with permutive local rule f. The topological pressure of Fn can be
expressed as

P(Fn,g) = nP(F,g) − (n− 1)
∫
X

g dµ, (13)

for all n ∈ N, g ∈ C(X,R).

Theorem 3.1 shows that, for a CA F with the local rule f, if f is permutive, then F is ergodic.
Therefore, there is an immediate consequence comes from Birkhoff Ergodic Theorem.

Lemma 4.5. Consider g ∈ C(X,R). For any � > 0, there exists N ∈ N such that for ` ≥ N,

| sup
x∈A

S`g(x) − sup
x∈B

S`g(x)| < `�,

for any two disjoint measurable set A,B, where S`g =
∑`−1
i=0 g ◦F

ni.

Proof. The permutivity of f implies fn is permutive, thus Fn is ergodic. Birkhoff Ergodic Theorem
demonstrates that 1

`
S`g converges a.e. to a function ḡ and ḡ =

∫
X
g dµ is constant a.e.

The proof is completed.

Proof of Theorem 4.4. ξ is a strong generator implies that

P(Fn,g) = lim
m→∞

1

m
log pm(F

n,g,ξ),

for g ∈ C(X,R). Same discussion as in the proof of Lemma 4.1 indicates that
m−1∨
i=0

F−niξ =

{
ξ(a,b + (m− 1)ns), 0 ≤ r;
ξ(a + (m− 1)nr,b + (m− 1)ns), 0 ≥ r.

and

card

m−1∨
i=0

F−niξ =

{
υb−a+1+(m−1)ns, 0 ≤ r;
υb−a+1+(m−1)n(s−r), 0 ≥ r.

Hence

P(Fn,g) = lim
m→∞

1

m
log pm(F

n,φ,ξ)

= lim
m→∞

1

m
log inf{

∑
B

sup
x∈B

e(Smg)(x) : B ∈
m−1∨
i=0

F−niξ}

= lim
m→∞

1

m
log

{
υb−a+1+(m−1)nse(Smg), 0 ≤ r;
υb−a+1+(m−1)n(s−r)e(Smg), 0 ≥ r.

=

{
ns log υ +

∫
X
g dµ, 0 ≤ r;

n(s−r) log υ +
∫
X
g dµ, 0 ≥ r.

by Lemma 4.5.

It is easily seen that P(Fn,g) = nP(F,g) − (n− 1)
∫
X
g dµ.

This completes the proof.

49



Some properties of topological pressure on cellular automata

Example 4.6 (Continued). Let A and f same as in Example 2.6. Replace n by 1 in the proof above,
we have

P(F,g) = 2 log 4 +

∫
X

g dµ,

and

P(Fn,g) = 2n log 4 +

∫
X

g dµ.

Hence P(Fn,g) = nP(F,g) − (n− 1)
∫
X
g dµ for all n ∈ N.

Furthermore, Ward [25] shows that htop(F) = 2 log 4. This implies

P(Fn,g) = nhtop(F) +

∫
X

g dµ = htop(F
n) +

∫
X

g dµ.

Notably, Theorem 4.4 fails if the permutivity of F is omitted.

Proposition 4.7. Consider F a CA with local rule

f : A2k+1 →A, defined by f(x−k, . . . ,fk) = κx0,

where 0 ≤ κ ≤ υ − 1. Then P(Fn,g) = 0 for all n ∈ N,g ∈ C(X,R).

Proof. It can be easily verified that F is not permutive.

If κ = 0, it comes immediately that P(Fn,g) = 0 for all n ∈ N,g ∈ C(X,R). It remains to show the
cases κ 6= 0.

For n ∈ N and ξ(a,b) a partition of X, where a ≤ b. Since f(x−k, . . . ,xk) = κx0, we have∨m−1
i=0 F

−niξ(a,b) = ξ(a,b). This implies P(Fn,g) = 0 for any g ∈ C(X,R).
The proof is completed.

Acknowledgment

The author wishes to express his gratitude to the anonymous referees. Their comments make a
significant improvement to this paper.

References

[1] H. Akin, On the ergodic properties of certain additive cellular automata over Zm, Appl. Math.
Comput., 168, 192-197, 2005.

[2] H. Akin, Some strong ergodic properties of 1d invertible linear cellular automata, arXiv: 0902.3762,
2014.

[3] H. Akin, J.-C. Ban, and C.-H. Chang, On the qualitative behavior of linear cellular automata, J. Cell.
Autom., 8, 205-231, 2013.

[4] J.-C. Ban and C.-H. Chang, The topological pressure of linear cellular automata, Entropy, 11, 271-
284, 2009.

[5] J.-C. Ban, C.-H. Chang, T.-J. Chen, and M.-S. Lin, The complexity of permutive cellular automata,
J. Cell. Autom., 6, 385-397, 2011.

50



C.-H. Chang

[6] G. Bub, A. Shrier, and L. Glass, Spiral wave generation in heterogeneous excitable media, Phys. Rev.
Lett., 88(5), 058101, 2002.

[7] Y. B. Chernyak, A. B. Feldman, and R. J. Cohen, Correspondence between discrete and continuous
models of excitable media: Trigger waves, Phys. Rev. E, 55, 3125-3233, 1997.

[8] E. M. Coven, Topological entropy of block maps, Proc. Amer. Math. Soc., 78, 590-594, 1980.
[9] E. M. Coven and M. Paul, Endomorphisms of irreducible shifts of finite type, Math. Syst. Theory, 8,

165-177, 1974.
[10] A. B. Feldman, Y. B. Chernyak, and R. J. Cohen, Wave-front propagation in a discrete model of

excitable media, Phys. Rev. E, 57, 7025-7040, 1998.
[11] J. M. Greenberg, C. Greene, and S. P. Hastings, Acombinatorial problem arising in the study of

reaction-diffusion equations, SIAM J. Algebraic Discrete Methods, 1, 34-42, 1980.
[12] J. M. Greenberg, B. D. Hassard, and S. P. Hastings, Pattern formation and periodic structure in

systems modeled by reaction-diffusion equations, Bull. Amer. Math. Soc., 84, 1296-1327, 1978.
[13] J. M. Greenberg and S. P. Hastings, Spatial patterns for discrete models of diffusion in excitable

media, SIAM J. Appl. Math., 34, 515-523, 1978.
[14] J. Hardy, O. de Pazzis, and Y. Pomeau, Molecular dynamics of a classical lattice gas: transport

properties and time correlation functions, Phys. Rev. A, 13, 1949-1960, 1976.
[15] G. A. Hedlund, Endomorphisms and automorphisms of full shift dynamical system, Math. Systems

Theory, 3, 320-375, 1969.
[16] D. Richardson, Tessellation with local transformations, J. Compuut. System Sci., 6, 373-388, 1972.
[17] M. Sabbagan and P. Nasertayoob, Ergodic theory and dynamical systems from a physical point of

view, Arab. J. Sci. Eng. Sect. A Sci., 33, 373-387, 2008.
[18] M. A. Shereshevsky, Ergodic properties of certain surjective cellular automata, Monatsh. Math., 114,

305-316, 1992.
[19] M. Shirvani and T. D. Rogers, On ergodic one-dimensional cellular automata, Commun. Math. Phys.,

136, 599-605, 1991.
[20] A. R. Smith III, Simple computational universal spaces, J. Assoc. Comput. Mach., 18, 339-353, 1971.
[21] S. Ulam, Random process and transformations, Proc. Int. Congress of Math., 2, 264-275, 1952.
[22] G. Y. Vichniac, Boolean derivatives on cellular automata, Phys. D, 45, 63-74, 1990.
[23] J. von Neumann, Theory of self-reproducing automata, Univ. of Illinois Press, Urbana, 1966.
[24] P. Walters, An introduction to ergodic theory, Springer-Verlag New York, 1982.
[25] T. Ward, Additive cellular automata and volume growth, Entropy, 2, 142-167, 2000.
[26] J. R. Weimar, J. J. Tyson, and L. T. Watson, Third generation cellular automaton for modeling

excitable media, Phys. D, 55, 328-339, 1992.
[27] S. Wolfram, Statistical mechanics of cellular automata, Rev. Modern Physics, 55, 601-644, 1983.

51


	Introduction
	Preliminaries
	Ergodicity on Permutive Cellular Automata
	The Topological Pressure of Power Rule of CA
	Acknowledgment
	References