Symmetry, Integrability and Geometry: Methods and Applications SIGMA 6 (2010), 027, 18 pages
Level Set Structure
of an Integrable Cellular Automaton?
Taichiro TAKAGI
Department of Applied Physics, National Defense Academy, Kanagawa 239-8686, Japan
E-mail: takagi@nda.ac.jp
Received October 23, 2009, in final form March 15, 2010; Published online March 31, 2010
doi:10.3842/SIGMA.2010.027
Abstract. Based on a group theoretical setting a sort of discrete dynamical system is
constructed and applied to a combinatorial dynamical system defined on the set of certain
Bethe ansatz related objects known as the rigged configurations. This system is then used
to study a one-dimensional periodic cellular automaton related to discrete Toda lattice. It
is shown for the first time that the level set of this cellular automaton is decomposed into
connected components and every such component is a torus.
Key words: periodic box-ball system; rigged configuration; invariant torus
2010 Mathematics Subject Classification: 82B23; 37K15; 68R15; 37B15
1 Introduction
The Liouville’s theorem on completely integrable systems is one of the most fundamental results
in classical mechanics. By V.I. Arnold’s formulation one of the claims in the theorem says that
any compact connected level set of completely integrable systems with N degrees of freedom is
diffeomorphic to an N -dimensional torus [1]. It is called an invariant torus and the theorem also
claims that the phase flow with the Hamiltonian function determines a conditionally periodic
motion on it.
In this paper we study the level set structure of a one-dimensional cellular automaton known
as the periodic box-ball system (pBBS) [2, 3] and construct its invariant tori. It is one of the
(ultra-)discrete dynamical systems associated with integrable non-linear evolution equations. See
the “picture” in Subsection 4.1, just below Remark 4, for an example of the time evolution of this
system, in which mutually interacting solitons are traveling along it. This system is attracting
attentions because of its relations with discrete Toda lattice [4], Bethe ansatz of integrable
quantum spin chains [5], tropical geometry [6] and ultradiscrete Riemann theta functions [7].
The purpose of this paper is twofold. The first is to construct a discrete dynamical system
through a group theoretical setting which has potentially several applications in (ultra-)discrete
integrable systems (Theorem 1). The second is to make the structure of the level set of pBBS
perfectly clear as one of its applications (Theorem 2). It is shown for the first time that the
level set is decomposed into connected components and every such component is a torus, as if
it were a compact level set of completely integrable systems in Hamiltonian mechanics.
Let us begin by describing backgrounds and motivations on the problem more precisely. Con-
sider the completely integrable systems with N degrees of freedom again. Such a system has N
independent first integrals. Its level set is determined by fixing the values of the first integrals,
and becomes an N -dimensional manifold in the 2N -dimensional phase space. Inspired by this
?This paper is a contribution to the Proceedings of the Workshop “Geometric Aspects of Discrete and Ultra-
Discrete Integrable Systems” (March 30 – April 3, 2009, University of Glasgow, UK). The full collection is available
at http://www.emis.de/journals/SIGMA/GADUDIS2009.html
2 T. Takagi
picture in Hamiltonian mechanics, A. Kuniba, A. Takenouchi and the author introduced the no-
tion of the level set of pBBS [5], and provided its volume formula. In fact it was exactly equal to
the same formula for the enumeration of the off-diagonal solutions to the string center equations
in combinatorial Bethe ansatz [8]. It is based on the notion of rigged configurations [9, 10], and
is described in the following way. Let mj be the number of solitons with amplitude j. In what
follows mj are supposed to be positive for 1 ≤ j ≤ N and to be zero for j > N for simplicity.
One can think of m = (mj)1≤j≤N as a collection of fixed values of the first integrals. We denote
by J (m) the level set specified by m and by Ω(m) its volume. Then we have [5]
Ω(m) = (detF )
∏
1≤j≤N
1
mj
(
pj +mj − 1
mj − 1
)
. (1)
Here pj are positive integers and F is an N ×N matrix with integer entries, which are explicitly
expressed in terms of m and the system size L.
It can be shown that if there is no solitons of common amplitudes then the level set J (m)
becomes a torus FZN\ZN .1 This fact is suggested by the volume formula (1) that reduces to
Ω(m) = detF when mj = 1 for every j. However this simple picture fails when there are
multiple solitons of common amplitudes. If so, the right hand side of (1) can not be regarded as
the volume of a torus any more. An expression for the level set in this generalized case is given
by
J (m) = AZm1+···+mN \(Im1 × · · · × ImN ), (2)
where In = Sn\(Zn − ∆n) is the n dimensional lattice without the diagonal points ∆n =
{(z1, . . . , zn) ∈ Zn | zα = zβ for some 1 ≤ α 6= β ≤ n} and identified under the permutationsSn.
The A is a γ × γ symmetric matrix (γ = m1 + · · ·+mN ) with integer entries [5].
In this paper we show that the level set (2) has generally many connected components, and
every such component is written as F (α)ZN\ZN where F (α) is an N ×N matrix determined by
the above F and the symmetry α of the system that depends on the initial conditions. It is also
shown that the time evolutions of the cellular automaton yield straight motions on the torus,
just like the phase flows on the invariant torus generated by first integrals.
The layout of the rest of this paper is as follows. In Section 2 we begin with an abstract
group theoretical setting and present a general result, and one of its specializations called a direct
product model. Here we establish our first main result, Theorem 1. This model is interpreted
as a discrete dynamical system. In Section 3 we construct a specific example of the direct
product model associated with the rigged configurations. We give a review on the periodic box-
ball system in Section 4, and then construct its invariant tori based on the results in previous
sections. Our second main result is Theorem 2. Properties of the cellular automaton that follows
from this result are discussed in Section 5. Two elementary lemmas are given in Appendix A,
and an algorithm for calculating rigged configurations is presented in Appendix B.
2 Construction of a discrete dynamical system
2.1 Group theoretical setting
Let X be a set, S(X) be the group of all bijections from X to itself. Then S(X) acts on X
from the left by σ · x = σ(x) (∀x ∈ X, ∀σ ∈ S(X)). From now on we assume that every group
action is left action and omit the word “from the left”. Given any group G acting on X there
1More precisely, it is not a torus but a set of all integer points on the torus FZN\RN . For the sake of simplicity
we call such a set a torus. Besides, in this paper we write all the quotient sets as left quotient ones.
Level Set Structure of an Integrable Cellular Automaton 3
is an equivalence relation associated with its action. Its equivalence classes are called G-orbits
on X. If there is only one G-orbit, the action of G is called transitive.
The G-orbit containing x ∈ X is denoted G · x, and is called the G-orbit of x. The set of all
G-orbits on X is denoted G\X. Though one can think of G · x either as an element of G\X or
as a subset of X, we shall adopt the latter interpretation and elements of G\X will be written
as [x]G. The map X 3 x 7→ [x]G ∈ G\X is called the canonical map associated with G\X.
There is a transitive action of G on G · x(⊂ X). The following lemma is elementary.
Lemma 1. Let G and H be any groups that act on X commutatively. Then G naturally acts
on H\X. Namely their is a unique action of G on H\X that is commutative with the canonical
map X 3 x 7→ [x]H ∈ H\X.
Proof. Given any p ∈ H\X one can write it as p = [x]H for some x ∈ X. We define Γ :
G×H\X → H\X to be a map given by the relation Γ (g, p) = [g · x]H for all g ∈ G. It is easy
to see that this map is well-defined and yields the desired action of G by g · p = Γ (g, p). 
Let G1 and G2 be subgroups of S(X) that act on X commutatively. Then G1 ∩ G2 is also
a subgroup of S(X) and its action on X is commutative with those of G1 and G2. By Lemma 1
there is a natural action of G1 on G2\X. Let x be any element of X. Then G1 · [x]G2 is a subset
of G2\X where G1 acts on transitively. Similarly G1 · x is a subset of X where G1 and G1 ∩G2
act on commutatively. Hence by Lemma 1 there is a natural action of G1 on (G1 ∩G2)\(G1 ·x).
Proposition 1. Let G1 and G2 be subgroups of S(X) and suppose their actions on X is com-
mutative. Suppose we have (G1 · x) ∩ (G2 · x) ⊂ (G1 ∩ G2) · x for some x ∈ X. Then there is
a bijection between G1 · [x]G2 and (G1 ∩G2)\(G1 · x) that is commutative with the action of G1.
Proof. Let z be any element of G1 · [x]G2 . Then there exists g ∈ G1 such that z = g · [x]G2 .
Define Ξ : G1 · [x]G2 → (G1 ∩G2)\(G1 · x) by Ξ(z) = [g · x]G1∩G2 .
Well-definedness: Suppose there is another g′ ∈ G1 such that z = g′ · [x]G2 . Since the actions
of G1 and G2 are commutative we have [g ·x]G2 = z = [g
′ ·x]G2 . Hence there exists h ∈ G2 such
that h · (g · x) = g′ · x. This implies h · x = (g−1 ◦ g′) · x ∈ (G1 · x) ∩ (G2 · x) ⊂ (G1 ∩ G2) · x.
Hence one can take h as an element of G1 ∩G2. Thus [g′ · x]G1∩G2 = [g · x]G1∩G2 .
Commutativity with G1 action: Let g′ ∈ G1. Then g′ · z = (g′ ◦ g) · [x]G2 . Hence Ξ(g
′ · z) =
[(g′ ◦ g) · x]G1∩G2 = [g
′ · (g · x)]G1∩G2 = g
′ · ([g · x]G1∩G2) = g
′ ·Ξ(z).
Injectivity: Suppose Ξ(z) = Ξ(z′) for z, z′ ∈ G1 · [x]G2 . Then there exist g, g
′ ∈ G1 such that
z = g · [x]G2 and z
′ = g′ · [x]G2 with the property [g · x]G1∩G2 = [g
′ · x]G1∩G2 . Hence there exists
h ∈ G1 ∩G2 such that h · (g · x) = g′ · x. Then g · ([x]G2) = [g · x]G2 = [h · (g · x)]G2 = [g
′ · x]G2 =
g′ · ([x]G2). Hence z = z
′.
Surjectivity: Choose an arbitrary element C of (G1∩G2)\(G1 ·x). Then there exists y ∈ G1 ·x
such that C = [y]G1∩G2 . Since y lies in G1 · x there exists g ∈ G1 such that y = g · x. Let
z = g · [x]G2 ∈ G1 · [x]G2 . Then Ξ(z) = [g · x]G1∩G2 = [y]G1∩G2 = C. 
Among the assumptions of Proposition 1, the condition (G1 · x) ∩ (G2 · x) ⊂ (G1 ∩G2) · x is
rather specific. In the next subsection we construct an example of the triplet (G1, G2, X) that
satisfies this condition for all x ∈ X.
2.2 Direct product model
Let X1, X2 be sets and H1, H2 groups that act on X1, X2 respectively. Choose an arbitrary
subgroup H ′2 of H2. We define
X ′2 = {y ∈ X2 | g · y = y if and only if g ∈ H
′
2}. (3)
4 T. Takagi
In other words X ′2 is the set of all elements of X2 whose stabilizer associated with the H2 action
is H ′2.
In what follows H2 is supposed to be abelian, and we denote the multiplication as a sum
g + h ∈ H2 for any g, h ∈ H2. Then X ′2 is invariant under the action of H2.
Remark 1. Suppose there are several different actions of the group G on the set X. To
distinguish them we write Γ : G × X → X for example to denote a specific action of G
on X. For any such Γ there is a group homomorphism ρΓ : G → S(X) such that the relation
Γ (g, x) = ρΓ (g)·x holds for all g ∈ G, x ∈ X. Such group homomorphisms are called permutation
representations.
Let X = X1 × X ′2. We define Γ1 : H1 × X → X to be a diagonal action of H1 on X
in which its action on X ′2 is trivial. In other words we have Γ1(g, x) = (g · x1, x2) for all
g ∈ H1, x = (x1, x2) ∈ X.
Suppose there exists a map Γ2 : H2 × X → X that has the following property. For all
g ∈ H2, x = (x1, x2) ∈ X we have Γ2(g, x) = (ϕ(g, x1, x2), g · x2) where ϕ : H2 ×X1 ×X ′2 → X1
is a map satisfying the relation ϕ(g + h, x1, x2) = ϕ(h, ϕ(g, x1, x2), g · x2) for all g, h ∈ H2.
Then Γ2 yields an action of H2 on X.
By definition we have Γ2(g, x) = (ϕ(g, x1, x2), x2) for all g ∈ H ′2. This implies that Γ2|H′2×X
yields an action of H ′2 on X in which its action on X
′
2 is trivial.
Let G1 = ρΓ1(H1), G2 = ρΓ2(H2), and G
′
2 = ρΓ2(H
′
2) where ρΓ1 and ρΓ2 are the permutation
representations. Note that G1 and G2 depend on the choice of H ′2.
In what follows the action of H1 on X1 is supposed to be transitive.
Lemma 2. G′2 ⊂ G1 ∩G2.
Proof. By definition we have G′2 ⊂ G2. The inclusion G
′
2 ⊂ G1 holds since the action of G
′
2
on X ′2 is trivial, and the action of G1 on X1 is transitive. 
Lemma 3. The following relation holds
G′2 · x = (G1 ∩G2) · x = (G1 · x) ∩ (G2 · x),
for all x ∈ X = X1 ×X ′2.
Proof. By Lemma 2 we have
G′2 · x ⊂ (G1 ∩G2) · x ⊂ (G1 · x) ∩ (G2 · x),
for all x ∈ X, where the latter inclusion is obvious. The opposite inclusions are proved as follows.
Take any x = (x1, x2) ∈ X. Choose an arbitrary element y of (G1 · x) ∩ (G2 · x). Since y lies in
G2 · x there exists g ∈ H2 such that y = ρΓ2(g) · x = (ϕ(g, x1, x2), g · x2). Then since y lies in
G1 · x this implies g · x2 = x2, forcing g to be an element of H ′2 by (3). Hence y is an element of
G′2 · x. 
In what follows the actions of G1 and G2 on X are supposed to be commutative.
By Proposition 1 and Lemma 3 there is a bijection between G1 · [x]G2 and G1 ∩G2\(G1 · x)
that is commutative with the action of G1 = ρΓ1(H1). Note that Lemma 3 implies G
′
2 = G1∩G2.
Note also that for any x = (x1, x2) ∈ X we have G1 · x = X1 × {x2} ∼= X1 as a subset of X, for
the action of G1 on X1 is transitive and that on X2 is trivial. Thus we have the following.
Theorem 1. Let the sets X1, X ′2, the groups G1, G2, G
′
2, and their actions on the set X =
X1 × X ′2 be defined as above, and x be any element of X. Then there is a bijection between
G1 · [x]G2 and G
′
2\X1 that is commutative with the action of G1.
This is our first main result in this paper.
Level Set Structure of an Integrable Cellular Automaton 5
2.3 Interpretation as a dynamical system
In this subsection we present, without mathematical rigor, an interpretation of the direct product
model as a dynamical system. It is intended to help readers to have some intuitive physical
images on the model.
Consider any completely integrable system with N degrees of freedom in Hamiltonian me-
chanics. There are N independent first integrals. By fixing their values we obtain the level
set, an N -dimensional manifold in the phase space R2N . On the level set there are N mutually
commuting phase flows associated with the first integrals. Note that the time evolution of the
system is one of the phase flows since the Hamiltonian itself is one of the first integrals.
One can think of the triplet (G1, G2, X) in Subsection 2.2 as a discrete analogue of such
a completely integrable system. Let X˜ := X1 × X2 be a non-compact level set and suppose
the groups G1, G2 are acting on X˜ commutatively. We regard the group action of G2 as the
symmetry of the system and assume that it yields a compact (but not necessarily connected)
level set G2\X˜. Then each state of the system is represented by a G2-orbit [x]G2 for some x ∈ X˜.
We regard G1 as the group generated by the mutually commuting phase flows associated with
the first integrals. Then one can think of G1 · [x]G2(⊂ G2\X˜) as a connected component of the
compact level set G2\X˜ containing the state [x]G2 .
Suppose the group G2 acts not only on X˜ but also on X2. Choose an arbitrary subgroup G′2
of G2 and denote by X ′2 the set of all elements of X2 whose stabilizer associated with the G2
action is G′2. Let x be any element of X = X1 ×X
′
2. Now the model in Subsection 2.2 can be
interpreted as follows. There is a bijection between the connected component of the level set
G1 · [x]G2 and the quotient set G
′
2\X1 that is commutative with the phase flows of the system.
In particular the time evolution of the system is commutative with this bijection.
Consider the completely integrable system in Hamiltonian mechanics again. Suppose the
level set is compact and connected. Then by Arnold–Liouville theorem it must be diffeomorphic
to an N -dimensional torus [1]. It is called an invariant torus. In the following sections we
construct a direct product model with X1 = ZN and G′2 being a sub-lattice of Z
N which acts
on X1 by left translation. Now the quotient set G′2\X1 is, roughly speaking, a discrete analogue
of invariant torus.
3 A dynamical system on rigged configurations
3.1 Extended rigged configurations
The rigged configuration is an ingenious device utilized in combinatorial Bethe ansatz [9, 10].
We construct an example of the direct product model associated with the rigged configurations.
The result of this section will be used in Subsection 4.4.
We introduce a pair of sets X1 and X2. Choose an arbitrary positive integer N and define
X1 = ZN . For any pair of positive integers m, p we define
Λ(m, p) = {(λi)i∈Z | λi ∈ Z, λ1 = 0, λi ≤ λi+1, λi+m = λi + p for all i}. (4)
Given any positive integer sequences (mj)1≤j≤N , (pj)1≤j≤N we define X2 =
∏N
j=1 Λ(mj , pj).
Each element of X2 is written, for instance, as λ = (λ(j))1≤j≤N with λ(j) ∈ Λ(mj , pj) or
λ = (λ(j)i )i∈Z,1≤j≤N .
Example 1. Let (m1,m2,m3) = (3, 2, 1) and (p1, p2, p3) = (12, 6, 4). Each element of the set
X2 = Λ(3, 12)×Λ(2, 6)×Λ(1, 4) is written as λ = (λ(1), λ(2), λ(3)). It is labeled by three integers
a = λ(1)2 , b = λ
(1)
3 and c = λ
(2)
2 satisfying the conditions 0 ≤ a ≤ b ≤ 12 and 0 ≤ c ≤ 6. Note
that λ(3) = (λ(3)i )i∈Z has a unique element λ
(3)
i = 4(i− 1).
6 T. Takagi
The set X˜ = X1 × X2 with the above X1, X2 is regarded as the non-compact level set
considered in Subsection 2.3. It will be identified with the set of extended rigged configurations
in Subsection 4.3 under a certain condition imposed on the values of mj and pj . For the time
being we ignore this condition and call X˜ itself the set of extended rigged configurations.
We introduce a pair of abelian groups H1 and H2. Suppose H1 acts on X1 by
Γ : H1 ×X1 → X1, (g,ω) 7→ Γ (g,ω) = ω + ψΓ (g),
where ψΓ : H1 → X1 is a map common to every ω ∈ X1. This map must be linear, i.e. for all
g, h ∈ H1 we have ψΓ (g + h) = ψΓ (g) + ψΓ (h). We assume that this action is transitive, i.e. for
any ω,ω′ ∈ X1 there exists g ∈ H1 such that Γ (g,ω) = ω′. An example of such a map will
appear in the next section, just above Lemma 6.
Remark 2. Since X1 = ZN , any sub-lattice of X1 can be thought of as an abelian group which
acts on X1 by translation. As a sub-lattice of X1 we can take X1 itself, which leads to the
above H1 and its action on X1.
Suppose H2 is a free abelian group with generators s1, . . . , sN . We define Υ : H2 ×X2 → X2
to be an action of H2 on X2 by
Υ(g,λ) =
(
λ(j)nj+i − λ
(j)
nj+1
)
i∈Z,1≤j≤N , (5)
for each g =
∑N
j=1 njsj ∈ H2 and λ = (λ
(j)
i )i∈Z,1≤j≤N ∈ X2.
Example 2. Consider the X2 in Example 1. Let λ = Υ(g,λ) for g = n1s1 + n2s2 + n3s3 ∈ H2.
Then λ =
(
λ
(1)
, λ
(2)
, λ
(3))
is specified by three integers a = λ
(1)
2 , b = λ
(1)
3 and c = λ
(2)
2 as
(a, b) =



(a, b) n1 ≡ 0 (mod 3),
(b− a, 12− a) n1 ≡ 1 (mod 3),
(12− b, 12− b+ a) n1 ≡ 2 (mod 3),
c =
{
c n2 ≡ 0 (mod 2),
6− c n2 ≡ 1 (mod 2).
Here a, b, c are the labels for λ in Example 1.
3.2 Cyclic group structures
Let ρΥ : H2 → S(X2) be the permutation representation for the action of Υ in the previous
subsection. Then ρΥ(H2) is isomorphic to Cm1 ×· · ·×CmN , where Cm is an order m cyclic group.
This in particular determines an action of Cm on Λ(m, p). The following facts are well known in
the theory of cyclic groups.
Proposition 2. Every subgroup of a cyclic group is a cyclic group.
Proposition 3. Let m be a positive integer and n be a divisor of m. Then there exists a unique
subgroup of Cm that is isomorphic to Cn.
Let α be a common divisor of m and p. As a subset of Λ(m, p) we define
Λ(α)(m, p) = {λ ∈ Λ(m/α, p/α) | λ /∈ Λ(m/α′, p/α′) for every common divisorα′ > α}. (6)
In other words Λ(α)(m, p) is the set of all elements of Λ(m, p) whose stabilizer associated with
the action of Cm is isomorphic to Cα. Now we have the decomposition Λ(m, p) =
⊔
α Λ
(α)(m, p)
where α runs over every common divisor of m and p.
Choose a sequence α = (αj)1≤j≤N with each αj being a common divisor of mj and pj . Let
H(α)2 be a group generated by (m1/α1)s1, . . . , (mN/αN )sN . It is a subgroup of H2 whose
Level Set Structure of an Integrable Cellular Automaton 7
image ρΥ(H
(α)
2 ) by the permutation representation is isomorphic to Cα1 × · · · × CαN . Let
X(α)2 =
∏N
j=1 Λ
(αj)(mj , pj). In other words X
(α)
2 is the set of all elements of X2 whose sta-
bilizer associated with the H2 action is H
(α)
2 .
Example 3. Consider the X2 in Example 1. We have Λ(3, 12) = Λ(1)(3, 12) unionsq Λ(3)(3, 12),
Λ(2, 6) = Λ(1)(2, 6) unionsq Λ(2)(2, 6) and Λ(1, 4) = Λ(1)(1, 4). If we set α = (α1, α2, α3) = (3, 1, 1),
then (a, b) = (4, 8) and c 6= 3 for any λ ∈ X(α)2 . It follows from Example 2 that the set of all
g ∈ H2 satisfying Υ(g,λ) = λ is H
(α)
2 = {g = n1s1 + 2n2s2 + n3s3 |n1, n2, n3 ∈ Z}.
Since H2 is abelian, X
(α)
2 (⊂ X2) is invariant under the action of H2. Let
X(α) = X1 ×X
(α)
2 . (7)
The X(α)2 here corresponds to the X
′
2, and the X
(α) to the X in Subsection 2.2. The set
X˜ = X1 ×X2 is decomposed as X˜ =
⊔
αX
(α) where each αj runs over every common divisor
of mj and pj .
3.3 Group actions on the set of rigged configurations
We define a pair of commutative actions of H1 and H2 on X˜ = X1 ×X2. As in Subsection 2.2,
let Γ1 : H1× X˜ → X˜ be a diagonal action of H1 on X˜ in which its action on X2 is trivial, i.e. for
each f ∈ H1 and x = (ω,λ) ∈ X˜ we set Γ1(f, x) = (ω+ψΓ (f),λ). Let Γ2 : H2 × X˜ → X˜ be an
action of H2 on X˜ which is defined as follows.
Fix an arbitrary set of N2 integers (Bj,k)1≤j,k≤N ∈ ZN
2
. In the next section we take Bj,k to be
those given in (12). For each g ∈ H2 and x = (ω,λ) ∈ X˜ we set Γ2(g, x) = (ϕ(g,ω,λ),Υ(g,λ))
where Υ(g,λ) is given by (5) and ϕ : H2 ×X1 ×X2 → X1 is a map defined by
ϕ(g,ω,λ) = ω +
(
λ(j)nj+1 +
N∑
k=1
Bj,knk
)
1≤j≤N
, (8)
for each g =
∑N
k=1 nksk ∈ H2, ω ∈ X1 and λ = (λ
(j)
i )i∈Z,1≤j≤N ∈ X2. It is easy to see
that the map Γ2 indeed yields an action of H2 on X˜, since the relation ϕ(g + h,ω,λ) =
ϕ(h, ϕ(g,ω,λ),Υ(g,λ)) holds for all g, h ∈ H2. It is also easy to see that H1 and H2 act
on X˜ commutatively by Γ1 and Γ2.
Example 4. Consider the X2 in Example 1. For g = n1s1+n2s2+n3s3 ∈ H2 and x = (ω,λ) ∈
X˜ we write Γ2(g, x) = (ω,λ) ∈ X˜. Here λ = Υ(g,λ) is the one given in Example 2, and
ω = ϕ(g,ω,λ) is written as
ϕ(g,ω,λ) = ω +
(
µj +
3∑
k=1
Bj,knk
)
1≤j≤3
.
Here we set
µ1 =



12l1 n1 = 3l1,
12l1 + a n1 = 3l1 + 1,
12l1 + b n1 = 3l1 + 2,
µ2 =
{
6l2 n2 = 2l2,
6l2 + c n2 = 2l2 + 1,
for any l1, l2 ∈ Z, and µ3 = 4n3. The a, b, c are the labels for λ in Example 1.
8 T. Takagi
By definition the set X(α)(⊂ X˜) is invariant under the action of H1. It is also invariant
under H2. Thus by restricting their domains from X˜ to X(α), Γ1 and Γ2 yield their actions
on X(α). In what follows we denote them by the same symbols Γ1 and Γ2 for simplicity.
We define G1 = ρΓ1(H1), G2 = ρΓ2(H2), and G
(α)
2 = ρΓ2(H
(α)
2 ) to be subgroups of S(X
(α))
where ρΓ1 and ρΓ2 are the permutation representations.
Lemma 4. Consider the action of G(α)2 on X
(α) = X1 ×X
(α)
2 .
(i) It is trivial on the X(α)2 -part.
(ii) On the X1-part, G
(α)
2 acts as a sub-lattice of X1 by translation.
(iii) The action on the X1-part is independent of the X
(α)
2 -part.
Proof. Since the G(α)2 corresponds to the G
′
2 in Subsection 2.2, we have G
(α)
2 = G1 ∩ G2
by Lemma 3. In particular G(α)2 is a subgroup of G1, hence follow items (i) and (ii). Con-
sider item (iii). The X1-part is given by the map ϕ in (8). We show that for each g =
∑N
k=1 nk(mk/αk)sk ∈ H
(α)
2 and ω ∈ X1 the image ϕ(g,ω,λ) of the map ϕ is common to all
λ ∈ X(α)2 . In fact for any λ ∈ X2 we have
ϕ(g,ω,λ) = ω +
(
λ(j)(mj/αj)nj+1 +
N∑
k=1
(mk/αk)Bj,knk
)
1≤j≤N
. (9)
Note that if λ lies in X(α)2 then we have λ
(j)
(mj/αj)nj+1
= (pj/αj)nj from (4) and (6). Hence
ϕ(g,ω,λ) is independent of the choice of λ ∈ X(α)2 . 
We define F (α) = (F (α)j,k )1≤j,k≤N to be an N ×N matrix whose elements are given by
F (α)j,k = (δj,kpk +Bj,kmk)/αk, (10)
and regard ω, n = t(n1, . . . , nN ) and ϕ(g,ω,λ) as column vectors. Then (9) is written as
ϕ(g,ω,λ) = ω + F (α)n when λ lies in X(α)2 . By Lemma 4 we can think of G
(α)
2 as a subgroup
of S(X1) rather than that of S(X(α)). In this sense the group G
(α)
2 is isomorphic to the lattice
F (α)ZN which acts on X1 = ZN by translation.
Thus Theorem 1 for the present construction with Lemma 7 (to appear in the appendix) is
now stated as follows.
Proposition 4. Let the set X(α), the matrix F (α), the groups H1, H2 and their actions on X(α)
be def ined as above, and x be any element of X(α). Then there is a bijection between H1 · [x]H2
and F (α)ZN\ZN that is commutative with the action of H1.
The set F (α)ZN\ZN becomes compact (and is a torus) if and only if detF (α) 6= 0. A way to
achieve this condition is given as follows. Let L be an integer satisfying L ≥ 2
∑N
k=1 kmk and
set
pj = L− 2
N∑
k=1
min(j, k)mk, (11)
Bj,k = 2min(j, k). (12)
Then we have L > p1 > p2 > · · · > pN = L− 2
∑N
k=1 kmk ≥ 0 and
detF (α) = Lp1p2 · · · pN−1/(α1 · · ·αN ) > 0.
Note that pN = 0 is allowed here. In this case we have Λ(mN , pN ) = Λ(mN )(mN , pN ) which has
a unique element (0)i∈Z.
Level Set Structure of an Integrable Cellular Automaton 9
Example 5. The pj and mj in Example 1 satisfy the relation (11) with L = 24. We set
α = (α1, α2, α3) = (3, 1, 1) as in Example 3. By taking Bj,k as in (12) we have
F (α) =


p1/α1 0 0
0 p2/α2 0
0 0 p3/α3

+


2 2 2
2 4 4
2 4 6




m1/α1 0 0
0 m2/α2 0
0 0 m3/α3


=


6 4 2
2 14 4
2 8 10

 ,
and detF (α) = 576. For instance, let x = (ω,λ) be the element of X(α) specified by ω =
(0, 0, 0) ∈ X1 = Z3, and λ ∈ X
(α)
2 that is labeled by (a, b, c) = (4, 8, 1). Then there is a bijection
between H1 · [x]H2 and the three dimensional torus F
(α)Z3\Z3 that is commutative with the
action of H1.
Remark 3. Given any positive integer s, choose an increasing sequence of positive integers
j1, . . . , js and define H to be the set H = {j1, . . . , js}. A generalization of the arguments in this
section is given by replacing the positive integer sequence (mj)1≤j≤N by (mj)j∈H, which fits to
the case in [5].
All the results in this paper can be extended to this generalized setting: We set X1 = Zs,
and H2 to be a free abelian group with generators {sj}j∈H. Given any positive integer sequence
(pj)j∈H we set X2 =
∏
j∈H Λ(mj , pj). Proposition 4 becomes a claim on the bijection between
H1 · [x]H2 and F
(α)Zs\Zs where the F (α) = (F (α)j,k )j,k∈H is now an s × s matrix. The other
definitions and statements can be modified similarly.
4 A one-dimensional integrable cellular automaton
4.1 The periodic box-ball system
The periodic box-ball system (pBBS) is a one-dimensional cellular automaton with periodic
boundary conditions. We give a brief review on this system based on [5] from here to Subsec-
tion 4.3. Let L be a positive integer and p be a sequence of letters 1 and 2 under the conditions
#(1) ≥ #(2) and #(1) + #(2) = L. Such sequences are called paths of positive weight and of
length L. Denote by P the set of all such paths. We can define a commuting family of time
evolutions Tk (k = 1, 2, . . .) acting on P. It is a collection of update procedures for the cellular
automaton. In this paper we write nTk for an n times repeated application of Tk instead of Tnk ,
regarding Tks as generators of an abelian group (see Subsection 4.3).
The action of T1 is given by a cyclic shift by one digit to the right. The definition of Tk for
the other k’s is given by means of the crystal basis of the quantized envelope algebra [11] and is
available in Section 2.2 of [5]. Here we review it shortly.
Let Bk be the set of one-row semistandard tableaux of length k with entries 1 and 2. For
instance, B1 = {1, 2}, B2 = {11, 12, 22} and B3 = {111, 112, 122, 222}. The combinatorial R
map R : Bk ×B1 → B1 ×Bk is defined as follows. If we depict the relation R(x, y) = (y˜, x˜) by
x x˜
y
y˜
then the definition of R is given by the following diagrams:
10 T. Takagi
1k
︷ ︸︸ ︷
1 · · · · · · 1
k
︷ ︸︸ ︷
1 · · · · · · 1
1
2k
︷ ︸︸ ︷
2 · · · · · · 2
k
︷ ︸︸ ︷
2 · · · · · · 2
2
1k−a
︷ ︸︸ ︷
1 · · · 1
a
︷ ︸︸ ︷
2 · · · 2
k−a+1
︷ ︸︸ ︷
1 · · · 1
a−1
︷ ︸︸ ︷
2 · · · 2
2
(0<a≤k)
2k−a
︷ ︸︸ ︷
1 · · · 1
a
︷ ︸︸ ︷
2 · · · 2
k−a−1
︷ ︸︸ ︷
1 · · · 1
a+1
︷ ︸︸ ︷
2 · · · 2
1
(0≤a<k)
By repeated use of this R we define the following map
Bk × (B1 × · · · ×B1) → (B1 × · · · ×B1)×Bk,
v × (b1 × · · · × bL) 7→ (b
′
1 × · · · × b
′
L)× v
′. (13)
Example 6. Set k = 3, L = 13, v = 122 and b1 . . . b13 = 1122211112212. (We omit the
symbol × here and in what follows.) Then we have b′1 . . . b
′
13 = 2211122211121 and v
′ = 122. It
is verified by the following diagram
1 1 2 2 2 1 1 1 1 2 2 1 2
2 2 1 1 1 2 2 2 1 1 1 2 1
122 112 111 112 122 222 122 112 111 111 112 122 112 122
In this example we have v = v′. In fact one can always find an element of Bk with this
property.
Proposition 5 ([5]). Given any b1× · · ·× bL ∈ P ⊂ B
×L
1 , let v0 ∈ Bk be the one defined in the
same way as (13) by
k
︷ ︸︸ ︷
1 . . . 1×(b1 × · · · × bL) 7→ (b
′′
1 × · · · × b
′′
L)× v0.
Then we have v = v′ in (13) when we adopt this v0 as the v there.
By this choice of v, we define the time evolution Tk by Tk(b1 . . . bL) = b′1 . . . b
′
L.
Example 7. We have T3(1122211112212) = 2211122211121 by Example 6.
Remark 4. Given any initial condition, the actions of Tks for sufficiently large k’s are common
to them and determine a unique time evolution. The original study of pBBS [2, 3] considers
only this time evolution which we denote by T∞. In the context of the dynamical system in
Subsection 2.3, we can regard the T∞ as the unique time evolution in this dynamical system,
and the other Tks can be thought of as the phase flows associated with the other first integrals.
Here we give an example of the time evolution of this cellular automaton. (The case of
L = 31, and evolved by T4 = T∞.)
t = 0 : 2 2 2 2 1 1 1 2 1 1 2 2 1 1 1 1 1 2 2 2 1 1 1 1 1 1 1 1 1 1 1
t = 1 : 1 1 1 1 2 2 2 1 2 2 1 1 2 2 1 1 1 1 1 1 2 2 2 1 1 1 1 1 1 1 1
t = 2 : 1 1 1 1 1 1 1 2 1 1 2 2 1 1 2 2 2 2 1 1 1 1 1 2 2 2 1 1 1 1 1
t = 3 : 1 1 1 1 1 1 1 1 2 1 1 1 2 2 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 1 1
t = 4 : 2 1 1 1 1 1 1 1 1 2 1 1 1 1 2 2 1 1 1 1 1 1 2 2 2 2 1 1 1 2 2
t = 5 : 1 2 2 2 2 1 1 1 1 1 2 1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 2 2 2 1 1
Level Set Structure of an Integrable Cellular Automaton 11
t = 6 : 2 1 1 1 1 2 2 2 2 1 1 2 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 2 2
t = 7 : 1 2 2 2 1 1 1 1 1 2 2 1 2 2 2 1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1
t = 8 : 1 1 1 1 2 2 2 1 1 1 1 2 1 1 1 2 2 2 2 1 1 1 2 2 1 1 1 1 1 1 1
t = 9 : 1 1 1 1 1 1 1 2 2 2 1 1 2 1 1 1 1 1 1 2 2 2 1 1 2 2 2 1 1 1 1
If we denote by p ∈ P the sequence for t = 0 then the sequence for t = n stands for
(nT4) · p ∈ P.
When sufficiently separated from the other 2’s, one can think of a consecutive sequence of
2’s of length k as a soliton of amplitude k. By an appropriate definition one can say that the
number of solitons conserves for each amplitude. In this example there are four solitons of
distinct amplitudes (1, 2, 3 and 4) in every time step. For instance, in the state for t = 9 in the
above example, the sequence 2 2 2 1 1 2 2 2 should be interpreted as an intermediate stage of
the collision of two solitons of amplitudes 4 and 2.
4.2 Soliton content and rigged configurations
Let P+ be the set of all ballot sequences in P: A path p = b1b2 . . . bL is called a ballot sequence
if and only if the number of 1’s in the prefix b1 . . . bk is at least as large as the number of 2’s in
that prefix for every k. For any p ∈ P there exist an integer d and a sequence p+ ∈ P+ such
that p = (dT1) · p+ where T1 is the right cyclic shift operator.
Given any p+ ∈ P+, a bijective map φ due to Kerov–Kirillov–Reshetikhin [9, 10] yields
the following data (H,m,J). Here H = {j1, . . . , js} is a set of positive integers satisfying the
condition j1 < · · · < js, and m = (mj1 , . . . ,mjs) is an array of positive integers. The J =(
(J (j1)i )1≤i≤mj1 , . . . , (J
(js)
i )1≤i≤mjs
)
is an array of partitions: Each (J (j)i )1≤i≤mj is a partition of
non-negative integers into at most mj parts in increasing order, with largest part ≤ pj where
pj = L−2
∑
k∈H min(j, k)mk. In symbols it is written as φ(p+) = (m,J). The collection (m,J)
is called a rigged configuration with configuration m and riggings J , and pj are called vacancy
numbers. The set of all rigged configurations with configuration m is denoted Rig(m). An
algorithm to obtain the data (H,m,J) is presented in Appendix B.
Suppose there are two possible ways to write p as p = (dT1) · p+ = (d′T1) · p′+. Then it can
be shown that one obtains a common configuration m by φ(p+) = (m,J) and φ(p′+) = (m,J
′)
with some J , J ′. Hence for each p ∈ P one can label it with a specific m, and we say that such
a path has soliton content m. The set P is decomposed as P =
⊔
m P(m) where P(m) is the
set of all paths of soliton content m. It can be shown that each P(m) is invariant under the
action of Tk for all k.
Example 8. Consider the paths
p = p+ = 121122111212211222121111 and p
′
+ = 111212211222121111121122,
in P+ with L = 24 which are related by p = (6T1) · p′+. By the bijective map φ we obtain
φ(p) = (m,J) and φ(p′+) = (m,J
′) with
m = (m1,m2,m3) = (3, 2, 1),
J =
((
J (1)1 , J
(1)
2 , J
(1)
3
)
,
(
J (2)1 , J
(2)
2
)
,
(
J (3)1
))
= ((0, 4, 8), (0, 1), (0)),
J ′ =
((
J ′(1)1 , J
′(1)
2 , J
′(1)
3
)
,
(
J ′(2)1 , J
′(2)
2
)
,
(
J ′(3)1
))
= ((2, 6, 10), (1, 6), (0)).
4.3 Direct scattering transform
By means of the map φ one can construct a bijection between the set of all states in the cellular
automaton and the set of extended rigged configurations divided by a group action. The map
12 T. Takagi
from the former to the latter is called the direct scattering transform (and its inverse is referred to
as the inverse scattering transform), named after a similar transform in the theory of integrable
non-linear evolution equations [12].
For the sake of simplicity we assume H = {1, . . . , N} in what follows. Then we have m =
(mj)1≤j≤N , J = ((J
(j)
i )1≤i≤mj )1≤j≤N and the vacancy numbers are given by (11). See Remark 3
for the recipe to recover the original setting for general H.
We define
J (m, p) = {(Ji)i∈Z | Ji ∈ Z, Ji ≤ Ji+1, Ji+m = Ji + p for all i}, (14)
and J (m) =
∏N
j=1 J (mj , pj). There is a map
ι : Rig(m) −→ J (m)
((J (j)i )1≤i≤mj )1≤j≤N 7→ (J
(j)
i )i∈Z,1≤j≤N
(15)
where the infinite sequence (J (j)i )i∈Z ∈ J (mj , pj) is the one that extends (J
(j)
i )1≤i≤mj quasi-
periodically as J (j)i+mj = J
(j)
i + pj for all i ∈ Z. In this article we call the elements of J (m)
extended rigged configurations. The relation between J (m) and the set X˜ in Subsection 3.1
will be explained in the next subsection.
Let A be a free abelian group with generators σ1, . . . , σN . We define its action on the
set J (m). Given any g =
∑N
k=1 nkσk ∈ A and J = (J
(j)
i )i∈Z,1≤j≤N ∈ J (m) we set
g · J =
(
J (j)i+nj + 2
N∑
k=1
nk min(j, k)
)
i∈Z,1≤j≤N
.
Recall the family of time evolutions Tk (k = 1, 2, . . .) introduced in Subsection 4.1. Let T be
the free abelian group generated by T1, . . . , TN which acts on P(m). We define its actions on
the set J (m). Given any h =
∑N
k=1 nkTk ∈ T and J = (J
(j)
i )i∈Z,1≤j≤N ∈ J (m) we set
h · J =
(
J (j)i +
N∑
k=1
nk min(j, k)
)
i∈Z,1≤j≤N
.
The direct scattering transform Φ ((3.15) in [5]) is given as follows:
Φ : P(m) −→ Z× P+(m) −→ J (m) −→ A\J (m)
p 7−→ (d, p+) 7−→ ι(J) + d 7−→ [ι(J) + d]A
(16)
Here the second map is given by φ together with the map ι (15), where for any d ∈ Z and
J = ((J (j)i )1≤i≤mj )1≤j≤N ∈ Rig(m) we write ι(J) + d = (J
(j)
i + d)i∈Z,1≤j≤N ∈ J (m). As in
Subsection 4.2, suppose there are two possible ways to write p as p = (dT1) · p+ = (d′T1) · p′+.
Then one generally has ι(J ′)+d′ 6= ι(J)+d in J (m). However it can be shown that the relation
[ι(J ′) + d′]A = [ι(J) + d]A holds, permitting the map Φ to be well-defined.
Example 9. Let J and J ′ be the ones in Example 8. Then we have (σ1+σ2)·(ι(J)+d) = ι(J ′)+
d′ with d = 0, d′ = 6. Hence for the p and m in that example, Φ(p) = [ι(J)+d]A = [ι(J ′)+d′]A.
It is easy to see that the actions of A and T on J (m) is commutative. Hence by Lemma 1
there is a natural action of T on A\J (m).
The main result of [5] is as follows.
Level Set Structure of an Integrable Cellular Automaton 13
Proposition 6 ([5, Theorem 3.12]). The map Φ is a bijection between P(m) and A\J (m)
that is commutative with the action of T .
In particular one has |P(m)| = |A\J (m)|. This quantity is written as Ω(m) in (1) where
the N × N matrix F is set to be the F (α) in (10) with (11), (12) and α = (1, . . . , 1). The
level set itself is written as J (m):= A\J (m) in (2) where the γ × γ matrix A is defined by
A = (Ajα,kβ)1≤j,k≤N,1≤α≤mj ,1≤β≤mk with Ajα,kβ = δj,kδα,β(pj +mj) + 2min(j, k)− δj,k.
4.4 Construction of the invariant tori
Let α be a common divisor of m and p. As a subset of J (m, p) we define
J
(α)
(m, p) = {J ∈ J (m/α, p/α) | J /∈ J (m/α′, p/α′) for every common divisorα′ > α}.
Choose a sequence α = (αj)1≤j≤N with each αj being a common divisor ofmj and pj . We define
J
(α)
(m) =
∏N
j=1 J
(αj)(mj , pj). This α represents the symmetry of the system that depends
on the initial conditions. As a subset of J (m) it is invariant under the actions of A and T . Let
P(α)(m) = Φ−1(J
(α)
(m)). As a corollary of Proposition 6 we have the following.
Corollary 1. The map Φ is a bijection between P(α)(m) and A\J
(α)
(m) that is commutative
with the action of T .
Let X(α) = X1×X
(α)
2 be the set introduced in (7). In what follows we identify the group H2
in Subsection 3.1 with the group A by si = σi, and set pj and Bj,k as in (11) and (12).
Lemma 5. There is a bijection between J
(α)
(m) and X(α) that is commutative with the action
of A.
Proof. For each J =
(
J (j)i
)
i∈Z,1≤j≤N ∈ J
(α)
(m) let
ω =
(
J (j)1
)
1≤j≤N , λ =
(
J (j)i − J
(j)
1
)
i∈Z,1≤j≤N .
Then the map J
(α)
(m) 3 J 7→ (ω,λ) ∈ X(α) yields the desired bijection. 
By this lemma we can identify the set X˜ = X1 ×X2 in Subsection 3.1 with the set J (m).
Example 10. Let J , J ′, d, d′ be the ones in Examples 8 and 9. Then ι(J) + d and ι(J ′) + d′
are elements of J
(α)
(m) with m in those examples, and α = (α1, α2, α3) = (3, 1, 1). The
above map sends ι(J) + d to the (ω,λ) ∈ X(α) in Example 5. Write the image of ι(J ′) + d′ as
(ω′,λ′) ∈ X(α). Then ω′ = (8, 7, 6) ∈ X1 = Z3, and λ′ is the one labeled by (a, b, c) = (4, 8, 5).
By using the formula in Example 4 one can show that (s1 + s2) · (ω,λ) = (ω′,λ′). Compared
with Example 9 this shows the commutativity of the action of A with the bijection in Lemma 5.
By Lemmas 5 and 8 (to appear in the appendix) there is a natural action of T on X(α) that
is commutative with the action of A. Also one has a bijection between A\J
(α)
(m) and A\X(α)
that is commutative with the action of T . Now by Corollary 1 we have the following.
Proposition 7. There is a bijection between P(α)(m) and A\X(α) that is commutative with
the action of T .
We denote by Ψ the map representing this bijection. Then for any p ∈ P(α)(m) there exists
some x ∈ X(α) such that Ψ(p) = [x]A. Now as a corollary of Proposition 7 we have the following.
14 T. Takagi
Proposition 8. Given p ∈ P(α)(m) and x ∈ X(α) as above, there is a bijection between
T · p(⊂ P(α)(m)) and T · [x]A(⊂ A\X(α)) that is commutative with the action of T .
The action of the abelian group T on the set X(α) = X1×X
(α)
2 keeps X
(α)
2 untouched. Thus
this action is essentially defined on the setX1 = ZN . By Lemma 8 it is uniquely determined from
the action of T on the set P(m) in Subsection 4.3. An explicit description of this action is as
follows. For each h =
∑N
k=1 nkTk ∈ T and ω = (ω
(j))1≤j≤N ∈ X1 we set h ·ω = ω+
∑N
k=1 nkhk
where hk = (min(j, k))1≤j≤N ∈ X1.
Lemma 6. The action of the group T on the set X1 = ZN is transitive.
Proof. Let ω, ω′ be any two elements of ZN , thought of as column vectors. We define the
N ×N matrix M = (h1, . . . ,hN ). It is easy to see that detM = 1. Hence by n = M−1(ω′ −ω)
we obtain a column vector n = t(n1, . . . , nN ) with integer entries. Then we have ω′ = (n1T1 +
n2T2 + · · ·+ nNTN ) · ω. 
Remark 5. For the generalized case in Remark 3 we define T to be the free abelian group
generated by T1, Tj1+1, . . . , Tjs−1+1. Then one can show that the action of T on the set X1 = Z
s
is transitive in the same way as above.
By Lemma 6 one can adopt T as the abelian group H1 in Subsection 3.1. Given any p ∈
P(α)(m), a path of soliton content m and with the symmetry α, one can obtain the matrix F (α)
by (10), (11) and (12). By Propositions 4 and 8 we finally obtain our second main result.
Theorem 2. There is a bijection between T · p and F (α)ZN\ZN that is commutative with the
action of T .
As we have shown at the end of Subsection 3.3 the F (α)ZN\ZN is an N -dimensional discrete
torus. By the considerations given just above Lemma 6 one also knows that each time evolu-
tion Tk yields a straight motion on the torus with the “velocity” vector hk = (min(j, k))1≤j≤N .
Example 11. For p = 121122111212211222121111 and
F (α) =


6 4 2
2 14 4
2 8 10

 ,
there is a bijection between T ·p and F (α)Z3\Z3. This is a consequence of Examples 5, 8 and 10.
5 Periods and the level set structure
5.1 Dynamical periods
Given p ∈ P(α)(m), a path of soliton content m and with the symmetry α, there is a smallest
positive integer nk such that (nkTk) · p = p for each k. It is called the dynamical period of p
associated with the time evolution Tk. Since the time evolutions are mapped to straight motions
on the torus F (α)ZN\ZN , it is easy to obtain an explicit formula for nk.
We fix a bijection Ψ̂ from T · p to F (α)ZN\ZN whose existence was ensured by Theorem 2.
Then since p lies in T · p there exists ω ∈ ZN such that Ψ̂(p) = [ω]F (α)ZN . By the definition of
the action of T on F (α)ZN\ZN we have
(nkTk) · Ψ̂(p) = [(nkTk) · ω]F (α)ZN = [ω + nkhk]F (α)ZN .
Level Set Structure of an Integrable Cellular Automaton 15
On the other hand since Ψ̂ is commutative with the action of T we have
(nkTk) · Ψ̂(p) = Ψ̂((nkTk) · p) = Ψ̂(p) = [ω]F (α)ZN .
Thus nkhk must lie in the F (α)ZN -orbit of 0, implying that nk is defined as the smallest positive
integer satisfying nkhk ∈ F (α)ZN . This condition is essentially the same one given in (4.32)
of [5] which yields an explicit formula for this quantity ((4.26) of [5]). Note that our formulation
uses no Bethe ansatz considerations to obtain this result.
Example 12. For p = 121122111212211222121111 one can observe the dynamical periods
n1 = 24, n2 = 48 and n3 = 72 by directly applying the time evolutions in Subsection 4.1. By
using the above considerations they are also calculated as
nk = L.C.M.
(
detF (α)
detF (α)[1]
,
detF (α)
detF (α)[2]
,
detF (α)
detF (α)[3]
)
,
where F (α) is the one in Example 11 and F (α)[i] is the matrix obtained from F (α) by replacing
its i-th column by hk. Here L.C.M. stands for the least common multiple. For instance, we have
n3 = L.C.M.
(
24,
72
5
,
72
17
)
= 72.
5.2 Decomposition of the level set
Each element λ = (λi)i∈Z of the set Λ(m, p) is specified by a non-decreasing sequence of integers
(0 ≤)λ2 ≤ λ3 ≤ · · · ≤ λm(≤ p), or a partition (λm, . . . , λ2). Hence the cardinality of Λ(m, p)
is given by the binomial coefficient |Λ(m, p)| =
(p+m−1
m−1
)
. Recall the decomposition of the set
Λ(m, p) =
⊔
α Λ
(α)(m, p), where α runs over every common divisor of m and p. Thus we have
the relation
(
p+m− 1
m− 1
)
=
∑
α
|Λ(α)(m, p)|.
The formula (1) for the cardinality of the whole level set with soliton content m is now written
as
Ω(m) = (detF )
∏
1≤j≤N
1
mj
(
pj +mj − 1
mj − 1
)
=
∑
α1
· · ·
∑
αN
(
detF (α)
) ∏
1≤j≤N
|Λ(αj)(mj , pj)|
mj/αj
. (17)
This expression for the volume formula shows the decomposition of the level set (2) into the
invariant tori: For each α = (αj)1≤j≤N we have the tori F (α)ZN\ZN with the multiplicity
∏
1≤j≤N
|Λ(αj)(mj ,pj)|
mj/αj
. See [13, Lemmas 3.1 and 3.2] for a proof of this statement. While the
smallest torus is given by α = (αj)1≤j≤N with every αj being the greatest common divisor of mj
and pj , the largest torus is given by α = (1)1≤j≤N when pN > 0, or α = (1, . . . , 1,mN ) when
pN = 0.
One can check that this expression for the multiplicity is indeed an integer. Let s be the
generator of the cyclic group Cm that acts on Λ(α)(m, p). For each λ ∈ Λ(α)(m, p) the m/α
elements (ks) · λ (0 ≤ k ≤ m/α− 1) are all distinct and hence |Λ(α)(m, p)| is divisible by m/α.
An expression for the quantity |Λ(α)(m, p)| is given as follows. Let µ(n) be the Mo¨bius
function of number theory [14]; that is, µ(1) = 1, µ(n) = 0 if n is divisible by the square of an
16 T. Takagi
integer greater than one, and µ(n) = (−1)r if n is the product of r distinct primes. Then we
have
|Λ(α)(m, p)| =
∑
β
µ(β/α)
(p+m
β − 1
m
β − 1
)
, (18)
where β runs over every common divisor of m and p that is a multiple of α.
Example 13. For L = 24 and m = (m1,m2,m3) = (3, 2, 1) we have (p1, p2, p3) = (12, 6, 4).
The former expression of (17) gives
Ω(m) = (detF )
1
m1
(
p1 +m1 − 1
m1 − 1
)
1
m2
(
p2 +m2 − 1
m2 − 1
)
1
m3
(
p3 +m3 − 1
m3 − 1
)
= 1728 ·
1
3
(
14
2
)
·
1
2
(
7
1
)
= 183456,
where F = F (α1) is given below. Let α1 = (1, 1, 1), α2 = (1, 2, 1), α3 = (3, 1, 1), α4 = (3, 2, 1).
Then
F (α1) =


18 4 2
6 14 4
6 8 10

 , F (α2) =


18 2 2
6 7 4
6 4 10

 ,
F (α3) =


6 4 2
2 14 4
2 8 10

 , F (α4) =


6 2 2
2 7 4
2 4 10

 .
By using (18) one has |Λ(1)(3, 12)| = 90, |Λ(3)(3, 12)| = 1, |Λ(1)(2, 6)| = 6 and |Λ(2)(2, 6)| = 1.
See Example 3 for the decomposition of the set Λ(m, p) in the present example. Now the latter
expression of (17) gives
Ω(m) = 90 detF (α1) + 30detF (α2) + 3detF (α3) + detF (α4) = 183456.
This enumeration reflects the following decomposition of the level set into invariant tori:
J (m) = 90(F (α1)Z3\Z3) unionsq 30(F (α2)Z3\Z3) unionsq 3(F (α3)Z3\Z3) unionsq (F (α4)Z3\Z3).
The T · p ∼= F (α)Z3\Z3 in Example 11 is one of the three F (α3)Z3\Z3s in this J (m).
A Two elementary lemmas
The following lemma is used in Subsection 3.3
Lemma 7. Let G,H be groups and X be a set. Suppose there are commutative actions of G
and H on X. Denote by Γ (resp. Γ ′) the action of G (resp. H) on X, and by ρΓ (resp. ρΓ ′) its
permutation representation. Then:
(i) The actions of ρΓ (G) and H on X are commutative.
(ii) There is a bijection between G\X and ρΓ (G)\X that is commutative with the action of H.
(iii) For all x ∈ X there is a bijection between H · [x]G and ρΓ ′(H) · [x]ρΓ (G) that is commutative
with the action of H.
Level Set Structure of an Integrable Cellular Automaton 17
Proof. (i) For all g ∈ G, h ∈ H and x ∈ X we have h · (ρΓ (g) · x) = h · Γ (g, x) = Γ (g, h · x) =
ρΓ (g) · (h · x). (ii) Given any p ∈ G\X it can be written as p = [x]G with some x ∈ X.
Define ψ : G\X → ρΓ (G)\X by the relation ψ(p) = [x]ρΓ (G). It is easy to see that this map
is well-defined and yields the desired bijection. (iii) The bijection is given from that in (ii) by
restricting its domain to H · [x]G. 
The following lemma is used in Subsection 4.4
Lemma 8. Let G be a group and X1, X2 be sets. Suppose there are actions of G on X1 and X2,
and there is a bijection φ : X1 → X2 that is commutative with the actions of G. Let H be
another group, and suppose there is an action of H on X1 that is commutative with the action
of G. Then:
(i) There is a unique action of H on X2 that is commutative with φ, and commutative with
the action of G on X2.
(ii) There is a bijection between G\X1 and G\X2 that is commutative with the action of H.
Proof. (i) For all h ∈ H and x ∈ X2 the desired action is uniquely determined by h · x =
φ(h · φ−1(x)). (ii) Given any p ∈ G\X1 it can be written as p = [x]G with some x ∈ X1. Define
φ¯ : G\X1 → G\X2 by the relation φ¯(p) = [φ(x)]G. It is easy to see that this map is well-defined
and yields the desired bijection. 
B An algorithm for Kerov–Kirillov–Reshetikhin map
We present an algorithm for the map of Kerov–Kirillov–Reshetikhin based on [15].
Let p = b1 . . . bL be a ballot sequence of letters 1 and 2. We define M1, M2 to be a pair
of subsets of {1, . . . , L} that is specified by the following condition: The integer j lies in M1
(resp. M2) if and only if bj = 1 and bj+1 = 2 (resp. bj = 2 and bj+1 = 1) . Here we interpret
bL+1 = 1.
We define Op1, Op2 to be a pair of operators acting on finite sets of distinct integers: Given
any such set M , the Op1 (resp. Op2) replaces its i-th smallest element, say x, by x − (2i − 1)
(resp. x− 2i) from i = 1 to i = |M |.
Let ϕ = {} be an empty data set. We repeat the following procedure until we have M1 =
M2 = ∅.
(i) Let i = 0.
(ii) While M1 ∩M2 = ∅, apply Op1 to M1 and Op2 to M2, and replace i by i+ 1.
(iii) WhenM1∩M2 6= ∅ is attained, append {M1∩M2, i} to ϕ, and replaceM1 byM1\(M1∩M2)
and M2 by M2 \ (M1 ∩M2).
In the above procedure the multiplicity of the elements should be respected. For instance
{1, 2, 2, 3} ∩ {2, 2, 4, 5} is equal to {2, 2}, not to {2}. And {1, 2, 2, 3} \ {2, 3} is equal to {1, 2},
not to {1}. At the end we obtain such type of data ϕ = {{S1, i1}, {S2, i2}, . . . , {Ss, is}} for
some s, where Sa are sets of integers and ia are positive integers.
Now we have H = {j1, . . . , js} with j1 = i1, j2 = i1 + i2, . . . , js = i1 + · · · + is, and m =
(mj1 , . . . ,mjs) = (|S1|, . . . , |Ss|). For the riggings J , each (J
(jk)
i )1≤i≤mjk is obtained from Sk by
ordering its elements in increasing order.
Example 14. Consider the path p = 11112222111112221112111222111222212222. Then M1 =
{4, 13, 19, 23, 29, 34} andM2 = {8, 16, 20, 26, 33, 38}. By applying procedure (ii) once, we obtain
M1 = {3, 10, 14, 16, 20, 23} and M2 = {6, 12, 14, 18, 23, 26}. Then by procedure (iii) one has
ϕ = {{{14, 23}, 1}}, M1 = {3, 10, 16, 20}, and M2 = {6, 12, 18, 26}.
18 T. Takagi
In the second turn of the algorithm, we obtain M1 = {1, 4, 6, 6} and M2 = {2, 4, 6, 10} after
applying procedure (ii) twice. Thus one has ϕ = {{{14, 23}, 1}, {{4, 6}, 2}}, M1 = {1, 6}, and
M2 = {2, 10}.
After two more turns, one has ϕ = {{{14, 23}, 1}, {{4, 6}, 2}, {{0}, 1}, {{0}, 3}} and M1 =
M2 = ∅. Hence we have H = {1, 3, 4, 7}, m = (m1,m3,m4,m7) = (2, 2, 1, 1) and
J =
((
J (1)1 , J
(1)
2
)
,
(
J (3)1 , J
(3)
2
)
,
(
J (4)1
)
,
(
J (7)1
))
= ((14, 23), (4, 6), (0), (0)).
Acknowledgements
The author thanks Atsuo Kuniba for valuable discussions.
References
[1] Arnold V.I., Mathematical methods of classical mechanics, 2nd ed., Graduate Texts in Mathematics, Vol. 60,
Springer-Verlag, New York, 1989.
[2] Yura F., Tokihiro T., On a periodic soliton cellular automaton, J. Phys. A: Math. Gen. 35 (2002), 3787–3801,
nlin.SI/0112041.
[3] Yoshihara D., Yura F., Tokihiro T., Fundamental cycle of a periodic box-ball system, J. Phys. A: Math.
Gen. 36 (2003), 99–121, nlin.SI/0208042.
[4] Iwao S., Tokihiro T., Ultradiscretization of the theta function solution of pd Toda, J. Phys. A: Math. Gen.
40 (2007), 12987–13021, arXiv:0705.4013.
[5] Kuniba A., Takagi T., Takenouchi A., Bethe ansatz and inverse scattering transform in a periodic box-ball
system, Nuclear Phys. B 747 (2006), 354–397, math.QA/0602481.
[6] Inoue R., Takenawa T., Tropical spectral curves and integrable cellular automata, Int. Math. Res. Not.
2008 (2008), Art ID. rnn019, 27 pages, arXiv:0704.2471.
[7] Kuniba A., Sakamoto R., Bethe ansatz in a periodic box-ball system and ultradiscrete Riemann theta
function, J. Stat. Mech. Theory Exp. 2006 (2006), no. 9, P09005, 12 pages, math.QA/0606208.
[8] Kuniba A., Nakanishi T., The Bethe equation at q = 0, the Mo¨bius inversion formula, and weight multiplici-
ties. I. The sl(2) case, in Physical Combinatorics (Kyoto, 1999), Progr. Math., Vol. 191, Birkha¨user Boston,
Boston, MA, 2000, 185–216, math.QA/9909056.
[9] Kerov S.V., Kirillov A.N., Reshetikhin N.Yu., Combinatorics, Bethe ansatz, and representations of the
symmetric group, Zap. Nauch. Semin. LOMI 155 (1986), 50–64 (English transl.: J. Soviet Math. 41 (1988),
916–924).
[10] Kirillov A.N., Reshetikhin N.Yu., The Bethe ansatz and the combinatorics of Young tableaux, Zap. Nauch.
Semin. LOMI 155 (1986), 65–115 (English transl.: J. Soviet Math. 41 (1988), 925–955).
[11] Kashiwara M., Crystal bases of modified quantized universal enveloping algebra, Duke Math. J. 73 (1994),
383–413.
[12] Ablowitz M.J., Segur H., Solitons and the inverse scattering transform, SIAM Studies in Applied Mathe-
matics, Vol. 4, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1981.
[13] Kuniba A., Takagi T., Bethe ansatz, inverse scattering transform and tropical Riemann theta function in
a periodic soliton cellular automaton for A(1)n , SIGMA 6 (2010), 013, 52 pages, arXiv:0909.3759.
[14] Stanley R.P., Enumerative Combinatorics, Vol. 1, Cambridge Studies in Advanced Mathematics, Vol. 49,
Cambridge University Press, Cambridge, 1997.
[15] Takagi T., Soliton cellular automata, in Combinatorial Aspect of Integrable Systems, MSJ Mem., Vol. 17,
Math. Soc. Japan, Tokyo, 2007, 105–144.