# Geometric Representations of Interacting Maps

Authors: Tsuyoshi Kato
Journal: International Journal of Mathematics and Mathematical Sciences
 (2010)

---

## Abstract

Tropical geometry is a kind of dynamical scale transform which connects automata with real rational dynamics. Real rational dynamics are deeply studied from global analytic viewpoints. On the other hand, automata appear in various contexts in topology, combinatorics, and integrable systems. In this paper we study the analysis of these materials passing through tropical geometry. In particular we discover a new duality on the set of automata which arise from the projective duality in algebraic geometry.


---

## Body

## 1. Introduction

Motivated by the phenomena in molecular biology, in [1] we have formulated random interaction systems by use of families of maps on intervals, which consist  of infinite families of compositions between them. By wasting detailed and extracting more rough information by use of projections, one can produce automata. This construction covers some discrete integrable systems which possess solitons. This paper is a trial to represent creation of some macroscopic patterns which arise from random and micro dynamics.Letf:[0,1]→[0,1] be a map, and consider its iteration {fn(x)}n=0∞. This will behave very randomly and will touch sensitively with respect to the initial points x∈[0,1] (see [2]).LetX2={(a0,a1,…):ai∈{0,1}}  be the set of one-sided sequences, and take two maps {f0,f1}. Let us generalize the iteration of a single map to random compositions by two maps. Let us choose an element  k¯=(k0,k1,…)∈X2. Then, correspondingly one obtains families of maps {hn:[0,1]→[0,1]}n=0,1,… on the interval by compositions hn(x)=fkn∘⋯fk0(x).Using them, one can construct continuous mapsΦ(x)=Φ(f1,f2)(x):X2→X2 for each point x∈[0,1], which are called the interaction maps. These are defined by use of projections on the interval, and so their values are determined by which subinterval hn(x) lies on for each n. Thus in order to determine a value Φ(x)(k¯), it is enough to know rough values of them, rather than rigorous ones on [0,1], even though one is required to have information on hn(x) for all n. So Φ(x) is a map in a macroscopic scale compared with the micro interaction {hn(x)}. This might explain one aspect of a very simple mechanism to create patterns in macro scale from random micro dynamics. This method is immediately generalized to use families of maps on intervals {fi}i, and one also obtains interaction maps Φ(f1,…,fk) by the same way.So far, we have known that many important cell automata can be expressible by interaction systems as above (see [3, 1.A]). In the first part of this paper, we study geometric properties of such cell automata which include the box and ball system (BBS), Lotka-Volterra cell automaton, and lamplighter automaton. For example, we will construct assignments from BBS flows to braid groups and extensions of BBS actions on compactified spaces passing through group actions on trees. We will see some relation between LV cell automaton and the lamplighter automaton, and generalize the latter to obtain more group actions on trees using such relation.In the middle part, we study connections of automata with complex geometry. In real algebraic geometry, some geometric mappings from complex planes to the real ones were discovered, by taking coordinatewisely absolute values and their logarithms (see [4, 5]). This connects algebraic varieties with piecewise linear maps and is called the tropical geometry. On the other hand, in [6] several relations of pl maps with automata are studied. For example, the LV cell automaton is given by a family of pl maps. Passing through the above operations, in this paper we will associate a family of polynomials from an automaton. Using the projective duality on projective varieties and the above assignment, we will discover a duality between cell automata. In fact, for an automaton A, we will associate a dual one A∨, and call it as the projectively dual automaton. We will calculate some examples in the case of curves. Notice that duality on the Mealy automata was already introduced by exchanging the role of the exit and the transition functions mutually (see [7, 8]).In general, automata are represented by families of interaction maps. Thus direct assignments from families of maps to these geometric objects will show geometric representations of interaction systems.In the last part, we construct infinite families of graphs from finite families of maps, points, and symbolic sequences, and we call them theinteraction graphs. We will construct these graphs so that they represent some dynamics of interacting states in mesoscopic scale. The central dogma in molecular biology tells us that proteins are products of various interaction systems in mesoscopic scale, beginning from DNA. From geometric point of view, one would like to obtain a space and an automorphism on it from such interacting data, which will represent more macro features. In analogy to the central dogma as above, the space will be compared with protein or polymer, and orbits of the automorphism correspond to states on it, since functions of proteins are determined by the shapes of themselves.Abiological space-form problem is to construct a space V and an automorphism A on it so that the orbits {x,A(x),A2(x),…}⊂V are induced from the dynamics of the interaction graphs. In this paper we will formulate and address a space-form problem from toric variety viewpoint, passing through several hierarchies of dynamics.Throughout this paper, our basic direction is to study geometric properties of them as macro objects, which are induced by scaling transform of dynamics by compositions and iterations of families of maps as the micro one. In some particular cases of families of maps which include some piecewise linear maps, the interaction maps induce some automata.On the other hand, in general, maps on intervals are very flexible objects and their dynamics are very random. One of our main aims in further development will be to study macro properties of these dynamics for families of maps which are near such special types of maps. Namely, let{fi}i be a family as above so that the corresponding interaction system induces some automaton A. Let us take any geometric object G=G({fi}i) arising from the interaction system. We have several examples of G below. Since G passes through A, its structure will hold some rigid properties.Let us take another family of maps{gi}i which is sufficiently near the original {fi}i, where the corresponding interaction system for {gi}i may not induce any automata in general. We would like to study geometric properties of G({gi}i) by comparing with G({fi}i). This might give one direction of study to understand  mechanisms of creation of patterns. In particular,  several stability properties of G under small deformation of these maps will be particularly of interest for us.Now let us describe the contents of the paper more concretely.The box and ball system (BBS) is a dynamical system on the set of finite subsets inZ (see [9]). Let us describe the dynamics shortly. For {i1,…,il}⊂Z with i1<i2<⋯<il, let us imagine that a ball occupies in each position im for m=1,…,l. These balls will be moved by the following rule; the ball  i1 in the most left-hand side is moved to some i1<j1 which is the most left-hand side in {i1+1,i1+2,…}∖{i2,…,il}. We repeat the same procedure for ik with 2≤k≤l. When this procedure is finished for il, then we are done.LetΣ20 be all  of the finite subsets in Z. Then, the above procedure is expressed as  (1.1)T:Σ20≅Σ20.
Let Σ20(N)⊂Σ20 be the sets of N-subsets in Z. Then, since BBS preserves the number of the balls, T is a map as T:Σ20(N)≅Σ20(N).Following our expression of interaction, in Section2, we will describe the BBS system by an interaction of maps for some family of continuous maps.It is known that the BBS flows by the dynamics ofT contain solitons. Among dynamical properties of solitons, the relative positions of the individual waves and how these waves pass through the others will be in the most important structures. In Section 3 we will represent such information geometrically by using the braid groups. Elements in braid groups are certainly representing such situation. In order to eliminate infinitely many ambiguities, in this paper we will use quotient groups B¯n of the braid groups. There are many of them, and in a special case it is a subgroup of the mapping class group of finite index. Each σ admits an index among subsets in {1,…,N-1}, which is determined by Tt(σ) near t=±∞. We will associate a quotient braid group with respect to individual index. Then, we obtain the canonical maps  (1.2)B:Σ20(N)→B¯N
which we call the braiding map. B(σ) is constructed from the dynamics of iterations (1.3){…,T-1,σ,T(σ),T2(σ),…}.
Scattering process of BBS is described in [10] by using the combinatorial R-matrix. Using such direction, one may obtain some invariants of the dynamics T.LetΣ2 be the set of two-sided sequences with the alphabets {0,1}. Then, Σ20 can be regarded as a subset Σ2. In Section 5, we study geometric properties of the BBS map T. For example, we see that it can be extended as T:Σ2→Σ2.The Lotka-Volterra cell automaton is given by the equation (see [9])  (1.4)Vnt+1-Vnt=max(0,Vn+1t-L)-max(0,Vn-1t+1-L).
This is obtained from the original Lotka-Volterra equation by making discretizations twice. It is known that this possesses solitons which are induced from the ones of the difference LV solitons (see [3]). BBS is isomorphic to the Lotka-Volterra cell automaton. In fact, there is an explicit procedure to construct such isomorphism. Thus one obtains an injection Σ20↪Σ∞0 which assigns flows of the BBS to the corresponding dynamics of the LV. We will see that it can be extended on some partially compactified space. In Section 4, we study structures of path spaces of the set of cell automata, which arose from the relation of LV-CA with BBS.The lamplighter group is well known as an automata group in geometric group theory (see [11]), which admits an action on the rooted binary tree. In Section 5, we find that in a special case the LV cell automaton is in fact a transition function for the lamplighter automaton.Lemma 1.1.
Suppose that the initial sequence(a0,a1,…) consists of only {0,1} entries. Then, the degeneration of the LV cell automaton is the same as the transition function ϕ of an automaton whose group is isomorphic to the lamplighter group.Thus using the LV cell automaton as transition functions, one can construct a family of automata groups which we callLV cell automata groups. They can act on the boundary ∂̃T∞*≡⋃i∂Ti* of the rooted infinite tree.In Section6, we study automata from complex geometry point of view. Tropical geometry connects algebraic geometry with automata. There is a kind of scale transform Φt with t∈(1,∞) by taking absolute values and taking the conjugation by Logt (see [4, 12]). To a pair of parameterized polynomials (ft1,ft2), both limt→∞Φt(ft1) and limt→∞Φt(ft2) become piecewise linear maps. In general, the equation Φ∞(f∞1)=Φ∞(f∞2) represent complicated dynamics, but in some cases it gives automata. This is the point where  we find importance to study stability of the dynamics. We study this aspect in Section 6.3.2.On the other hand, the above process is invertible in the sense that one can associate pairs of parameterized polynomials(ft1,ft2) from automata A. Now using these polynomials, one can obtain spaces as follows.Definition 1.2.
The associated affine hypersurfaces are   parameterized family of hypersurfaces given by the following equations:(1.5)V(A)t={z∈CN:ft1(z)=ft2(z)}.One important reason to consider such varieties comes fromprojective duality on algebraic varieties. Let us denote by X∨  the projective dual of an algebraic variety X. Suppose that the projective duals of V(A)t are also hypersurfaces. The parameterized families of polynomials Δ(A)t which define these hypersurfaces  are called A-discriminant.Again by taking the above scaling limit in tropical geometry, one obtains another automatonA∨. Thus passing through duality in complex geometry, there is an assignment between automata: (1.6)A→A∨.
We call A∨ the projectively dual automaton.We have calculated in the case of some curves. Leta≥2, α, and c be integers. Then, we have the following.Proposition 1.3.
Consider the following:(1.7)[max{aun,α+aun+1}=c]∨=max{aa-1(c-αa)+aa-1un+1,aca-1+aa-1un}=c.In micro level, molecular interactions occur by covalent or hydrogen bonds where electrons of molecules share their orbitals. Inspired on this aspect, in Section7 one  formulates interaction systems of families of maps by constructing some graphs.Let us take two interval mapsf0,f1:[0,1]→[0,1] and let  Φ(x,f0,f1):X2→X2 be the interaction map. Let us choose another map d:[0,1]→[0,1]. In the light of orbitals stated above, if the projection of the iterations {dn(z)}n coincides with Φ(x,f,g)(k¯) in X2, then we construct a marked oriented edge as  (1.8)(f,x)→(g,k¯)(d,z).Let us fix families of maps{f1,…,fk}, points {x1,…,xl}⊂[0,1],  and {a¯(i,j,h)}i,j,h=1i,j=k,h=l∈X2. By the above way, we obtain the corresponding oriented marked finite graph  (1.9)G({fi},{xj},{a¯(i,j,h)}).
We call them the interaction graphs.One can interpret these graphs to represent states of the system consisted by the triple({fi},{xj},{a¯(i,j,h)}).Let us choose(fi,fj,xh). Then, we have the corresponding interaction map Φ(fi,fj,xh):X2→X2. In particular one can obtain  other elements as follows: (1.10)a¯(i,j,h)2≡Φ(fi,fj,xh)(a¯(i,j,h))∈X2.
By this way one can obtain another interaction graph: (1.11)G({fi},{xj},{a¯(i,j,h)2}).Let us denote by𝔊({fi},{xj}) the set of interaction graphs with fixed families of maps and points. The numbers of vertices are all the same in any element in this. Notice that this is a finite set. Then, by the above procedure one has obtained the following map: (1.12)Φ*:𝔊({fi},{xj})→𝔊({fi},{xj}).By iterating this procedure, one obtains an infinite family of interaction graphsG({fi},{xj},{a¯(i,j,h)}), G({fi},{xj},{a¯(i,j,h)2}), G({fi},{xj},{a¯(i,j,h)3}),…. One can regard that this family of interaction graphs might represent dynamics of states of the micro interaction systems, and according to our principle at the beginning of the introduction, one may induce some macro patterns from them. In this paper we will induce some hierarchies of combinatoric objects arising from such family of graphs.Let𝔊 be the set of finite graphs, and let  F:𝔊({fi},{xj})→𝔊 be the forgetful map. Passing through F, one obtains a family of finite graphs: (1.13)G1≡F(G¯1),G2…⊂𝔊,G¯t=G({fi},{xj},{a¯(i,j,h)t}),
which we call just the associated graphs. Any Gi has the same number of vertices N. Thus there is a finite number of finite graphs {H1,…,Hm} so that each Gi coincides with one of {Hj}.We say that a family of finite graphs isstrongly regular  if they have the same number of edges as others.LetG be a finite graph. Then, the associated configurationa¯∈Zm in combinatorics is determined. Thus one obtains another family of configurations: (1.14)a¯1,a¯2,a¯3,…⊂Zm,
which we call the transcripted configurations.For each configurationa¯∈Z, one obtains an ideal Ia¯⊂C[y1,…,ym] which is called the toric ideal. Thus associated to the family of configurations, one obtains the corresponding family of ideals: (1.15)I1,I2,…,Ij⊂C[y1,…,ymj],
which we call the associated ideals.For each idealI⊂C[y1,…,ym], one obtains a complete fan over Rm and the corresponding toric variety XI⊂CPm-1. The fan is called the Gröbner fan.Thus corresponding to the associate ideals, one obtains a family of toric varieties:(1.16)X1,X2,…⊂CPm-1,m=sup{m1,m2,…}.
We call the sequence as the translated toric variety. When the associated graphs are strongly regular, then all Xj have the same dimension.Let us have more abstract setting. LetV be an algebraic variety with the affine coordinates Vi defined by an ideal Ji. Let us take an automorphism A on V. We say that an affine coordinate {(Vi,Ji)}i=1m is an (stable) algebraic Markov partition for A  if, for each i, there is some j so that  (1.17)A(Vi)⊂Vj
holds.We say that the  associated ideals{Ii}i are regular  if they have the same dimension as others. Let us put ⋃iIi={J1,…,Jk}. Now we have one realization of the space-form problem.Definition 1.4.
Let({fi}i,{xj}j,{a¯(i,j,h)}) be   interaction data, and suppose that the associated ideals I=(I0,I1,…) are regular. The sequence is called a symbolic flow of an automorphism  if there is an algebraic Markov partition for (V,A) with an affine coordinate {(Vi,Ji)}i=1k and some x∈V so that its orbit {An(x)}n=0,1,… corresponds to the sequence.We would like to call such pair(V,A) a prohedron (which comes from “proteiform’’). We will see by an easy example that combinatorics of the interaction graphs will reflect existence of such pairs.The author would like to thank   the referee for giving him the useful suggestions and comments.


## 2. Automata and Interaction by Families of Maps

### 2.1. Classes of Automata

In this paper we treat some automata  whose classes we will clarify below.LetA be a finite set called the alphabet, and let Q be a set called the state set.Let us introduce the most general form of automata here. Letm,l≥0 be integers. A bounded automatonA over A is given by two functions: (2.1)ψ:Q×Am+l+2→A,ϕ:Q×A→Q.A flow of the sets of strings of one-sided infinite length(2.2){k¯t=(k0t,k1t,…):kit∈A}t≥0
is determined by A  if {kNt}N,t≥0 satisfy the following relations: (2.3)kit+1=ψ(qit+1,ki-lt,…,ki+mt,ki-1t+1),qit=ϕ(qi-1t,kit).We regard that they grow time  evolutionally ask¯0→k¯1→⋯→k¯t→⋯.One can similarly consider the two-sided case(2.4){k¯t=(…,k-nt,…,k0t,k1t,…):kit∈A}t≥0.


#### 2.1.1. Mealy Automaton (see [7, 8])

AMealy automatonA over X is given by two functions: (2.5)ψ:Q×A→A,ϕ:Q×A→Q.(A) One-Sided Case
Let(2.6)XA={k¯=(k0,k1,…):ki∈A}
be all of the set of strings of one-sided infinite length. Then, each q∈Q induces a continuous map
(2.7)Aq:XA→XA
given by  Aq(k0,k1,…)=(k0′,k1′,…), where ki′ are inductively defined with q-1=q as follows:
(2.8)ki′=ψ(qi,ki),qi=ϕ(qi-1,ki).
One can check easily that Mealy automata can be obtained by choosingψ:Q×A→A by kit+1=ψ(qit+1,kit) and ϕ are the same.
LetXAN={k¯*=(k0,k1,…,kN):ki∈A} be the set of words of length N with alphabet X. Then,  Aq restricts the action as Aq:XAN→XAN for all N∈{0,1,2,…}.
Letm=|A| and let  Tm be the rooted m-tree. The set of all vertices of Tm can be identified with XA∞≡⋃NXAN. Thus Aq gives the following  action:
(2.9)Aq:Tm→Tm.
Let us say thatA is invertible (see [7])  if  ψ(q,):A≅A  are one-to-one onto for all q∈Q. An invertible automaton A gives automorphisms Aq:Tm≅Tm, and the group generated by the set of states is denoted by G(A):
(2.10)G(A)=gen{Aq:Tm≅Tm:q∈Q}.(B) Two-Sided Case
LetA={0,1,…,L-1} and let S be a finite set. Let us consider the two maps
(2.11)ψ:S×A→A,ϕ:S×A→S
equipped with the initial state q∈S. These data give a structure of Mealy automaton A.
Let us put the set of the two-sided sequences byΣL={(…,v-n,…,v0,…):vi∈A}. Let σ=(…,v-n,…,v0,…) be an infinite sequence by {0,…,L-1} such that vn=v-n=0 holds for all sufficiently large n≫0. Let us denote the set of such sequences by
(2.12)ΣL0={(…,v-n,…,v0,v1,…):vi∈A,vn=0∀large|n|≫0}.
Notice that ΣL0 are shift invariant.
Let us say thatA is semiproper if ψ(q,0)=0 is satisfied.
IfA is semi-proper, then it induces a continuous map
(2.13)Aq:ΣL0→ΣL,Aq(…,vn,vn+1,…)=(…,vn′,vn+1′,…)
given by the same rule as that of the one-sided case. Namely, let us take (…,vn,vn+1,…)∈ΣL0, and choose sufficiently small m0 so that vm=0 holds for all m≤m0. Then, we define inductively as
(2.14)vm0+k′=ψ(sk,vm0+k),sk=ϕ(sk-1,vm0+k),
where we put vm′=0 for all m≤m0. This is independent of choice of m0 and gives an assignment
(2.15)Aq:(…,vm,vm+1,…)→(…,vm′,vm+1′,…).
LetA be a Mealy automaton which is semi-proper. If it induces a continuous map
(2.16)Aq:ΣL0→ΣL0,
then we say that A is proper.


#### 2.1.2. Cellular Automaton

The cell automata we treat here require only the initial states. LetA=Q, and take a function ψ:A3→A. Then, each q∈Q=A induces a continuous map  (2.17)Aq:XA→XA
given by  Aq(k0,k1,…)=(k0′,k1′,…), where ki′ are inductively defined with k-1′=q: (2.18)ki′=ψ(ki,ki+1,ki-1′).
So the flows {k¯t}t satisfy the relations kit+1=ψ(kit,ki+1t,ki-1t+1).


### 2.2. Interacting Maps

Let us take the two interval maps(2.19)f0,f1:[0,1]→[0,1]
and consider their iterations  as (2.20)O0(x)={f0k(x)}k=0,1,…,O1(x)={f1k(x)}k=0,1,….
We call them the oscillations (see [3]).Let us defineinteraction of these orbits below. For this, let X2 be the set of one-sided sequences with two alphabets {0,1} as follows: (2.21)X2={(k0,k1,…):ki∈{0,1}}.
For each element k¯=(k0,k1,…)∈X2, we associate a family of maps {hm}m=0,1,… with hm:[0,1]→[0,1] by the random iterations  (2.22)hm(x)≡fkm∘fkm-1∘⋯∘fk0(x).Let(2.23)π:[0,1]→{0,1}
be the measurable map given by π([0,1/2))≡0 and π((1/2,1])≡1. Then, for each x∈[0,1], one can compose {hm(x)}m with π and obtain  another element for a.e. x as follows: (2.24)k¯′≡π((h0(x),h1(x),…))≡(π∘h0(x),π∘h1(x),…)∈X2.
This assignment gives a map from each element k¯ to k¯′. We denote this map  (2.25)Φ(x,f0,f1):X2→X2
by Φ(x,f,g)(k¯)=k¯′≡π((h0(x),h1(x),…))  and call it the interaction map.Let us introduce a generalization of the interaction. Let us fix a set of alphabets{0,1,…,L}  and choose a family of maps {fi,j}i,j=0,1,…,L and k¯∈XL+1. Then, we define inductively  (2.26)hm(x)=fkm,km+1∘hm-1(x),h-1(x)≡x.
We say that {hm(x)}m is a two-step interaction.Letπ:[0,1]→{0,1,…,L}  be the projection. Then, as before one obtains a map (2.27)Φ(x):XL+1→XL+1,Φ(x)(k̅)=k̅',k̅m′=π∘hm(x).
Let Φ:XL+1→XL+1 be a map, and take an initial condition  (2.28)(k00,k10,k20,…)
and a boundary condition  (2.29)(k01,k02,k03,…).
Then, we inductively put  (2.30)(k0t,k1t,…)=Φ(k0t-1,k1t-1,…)=Φt(k00,k10,k20,…)∈XL+1.
We call (k0t,k1t,…) as the flow of Φ.In Section6, we consider the flow of the Lotka-Volterra cell automaton by the iteration of the interaction map for some family of interval maps. LV cell automaton is isomorphic to the BBS system described below. We will study the isomorphism in Section 4.


### 2.3. BBS System

LetΣ2 be the set of two-sided sequences with two alphabets, and consider its subsets Σ20⊂Σ2: (2.31)Σ20={(…,v-n,…,v0,v1,…)∈Σ2:vn=0∀large|n|≫0}.
Notice that it is shift invariant.Let us describe the dynamical systemT:Σ20≅Σ20 called BBS below (see [9]). One can canonically identify Σ20 with the set of ordered integers  (2.32)Σ20≅O={i1<i2<⋯<im:ik∈{…,0,1,…},m∈ℕ}
by (…,v-n,…,vn,…)→{n:vn=1} as in the introduction.Let us choose an elementσ∈Σ20 and let  (i1<i2<⋯<im) be the corresponding ordered integers. Let  (2.33)T(σ)1=(…,v-m1,…,v01,v11,…)∈Σ20
be another element defined as follows: let j1≥i1 be the smallest index with vj1=0. Then, we put  (2.34)vl1={vl,l≠i1,j1,0,l=i1,1,l=j1.Next we do the same thing forvi21=vi2 in T(σ)1  and find another smallest index j2≥i2 with vj21=0. Then, we exchange 0 and 1 in vi21 and vj21 as above. The result is denoted by T(σ)2.We continue this process fori3,i4,… until im, and finally one obtains the desired T(σ)≡T(σ)m∈Σ20.Thus one has obtained a continuous bijective map(2.35)T:Σ20≅Σ20
which is calld the box and ball system (BBS) (see [13]).LetON={i1<i2<⋯<iN:ik∈{…,0,1,…}}⊂O be the subset consisted by the set of exactly N indices. Let Σ20(N)⊂Σ20 be the corresponding subsets. Then, the BBS system preserves them and induces bijections T:Σ20(N)≅Σ20(N).


#### 2.3.1. BBS as a Mealy Automaton

Let us describe the BBS mapT by an interaction of a family of interval maps. The basic method will take two steps. Firstly we will describe it by a proper Mealy automaton, and then we write down the automaton by an interaction of a family of maps. Here we will use some modified way in order to express it by a family of continuous maps. For the presentation, see also  Section 4.1.Firstly we will construct an automatonA. It will induce a map M:Σ20(N)≅Σ20(N) which corresponds to T(σ)1 in   Section 2.3.  Then, the BBS map T:Σ20(N)≅Σ20(N) is given by T∣Σ20(N)=MN.Lemma 2.1.
For the state setS={0,1,2,3,4} with the initial state 0, there is a proper Mealy automaton A which induces M:Σ20≅Σ20.Proof.
Let us defineA by
(2.36)ψ:S×{0,1}→{0,1},ϕ:S×{0,1}→S,
where
(2.37)ψ(a,)={ϵ,a=1,2,id,a=0,3,4
(ϵ∈S2 is the nontrivial element in the permutation group on {0,1}).
It is immediate to check the conclusion. This completes the proof.Let us consider expressing BBS by an  interaction of maps. Let us denoteϕ={ϕ0,ϕ1} as in Table 1 and ψ={ψ0,ψ1}, where ϕi:S→S and ψi:S→{0,1} for i=0,1. Let π:[0,1]→{0,1} and π5:[0,1]→{0,1,2,3,4} be the canonical projections.Table 1
Values ofϕ.
01234002424113434If the automaton above is described by compositions of a family of continuous maps{αi}i=0,1 and {fi}i=0,1 as ϕi=π5∘αi and ψi=π∘fi, then we say that the automaton is given by an interaction of maps on intervals (see [6]).It is immediate to see that the aboveA cannot be expressible by a family of continuous maps as above. So we will modify as follows. Let us choose two permutations  ϵ0,ϵ1:S≅S. Then, we say that A is given by a modified interaction of maps with respect to (ϵ0,ϵ1), if there are families of continuous maps {αi}i=0,1 and {fi}i=0,1 so that the following hold:(2.38)ϕi=ϵi∘π5∘αi,ψi=π∘fi.When these maps can be chosen piecewisely linearly, then tropical geometry in Section6 can be applied, since piecewise linear functions can have representations by the relative arithmetics of (max,+). BBS is also the following case.Lemma 2.2.
There are families of continuous maps and permutations so that they give the modified interaction of maps representing the proper Mealy automatonA above. In particular the BBS automaton is given by MN=M∘⋯∘M on Σ20(N) for N=0,1,2,….Proof.
Let us choose permutations  as(2.39)ϵ0:(0,1,2,3,4)→(0,2,4,1,3),ϵ1:(0,1,2,3,4)→(0,1,3,4,2).
Then, we can choose piecewise linear functionsαi and fi so that they satisfy the following properties:
(2.40)α0∣[i5,i+15]⊂[i5,i+15],i=0,1,2,α0∣[35,45]⊂[15,25],α0∣[45,1]⊂[25,35],α1∣[i5,i+15]⊂[i+15,i+25],i=0,1,2,α1∣[i5,i+15]⊂[i-15,i5],i=3,4,f0∣[j5,j+15]⊂[0,12],j=0,3,4,f0∣[j5,j+15]⊂[12,1],j=1,2,f1∣[j5,j+15]⊂[0,12],j=1,2,f1∣[j5,j+15]⊂[0,15],j=0,3,4.
This completes the proof.


## 2.1. Classes of Automata

In this paper we treat some automata  whose classes we will clarify below.LetA be a finite set called the alphabet, and let Q be a set called the state set.Let us introduce the most general form of automata here. Letm,l≥0 be integers. A bounded automatonA over A is given by two functions: (2.1)ψ:Q×Am+l+2→A,ϕ:Q×A→Q.A flow of the sets of strings of one-sided infinite length(2.2){k¯t=(k0t,k1t,…):kit∈A}t≥0
is determined by A  if {kNt}N,t≥0 satisfy the following relations: (2.3)kit+1=ψ(qit+1,ki-lt,…,ki+mt,ki-1t+1),qit=ϕ(qi-1t,kit).We regard that they grow time  evolutionally ask¯0→k¯1→⋯→k¯t→⋯.One can similarly consider the two-sided case(2.4){k¯t=(…,k-nt,…,k0t,k1t,…):kit∈A}t≥0.


### 2.1.1. Mealy Automaton (see [7, 8])

AMealy automatonA over X is given by two functions: (2.5)ψ:Q×A→A,ϕ:Q×A→Q.(A) One-Sided Case
Let(2.6)XA={k¯=(k0,k1,…):ki∈A}
be all of the set of strings of one-sided infinite length. Then, each q∈Q induces a continuous map
(2.7)Aq:XA→XA
given by  Aq(k0,k1,…)=(k0′,k1′,…), where ki′ are inductively defined with q-1=q as follows:
(2.8)ki′=ψ(qi,ki),qi=ϕ(qi-1,ki).
One can check easily that Mealy automata can be obtained by choosingψ:Q×A→A by kit+1=ψ(qit+1,kit) and ϕ are the same.
LetXAN={k¯*=(k0,k1,…,kN):ki∈A} be the set of words of length N with alphabet X. Then,  Aq restricts the action as Aq:XAN→XAN for all N∈{0,1,2,…}.
Letm=|A| and let  Tm be the rooted m-tree. The set of all vertices of Tm can be identified with XA∞≡⋃NXAN. Thus Aq gives the following  action:
(2.9)Aq:Tm→Tm.
Let us say thatA is invertible (see [7])  if  ψ(q,):A≅A  are one-to-one onto for all q∈Q. An invertible automaton A gives automorphisms Aq:Tm≅Tm, and the group generated by the set of states is denoted by G(A):
(2.10)G(A)=gen{Aq:Tm≅Tm:q∈Q}.(B) Two-Sided Case
LetA={0,1,…,L-1} and let S be a finite set. Let us consider the two maps
(2.11)ψ:S×A→A,ϕ:S×A→S
equipped with the initial state q∈S. These data give a structure of Mealy automaton A.
Let us put the set of the two-sided sequences byΣL={(…,v-n,…,v0,…):vi∈A}. Let σ=(…,v-n,…,v0,…) be an infinite sequence by {0,…,L-1} such that vn=v-n=0 holds for all sufficiently large n≫0. Let us denote the set of such sequences by
(2.12)ΣL0={(…,v-n,…,v0,v1,…):vi∈A,vn=0∀large|n|≫0}.
Notice that ΣL0 are shift invariant.
Let us say thatA is semiproper if ψ(q,0)=0 is satisfied.
IfA is semi-proper, then it induces a continuous map
(2.13)Aq:ΣL0→ΣL,Aq(…,vn,vn+1,…)=(…,vn′,vn+1′,…)
given by the same rule as that of the one-sided case. Namely, let us take (…,vn,vn+1,…)∈ΣL0, and choose sufficiently small m0 so that vm=0 holds for all m≤m0. Then, we define inductively as
(2.14)vm0+k′=ψ(sk,vm0+k),sk=ϕ(sk-1,vm0+k),
where we put vm′=0 for all m≤m0. This is independent of choice of m0 and gives an assignment
(2.15)Aq:(…,vm,vm+1,…)→(…,vm′,vm+1′,…).
LetA be a Mealy automaton which is semi-proper. If it induces a continuous map
(2.16)Aq:ΣL0→ΣL0,
then we say that A is proper.


### 2.1.2. Cellular Automaton

The cell automata we treat here require only the initial states. LetA=Q, and take a function ψ:A3→A. Then, each q∈Q=A induces a continuous map  (2.17)Aq:XA→XA
given by  Aq(k0,k1,…)=(k0′,k1′,…), where ki′ are inductively defined with k-1′=q: (2.18)ki′=ψ(ki,ki+1,ki-1′).
So the flows {k¯t}t satisfy the relations kit+1=ψ(kit,ki+1t,ki-1t+1).


## 2.1.1. Mealy Automaton (see [7, 8])

AMealy automatonA over X is given by two functions: (2.5)ψ:Q×A→A,ϕ:Q×A→Q.(A) One-Sided Case
Let(2.6)XA={k¯=(k0,k1,…):ki∈A}
be all of the set of strings of one-sided infinite length. Then, each q∈Q induces a continuous map
(2.7)Aq:XA→XA
given by  Aq(k0,k1,…)=(k0′,k1′,…), where ki′ are inductively defined with q-1=q as follows:
(2.8)ki′=ψ(qi,ki),qi=ϕ(qi-1,ki).
One can check easily that Mealy automata can be obtained by choosingψ:Q×A→A by kit+1=ψ(qit+1,kit) and ϕ are the same.
LetXAN={k¯*=(k0,k1,…,kN):ki∈A} be the set of words of length N with alphabet X. Then,  Aq restricts the action as Aq:XAN→XAN for all N∈{0,1,2,…}.
Letm=|A| and let  Tm be the rooted m-tree. The set of all vertices of Tm can be identified with XA∞≡⋃NXAN. Thus Aq gives the following  action:
(2.9)Aq:Tm→Tm.
Let us say thatA is invertible (see [7])  if  ψ(q,):A≅A  are one-to-one onto for all q∈Q. An invertible automaton A gives automorphisms Aq:Tm≅Tm, and the group generated by the set of states is denoted by G(A):
(2.10)G(A)=gen{Aq:Tm≅Tm:q∈Q}.(B) Two-Sided Case
LetA={0,1,…,L-1} and let S be a finite set. Let us consider the two maps
(2.11)ψ:S×A→A,ϕ:S×A→S
equipped with the initial state q∈S. These data give a structure of Mealy automaton A.
Let us put the set of the two-sided sequences byΣL={(…,v-n,…,v0,…):vi∈A}. Let σ=(…,v-n,…,v0,…) be an infinite sequence by {0,…,L-1} such that vn=v-n=0 holds for all sufficiently large n≫0. Let us denote the set of such sequences by
(2.12)ΣL0={(…,v-n,…,v0,v1,…):vi∈A,vn=0∀large|n|≫0}.
Notice that ΣL0 are shift invariant.
Let us say thatA is semiproper if ψ(q,0)=0 is satisfied.
IfA is semi-proper, then it induces a continuous map
(2.13)Aq:ΣL0→ΣL,Aq(…,vn,vn+1,…)=(…,vn′,vn+1′,…)
given by the same rule as that of the one-sided case. Namely, let us take (…,vn,vn+1,…)∈ΣL0, and choose sufficiently small m0 so that vm=0 holds for all m≤m0. Then, we define inductively as
(2.14)vm0+k′=ψ(sk,vm0+k),sk=ϕ(sk-1,vm0+k),
where we put vm′=0 for all m≤m0. This is independent of choice of m0 and gives an assignment
(2.15)Aq:(…,vm,vm+1,…)→(…,vm′,vm+1′,…).
LetA be a Mealy automaton which is semi-proper. If it induces a continuous map
(2.16)Aq:ΣL0→ΣL0,
then we say that A is proper.


## 2.1.2. Cellular Automaton

The cell automata we treat here require only the initial states. LetA=Q, and take a function ψ:A3→A. Then, each q∈Q=A induces a continuous map  (2.17)Aq:XA→XA
given by  Aq(k0,k1,…)=(k0′,k1′,…), where ki′ are inductively defined with k-1′=q: (2.18)ki′=ψ(ki,ki+1,ki-1′).
So the flows {k¯t}t satisfy the relations kit+1=ψ(kit,ki+1t,ki-1t+1).


## 2.2. Interacting Maps

Let us take the two interval maps(2.19)f0,f1:[0,1]→[0,1]
and consider their iterations  as (2.20)O0(x)={f0k(x)}k=0,1,…,O1(x)={f1k(x)}k=0,1,….
We call them the oscillations (see [3]).Let us defineinteraction of these orbits below. For this, let X2 be the set of one-sided sequences with two alphabets {0,1} as follows: (2.21)X2={(k0,k1,…):ki∈{0,1}}.
For each element k¯=(k0,k1,…)∈X2, we associate a family of maps {hm}m=0,1,… with hm:[0,1]→[0,1] by the random iterations  (2.22)hm(x)≡fkm∘fkm-1∘⋯∘fk0(x).Let(2.23)π:[0,1]→{0,1}
be the measurable map given by π([0,1/2))≡0 and π((1/2,1])≡1. Then, for each x∈[0,1], one can compose {hm(x)}m with π and obtain  another element for a.e. x as follows: (2.24)k¯′≡π((h0(x),h1(x),…))≡(π∘h0(x),π∘h1(x),…)∈X2.
This assignment gives a map from each element k¯ to k¯′. We denote this map  (2.25)Φ(x,f0,f1):X2→X2
by Φ(x,f,g)(k¯)=k¯′≡π((h0(x),h1(x),…))  and call it the interaction map.Let us introduce a generalization of the interaction. Let us fix a set of alphabets{0,1,…,L}  and choose a family of maps {fi,j}i,j=0,1,…,L and k¯∈XL+1. Then, we define inductively  (2.26)hm(x)=fkm,km+1∘hm-1(x),h-1(x)≡x.
We say that {hm(x)}m is a two-step interaction.Letπ:[0,1]→{0,1,…,L}  be the projection. Then, as before one obtains a map (2.27)Φ(x):XL+1→XL+1,Φ(x)(k̅)=k̅',k̅m′=π∘hm(x).
Let Φ:XL+1→XL+1 be a map, and take an initial condition  (2.28)(k00,k10,k20,…)
and a boundary condition  (2.29)(k01,k02,k03,…).
Then, we inductively put  (2.30)(k0t,k1t,…)=Φ(k0t-1,k1t-1,…)=Φt(k00,k10,k20,…)∈XL+1.
We call (k0t,k1t,…) as the flow of Φ.In Section6, we consider the flow of the Lotka-Volterra cell automaton by the iteration of the interaction map for some family of interval maps. LV cell automaton is isomorphic to the BBS system described below. We will study the isomorphism in Section 4.


## 2.3. BBS System

LetΣ2 be the set of two-sided sequences with two alphabets, and consider its subsets Σ20⊂Σ2: (2.31)Σ20={(…,v-n,…,v0,v1,…)∈Σ2:vn=0∀large|n|≫0}.
Notice that it is shift invariant.Let us describe the dynamical systemT:Σ20≅Σ20 called BBS below (see [9]). One can canonically identify Σ20 with the set of ordered integers  (2.32)Σ20≅O={i1<i2<⋯<im:ik∈{…,0,1,…},m∈ℕ}
by (…,v-n,…,vn,…)→{n:vn=1} as in the introduction.Let us choose an elementσ∈Σ20 and let  (i1<i2<⋯<im) be the corresponding ordered integers. Let  (2.33)T(σ)1=(…,v-m1,…,v01,v11,…)∈Σ20
be another element defined as follows: let j1≥i1 be the smallest index with vj1=0. Then, we put  (2.34)vl1={vl,l≠i1,j1,0,l=i1,1,l=j1.Next we do the same thing forvi21=vi2 in T(σ)1  and find another smallest index j2≥i2 with vj21=0. Then, we exchange 0 and 1 in vi21 and vj21 as above. The result is denoted by T(σ)2.We continue this process fori3,i4,… until im, and finally one obtains the desired T(σ)≡T(σ)m∈Σ20.Thus one has obtained a continuous bijective map(2.35)T:Σ20≅Σ20
which is calld the box and ball system (BBS) (see [13]).LetON={i1<i2<⋯<iN:ik∈{…,0,1,…}}⊂O be the subset consisted by the set of exactly N indices. Let Σ20(N)⊂Σ20 be the corresponding subsets. Then, the BBS system preserves them and induces bijections T:Σ20(N)≅Σ20(N).


### 2.3.1. BBS as a Mealy Automaton

Let us describe the BBS mapT by an interaction of a family of interval maps. The basic method will take two steps. Firstly we will describe it by a proper Mealy automaton, and then we write down the automaton by an interaction of a family of maps. Here we will use some modified way in order to express it by a family of continuous maps. For the presentation, see also  Section 4.1.Firstly we will construct an automatonA. It will induce a map M:Σ20(N)≅Σ20(N) which corresponds to T(σ)1 in   Section 2.3.  Then, the BBS map T:Σ20(N)≅Σ20(N) is given by T∣Σ20(N)=MN.Lemma 2.1.
For the state setS={0,1,2,3,4} with the initial state 0, there is a proper Mealy automaton A which induces M:Σ20≅Σ20.Proof.
Let us defineA by
(2.36)ψ:S×{0,1}→{0,1},ϕ:S×{0,1}→S,
where
(2.37)ψ(a,)={ϵ,a=1,2,id,a=0,3,4
(ϵ∈S2 is the nontrivial element in the permutation group on {0,1}).
It is immediate to check the conclusion. This completes the proof.Let us consider expressing BBS by an  interaction of maps. Let us denoteϕ={ϕ0,ϕ1} as in Table 1 and ψ={ψ0,ψ1}, where ϕi:S→S and ψi:S→{0,1} for i=0,1. Let π:[0,1]→{0,1} and π5:[0,1]→{0,1,2,3,4} be the canonical projections.Table 1
Values ofϕ.
01234002424113434If the automaton above is described by compositions of a family of continuous maps{αi}i=0,1 and {fi}i=0,1 as ϕi=π5∘αi and ψi=π∘fi, then we say that the automaton is given by an interaction of maps on intervals (see [6]).It is immediate to see that the aboveA cannot be expressible by a family of continuous maps as above. So we will modify as follows. Let us choose two permutations  ϵ0,ϵ1:S≅S. Then, we say that A is given by a modified interaction of maps with respect to (ϵ0,ϵ1), if there are families of continuous maps {αi}i=0,1 and {fi}i=0,1 so that the following hold:(2.38)ϕi=ϵi∘π5∘αi,ψi=π∘fi.When these maps can be chosen piecewisely linearly, then tropical geometry in Section6 can be applied, since piecewise linear functions can have representations by the relative arithmetics of (max,+). BBS is also the following case.Lemma 2.2.
There are families of continuous maps and permutations so that they give the modified interaction of maps representing the proper Mealy automatonA above. In particular the BBS automaton is given by MN=M∘⋯∘M on Σ20(N) for N=0,1,2,….Proof.
Let us choose permutations  as(2.39)ϵ0:(0,1,2,3,4)→(0,2,4,1,3),ϵ1:(0,1,2,3,4)→(0,1,3,4,2).
Then, we can choose piecewise linear functionsαi and fi so that they satisfy the following properties:
(2.40)α0∣[i5,i+15]⊂[i5,i+15],i=0,1,2,α0∣[35,45]⊂[15,25],α0∣[45,1]⊂[25,35],α1∣[i5,i+15]⊂[i+15,i+25],i=0,1,2,α1∣[i5,i+15]⊂[i-15,i5],i=3,4,f0∣[j5,j+15]⊂[0,12],j=0,3,4,f0∣[j5,j+15]⊂[12,1],j=1,2,f1∣[j5,j+15]⊂[0,12],j=1,2,f1∣[j5,j+15]⊂[0,15],j=0,3,4.
This completes the proof.


## 2.3.1. BBS as a Mealy Automaton

Let us describe the BBS mapT by an interaction of a family of interval maps. The basic method will take two steps. Firstly we will describe it by a proper Mealy automaton, and then we write down the automaton by an interaction of a family of maps. Here we will use some modified way in order to express it by a family of continuous maps. For the presentation, see also  Section 4.1.Firstly we will construct an automatonA. It will induce a map M:Σ20(N)≅Σ20(N) which corresponds to T(σ)1 in   Section 2.3.  Then, the BBS map T:Σ20(N)≅Σ20(N) is given by T∣Σ20(N)=MN.Lemma 2.1.
For the state setS={0,1,2,3,4} with the initial state 0, there is a proper Mealy automaton A which induces M:Σ20≅Σ20.Proof.
Let us defineA by
(2.36)ψ:S×{0,1}→{0,1},ϕ:S×{0,1}→S,
where
(2.37)ψ(a,)={ϵ,a=1,2,id,a=0,3,4
(ϵ∈S2 is the nontrivial element in the permutation group on {0,1}).
It is immediate to check the conclusion. This completes the proof.Let us consider expressing BBS by an  interaction of maps. Let us denoteϕ={ϕ0,ϕ1} as in Table 1 and ψ={ψ0,ψ1}, where ϕi:S→S and ψi:S→{0,1} for i=0,1. Let π:[0,1]→{0,1} and π5:[0,1]→{0,1,2,3,4} be the canonical projections.Table 1
Values ofϕ.
01234002424113434If the automaton above is described by compositions of a family of continuous maps{αi}i=0,1 and {fi}i=0,1 as ϕi=π5∘αi and ψi=π∘fi, then we say that the automaton is given by an interaction of maps on intervals (see [6]).It is immediate to see that the aboveA cannot be expressible by a family of continuous maps as above. So we will modify as follows. Let us choose two permutations  ϵ0,ϵ1:S≅S. Then, we say that A is given by a modified interaction of maps with respect to (ϵ0,ϵ1), if there are families of continuous maps {αi}i=0,1 and {fi}i=0,1 so that the following hold:(2.38)ϕi=ϵi∘π5∘αi,ψi=π∘fi.When these maps can be chosen piecewisely linearly, then tropical geometry in Section6 can be applied, since piecewise linear functions can have representations by the relative arithmetics of (max,+). BBS is also the following case.Lemma 2.2.
There are families of continuous maps and permutations so that they give the modified interaction of maps representing the proper Mealy automatonA above. In particular the BBS automaton is given by MN=M∘⋯∘M on Σ20(N) for N=0,1,2,….Proof.
Let us choose permutations  as(2.39)ϵ0:(0,1,2,3,4)→(0,2,4,1,3),ϵ1:(0,1,2,3,4)→(0,1,3,4,2).
Then, we can choose piecewise linear functionsαi and fi so that they satisfy the following properties:
(2.40)α0∣[i5,i+15]⊂[i5,i+15],i=0,1,2,α0∣[35,45]⊂[15,25],α0∣[45,1]⊂[25,35],α1∣[i5,i+15]⊂[i+15,i+25],i=0,1,2,α1∣[i5,i+15]⊂[i-15,i5],i=3,4,f0∣[j5,j+15]⊂[0,12],j=0,3,4,f0∣[j5,j+15]⊂[12,1],j=1,2,f1∣[j5,j+15]⊂[0,12],j=1,2,f1∣[j5,j+15]⊂[0,15],j=0,3,4.
This completes the proof.


## 3. Quotient of the Braid Groups and BBS System

### 3.1. Quotient of the Braid Groups

LetBn be the braid group with n-strands. It has the following  presentation: (3.1)Bn={t1,…,tn-1:titj=tjti,|i-j|>1,titi+1ti=ti+1titi+1}.
It has a canonical element representing the half-twist, that is, (3.2)Ωn≡(t1…tn-1)(t1…tn-2)⋯(t1t2)t1∈Bn.
The quotient group by Ωn2 is isomorphic to a subgroup of the mapping class group on (n+1)-punctured sphere, which is consisted by groups which fix  ∞ point and index n+1 (see [14]): (3.3)Bn/〈Ωn2〉⊂MPGn+1.Let us generalize it and have quotient braid groups.Leti=1,…,n-1 and k=0,…,n-1, and denote subsets by [i,k]≡(i,i+1,…,i+k)⊂{1,…,n-1}. Let B[i,k]⊂Bn be the subgroup generated by {ti,…,ti+k}. By the same way, each B[i,k] contains the following  corresponding canonical elements: (3.4)Ω[i,k]∈B[i,k].We will define two types of quotients of the braid groups using these canonical elements.Definition 3.1.
The mod2 braid group M2B¯n is given by the following:
(3.5)M2B̅n={t1,…,tn-1:titj=tjti,|i-j|>1,titi+1ti=ti+1titi+1,ti2}=Bn/gen〈⋃i=1n-1ti2〉.
For example, M2B¯2=Z2 and M2B¯3 is an infinite group which has a presentation given by Z2*Z2/〈t1t2t12t2t1〉.
Let us denote the quotient map by(3.6)π:Bn→M2B¯n.Lemma 3.2.
Letπ(Ω[i,k]2)=1∈M2B¯n for any i,k.  Then, in particular one has
(3.7)M2B¯n=Bn/gen〈⋃[i,k]⊂{1,…,n-1}Ω[i,k]2〉.Proof.
We check forn=4, and the general case will follow from this immediately.
In factπ(Ω42)=(t1t2t3t1t2t1)(t1t2t3t1t2t1)=t1t2t3t1t2t12t2t3t1t2t1=t1t2t3t1t22t3t1t2t1=t1t2t3t1t3t1t2t1=t1t2t3t3t1t1t2t1=1.
This completes the proof.LetI⊂{1,…,n-1}2  be a set of subsets, and denote by gen〈ΩI:I∈I〉 the group generated by elements ΩI. Then, we define another type of quotient braid groups by  (3.8)B¯n(I)=Bn/gen〈ΩI:I∈I〉.
Notice that we do not include elements like (i,0) which correspond to one string. We will denote πI:Bn→B¯n(I) for the projection.Later we will have geometric meaning to divide by the twists in terms of the BBS system. In particular we will see in the following section that solitary behaviour in BBS system can be represented as an element in the quotient braid groups.


### 3.2. Solitary Flow

Anyσ∈Σ20 can be uniquely expressed by a finite set  (3.9){I1,…,Il}≡{(i1,N1),…,(il,Nl)},
where Nj≥1 and l≥0. They satisfy the following:(1)
vj=1 for all j∈⋃k=1,…,l{ik,ik+1,…,ik+Nk-1},(2)
vj=0 holds for some j in {ik+Nk,…,ik+1-1}, k=1,…,l.We call(N1,…,Nl) the index of σ. Thus one may regard each Ij as one soliton.Letσ∈Σ20 and consider the BBS map T. The indices of Tt(σ), (S1,…,Sm) are all constant for sufficiently small t≪0, and also for all sufficiently large t≫0, they are also constant (T1,…,Tm′), where ΣSi=ΣTj holds. Here inequalities hold as follows: (3.10)S1≥S2≥⋯≥Sm,T1≤T2≤⋯≤Tm′.
We say that σ has its type(3.11)({Si}i=1m,{Tj}j=1m′).Ifσ is a soliton, then the equality  (3.12)(T1,…,Tm′)=(Sm,Sm-1,…,S1)
holds. More precisely, let {σt}t∈Z⊂Σ20 be a flow. We say that it is solitary  if there are a set {M1,…,Mm}⊂N, 1≤M1<M2<⋯<Mm, and families {i1t,…,imt}⊂Z such that, for all sufficiently large t≫0,(3.13)σ-t={(i1-t,M1),(i2-t,M2),…,(im-t,Mm)},σt={(i1t,Mm),(i2t,Mm-1),…,(imt,M1)},
where (1)
i1t<i2t<⋯<imt and im-t<im-1-t<⋯<i1-t hold,(2)
|ij±t-ij+1±t|→∞ as t→∞ for all j=1,…,m-1.Thus for anyσ∈Σ20, the corresponding flow {Tt(σ)}t∈Z is solitary.


### 3.3. Assignment of Braid Elements

Let us takeσ∈Σ20(N), and let  T be the BBS map. Let us take a large t0≫0 so that T-t0(σ) and Tt0(σ) have indices (S1,…,Sm) and (T1,…,Tm′), respectively. Notice the equality N≡Σi=1mSi=Σj=1m′Tj.Let us putσ0≡T-t0(σ), and we consider the step T(σ0)i, i=1,…,m, in the definition of the map T  in Section 2.2.  For the step from σ0 to T(σ0)1, let us assign a natural element  (3.14)b1∈BN
below, where each string corresponds to an element 1 in σ0. Namely, when the most left-hand side 1 moves into a position passing through another r number of 1's, then tr-1⋯t1 is assigned. For example, if σ0=(…,0,1,1,0,…) moves as (…,0,0,1,1,…), then one generating element t1 is assigned. Similarly, if σ0=(…,1,1,1,0,…) which moves as (…,0,0,1,1,1,…), then t2t1 is assigned.Next for the second step fromT(σ0)1 to T(σ0)2, one assigns another element b2∈BN by the same way. Continuing, one obtains another b3,…,bm.By this way one has assigned an element(3.15)b=b(σ0,t0)=bmbm-1⋯b1∈BN
which we call the braiding element.


#### 3.3.1. Braiding Maps

Notice thatb depends on the choice of t0 and so σ0 in the above. In fact there will be infinitely many elements which are different from each other with respect to the choice of t0. The ambiguities arise from choices of the starting point σ0=T-t0(σ) and the ending point Tt0(σ). Let σ have the type ({Si}i=1m,{Tj}j=1m′). They are essentially given by the twists of the canonical elements (3.16)Ω[1,S1-1],Ω[S1+1,S2-1],Ω[S1+S2+1,S3-1],…,Ω[S1+⋯+Si-1+1,Si-1],
for the former and given for the latter by  (3.17)Ω[T1+⋯+Tj+1,Tj+1-1],Ω[T1+⋯+Tj+Tj+1+1,Tj+2-1],…,Ω[N-Tm′,Tm′-1],
where the rest indices all correspond to one string: (3.18)Sk=1(k=i+1,…,m),Tl=1(l=1,2,…,j).Let us denote the set(3.19)I(σ)={Tj+1[1,S1-1],[S1+1,S2-1],…,[S1+⋯+Si-1+1,Si-1],[T1+⋯+Tj+1,Tj+1-1],[T1+⋯+Tj+1+1,Tj+2-1],…,[N-Tm′,Tm′-1]Tj+1}.
We say that I(σ) is the index of the BBS flow for σ.LetI⊂{1,…,n-1} be a set of subsets. Then, we put  (3.20)Σ20(I)≡{σ∈Σ20:I(σ)=I}.LetπI be the projection as before. Then, we define the following restricted braiding map with respect toI as (3.21)B(I):Σ20(I)→B¯N(I)
by assigning πI(b), b=b(σ0,t0)). It is independent of choice of t0 and gives a single map.The above map depends onI. Below we will have another braiding map from Σ20 as a multivalued one. The target space is also obtained by the quotient of the braid group.Letπ:BN→M2B¯N be the projection. Thus π(b)∈M2B¯N have ambiguity at most finitely many elements with respect to t0. Now we define the mod 2braiding map: (3.22)B2:Σ20(N)→M2B¯N
as the images of all various values of t0 for sufficiently large |t0|≫0, given by π(b)≡b¯∈M2B¯N, where b is as above. Thus B2 is a finite multivalued mapWe callb¯ the  mod 2braiding element.


### 3.4. Connected Braiding Maps

Let us take two elements as follows:(3.23)σk=(…,0,ai1,k,…,aimk,k,0,…)∈Σ20,k=1,2.
Choose sufficiently large M≫0. Then, we define the connected sum of σ1 with σ2 of length M by  (3.24)σ1#Mσ2=(…,0,ai1,1,…,aim1,1,0,…,0,ai2,2,…,aim2,2,0,…)∈Σ20,
where 0 appears M times in the middle.The index of theconnected sum and their union are given by (3.25)I(σ1,σ2;M)=I(σ1)∪I(σ2)∪I(σ1#Mσ2)⊂{1,…,m1+m2-1},I(σ1,σ2)≡⋃M≫0I(σ1#Mσ2).
In fact  I(σ1,σ2;M) is completely determined by the triple  (I(σ1),I(σ2),M).LetIN be all of the set of subsets in {1,…,N-1} such that each element can be an index for some σ∈Σ20. Then, for large M≫0, there are maps  (3.26)HM:IN×IN′→IN+N′
which give the indices of connected sums.Thus these induce a family of maps(3.27)H(I,I′;M):B¯N(I)×B¯N′(I′)→B¯N+N′(HM(I,I′))
satisfying  (3.28)H(I,I′;M)(B(I)(σ1),B(I′)(σ2))=B(HM(I,I′))(σ1#Mσ2)
for I∈IN and I′∈IN′. We will say that H(I,I′;M) is a connected braiding map.Proposition 3.3.
H(I,I′;M) is eventually period with respect to M.This follows since the target space is divided by twists in braid groups.


## 3.1. Quotient of the Braid Groups

LetBn be the braid group with n-strands. It has the following  presentation: (3.1)Bn={t1,…,tn-1:titj=tjti,|i-j|>1,titi+1ti=ti+1titi+1}.
It has a canonical element representing the half-twist, that is, (3.2)Ωn≡(t1…tn-1)(t1…tn-2)⋯(t1t2)t1∈Bn.
The quotient group by Ωn2 is isomorphic to a subgroup of the mapping class group on (n+1)-punctured sphere, which is consisted by groups which fix  ∞ point and index n+1 (see [14]): (3.3)Bn/〈Ωn2〉⊂MPGn+1.Let us generalize it and have quotient braid groups.Leti=1,…,n-1 and k=0,…,n-1, and denote subsets by [i,k]≡(i,i+1,…,i+k)⊂{1,…,n-1}. Let B[i,k]⊂Bn be the subgroup generated by {ti,…,ti+k}. By the same way, each B[i,k] contains the following  corresponding canonical elements: (3.4)Ω[i,k]∈B[i,k].We will define two types of quotients of the braid groups using these canonical elements.Definition 3.1.
The mod2 braid group M2B¯n is given by the following:
(3.5)M2B̅n={t1,…,tn-1:titj=tjti,|i-j|>1,titi+1ti=ti+1titi+1,ti2}=Bn/gen〈⋃i=1n-1ti2〉.
For example, M2B¯2=Z2 and M2B¯3 is an infinite group which has a presentation given by Z2*Z2/〈t1t2t12t2t1〉.
Let us denote the quotient map by(3.6)π:Bn→M2B¯n.Lemma 3.2.
Letπ(Ω[i,k]2)=1∈M2B¯n for any i,k.  Then, in particular one has
(3.7)M2B¯n=Bn/gen〈⋃[i,k]⊂{1,…,n-1}Ω[i,k]2〉.Proof.
We check forn=4, and the general case will follow from this immediately.
In factπ(Ω42)=(t1t2t3t1t2t1)(t1t2t3t1t2t1)=t1t2t3t1t2t12t2t3t1t2t1=t1t2t3t1t22t3t1t2t1=t1t2t3t1t3t1t2t1=t1t2t3t3t1t1t2t1=1.
This completes the proof.LetI⊂{1,…,n-1}2  be a set of subsets, and denote by gen〈ΩI:I∈I〉 the group generated by elements ΩI. Then, we define another type of quotient braid groups by  (3.8)B¯n(I)=Bn/gen〈ΩI:I∈I〉.
Notice that we do not include elements like (i,0) which correspond to one string. We will denote πI:Bn→B¯n(I) for the projection.Later we will have geometric meaning to divide by the twists in terms of the BBS system. In particular we will see in the following section that solitary behaviour in BBS system can be represented as an element in the quotient braid groups.


## 3.2. Solitary Flow

Anyσ∈Σ20 can be uniquely expressed by a finite set  (3.9){I1,…,Il}≡{(i1,N1),…,(il,Nl)},
where Nj≥1 and l≥0. They satisfy the following:(1)
vj=1 for all j∈⋃k=1,…,l{ik,ik+1,…,ik+Nk-1},(2)
vj=0 holds for some j in {ik+Nk,…,ik+1-1}, k=1,…,l.We call(N1,…,Nl) the index of σ. Thus one may regard each Ij as one soliton.Letσ∈Σ20 and consider the BBS map T. The indices of Tt(σ), (S1,…,Sm) are all constant for sufficiently small t≪0, and also for all sufficiently large t≫0, they are also constant (T1,…,Tm′), where ΣSi=ΣTj holds. Here inequalities hold as follows: (3.10)S1≥S2≥⋯≥Sm,T1≤T2≤⋯≤Tm′.
We say that σ has its type(3.11)({Si}i=1m,{Tj}j=1m′).Ifσ is a soliton, then the equality  (3.12)(T1,…,Tm′)=(Sm,Sm-1,…,S1)
holds. More precisely, let {σt}t∈Z⊂Σ20 be a flow. We say that it is solitary  if there are a set {M1,…,Mm}⊂N, 1≤M1<M2<⋯<Mm, and families {i1t,…,imt}⊂Z such that, for all sufficiently large t≫0,(3.13)σ-t={(i1-t,M1),(i2-t,M2),…,(im-t,Mm)},σt={(i1t,Mm),(i2t,Mm-1),…,(imt,M1)},
where (1)
i1t<i2t<⋯<imt and im-t<im-1-t<⋯<i1-t hold,(2)
|ij±t-ij+1±t|→∞ as t→∞ for all j=1,…,m-1.Thus for anyσ∈Σ20, the corresponding flow {Tt(σ)}t∈Z is solitary.


## 3.3. Assignment of Braid Elements

Let us takeσ∈Σ20(N), and let  T be the BBS map. Let us take a large t0≫0 so that T-t0(σ) and Tt0(σ) have indices (S1,…,Sm) and (T1,…,Tm′), respectively. Notice the equality N≡Σi=1mSi=Σj=1m′Tj.Let us putσ0≡T-t0(σ), and we consider the step T(σ0)i, i=1,…,m, in the definition of the map T  in Section 2.2.  For the step from σ0 to T(σ0)1, let us assign a natural element  (3.14)b1∈BN
below, where each string corresponds to an element 1 in σ0. Namely, when the most left-hand side 1 moves into a position passing through another r number of 1's, then tr-1⋯t1 is assigned. For example, if σ0=(…,0,1,1,0,…) moves as (…,0,0,1,1,…), then one generating element t1 is assigned. Similarly, if σ0=(…,1,1,1,0,…) which moves as (…,0,0,1,1,1,…), then t2t1 is assigned.Next for the second step fromT(σ0)1 to T(σ0)2, one assigns another element b2∈BN by the same way. Continuing, one obtains another b3,…,bm.By this way one has assigned an element(3.15)b=b(σ0,t0)=bmbm-1⋯b1∈BN
which we call the braiding element.


### 3.3.1. Braiding Maps

Notice thatb depends on the choice of t0 and so σ0 in the above. In fact there will be infinitely many elements which are different from each other with respect to the choice of t0. The ambiguities arise from choices of the starting point σ0=T-t0(σ) and the ending point Tt0(σ). Let σ have the type ({Si}i=1m,{Tj}j=1m′). They are essentially given by the twists of the canonical elements (3.16)Ω[1,S1-1],Ω[S1+1,S2-1],Ω[S1+S2+1,S3-1],…,Ω[S1+⋯+Si-1+1,Si-1],
for the former and given for the latter by  (3.17)Ω[T1+⋯+Tj+1,Tj+1-1],Ω[T1+⋯+Tj+Tj+1+1,Tj+2-1],…,Ω[N-Tm′,Tm′-1],
where the rest indices all correspond to one string: (3.18)Sk=1(k=i+1,…,m),Tl=1(l=1,2,…,j).Let us denote the set(3.19)I(σ)={Tj+1[1,S1-1],[S1+1,S2-1],…,[S1+⋯+Si-1+1,Si-1],[T1+⋯+Tj+1,Tj+1-1],[T1+⋯+Tj+1+1,Tj+2-1],…,[N-Tm′,Tm′-1]Tj+1}.
We say that I(σ) is the index of the BBS flow for σ.LetI⊂{1,…,n-1} be a set of subsets. Then, we put  (3.20)Σ20(I)≡{σ∈Σ20:I(σ)=I}.LetπI be the projection as before. Then, we define the following restricted braiding map with respect toI as (3.21)B(I):Σ20(I)→B¯N(I)
by assigning πI(b), b=b(σ0,t0)). It is independent of choice of t0 and gives a single map.The above map depends onI. Below we will have another braiding map from Σ20 as a multivalued one. The target space is also obtained by the quotient of the braid group.Letπ:BN→M2B¯N be the projection. Thus π(b)∈M2B¯N have ambiguity at most finitely many elements with respect to t0. Now we define the mod 2braiding map: (3.22)B2:Σ20(N)→M2B¯N
as the images of all various values of t0 for sufficiently large |t0|≫0, given by π(b)≡b¯∈M2B¯N, where b is as above. Thus B2 is a finite multivalued mapWe callb¯ the  mod 2braiding element.


## 3.3.1. Braiding Maps

Notice thatb depends on the choice of t0 and so σ0 in the above. In fact there will be infinitely many elements which are different from each other with respect to the choice of t0. The ambiguities arise from choices of the starting point σ0=T-t0(σ) and the ending point Tt0(σ). Let σ have the type ({Si}i=1m,{Tj}j=1m′). They are essentially given by the twists of the canonical elements (3.16)Ω[1,S1-1],Ω[S1+1,S2-1],Ω[S1+S2+1,S3-1],…,Ω[S1+⋯+Si-1+1,Si-1],
for the former and given for the latter by  (3.17)Ω[T1+⋯+Tj+1,Tj+1-1],Ω[T1+⋯+Tj+Tj+1+1,Tj+2-1],…,Ω[N-Tm′,Tm′-1],
where the rest indices all correspond to one string: (3.18)Sk=1(k=i+1,…,m),Tl=1(l=1,2,…,j).Let us denote the set(3.19)I(σ)={Tj+1[1,S1-1],[S1+1,S2-1],…,[S1+⋯+Si-1+1,Si-1],[T1+⋯+Tj+1,Tj+1-1],[T1+⋯+Tj+1+1,Tj+2-1],…,[N-Tm′,Tm′-1]Tj+1}.
We say that I(σ) is the index of the BBS flow for σ.LetI⊂{1,…,n-1} be a set of subsets. Then, we put  (3.20)Σ20(I)≡{σ∈Σ20:I(σ)=I}.LetπI be the projection as before. Then, we define the following restricted braiding map with respect toI as (3.21)B(I):Σ20(I)→B¯N(I)
by assigning πI(b), b=b(σ0,t0)). It is independent of choice of t0 and gives a single map.The above map depends onI. Below we will have another braiding map from Σ20 as a multivalued one. The target space is also obtained by the quotient of the braid group.Letπ:BN→M2B¯N be the projection. Thus π(b)∈M2B¯N have ambiguity at most finitely many elements with respect to t0. Now we define the mod 2braiding map: (3.22)B2:Σ20(N)→M2B¯N
as the images of all various values of t0 for sufficiently large |t0|≫0, given by π(b)≡b¯∈M2B¯N, where b is as above. Thus B2 is a finite multivalued mapWe callb¯ the  mod 2braiding element.


## 3.4. Connected Braiding Maps

Let us take two elements as follows:(3.23)σk=(…,0,ai1,k,…,aimk,k,0,…)∈Σ20,k=1,2.
Choose sufficiently large M≫0. Then, we define the connected sum of σ1 with σ2 of length M by  (3.24)σ1#Mσ2=(…,0,ai1,1,…,aim1,1,0,…,0,ai2,2,…,aim2,2,0,…)∈Σ20,
where 0 appears M times in the middle.The index of theconnected sum and their union are given by (3.25)I(σ1,σ2;M)=I(σ1)∪I(σ2)∪I(σ1#Mσ2)⊂{1,…,m1+m2-1},I(σ1,σ2)≡⋃M≫0I(σ1#Mσ2).
In fact  I(σ1,σ2;M) is completely determined by the triple  (I(σ1),I(σ2),M).LetIN be all of the set of subsets in {1,…,N-1} such that each element can be an index for some σ∈Σ20. Then, for large M≫0, there are maps  (3.26)HM:IN×IN′→IN+N′
which give the indices of connected sums.Thus these induce a family of maps(3.27)H(I,I′;M):B¯N(I)×B¯N′(I′)→B¯N+N′(HM(I,I′))
satisfying  (3.28)H(I,I′;M)(B(I)(σ1),B(I′)(σ2))=B(HM(I,I′))(σ1#Mσ2)
for I∈IN and I′∈IN′. We will say that H(I,I′;M) is a connected braiding map.Proposition 3.3.
H(I,I′;M) is eventually period with respect to M.This follows since the target space is divided by twists in braid groups.


## 4. Transformations on Cell Automata

### 4.1. From BBS to LV

The Lotka-Volterra cell automaton is given by the equation(4.1)Vnt+1-Vnt=max(0,Vn+1t-L)-max(0,Vn-1t+1-L).
This is obtained from the original Lotka-Volterra equation by taking differentiations twice. It is known that this possesses solitons which are induced from the ones of the difference LV solitons.There is a procedure to transform BBS equation to LV cell automaton  and vice versa (see [9, 13, 15]):(4.2)Bnt+1=min{1-Bnt,Σi=-∞n-1(Bit-Bit+1)}⇔Vnt+1-Vnt=max{L,Vn+1t}-max{L,Vn-1t+1},
by changes of variables.Let(4.3)O0=LVcellautomaton→O1→⋯→Ok=BBS
be a procedure of transformations. We say that it is invertible, if the procedure has its inverse Ok→Ok-1→⋯→O0. We say that O0 and Ok can be connected by an invertible procedure.Lemma 4.1.
LV cell automaton and BBS can be connected by an invertible procedure as follows:(4.4)O0={Vnt}→O1={Unt}→O2={Snt}→O3={Bnt}.Proof.
They can be connected by three steps as follows:(4.5)Sn+1t+1-Snt=min{0,1-Sn+1t+Snt+1},Snt=Σi=-∞nBit,Un+1t+1-Unt=max{0,Unt+1-1}-max{0,Un+1t-1},Unt=Sn+1t-Snt+1,Vnt+1-Vnt=max{1,Vn+1t}-max{1,Vn-1t+1},Vt-nn=Unt.
For the first transformation, one has the relationsBnt=Snt-Sn-1t. For the second, notice that Sn-at+a+1=0 for all sufficiently large a. Then, we have the relations
(4.6)Σx=0∞Un-xt+x=Sn+1t-lima→∞Sn-at+a+1=Sn+1t.
This completes the proof.Remark 4.2.
It has been shown in [3] that LV cell automaton is given by a family of PL maps and projections on the interval [0,1]. We have seen that BBS is given by a family of PL maps, projections, and permutations in   Section 2.3.


#### 4.1.1. Deformation by Commutators

Let us consider the second step in the proof of Lemma4.1. We express the linear transformation Unt=Sn+1t-Snt+1 as  (4.7)U=α(S),
where we mean that α(S)nt≡Unt. By this way, let us express others by (4.8)f(S),f(S)nt=Snt-Sn-1t-1,β(S),β(S)nt=Sn+1t-Snt+1,γ(S),γ(S)nt=min{0,1-Sn-1t-1}.Now the second step is expressed as(4.9)U=α(S),*f(U)=β∘f(S),
and the defining equation becomes   **f(S)=γ∘α(S).
Thus combining with (*) and (**), after the transformation, the equation changes as below: ***f(U)=β∘γ(U).Let us consider   deforming the transformations. Leth be a transformation. Then, we say that it commutes with f  if (4.10)f∘h=h∘f
holds.Example 4.3.
LetU={Unt}t,n satisfy limi→∞Un-it-i=0 for each t and n.
Leth be given as
(4.11)h(U)tn=Σi=-∞0Un-it-i,
and let f be f(U)nt=Unt-Un-1t-1 as above. Then, h commutes with f.Let us consider transformations given by (*) and (**) above. Then, a deformation of the transformation by a commutator h is another one given below:(4.12)W=h∘α(S),f(W)=h∘β∘f(S),
which follows from (*). When one considers the equation of the form  (4.13)f(S)=γ∘h∘α(S),
then it is changed to  f(W)=h∘β∘γ(W).We denote all of the set of commutators with respect tof by  (4.14)C(f)={h:[h,f]=0}.


### 4.2. Spaces of Cell Automata

So far, we have considered   certain types of automato in Section2.1,  mainly those  whose defining equations are given by max-plus equations. These are not closed under change of variables, and so here we will generalize the classes of functions we treat.Let us denote the set of integer-valued maps(4.15)PLn={f:Z3n+1→Z,f(x-n,…,x-1,y-n,…,y0,y1,…,yn)∈Z}.
Notice that there are canonical extensions of any f∈PLn to piecewisely linear maps f:R3n+1→R just by connecting images of f piecewisely linearly. Sometimes we will identify both of the maps. Such viewpoints will become important in Section 6.Ageneral automaton is given by an element of the direct limit  (4.16)f∈PL∞=limn→∞PLn,
where the defining equation of the automaton is given by   (4.17)Tkt=f({Tk-nt-1…,Tk-nt,Tk-n+1t,…,Tk-1t},{…,Tk-nt-1,…,Tkt-1,…}).Iff is of the form f(x-N,…,x-1,…,y-n,…,y1,…,yn,…), for some N, then we say that it is of (N,∞) type.Iff is of the form f(…,x-n,…,x-1,y-M,…,y1,…,yn,…), for some M, then we say that it is of (∞,M) type.For simplicity, we will say that they are of finite-∞ or ∞-finite types, respectively. If both cases hold, then we say that it is of (N,M) or of finite-finite type.Notice that the Lotka-Volterra cell automaton is of finite-finite type and the BBS is of infinite-infinite type.Let us denote all of the set of general automata and its subsets consisted by those of*-*′ types by  (4.18)GAut*-*′⊂GAut,
where *,*′= finite or ∞. Notice that  GAut∞-∞=GAut.We will also denote the set of general automata presented by the max-plus equations and its subsets by(4.19)MP*-*′⊂MP.One has the following inclusions:(4.20)BBS∈MP⊂GAut⊃GAutf-f⊃MPf-f∋L-VCA.


### 4.3. Loop Groupoid

Let us choose two general automataO={Snt} and O′={Tnt} in GAut. A transformation from O to O′ is the one given by a change of variables: (4.21)Tkt=F({…,Sk-nt,Sk-n+1t,…,Sk-1t},{…,Sk-nt-1,…,Skt-1,…})
for some linear function F. We denote the transformation by  (4.22)O→O′.
They are mutually invertible  if both O→O′ and O′→O hold.Let us consider two invertible pathsO0=O→O1→⋯→Om=O′  and O0′=O′→O1′→⋯→On′=O in GAut. Then, the composition  (4.23)O=O0→⋯→Om→O1′→O2′⋯→On′=O
gives a loop with the origin O. Clearly two loops with the origin O admit  a natural composition, and by this operation, the set of loops  (4.24)ΩO={O¯≡O=O0→O1⋯→Om=O:invertiblepaths}
admits a group structure.Definition 4.4.
The loop groupoidΩ is given by
(4.25)Ω(O,O′)={O=O0→O1→⋯→On:invertiblepaths}.
Therefore, Ω(O)≡Ω(O,O) is called the loop group.LetO0 be the LV cell automaton, and denote all of the set of the solutions of the equation  (4.26)SLV={{vnt}t,n:solutionsoftheLVcellautomaton}.
Let us take an element O¯∈ΩO0. Then correspondingly, there is a bijective map  between solutions of the equations: (4.27)O¯*:SLV≅SLV.
We call it as an induced map associated with O¯∈ΩO0.In Section6 we construct and study an involution on some classes of GAut by use of tropical geometry and projective duality in affine algebraic varieties.Example 4.5.
Let us use the notations in Section4.1. Let {Bnt} and {Vnt} be the BBS and LV cell automaton, respectively. In  Section 4.1, one has obtained a path O¯={O0={Vnt}→O1={Unt}→O2={Snt}→O3={Bnt}}.
Let us put a general automaton(4.28)Tnt=Bn+1t-Bnt+1.
Then, O1′≡{Tnt}∈GAut is linearly invertible with {Unt} by the relations
(4.29)Unt=Σi=-∞nTit⇔Tnt=Unt-Un-1t.
Thus one has obtained another path O¯′={O0→O1′→O2→O3}.


## 4.1. From BBS to LV

The Lotka-Volterra cell automaton is given by the equation(4.1)Vnt+1-Vnt=max(0,Vn+1t-L)-max(0,Vn-1t+1-L).
This is obtained from the original Lotka-Volterra equation by taking differentiations twice. It is known that this possesses solitons which are induced from the ones of the difference LV solitons.There is a procedure to transform BBS equation to LV cell automaton  and vice versa (see [9, 13, 15]):(4.2)Bnt+1=min{1-Bnt,Σi=-∞n-1(Bit-Bit+1)}⇔Vnt+1-Vnt=max{L,Vn+1t}-max{L,Vn-1t+1},
by changes of variables.Let(4.3)O0=LVcellautomaton→O1→⋯→Ok=BBS
be a procedure of transformations. We say that it is invertible, if the procedure has its inverse Ok→Ok-1→⋯→O0. We say that O0 and Ok can be connected by an invertible procedure.Lemma 4.1.
LV cell automaton and BBS can be connected by an invertible procedure as follows:(4.4)O0={Vnt}→O1={Unt}→O2={Snt}→O3={Bnt}.Proof.
They can be connected by three steps as follows:(4.5)Sn+1t+1-Snt=min{0,1-Sn+1t+Snt+1},Snt=Σi=-∞nBit,Un+1t+1-Unt=max{0,Unt+1-1}-max{0,Un+1t-1},Unt=Sn+1t-Snt+1,Vnt+1-Vnt=max{1,Vn+1t}-max{1,Vn-1t+1},Vt-nn=Unt.
For the first transformation, one has the relationsBnt=Snt-Sn-1t. For the second, notice that Sn-at+a+1=0 for all sufficiently large a. Then, we have the relations
(4.6)Σx=0∞Un-xt+x=Sn+1t-lima→∞Sn-at+a+1=Sn+1t.
This completes the proof.Remark 4.2.
It has been shown in [3] that LV cell automaton is given by a family of PL maps and projections on the interval [0,1]. We have seen that BBS is given by a family of PL maps, projections, and permutations in   Section 2.3.


### 4.1.1. Deformation by Commutators

Let us consider the second step in the proof of Lemma4.1. We express the linear transformation Unt=Sn+1t-Snt+1 as  (4.7)U=α(S),
where we mean that α(S)nt≡Unt. By this way, let us express others by (4.8)f(S),f(S)nt=Snt-Sn-1t-1,β(S),β(S)nt=Sn+1t-Snt+1,γ(S),γ(S)nt=min{0,1-Sn-1t-1}.Now the second step is expressed as(4.9)U=α(S),*f(U)=β∘f(S),
and the defining equation becomes   **f(S)=γ∘α(S).
Thus combining with (*) and (**), after the transformation, the equation changes as below: ***f(U)=β∘γ(U).Let us consider   deforming the transformations. Leth be a transformation. Then, we say that it commutes with f  if (4.10)f∘h=h∘f
holds.Example 4.3.
LetU={Unt}t,n satisfy limi→∞Un-it-i=0 for each t and n.
Leth be given as
(4.11)h(U)tn=Σi=-∞0Un-it-i,
and let f be f(U)nt=Unt-Un-1t-1 as above. Then, h commutes with f.Let us consider transformations given by (*) and (**) above. Then, a deformation of the transformation by a commutator h is another one given below:(4.12)W=h∘α(S),f(W)=h∘β∘f(S),
which follows from (*). When one considers the equation of the form  (4.13)f(S)=γ∘h∘α(S),
then it is changed to  f(W)=h∘β∘γ(W).We denote all of the set of commutators with respect tof by  (4.14)C(f)={h:[h,f]=0}.


## 4.1.1. Deformation by Commutators

Let us consider the second step in the proof of Lemma4.1. We express the linear transformation Unt=Sn+1t-Snt+1 as  (4.7)U=α(S),
where we mean that α(S)nt≡Unt. By this way, let us express others by (4.8)f(S),f(S)nt=Snt-Sn-1t-1,β(S),β(S)nt=Sn+1t-Snt+1,γ(S),γ(S)nt=min{0,1-Sn-1t-1}.Now the second step is expressed as(4.9)U=α(S),*f(U)=β∘f(S),
and the defining equation becomes   **f(S)=γ∘α(S).
Thus combining with (*) and (**), after the transformation, the equation changes as below: ***f(U)=β∘γ(U).Let us consider   deforming the transformations. Leth be a transformation. Then, we say that it commutes with f  if (4.10)f∘h=h∘f
holds.Example 4.3.
LetU={Unt}t,n satisfy limi→∞Un-it-i=0 for each t and n.
Leth be given as
(4.11)h(U)tn=Σi=-∞0Un-it-i,
and let f be f(U)nt=Unt-Un-1t-1 as above. Then, h commutes with f.Let us consider transformations given by (*) and (**) above. Then, a deformation of the transformation by a commutator h is another one given below:(4.12)W=h∘α(S),f(W)=h∘β∘f(S),
which follows from (*). When one considers the equation of the form  (4.13)f(S)=γ∘h∘α(S),
then it is changed to  f(W)=h∘β∘γ(W).We denote all of the set of commutators with respect tof by  (4.14)C(f)={h:[h,f]=0}.


## 4.2. Spaces of Cell Automata

So far, we have considered   certain types of automato in Section2.1,  mainly those  whose defining equations are given by max-plus equations. These are not closed under change of variables, and so here we will generalize the classes of functions we treat.Let us denote the set of integer-valued maps(4.15)PLn={f:Z3n+1→Z,f(x-n,…,x-1,y-n,…,y0,y1,…,yn)∈Z}.
Notice that there are canonical extensions of any f∈PLn to piecewisely linear maps f:R3n+1→R just by connecting images of f piecewisely linearly. Sometimes we will identify both of the maps. Such viewpoints will become important in Section 6.Ageneral automaton is given by an element of the direct limit  (4.16)f∈PL∞=limn→∞PLn,
where the defining equation of the automaton is given by   (4.17)Tkt=f({Tk-nt-1…,Tk-nt,Tk-n+1t,…,Tk-1t},{…,Tk-nt-1,…,Tkt-1,…}).Iff is of the form f(x-N,…,x-1,…,y-n,…,y1,…,yn,…), for some N, then we say that it is of (N,∞) type.Iff is of the form f(…,x-n,…,x-1,y-M,…,y1,…,yn,…), for some M, then we say that it is of (∞,M) type.For simplicity, we will say that they are of finite-∞ or ∞-finite types, respectively. If both cases hold, then we say that it is of (N,M) or of finite-finite type.Notice that the Lotka-Volterra cell automaton is of finite-finite type and the BBS is of infinite-infinite type.Let us denote all of the set of general automata and its subsets consisted by those of*-*′ types by  (4.18)GAut*-*′⊂GAut,
where *,*′= finite or ∞. Notice that  GAut∞-∞=GAut.We will also denote the set of general automata presented by the max-plus equations and its subsets by(4.19)MP*-*′⊂MP.One has the following inclusions:(4.20)BBS∈MP⊂GAut⊃GAutf-f⊃MPf-f∋L-VCA.


## 4.3. Loop Groupoid

Let us choose two general automataO={Snt} and O′={Tnt} in GAut. A transformation from O to O′ is the one given by a change of variables: (4.21)Tkt=F({…,Sk-nt,Sk-n+1t,…,Sk-1t},{…,Sk-nt-1,…,Skt-1,…})
for some linear function F. We denote the transformation by  (4.22)O→O′.
They are mutually invertible  if both O→O′ and O′→O hold.Let us consider two invertible pathsO0=O→O1→⋯→Om=O′  and O0′=O′→O1′→⋯→On′=O in GAut. Then, the composition  (4.23)O=O0→⋯→Om→O1′→O2′⋯→On′=O
gives a loop with the origin O. Clearly two loops with the origin O admit  a natural composition, and by this operation, the set of loops  (4.24)ΩO={O¯≡O=O0→O1⋯→Om=O:invertiblepaths}
admits a group structure.Definition 4.4.
The loop groupoidΩ is given by
(4.25)Ω(O,O′)={O=O0→O1→⋯→On:invertiblepaths}.
Therefore, Ω(O)≡Ω(O,O) is called the loop group.LetO0 be the LV cell automaton, and denote all of the set of the solutions of the equation  (4.26)SLV={{vnt}t,n:solutionsoftheLVcellautomaton}.
Let us take an element O¯∈ΩO0. Then correspondingly, there is a bijective map  between solutions of the equations: (4.27)O¯*:SLV≅SLV.
We call it as an induced map associated with O¯∈ΩO0.In Section6 we construct and study an involution on some classes of GAut by use of tropical geometry and projective duality in affine algebraic varieties.Example 4.5.
Let us use the notations in Section4.1. Let {Bnt} and {Vnt} be the BBS and LV cell automaton, respectively. In  Section 4.1, one has obtained a path O¯={O0={Vnt}→O1={Unt}→O2={Snt}→O3={Bnt}}.
Let us put a general automaton(4.28)Tnt=Bn+1t-Bnt+1.
Then, O1′≡{Tnt}∈GAut is linearly invertible with {Unt} by the relations
(4.29)Unt=Σi=-∞nTit⇔Tnt=Unt-Un-1t.
Thus one has obtained another path O¯′={O0→O1′→O2→O3}.


## 5. Actions on the Boundary of Trees

### 5.1. Actions on the Boundary and Compactification

For any graph with marking on each edge, we denote bym(e)   the marking at the edge e. A tree T is said to be biinfinite if, for any vertex v∈T, it contains a geodesic real line v∈R⊂T.LetT2 be the marked biinfinite binary tree with marking {0,1} so that it contains a base path l0:R→T2 with m(l0(t))=0, t∈Z. Let P={R→T2} be all of the set of geodesics. Then, there is a canonical inclusion  (5.1)P⊂Σ2,
where Σ2 is the set of two-sided sequences with the alphabets {0,1}. Thus Σ2 can be regarded as a compactification of the set of all geodesics in T2.Let us put(5.2)P0={l∈P:m(l(t))=0∀sufficientlylarge|t|≫0}.
Then, we have the following proper inclusions: (5.3)P0⊂P⊂Σ2.
It is easy to see that P0⊂Σ2 is dense. In fact Σ2∖P0 consist of elements l=(…,a-1,a0,a1,…) such that the sets {i:m(ai)=1} are unbounded at least for one direction.Now we have a natural identification (Section2.2)  (5.4)Σ20≅P0⊂Σ2.
Then, the BBS system is described by an isomorphism  (5.5)Φ:P0≅P0.
Notice that the only fixed point is (…,0,0,…).Proposition 5.1.
Φ can be naturally extended to the continuous map
(5.6)Φ:Σ2→Σ2,
where
(5.7)Φ((…,1,1,…))=(…,0,0,…).Thus the extended map is not an isomorphism. More generally one has noninjective points(5.8)Φ((…,0,1,0,…))=(…,0,0,1,…)=Φ((…,0,1,1,0,1,…)).
The extension also has one fixed point (…,0,…).In Section4.1, we have assigned the following isomorphic procedures: (5.9)O0=BBS→O1→O2→O3=LVcellautomaton,
where we denote each step by Fi:Oi→Oi+1, i=0,1,2. Each Oi admits an N action by the flow. By the construction, we have that F0 and F1 both are equivariant with respect to the flow, but F2 is not.Let us putΣ∞0≡⋃m=1∞Σm0, and Σ∞ is defined similarly. Then, by the above procedure F:O0→O3, we have an injection  (5.10)F:P0↪Σ∞0
which assigns the solution of the BBS to the one of LV.Notice thatF extends as F:P→Σ∞ with respect to the compactification of P0 defined above; on the other hand, it cannot be extended as F:Σ2→Σ∞.Lemma 5.2.
F:P→Σ∞ is not a surjection to the set of all solutions of the LV cell automaton.Proof.
Recall that, in the transformations above,F0 and F1:O1→O2 are equivariant, and F2 is just change of indices. Then, the result follows since there are at least two fixed points for O2 as
(5.11){(…,0,0,…),(…,1,1,…)}.Question 1.
Let us choose a largeN≫0. Describe compactification of F(P0)∩ΣN⊂ΣN0.


### 5.2. Embedding of the Lamplighter Group

LetS and A be finite sets. An automata groupG is an infinite group acting on the rooted tree Tm*, m=#A, which is determined by a transition function ϕ:S×A→S and an exit function ψ:S×A→A such that ψ(a)∈Sm is an element of the permutation group for each a∈A.LetT2 be as in  Section 5.1. Recall that the lamplighter group is an automata group which acts on the rooted binary tree T2*, and it has a presentation (see [11])  (5.12)G=〈a,γ:γ2=1,[γai,γaj]=1,i,j∈Z〉.
The action of G preserves each level set of T2*, since it is constructed using an automaton. The automaton is given in Table 2:(5.13)ψ(a)=ϵ,ψ(b)=id,
where ϵ∈S2 is the nontrivial permutation on {0,1}. We call it the lamplighter automaton.Table 2
Values ofϕ.
ab0aa1bbLet us construct another groupG̃ which contains G and acts on T2. Recall that T2 contains a line (…,0,0,…)⊂T2, and choose a base vertex * on the line. By identifying * with the root in T2*, one can embed T2* into T2: (5.14)T2*↪T2.
Now passing through this embedding, one can make G act on T2 by letting the same action as the lamplighter group on T2*↪T2  and by putting the identity on T2∖T2*.Now AutT2⊃G̃⊃G is generated by G and another element τ. Let us describe τ. Notice that each edge of T2 is assigned by one of {0,1}. We say that an automorphism g on T2preserves the marking  if g(e) has the same marking as the one of e in {0,1}. Now τ is an automorphism preserving the marking and uniquely defined by the property that it shifts i-zero in ((…,0,0,…)) to i+1-one. Thus τ preserves the line. Then, G̃ is generated by a, γ, and τ.The action ofG̃ on T̃2 has no fixed point. Moreover it is finitely generated and has quotient isomorphic to Z. Thus the Bass-Serre theory suggests the following.Question 2.
IsG̃ an amalgam? If so, write down explicitly G1,  G2, and A with an isomorphism
(5.15)G̃≅G1*AG2.


### 5.3. Actions on Tree by Cellular Automata

The action of the automata group onT2* is determined by the levelwise way. In fact it is an action on each vertex of T2*. This is not the case for general cellular automata, like LV cell automaton. In fact the action is determined for each path in T2*, rather than points in T2*. More precisely, for many automata including LV case, the image of a vertex v by an element g∈G is determined by a neighbourhood of v.


#### 5.3.1. LV Cell Automaton as a Transition Function

Let us consider a cell automaton(5.16)Φ:N×N2→N,
where each Unt is determined inductively by Unt+1=Φ(Un-1t+1,Unt,Un+1t).We say that{Unt}degenerates with respect to Φ  if there is another function G so that it satisfies the following relation: (5.17)Unt+1=Φ(G(Unt,Un+1t),Unt,Un+1t).Recall that the lamplighter automaton has two states{a,b} and the alphabets {0,1}. In order to compare the LV cell automaton with the transition function of it, we regard the flow {Ut0}t→{Ut1}t as an output of a transition function. By this way let us regard that the initial flow (U00,U10,…), Ui0∈{0,1} is a sequence of the alphabets and (U01,U11,…) is another sequence of the states, where one identifies a and b with 0 and 1, respectively.Lemma 5.3.
Suppose an initial sequence(a0,a1,…) consists of only {0,1} entries.
Then, the degeneration of the LV cell automaton byG(x,y)=x is the same as the transition function ϕ of the lamplighter automaton.When one expresses the flow ofΦ by an automaton, one puts an exit function by: (5.18)ψ(a,i)=0,ψ(b,i)=1,i=0,1.
In particular, the corresponding continuous map on the rooted tree is not an automorphism (it is not one to one).In general flows of the LV cell automaton take  integer elementsUnt∈N. In order to treat these cases, let us put a sequence of states  (5.19)(a0,a1,…),
where a0=a and a1=b. Let S∞ be the group of compactly supported permutation on {0,1,…}. Then, consider an exit function  (5.20)ψ:N→S∞
with ψ(0)=ϵ∈S2⊂S∞ and ψ(1)= id.In general letΦ:N×N2→N be a transition function, and choose an initial sequence (i0,i1,…)⊂N and any U01∈N.Now we define thegeneralized automaton(Φ,ψ) as follows. As an output, we will exit another sequence (i01,i11,…)⊂N as follows.Firstly determine the sequence of the states(U01,U11,…) inductively by Φ: (5.21)Un1=Φ(Un-11,int,in+1t).
Then, inductively we obtain the exits by  (5.22)in1=ψ(Un1)(in0).
By this way one obtains an assignment which is in fact an isomorphism: (5.23)gU01:X∞≅X∞,
where XN are the sets of one-sided sequences with N alphabets and X∞ is their union. The group G(Φ,ψ) generated by gm, m=0,1,…, is also called the generalized automata group given by (Φ,ψ).In the case whenΦ0 is the LV cell automaton, the equation of the transition function becomes   (5.24)Ut+11=int+max(L,in+1t)-max(L,Un-1t+1).Definition 5.4.
The LV cell automata group is a group acting on the boundary∂̃T∞*≡⋃i∂Ti*  of the rooted infinite tree defined by the transition function Φ0 and an exit function ψ as above.A generalized automata group is ofbounded type by N  if it induces an action between XN=∂TN*.


### 5.4. Quasi Actions on Trees

LetG be a group acting on the boundary of the rooted tree T2*.We say that an elementγ∈G is a k0-quasi action on T2*  if there is some k0≥0 such that, if we write γ(a0,a1,…)=(a0′,a1′,…), then aM′ is determined by the data (a0,a1,…,aM+k0) for each M=0,1,…. We denote  (5.25)γ(a0,a1,…)M=(a0′,…,aM′)∈F2,
where F2 is the free group generated by {α,β}. We denote the word length by |g|.Suppose thatγ is a 1-quasi action. Then, we have a map (5.26)Fγ:F2→F2,Fγ(g)=(γ(gα)|g|)-1γ(gβ)|g|∈F2,
which we call the differential of γ. Notice that, when γ is an automorphism on the tree, then F is the identity map.We say that a quasi action byγ is (k0,l0)-semi Markov  if there is some l0≥0 such that aM′ is determined by (aM-l0,…,aM+k0) for each M=0,1,….Letγ has a 1-quasi action on T2*. We say that it is bounded  if there is a bounded function B:F2→F2 so that the differential satisfies the following equality: (5.27)Fγ(g)=B(gα)-1B(gβ).Lemma 5.5.
A bounded quasi actionγ is semi-Markov.Proof.
In fact one has the equality(5.28)γ(gα)|g|B(gα)-1=γ(gβ)|g|B(gβ)-1.
This implies the equality
(5.29)γ(gα)|g|-N=γ(gβ)|g|-N,
where N=sup{|B(g)|:g∈F2}. This completes the proof.


## 5.1. Actions on the Boundary and Compactification

For any graph with marking on each edge, we denote bym(e)   the marking at the edge e. A tree T is said to be biinfinite if, for any vertex v∈T, it contains a geodesic real line v∈R⊂T.LetT2 be the marked biinfinite binary tree with marking {0,1} so that it contains a base path l0:R→T2 with m(l0(t))=0, t∈Z. Let P={R→T2} be all of the set of geodesics. Then, there is a canonical inclusion  (5.1)P⊂Σ2,
where Σ2 is the set of two-sided sequences with the alphabets {0,1}. Thus Σ2 can be regarded as a compactification of the set of all geodesics in T2.Let us put(5.2)P0={l∈P:m(l(t))=0∀sufficientlylarge|t|≫0}.
Then, we have the following proper inclusions: (5.3)P0⊂P⊂Σ2.
It is easy to see that P0⊂Σ2 is dense. In fact Σ2∖P0 consist of elements l=(…,a-1,a0,a1,…) such that the sets {i:m(ai)=1} are unbounded at least for one direction.Now we have a natural identification (Section2.2)  (5.4)Σ20≅P0⊂Σ2.
Then, the BBS system is described by an isomorphism  (5.5)Φ:P0≅P0.
Notice that the only fixed point is (…,0,0,…).Proposition 5.1.
Φ can be naturally extended to the continuous map
(5.6)Φ:Σ2→Σ2,
where
(5.7)Φ((…,1,1,…))=(…,0,0,…).Thus the extended map is not an isomorphism. More generally one has noninjective points(5.8)Φ((…,0,1,0,…))=(…,0,0,1,…)=Φ((…,0,1,1,0,1,…)).
The extension also has one fixed point (…,0,…).In Section4.1, we have assigned the following isomorphic procedures: (5.9)O0=BBS→O1→O2→O3=LVcellautomaton,
where we denote each step by Fi:Oi→Oi+1, i=0,1,2. Each Oi admits an N action by the flow. By the construction, we have that F0 and F1 both are equivariant with respect to the flow, but F2 is not.Let us putΣ∞0≡⋃m=1∞Σm0, and Σ∞ is defined similarly. Then, by the above procedure F:O0→O3, we have an injection  (5.10)F:P0↪Σ∞0
which assigns the solution of the BBS to the one of LV.Notice thatF extends as F:P→Σ∞ with respect to the compactification of P0 defined above; on the other hand, it cannot be extended as F:Σ2→Σ∞.Lemma 5.2.
F:P→Σ∞ is not a surjection to the set of all solutions of the LV cell automaton.Proof.
Recall that, in the transformations above,F0 and F1:O1→O2 are equivariant, and F2 is just change of indices. Then, the result follows since there are at least two fixed points for O2 as
(5.11){(…,0,0,…),(…,1,1,…)}.Question 1.
Let us choose a largeN≫0. Describe compactification of F(P0)∩ΣN⊂ΣN0.


## 5.2. Embedding of the Lamplighter Group

LetS and A be finite sets. An automata groupG is an infinite group acting on the rooted tree Tm*, m=#A, which is determined by a transition function ϕ:S×A→S and an exit function ψ:S×A→A such that ψ(a)∈Sm is an element of the permutation group for each a∈A.LetT2 be as in  Section 5.1. Recall that the lamplighter group is an automata group which acts on the rooted binary tree T2*, and it has a presentation (see [11])  (5.12)G=〈a,γ:γ2=1,[γai,γaj]=1,i,j∈Z〉.
The action of G preserves each level set of T2*, since it is constructed using an automaton. The automaton is given in Table 2:(5.13)ψ(a)=ϵ,ψ(b)=id,
where ϵ∈S2 is the nontrivial permutation on {0,1}. We call it the lamplighter automaton.Table 2
Values ofϕ.
ab0aa1bbLet us construct another groupG̃ which contains G and acts on T2. Recall that T2 contains a line (…,0,0,…)⊂T2, and choose a base vertex * on the line. By identifying * with the root in T2*, one can embed T2* into T2: (5.14)T2*↪T2.
Now passing through this embedding, one can make G act on T2 by letting the same action as the lamplighter group on T2*↪T2  and by putting the identity on T2∖T2*.Now AutT2⊃G̃⊃G is generated by G and another element τ. Let us describe τ. Notice that each edge of T2 is assigned by one of {0,1}. We say that an automorphism g on T2preserves the marking  if g(e) has the same marking as the one of e in {0,1}. Now τ is an automorphism preserving the marking and uniquely defined by the property that it shifts i-zero in ((…,0,0,…)) to i+1-one. Thus τ preserves the line. Then, G̃ is generated by a, γ, and τ.The action ofG̃ on T̃2 has no fixed point. Moreover it is finitely generated and has quotient isomorphic to Z. Thus the Bass-Serre theory suggests the following.Question 2.
IsG̃ an amalgam? If so, write down explicitly G1,  G2, and A with an isomorphism
(5.15)G̃≅G1*AG2.


## 5.3. Actions on Tree by Cellular Automata

The action of the automata group onT2* is determined by the levelwise way. In fact it is an action on each vertex of T2*. This is not the case for general cellular automata, like LV cell automaton. In fact the action is determined for each path in T2*, rather than points in T2*. More precisely, for many automata including LV case, the image of a vertex v by an element g∈G is determined by a neighbourhood of v.


### 5.3.1. LV Cell Automaton as a Transition Function

Let us consider a cell automaton(5.16)Φ:N×N2→N,
where each Unt is determined inductively by Unt+1=Φ(Un-1t+1,Unt,Un+1t).We say that{Unt}degenerates with respect to Φ  if there is another function G so that it satisfies the following relation: (5.17)Unt+1=Φ(G(Unt,Un+1t),Unt,Un+1t).Recall that the lamplighter automaton has two states{a,b} and the alphabets {0,1}. In order to compare the LV cell automaton with the transition function of it, we regard the flow {Ut0}t→{Ut1}t as an output of a transition function. By this way let us regard that the initial flow (U00,U10,…), Ui0∈{0,1} is a sequence of the alphabets and (U01,U11,…) is another sequence of the states, where one identifies a and b with 0 and 1, respectively.Lemma 5.3.
Suppose an initial sequence(a0,a1,…) consists of only {0,1} entries.
Then, the degeneration of the LV cell automaton byG(x,y)=x is the same as the transition function ϕ of the lamplighter automaton.When one expresses the flow ofΦ by an automaton, one puts an exit function by: (5.18)ψ(a,i)=0,ψ(b,i)=1,i=0,1.
In particular, the corresponding continuous map on the rooted tree is not an automorphism (it is not one to one).In general flows of the LV cell automaton take  integer elementsUnt∈N. In order to treat these cases, let us put a sequence of states  (5.19)(a0,a1,…),
where a0=a and a1=b. Let S∞ be the group of compactly supported permutation on {0,1,…}. Then, consider an exit function  (5.20)ψ:N→S∞
with ψ(0)=ϵ∈S2⊂S∞ and ψ(1)= id.In general letΦ:N×N2→N be a transition function, and choose an initial sequence (i0,i1,…)⊂N and any U01∈N.Now we define thegeneralized automaton(Φ,ψ) as follows. As an output, we will exit another sequence (i01,i11,…)⊂N as follows.Firstly determine the sequence of the states(U01,U11,…) inductively by Φ: (5.21)Un1=Φ(Un-11,int,in+1t).
Then, inductively we obtain the exits by  (5.22)in1=ψ(Un1)(in0).
By this way one obtains an assignment which is in fact an isomorphism: (5.23)gU01:X∞≅X∞,
where XN are the sets of one-sided sequences with N alphabets and X∞ is their union. The group G(Φ,ψ) generated by gm, m=0,1,…, is also called the generalized automata group given by (Φ,ψ).In the case whenΦ0 is the LV cell automaton, the equation of the transition function becomes   (5.24)Ut+11=int+max(L,in+1t)-max(L,Un-1t+1).Definition 5.4.
The LV cell automata group is a group acting on the boundary∂̃T∞*≡⋃i∂Ti*  of the rooted infinite tree defined by the transition function Φ0 and an exit function ψ as above.A generalized automata group is ofbounded type by N  if it induces an action between XN=∂TN*.


## 5.3.1. LV Cell Automaton as a Transition Function

Let us consider a cell automaton(5.16)Φ:N×N2→N,
where each Unt is determined inductively by Unt+1=Φ(Un-1t+1,Unt,Un+1t).We say that{Unt}degenerates with respect to Φ  if there is another function G so that it satisfies the following relation: (5.17)Unt+1=Φ(G(Unt,Un+1t),Unt,Un+1t).Recall that the lamplighter automaton has two states{a,b} and the alphabets {0,1}. In order to compare the LV cell automaton with the transition function of it, we regard the flow {Ut0}t→{Ut1}t as an output of a transition function. By this way let us regard that the initial flow (U00,U10,…), Ui0∈{0,1} is a sequence of the alphabets and (U01,U11,…) is another sequence of the states, where one identifies a and b with 0 and 1, respectively.Lemma 5.3.
Suppose an initial sequence(a0,a1,…) consists of only {0,1} entries.
Then, the degeneration of the LV cell automaton byG(x,y)=x is the same as the transition function ϕ of the lamplighter automaton.When one expresses the flow ofΦ by an automaton, one puts an exit function by: (5.18)ψ(a,i)=0,ψ(b,i)=1,i=0,1.
In particular, the corresponding continuous map on the rooted tree is not an automorphism (it is not one to one).In general flows of the LV cell automaton take  integer elementsUnt∈N. In order to treat these cases, let us put a sequence of states  (5.19)(a0,a1,…),
where a0=a and a1=b. Let S∞ be the group of compactly supported permutation on {0,1,…}. Then, consider an exit function  (5.20)ψ:N→S∞
with ψ(0)=ϵ∈S2⊂S∞ and ψ(1)= id.In general letΦ:N×N2→N be a transition function, and choose an initial sequence (i0,i1,…)⊂N and any U01∈N.Now we define thegeneralized automaton(Φ,ψ) as follows. As an output, we will exit another sequence (i01,i11,…)⊂N as follows.Firstly determine the sequence of the states(U01,U11,…) inductively by Φ: (5.21)Un1=Φ(Un-11,int,in+1t).
Then, inductively we obtain the exits by  (5.22)in1=ψ(Un1)(in0).
By this way one obtains an assignment which is in fact an isomorphism: (5.23)gU01:X∞≅X∞,
where XN are the sets of one-sided sequences with N alphabets and X∞ is their union. The group G(Φ,ψ) generated by gm, m=0,1,…, is also called the generalized automata group given by (Φ,ψ).In the case whenΦ0 is the LV cell automaton, the equation of the transition function becomes   (5.24)Ut+11=int+max(L,in+1t)-max(L,Un-1t+1).Definition 5.4.
The LV cell automata group is a group acting on the boundary∂̃T∞*≡⋃i∂Ti*  of the rooted infinite tree defined by the transition function Φ0 and an exit function ψ as above.A generalized automata group is ofbounded type by N  if it induces an action between XN=∂TN*.


## 5.4. Quasi Actions on Trees

LetG be a group acting on the boundary of the rooted tree T2*.We say that an elementγ∈G is a k0-quasi action on T2*  if there is some k0≥0 such that, if we write γ(a0,a1,…)=(a0′,a1′,…), then aM′ is determined by the data (a0,a1,…,aM+k0) for each M=0,1,…. We denote  (5.25)γ(a0,a1,…)M=(a0′,…,aM′)∈F2,
where F2 is the free group generated by {α,β}. We denote the word length by |g|.Suppose thatγ is a 1-quasi action. Then, we have a map (5.26)Fγ:F2→F2,Fγ(g)=(γ(gα)|g|)-1γ(gβ)|g|∈F2,
which we call the differential of γ. Notice that, when γ is an automorphism on the tree, then F is the identity map.We say that a quasi action byγ is (k0,l0)-semi Markov  if there is some l0≥0 such that aM′ is determined by (aM-l0,…,aM+k0) for each M=0,1,….Letγ has a 1-quasi action on T2*. We say that it is bounded  if there is a bounded function B:F2→F2 so that the differential satisfies the following equality: (5.27)Fγ(g)=B(gα)-1B(gβ).Lemma 5.5.
A bounded quasi actionγ is semi-Markov.Proof.
In fact one has the equality(5.28)γ(gα)|g|B(gα)-1=γ(gβ)|g|B(gβ)-1.
This implies the equality
(5.29)γ(gα)|g|-N=γ(gβ)|g|-N,
where N=sup{|B(g)|:g∈F2}. This completes the proof.


## 6. Associated Algebraic Varieties

### 6.1. Tropical Algebra

Maslov introduced a kind of scale transform called thedequantization of the real line R. It is given by deformations of the arithmetics over the real number R, which are parameterized by a family of semirings Rt for t>1.The multiplications and the additions are, respectively, given by(6.1)x⨁ty=logt(tx+ty),x⨂ty=x+y.
Notice the following particular property: (6.2)x⨁∞y≡limt→∞x⨁ty=max{x,y}.
This is called the tropical semiring.Corresponding to polynomials over the usual real numbers, one obtainsRt-polynomials as (6.3)φt(x)=(α1+j1x)⨁t⋯⨁t(αk+jkx)(x∈Rn,jl∈Zn)
whose limit t→∞ satisfies the following max-plus equation: (6.4)φ∞(x)=max(α1+j1x,…,αk+jkx).LetLogt:(C*)n→Rn be defined as  (6.5)Logt(z1,…,zn)≡(log|z1|,…,log|zn|).The following can be checked easily by direct calculations, but the conclusions are highly nontrivial and interesting.Proposition 6.1 (see [4, 12]).
ft≡(logt)-1∘φt∘Logt:R+n→R+ is in fact a polynomial map ft(z)=Σjtαjzj.ThusRt-polynomials are conjugate to the standard real polynomials by logt.Conversely letφ:R+n→R+ be a piecewisely linear map equipped with the presentation by a max-plus equation. Then, one can associate a parameterized Rt and R polynomials, respectively, since their presentations are determined by the coefficients α1,…,αk,j1,…,jk. Later on, we will denote them, respectively, by φt and ft  and call the associatedRtandRpolynomials with respect to φ.


### 6.2. Tropical Maps in LV Cell Automaton

It is immediate to generalize Section6.1  to the relative case  [16].LetFt:CN→C be a family of rational functions given by  (6.6)F(z1,…,zN)=ΣltalzjlΣmtbmzjm,
where j=(j1,…,jN)∈ZN and z=(z1,…,zN)∈CN. Then, we define the corresponding tropical polynomialf=ftr as a piecewise linear map on RN by  (6.7)ftr(x1,…,xN)=maxl{al+jlx}-maxm{bm+jmx}.
where x=(x1,…,xN)∈RN. Such functions are called the relative(max,+)functions.Let us recall the Lotka-Volterra cell automaton in Section4. We describe it as flows of the generalized interactions in Section 2.2.Proposition 6.2 (see [3]).
There is a family of smooth maps{fi,j}i,j=0,…,L so that the corresponding flow Φ(x)t, t=0,1,…, determined by {fi,j}i,j gives the solutions of the Lotka-Volterra cell automaton.Proof.
Let us construct the map(6.8)Φ̃:{0,…,L}×{0,…,L}2→{0,…,L},Φ̃(kn-1t,knt-1,kn+1t-1)=knt∈{0,,…,L}.
Let us put a piecewise linear mapfLV by
(6.9)fLV(x1,x2,x3)=x1+max{L0,x2}-max{L0,x3}=x1+max{0,x2-L0}-max{0,x3-L0}.
Then, we renormalize them and putfi,j:[0,1]→[0,1] by
(6.10)fi,j(x)=1LfLV(i,j,Lx)∈[0,1].
Let us divide the interval [0,1] into L+1 intervals, and denote them as I0<I1<⋯<IL. Then, fi,j(Il)⊂IΦ̃(l,i,j) are satisfied for all i,j,l∈{0,1,…,L}. This is the desired family of maps.
This completes the proof.


### 6.3. Associated Hypersurfaces

In order to avoid minus sign in the defining equations, one can transpose some terms there. Then, the equation can be expressible by max-plus equations in both sides. So when a bounded automaton is determined by a relative(max,+) function φ, then it associates the pair of (max,+) functions (φ1,φ2).For example, the LV-CA can be immediately rewritten as(6.11)Vn+1t+1+max{L,Vnt+1}=Vn+1t+max{L,Vn+2t}.Let us consider a bounded automaton defined by a relative(max,+) function: (6.12)Vn+1t+1=φ(Vn-kt-l,…,Vnt+1).
Let φ1 and φ2 be two max-plus equations with respect to φ. Then, the above equation can be rewritten as  (6.13)φ1(Vn-kt-l,…,Vn+1t+1)=φ2(Vn-kt-l,…,Vnt+1),n=0,1,…,
for some k and l. Notice that φ1 can be rewritten as  (6.14)φ1(Vn-kt-l,…,Vn+1t+1)=Vn+1t+1+φ̃1(Vn-kt-l,…,Vnt+1)
for another some (max,+) function φ̃1, and they satisfy the relation  (6.15)φ(Vn-kt-l,…,Vnt+1)=φ2(Vn-kt-l,…,Vnt+1)-φ̃1(Vn-kt-l,…,Vnt+1)=φ2(Vn-kt-l,…,Vnt+1)-φ1(Vn-kt-l,…,Vn+1t+1)+Vn+1t+1.
One may assume that both φ̃1 and φ2 have the same N variables.Letft1 and ft2 be the associated R polynomials and assign the complex variables z=(z1,z2,…,zN+1) with respect to (Vn-kt-l,…,Vn+1t+1).Definition 6.3.
The associated affine hypersurfaces are a parameterized family of hypersurfaces given by the following equations:(6.16)V(A)t={z∈CN+1:ft1(z)=ft2(z)}.Example 6.4.
Let us consider the LV cell automaton. Let us put a parameterized polynomial  of degree2 by ft(z,w)=tLz+zw. Then, the corresponding equation becomes   ft(z4,z3)=ft(z1,z2), where each zi corresponds to z1↔Vn+1t, z2↔Vn+2t, z3↔Vnt+1, and z4↔Vn+1t+1. Thus the associated hypersurfaces V(LV)t⊂C4 are a family defined by
(6.17)V(LV)t={(z1,z2,z3,z4)∈C4:ft(z4,z3)=ft(z1,z2)}.


#### 6.3.1. The Associated Complex Dynamics

Let us consider a bounded automatonA given by a relative (max,+) function φ. As above, it is given by a pair of (max,+) functions (φ1,φ2). Let ft and (ft1,ft2) be the associated rational and the pair of polynomial functions with respect to φ and (φ1,φ2) mutually. Notice that they are related in the following way: (6.18)ft(z1,z2,…,zN)=zN+1ft2(z1,z2,…,zN)ft1(z1,z2,…,zN,zN+1).For the LV cell automaton,ft above is given by  (6.19)ft(z1,z2,z3)=(tL+z3)-1(tLz1+z1z2).Now fort=0,1,…, let us consider a flow given by infinite sequences of complex numbers (z1t,z2t,z3t,…)∈C∞ which obey the equation  (6.20)zn+1t+1=ft(zn-kt-l,…,znt+1).
Notice that, if (zn-kt-l,…,znt+1)∈R>0N, then zn+1t+1∈(0,∞).Since it also satisfies the equation(6.21)ft1(zn-kt-l,…,zn+1t+1)=ft2(zn-kt-l,…,znt+1),
each building block znt=(zn-kt-l,…,znt+1) lies on V(A)t for all n≥k and t≥l. We say that the sequences  (6.22){znt}n≥k,t≥l⊂V(A)t
are the induced dynamics on V(A)t.


#### 6.3.2. Stability

So far, we have discussed by fixing the parametert. Here we consider the asymptotics of flows as t→∞.Let(φ1,φ2) be a bounded automaton given by two max-plus functions with the N+1 variables (Vn-kt-l,…,Vn+1t+1) as above. Let us denote the associated polynomials φti and fti, i=1,2.Lemma 6.5.
Letzt∈R>0N+1 be a family of points. Suppose that the convergent condition
(6.23)x≡limt→∞Logt(zt)
is satisfied. Then, x∈RN+1 satisfies the following equation:
(6.24)φ1(x)=φ2(x).Proof.
We recall the equalityft=logt-1∘φt∘Logt on the positive real numbers. Thus they satisfy the following equation:
(6.25)φt1∘Logt(zt)=φt2∘Logt(zt).
Then the conclusion holds, since φti converge to the original max-plus functions φi. This completes the proof.Let[v]∈Z be the integer part of v∈R. For a sequence v=(v1,v2,…), we denote by [v]≡([v1],[v2],…).Definition 6.6.
LetA be a bounded automaton, and choose   parameterized families of sequences {znt}n≥k,t≥l⊂CN+1.
We say that they are stable, if there ist0 so that, for all t≥t0,
(6.26){[Logt(znt)]}n≥k,t≥l⊂ZN+1
gives a flow of the solutions of the original automaton A.LetA be the LV cell automaton. Then, as in Section 6.2, there is a family of interval maps {fi,j}i,j so that the flow of the solutions of LV-CA can be represented by interactions of maps between {fi,j}. Thus existence of stable families above will be heavily influenced by stability of dynamical properties of the family {fi,j} under continuous deformations of these maps.


### 6.4. Cell Automatic Varieties

LetA1 and A2 be two cell automata, and consider an integer-valued flow  (6.27){Vt=(V1t,V2t,…)}t≥0⊂Z∞.
If it satisfies both equations for A1 and A2, then we say that {Vt}t is a flow for A1 and A2.Let us denote the set of such flows by(6.28)F(A1,A2)={{Vt}t=0,1,2,…⊂Z∞:flowsforbothA1,A2}.
We say that  F(A1,A2) is a cell automatic variety for A1 and A2.LetA1,…,Am be a family of cell automata. By considering flows for them, one also obtains the cell automatic variety  F(A1,…,Am).


#### 6.4.1. Compatible Automata

LetA1 and A2 be two cell automata given by φ and φ', respectively: (6.29)Vn+1t+1=φ(′)({Vn-kt,…,Vn+lt},{Vn-k′t+1,…,Vnt+1})[*](′).
Let us denote the following sets: (6.30)Vnt≡(Vn-kt,…,Vn+lt,Vn-k't+1,…,Vnt+1)∈ZN.We say thatA2 is compatible with A1  if the following holds; suppose that  Vnt satisfies both [*] and [*]′. Let Vn+1t be determined by [*]′. Then, it also satisfies [*].In the case of compatible automata(A1,A2), the cell automatic variety  F(A1,A2) will be nonempty, which does not hold in general.Example 6.7.
LetA1 and A2 be both automata given by linear maps as follows:
(6.31)un+1=αun+βun-1+γ,(A1),un-1=aun+b,(A2).
If these coefficients satisfy the following relations:
(6.32)(1-β)a=α,(1-β)b=γ,
then A2 is compatible with A1.


#### 6.4.2. Associated Varieties

LetA1 and A2 be two CA. Let us denote the associated R-polynomials by fti and gti for i=1,2, respectively. Then, one obtains the parameterized affine algebraic varieties given by the following equations: (6.33)V(A1,A2)t={z∈CN:ft1(z)=ft2(z),gt1(z)=gt2(z)}.Let us consider the associated systems of complex dynamics. Let(z1t,z2t,z3t,…)∈C∞ which obey the following system of the equations: (6.34)ft1(zn-kt-l,…,zn+1t+1)=ft2(zn-kt-l,…,znt+1),gt1(zn-kt-l,…,zn+1t+1)=gt2(zn-kt-l,…,znt+1).
Again each building block znt=(zn-kt-l,…,znt+1) lies on V(A1,A2)t, and we say that {znt}n,t is the induced dynamics on V(A1,A2)t.LetA1,…,Am be a family of CA. Then, by the same way as above, one obtains the following  parameterized associated affine algebraic variety: (6.35)V(A1,…,Am)t={z∈CN:(ftk)1(z)=(ftk)2(z),k=1,…,m},
where (ftk)i, i=1,2, are the associated R-polynomials with respect to Ak.


### 6.5. Duality

Here we introduce a new duality on the set of automata. It passes through theprojective duality between algebraic varieties [17].LetV be a complex n-dimensional vector space and let  P(V) be its projective space. There is a natural isomorphism P(V)≅P*(V*), where P*(W) is the set of all hyperplanes in W  and V* is the dual space to V.Projective duality generalizes this operation to varieties. Let us quickly describe its construction. LetX⊂P(V) be an algebraic variety. Then, one can associate another variety X∨⊂P(V*) as follows. A hyperplane H⊂P(V) is said to be tangent to X  if there exists a smooth point x∈H∩X and the tangent space of X at x is contained in H. Let X*⊂P*(V) be all of the set of tangent hyperplanes, and passing through the above isomorphism, one obtains a set X∨⊂P(V*) which is the desired one. It is called the projective dual variety. In the case when X∨⊂P(V*) is a hypersurface, then its defining polynomial ΔX is called the X-discriminant.Let{A1,…,Am} be a family of automata. Thus one obtains a parameterized family of projective varieties V({Ai})t⊂CPN by taking closure of the associated affine varieties.LetṼ({Ai})t∨⊂CPN be the corresponding parameterized projective dual varieties.Suppose that  these are hypersurfaces, and denote the defining functions byΣjtαjajzj. When one can modify the polynomial as Σjtαjwj by change of variables alzl=wl, then we call Σjtαjwj  the {Ai}-discriminant  and denote it by  (6.36)Δ({Ai})t.
We will denote the corresponding modified varieties by  (6.37)V({Ai})t∨
and call them as the associated dual varieties with respect to {Ai}i. They are isomorphic with Ṽ({Ai})t∨.Definition 6.8.
Letφt be the associated Rt-polynomials to Δ({Ai})t). The automaton defined by φ∞=limt→∞φt is called the projectively dual automaton.We denote the projectively dual automaton by(6.38){Ai}∨.


#### 6.5.1. Curves inCP2

In general it is not easy to calculate the defining equations of the projective varieties. However as far as the simplest case is that  of the curves inCP2, one can write down them explicitly. Using this fact, we verify the following.Proposition 6.9.
Consider(6.39)[max{aun,α+aun+1}=c]∨=max{aa-1(c-αa)+aa-1un+1,aca-1+aa-1un}=c.Proof.
LetX⊂CP2 be an irreducible curve. Then, it is known that X∨⊂CP2 is also another irreducible one. In the affine coordinate, if X has a parameterization x=x(s) and y=y(s), s∈C, then X∨ has a parameterization given by the following (see [17]):
(6.40)p(s)=-y'(s)x'(s)y(s)-x(s)y'(s),q(s)=x'(s)x'(s)y(s)-x(s)y'(s).
Using this, let us consider the very simple case above. Leta≥2, let α and c be integers, and consider an automaton A given by
(6.41)max{aun,α+aun+1}=c.
The associated polynomial and the associated varieties are given by
(6.42)X={(x,y)∈C2⊂CP2:xa+tαya=tc}.
Choosing a parameterization as
(6.43)x=s,y=t-α/a(tc-sa)1/a,
one can immediately obtain the parameterization of X∨ as
(6.44)t(a/(a-1))(c-α/a)qa/(a-1)+tac/(a-1)pa/(a-1)=tc(*)
which gives the dual varieties
(6.45)V(A)t∨={(p,q)∈C2⊂CP2:(*)}.
Thus the projectively dual automaton admits the desired presentation. This completes the proof.


### 6.6. Transformations

Let us take two automataO and O′,  and let  O¯={O=O0→O1→⋯Om=O′}∈Ω(O,O′) be an invertible path, as in Section 4.3, whose associated R-polynomials are given as the pairs (ft1,ft2)i, i=0,…,m. Then, correspondingly the associated hypersurfaces {V(Oi)}i=0,…,m⊂CN are obtained. We call this a lifting of O¯∈ΩO.Question 3.
What are geometric structure of such liftings?Recall that we have obtained  other cell automataO1 and O2 during the process of transforming from BBS to LV; see  Section 4.1. Similarly, as above we rewrite these as (6.46)Un+1t+1+max{1,Un+1t}=Unt+max{1,Unt+1},Sn+1t+1+max{Snt+1+1,Sn+1t}=Snt+Snt+1+1.
Let us assign the variables as  (6.47)z1⟷Xnt,z2⟷Xn+1t,z3⟷Xnt+1,z4⟷Xn+1t+1
for both X=S and X=U. Then, we have the corresponding polynomial pairs as  (6.48)ft1(z2,z4)=z4(t+z2),ft2(z1,z3)=z1(t+z3),forU,ft1(z2,z3,z4)=z4(tz3+z2),ft2(z1,z3)=tz3z1,forS.
Thus one has obtained three associated hypersurfaces as follows: (6.49)V(LV),V(U),V(S)⊂C4.
Below we study one aspect of Question 3 for this case.


#### 6.6.1. Representatives by Homogeneous Maps

Let us consider a bounded automatonA given by a relative (max,+) function φ. As in Section 6.3.1, it is given by a pair of (max,+) functions (φ1,φ2). Let (ft1,ft2) be the associated polynomials with respect to (φ1,φ2).If bothft1 and ft2 are homogeneous polynomials of the same degree, then we say that A is a homogeneous cell automaton.The LV-CA is not homogeneous; see Section6.3. However one can deform it so that the result becomes homogeneous as below.LetO be a cell automaton. We say that  O admits a homogeneous representative  if there is an invertible transformation  O=O0→O1→⋯→Ok so that Ok is homogeneous.Lemma 6.10.
LV cell automaton admits a homogeneous representative.Proof.
LetO0=LV→O1→O2→O3=BBS be the invertible path in Lemma 4.1. Then, certainly O2 is homogeneous as above.
This completes the proof.LetO be a homogeneous cell automaton. Then, one obtains theassociated projective hypersurface(6.50)V(O)⊂CPN-1.
We say that V(O) is the associated projective hypersurface.


## 6.1. Tropical Algebra

Maslov introduced a kind of scale transform called thedequantization of the real line R. It is given by deformations of the arithmetics over the real number R, which are parameterized by a family of semirings Rt for t>1.The multiplications and the additions are, respectively, given by(6.1)x⨁ty=logt(tx+ty),x⨂ty=x+y.
Notice the following particular property: (6.2)x⨁∞y≡limt→∞x⨁ty=max{x,y}.
This is called the tropical semiring.Corresponding to polynomials over the usual real numbers, one obtainsRt-polynomials as (6.3)φt(x)=(α1+j1x)⨁t⋯⨁t(αk+jkx)(x∈Rn,jl∈Zn)
whose limit t→∞ satisfies the following max-plus equation: (6.4)φ∞(x)=max(α1+j1x,…,αk+jkx).LetLogt:(C*)n→Rn be defined as  (6.5)Logt(z1,…,zn)≡(log|z1|,…,log|zn|).The following can be checked easily by direct calculations, but the conclusions are highly nontrivial and interesting.Proposition 6.1 (see [4, 12]).
ft≡(logt)-1∘φt∘Logt:R+n→R+ is in fact a polynomial map ft(z)=Σjtαjzj.ThusRt-polynomials are conjugate to the standard real polynomials by logt.Conversely letφ:R+n→R+ be a piecewisely linear map equipped with the presentation by a max-plus equation. Then, one can associate a parameterized Rt and R polynomials, respectively, since their presentations are determined by the coefficients α1,…,αk,j1,…,jk. Later on, we will denote them, respectively, by φt and ft  and call the associatedRtandRpolynomials with respect to φ.


## 6.2. Tropical Maps in LV Cell Automaton

It is immediate to generalize Section6.1  to the relative case  [16].LetFt:CN→C be a family of rational functions given by  (6.6)F(z1,…,zN)=ΣltalzjlΣmtbmzjm,
where j=(j1,…,jN)∈ZN and z=(z1,…,zN)∈CN. Then, we define the corresponding tropical polynomialf=ftr as a piecewise linear map on RN by  (6.7)ftr(x1,…,xN)=maxl{al+jlx}-maxm{bm+jmx}.
where x=(x1,…,xN)∈RN. Such functions are called the relative(max,+)functions.Let us recall the Lotka-Volterra cell automaton in Section4. We describe it as flows of the generalized interactions in Section 2.2.Proposition 6.2 (see [3]).
There is a family of smooth maps{fi,j}i,j=0,…,L so that the corresponding flow Φ(x)t, t=0,1,…, determined by {fi,j}i,j gives the solutions of the Lotka-Volterra cell automaton.Proof.
Let us construct the map(6.8)Φ̃:{0,…,L}×{0,…,L}2→{0,…,L},Φ̃(kn-1t,knt-1,kn+1t-1)=knt∈{0,,…,L}.
Let us put a piecewise linear mapfLV by
(6.9)fLV(x1,x2,x3)=x1+max{L0,x2}-max{L0,x3}=x1+max{0,x2-L0}-max{0,x3-L0}.
Then, we renormalize them and putfi,j:[0,1]→[0,1] by
(6.10)fi,j(x)=1LfLV(i,j,Lx)∈[0,1].
Let us divide the interval [0,1] into L+1 intervals, and denote them as I0<I1<⋯<IL. Then, fi,j(Il)⊂IΦ̃(l,i,j) are satisfied for all i,j,l∈{0,1,…,L}. This is the desired family of maps.
This completes the proof.


## 6.3. Associated Hypersurfaces

In order to avoid minus sign in the defining equations, one can transpose some terms there. Then, the equation can be expressible by max-plus equations in both sides. So when a bounded automaton is determined by a relative(max,+) function φ, then it associates the pair of (max,+) functions (φ1,φ2).For example, the LV-CA can be immediately rewritten as(6.11)Vn+1t+1+max{L,Vnt+1}=Vn+1t+max{L,Vn+2t}.Let us consider a bounded automaton defined by a relative(max,+) function: (6.12)Vn+1t+1=φ(Vn-kt-l,…,Vnt+1).
Let φ1 and φ2 be two max-plus equations with respect to φ. Then, the above equation can be rewritten as  (6.13)φ1(Vn-kt-l,…,Vn+1t+1)=φ2(Vn-kt-l,…,Vnt+1),n=0,1,…,
for some k and l. Notice that φ1 can be rewritten as  (6.14)φ1(Vn-kt-l,…,Vn+1t+1)=Vn+1t+1+φ̃1(Vn-kt-l,…,Vnt+1)
for another some (max,+) function φ̃1, and they satisfy the relation  (6.15)φ(Vn-kt-l,…,Vnt+1)=φ2(Vn-kt-l,…,Vnt+1)-φ̃1(Vn-kt-l,…,Vnt+1)=φ2(Vn-kt-l,…,Vnt+1)-φ1(Vn-kt-l,…,Vn+1t+1)+Vn+1t+1.
One may assume that both φ̃1 and φ2 have the same N variables.Letft1 and ft2 be the associated R polynomials and assign the complex variables z=(z1,z2,…,zN+1) with respect to (Vn-kt-l,…,Vn+1t+1).Definition 6.3.
The associated affine hypersurfaces are a parameterized family of hypersurfaces given by the following equations:(6.16)V(A)t={z∈CN+1:ft1(z)=ft2(z)}.Example 6.4.
Let us consider the LV cell automaton. Let us put a parameterized polynomial  of degree2 by ft(z,w)=tLz+zw. Then, the corresponding equation becomes   ft(z4,z3)=ft(z1,z2), where each zi corresponds to z1↔Vn+1t, z2↔Vn+2t, z3↔Vnt+1, and z4↔Vn+1t+1. Thus the associated hypersurfaces V(LV)t⊂C4 are a family defined by
(6.17)V(LV)t={(z1,z2,z3,z4)∈C4:ft(z4,z3)=ft(z1,z2)}.


### 6.3.1. The Associated Complex Dynamics

Let us consider a bounded automatonA given by a relative (max,+) function φ. As above, it is given by a pair of (max,+) functions (φ1,φ2). Let ft and (ft1,ft2) be the associated rational and the pair of polynomial functions with respect to φ and (φ1,φ2) mutually. Notice that they are related in the following way: (6.18)ft(z1,z2,…,zN)=zN+1ft2(z1,z2,…,zN)ft1(z1,z2,…,zN,zN+1).For the LV cell automaton,ft above is given by  (6.19)ft(z1,z2,z3)=(tL+z3)-1(tLz1+z1z2).Now fort=0,1,…, let us consider a flow given by infinite sequences of complex numbers (z1t,z2t,z3t,…)∈C∞ which obey the equation  (6.20)zn+1t+1=ft(zn-kt-l,…,znt+1).
Notice that, if (zn-kt-l,…,znt+1)∈R>0N, then zn+1t+1∈(0,∞).Since it also satisfies the equation(6.21)ft1(zn-kt-l,…,zn+1t+1)=ft2(zn-kt-l,…,znt+1),
each building block znt=(zn-kt-l,…,znt+1) lies on V(A)t for all n≥k and t≥l. We say that the sequences  (6.22){znt}n≥k,t≥l⊂V(A)t
are the induced dynamics on V(A)t.


### 6.3.2. Stability

So far, we have discussed by fixing the parametert. Here we consider the asymptotics of flows as t→∞.Let(φ1,φ2) be a bounded automaton given by two max-plus functions with the N+1 variables (Vn-kt-l,…,Vn+1t+1) as above. Let us denote the associated polynomials φti and fti, i=1,2.Lemma 6.5.
Letzt∈R>0N+1 be a family of points. Suppose that the convergent condition
(6.23)x≡limt→∞Logt(zt)
is satisfied. Then, x∈RN+1 satisfies the following equation:
(6.24)φ1(x)=φ2(x).Proof.
We recall the equalityft=logt-1∘φt∘Logt on the positive real numbers. Thus they satisfy the following equation:
(6.25)φt1∘Logt(zt)=φt2∘Logt(zt).
Then the conclusion holds, since φti converge to the original max-plus functions φi. This completes the proof.Let[v]∈Z be the integer part of v∈R. For a sequence v=(v1,v2,…), we denote by [v]≡([v1],[v2],…).Definition 6.6.
LetA be a bounded automaton, and choose   parameterized families of sequences {znt}n≥k,t≥l⊂CN+1.
We say that they are stable, if there ist0 so that, for all t≥t0,
(6.26){[Logt(znt)]}n≥k,t≥l⊂ZN+1
gives a flow of the solutions of the original automaton A.LetA be the LV cell automaton. Then, as in Section 6.2, there is a family of interval maps {fi,j}i,j so that the flow of the solutions of LV-CA can be represented by interactions of maps between {fi,j}. Thus existence of stable families above will be heavily influenced by stability of dynamical properties of the family {fi,j} under continuous deformations of these maps.


## 6.3.1. The Associated Complex Dynamics

Let us consider a bounded automatonA given by a relative (max,+) function φ. As above, it is given by a pair of (max,+) functions (φ1,φ2). Let ft and (ft1,ft2) be the associated rational and the pair of polynomial functions with respect to φ and (φ1,φ2) mutually. Notice that they are related in the following way: (6.18)ft(z1,z2,…,zN)=zN+1ft2(z1,z2,…,zN)ft1(z1,z2,…,zN,zN+1).For the LV cell automaton,ft above is given by  (6.19)ft(z1,z2,z3)=(tL+z3)-1(tLz1+z1z2).Now fort=0,1,…, let us consider a flow given by infinite sequences of complex numbers (z1t,z2t,z3t,…)∈C∞ which obey the equation  (6.20)zn+1t+1=ft(zn-kt-l,…,znt+1).
Notice that, if (zn-kt-l,…,znt+1)∈R>0N, then zn+1t+1∈(0,∞).Since it also satisfies the equation(6.21)ft1(zn-kt-l,…,zn+1t+1)=ft2(zn-kt-l,…,znt+1),
each building block znt=(zn-kt-l,…,znt+1) lies on V(A)t for all n≥k and t≥l. We say that the sequences  (6.22){znt}n≥k,t≥l⊂V(A)t
are the induced dynamics on V(A)t.


## 6.3.2. Stability

So far, we have discussed by fixing the parametert. Here we consider the asymptotics of flows as t→∞.Let(φ1,φ2) be a bounded automaton given by two max-plus functions with the N+1 variables (Vn-kt-l,…,Vn+1t+1) as above. Let us denote the associated polynomials φti and fti, i=1,2.Lemma 6.5.
Letzt∈R>0N+1 be a family of points. Suppose that the convergent condition
(6.23)x≡limt→∞Logt(zt)
is satisfied. Then, x∈RN+1 satisfies the following equation:
(6.24)φ1(x)=φ2(x).Proof.
We recall the equalityft=logt-1∘φt∘Logt on the positive real numbers. Thus they satisfy the following equation:
(6.25)φt1∘Logt(zt)=φt2∘Logt(zt).
Then the conclusion holds, since φti converge to the original max-plus functions φi. This completes the proof.Let[v]∈Z be the integer part of v∈R. For a sequence v=(v1,v2,…), we denote by [v]≡([v1],[v2],…).Definition 6.6.
LetA be a bounded automaton, and choose   parameterized families of sequences {znt}n≥k,t≥l⊂CN+1.
We say that they are stable, if there ist0 so that, for all t≥t0,
(6.26){[Logt(znt)]}n≥k,t≥l⊂ZN+1
gives a flow of the solutions of the original automaton A.LetA be the LV cell automaton. Then, as in Section 6.2, there is a family of interval maps {fi,j}i,j so that the flow of the solutions of LV-CA can be represented by interactions of maps between {fi,j}. Thus existence of stable families above will be heavily influenced by stability of dynamical properties of the family {fi,j} under continuous deformations of these maps.


## 6.4. Cell Automatic Varieties

LetA1 and A2 be two cell automata, and consider an integer-valued flow  (6.27){Vt=(V1t,V2t,…)}t≥0⊂Z∞.
If it satisfies both equations for A1 and A2, then we say that {Vt}t is a flow for A1 and A2.Let us denote the set of such flows by(6.28)F(A1,A2)={{Vt}t=0,1,2,…⊂Z∞:flowsforbothA1,A2}.
We say that  F(A1,A2) is a cell automatic variety for A1 and A2.LetA1,…,Am be a family of cell automata. By considering flows for them, one also obtains the cell automatic variety  F(A1,…,Am).


### 6.4.1. Compatible Automata

LetA1 and A2 be two cell automata given by φ and φ', respectively: (6.29)Vn+1t+1=φ(′)({Vn-kt,…,Vn+lt},{Vn-k′t+1,…,Vnt+1})[*](′).
Let us denote the following sets: (6.30)Vnt≡(Vn-kt,…,Vn+lt,Vn-k't+1,…,Vnt+1)∈ZN.We say thatA2 is compatible with A1  if the following holds; suppose that  Vnt satisfies both [*] and [*]′. Let Vn+1t be determined by [*]′. Then, it also satisfies [*].In the case of compatible automata(A1,A2), the cell automatic variety  F(A1,A2) will be nonempty, which does not hold in general.Example 6.7.
LetA1 and A2 be both automata given by linear maps as follows:
(6.31)un+1=αun+βun-1+γ,(A1),un-1=aun+b,(A2).
If these coefficients satisfy the following relations:
(6.32)(1-β)a=α,(1-β)b=γ,
then A2 is compatible with A1.


### 6.4.2. Associated Varieties

LetA1 and A2 be two CA. Let us denote the associated R-polynomials by fti and gti for i=1,2, respectively. Then, one obtains the parameterized affine algebraic varieties given by the following equations: (6.33)V(A1,A2)t={z∈CN:ft1(z)=ft2(z),gt1(z)=gt2(z)}.Let us consider the associated systems of complex dynamics. Let(z1t,z2t,z3t,…)∈C∞ which obey the following system of the equations: (6.34)ft1(zn-kt-l,…,zn+1t+1)=ft2(zn-kt-l,…,znt+1),gt1(zn-kt-l,…,zn+1t+1)=gt2(zn-kt-l,…,znt+1).
Again each building block znt=(zn-kt-l,…,znt+1) lies on V(A1,A2)t, and we say that {znt}n,t is the induced dynamics on V(A1,A2)t.LetA1,…,Am be a family of CA. Then, by the same way as above, one obtains the following  parameterized associated affine algebraic variety: (6.35)V(A1,…,Am)t={z∈CN:(ftk)1(z)=(ftk)2(z),k=1,…,m},
where (ftk)i, i=1,2, are the associated R-polynomials with respect to Ak.


## 6.4.1. Compatible Automata

LetA1 and A2 be two cell automata given by φ and φ', respectively: (6.29)Vn+1t+1=φ(′)({Vn-kt,…,Vn+lt},{Vn-k′t+1,…,Vnt+1})[*](′).
Let us denote the following sets: (6.30)Vnt≡(Vn-kt,…,Vn+lt,Vn-k't+1,…,Vnt+1)∈ZN.We say thatA2 is compatible with A1  if the following holds; suppose that  Vnt satisfies both [*] and [*]′. Let Vn+1t be determined by [*]′. Then, it also satisfies [*].In the case of compatible automata(A1,A2), the cell automatic variety  F(A1,A2) will be nonempty, which does not hold in general.Example 6.7.
LetA1 and A2 be both automata given by linear maps as follows:
(6.31)un+1=αun+βun-1+γ,(A1),un-1=aun+b,(A2).
If these coefficients satisfy the following relations:
(6.32)(1-β)a=α,(1-β)b=γ,
then A2 is compatible with A1.


## 6.4.2. Associated Varieties

LetA1 and A2 be two CA. Let us denote the associated R-polynomials by fti and gti for i=1,2, respectively. Then, one obtains the parameterized affine algebraic varieties given by the following equations: (6.33)V(A1,A2)t={z∈CN:ft1(z)=ft2(z),gt1(z)=gt2(z)}.Let us consider the associated systems of complex dynamics. Let(z1t,z2t,z3t,…)∈C∞ which obey the following system of the equations: (6.34)ft1(zn-kt-l,…,zn+1t+1)=ft2(zn-kt-l,…,znt+1),gt1(zn-kt-l,…,zn+1t+1)=gt2(zn-kt-l,…,znt+1).
Again each building block znt=(zn-kt-l,…,znt+1) lies on V(A1,A2)t, and we say that {znt}n,t is the induced dynamics on V(A1,A2)t.LetA1,…,Am be a family of CA. Then, by the same way as above, one obtains the following  parameterized associated affine algebraic variety: (6.35)V(A1,…,Am)t={z∈CN:(ftk)1(z)=(ftk)2(z),k=1,…,m},
where (ftk)i, i=1,2, are the associated R-polynomials with respect to Ak.


## 6.5. Duality

Here we introduce a new duality on the set of automata. It passes through theprojective duality between algebraic varieties [17].LetV be a complex n-dimensional vector space and let  P(V) be its projective space. There is a natural isomorphism P(V)≅P*(V*), where P*(W) is the set of all hyperplanes in W  and V* is the dual space to V.Projective duality generalizes this operation to varieties. Let us quickly describe its construction. LetX⊂P(V) be an algebraic variety. Then, one can associate another variety X∨⊂P(V*) as follows. A hyperplane H⊂P(V) is said to be tangent to X  if there exists a smooth point x∈H∩X and the tangent space of X at x is contained in H. Let X*⊂P*(V) be all of the set of tangent hyperplanes, and passing through the above isomorphism, one obtains a set X∨⊂P(V*) which is the desired one. It is called the projective dual variety. In the case when X∨⊂P(V*) is a hypersurface, then its defining polynomial ΔX is called the X-discriminant.Let{A1,…,Am} be a family of automata. Thus one obtains a parameterized family of projective varieties V({Ai})t⊂CPN by taking closure of the associated affine varieties.LetṼ({Ai})t∨⊂CPN be the corresponding parameterized projective dual varieties.Suppose that  these are hypersurfaces, and denote the defining functions byΣjtαjajzj. When one can modify the polynomial as Σjtαjwj by change of variables alzl=wl, then we call Σjtαjwj  the {Ai}-discriminant  and denote it by  (6.36)Δ({Ai})t.
We will denote the corresponding modified varieties by  (6.37)V({Ai})t∨
and call them as the associated dual varieties with respect to {Ai}i. They are isomorphic with Ṽ({Ai})t∨.Definition 6.8.
Letφt be the associated Rt-polynomials to Δ({Ai})t). The automaton defined by φ∞=limt→∞φt is called the projectively dual automaton.We denote the projectively dual automaton by(6.38){Ai}∨.


### 6.5.1. Curves inCP2

In general it is not easy to calculate the defining equations of the projective varieties. However as far as the simplest case is that  of the curves inCP2, one can write down them explicitly. Using this fact, we verify the following.Proposition 6.9.
Consider(6.39)[max{aun,α+aun+1}=c]∨=max{aa-1(c-αa)+aa-1un+1,aca-1+aa-1un}=c.Proof.
LetX⊂CP2 be an irreducible curve. Then, it is known that X∨⊂CP2 is also another irreducible one. In the affine coordinate, if X has a parameterization x=x(s) and y=y(s), s∈C, then X∨ has a parameterization given by the following (see [17]):
(6.40)p(s)=-y'(s)x'(s)y(s)-x(s)y'(s),q(s)=x'(s)x'(s)y(s)-x(s)y'(s).
Using this, let us consider the very simple case above. Leta≥2, let α and c be integers, and consider an automaton A given by
(6.41)max{aun,α+aun+1}=c.
The associated polynomial and the associated varieties are given by
(6.42)X={(x,y)∈C2⊂CP2:xa+tαya=tc}.
Choosing a parameterization as
(6.43)x=s,y=t-α/a(tc-sa)1/a,
one can immediately obtain the parameterization of X∨ as
(6.44)t(a/(a-1))(c-α/a)qa/(a-1)+tac/(a-1)pa/(a-1)=tc(*)
which gives the dual varieties
(6.45)V(A)t∨={(p,q)∈C2⊂CP2:(*)}.
Thus the projectively dual automaton admits the desired presentation. This completes the proof.


## 6.5.1. Curves inCP2

In general it is not easy to calculate the defining equations of the projective varieties. However as far as the simplest case is that  of the curves inCP2, one can write down them explicitly. Using this fact, we verify the following.Proposition 6.9.
Consider(6.39)[max{aun,α+aun+1}=c]∨=max{aa-1(c-αa)+aa-1un+1,aca-1+aa-1un}=c.Proof.
LetX⊂CP2 be an irreducible curve. Then, it is known that X∨⊂CP2 is also another irreducible one. In the affine coordinate, if X has a parameterization x=x(s) and y=y(s), s∈C, then X∨ has a parameterization given by the following (see [17]):
(6.40)p(s)=-y'(s)x'(s)y(s)-x(s)y'(s),q(s)=x'(s)x'(s)y(s)-x(s)y'(s).
Using this, let us consider the very simple case above. Leta≥2, let α and c be integers, and consider an automaton A given by
(6.41)max{aun,α+aun+1}=c.
The associated polynomial and the associated varieties are given by
(6.42)X={(x,y)∈C2⊂CP2:xa+tαya=tc}.
Choosing a parameterization as
(6.43)x=s,y=t-α/a(tc-sa)1/a,
one can immediately obtain the parameterization of X∨ as
(6.44)t(a/(a-1))(c-α/a)qa/(a-1)+tac/(a-1)pa/(a-1)=tc(*)
which gives the dual varieties
(6.45)V(A)t∨={(p,q)∈C2⊂CP2:(*)}.
Thus the projectively dual automaton admits the desired presentation. This completes the proof.


## 6.6. Transformations

Let us take two automataO and O′,  and let  O¯={O=O0→O1→⋯Om=O′}∈Ω(O,O′) be an invertible path, as in Section 4.3, whose associated R-polynomials are given as the pairs (ft1,ft2)i, i=0,…,m. Then, correspondingly the associated hypersurfaces {V(Oi)}i=0,…,m⊂CN are obtained. We call this a lifting of O¯∈ΩO.Question 3.
What are geometric structure of such liftings?Recall that we have obtained  other cell automataO1 and O2 during the process of transforming from BBS to LV; see  Section 4.1. Similarly, as above we rewrite these as (6.46)Un+1t+1+max{1,Un+1t}=Unt+max{1,Unt+1},Sn+1t+1+max{Snt+1+1,Sn+1t}=Snt+Snt+1+1.
Let us assign the variables as  (6.47)z1⟷Xnt,z2⟷Xn+1t,z3⟷Xnt+1,z4⟷Xn+1t+1
for both X=S and X=U. Then, we have the corresponding polynomial pairs as  (6.48)ft1(z2,z4)=z4(t+z2),ft2(z1,z3)=z1(t+z3),forU,ft1(z2,z3,z4)=z4(tz3+z2),ft2(z1,z3)=tz3z1,forS.
Thus one has obtained three associated hypersurfaces as follows: (6.49)V(LV),V(U),V(S)⊂C4.
Below we study one aspect of Question 3 for this case.


### 6.6.1. Representatives by Homogeneous Maps

Let us consider a bounded automatonA given by a relative (max,+) function φ. As in Section 6.3.1, it is given by a pair of (max,+) functions (φ1,φ2). Let (ft1,ft2) be the associated polynomials with respect to (φ1,φ2).If bothft1 and ft2 are homogeneous polynomials of the same degree, then we say that A is a homogeneous cell automaton.The LV-CA is not homogeneous; see Section6.3. However one can deform it so that the result becomes homogeneous as below.LetO be a cell automaton. We say that  O admits a homogeneous representative  if there is an invertible transformation  O=O0→O1→⋯→Ok so that Ok is homogeneous.Lemma 6.10.
LV cell automaton admits a homogeneous representative.Proof.
LetO0=LV→O1→O2→O3=BBS be the invertible path in Lemma 4.1. Then, certainly O2 is homogeneous as above.
This completes the proof.LetO be a homogeneous cell automaton. Then, one obtains theassociated projective hypersurface(6.50)V(O)⊂CPN-1.
We say that V(O) is the associated projective hypersurface.


## 6.6.1. Representatives by Homogeneous Maps

Let us consider a bounded automatonA given by a relative (max,+) function φ. As in Section 6.3.1, it is given by a pair of (max,+) functions (φ1,φ2). Let (ft1,ft2) be the associated polynomials with respect to (φ1,φ2).If bothft1 and ft2 are homogeneous polynomials of the same degree, then we say that A is a homogeneous cell automaton.The LV-CA is not homogeneous; see Section6.3. However one can deform it so that the result becomes homogeneous as below.LetO be a cell automaton. We say that  O admits a homogeneous representative  if there is an invertible transformation  O=O0→O1→⋯→Ok so that Ok is homogeneous.Lemma 6.10.
LV cell automaton admits a homogeneous representative.Proof.
LetO0=LV→O1→O2→O3=BBS be the invertible path in Lemma 4.1. Then, certainly O2 is homogeneous as above.
This completes the proof.LetO be a homogeneous cell automaton. Then, one obtains theassociated projective hypersurface(6.50)V(O)⊂CPN-1.
We say that V(O) is the associated projective hypersurface.


## 7. Interaction Graphs

Letf,g:[0,1]→[0,1] be two interval maps and let Φ(x,f,g):X2→X2 be the interaction map. Recall that  π:[0,1]∖1/2→{0,1} is the projection. Let us choose another map d:[0,1]→[0,1].Suppose that,  for a pointz∈[0,1] and some k¯∈X2, the following equality holds: (7.1)Φ(x,f,g)(k¯)=π((d(z),d2(z),…))≡(π(d(z)),π(d2(z)),…).
Then, we express this by a marked oriented edge as  (7.2)(f,x)→(g,k¯)(d,z).Let us choose families of maps{f0,…,fk} and points {x0,…,xl}. For each (i,j,x)∈{0,…,k}2×{x0,…,xl}, let us assign an element k¯(i,j,x)∈X2. Thus we obtain another family {k¯(i,j,xh)}i,j,h=0i,j=k,h=l⊂X2. Then, we put the following two sets:(7.3)V={(fi,xj):0≤i≤k,0≤j≤l}(thesetofvertices),E={ei,j,k:(fi,xh)→(fj,k̅(i,j,xh))(fk,xv):}(thesetofedges).Definition 7.1.
An interaction graph is a marked oriented graph, where the sets of verticesV and edges E are given as above. We denote it by
(7.4)G({fi}ik;{xj}jl;{k¯(i,j,xh)}i,j,h=0i,j=k,h=l).
We will denote the set of interaction graphs arising from {f0,…,fk} and {x0,…,xl} by
(7.5)𝔊({fi}i=0k;{xj}j=0l).
Notice that this is a finite set.Let us put(7.6)X2k,l≡X2k2+l=X2×X2×⋯×X2.
Then, any element in X2k,l can be written as k¯(i,j,x) as above. Then, the family of the interaction map gives a map (7.7)Φ:X2k,l→X2k,l,
where (7.8)Φ({k̅(i,j,x)})={k̅′(i,j,x)},k̅′(i,j,x)≡Φ(fi,fj,x)(k̅(i,j,x)).This induces a map on the set of the interaction graph as(7.9)Φ*:𝔊({fi}i=0k;{xj}j=0l)→𝔊({fi}i=0k;{xj}j=0l)
by(7.10)Φ*(G({fi}ik;{xj}jl;{k̅(i,j,xh)}))=G({fi}ik;{xj}jl;Φ({k̅(i,j,xh)})).
Thus one obtains a sequence of the interaction graphs as follows:(7.11)(G0,G1,…),Gi=G({fi}ik;{xj}jl;Φi({k̅(i,j,xh)}i,j,h=0i,j=k,h=l)).
This gives a dynamics of the interaction graphs. Below we will formulate several geometric spaces arising from dynamics of the interaction graphs which we call the spaces from the interaction graphs.


### 7.1. Veronese Map

Here we have an easy example of spaces from the interaction graphs. Let({fi},{xj},{k¯(i,j,xh)}) be an interaction system, and denote the corresponding interaction graphs by (G0,G1,…). Passing through the forgetful map, one obtains a sequence of finite graphs (G0′,G1′,…).For each vertexv∈Gi′, let e(v) be the number of the edges with a common vertex v. Let us fix m≥0 and put  (7.12)P(m,G)={(i0,…,ik):Σa=0ke(ia)=m,k≤N}.LetN+1 be the number of the edges in the interaction graphs. The Veronese map with respect to {Gi′}i is a family of embeddings:(7.13)Ii:CPN↪CPM,[x0,…,xN]→[{x0i0…,xkik:(i0,…,ik)∈P(m,Gi)}],
where Ni=#P(mi,Gi)+1  and M=(N+1)N/2 is the maximum number of the edges in the graphs.


#### 7.1.1. Reduction to Dynamics of Toric Ideals

Let𝔊 be the set of finite graphs, and let (7.14)F:𝔊({fi}i=0k;{xj}j=0l)→𝔊
be the forgetful map. Then, one obtains a family of finite graphs  (7.15)G1,G2,…⊂𝔊
consisted by the images of F of the interaction graphs. We call them just the associated graphs.Let{G0,G1,…} be a family of finite graphs. We say that the family is strongly regular  if the numbers of edges of Gi are all the same. In Section 7.1, we will always assume that sequences consisted by the images of F of the interaction graphs are strongly regular.For eachG∈𝔊, let us associate a configuration(7.16)𝔄={a¯1,…,a¯m}⊂ZN
as follows, where N=(k+1)(l+1) is the number of the vertices. Let us make a numbering of the set of vertices, v1,…,vN, and let ei∈ZN be the unit vector (0,…,0,1,0,…,0), where 1 appears only at the  ith. Then, ei+ej∈𝔄 if and only if vi and vj are mutually connected by an edge.Thus one obtains a reduction from dynamics of the interaction graphs to the one of the following configurations:(7.17){𝔄0,𝔄1,…},
which we call the transcripted configurations.For a configuration𝔄={a¯1,…,a¯m}⊂ZN, we associate a Laurent polynomial: (7.18)C[𝔄]≡C[ta¯1,…,ta¯m]⊂C[t1±1,…,tN±1],
where ta¯k=t1ak1⋯tNakN, a¯k=(ak1,…,akN). We call C[𝔄] as the associated toric ring.By assigningyi→ta¯i, one obtains a ring homomorphism  (7.19)π:C[y1,…,ym]→C[𝔄]
and its kernel I𝔄 is called the toric ideal.For each interaction graphGi∈𝔊({fi}i=0k,{xj}j=0l), one forgets markings on edges and orientation  and then obtains a finite graph F(Gi). Then, one can assign a configuration 𝔄i⊂ZN. Now correspondingly one has the associated toric ideal Ii⊂C[y1,…,ym]. Thus one has obtained a sequence of toric ideals as (7.20)I0,I1,…,Ik,Ik+1,…⊂C[y1,…,ym]
which we will call the associated ideals. Notice that there are a finite number of ideals {J1,…,Jd} such that each Ii coincides with one of {Jj}. We say that the associated ideals are regular  if all Ii has the same dimension.Let us fix a total ordering< on the set of monomials of the polynomial ring  C[y1,…,ym], for example,  lexicographic or its reverse ones.LetI⊂C[y1,…,ym] be an ideal, and let z¯={z1,…,zk} be a generating set. We denote by intzi to imply the leading term of the polynomial with respect to the ordering. Let int I⊂C[y1,…,yN] be another ideal generated by intz for all z∈I. It is called the initial ideal. We say that z¯ is a Gröbner basis  if (7.21)intI=gen{intz1,…,intzk}.Notice that the sequence of the toric ideals{Ii}i is obtained originally from the data ({fi}i,{xj}j,{k¯(i,j,xh)}). The following problem seems natural, since, in some cases, these interactions come from some combinatoric structures, like cell automata [3].Question 4.
Can one find an algorithm to find out Gröbner basis successively forI0,I1,… from the interaction data?


#### 7.1.2. Gröbner Fans and Translated Varieties

Letw=(w1,…,wm)∈Rm be a vector which is called the weight vector. Then, the weight of a monomial y1a1⋯ymam is equal to 〈w,a¯〉=w1a1+w2a2+⋯+wmam. For each polynomial f=Σca¯ya¯∈C[y1,…,ym], let inw(f)=Σb¯cb¯yb¯, where any b¯ satisfies  〈w,b¯〉=maxca¯≠0〈w,a¯〉.LetI be an  ideal. Then, we denote the corresponding initial ideal  inw(I) generated by all elements of the form  inw(f). It is known that, for every ideal I and ordering <, a weight vector w is associated which satisfies in<(I)=inw(I).For an idealI, we say that w and w′ are equivalent  if they give the same initial ideal intwI=intw′I. The equivalence class  (7.22)ℭ(I,w)={w'∈Rm:intwI=intw′I}
is an open polyhedral cone in Rm.The set of the cones{ℭ(I,w)}w is finite and defines a polyhedral fan 𝔉(I). We say that it is the Gröbner fan of I (see [18]).For each fan, there associated with a toric variety. Thus for each interaction graphG, one associates with a toric variety XG which we call the translated variety.Thus corresponding to a sequence of the associated idealsI0,I1,…, one obtains a sequence of fans over Rm and the associated translated varieties  (7.23)X¯=(X0,X1,…,Xi,…).Remark 7.2.
In order to study structure ofX¯, one may use resultants for the defining polynomials of these ideals.
Now we have started from a finite data(7.24)D=({fi}i=0k,{xj}j=0l,{a¯(i,j,h)}i,j,h=0i,j=k,h=l).
We will call such data an interaction data.
Then, we have obtained a sequence of the interaction graphs:(7.25)G0,G1,…,Gi=G({fi}i=0k,{xj}j=0l,Φ*i({a̅(i,j,h)})).
By forgetting extra data, one obtains a sequence of the transcripted configurations:
(7.26)𝔄0,𝔄1,…,
where 𝔄i⊂ZN. Then, one has obtained a sequence of the toric ideals {I0,I1,…} and the translated toric varieties:
(7.27){X0,X1,…}⊂CPm-1,
where each Xi coincides with one in a finite set of toric varieties {Y1,…,Yl}⊂CPm-1.


#### 7.1.3. Correspondence on Polytopes

Let({fi}k,{xj}l,{a¯(i,j,h)}) be a triple, and consider the corresponding interaction graphs {Gi}i=0∞. Then, there are finite configurations {𝔄1,…,𝔄l}⊂ZN such that each Gi associates one of 𝔄j for some j=j(i).Let𝔄⊂ZN be a configuration, and let  m be the number of the elements in 𝔄.LetΔ be a triangulation of 𝔄. Then, every ψ∈Rm defines the corresponding piecewise linear function gψ,Δ on Rm satisfying gψ,Δ(ai)=ψ(ai) for each vertex ai of Δ which is affine on each simplex of Δ.Then, we put(7.28)ℭ(𝔄,Δ)≡{ψ∈Rm:gψ,Δisconcaveandgψ,Δ≥ψ(ai)wheneveraiisnotavertexofΔ}.
Moreover,  ℭ(𝔄,Δ) is a closed polyhedral cone, and
(7.29)𝔉(𝔄)≡{ℭ(𝔄,Δ):Δisatriangulation}
forms a complete fan on Rm  and is called the secondary fan of 𝔄 [17, page 219]. It is known that the Gröbner fan is a refinement of the secondary fan [18].LetQ⊂Rm be a polytope. Then, for each p∈Q, let us define the normal cone(7.30)N(Q,p)≡{v∈Rm:〈v,p〉≥〈v,y〉∀y∈Q}.
The set of the normal cones  (7.31)N(Q)=⋃p∈VertQN(Q,p)
is called the normal fan.Theorem 7.3 (see [17]).
For a configuration𝔄, there is a polytope Q≡Σ(𝔄) and an assignment of a vertex φΔ∈Q for each triangulation Δ such that the normal cone N(Σ(𝔄),φΔ) coincides with ℭ(𝔄,Δ).
In particular there is a natural correspondence from the secondary fan𝔉(𝔄) to   the corresponding normal fan N(Q).Σ(𝔄) is called the secondary polytope.Let us denote𝔄={a1,…,am}. Then, one can describe Q explicitly as follows. Let us put (7.32)ϕΔ=(ϕδ1,…,ϕΔm)∈Rm,ϕΔi=Σ{vol(τ):τ∈Δ,ai∈τ}.
Then, Q=Σ(𝔄) is given by  (7.33)Q≡Conv{ϕΔ:Δisatriangulationof𝔄},
where vol(τ) is the volume of τ.Now let{𝔄0,…,𝔄l,…}⊂ZN be the transcripted configurations. Then, correspondingly one obtains  other sequences of polytopes: (7.34){Σ(𝔄0),Σ(𝔄1),…},
which is called the secondary transcripted polytopes.


### 7.2. Dynamics over Local Charts

Let us fix two sets{fi}i=0k and {xj}j=0l. Then, there associates with finite numbers of toric ideals {J1,…,Jm}⊂C[y1,…,yN].If we choose a finite subset{a¯(i,j,h)}⊂X2, then one obtains an infinite sequence of ideals  (7.35)I({a¯(i,j,h)})=(I0,I1,…,Ii,…)
among a finite set {Jj}j above.Let us put all of the set of sequences(7.36)I={I({a¯(i,j,h)}):{a¯(i,j,h)}⊂X2}.
We call it the sequence of local charts.One may consider this as though it might be a symbolic dynamics of some “Markov partition’’ over some algebraic varietyV, by regarding each Ik as a defining ideal of a local chart of V.


#### 7.2.1. Algebraic Markov Partition

LetV be an algebraic variety with the affine coordinates Vi defined by an ideal Ji. Let us take an automorphism A on V. We say that an affine coordinate {(Vi,Ji)}i=1m is an (stable) algebraic Markov partition for A  if, for each i, there is some j so that  (7.37)A(Vi)⊂Vj
holds.Example 7.4.
LetA be an automorphism on CPN by [z0,z1,…,zN]→[z1,z0,z2,z3,…,zN]. Then, for Vi={[z0,z1,…,zN]:zi≠0}, CPN admits an affine covering by V0∪V1. Moreover A(Vi)=Vi+1 mod 2.
LetA:V≅V be an automorphism, and consider its iteration At:V≅V. Let us have an algebraic Markov partition by the set {Vi}i. Then, one obtains a symbolic dynamics of the algebraic Markov partition:
(7.38)Σ(A;{Vl}l)={(a0,a1,…):A(Vai)⊂Vai+1)}⊂Xm,
where m is the number of the local charts. It can be expressed by a set of sequences of the defining ideals {(I0,I1,…)}.
One can consider its converse. Let us put the set of all sequences coming from the algebraic Markov partition:(7.39)A={(I0,I1,…)}.
When one is given an interaction data({fi}i,{xj}j,{a¯(i,j,h)}), then one obtains a sequence of ideals. Thus a fundamental question in symbolic dynamics of ideals will be to construct correspondence from interaction data to algebraic Markov partitions.Question 5.
LetI be a set of sequences of ideals among a finite set of ideals. Then, can one construct an algebraic Markov partition {J1,…,Jk} for an algebraic variety V and an automorphism A, so that I⊂A might hold? Namely, when are a set of sequences of ideals symbolic dynamics of algebraic Markov partitions?Conversely, givenA, can one find some {fi}i=0k and {xj}j=0l so that the corresponding I might satisfy I⊂A?We say that  associated idealsI=(I0,I1,…) are regular  if they have the same dimension as the others. Let us put ⋃iIi={J1,…,Jk}.Definition 7.5.
Let({fi}i,{xj}j,{a¯(i,j,h)}) be an interaction data, and suppose that  the associated ideals by I=(I0,I1,…) are regular. The sequence is called a symbolic flow of an automorphism  if there is an algebraic Markov partition for (V,A) with an affine coordinate {(Vi,Ji}i=1k and some x∈V so that its orbit {An(x)}n=0,1,… corresponds to the sequence.We call such pair(V,A) corresponding to I a prohedron. (One may imagine as though it represents some state of a protein.)Let us consider the simplest case. Let us consider the partition ofCPN=V0∪V1 and the involution A in Example 7.4.Lemma 7.6.
Let({fi}i=0k,{xj}j=0l,{a¯(i,j,h)}) be an interaction data such that the corresponding sequence of the interaction graphs G0,G1,… satisfies that (1) the numbers of edges are all constant m, that  (2) F(G2i) and F(G2i+1) are mutually the same finite graphs G and G', respectively for all i, and (3) there are no primitive loops of even length for any graph.
Then, the corresponding sequence of ideals gives an algebraic Markov partition for(V0,V1,A) above.This follows from the following general facts.Sublemma 6.1
The toric ideal is generated by the set of primitive loops of the even length.It follows from this that the corresponding ideals are all zero, which defines the affine planeCN. This completes the proof.This simple case suggests that, in general, possibility of construction of algebraic Markov partitions will be reflected by combinatorics of the transcripted configurations.


#### 7.2.2. Automorphism Groups

Let us choose a family of interval maps{fi}k, and let  V be an algebraic variety. We denote (7.40)D({fi}k,V)≡{({xj}l,{a̅(i,j,h)}):({fi}k,{xj}l,{k̅(i,j,h)})givealgebraicMarkovpartitionsforsomeAonV{xj}l}
in (∪l([0,1]l+1×X2k,l).Let us put the set of the associated automorphismsE and the automorphism groups G generated by E  as(7.41)E({fi}k,V)≡{A=A({fi}k,{xj}k,{k̅(i,j,h)}):({xj}l,{k̅(i,j,h)})∈D({xj}l,V)},G({fi}k,V)=genE({fi}k,V).
We also put the closure of G({fi}k,V) by G¯({fi}k,V)⊂ AutV.Thus for each algebraic varietyV, one has obtained a map from a set of interval maps and a Lie subgroup of Aut V: (7.42)({fi}k,V)→G¯({fi}k,V)⊂AutV.It is known that, whenV is compact and nonsingular toric variety, then Aut V is linear, and its root system can be written explicitly from the fan of V. Thus in this case G¯⊂ Aut V is a closed subgroup of a linear algebraic group. Thus it will be natural to ask the following.Question 6.
Whether one might write down the above subgroups from the information of the associated family of Gröbner fans.


### 7.3. Zariski Subsets on the Moduli of Interaction Graphs

Let us choose an interaction data: (1) a set of interval maps{f1,…,fk}, (2) an index {1,…,l}, and (3) a set of {0,1} sequences {a¯(i,j,h)}i,j,h⊂X2.For each assignment from{1,…,l} to {x1,…,xl}, one obtains the associated interaction graph G. Each edge e=((i,h),(k,v))∈G is assigned with some j∈{1,…,k} so that (fi,xh)→(fj,a¯(i,j,h))(fk,xv) hold. So an interaction graph Gk is a  weighted finite graph such that each edge is assigned with an element in {1,…,k}.Let us fixk and l as above  and denote the set of interaction graphs as follows: (7.43)G(k,l)={G(k,l):interactiongraphs}.
Then  G(k,l) can be parameterized as (7.44)GN≅[0,1]l×Map[({1,…,k}×{1,…,l})2→{0,1,…,k}]≅[0,1]M,
where 0 in the last term implies no edges  and M=M(k,l).So once one gives an interaction data(7.45)({f1,…,fk},{a¯(i,j,h)}),
then one obtains the family of the associated interaction graphs as follows: (7.46)G({fi}i,{a¯(i,j,h)})=⋃{xj}j∈[0,1]lG({fi}i,{xj}j,{a¯(i,j,h)})
in G(k,l)≅[0,1]M.Definition 7.7.
A Zariski subsetX⊂G(k,l)≅[0,1]M is a subset of the form
(7.47)X=G({fi}i,{a¯(i,j,h)})⊂[0,1]M.Let𝔄 be all of the set of the interval maps. Then, we have obtained a map  (7.48)J:𝔄k×[0,1]l×X2k2+l↦G(k,l).Let{fi} and {gi} be two k interval maps. Then consider the following.Question 7.
(1) In order to guarantee thatJ({fi},)=J({gi},) implies that {fi}={gi}, how should k and l be large?
(2) Can one find some continuous properties forJ?LetX be a Zariski subset, and consider a proper decreasing Zariski subsets  (7.49)X=X0⊃X1⊃⋯⊃Xn.
We define the dimension of X to be the largest number n with the above property.


#### 7.3.1. Dynamics on Zariski Subsets

Let us choose a set{xj}l⊂[0,1]l. Then, one obtains sequences {a¯(i,j,h)n}n=0,1,… by using the interaction map. Thus one obtains a sequence of Zariski subsets as follows:(7.50)X0,X1,…,Xn,Xn+1,…⊂[0,1]M,Xn=G({fi},{a̅(i,j,h)n}).
We say that ⋂nXn is an invariant subset. If limnXn⊂G(k,l) exists, then we say that the associated dynamics of the Zariski subsets converges.


## 7.1. Veronese Map

Here we have an easy example of spaces from the interaction graphs. Let({fi},{xj},{k¯(i,j,xh)}) be an interaction system, and denote the corresponding interaction graphs by (G0,G1,…). Passing through the forgetful map, one obtains a sequence of finite graphs (G0′,G1′,…).For each vertexv∈Gi′, let e(v) be the number of the edges with a common vertex v. Let us fix m≥0 and put  (7.12)P(m,G)={(i0,…,ik):Σa=0ke(ia)=m,k≤N}.LetN+1 be the number of the edges in the interaction graphs. The Veronese map with respect to {Gi′}i is a family of embeddings:(7.13)Ii:CPN↪CPM,[x0,…,xN]→[{x0i0…,xkik:(i0,…,ik)∈P(m,Gi)}],
where Ni=#P(mi,Gi)+1  and M=(N+1)N/2 is the maximum number of the edges in the graphs.


### 7.1.1. Reduction to Dynamics of Toric Ideals

Let𝔊 be the set of finite graphs, and let (7.14)F:𝔊({fi}i=0k;{xj}j=0l)→𝔊
be the forgetful map. Then, one obtains a family of finite graphs  (7.15)G1,G2,…⊂𝔊
consisted by the images of F of the interaction graphs. We call them just the associated graphs.Let{G0,G1,…} be a family of finite graphs. We say that the family is strongly regular  if the numbers of edges of Gi are all the same. In Section 7.1, we will always assume that sequences consisted by the images of F of the interaction graphs are strongly regular.For eachG∈𝔊, let us associate a configuration(7.16)𝔄={a¯1,…,a¯m}⊂ZN
as follows, where N=(k+1)(l+1) is the number of the vertices. Let us make a numbering of the set of vertices, v1,…,vN, and let ei∈ZN be the unit vector (0,…,0,1,0,…,0), where 1 appears only at the  ith. Then, ei+ej∈𝔄 if and only if vi and vj are mutually connected by an edge.Thus one obtains a reduction from dynamics of the interaction graphs to the one of the following configurations:(7.17){𝔄0,𝔄1,…},
which we call the transcripted configurations.For a configuration𝔄={a¯1,…,a¯m}⊂ZN, we associate a Laurent polynomial: (7.18)C[𝔄]≡C[ta¯1,…,ta¯m]⊂C[t1±1,…,tN±1],
where ta¯k=t1ak1⋯tNakN, a¯k=(ak1,…,akN). We call C[𝔄] as the associated toric ring.By assigningyi→ta¯i, one obtains a ring homomorphism  (7.19)π:C[y1,…,ym]→C[𝔄]
and its kernel I𝔄 is called the toric ideal.For each interaction graphGi∈𝔊({fi}i=0k,{xj}j=0l), one forgets markings on edges and orientation  and then obtains a finite graph F(Gi). Then, one can assign a configuration 𝔄i⊂ZN. Now correspondingly one has the associated toric ideal Ii⊂C[y1,…,ym]. Thus one has obtained a sequence of toric ideals as (7.20)I0,I1,…,Ik,Ik+1,…⊂C[y1,…,ym]
which we will call the associated ideals. Notice that there are a finite number of ideals {J1,…,Jd} such that each Ii coincides with one of {Jj}. We say that the associated ideals are regular  if all Ii has the same dimension.Let us fix a total ordering< on the set of monomials of the polynomial ring  C[y1,…,ym], for example,  lexicographic or its reverse ones.LetI⊂C[y1,…,ym] be an ideal, and let z¯={z1,…,zk} be a generating set. We denote by intzi to imply the leading term of the polynomial with respect to the ordering. Let int I⊂C[y1,…,yN] be another ideal generated by intz for all z∈I. It is called the initial ideal. We say that z¯ is a Gröbner basis  if (7.21)intI=gen{intz1,…,intzk}.Notice that the sequence of the toric ideals{Ii}i is obtained originally from the data ({fi}i,{xj}j,{k¯(i,j,xh)}). The following problem seems natural, since, in some cases, these interactions come from some combinatoric structures, like cell automata [3].Question 4.
Can one find an algorithm to find out Gröbner basis successively forI0,I1,… from the interaction data?


### 7.1.2. Gröbner Fans and Translated Varieties

Letw=(w1,…,wm)∈Rm be a vector which is called the weight vector. Then, the weight of a monomial y1a1⋯ymam is equal to 〈w,a¯〉=w1a1+w2a2+⋯+wmam. For each polynomial f=Σca¯ya¯∈C[y1,…,ym], let inw(f)=Σb¯cb¯yb¯, where any b¯ satisfies  〈w,b¯〉=maxca¯≠0〈w,a¯〉.LetI be an  ideal. Then, we denote the corresponding initial ideal  inw(I) generated by all elements of the form  inw(f). It is known that, for every ideal I and ordering <, a weight vector w is associated which satisfies in<(I)=inw(I).For an idealI, we say that w and w′ are equivalent  if they give the same initial ideal intwI=intw′I. The equivalence class  (7.22)ℭ(I,w)={w'∈Rm:intwI=intw′I}
is an open polyhedral cone in Rm.The set of the cones{ℭ(I,w)}w is finite and defines a polyhedral fan 𝔉(I). We say that it is the Gröbner fan of I (see [18]).For each fan, there associated with a toric variety. Thus for each interaction graphG, one associates with a toric variety XG which we call the translated variety.Thus corresponding to a sequence of the associated idealsI0,I1,…, one obtains a sequence of fans over Rm and the associated translated varieties  (7.23)X¯=(X0,X1,…,Xi,…).Remark 7.2.
In order to study structure ofX¯, one may use resultants for the defining polynomials of these ideals.
Now we have started from a finite data(7.24)D=({fi}i=0k,{xj}j=0l,{a¯(i,j,h)}i,j,h=0i,j=k,h=l).
We will call such data an interaction data.
Then, we have obtained a sequence of the interaction graphs:(7.25)G0,G1,…,Gi=G({fi}i=0k,{xj}j=0l,Φ*i({a̅(i,j,h)})).
By forgetting extra data, one obtains a sequence of the transcripted configurations:
(7.26)𝔄0,𝔄1,…,
where 𝔄i⊂ZN. Then, one has obtained a sequence of the toric ideals {I0,I1,…} and the translated toric varieties:
(7.27){X0,X1,…}⊂CPm-1,
where each Xi coincides with one in a finite set of toric varieties {Y1,…,Yl}⊂CPm-1.


### 7.1.3. Correspondence on Polytopes

Let({fi}k,{xj}l,{a¯(i,j,h)}) be a triple, and consider the corresponding interaction graphs {Gi}i=0∞. Then, there are finite configurations {𝔄1,…,𝔄l}⊂ZN such that each Gi associates one of 𝔄j for some j=j(i).Let𝔄⊂ZN be a configuration, and let  m be the number of the elements in 𝔄.LetΔ be a triangulation of 𝔄. Then, every ψ∈Rm defines the corresponding piecewise linear function gψ,Δ on Rm satisfying gψ,Δ(ai)=ψ(ai) for each vertex ai of Δ which is affine on each simplex of Δ.Then, we put(7.28)ℭ(𝔄,Δ)≡{ψ∈Rm:gψ,Δisconcaveandgψ,Δ≥ψ(ai)wheneveraiisnotavertexofΔ}.
Moreover,  ℭ(𝔄,Δ) is a closed polyhedral cone, and
(7.29)𝔉(𝔄)≡{ℭ(𝔄,Δ):Δisatriangulation}
forms a complete fan on Rm  and is called the secondary fan of 𝔄 [17, page 219]. It is known that the Gröbner fan is a refinement of the secondary fan [18].LetQ⊂Rm be a polytope. Then, for each p∈Q, let us define the normal cone(7.30)N(Q,p)≡{v∈Rm:〈v,p〉≥〈v,y〉∀y∈Q}.
The set of the normal cones  (7.31)N(Q)=⋃p∈VertQN(Q,p)
is called the normal fan.Theorem 7.3 (see [17]).
For a configuration𝔄, there is a polytope Q≡Σ(𝔄) and an assignment of a vertex φΔ∈Q for each triangulation Δ such that the normal cone N(Σ(𝔄),φΔ) coincides with ℭ(𝔄,Δ).
In particular there is a natural correspondence from the secondary fan𝔉(𝔄) to   the corresponding normal fan N(Q).Σ(𝔄) is called the secondary polytope.Let us denote𝔄={a1,…,am}. Then, one can describe Q explicitly as follows. Let us put (7.32)ϕΔ=(ϕδ1,…,ϕΔm)∈Rm,ϕΔi=Σ{vol(τ):τ∈Δ,ai∈τ}.
Then, Q=Σ(𝔄) is given by  (7.33)Q≡Conv{ϕΔ:Δisatriangulationof𝔄},
where vol(τ) is the volume of τ.Now let{𝔄0,…,𝔄l,…}⊂ZN be the transcripted configurations. Then, correspondingly one obtains  other sequences of polytopes: (7.34){Σ(𝔄0),Σ(𝔄1),…},
which is called the secondary transcripted polytopes.


## 7.1.1. Reduction to Dynamics of Toric Ideals

Let𝔊 be the set of finite graphs, and let (7.14)F:𝔊({fi}i=0k;{xj}j=0l)→𝔊
be the forgetful map. Then, one obtains a family of finite graphs  (7.15)G1,G2,…⊂𝔊
consisted by the images of F of the interaction graphs. We call them just the associated graphs.Let{G0,G1,…} be a family of finite graphs. We say that the family is strongly regular  if the numbers of edges of Gi are all the same. In Section 7.1, we will always assume that sequences consisted by the images of F of the interaction graphs are strongly regular.For eachG∈𝔊, let us associate a configuration(7.16)𝔄={a¯1,…,a¯m}⊂ZN
as follows, where N=(k+1)(l+1) is the number of the vertices. Let us make a numbering of the set of vertices, v1,…,vN, and let ei∈ZN be the unit vector (0,…,0,1,0,…,0), where 1 appears only at the  ith. Then, ei+ej∈𝔄 if and only if vi and vj are mutually connected by an edge.Thus one obtains a reduction from dynamics of the interaction graphs to the one of the following configurations:(7.17){𝔄0,𝔄1,…},
which we call the transcripted configurations.For a configuration𝔄={a¯1,…,a¯m}⊂ZN, we associate a Laurent polynomial: (7.18)C[𝔄]≡C[ta¯1,…,ta¯m]⊂C[t1±1,…,tN±1],
where ta¯k=t1ak1⋯tNakN, a¯k=(ak1,…,akN). We call C[𝔄] as the associated toric ring.By assigningyi→ta¯i, one obtains a ring homomorphism  (7.19)π:C[y1,…,ym]→C[𝔄]
and its kernel I𝔄 is called the toric ideal.For each interaction graphGi∈𝔊({fi}i=0k,{xj}j=0l), one forgets markings on edges and orientation  and then obtains a finite graph F(Gi). Then, one can assign a configuration 𝔄i⊂ZN. Now correspondingly one has the associated toric ideal Ii⊂C[y1,…,ym]. Thus one has obtained a sequence of toric ideals as (7.20)I0,I1,…,Ik,Ik+1,…⊂C[y1,…,ym]
which we will call the associated ideals. Notice that there are a finite number of ideals {J1,…,Jd} such that each Ii coincides with one of {Jj}. We say that the associated ideals are regular  if all Ii has the same dimension.Let us fix a total ordering< on the set of monomials of the polynomial ring  C[y1,…,ym], for example,  lexicographic or its reverse ones.LetI⊂C[y1,…,ym] be an ideal, and let z¯={z1,…,zk} be a generating set. We denote by intzi to imply the leading term of the polynomial with respect to the ordering. Let int I⊂C[y1,…,yN] be another ideal generated by intz for all z∈I. It is called the initial ideal. We say that z¯ is a Gröbner basis  if (7.21)intI=gen{intz1,…,intzk}.Notice that the sequence of the toric ideals{Ii}i is obtained originally from the data ({fi}i,{xj}j,{k¯(i,j,xh)}). The following problem seems natural, since, in some cases, these interactions come from some combinatoric structures, like cell automata [3].Question 4.
Can one find an algorithm to find out Gröbner basis successively forI0,I1,… from the interaction data?


## 7.1.2. Gröbner Fans and Translated Varieties

Letw=(w1,…,wm)∈Rm be a vector which is called the weight vector. Then, the weight of a monomial y1a1⋯ymam is equal to 〈w,a¯〉=w1a1+w2a2+⋯+wmam. For each polynomial f=Σca¯ya¯∈C[y1,…,ym], let inw(f)=Σb¯cb¯yb¯, where any b¯ satisfies  〈w,b¯〉=maxca¯≠0〈w,a¯〉.LetI be an  ideal. Then, we denote the corresponding initial ideal  inw(I) generated by all elements of the form  inw(f). It is known that, for every ideal I and ordering <, a weight vector w is associated which satisfies in<(I)=inw(I).For an idealI, we say that w and w′ are equivalent  if they give the same initial ideal intwI=intw′I. The equivalence class  (7.22)ℭ(I,w)={w'∈Rm:intwI=intw′I}
is an open polyhedral cone in Rm.The set of the cones{ℭ(I,w)}w is finite and defines a polyhedral fan 𝔉(I). We say that it is the Gröbner fan of I (see [18]).For each fan, there associated with a toric variety. Thus for each interaction graphG, one associates with a toric variety XG which we call the translated variety.Thus corresponding to a sequence of the associated idealsI0,I1,…, one obtains a sequence of fans over Rm and the associated translated varieties  (7.23)X¯=(X0,X1,…,Xi,…).Remark 7.2.
In order to study structure ofX¯, one may use resultants for the defining polynomials of these ideals.
Now we have started from a finite data(7.24)D=({fi}i=0k,{xj}j=0l,{a¯(i,j,h)}i,j,h=0i,j=k,h=l).
We will call such data an interaction data.
Then, we have obtained a sequence of the interaction graphs:(7.25)G0,G1,…,Gi=G({fi}i=0k,{xj}j=0l,Φ*i({a̅(i,j,h)})).
By forgetting extra data, one obtains a sequence of the transcripted configurations:
(7.26)𝔄0,𝔄1,…,
where 𝔄i⊂ZN. Then, one has obtained a sequence of the toric ideals {I0,I1,…} and the translated toric varieties:
(7.27){X0,X1,…}⊂CPm-1,
where each Xi coincides with one in a finite set of toric varieties {Y1,…,Yl}⊂CPm-1.


## 7.1.3. Correspondence on Polytopes

Let({fi}k,{xj}l,{a¯(i,j,h)}) be a triple, and consider the corresponding interaction graphs {Gi}i=0∞. Then, there are finite configurations {𝔄1,…,𝔄l}⊂ZN such that each Gi associates one of 𝔄j for some j=j(i).Let𝔄⊂ZN be a configuration, and let  m be the number of the elements in 𝔄.LetΔ be a triangulation of 𝔄. Then, every ψ∈Rm defines the corresponding piecewise linear function gψ,Δ on Rm satisfying gψ,Δ(ai)=ψ(ai) for each vertex ai of Δ which is affine on each simplex of Δ.Then, we put(7.28)ℭ(𝔄,Δ)≡{ψ∈Rm:gψ,Δisconcaveandgψ,Δ≥ψ(ai)wheneveraiisnotavertexofΔ}.
Moreover,  ℭ(𝔄,Δ) is a closed polyhedral cone, and
(7.29)𝔉(𝔄)≡{ℭ(𝔄,Δ):Δisatriangulation}
forms a complete fan on Rm  and is called the secondary fan of 𝔄 [17, page 219]. It is known that the Gröbner fan is a refinement of the secondary fan [18].LetQ⊂Rm be a polytope. Then, for each p∈Q, let us define the normal cone(7.30)N(Q,p)≡{v∈Rm:〈v,p〉≥〈v,y〉∀y∈Q}.
The set of the normal cones  (7.31)N(Q)=⋃p∈VertQN(Q,p)
is called the normal fan.Theorem 7.3 (see [17]).
For a configuration𝔄, there is a polytope Q≡Σ(𝔄) and an assignment of a vertex φΔ∈Q for each triangulation Δ such that the normal cone N(Σ(𝔄),φΔ) coincides with ℭ(𝔄,Δ).
In particular there is a natural correspondence from the secondary fan𝔉(𝔄) to   the corresponding normal fan N(Q).Σ(𝔄) is called the secondary polytope.Let us denote𝔄={a1,…,am}. Then, one can describe Q explicitly as follows. Let us put (7.32)ϕΔ=(ϕδ1,…,ϕΔm)∈Rm,ϕΔi=Σ{vol(τ):τ∈Δ,ai∈τ}.
Then, Q=Σ(𝔄) is given by  (7.33)Q≡Conv{ϕΔ:Δisatriangulationof𝔄},
where vol(τ) is the volume of τ.Now let{𝔄0,…,𝔄l,…}⊂ZN be the transcripted configurations. Then, correspondingly one obtains  other sequences of polytopes: (7.34){Σ(𝔄0),Σ(𝔄1),…},
which is called the secondary transcripted polytopes.


## 7.2. Dynamics over Local Charts

Let us fix two sets{fi}i=0k and {xj}j=0l. Then, there associates with finite numbers of toric ideals {J1,…,Jm}⊂C[y1,…,yN].If we choose a finite subset{a¯(i,j,h)}⊂X2, then one obtains an infinite sequence of ideals  (7.35)I({a¯(i,j,h)})=(I0,I1,…,Ii,…)
among a finite set {Jj}j above.Let us put all of the set of sequences(7.36)I={I({a¯(i,j,h)}):{a¯(i,j,h)}⊂X2}.
We call it the sequence of local charts.One may consider this as though it might be a symbolic dynamics of some “Markov partition’’ over some algebraic varietyV, by regarding each Ik as a defining ideal of a local chart of V.


### 7.2.1. Algebraic Markov Partition

LetV be an algebraic variety with the affine coordinates Vi defined by an ideal Ji. Let us take an automorphism A on V. We say that an affine coordinate {(Vi,Ji)}i=1m is an (stable) algebraic Markov partition for A  if, for each i, there is some j so that  (7.37)A(Vi)⊂Vj
holds.Example 7.4.
LetA be an automorphism on CPN by [z0,z1,…,zN]→[z1,z0,z2,z3,…,zN]. Then, for Vi={[z0,z1,…,zN]:zi≠0}, CPN admits an affine covering by V0∪V1. Moreover A(Vi)=Vi+1 mod 2.
LetA:V≅V be an automorphism, and consider its iteration At:V≅V. Let us have an algebraic Markov partition by the set {Vi}i. Then, one obtains a symbolic dynamics of the algebraic Markov partition:
(7.38)Σ(A;{Vl}l)={(a0,a1,…):A(Vai)⊂Vai+1)}⊂Xm,
where m is the number of the local charts. It can be expressed by a set of sequences of the defining ideals {(I0,I1,…)}.
One can consider its converse. Let us put the set of all sequences coming from the algebraic Markov partition:(7.39)A={(I0,I1,…)}.
When one is given an interaction data({fi}i,{xj}j,{a¯(i,j,h)}), then one obtains a sequence of ideals. Thus a fundamental question in symbolic dynamics of ideals will be to construct correspondence from interaction data to algebraic Markov partitions.Question 5.
LetI be a set of sequences of ideals among a finite set of ideals. Then, can one construct an algebraic Markov partition {J1,…,Jk} for an algebraic variety V and an automorphism A, so that I⊂A might hold? Namely, when are a set of sequences of ideals symbolic dynamics of algebraic Markov partitions?Conversely, givenA, can one find some {fi}i=0k and {xj}j=0l so that the corresponding I might satisfy I⊂A?We say that  associated idealsI=(I0,I1,…) are regular  if they have the same dimension as the others. Let us put ⋃iIi={J1,…,Jk}.Definition 7.5.
Let({fi}i,{xj}j,{a¯(i,j,h)}) be an interaction data, and suppose that  the associated ideals by I=(I0,I1,…) are regular. The sequence is called a symbolic flow of an automorphism  if there is an algebraic Markov partition for (V,A) with an affine coordinate {(Vi,Ji}i=1k and some x∈V so that its orbit {An(x)}n=0,1,… corresponds to the sequence.We call such pair(V,A) corresponding to I a prohedron. (One may imagine as though it represents some state of a protein.)Let us consider the simplest case. Let us consider the partition ofCPN=V0∪V1 and the involution A in Example 7.4.Lemma 7.6.
Let({fi}i=0k,{xj}j=0l,{a¯(i,j,h)}) be an interaction data such that the corresponding sequence of the interaction graphs G0,G1,… satisfies that (1) the numbers of edges are all constant m, that  (2) F(G2i) and F(G2i+1) are mutually the same finite graphs G and G', respectively for all i, and (3) there are no primitive loops of even length for any graph.
Then, the corresponding sequence of ideals gives an algebraic Markov partition for(V0,V1,A) above.This follows from the following general facts.Sublemma 6.1
The toric ideal is generated by the set of primitive loops of the even length.It follows from this that the corresponding ideals are all zero, which defines the affine planeCN. This completes the proof.This simple case suggests that, in general, possibility of construction of algebraic Markov partitions will be reflected by combinatorics of the transcripted configurations.


### 7.2.2. Automorphism Groups

Let us choose a family of interval maps{fi}k, and let  V be an algebraic variety. We denote (7.40)D({fi}k,V)≡{({xj}l,{a̅(i,j,h)}):({fi}k,{xj}l,{k̅(i,j,h)})givealgebraicMarkovpartitionsforsomeAonV{xj}l}
in (∪l([0,1]l+1×X2k,l).Let us put the set of the associated automorphismsE and the automorphism groups G generated by E  as(7.41)E({fi}k,V)≡{A=A({fi}k,{xj}k,{k̅(i,j,h)}):({xj}l,{k̅(i,j,h)})∈D({xj}l,V)},G({fi}k,V)=genE({fi}k,V).
We also put the closure of G({fi}k,V) by G¯({fi}k,V)⊂ AutV.Thus for each algebraic varietyV, one has obtained a map from a set of interval maps and a Lie subgroup of Aut V: (7.42)({fi}k,V)→G¯({fi}k,V)⊂AutV.It is known that, whenV is compact and nonsingular toric variety, then Aut V is linear, and its root system can be written explicitly from the fan of V. Thus in this case G¯⊂ Aut V is a closed subgroup of a linear algebraic group. Thus it will be natural to ask the following.Question 6.
Whether one might write down the above subgroups from the information of the associated family of Gröbner fans.


## 7.2.1. Algebraic Markov Partition

LetV be an algebraic variety with the affine coordinates Vi defined by an ideal Ji. Let us take an automorphism A on V. We say that an affine coordinate {(Vi,Ji)}i=1m is an (stable) algebraic Markov partition for A  if, for each i, there is some j so that  (7.37)A(Vi)⊂Vj
holds.Example 7.4.
LetA be an automorphism on CPN by [z0,z1,…,zN]→[z1,z0,z2,z3,…,zN]. Then, for Vi={[z0,z1,…,zN]:zi≠0}, CPN admits an affine covering by V0∪V1. Moreover A(Vi)=Vi+1 mod 2.
LetA:V≅V be an automorphism, and consider its iteration At:V≅V. Let us have an algebraic Markov partition by the set {Vi}i. Then, one obtains a symbolic dynamics of the algebraic Markov partition:
(7.38)Σ(A;{Vl}l)={(a0,a1,…):A(Vai)⊂Vai+1)}⊂Xm,
where m is the number of the local charts. It can be expressed by a set of sequences of the defining ideals {(I0,I1,…)}.
One can consider its converse. Let us put the set of all sequences coming from the algebraic Markov partition:(7.39)A={(I0,I1,…)}.
When one is given an interaction data({fi}i,{xj}j,{a¯(i,j,h)}), then one obtains a sequence of ideals. Thus a fundamental question in symbolic dynamics of ideals will be to construct correspondence from interaction data to algebraic Markov partitions.Question 5.
LetI be a set of sequences of ideals among a finite set of ideals. Then, can one construct an algebraic Markov partition {J1,…,Jk} for an algebraic variety V and an automorphism A, so that I⊂A might hold? Namely, when are a set of sequences of ideals symbolic dynamics of algebraic Markov partitions?Conversely, givenA, can one find some {fi}i=0k and {xj}j=0l so that the corresponding I might satisfy I⊂A?We say that  associated idealsI=(I0,I1,…) are regular  if they have the same dimension as the others. Let us put ⋃iIi={J1,…,Jk}.Definition 7.5.
Let({fi}i,{xj}j,{a¯(i,j,h)}) be an interaction data, and suppose that  the associated ideals by I=(I0,I1,…) are regular. The sequence is called a symbolic flow of an automorphism  if there is an algebraic Markov partition for (V,A) with an affine coordinate {(Vi,Ji}i=1k and some x∈V so that its orbit {An(x)}n=0,1,… corresponds to the sequence.We call such pair(V,A) corresponding to I a prohedron. (One may imagine as though it represents some state of a protein.)Let us consider the simplest case. Let us consider the partition ofCPN=V0∪V1 and the involution A in Example 7.4.Lemma 7.6.
Let({fi}i=0k,{xj}j=0l,{a¯(i,j,h)}) be an interaction data such that the corresponding sequence of the interaction graphs G0,G1,… satisfies that (1) the numbers of edges are all constant m, that  (2) F(G2i) and F(G2i+1) are mutually the same finite graphs G and G', respectively for all i, and (3) there are no primitive loops of even length for any graph.
Then, the corresponding sequence of ideals gives an algebraic Markov partition for(V0,V1,A) above.This follows from the following general facts.Sublemma 6.1
The toric ideal is generated by the set of primitive loops of the even length.It follows from this that the corresponding ideals are all zero, which defines the affine planeCN. This completes the proof.This simple case suggests that, in general, possibility of construction of algebraic Markov partitions will be reflected by combinatorics of the transcripted configurations.


## 7.2.2. Automorphism Groups

Let us choose a family of interval maps{fi}k, and let  V be an algebraic variety. We denote (7.40)D({fi}k,V)≡{({xj}l,{a̅(i,j,h)}):({fi}k,{xj}l,{k̅(i,j,h)})givealgebraicMarkovpartitionsforsomeAonV{xj}l}
in (∪l([0,1]l+1×X2k,l).Let us put the set of the associated automorphismsE and the automorphism groups G generated by E  as(7.41)E({fi}k,V)≡{A=A({fi}k,{xj}k,{k̅(i,j,h)}):({xj}l,{k̅(i,j,h)})∈D({xj}l,V)},G({fi}k,V)=genE({fi}k,V).
We also put the closure of G({fi}k,V) by G¯({fi}k,V)⊂ AutV.Thus for each algebraic varietyV, one has obtained a map from a set of interval maps and a Lie subgroup of Aut V: (7.42)({fi}k,V)→G¯({fi}k,V)⊂AutV.It is known that, whenV is compact and nonsingular toric variety, then Aut V is linear, and its root system can be written explicitly from the fan of V. Thus in this case G¯⊂ Aut V is a closed subgroup of a linear algebraic group. Thus it will be natural to ask the following.Question 6.
Whether one might write down the above subgroups from the information of the associated family of Gröbner fans.


## 7.3. Zariski Subsets on the Moduli of Interaction Graphs

Let us choose an interaction data: (1) a set of interval maps{f1,…,fk}, (2) an index {1,…,l}, and (3) a set of {0,1} sequences {a¯(i,j,h)}i,j,h⊂X2.For each assignment from{1,…,l} to {x1,…,xl}, one obtains the associated interaction graph G. Each edge e=((i,h),(k,v))∈G is assigned with some j∈{1,…,k} so that (fi,xh)→(fj,a¯(i,j,h))(fk,xv) hold. So an interaction graph Gk is a  weighted finite graph such that each edge is assigned with an element in {1,…,k}.Let us fixk and l as above  and denote the set of interaction graphs as follows: (7.43)G(k,l)={G(k,l):interactiongraphs}.
Then  G(k,l) can be parameterized as (7.44)GN≅[0,1]l×Map[({1,…,k}×{1,…,l})2→{0,1,…,k}]≅[0,1]M,
where 0 in the last term implies no edges  and M=M(k,l).So once one gives an interaction data(7.45)({f1,…,fk},{a¯(i,j,h)}),
then one obtains the family of the associated interaction graphs as follows: (7.46)G({fi}i,{a¯(i,j,h)})=⋃{xj}j∈[0,1]lG({fi}i,{xj}j,{a¯(i,j,h)})
in G(k,l)≅[0,1]M.Definition 7.7.
A Zariski subsetX⊂G(k,l)≅[0,1]M is a subset of the form
(7.47)X=G({fi}i,{a¯(i,j,h)})⊂[0,1]M.Let𝔄 be all of the set of the interval maps. Then, we have obtained a map  (7.48)J:𝔄k×[0,1]l×X2k2+l↦G(k,l).Let{fi} and {gi} be two k interval maps. Then consider the following.Question 7.
(1) In order to guarantee thatJ({fi},)=J({gi},) implies that {fi}={gi}, how should k and l be large?
(2) Can one find some continuous properties forJ?LetX be a Zariski subset, and consider a proper decreasing Zariski subsets  (7.49)X=X0⊃X1⊃⋯⊃Xn.
We define the dimension of X to be the largest number n with the above property.


### 7.3.1. Dynamics on Zariski Subsets

Let us choose a set{xj}l⊂[0,1]l. Then, one obtains sequences {a¯(i,j,h)n}n=0,1,… by using the interaction map. Thus one obtains a sequence of Zariski subsets as follows:(7.50)X0,X1,…,Xn,Xn+1,…⊂[0,1]M,Xn=G({fi},{a̅(i,j,h)n}).
We say that ⋂nXn is an invariant subset. If limnXn⊂G(k,l) exists, then we say that the associated dynamics of the Zariski subsets converges.


## 7.3.1. Dynamics on Zariski Subsets

Let us choose a set{xj}l⊂[0,1]l. Then, one obtains sequences {a¯(i,j,h)n}n=0,1,… by using the interaction map. Thus one obtains a sequence of Zariski subsets as follows:(7.50)X0,X1,…,Xn,Xn+1,…⊂[0,1]M,Xn=G({fi},{a̅(i,j,h)n}).
We say that ⋂nXn is an invariant subset. If limnXn⊂G(k,l) exists, then we say that the associated dynamics of the Zariski subsets converges.



---

*Source: 783738-2010-09-08.xml*