# The Measure-Theoretic Entropy and Topological Entropy of Actions overℤm

Authors: Chih-Hung Chang; Yu-Wen Chen
Journal: Journal of Mathematics
 (2013)

---

## Abstract

This paper studies the quantitative behavior of a class of one-dimensional cellular automata, named weakly permutive cellular automata, acting on the space of all doubly infinite sequences with values in a finite ringℤm, m≥2. We calculate the measure-theoretic entropy and the topological entropy of weakly permutive cellular automata with respect to any invariant measure on the space ℤmℤ. As an application, it is shown that the uniform Bernoulli measure is the unique maximal measure for linear cellular automata among the Markov measures.


---

## Body

## 1. Introduction

Cellular automata (CA for brevity), introduced by Ulam and von Neumann, have been systematically studied by Hedlund from purely mathematical point of view [1]. The study of such dynamics called CA has received remarkable attention in the last few years [1–3]. CA have been widely investigated in a lot of disciplines (e.g., mathematics, physics, and computer science). In [2], the dynamical behavior (ergodicity and topological transitivity) of n-dimensional linear CA (LCA) over the ring ℤm has been studied. Some open questions concerning the topological and ergodic dynamics of one-dimensional CA have been addressed in [4].It is well known that there are several notions of entropy (i.e., measure-theoretical, topological, and directional) of measure-preserving transformation on probability space in ergodic theory. It is important to know how these notions are related with each other. In the last years, a lot of works are devoted to this subject (see, e.g., [5–13]). Recall that by the Variational Principle the topological entropy is the supremum of the entropies of invariant measures. In [8, 14, 15], the authors showed that the uniform Bernoulli measure is a measure of maximal entropy for some one-dimensional CA.The notion of entropy has been extensively studied in many disciplines (e.g., computer science, mathematics, physics, chemistry, and information theory) with different purposes. This notion first arose in thermodynamics as a measure of the heat absorbed (or emitted), when external work is done on a system. In probability theory, it constitutes a measure of the uncertainty. The entropy has been interpreted as a measure of the chaotic character of a dynamical system by many authors (see [4, 16, 17]), the value htop(T) has been in general accepted as a measure of the complexity of the dynamics of T over the space X. Some authors have stated that the topological entropy of a map is a crude global measure of the exponential complexity of the structure of the orbits of the map (see [4, 17]). Badii and Politi [18] have studied the complexity exhibited by some CA with elementary rule by using both topological (graph-theoretical) and metric (thermodynamic) techniques. Lloyd and Pagels [19] have defined a measure complexity for the macroscopic states of physical systems. They have proved that the average complexity of a state must be proportional to Shannon entropy of the set of trajectories, S=-∑i‍pilogpi.In this paper we study the measure-theoretical entropy and topological entropy of one-dimensionalweakly permutiveCA F (defined later) acting on the space of all doubly infinite sequences with values in a finite ring ℤm, m≥2. In [14], the author computed the measure-theoretical entropy with respect to the uniform Bernoulli measure for the case where F is linear defined by the local rule f(x-r,…,xr)=∑i=-rr‍xi. Recently, Ban et al. [15] studied the complexity of permutative CA (defined later) in thermodynamics and topological aspects, and they also gave the formulae to compute measure-theoretic and topological entropies. In this paper, for both measure-theoretic and topological entropies, we extend results obtained in [8, 14, 15, 20] to the case that F is a weakly permutive CA over the ring ℤm with respect to any invariant measure. We remark that LCA is a special case of weakly permutive CA. In addition, the formula of topological entropy extends D’amico et al.’s result [17] for the topological entropy of LCA. We also show that the uniform Bernoulli measure is the unique maximal measure for LCA, whenever we focus on the Markov measures.We give an example herein. Suppose that the local rule is given by(1)f(x-2,x-1,x0,x1,x2)=18x-1+30(x0+x1)+20x2(mod90)
(cf. Figure 1). The local rule is nonlinear. Applying Theorems 4 and 11, we conclude that the topological entropy of the prescribed weakly permutive CA is 4log3+log5 (see Example 10).Figure 1
Spatial-temporal pattern determined by local rulef(x-2,x-1,x0,x1,x2)=18x-1+30(x0+x1)+20x2(mod90) in Example 10 with initial configuration (⋯010⋯). Theorems 4 and 11 indicate that the topological entropy is 4log3+log5 and the uniform Bernoulli measure is a maximal measure.The rest of the elucidation is organized as follows. The upcoming section gives some definitions and results of permutive and weakly permutive CA. Section3 demonstrates formulae of the measure-theoretic and topological entropies. The uniform Bernoulli measure is a measure of maximal entropy that is also demonstrated in Section 3.


## 2. Preliminary

Letℤm={0,1,…,m-1}, and let Ω=ℤmℤ be the space of bi-infinite sequence x=(xn)-∞∞. Hedlund examines CA in the viewpoint of symbolic dynamical systems [1]. He shows that F:Ω→Ω is a CA if and only if F can be represented as a sliding block code; that is, there exist k∈ℤ+ and a block map f:ℤm2k+1→ℤm such that F(x)i=f(xi-k,…,xi+k) for x∈Ω and i∈ℤ. Such f is called the local rule of F. The study of the local rule of a CA is essential for the understanding of this system.A local rulef:ℤm2k+1→ℤm is called leftmost (resp., rightmost) permutive if there exists an integer i, -k≤i≤-1 (resp., 1≤i≤k), such that (i)
fis a permutation at xi whenever the other variables are fixed;(ii)
f does not depend on xj for j<i (resp., j>i).f is called bipermutive provided f is both left-most and right-most permutive. The family of permutive cellular automata consists of the following three types of local rules: (1)
f is leftmost permutive and does not depend on xi for i>0;(2)
f is rightmost permutive and does not depend on xi for i<0;(3)
f is bipermutive. Without loss of generality, we may assume that f(xℓ,…,xr) depends only on xi for ℓ≤i≤r and the coefficients of xℓ and xr are both nonzero in ℤm. Let m=p1k1p2k2·pnkn be factorized into the product of prime factors. Suppose that a local rule f is given, and set fi(xℓ,…,xr)=f(xℓ,…,xr)modpiki. f is called weakly permutive if, for 1≤i≤n, there is τi∈ℕ such that fiτi is either constant, a multiple of an identity map, or permutive.The present elucidation investigates the measure-theoretic and topological entropies of weakly permutive CA. For reader’s convenience, we recall definitions of measure-theoretic entropy, topological entropy, and topological pressures. Reader may refer to [13] for more details.Letμ be an invariant probability measure on (Ω,F), and let α and β be two finite measurable partitions of Ω. Define α⋁β and Hμ(α) by
(2)α⋁β={A⋂‍B:A∈α,B∈β},Hμ(α)=-∑A∈α‍μ(A)logμ(A),
respectively. The measure-theoretic entropy of F is defined by
(3)hμ(F)=sup{limn→∞1nHμ(⋁i=0n-1F-iα)},
where the supremum is taken over all finite measurable partitions α.Defined:Ω×Ω→ℝ by
(4)d(x,y)=∑i=-∞∞‍|xi-yi|m|i|,x,y∈Ω.
It is easy to verify that d is a metric and (Ω,d) is a compact metric space. Moreover, let a[sa,…,sb]b={x∈Ω:xa=sa,…,xb=sb} be a cylinder in Ω, where a≤b,a,b∈ℤ. Then a[sa,…,sb]b is not only open but close in Ω. Let 𝒫 be an open cover of Ω, denoted by
(5)H(𝒫)=inf{log#𝒫^},
where the infimum is taken over the set of finite subcovers 𝒫^ of 𝒫 and #A denotes the cardinality of A. The topological entropy of F is defined by
(6)htop(F)=sup{limn→∞1nH(⋁i=0n-1F-i𝒫)},
where the supremum is taken over all open covers 𝒫.It is known that permutive possesses strongly mixing [3, 21]. Recall that F:Ω→Ω is strongly mixing if
(7)limn→∞μ(F-nU∩V)=μ(U)μ(V)foreverymeasurablesetsU,V⊂Ω.
The following example demonstrates that permuittivity cannot be omitted.Example 1.
Letf:ℤ43→ℤ4 be defined as
(8)f(x0,x1,x2)=2x0+x1+[25x2]+[34x2]-x2mod4,
where [·] is Gauss function. It is seen that f is a permutation at x1 but not permutive. Observe that x is Garden of Eden for x∈{y∈ℤ4ℤ:yi=0,yi+1=1  for  some  i∈ℤ}; namely, there exists no preimage of x. Then F is not strongly mixing.


## 3. Entropy of Weakly Permutive Cellular Automata

LetX,Y be two compact topological spaces, and let ν be a probability measure on X. If ϕ:X→Y is onto, the push forward measure νY of ν on Y is defined by νY=ν∘ϕ-1. It is wellknown that νY is also a probability measure.Lemma 2.
Letm=pq for some relative prime factors p and q. Denote
(9)fp(xℓ,…,xr)=f(xℓ,…,xr)modp,fq(xℓ,…,xr)=f(xℓ,…,xr)modq.
Then hμ(F)=hμp(Fp)+hμq(Fq) provided μ≅μp×μq, where μp and μq are the push forward measures of μ on ℤpℤ and ℤqℤ, respectively, and Fp and Fq are CA with local rules fp and fq, respectively.Proof.
DenoteΩp=ℤpℤ and Ωq=ℤqℤ. Define Φ:Ω→Ωp×Ωq by
(10)(Φx)i=(ximodp,ximodq),i∈ℤ.
Observe that ℤm≅ℤp×ℤq indicates that Φ is an isomorphism. Moreover,
(11)(Φ∘F)(x)i=(f(xi+ℓ,…,xi+r)modp,f(xi+ℓ,…,xi+r)modq)=(fp(xi+ℓ,…,xi+r),fq(xi+ℓ,…,xi+r))=(fp(xi+ℓ,…,xi+rmodp),fq(xi+ℓ,…,xi+rmodq))=((Fp×Fq)∘Φ)(x)i,
for i∈ℤ. That is, the diagram
(12)
commutes. ThusF is topologically conjugated to Fp×Fq. The isomorphism μ≅μp×μq indicates that hμ(F)=hμp×μq(Fp×Fq)=hμp(Fp)+hμq(Fq).
The proof is completed.Remark 3.
Notably, the demonstration of Lemma2 asserts that a CA F defined on ℤmℤ is topologically conjugated to the direct product of the projection of F on ℤpℤ and ℤqℤ provided that m=pq and p is relatively prime to q.
Theorem4 comes straightforwardly from the definition of weakly permutive CA and Lemma 2, and hence the proof is omitted.Theorem 4.
Letm=p1k1·p2k2⋯pnkn for some prime factors pi and ki∈ℕ. Suppose that F is a weakly permutive CA, μ is F-invariant, and μ≅μ1×⋯×μn, where μi is the push-forward measure of μ on ℤpikiℤ for i=1,…,n. Then
(13)hμ(F)=∑i=1n‍hμi(Fi).An immediate application of Theorem4 is computing the measure-theoretic entropy of a linear CA (LCA). Herein F is an LCA if its corresponding local rule is given by f(xℓ,…,xr)=Σi=ℓraiximodm for some ai∈ℤ, i=ℓ,…,r.Theorem 5.
Letm=p1k1·p2k2⋯pnkn for some prime pi and ki∈ℕ. Suppose F is an LCA and μ is F-invariant such that μ≅μ1×μ2×⋯×μn. Then
(14)hμ(F)=∑i=1n‍hμi(Fi).
Moreover, suppose that μ is a Bernoulli measure. Denote
(15)Ci={j:(aj,pi)=1}⋃‍{0},(16)r-i=maxCi,ℓ-i=minCi,
for 1≤i≤n. Then
(17)hμ(F)=∑i=1n‍hμi(Fi)=∑i=1n‍(r-i-ℓ-i)∑j=0piki-1‍-pijlogpij,
where pij=μi(j), 1≤i≤n,0≤j≤piki-1.Remark 6.
Theorem5 only presents the explicit form of the measure-theoretic entropy of an LCA with respect to a Bernoulli measure. The exact formula of the measure-theoretic entropy of an LCA with respect to a Markov measure can also be obtained. Since the formula is much complicated, we omit the case.
Before demonstrating Theorem5, we introduce the following lemma.Lemma 7.
Letm=pk for some prime p, k∈ℕ. If F is an LCA, then F is weakly permutive.Proof.
Denote byℒ the collection of linear local rules, and ℤm[x,x-1]={Σi=n1n2aixi,n1,n2∈ℤ}. Define χ:ℒ→ℤm[x,x-1] by
(18)χ(∑i=n1n2‍λixi)=∑i=n1n2‍λix-i.
It is easily seen that χ is bijective. Moreover, let ℤm[[x,x-1]] denote the power series generated by {x,x-1} over ℤm. Then χ^:Ω→ℤm[[x,x-1]] defined by
(19)χ^(b)=∑i=-∞∞‍bixi,whereb=(bi)i∈ℤ∈Ω,
is also a bijection. Observe that, for each b=(bi)∈Ω,
(20)χ^(Tf[-r,r](b))=χ^[(∑n=-r+ir+i‍an-ibn)i]=∑i=-∞∞‍(∑n=-r+ir+i‍an-ibn)xi,𝕋(χ^(b))=𝕋(∑i=-∞∞‍bixi)=∑n=-rr‍anx-n(∑i=-∞∞‍bixi)=∑i=-∞∞‍(∑n=-r+ir+i‍an-ibn)xi,
where 𝕋≡χ(f). This implements that the diagram
(21)
commutes. Moreover, yielding the Mathematical Induction, we havefn=χ-1(𝕋n) for all n∈ℕ, where fn=f∘fn-1.
Write𝕋(x) as 𝕋(x)=𝕋1(x)+p𝕋2(x) such that 𝕋1(x) is consisting of those monomials whose coefficients are coprime to p. We claim that, for all i∈ℕ,
(22)(𝕋1(x)+p𝕋2(x))pi≡𝕋1pi(x)(modpi+1).
It is seen that
(23)(𝕋1(x)+p𝕋2(x))p=∑j=0p‍(pj)(𝕋1(x))j(p𝕋2(x))p-j≡∑j=p-1p‍(pj)(𝕋1(x))j(p𝕋2(x))p-j(modp2)=p(𝕋1(x))p-1(p𝕋2(x))+𝕋1p(x)≡𝕋1p(x)(modp2).
Suppose that
(24)(𝕋1(x)+p𝕋2(x))pk≡𝕋1pk(x)(modpk+1)
In other words, (𝕋1(x)+p𝕋2(x))pk=pk+1Q(x)+𝕋1pk(x) for some Q(x). Therefore,
(25)(𝕋1(x)+p𝕋2(x))pk+1=[(𝕋1(x)+p𝕋2(x))pk]p=[pk+1Q(x)+𝕋1pk(x)]p=∑j=0p‍(pj)(pk+1Q(x))j[𝕋1pk(x)]p-j≡∑j=01‍(pj)(pk+1Q(x))j[𝕋1pk(x)]p-j(modpk+2)≡𝕋1pk+1(x)(modpk+2).
This demonstrates our claim by the mathematical induction.
Letn=pk-1; then 𝕋n(x)≡𝕋1n(x)(modpk), and fn=χ-1(𝕋n) is permutive. The proof is completed.Theorem5 is obtained by combining Lemma 7 and the following result.Theorem 8 (see [15]).
Suppose that the local rule of a CAF is given by f(xi,…,xj), where i≤j, i,j∈ℤ and μ=(p0,…,pm-1) is an F-invariant Bernoulli measure. Denote L=min{i,0} and R=max{j,0}. One has the following results.(i)
Iff is left permutive, then hμ(F)=L∑k=0m-1pklogpk;(ii)
Iff is right permutive, then hμ(F)=-R∑k=0m-1pklogpk;(iii)
Iff is bipermutive, then hμ(F)=-(R-L)∑k=0m-1pklogpk.
In general, Lemma7 does not hold. For instance, let f:ℤ63→ℤ6 be defined by f(x0,x1,x2)=x0+2x1mod6. Then f is weakly rightmost permutive. However, χfn=(1+2x-1)n whose coefficient of x-n is either 2 or 4mod6 for all n∈ℕ. Thus fn cannot be rightmost permutive for n∈ℕ.Example 9.
Letm=12, and let μ be the (p0,p1,…,p11)-Bernoulli measure. Then Ω≅Ω1×Ω2, where Ω1=ℤ4ℤ and Ω2=ℤ3ℤ. And the push forward measure of μ on Ω1 and Ω2 is
(26)μ1=(p0+p4+p8,p1+p5+p9,p2+p6+p10,p3+p7+p11),μ2=(p0+p3+p6+p9,p1+p4+p7+p10,p2+p5+p8+p11),
respectively. Set f(x-1,x0,x1,x2)=2x-1+x0+2x1+3x2; then
(27)f1(x-1,x0,x1,x2)=2x-1+x0+2x1+3x2mod4,f2(x-1,x0,x1,x2)=2x-1+x0+2x1mod3,r-1=2,ℓ-1=0,r-2=1,ℓ-2=-1.
Theorem 5 indicates that
(28)hμ(F)=hμ1(F1)+hμ2(F2)=-2((p0+p4+p8)log(p0+p4+p8)+(p1+p5+p9)log(p1+p5+p9)+(p2+p6+p10)log(p2+p6+p10)+(p3+p7+p11)log(p3+p7+p11)+(p0+p3+p6+p9)log(p0+p3+p6+p9)+(p1+p4+p7+p10)log(p1+p4+p7+p10)+(p2+p5+p8+p11)log(p2+p5+p8+p11)).Example 10.
Supposem=90=2·32·5. Let f:ℤ904→ℤ90 be given by f(x-1,x0,x1,x2)=18x-1+10x1(x0+x1)+20x2mod90. Then Ω≅Ω1×Ω2×Ω3 with Ω1=ℤ2ℤ, Ω2=ℤ9ℤ, and Ω3=ℤ5ℤ. It is seen that f1=0mod2 is a constant map, and f2=x1(x0+x1)+2x2mod9 and f3=3x-1mod5 are both permutive. Hence f is weakly permutive but not linear. Theorems 4 and 8 assert that
(29)hμ(F)=hμ2(F2)+hμ3(F3)=-2∑i=08‍p2ilogp2i-∑i=04‍p3ilogp3i
provided μ≅μ1×μ2×μ3, where pji is defined in Theorem 5.
Similar to the discussion of the formula of the measure-theoretic entropy of weakly permutive CA, the topological entropy of weakly permutive CA can be obtained analogously.Theorem 11.
Letm=p1k1p2k2·pnkn be factorized into the product of prime factors. Suppose that F is a weakly permutive CA and Fi is the projection of F on ℤpikiℤ for i=1,…,n. Then
(30)htop(F)=∑i=1n‍htop(Fi).In [17], the authors demonstrated the formula of the topological entropy of LCA. Lemma 7 indicates that LCA is a proper subset of weakly permutive CA. That makes Theorem 11 an extension of Theorem 12. More precisely, (31) holds for the topological entropy of weakly permutive CA.Theorem 12.
Letm=p1k1p2k2·pnkn be factorized into the product of prime factors. Suppose that F is a LCA. Then
(31)htop(F)=∑i=1n‍ki(r-i-ℓ-i)logpi,
where r-i and ℓ-i are defined in (16).Remark 13.
The variational principle in thermodynamic formalism indicates that the topological entropy of a compact system is obtained by the supermum of its measure-theoretic entropies among all invariant measures, and a measure that attains the supremum is called a maximal measure. It comes immediately from Theorems5 and 12 that, if we only consider invariant Markov measures, the uniform Bernoulli measure is the unique maximal measure for LCA.Example 14.
Letm and f be the same as in Example 9, and let μ be the uniform Bernoulli measure; then
(32)hμ(F)=-2(log14+log13)=4log2+2log3=htop(F).Example 15.
Letm and f be the same as in Example 10, and let μ be the uniform Bernoulli measure; then
(33)hμ(F)=-2log19-log15=4log3+log5=htop(F).



---

*Source: 404626-2013-06-12.xml*