ALGEBRAIC PROPERTIES OF
LINEAR, BINARY CELLULAR AUTOMATA
by
John Weigand
B.A., University of Colorado, 1971
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Computer Science
1996
This thesis for the Master of Science
degree by
John Weigand
has been approved
by
Jay Rothman
Tom Altman
Date
Weigand, John (M.S., Computer Science)
Algebraic Properties of Linear, Binary Cellular Automata
Thesis directed by Assistant Professor Jay Rothman
ABSTRACT
Algebraic properties for linear cellular automata over ZÂ£ are developed
in this thesis. These properties are then used in the characterization of state
transition graphs for this class of rules. The case n = 2m is treated first,
and it is shown that odd parity rules in this space are invertible, while even
parity rules are nilpotent. The operation of squaring linear rules is studied,
and these results are applied to the characterization of idempotent linear
rules over ZÂ£ for any n. Idempotent rules are used to generate direct sum
decompositions of the state space, and it is shown that linear rules are well
behaved with respect to these decompositions. It is furthermore shown that
state transition graphs for rules defined on spaces of arbitrary dimension may
be characterized by applying the techniques developed for the case n = 2m
termwise to these decompositions.
I
This abstract accurately represents the content of the candidates thesis. I
recommend its publication.
Signed
m
Jay Rothman
CONTENTS
Chapter
1. Introduction ................................................ 1
1.1 An Informal Introduction to Cellular Automata.............. 1
1.2 History of Cellular Automata ................................. 4
1.3 Applications ................................................. 8
1.4 Overview of Thesis ........................................... 9
2. Fundamental Concepts.......................................... 12
2.1 Introduction ................................................ 12
2.2 Notation..................................................... 12
2.3 OneDimensional Cellular Automata............................ 13
2.4 Linear Cellular Automata .................................... 18
3. Circulant Algebra ........................................... 25
3.1 Introduction ................................................ 25
3.2 Matrix Operations............................................ 25
3.3 Circulant Spaces............................................. 36
3.4 The Summation Homomorphism .................................. 41
3.5 State Transition Graphs ..................................... 43
4. Rule 60........................................................ 50
4.1 Introduction ................................................ 50
4.2 Basic Properties of Rule 60 50
4.3 Behavior of 6 on C(2,2m) ................................... 59
IV
Chapter
5. State Transition Graphs for C(2,2m)........................ 64
5.1 Introduction .......................................... 64
5.2 Properties of Odd Parity Rules ........................ 67
5.3 State Transition Graphs for Even Parity Rules.......... 70
5.4 State Transition Graphs for Odd Parity Rules .......... 81
5.5 Example Algorithms..................................... 85
6. Squares of Binary Linear Rules............................ 90
6.1 Introduction .......................................... 90
6.2 Circulant Space Homomorphisms ......................... 90
6.3 Properties of the Squaring Operator ................... 105
6.4 An Embedding of C(2,Z) into C(2,2Z).................... 116
7. Idempotent Binary Rules................................... 119
7.1 Introduction ............................................ 119
7.2 General Properties of Projections........................ 119
7.3 Characterization of Projections on C(2, k).............. 121
7.4 The Lattice of Projections .............................. 127
7.5 Direct Sum Decompositions ............................... 137
7.6 An Isomorphic Structure.................................. 152
8. Structure of C(2,n) ...................................... 157
8.1 Introduction .......................................... 157
8.2 Establishment of a Reference ............................ 158
8.3 Conjugate Level Structures C(2, k) ...................... 175
8.4 Invertible Rules ........................................ 178
8.5 Product Graphs .......................................... 183
v
Chapter
9. Conclusions.......................................... 187
9.1 Summary .......................................... 187
9.2 Related Problems ................................. 188
References .............................................. 190
vi
1. Introduction
1.1 An Informal Introduction to Cellular Automata
Cellular Automata provide mathematical models for spacially and tempo
rally discrete dynamical systems. An informal definition of cellular automata
is presented in this section, and a rigorous definition of onedimensional cel
lular automata is presented in the next chapter.
A cellular automaton is an ordered pair consisting of a state space and
a global map. If A is a finite, nonempty set, then it is said to be a state
alphabet, and its members are defined to be state symbols. If n > 0, then
Zn is said to be an ndimensional lattice, and members of Zn are called sites
or cells. Given a state alphabet and a lattice, an assignment of symbols from
the state alphabet to the cells of the lattice is called a configuration or a
state, and the set of all possible configurations is called a state space. While
it is not necessary that state alphabets possess algebraic structure, they are
usually finite rings.
Global maps are operations on state spaces. In order to identify this class
of operators, the concepts of neighborhood, neighborhood state, and local
map must first be presented. A neighborhood is simply a finite nonempty
subset of Zn, and a neighborhood state is an assignment of symbols from the
state alphabet to the sites in a neighborhood. For a fixed neighborhood and
state alphabet, a local map is a function from the set of neighborhood states
to the state alphabet. If L is a local map associated with a neighborhood N
1
and state alphabet A, then the global map Gi, which operates on the state
space X = Azn may be defined as follows. If x 6 X and c Zn, then a
neighborhood state S may be defined by
S{b) = x{c + b) \fbeN.
Informally, S is determined by the states of the cells in the neighborhood of
cell c. Finally, Gl : X X is defined by
Gl(x)(c) = L(S) VxeX,cÂ£ Zn.
Upon applying a global map to a configuration, the valuation of the result
at any given cell is thus yielded by the action of the local map on the neigh
borhood state associated with that cell.
The following simple example should clarify the preceding definition. The
behavior John Conways gameoflife, which is the best known example of a
cellular automaton, may be described as follows. The cells may be thought of
as squares on an infinite chess board which is the lattice. We may associate
each square with a member of Z x Z, thereby formalizing the lattice structure
and providing a coordinate system. The state alphabet for this automaton
is the set of binary digits, so that at any point in time, each cell is associated
with either a 0 or a 1 (off or on). The neighborhood for this automaton is
yielded by
N = Z x Z  i,j e (1,0,1}}.
Each cell may thus be associated with a nine cell neighborhood that consists
of that cell and the eight cells that share an edge or corner with it. The
local map, which assigns a binary digit to each of the 29 = 512 possible
neighborhood states, is defined as follows. If a cell is off, then it remains off
2
unless exactly three of its eight neighboring cells are on, in which case the
cell is set on. If the cell is on, then it remains on if and only if either two
or three of its neighboring cells are on. Application of the local map to each
square of the board then yields the global map.
There are many variations on the above definition of cellular automata.
First lattices need not be infinite in extent. For example, if m, n 6 Z+,
then Z serves as an example of a finite lattice. Lattices need not even be
rectangular; honeycomb patterns with hexagonal cells have been used. There
are also variations on the way in which local maps are defined. Local maps
may be defined so that they are dependent upon state values of neighboring
cells at times prior to the current time. Such local maps are said to possess
memory. It is also possible that local maps yield a probability distribution on
the state alphabet. The state symbol associated with such a local map is then
selected randomly with respect to the distribution. Cellular automata whose
local maps are defined in this way are called probabilistic cellular automata.
The local map for the gameoflife is easily specified by simple rules in
spite of the fact that there are 512 different neighborhood states. Generally,
local maps are defined by tables in which all neighborhood states and their
associated state symbols are specified. It should be noted that the number
of global maps associated with a particular state alphabet and neighborhood
may be very large, even when the alphabet and neighborhood are small.
For example, there are 2512 different local maps associated with the binary
alphabet and nine cell neighborhood used in the gameoflife.
While there are many variations on the structure of cellular automata,
even the simplest classes are not yet well understood. The class of cellular
automata for which the state alphabet is Z2, the cells are arrayed in one
3
dimension, the lattice is finite, and the global map is linear is clearly much
more amenable to mathematical analysis than most of the variations pre
sented above, yet many questions concerning this class remain unanswered.
1.2 History of Cellular Automata
The first cellular automaton was introduced by John von Neumann [70] in
the late 1940s. He was looking for a rigorous mathematical model of a Turing
machine that additionally had the capability of being able to replicate itself.
The lattice for this automaton is Z x Z, and the state alphabet consists of 29
symbols. This alphabet is not a ring, but some of the symbols still possess
algebraic properties, because they act as OR, and AND gates.
Von Neumann completed the general design of this automaton and spec
ified most of the operations of this machine in detail, but some difficult
timing issues associated with tape operations were left unresolved. After
von Neumanns death, Arthur Burks studied his manuscripts, then edited
and published the above cited work. He also noticed that certain design
features associated with selfreproduction could be utilized in the tape oper
ations, thereby eliminating the timing problems. Burks then published the
improved design. He conjectured that von Neumann must have been aware
of these improvements himself, because he had incorporated them into his
design of the construction unit.
Von Neumanns friend and associate Stanislaw Ulam also did pioneering
research on cellular automata. He used early electronic computers to model
the iteration of global maps on various starting configurations. The resulting
patterns, which were suggestive of growth patterns of crystals, showed that
4
cellular automata could be used to generate complex geometric structures.
Ulams work was years ahead of its time, and it is only in the last decade
it has been advanced. It is important to note that von Neumann and Ulam
were two of the most prolific mathematicians of the twentieth century.
The remainder of the early work on cellular automata was primarily con
cerned with problems in automata theory. Burks, Thatcher, Moore, Holland
and Myhill all made contributions in this area. Works of these researchers,
and the above mentioned work of Ulam may be found in Burks [72]. In
1968, E.F. Codd [71] exhibited of a cellular automaton capable of universal
computation and selfreproduction that only required an eight symbol state
alphabet.
In the 1970s interest in cellular automata automata theory dwindled, and
the field remained quiet until the early 1980s. In the thirty years since Ulam
first used computers to perform cellular automata simulations, they had be
come extremely powerful. In particular, processor speeds had increased dra
matically, and and graphics capabilities had become very sophisticated. This
allowed modern computer scientists and mathematicians to perform exhaus
tive studies of certain classes of cellular automata. It should be noted how
ever, that even with todays massively parallel computers, the combinatorial
properties of cellular automata are such that exhaustive searches are only
possible in special cases.
In the last ten years, the study of cellular automata has undergone ex
plosive growth. Computer simulation techniques have become very sophis
ticated, and results from diverse areas of mathematics have been applied to
cellular automata theory.
Stephen Wolfram [2] [4] is one of the better known mathematicians in
5
volved in the resurgence of interest in cellular automata theory. He used
computers to gather statistical data on cellular automata then used these
empirical results to formulate general theory. He was concerned with the
classification of rules in terms of both algebraic properties and the phe
nomonological results of computer simulations. In 1984 Martin, Odlyzko,
and Wolfram [1] published a paper in which the theory of linear cellular
automata was studied within the context of polynomials over finite fields.
Graph theory is another branch of mathematics that has been successfully
applied to the study of cellular automata. Given a cellular automaton for
which the state space is finite, a directed graph may be constructed by using
the configurations as nodes, and directing an arc from node x to node y if
the transition rule maps x to y. This digraph is called the state transition
graph for the automaton. Given a node in a state transition graph, its
trajectory under repeated application of the rule may be traced from node
to node simply by following arcs. Since the state space is finite, this process
must eventually result in a state being repeated. Furthermore, since cellular
automata are deterministic, once such a repeating state has been reached, the
system becomes periodic. The states which may be repeated thus reside on
cycles in the graph, while the others reside in trees connected to the cycles.
The classification of state transition graphs is currently one of the primary
areas of study in cellular automata theory. The above cited work of Martin,
Odlyzko, and Wolfram was one of the first contributions to the solution of
this problem. In 1985, Guan and He [27] solved the classification problem for
linear cellular automata over finite fields, by studying eigen values of circulant
matrices over those fields. In 1992 Wuensch and Lesser [75] published an atlas
of basins of attraction for state transition graphs of onedimensional cellular
6
automata.
DeBrujin graphs may also be used in the study of cellular automata.
Voorhees [28] incorporates them into algorithms which may be used to de
termine predecessors of configurations with respect to certain classes of rules,
and Sutner [48] utilizes them in a quadratic time algorithm which determines
reversibility of onedimensional cellular automata. The problem of reversibil
ity of cellular automata of higher dimensions was shown to be undecidible
by Kari [20]. He accomplished this by reducing an unsolvable problem con
cerned with determining if a certain class of tilings of the plane is possible
to the reversibility problem.
Information theoretic techniques may also be applied to the study of cel
lular automata. Certain cellular automata may be endowed with measures
which are preserved by the transition rule. Ergodic properties may then be
studied within this context. Cellular automata that exhibit selforganizing
behavior may be used to model processes whose asymptotic behavior corre
sponds to reverse entropy.
Since cellular automata transform strings, they may be used to model
productions in formal language theory. In this way cellular automata may
be classified in terms of the classes of formal languages which they leave
invariant.
This is a brief summary of some of the branches of mathematics that
have been applied to the study of cellular automata. In addition, much of
the current research in cellular automata theory is performed by computer
simulations. This has resulted in the development of new algorithms and
data structures. In particular, genetic algorithms are proving increasingly
useful in finding cellular automata rules that possess particular properties.
7
Richards [16] presents an interesting example in which genetic algorithms are
used to find a local map that can be used to model the growth of a particular
type of crystal.
1.3 Applications
The advances in microprocessor technology in the 1980s finally made
it feasible to use cellular automata as models for physical processes. The
problems best suited for modeling by cellular automata are those in which
evolution of the state space is determined by local interactions. Examples
include problems concerning turbulence, diffusion, wave propagation, crystal
growth and particle interactions. Artificial life is another area of research
that draws heavily on cellular automata theory. Here cellular automata have
been used to model biological systems from microscale molecular and cellular
behavior to macroscale processes such as the spread of diseases and predator
prey relationships.
1.4 Overview of Thesis
In this thesis, algebraic properties of linear cellular automata defined on
ZJj are studied. A cellular automaton is linear if its state space is a module
and its global map is a linear transformation. These notions will be formally
presented in detail in Chapter 2.
Most of the theory developed in this thesis concerns relationships between
graph theoretic and algebraic properties of linear cellular automata. While a
great deal of theory has already been developed concerning state transition
8
graphs for cellular automata, very little work has been devoted to the problem
of describing the algebraic properties of several different rules within the
context of the state transition graph for one particular rule. This thesis
addresses this problem by developing theory in a space whose members may
be considered to be both configurations and global maps. In addition to
yielding efficient methods for determining the structure of state transition
graphs for a large class of rules, this approach exposes previously unknown
algebraic structure of linear cellular automata.
In Chapters 2,3, and 4 several well known results concerning cellular
automata are presented. Although these results are often alluded to in journal
articles, they are seldom formally developed. In the interest of completeness,
all properties of cellular automata required for the theory presented in this
thesis are formally developed. The results presented in Chapters 5 through
8, pertain to relationships between algebraic and graph theoretic properties
of linear cellular automata.
The following as a summary of the material treated in this thesis
Chapter 2 The mathematical notation used in this thesis is introduced
first. Then onedimensional cellular automata are formally defined, and their
basic algebraic properties are developed. Finally linear cellular automata
are identified, their matrices are characterized, and several technical results
concerning them are established.
Chapter 3 In this chapter, circulant spaces are defined and it is shown
that the theory of linear cellular automata may be presented within this
context. While the theory presented in this chapter has been developed in
other contexts, its use in this thesis provides a novel approach to the study
cellular automata.
9
Chapter 4 The structures of the state transition graphs for rule 60 (this rule
is defined in Chapter 4) over a binary space of dimension 2m are characterized.
The graphs for this class of rules are shown to be a complete binary trees
whose heights equal the dimension of the space. These graphs will be used in
Chapter 5 as the reference point for the development of algebraic properties
of linear rules which operate on 22jT.
Chapter 5 Given a fixed value of m, it is shown that the structure of a state
transition graphs for a member of the binary, circulant space of dimension
2m may be obtained from the structure of the graph for rule 60. For such
dimensions, the algebra is particularly simple, because all global maps are
either invertible or nilpotent, with odd parity rules being invertible, while
even parity rules are nilpotent. The graphs associated with these classes of
rules are thus either collections of cycles or trees respectively.
Chapter 6 The theory of squaring linear rules is developed in this chapter. It
is shown that there are two general structures associated with this operation,
depending on the parity of the dimension. This operation is shown to be
linear, and the general forms of the matrices for the two cases are identified.
Chapter 7 Idempotent members of circulant spaces are characterized in
this chapter. Since a rule is idempotent if it equals its own square, the
results developed in this chapter are based on those established in Chapter
6. It is shown that idempotent operators may be used to obtain direct sum
decompositions of circulant spaces. Also it is established that idempotent
maps may be endowed with a natural partial ordering thereby yielding a
distinguished decomposition, and that circulant space operations are well
behaved with respect to this decomposition. Finally the structure of this
decomposition for a space of dimension 2n is shown to be obtainable from
10
that for a space of dimension n.
Chapter 8 The results of Chapters 4, 5, 6 and 7 are merged in this chapter.
If l is odd and the terms of the canonical decomposition of C(2, l) are fields,
then it is shown that any global map on a space of dimension I2r, where
r > 0, splits into a sum of nilpotent and invertible components. Techniques
developed in Chapter 5 are then adapted so that they may be used in this
context
Chapter 9 In this chapter the results established in this thesis are briefly
summarized and several generalizations of these results are suggested. Partic
ular attention is paid to the question of whether or not the theory developed
in Chapter 8 can always be applied to circulant spaces of any dimension.
11
2. Fundamental Concepts
2.1 Introduction
In this chapter notational conventions are introduced, and basic theory
of cellular automata is developed. Since this thesis treats the theory of linear
cellular automata, special attention is paid to this case.
While most of the results presented in this chapter are well known, they
are generally cited in journal articles without proof. Since these results are
important, and proofs are infrequently published, complete proofs of the fun
damental properties of cellular automata required for this thesis are presented
in this chapter.
2.2 Notation
The notation used in this paper is based on set theory. We begin by
defining
a, = {0,1.2....}.
u> is said to be the set of finite ordinal numbers. Each ordinal number is
equal to the set of ordinals that precede it. Thus 0 = 0, and more generally,
if n E u>, then n = {0,1,... n 1}. We furthermore define Z+ =
If A: G Z+, then we define
Zfc (A;, +, ).
12
It is well known that Zfc is a ring, and if k is prime, then Z*. is a field.
In cellular automata theory vectors are often denoted by strings. For
example, (1,0,1,1,0) and 10110 are alternate notations. String notation
provides for the use of underbars to represent repeating sequences. Thus 132
represents the string that repeats the sequence 132. Underbars will most
often be used to represent constant strings such as 0 and 1.
The following notational conventions will also be observed. If S is a set,
then V{S)n denotes its power set, and #(S) denotes its cardinality. The
symbol is read as end of proof, and 3 is read as such that.
2.3 OneDimensional Cellular Automata
Formal definitions of onedimensional cellular automata are presented in
this section. First it is necessary to introduce some concepts pertaining to
linearity.
Let 5 be a nonempty set, and define
Z% = {x \ x : S Zk}
Zf is a module of dimension ^(S) over Z*,, and S is said to be the index set
for this module. If A; is a prime, then Zf is also a vector space.
Let S and T be nonempty sets. A function
A ' Zf Zf
is said to be linear if for each x,y Zf, and j Â£ k,
A(x + y)= A(x) + A(y), and A(jx) = jA(x).
13
Generally, in order to establish that a transformation on a module is linear it
is necessary be show that it preserves scalar multiplication. However, since
multiplication by a scalar from Z*, may be obtained by iterated additions,
linearity of a transformation follows upon showing that addition is preserved.
Similarly, in order to show that a subset of module is a submodule, it is only
necessary to show that it is closed with respect to addition.
Definition 2.1 Let S be a nonempty set. IfiES and z E Z+; then define
&k,s,i e Zf
by
ek,S,i{j) ~ V 3 Â£ S.
(ek,s,i)ieS ^ defined to be the canonical basis for Zf.
This definition, while precise, often requires more symbols than are nec
essary. If k is known from context, then the notation e^; suffices. If S is
also known, then the conventional e may be used.
Let /c,n E Z+, and define
ZÂ£ = {x  x : n Zfc}.
ZÂ£ is defined to be the ndimensional state space over Z*.
In cellular automata theory members of ZÂ£ are called configurations, and
members of n are called sites or cells.
If x ZÂ£ and in, then x(i) represents component i of x. Furthermore,
if j E n, then the expression i + j is evaluated modulo n.
Notice that we have used the term dimension in two different senses. Z
is onedimensional in the sense that the components of any member may
14
?r 3
be thought of as being situated along a line, while this space clearly has
dimension n as a module. The meaning of this term will be clear from the
context in which it is used.
Two classes functions are required in order to define a cellular automaton.
First the local map must be specified. This function is then used to define
the global map. Before defining local maps, we must formalize the concept
of neighborhood.
Definition 2.2 Let r 6 Z+. Define
r = {r, r + 1,..., r 1, r}.
r is said to be the set of radius r indices.
Definition 2.3 Let k,r Z+. Define
N(k,r) {a  a : r Z*,}.
N(l,r) is said to be the space of radius r neighborhoods over Z*.
Definition 2.4 Let k,r Z+ and define
T(A;,r) = {r  r : N(k,r) Z*}.
T(fc,r) is said to be the space of Zfc valued, radius r local maps.
Since N(k,r) is the set of functions from r to Zit is a module of di
mension 2r + 1. Furthermore, it contains k2r+l elements. This implies that
T(fc,r) is a module of dimension k2r+l that contains fcfc2r+1 elements. Spaces
of local maps may clearly be very large, even for modest values of k and r.
15
Definition 2.5 Let k,n,r G Z+. Define
v : ZÂ£ x n N(k,r)
by
v(x,i)(s) = x(i f s), Vie Z^, i G n, s G r.
v is defined to be the radius r neighborhood extraction operator on ZÂ£, and
v{x,i) is defined to be the radius r neighborhood of x at i.
The neighborhood extraction operator simply copies segments of vectors
centered at a site onto vectors of smaller dimension. Thus if x,y G ZÂ£ and
i E n, then the process of adding x and y pointwise then extracting the
neighborhood about i yields the same result as does that of first extracting
the neighborhoods about i separately and then adding them. The following
proposition follows immediately from this observation.
Proposition 2.6 The operation of neighborhood extraction is linear.
Given a configuration x G ZÂ£, and a site i G n, u associates this pair with
the member of N(/c,r). This allows global maps to be defined in terms of
local maps as follows.
Definition 2.7 Let, k,r,n G Z+, with 2r + 1 < n and r G N(k,r). Define
AT : ZjJ > Zl
by
AT(x)(i) = r(i/(x,i)) V x G ZÂ£ and ViGn,
At is said to be the global map on ZÂ£ defined by r.
16
Definition 2.8 Let, k,r,n Z+ with 2r + 1 < n and define
A(k,r,n) = {Ar \ r Â£ T(/c,r)}.
A(k,r, n) is said to be the space of radius r cellular automaton rules on ZÂ£.
The following proposition follows immediately from the definitions.
Proposition 2.9 Let k,r,n Â£ Z+ with 2r + 1 < n, i,j Â£ n, and A Â£
A(k,r, n). Then
v{x,i) = u(y,j) = A(x){i) = A{y){j).
The evaluation of a cellular automaton operator at a site in a configuration
is thus determined by the valuations of the configuration in the neighborhood
of that site and not by its position.
Technically, cellular automata rules are elements of T(fc,r), but cellular
automata operators are often called rules and equated with the local maps
that define them. This relationship may be expressed in terms of the following
isomorphism.
Definition 2.10 Let, k,r,n Z+ with 2r + 1 < n and define
Cft.r,n : T(fc,r) A(k,r, n)
by
Cfc,r,n('7) AT.
For each n Â£ Z+, this operator simply pairs local maps with the global
maps which they define. The next theorem shows that A(k, r, n) is a vector
space with respect to pointwise addition, and that (k,r,n is a vector space
isomorphism.
17
Theorem 2.11 Let, k,r,n E Z+ with 2r + 1 < n. Ifr0,Ti E T(k,r), then
Ck,r,n(T"0 T 7l) = Cfc,r,n(^o) T Ck,r,n('Ll)
Proof Let x E ZÂ£ and i E n. Then
Ck,r,n(ro)(x)(i) + Cfc,r,n(ri)(x)(i) = T0(i/(:c,i)) +
= (To + nXi/foz))
= Cfc.r.n^O +Ti)(rr)(i).
' We may now define onedimensional cellular automata.
Definition 2.12 Let k,r,n E Z+, r E T(k,r), and AT E A(k,r,n). The
ordered pair (Z%,AT) is defined to be a onedimensional cellular automaton.
2.4 Linear Cellular Automata
Linear global maps possess a great deal of structure. In this section
linear local maps are identified, and it is shown that a global map is linear
if and only if its defining local map is. We begin by defining dot products,
and establishing some of their basic properties. These results are similar to
familiar results concerning dot products on Euclidean spaces.
Definition 2.13 Let k Z+ and let S be a finite, nonempty set. Define
< , >:Zf x Zf >Zk
by
= ^x(s)y(s), V x,y E Zf.
365
Then < x,y > is said to be the dot product of x and y.
18
Proposition 2.14 is linear in both arguments.
Proof Let x,y,z E ZÂ£. Then
=
^x{s)(y + z){s)
s65
^2x{s){y{s) + z(s))
36S
J2{x{s)y(s) + x{s))z{s)
J^a;(s)y(s) + J^(a)z(s)
365 365
+ .
Scalar multiplication is preserved since multiplication by an element of
corresponds to a finite number of additions. Linearity with respect to the
first argument follows by symmetry.
Since local maps are functions from N(fc,r) to Zthey are functionals.
The following theorem characterizes the linear functionals on N(fc, r).
Theorem 2.15 Let k E Z+. Let S be a finite, nonempty set. If
F : Z f > Zj.,
then F is linear if and only if there exists x E Zf such that
F(y) =< y,x > Vy e zÂ£.
Proof (<*=) If x E Zf, then < ,x > is linear by Proposition 2.14.
(=>) Assume that F is hnear, and define x E Zf by
a;(s) = F(es) Vs E S.
19
Now let y Â£ Zf and show that F(y) =< y, x >. First notice that
y = ^2y(s)e3.
ses
Next,
F(y) = F(^2v(s)es)
ses
= l^^(y(s)es))
36 S
= ^y(s)F(es)
365
= ^y(s)x(s)
365
= < y, x > .
Corollary 2.16 If k,r Â£ 1+ and r Â£ T(fc,r), then r is linear if and only if
there exists a Â£ N(fc,r) such that
t(J3) =< p,a> Vp Â£ N(fc,r).
Proof Simply substitute N(k,r) for S in the theorem.
Definition 2.17 If k,r Â£ Z+, r T(k,r) and a Â£ N(k,r) such that
r(p) =< p,a> V P Â£ N(fc,r),
then a is said to generate r.
Corollary 2.16 states that there is a natural correspondence between mem
bers of N (k, r) and the subset of T(fc, r) that consists of the linear local maps.
It has already been shown that N(k, r) is a module. The next theorem asserts
that the set of linear local maps constitute a submodule of T(k,r) that is
isomorphic to N(k,r) via this correspondence.
20
Theorem 2.18 Letk,r E Z+, a0,ax E N(k,r) andrQ,Ti E T(k,r) suc/i that
aj generates Tj Vj 6 2. Then To + Ti is o linear map. Furthermore, r0 + ti
is generated by ao + Â£*1.
Proof It suffices to show that
(To + n)(P) =< P,^o + Oil > V/?eN(k,r).
Now
(to+ti){P) = r0(f3) + tx{/3)
= < fi, a0 > + < /?, ai >
= < /?, Qto + Qi >
Since the operation of neighborhood extraction is linear, it is easily shown
that the linearity of a global map follows from that of its defining local map.
Theorem 2.19 Let k,r,n E Z+, r E T(&,r) and Ar E A(k,r,n). Then AT
is linear if and only if r is linear.
Proof ('*=) Assume r is linear and let x,y E ZjJ, i E n. Then
Ar(x + y){i) = t(v(x + y,i))
= r{v{x,i)+ i/{y,i))
= r(v{x,i))+T{u{y,i))
= Ar{x)(i)+Ar{y)(i).
(==*>) Assume that r is not linear. Then there exists a,/? E N(/c,r) such
that
r(a + P) ^ r(a) + r(/?).
21
Define x 6 ZÂ£ by
x{i)
a{s)
0
if i = s, where sÂ£r
otherwise.
Notice that negative values of s are evaluated modulo n. x is defined so that
its neighborhood at site 0 is equal to a, while it is constant at 0 outside of
this neighborhood. If we define y e similarly in terms of (3, then
AT(x + 2/)(0)
r(i/(x + y,0))
r{u(x,0 ) + v(y,0))
r(a + j3)
r(a) + t((3)
= tMM)) +r{u{y,0))
= ylT(m)(0) + ^(2/)(0).
Definition 2.20 Let, k,r,n Z+ and define
Â£(k,r,n) = {A A(k,n, r) \ A is linear}.
Â£.(k,r,n) is said to be the space of ndimensional, radius r linear cellular
automata rules over k.
Since the set of linear local maps is a submodule of T(A;, r), and the oper
ation of pairing a global map with its defining local map preserves addition,
it immediately follows that Â£(k,r,n) is a submodule of A(k,r,n).
Generally, in order to evaluate a cellular automaton operator at a con
figuration, it is necessary to extract the neighborhood about each site, then
retrieve the valuation of the local map from a table. This procedure is both
22
difficult to model mathematically, and computationally intensive. Linear
rules are easily modeled mathematically. Furthermore, they may be effi
ciently implemented on computers if the property established in the next
theorem is utilized.
Theorem 2.21 Letk,r,n E Z+, a E N(fc,r),r E T(A;,r), andAr E A(k,r,n)
such that a generates r. If x E%% and i En, then
r
Ar(x)(i) = ^ x(i + s)a(s).
s=r
Proof
r{v{x,i))
< v(x,i), a >
r
is(x,i)(s)a(s)
s=r
r
^2 x(i + s)a(s).
s=r
For example, consider the radius one binary local map that is defined
by the dot product with respect to the vector (1,0,1). This rule sets the
valuation at site i to 1 if the valuations at sites i 1 and i + 1 are different
and 0 if they are the same. If we let A denote the global map defined by this
rule, then for any configuration x on which A is defined,
A(x)(i) = x(i 1) + x(i + 1)
holds for each site i of x.
Table 2.1 lists the linear members of T(2,1) and their generators. The
rows of this table correspond to the eight linear members of T(2,1). The
23
column headings for the rule definition are the neighborhoods, and the entry
corresponding to a row and column yields the valuation of the corresponding
rule at the corresponding neighborhood. That entry is obtained by perform
ing the dot product of the neighborhood and the generator for the rule. The
decimal equivalent of the eight digit binary number yielded by the defining
entries for a rule is listed in the index column of the table. Notice that the
operation of adding generators corresponds to the operation of adding rows
of the table. This is the property established by Theorem 2.18.
Table 2.1 Linear Members of T(2,l)
Index Gen 111 110 101 Rule 100 Oil 010 001 000
0 000 0 0 0 0 0 0 0 0
60 110 0 0 1 1 1 1 0 0
90 101 0 1 0 1 1 0 1 0
102 Oil 0 1 1 0 0 1 1 0
170 001 1 0 1 0 1 0 1 0
150 111 1 0 0 1 0 1 1 0
204 010 1 1 0 0 1 1 0 0
240 100 1 1 1 1 0 0 0 0
24
3. Circulant Algebra
3.1 Introduction
Since ZÂ£ is a module, each linear rule may be associated with a matrix,
and hence, the set of radiusone linear rules which operate on ZÂ£ generates a
subring of the ring of order n matrices over Z*. In this chapter this subring
is characterized, and it is shown that the operations of matrix addition and
multiplication, as well as the'multiplication of a vector by a matrix may be
expressed in terms of binary operations on ZÂ£. Several technical properties
concerning these operations are then established.
3.2 Matrix Operations
In this section matrices and their basic operations are defined. While the
definitions presented in this section are technically different from the usual
definitions of matrices, these differences are essentially notational. Since
ordinal notation is used, we note that row and column numbering begins at
zero.
Definition 3.1 Let k,m,n Z+. ZÂ£xm is said to be the space of n x m
matrices ouerZ*.
We next define matrix addition and multiplication.
Definition 3.2 Let k,l,n,m 6 Z+, and define:
25
1. + : ZÂ£xm x ZÂ£xm > Z"xm by
(A + B)(i,j) = A(i,j) + B(i,j) Vi En, j Em, A,B E ZÂ£xm.
A + B is said to be the matrix sum of A and B.
2. o : ZÂ£xm x Zx! ZÂ£xi by
Ao B(i,j) ^2A(i,s)B(s,j) Vi En, j El, A E ZÂ£xm, B EZ
mxl
k '
s6m
Ao B is said to be the matrix product of A and B.
When expressing matrix products the symbol o will generally be omit
ted, so that matrix multiplication will simply be denoted by juxtaposition of
terms.
Definition 3.3 Let k,m,n E Z+, A E ZÂ£xm and define
AT EZ
mxri
k
by
AT{j,i) = A(i,j), V O',i) Emx n.
AT is said to be the transpose of A.
Definition 3.4 Let k,m,n E Z+, A E ZÂ£xm, and x E Z. Define
ArT e z?
by
AxT(i) = ^~^A{i,j)x{j) Vi E n.
jem
Ax1 is said to be multiplication of the vector xT by the matrix A.
26
Multiplication of xT by A clearly corresponds to multiplication of matrices
where xr is assumed to be a matrix with a single column.
At the end of this section it will be shown that the class of matrices
introduced in the next definition yields the smallest subring generated by
the radiusone, linear rules on ZÂ£.
Definition 3.5 Letk,nÂ£ Z+. Then:
1. Define circ : ZÂ£ ZÂ£xn by
circ(x)(i,j) = x(j i) V i,j Â£ n and x Â£ ZÂ£.
circ is said to be the circulant matrix operator on ZjJ.
2. If x Â£ ZÂ£; then circ(x) is said to be the circulant matrix generated by
x.
3. Define M(k,n) = ({circ(x)  x Â£ ZÂ£},+, o). M(k,n) is said to be the
ring of order n circulant matrices over Z
After introducing some preliminary results, it will be shown that Ai(k, n)
is indeed a ring. It will furthermore be shown that matrix operations may
be defined in terms of generating vectors.
Proposition 3.6 M(k,n) = {A Â£ ZÂ£*n  A(i + l,j + 1) = A(i,j)Vi,j Â£ n}.
Proof (C) Let ieZJ and i,j Â£ n. Then
circ(x)(i + l,j + 1) = x(j + 1 (i + 1))
= x(ji)
= circ {x)(i,j).
27
(2) Let A G ZÂ£xn such that
A(i + l,j + 1) = A(i,j) Vi,jen,
and define x G ZÂ£ by
x(j) =A{0,j),Vj en.
By induction on the rows of A, we now show that circ(x) = A. First, if i = 0,
then
A(i,j) = A(0,j)
= x{j)
= z(j0).
Next, assume that the theorem holds for row i, where i < n 1, and let
j G n. Then
A(i + l,j) = A(i,j 1)
= x((jl)i)
= x(j ~{i + 1)).
The proof of this proposition contains a proof that the generator of a
circulant matrix is row zero of that matrix. This observation serves to prove
the next corollary.
Corollary 3.7 The circulant operator is injective.
The proof of Proposition 3.6 also shows that given j G n, row i + 1 is a
rotation of row i one position to the right, and column j + 1 is a rotation of
column j one position downward.
28
We next show that addition of circulant matrices corresponds to addition
of generators. Then, since ZÂ£ is a vector space, A4(k,n) must a subspace of
Znxn_
Proposition 3.8 If x,y 6 ZÂ£, then
circ(x + y) = circ(x) + circ(y).
Proof Given i,j 6 n,
circ(a:+y)(i,j) = (x + y)(ji)
= x{j i) + y(j i)
= ckc(x)(i,j) + civc(y)(i,j).
Corollary 3.9 M.(k,n) is a subspace ofZ^xn.
Convolution is a binary operation that arises in many different contexts.
We next show that multiplication of circulant matrices corresponds to con
volution of their generators. In this way, linear rules may be equated with
configurations. In following chapters, this blurring of the distinction between
rules and configurations will provide a means to express the algebraic prop
erties of a rule in terms of its position in the state transition graph associated
with another rule.
Definition 3.10 Define
* : %nk x ZÂ£
by
x*y(i) = ^2x(l)y(il) Vx,yel%,iEn.
in
x y is defined to be the convolution of x and y.
29
Theorem 3.11 Let x,y ZÂ£. Then
circ(x)circ(y) = circ(a; y).
Proof Define 2 E ZÂ£ by
z{i) = circ(a;)circ(y)(0,i) Vi (E n.
Now, given j 6 n,
z(j) = circ(x)circ(y)(0, j)
= ^circ(x)(0,s)circ(2/)(s,j)
sen
= x(s s)
sen
= X*y(j).
To complete the proof, we show show that circ(x)circ(y) has the structure of
a circulant matrix as follows. If i,j Â£ n, then
circ(x)circ(?/)(i + 1 ,j + 1) = ^^circ (x)(i + 1, s)circ(y)(s, j + 1)
sen
= ^ z(s (i + 1 ))y((j + 1) s)
sen
= ^x(t i)y(j t) where t = s 1
ten
= ^circ(z)(i,Â£)circ(y) (Â£,;?')
ten
= ciic(x)circ(y)(i,j).
The next two propositions show that convolution is commutative, and
that e0 is the multiplicative identity on ZÂ£.
30
Proposition 3.12 Ifx,y Â£ ZÂ£, then
x y y x.
Proof If x, y Â£ ZÂ£ and iÂ£n, then
x*y(i) 'y^x(s)y(i s)
sen
= ^^x(i t)y(t) where f = i s
ten
= *)
ten
= y*x(i).
Proposition 3.13 eo z = x Vi Â£ ZÂ£.
Pix>of Let igZJ and iÂ£n. Then
eQ*x{i) = eo(s)x(i s)
sen
 X <5o,sa:(i s)
sen
= x(i).
The above results may now be combined to show that JA(k, n) is a com
mutative ring.
Theorem 3.14 M.{k,n) is a commutative subring of ZjJxn.
i
Proof A4(k, n) is a subspace by Corollary 3.9, and closed under multiplica
tion by Proposition 3.11. Proposition 3.13 shows that e0 is the identity with
respect to convolution, and it is easily seen that eo generates the identity
matrix. Finally, Proposition 3.12 establishes commutivity.
31
Corollary 3.7 shows that circ is injective and, surjectivity follows by def
inition. Corollary 3.9 shows that it preserves addition, and Proposition 3.11
shows that multiplication is preserved. This argument serves to prove the
next theorem.
Theorem 3.15 circ. (ZÂ£,+,*) M(k,n) is a ring isomorphism.
Theorems 3.14 and 3.15 show that the ring operations on A4(k,n) may
be naturally associated with the operations of addition and convolution on
C(k, n). We now use this isomorphism to show that multiplication of a vector
by a circulant matrix corresponds to a linear combination of rotations of that
vector.
Since (ej)ln is a basis for ZÂ£, Proposition 3.9 shows that (circ(ej))ten is
a basis for A4(k,n). The next two propositions show that this basis forms
a cyclic group with respect to convolution, with each 6i acting as a rotation
on Zg.
Proposition 3.16 Let nÂ£ Z+ and i,j n. Then
Ct ej &i+j.
Proof Let mÂ£n.
e* * ^ ei(l)ej(m l)
ten
= ei(i)ej(m Â£), since ej(Z) = 6u.
That
ej{mi) =
1 if j = m i
0 otherwise
32
follows immediately from the definition of ej. This finally yields
e{ ej(m) =
1 if m = i + j
0 otherwise.
Proposition 3.17 Let i En and x E ZÂ£. Then given j E n,
ei*x(i) =x(j + i).
Proof Apphcation of the definition of convolution yields
e* x(j) = ^2 ei(l)xU + 0
len
= YlSiixti+l)
le n
= x(j + i).
Just as multiplication of circulant matrices may be expressed in terms of
generators, given x,y E 1%, circ(x)yT may be expressed in terms of x and y
as follows.
Definition 3.18 Define
O
K x K
n
'k
by
x Qy ^2x(s)y(i + s) ViEn.
sen
x Qy is defined to be the circulant product of x and y.
Theorem 3.19 If x,y E ZÂ£, then (xQy)r = circ(x)?/T.
33
Proof Let x,y G ZÂ£ and i En. Now
circ(x)yT(i) = circ(z)(i, s)y(s)
sen
sen
= + Â£), where i = s i
ten
= xQy(i).
Linear rules have been characterized, but their matrices have not. First, in
order to assign a vector to a rule of radius r, we require that the rule be defined
on a space of dimension at least 2r + 1. This insures that neighborhoods do
not wrap around and overlap themselves. By Theorem 3.19, we need only
define a vector such that circulant multiplication of each member of ZÂ£ by
that vector yields the same function as does application of its associated rule.
Theorem 3.20 Let, k,r,n E Z +,a E N(fc,r),r G T(A;,r) andAr C{k,r,n)
such that t defines AT and r =< ,a>. Define xa G ZÂ£ by
{a(i), ifin r
0, if r < i < n r.
Then, given y G ZÂ£,
Ar{y) =xaOy.
Proof If i En, then
r
Ar(y){i) = y(Â£ + s)a(s)
s=r
r
= Y^y(i+s)a;(s)
s=r
34
r nr1
= y{i + s)xa(s) + y{i + l)0
s=r Z=r+1
r nr1
= ^2 p(i + s)xa(s) + J2 l/(* + 0(0
s=r Z=r+1
= ^2,y{i + l)xa(!)
len
= ^2xa(l)y(i + l)
len
= xaQy{i).
N(fc,r) is closed under addition, but not multiplication. For example, the
linear rule generated by 001 N(A:, 1) shifts each configuration one position
to the left, while its square 00001, which shifts configurations two places to
the left, is a member of N(k, 2)\ N(/c, 1). By Theorem 3.20, a subset of N(/c, r)
may be equated with elements of ZÂ£. Thus, if n > 3, then
N(M)C(ZÂ£,+,*),
and hence, there must be a smallest subring of (ZÂ£,+,*) that contains it.
The next theorem shows that this ring is all of (ZÂ£, +, *).
Theorem 3.21 If k,n E Z+, with n> 3, then N(k, 1) generates (ZÂ£ + *).
Proof First notice that
001 eN (Jb, l).
By Theorem 3.20, this generator corresponds to ex E ZÂ£. By Proposition
3.16,
^ ^i+j
Thus the ring generated by N(/c, 1) must contain
35
Since this is a basis for (ZÂ£, +, *), we see that N(fc, 1) generates (ZÂ£, +, *).
3.3 Circulant Spaces
Vector addition is defined pointwise for elements of ZÂ£, multiplication of
circulant matrices is performed on pairs of elements from ZÂ£xn, and operation
on a vector by a circulant matrix involves one argument from ZÂ£xn and one
from ZÂ£. All three of these operations thus have different domains. Matrix
multiplication maps into ZÂ£xn, while the other operations have ZÂ£ as their
range. In spite of these differences, it is possible to consolidate all three of
these operations into one abstract structure. This is so because circulant
matrices are defined in terms of vectors.
Definition 3.22 Let k,n E Z+, and define
C(k,n) = (Z]J,+,*,).
C(k,n) is defined to be the n dimensional circulant space over Z*.
This consolidation of operations into one structure provides a context
within which it is possible to investigate relationships between the opera
tions of convolution and circulant products. The most important of these
relationships is based on the concept of conjugation of a configuration.
Definition 3.23 Let x E ZÂ£ and define x ZÂ£ by
x(i) = x(i) Vi E n.
x(i) is said to be the conjugate of x.
36
It is clear that
x = x yx E ZÂ£.
We now show that conjugation distributes over all circulant space operations.
Proposition 3.24 Ifk,nE Z+, and x,y E Z, then
x + y = x + y.
Proof If i E n, then
x + y{i) = (x + y)(i)
= x(i)+y(i)
= x(i) +y(i).
Proposition 3.25 Given k,n EZ+ and x,y E ZÂ£,
x y = x*y.
Proof Let i E n. Then
x y(i) x* y(i)
= o
Zen
Zen
=  l)
Zen
= x*y(i).
The next corollary extends Proposition 3.25 to the operation of exopnen
tiation.
37
Corollary 3.26 If x Â£ ZÂ£ and i Â£ Z+, then x{ = xl.
Proof The case i = 1 is obvious and yields a base for the induction. For
i > 1, the induction step follows by letting re11 = y in the proposition.
Theorem 3.27 If x,y G 7%,then
x y = x Qy.
Proof Given iG/i,
x*y(i) = ^Tx{l)y(il)
ln
 (0)
lÂ£n
= ^z(l)y(i + l)
lÂ£n
 x O y(i).
Corollary 3.28 For x,y G ZÂ£,
x(Dy = x*y.
Proof This follows from the reflexivity of conjugation.
Finally, we show that conjugation distributes over circulant multiplica
tion.
Theorem 3.29 For x,y Â£ ZÂ£,
xQy = iO y.
38
Proof
x y x y
= x*y
= x y
= xQy.
In matrix theory, it is well known that given a pair of conformable matri
ces and a vector, the result obtained by first multiplying the matrices then
operating on the vector is the same as the result obtained by first operating
on the vector by the right matrix then operating on the resulting vector by
the left matrix. The next theorem simply restates this property in terms of
convolution and circulant multiplication.
Theorem 3.30 Given k,nÂ£Z+ and x,y,z Z]
(x y) Q z x Q (y Q z).
Proof
(x*y)Qz =
(x *y) z
(x*y) z
x (y z)
xQ(yOz).
In the literature on cellular automata, it is common to see a diagram
of the evolution of a onedimensional automaton under a rule, where the
initial configuration is displayed on the top line and each succeeding line is
the result of applying the rule to the line above. Patterns for many rules
39
are well known. It is often useful to know the pattern obtained by raising
a rule to powers, but these are rarely published. The next theorem shows
how to determine this structure for a rule from the evolution of eo under its
conjugate.
Theorem 3.31 Let x ZÂ£ and m Â£ Z+. Then
xm = x77le0.
Proof First let m = 1. In this case, application of Theorem 3.27 yields
x x eo
= x e0.
Next assume that the result holds for m 1. Then
x x1
x (x7711 O eo)
x O (x7711 0 e0)
x O e0.
The space of circulant matrices is closed under transposition. In fact,
the next theorem asserts that conjugation of configurations corresponds to
transposition of associated matrices.
Theorem 3.32 If x Â£ then
circ(x) = circ(x)T.
x
40
Proof Let and i,j e n. Then
civc(x)(i,j) = x(ji)
= x(ij)
= circ(x)(j, i)
= circ(x)T(i,j).
If x E Z%, then
x : n
while
circ(a:) : ZÂ£ ZJJ.
Thus x and circ(x) have different domains and ranges. The'next two defi
nitions, which are technically abuses of notation, establish notations for the
kernels and ranges of members of ZjJ when they are equated with their asso
ciated circulant matrices.
Definition 3.33 Let k,nÂ£ Z+, x ZÂ£ and define
ker (x) {y e Z^\x Q y = 0}.
Definition 3.34 Let k,n Z+, x E ZÂ£ and define
rng (x) = {y ZÂ£ 13 z e ZÂ£ 9 x z = y}. (3.1)
3.4 The Summation Homomorphism
The linear functional presented in this section simply sums the valua
tions of a configuration. This operation will be used extensively in the next
chapter.
41
Definition 3.35 Let k,n e Z+ and x e ZÂ£. Define
E : ZÂ£ Ik
by
S(x) = ^2x
l n
Ex is said to be the summation of x.
Theorem 3.36 E : (ZÂ£,+, *) * (Zfc,+,) is a ring homomorphism.
Proof The operation of addition is clearly preserved because it is commu
tative. We next show that convolution is preserved. Let x,y 6 ZÂ£. Then
E {x*y) = ^2x*v(i)
ien
ien ien
ien ien
= 5>(Z)S(v)
ien
= z(y)Jtx(l)
ien
= 2fe)S(i)
= E(x)E (y).
Corollary 3.37 Ifx,y ZÂ£ then
T,(xQy) = E(x)E(y).
Proof Clearly
E(x) = E(x).
42
Next notice that
x Qy x *y,
and apply the theorem.
If k = 2,' then this operation returns 0 for configurations that map an even
number of indices to 1, and 1 for configurations that map an odd number
of indices to 1, that is, it returns the parity of a configuration. The next
definition formalizes the notion of parity.
Definition 3.38 Let nÂ£ Z+ and define
1. even(n) = ({re E C(2,n) \ Ex = 0}, *) is defined to be the simi group of
ndimensional, even parity configurations.
2. odd(n) = ({x E C(2,n)  Ex = 1},*) is defined to be the simi group of
ndimensional, odd parity configurations.
It is an immediate consequence of Theorem 3.36 that these sets are indeed
semi groups.
3.5 State Transition Graphs
Any cellular automaton for which the state space is finite may be asso
ciated with a directed graph, called a state transition graph. The nodes of
this graph are the configurations of the state space, and an arc exists from
node y to node z if the automaton rule maps y to z. Each node thus has
outdegree equal to one. Given any configuration, the rule may be applied
to it resulting in another configuration to which the rule may again be ap
plied. Since the state space is finite, this process must eventually result in a
43
repetition. If a node is eventually repeated, it is defined to be an attractor
state. Such a node, and all of the nodes occurring between it and the first
repetition, induce a cyclic subgraph. This subgraph is called an attractor.
Clearly, each element of an attractor is also an attractor state. The remain
ing states are called transient states. For a particular automaton, transient
states may or may not exist, but if they do exist, then some of them will not
have preimages; these states are called GardenofEden states. Given any
attractor state, the subgraph induced by that state and the transient states
that eventually map to it is a tree. This tree is defined to be the transient
tree rooted at that node. The subgraph that consists of an attractor and all
of the subtrees rooted at those attractor nodes is called a basin of attraction.
The basins of attraction are also the weakly connected components of the
state transition graph. The next definition formalizes these concepts.
Definition 3.39 Let k,n Â£ Z+ and x Â£ C(k,ri). Define:
1. G(x) (C(k,n),E(x)), where E(x) = {(y,xQy)\y Â£ C(k,n)}. G(x)
is said to be the state transition graph for x.
2. atr(x) = {y Â£ C(k, n)  3 r Â£ Z+ 3 xr y = y}. atr(:r) is said to be the
attractor space for x.
3. trn(x) = C(k,n) \atr(:c). trn(a:) is said to be the transient space for x.
4 goe(z) = {y Â£ C(k,n)  {z Â£ C(k,n) \xQz y} = 0}. goe(z) is said to
be the set of GardenofEden states for x.
44
Definition 3.40 Let k,n
1. Define pLx : C(k, n) > u by
(J'xi'y) min{r G u>  xT 0 y 6 atrx}
px{y) is said to be the x level of y.
2. Define px : atr(x) Z+ by
Px(y) = min{r 6  xr 0 y = y}
px(y) is said to be the x period of y.
The restriction of x to atr(z) is invertible, and the inverse of y atr(a:)
is yielded by xPx^~l Qy. This choice clearly works as an inverse image, and
it must be unique since any attractor state which maps to y must be in the
same attractor as y, and x3 Qy ^ y whenever 0 < s < px(y).
Definition 3.41 Letyt atr(x). Define:
1. Vx(y) = {z E trn(x)  3 r e Z+ 3 xr z = y} U{y} Ve(y) is said to be
the vertex set of the transient tree rooted at y.
2. Ex(y) = {(z,x O z)  z 14(y)\{y}}. Ex(y) is said to be the edge set
for the transient tree rooted at y.
3. Hx(y) = (Vx(y), Ex(y)). Hx(y) is said to be the transient tree rooted at
V
To see that Hx(y) is indeed a tree, first notice that it contains no cycles
since each vertex other then y has outdegree equal to one, and given a node
2 e Hx((y),
p,x(z) > p,x(x z).
45
Finally, it is weakly connected because each node is connected to y. It is
clear that the set of leaves of Hx(y) is equal to Vx(y) Q goe(x).
Since iQO = 0 Vi, it follows that 0 Â£ atr(x). This fact insures us that
the following definition always makes sense.
Definition 3.42 Define nil(rc) = 14(0). nil(a;) is said to be the space of nil
states for x.
It follows from this definition that nil(a;) is the set of nodes upon which
x acts as a nilpotent operator. Since the null space of x is the set of nodes
which map to 0 under one application of x, it must be contained in nil(x).
The next proposition asserts that nil(x) is indeed a subspace of C(k,n).
Proposition 3.43 Ify, z Â£ nil(:r), then
y + zÂ£ nil(x).
Proof Let t = max{fix(y),fix(z)}. Then
x1 Q (y + z) = xl Qy + xl Q z = 0.
It is also easy to show that atr(x) is a subspace of ZÂ£.
Proposition 3.44 Ify, z Â£ atr(rr), then
y + zE atr(z).
Proof Let t = yx{y)fix{z). Then
x1 Q (y + z) = xl Q y + xl Q z = y + z.
46
The restrictions of x to its nil and attractor spaces result in simple state
transition graphs. The action of x on nil(rr) yields in a tree with a self loop
at 0, while its action on atr(rr) yields a collection of cycles. The next theorem
states that given any linear rule, the state space decomposes into the direct
sum of its nil and attractor states. Once the structure of the two resulting
state transition graphs is known then the graph for x is obtained by simply
attaching a copy of the nil tree at each attractor node.
Theorem 3.45 If x G C(k,n), then C(k,n) = atr(z) nil(:r).
Proof Let y E C(k,n), t = /ix(y), and yo G atr(x) such that
xl Oy0 = xtO y.
Define
yi=y yo
Clearly, y0 exists and is unique, since the restriction of x to atr(x) is invertible.
It is also clear that y = yo + yi To complete the proof, it must be shown
that yi 6 nil(x), and that the decomposition is unique. We first show that
xtQyi= 0. Now
xtOyl = Â£* (y + yo)
= xl y + xl y0
= xl y + x1 y
= 0.
To establish uniqueness, assume that
y = Zq + Zi,
47
where
z0 E atr(x) and Z\ E nil(a;).
If s = max{/it(j/1),/is.(z1)}, then
xs Qy = Xs Qy0 = Xs Q z0 E atr(z).
Since there is a unique v E atr(rr) such that x3 G v = y, it follows that
2/o = zQ.
This, in turn, implies that
2/1 = z1.
The Corollary 3.46 follows immediately from the theorem and properties
of direct sum decompositions.
Corollary 3.46 #(atr(z))#(nil(:r)) = kn.
We close this chapter by showing that the state transition graph for a
linear rule is obtained by attaching a copy of its nil tree at each member of
its attractor space.
Theorem 3.47 If x E C(k,n) and y E atr(rc), then
HM = HM
Proof Assume that t > 0. Since the restriction of x to atr(s) is invertible,
there exists
yt E atr(x) such that xl Qyt y.
Now, define
Zy HM HM
48
by
Since
Â£y(z) ~ V^x{z) + z
C(k,n) = atr(z) nil(a;),
Â£y is injective. To see that Â£ maps into Hx(y) let z 6 HX(Q), and s fix(z).
Then
= a:sO (Vs + z)
= xs G ys + x3 z
= y + Q.
If z e Hx (0) \0, then
Â£y(xOz) = yxixQz) + x Q z
= ?/s_ i +I0z
= 3fy(*)
This shows that adjacency is preserved. To complete the proof, we show that
Â£,y is surjective as follows. Since Â£y is injective, Hx(y) is at least as large as
Hx (0). Since y is an arbitrary element of atr(x), Corollary 3.46 implies that
Hx(y) is no larger than Hx(0).
49
4. Rule 60
4.1 Introduction
In Chapter 2 rule 60 was shown to be linear. This rule sets a site on if
and only if its current valuation is different from that of its left neighbor.
Rule 60 thus flags the positions at which the configuration changes value
as it is read in increasing order. In this chapter, basic properties of rule 60
are developed. This rule is particularly well behaved when it operates on
spaces whose dimensions are a power of two. In this case, the graph for rule
60 is a binary tree. In the next chapter, it will be shown that the structure
of the state transition graph for any member of C(2,2m) may be expressed
entirely in terms of the structure of the graph associated with rule 60.
4.2 Basic Properties of Rule 60
In this section it will be shown that the theory developed in the previous
chapter extends naturally to operators on spaces of infinite dimension. Some
technical results are developed concerning rule 60 as an operator on Zf.
These results are then be applied to the study of rule 60 as an operator on
spaces of finite dimension. We first define neighborhood extraction operators
for doubly infinite sequences.
50
Definition 4.1 Let r,k Â£ Z+, and de/irae
z/:Zf xZ>N(k,r)
by
i/(x,i)(s) = x(i + s)Va: Â£ Zf, i Â£ Z, and s Â£ r.
Given any local map, the neighborhood extraction operator links it to a global
map in the infinite dimensional case exactly as it does when the dimension
is finite. Similarly, a global map is linear exactly when its associated local
map is.
The local map, rule 60, defines operations on many different state spaces,
and these operations are technically different functions. It is often possible to
equate a local map with the global map that it generates, but in this section
we must simultaneously consider the global maps generated by rule 60 on
different spaces. We thus define
D = Z+U{Z}.
D yields a set of indices that may be used to identify the different state
spaces upon which rule 60 operates. Now, given S Â£ D we let Rs,60 denote
the global map on Zf generated by rule 60. The next proposition identifies
the kernel of rule 60, and its corollary establishes when two configurations
have the same image.
Proposition 4.2 If S Â£ D, then
ker (R6o,s) = {Q>1}
51
Proof Let x E Zf and i E S. It follows immediately from the definition of
rule 60 that
Rs,6a(x)(i) = 0 <*=> x(i) = x(i 1).
Clearly, x(i) = x(i 1) for each i exactly when Â£ is a constant.
Definition 4.3 Let x E Zf. and define x E Zf, by
, x(i) = a:(i) + 1, Vz E S.
x(i) is said to be the compliment of x.
Corollary 4.4 If x,y E Zf, then
Rs,so (z) = RsMv) 4==* y 6 {x,5}.
Proof First notice that ir = z +1. Since ^5,60 is linear, x and y will map
to the same vector if and only if they are in the same coset of the kernel.
Repeated application of a rule causes information contained in the initial
configuration to propagate through the state space. The radius of the rule
provides an upper bound for the rate of transmission of information. De
pending on the particular properties of the rule, this upper bound may or
may not be achieved. By starting with a configuration of the form e< E Zf
and repeatedly applying a rule, an envelope identifying the range of sites that
may be on at any point in time is generated. The shape of this envelope is
defined to be the light cone for the rule. For example, figure 4.1 illustrates
the fight cone generated by 31 iterations of rule 60, for which the initial con
figuration is eo. Numbered rows correspond to configurations at indicated
52
times, black cells correspond to values of 1, and white cells correspond to
values of 0. We see that the rule does not propagate information to the left,
while it propagates information to the right at a rate of 1 site per unit of
time. The next proposition formally establishes these properties.
Figure 4.1 Light Cone for Rule 60
0
1
2
3
4
5
6
7
S
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Proposition 4.5 The following properties hold for each t > 0:
1 Rz,6o(eo)(i) = Vi < 0.
5. ^i6o(eo)(0) = 1.
& ^z,6o(eo)(2) 0 Vi > t.
4 ^Z,6o(eo)(0 1
53
Proof First, if t 0, then
RZfiO (eo) eO>
and hence, all properties hold for this case. This provides bases for inductive
proofs of each of the four properties.
1. Assume that the assertion holds for t, and let i < 0. Then
^z!6o(e)(^) = ^Z,6o(eo)(^ 1) + ^Z,6o(eo)(^)
= 0 + 0
= 0.
2. Assume that the assertion holds for t. Then
^z!"6o(eo)(0) ^Z,6o(eo)( 1) + ^Z,6o(eo)(0)
= 0 + 1
= 1.
3. Assume that the assertion holds for t. If i > t + 1, then
flzJofoXO = #z,6o(eo)(i !) +Rzj60(eo)W
= 0 + 0
= 0.
4. Assume that the assertion holds for t. Then
+ 1) = ftz,6o(eo)(i + 1 1) + Rzteo{eo){t + 1)
= 1 + 0
= 1.
54
This establishes the maximum range of sites over which 6o(eo)C0 may
equal 1. The next proposition asserts that R^eo(eo) 1 over the entire range
whenever t is of the form 2m 1. While the rigorous proof of this proposition
is somewhat tedious, the concept is very simple. Notice that in figure 4.1 the
proposition holds for each such t. In particular, when t = 15, sites 0 through
15 are on. Since rule 60 flags changes in a configuration, only sites 0 and
16 are on at t 16. The resulting configuration is thus e0 + e^. Now assume
that only site 0 is on at t = 16. Since this is exactly the situation at t = 0,
the evolution from t = 16 through t 31 must be exactly the same as the
evolution from t = 0 through t = 15. Thus at t = 31 sites 0 through 15
must be on. Similarly, if we assume that only site 16 is on at t = 16, then at
t = 31, sites 16 through 31 must be on. Since rule 60 is linear, the result at
t = 31 of both sites 0 and 16 being on at t = 16 is obtained by adding the
independent results. This shows that all of sites 0 through 31 must be on at
t 31. The proof of the next proposition simply generalizes this argument.
Proposition 4.6 lfm>0, and t 2m 1, then
Proof Proceed by induction on m. First, if m = 0, then t = 0, and hence,
t = 2m 1. To establish it for t = 2m+1 1, first evaluate R^o^o). By
Proposition 4.5,
^z,6o(eo)(^) 1 ^^ 0 ^ i ^ t.
Rz,6o(eo) eo
The proposition clearly holds in this case. Next assume that it holds for
ifi<0ori>t + l
if i 6 {0, t + 1}.
55
It only remains to consider 1 < i < t. In this case,
^%6o(eo){^) = Rz,6o(eo)(* 1) + ^Z,6o(eo)(0
= 1 + 1
= 0.
This now yields
^60 (e) = eo + et+1
Since
2771+1 1 = 2t + 1,
we have
j?2m+1l
"z^o
(eo)
^Z,6o(^z!6o(eo))
^Z,6o(eO + et+l)
^Z,60 (e0) + i?2,6o(et+l)
By the induction hypothesis,
^z,6o(o)(0 1 >^ 0 < i < t.
Since et+i is the translation of eo by t + 1, we have
#z,6o(e*+0(0 = 1 * + l<<2t + l
This now yields
Rw''Mii) = 1 =* 0 < < 2+1 1.
The actions of rule 60 on Zf and Z are compared next. Since two
different spaces are being considered, we continue to link global maps to the
56
state spaces upon which they operate, via subscripts. Similarly, subscripts
are used to identify the spaces associated with basis elements.
Proposition 4.7 Let n E Z+ and t,i En. Then
^71,60 (en,o)(0 = ^Z,6Cl(eZ,o)(^)
Proof If t = 0, then
en,o(i) = d0i = ez,o(), ViGn.
This establishes a base for the induction. Next assume that the proposition
holds for t E n 1. If i > 0, then by the induction hypothesis
^7iT6o(en>o)(0 ftn,6o(en,o)(^ 1) + ^n,o(en,o)(^)
= Rz,6o(eZ,o)(* 1) + Rz,6o(eZ,o)()
= ^z^o (ez,0 W
Site 0 is now the only remaining position at which the proposition could fail
to hold. To this case notice that
1 = n 1( mod n),
and
^n,6o(en,o)(w 1) = 0.
This shows that
<6o(en,o)(0) = 1.
We now show that the property established by Proposition 4.7 does not
hold when t = n.
57
Proposition 4.8 IfnE Z+; then
^n,6o(en,o)(0) 0
Proof
^n,6o(eri,o)(0) ^n,6o{en,o)(n 1) + ^n,60 (en,o) (0)
= 1 + 1
= 0.
The next definition introduces notations for rules 60 and 102 when they
are equated with members of Z^, and the following proposition shows that
i/iE{0,n 1}
otherwise
ifi e {0,1}
I 0 otherwise.
Proposition 4.10 If n Z+, then <$_ and Rn,6o define the same function
on ZÂ£. Similarly, <5+ and Rn,102 define the same function on ZÂ£.
Proof By symmetry, it suffices to prove the proposition for 8 and Rn,60
Let y 6 ZÂ£ and i G n. Then
8 y(i) = Y^S(l)y(i + l)
len
these definitions are reasonable.
Definition 4.9 Let n Z+. Define:
1. 8_ e ZÂ£ by
S =
2. 8+ E Z5 by
8+{i) =
58
= 6_(0)y(i + 0) + <5_(n l)y(i + (n 1))'
= y(i)+y(il)
= Rnfioiy)^) n
Next, the summation homomorphism is used to characterize both the
range of 6 and its GardenofEden states.
Theorem 4.11 rng(6_) = even(n).
Proof Clearly,
= 0,
and hence, given y G Zg,
E(<5_Oy) = Â£(<5_)Â£y = 0.
Thus, each x G rng (<5_) has even parity. The result now follows upon noting
that
[ker 6 : 1] = 2,
and that the even parity rules account for exactly half of ZÂ£.
Corollary 4.12 The GardenofEden states for <$_ are the odd parity con
figurations.
4.3 Behavior of 6_ on C(2,2m)
For the remainder of this chapter we study the operation of 6 on spaces
whose dimensions are powers of two. We therefore assume that m,n G Z+,
and that the relation n = 2m holds in all definitions and theorems. We begin
by showing that 6 is a.nilpotent operator on C(2,2m).
59
Theorem 4.13 <5" e0 = 0.
Proof By Propositions 4.6 and 4.7,
5r1Oe0 =1.
Now apply Proposition 4.2 to obtain
<501 = 0. .
Corollary 4.14 IfiEn, then
5^ O e* = 0.
Proof Notice that e* is the translation of eo by i, and hence, 5 e* is the
translation of 5" eo by i.
Corollary 4.15 IfxE ZÂ£, then
SI x = 0.
Proof Clearly
x= J2ei
x(i)=l
Thus, by the linearity of <5_,
Sl x = ^ 6" ei
i(i)=l
= 0.
Since <5_ is linear, 0 is a fixed point, and hence, the state transition graph
for 6 must have a self loop at 0. Corollary 4.15 shows that the remainder
of the graph must be a tree. Also, since ker (<$_) = {0,1}, this tree must be
binary. Notation for the levels in this tree is introduced next.
60
Definition 4.16 Define X : ZÂ£
Z by
X(x) min{Â£ > 0  Si. x 0}, Vi e ZÂ£.
X(x) is defined to be the basic level ofx. Furthermore, given j E n + 1, define
iviO') = {x ez^\x(x) = j}.
lvl(j) is said to be basic level j of ZÂ£.
The next theorem establishes the cardinalities of the basic levels.
Theorem 4.17 Let j E n + 1. Then
{1 if j=0
23 1 otherwise
Proof Clearly, only 0 satisfies
P_(x) = 0.
Since ker (5_) = {0,1.}, and 0 E lvl(0), we must have
lvl(l) = {I}
Again, since ker (<5_) = {0,1}, it follows that
#(lvl(j)) <'2#(lvl{j 1)) for 2 < j < n.
This last statement, and the fact that #(lvl(l)) = 1 imply
#(lvl(j)) < 2J_1 for 1 < j < n.
61
This establishes an upper bound for the cardinality of each level. To complete
the proof, it is only necessary to show that in order for the tree to contain
all of Zg, each level must be full. This is established as follows.
#(ZS)
T
i+E2'
1=0
i+E2'71
i=i
Since all levels are full, leaves only occur at level n. Also, each internal node
has exactly two predecessors. More generally, if A(x) = j < n, then x has
2n~j predecessors with respect to and all of them are leaves. Proposition
4.18 characterizes the action of powers of <5_ on basic levels. This result is
based on the fact that basic levels are defined in terms of the action of <5_.
Proposition 4.18 If j,l n + 1 and x lvl(Z), then:
1. If j < l, then 8i_ x E lvl(Z j).
2. If j > l, then Si. Qx G lvl(O).
Proof
1. The assertion clearly holds for j = 0, so assume that it holds for j < l.
Then
\{6lSj Qx) = lj> 0.
Since 6l_ x = <5_ 0 (8l_ J x), it is clear that
\{6l~U+1)) Qx = ljl=l{j + l).
62
2 By (1),
si x = o.
Since 0 is a fixed point for S, it follows that
Si Ox = 0 whenever j > l.
We complete this chapter with a characterization of kernels of powers of
S_ in terms of basic levels.
Definition 4.19 Let l Â£ n + 1 and define
i
K, = 1J lvl(j)
3=0
Corollary 4.20 If l Â£ n + 1, then
Kt = ker ($L)
63
5. State Transition Graphs for C{2,2m)
5.1 Introduction
The state transition graphs for rule 60 on spaces of dimension 2m were
characterized in Chapter 4. In this chapter it is shown that the structure
of the state transition graph for each member of Zm is obtainable from the
structure of the graph for rule 60. Figures 5.1 and 5.2 provide examples of
graphs for two members of C(2,4).
Application of rule 60 corresponds to circulant multiplication by <5_, which
in the current context equals 1001. Figure 5.1 illustrates the state transition
graph for this rule. This graph is actually a digraph, but arrow heads on arcs
are not required because, by convention, the direction of flow is towards the
attractor. Notice that this graph is a binary tree of height 4 with a loop at 0.
The nodes of this tree may be viewed as configurations upon which <5_ acts,
and each such configuration also represents a rule that operates on C{2,4),
and hence, has a state transition graph of its own. This concept is extremely
important, as the primary results presented in this thesis are obtained by
exploiting the dual nature of members of circulant spaces.
Several properties of rule 1001 are illustrated in figure 5.1. First since the
graph is a binary tree with 0000 as its root, this rule must be nilpotent. The
kernel consists of the constant configurations 0000 and 1111, and hence com
plimentary configurations map to the same image. Furthermore, all leaves of
this tree have odd parity, while all internal nodes have even parity.
64
Figure 5.1 State Transition Graph for 1001
Level
0001 1110 0100 1011 0010 1101 0111 1000
Figure 5.2 State Transition Graph for 0001
Level 1000 0111
0000
(!)
65
In addition, the following properties of state transition graphs for mem
bers of C(2,4) which are determined by this tree are not apparent by simple
inspection. A member of C(2,4) is invertible if its parity is odd and nilpo
tent if its parity is even. More generally, the order of the kernel of each rule
is determined by its level in this tree. Each of the 4 rules at level 3 have
kernels of order 2, 0101 and 1010, which are at level 2, both have kernels
of order 4, the kernel of 1111 has order 8, and finally, the entire space is
the kernel of 0000. Thus the leaves each possess kernels of order 1, and at
successively lower levels, the orders of the kernels double. Even parity rules
at the same level not only have kernels of equal order; they have isomorphic
state transition graphs.
While all of the odd parity rules are leaf nodes, they do not all have
isomorphic graphs. Since the graphs for invertible rules consist of collections
of cycles, in order to classify these graphs it is only necessary to determine
which cycle lengths may occur, and then count the number of occurrences of
each. For example, figure 5.2 depicts the graph for 0001, which rotates each
configuration 1 position to the right. Again, arrow heads on the arcs are
implicit because, within attractors, flow is assumed to be in the clockwise
direction. Notice that the levels benerated by rule 1001 are preserved by
rule 0001. In fact, each odd parity member of C(2,4) preserves this level
structure.
The graph for 0001 is isomorphic to the graphs for rules 1110, 1011 and
0100, and no other rules have graphs with this structure. To express this
relationship in terms of levels, simply add 1000 to each of these rules, resulting
in 1001, 0110, 0011, and 1100 respectively. These rules clearly constitute level
3 of the graph for <5_. Similarly, 1101 and 0010 have isomorphic graphs and
66
the addition of 1000 to each of them yields the rules at level 2. Addition
of 1000 to 0111 yields 1111, which is the only rule at level 1, and the graph
for 0111 is unique. Finally, the graph for 1000 consists of 16 self loops, and
1000+1000=0000, which is the only rule at level 0. Thus, although not every
pair of leaf nodes have isomorphic graphs, the graphs associated with two
such nodes are isomorphic if and only if addition of 1000 to each of them
results in even parity rules at the same level.
The remainder of this chapter is devoted to showing that generalizations
of these properties hold in arbitrary spaces of dimension 2m. Thus, for the
remainder of this chapter, we assume that m, n Z+, and n 2m.
5.2 Properties of Odd Parity Rules
Corollary 4.12 states that the odd parity configurations are the leaves of
the tree for <5_. In this section, it is shown that multiplication by odd parity
rules preserves the level structure of this tree. This fact then leads to a simple
proof that odd parity rules are invertible.
Since E is a ring Homomorphism from (ZÂ£,+,*) to (Z2,+, ), it follows
that even(n) and odd(n) are both closed under convolution and circulant
multiplication. It is now easy to show that odd parity rules leave basic levels
invariant.
Proposition 5.1 Let, x e odd(n) and j/GZJ. Then
\{xOy) = X (y).
Proof Proceed by induction on basic levels, starting with level n and work
ing downward. First, let y lvl(n). Since lvl(n) = odd(n), and convolution
67
preserves parity, we must have
I0I/6 lvl(n).
Next, assume that the proposition holds for lvl(Z), with l > 0. If y E lvl(Z 1),
then, because the tree for 8_ is full,
3 2 6 lvl(f) such that 8_ Q z = y.
By the induction hypothesis,
\(x z) = l,
and hence,
A(<5_ (x z)) = l 1.
Finally,
x y = x (<5_ z)
= (x 8) Q z
 (8 x) z
= 8 Q (x z) E. lvl(/ 1).
Corollary 5.2 Let, x odd(n) and y Then
\{x*y)=X{y).
Proof Because T,x = T,x, we have
x 6 odd(n).
Now, upon noting that
x *y = x Qy,
68
we may apply the proposition.
A graph theoretic argument next establishes the invertibility of odd parity
rules.
Theorem 5.3 If x E odd(n), then x is invertible.
Proof Let x E odd(n). Since is finite, it is only necessary to show that
x is injective. So let y E ker (x) and show that y = 0. By Proposition 5.1,
\(y) = X(x Oy) = A(0) = 0.
Clearly, only 0 E lvl(0).
The next theorem shows that any member of ZÂ£ is reachable from any
other configuration at the same level via the action of some odd parity rule.
Theorem 5.4 Let l E n + 1 and x,y E lvl(Z). Then
3 z E odd(n), such that y = z Ox.
Proof We proceed by induction on levels, starting at the top of the tree.
Let l n. Clearly,
x,y,x~l E odd(n).
Now
(y*x 1) Q x
yG {x 1 Ox)
y O (z1 x)
y Oe0
= y*e0
= y
69
Next let l < n, and assume that the proposition is true for l + 1. Then there
exist Xo,yo 6 lvl(Z + 1) such that
6 Q x0 = x and 6 yo = y.
By the induction hypothesis, there exists z 6 odd(n) such that
zQxq = y0.
Now
zQx = z O (6 O x0)
(z S) Qxo
(6 *z)Qx0
= <5_ Q (zQ x0)
= SQyo
= y
The results presented in this section constitute all of the theory of odd
parity rules required for the characterization of state transition graphs for
even parity rules. Once even parity rules have been treated, we will return
to the characterization problem for odd parity rules.
5.3 State Transition Graphs for Even Parity Rules
In this section it is shown that each even parity rule is nilpotent. The
graph for a nilpotent rule is a tree with a self loop at 0, and the indegree
of a node in such a tree is equal to either 0, for GardenofEden states, or
70
the order of the kernel. Since odd parity rules preserve basic levels and
convolution is commutative, it follows that the product of an odd parity rule
and a power of 8 must also be nilpotent. The level structure for a power
of 8_ is easily expressed in terms of basic levels, and hence, so is the level
structure of a configuration of the form 8l_ x, where x E odd(ra). Upon
showing that each even parity rule may be expressed as such a product, it
is very easy to determine both the structure of the state transition graph
for individual rules and number of different rules possessing any particular
structure.
Definition 5.5 Let I Â£n + l and define
Bi = {x 8?rl  x E odd(n)}.
Since eo G odd(ra), and eo is the multiplicative identity in Zwe have
8n_~l = e0 6n_~l eBlVlen + 1.
It will be shown that these sets yield a partition of Zwhich equals the
partition generated by the levels of the tree associated with <$_. These two
characterizations of this partition provide insight into the basic structure of
state transition graphs for members of ZÂ£.
Proposition 5.6 Let l,j n+ 1, y E Bt and z E lvl(j). Then:
1. j >n l => y O z G lvl(j (n l))
2. j < n l =Â£ y O z E lvl(O).
Proof Both (1) and (2) hold for because levels are defined in terms
of <5_. The results for arbitrary elements of Bi follow upon noting that odd
parity rules preserve basic levels.
71
Corollary 5.7 If l, j 6n + l such that l j then
Proof Let l, j Gn+1 and x,y odd(n) such that
By the proposition,
(x fflT1) O eo lvl(n l) and (y * eo G lvl(n j).
This is possible only if l = j.
Corollary 5.8 Let l G n + 1 and y Bi. Then
i=o
Corollary 5.9 Let l n + 1 and y Bi. Then
[ker (y) : 1] = 2n~l.
Proof Clearly lvl(O) = {0} and if j > 0, then
#(lvl(j)) = 2J'1.
Since basic levels are disjoint, it follows that
x ST1 = y Â£Tj.
nl
ker (y) = J lvl(j).
[ker (y) : 1] = #
J=o
nl
= 1 + 2n~l 1
72
Proposition 5.6 makes use of the fact that odd parity rules preserve basic
levels. More generally, any assertion concerning the behavior of elements of
Bi with respect to basic levels holds for all elements of Bi once it is shown
to hold for 6*~l. The following proposition provides another example of the
usefulness of this property.
Proposition 5.10 IflE{n + 1)\{0} and y E Bi, then y is nilpotent.
Proof Let l E (n + 1), x E odd(n), and y = x*8l_. We may now choose
t E Z+ such that tl > n.
Since convolution is commutative,
yl xl 5.
But,
6 =0.
We next show that Bi = lvl(Z) for each l E n. It then easily follows that
all even parity rules are nilpotent. This result, furthermore, provides a simple
means by which the kernel of any even parity rule may be determined.
Proposition 5.11 If l E n + 1, then #(Bi) > #lvl(l).
Proof Let l E n + 1 and define
wt = 8HT1 O e0.
Clearly,
wi E lvl(J).
73
If y 6 lvl(Z), then, by Theorem 5.4,
3 zy 6 odd(n) such that zy Qwi = y.
If 2/o, 2/i Â£ lvl(Z), and they are distinct, then
Zyo 0 wi = Vo Vi = wh
and hence
(V0 * e0 (zyi 5Tl) e0.
This shows that the number of different valuations of e0 with respect to
members of Bi is at least as large as the number of members of lvl(i). This
establishes the inequality.
In summary, the following inequalities have now been shown to hold:
#(Z?) > #(Uien+iBi) since each Bi C
= Xwgn+i since the Bi are disjoint
> Eten+i#(lvl(0) by Proposition 5.6
= #(Z5) since the basic levels partition .
Since the first and last terms of this sequence are equal, the two in
equalities must actually be equalities. Several technical results may now be
established.
Proposition 5.12 Given l n + 1,
= #(ivi(0).
Proof This follows immediately from the preceding sequence of inequali
ties.
74
Proposition 5.13 (Bi)ln+1 partitions ZÂ£. Furthermore, for each l E n + l,
Bi {x ZÂ£  [ker (x) : 1] = 2n~1}.
Proof By Corollary 5.7, the are pairwise disjoint. They must then
partition ZÂ£ because their cardinalities sum to its cardinality. The second
part of the proposition now follows from the definition of the Bi.
Corollary 5.14 The only rule whose kernel is all of 7% is 0, and for j > 0,
#{{x I [ker (x) : 1] = 2J } = 2nJ'1.
Proof The corollary clearly holds for j = 0 so let j > 0. Then, by Propo
sition 5.13,
{x  [ker (x) : 1] = 23} = Bnjt
and, by Proposition 8.16,
Finally, apply Theorem 4.17.
All rules have now been shown to factor into the product of an odd parity
rule and 6l_, where l n + 1. The next theorem shows that the order of the
kernel of a rule is determined by its basic level. Since even parity rules
are nilpotent, the structures of their state transition graphs are determined
by the order of their kernels. The problem of determining the structure of a
graph for an even parity rule therefore reduces to the problem of determining
its basic level.
Theorem 5.15 If l G n + 1, then
Bt = lvl(Z).
75
Proof Let l G n + 1. Since = #(lvl(l)), it suffices to show that
Bx C lvl(0
First notice that <5+ has the same level structure as <$_, because 8+ == ex <5_,
and ei G odd(n). Clearly,
8n_~l G Bh
and
* e0 = 0 e0 G lvl(Z).
Next if x G odd(n), then show that a; SlT1 G lvl(Z). Now by Corollary 5.2,
x*Sl1 G lvl(Z).
This shows that the partition of into basic levels coincides with the
partition generated by taking two rules to be equivalent if their kernels have
the same order. Since each nilpotent rule is a product of an odd parity rule
and a power of
In order to identify level structures for trees associated with even parity
rules we define a partition of for each internal basic level, and then show
that the level structure for any even parity rule is yielded by the partition
associated with the level at which that rule resides. We begin by defining
a function that assigns to each internal basic level, the height of the tree
associated with any member of that level.
Definition 5.16 Define
h : n
n
by
hti)
n
nj
V j En.
76
Proposition 5.17 Let x G lvl(j). Then:
1. y 0 V y Zg.
2. xh^~l Gj/^0Vj/ lvl(n).
Proof
1. Clearly,
MiXi)
n
nj
(n
We need only consider 81 3 6 lvl(j). If y E
j) > n.
2, then
<^O
By the preceding comment,
(Â£nj)M.j) = ,5^} where Â£ = n + s for some s > 0.
2. Now,
Thus
7Z T
h(j) 1r, where 0 < r < n j.
nj nj
nj nj
This yields
(nj)(h(j)~ 1) = + I
= n + r (n j)
< n.
But then,
where t < n.
77
Clearly,
8l_ O y 7^ OVy G lvl(n).
This shows that if a; lvl(j), then h(j) is the height of the tree associated
with x.
Definition 5.18 Let S be a non empty set and let r G Z+. Define
P : r * V{S)\{
such that
S = \J P{i), and i ^ l =$ P(i) P{1) = 0.
ier
P is defined to be an order r partition of S.
This definition differs from the usual definition of a partition only in that
the members are ordered.
It has been established that given l G n + 1, each member of level n l
has the form x Sl_, where x G odd(n). If l > 0, then x 8l_ is nilpotent,
and hence its state transition graph is a tree. Furthermore, since odd parity
rules preserve levels, the action of such a rule on basic levels, is the same as
that of 8l_. This property provides for the definition of a class of partitions
of Zj in terms of basic levels as follows.
Definition 5.19 Let j G n.
1. Define 'ipj : h(j) + 1 * n by
m =
(nj)l
n
if l < h(j)
if l = h(j).
ipj is defined to be the level j delimiter.
78
2. If l e h(j) + 1, then define
blvl fil) =
{0}
if 1 = 0
if l > 0.
blvlj is defined to be block partition j of ZÂ£, and blvly(Z) is defined to
be level l of block partition j.
Proposition 5.20 If j E n, then blvlj is an order h(j) + 1 partition of ZÂ£.
Proof If l E h(j) + 1, then blvl^Z) is nonempty, because it is a union of
basic levels. To see that the blvlj(Z) are disjoint and cover all of ZÂ£, notice
that ipj is strictly monotonically increasing with
Vj(O) = 0 and tpj{h(j)) = n.
Block partition j contains only 0 at level 0, and unions of nl consecutive
basic levels for higher levels, with the exception that the highest level will
contain less than n l levels whenever (n l) \ n.
Corollary 5.21 Let j En and l E h(j) + 1. Then
#(blvlj(i)) =
1 if 1 = 0
d+i2'1 otherwise.
Proof This expression simply sums the cardinalities of the basic levels used
to form the members of blvlj(J).
The final theorem of this section asserts that the level structure of the
tree associated with an even parity rule x coincides with the block partition
associated with the basic level of x.
79
Theorem 5.22 Let, j E n and x E lvl(j?); If l E h(j) + 1 and y E blvl^Z),
then
xl G y = 0.
If furthermore, l > 0, then
xl 1 O y / 0.
Proof Let j E n. Since odd parity rules preserve level structure, we need
only consider
G lvl {j).
Let
l E h(j) + 1 and y E blvl,(Z).
If l = 0 then the result is obvious, so assume l > 0. We know that y E lvl(s),
where
ipj{l 1) < s < <{n j)l.
Since
(8f~3)1 _ an(j jy > Sj
we must have
(8n_j)lOy = 0.
To establish the second part of the theorem, assume that l > 0. Then
(nj)(ll)=ifj(ll)
where s is as above. This implies
1
(ST3)11 y ^ 0.
80
Definition 5.23 Let j En and define
by
\j : Z2 h{j) + 1
Xj (y) = l, where y G blvl.,(Z).
This function clearly assigns to y its level with respect to any x G lvl(j).
5.4 State Transition Graphs for Odd Parity Rules
Now that even parity rules have been studied, the structures of graphs
for odd parity rules may be determined. First it is necessary to establish two
technical results that hold for binary rules of any finite dimension. The first
is a variation on a well known result from the theory of finite fields.
Proposition 5.24 Let r G Z+,s > 0 and x,y G ZT2. Then
(x + yF=x*+if.
Proof Proceed by induction on s. The case s = 0 is obvious. Assume the
theorem holds for s. Then
(x + jif*' = (1 + if)2' (1 + y)2'
= {x2 + s/2) (z2* + yv)
= X2*1
= x^'+y2'*'.
Definition 5.25 Let r G Z+ and x G ZDefine e0 + x to be the corule of
x.
81
Because eo + (eo + x)) = x, it makes sense to refer to a corule pair.
Furthermore, since corules differ only at site 0, one rule of the pair has even
parity while the other has odd parity. The next proposition asserts that the
set of fixed points for a rule equals the kernel of its corule.
Proposition 5.26 Let r 6 Z+ and x,y 6 ZÂ£. Then
xQ y y = (e0 + x) O y = 0.
Proof
(e0 + x) y = 0 <*=* eoQy + xQy = 0
=*> y + xOy = 0
$=* xQy = y.
Odd parity rules are invertible, and hence their state transition graphs
consist of a set of cycles. We next show that if x E odd(n) and y E ZÂ£, then
the x period of y is obtained by determining the level of y in the tree for
e0 + x, then rounding that number up to the next power of two. We first
formally define the notion of rounding up to the next power of two.
Definition 5.27 Let s > 0, and define
["s"2 = min{2t  s < 2}.
[Y2 is defined to be the power of two ceiling of s.
If x odd(n) then x is invertible, and hence atr(x) = ZÂ£. We may
therefore apply Definition 3.40, to obtain that px(y) yields the x period of y
for each y G Zj.
82
Theorem 5.28 Let x E odd(n) and j En such that (e0 + x) E lvl(j). Then
given y E Zg,
Px(y) = fAj(y) 12
Proof First assume
fAi(y)l2 = l.
 In this case,
y 6 ker (e0 + x),
and, by Proposition 5.26, y is a fixed point for x. Next, let
fAj(y) 12 = 2S > 1.
Then
2*1 < \j(v) < 2*.
We thus have
(e0 + x)23 1 y ^ Q and (e0 + x)2" = 0.
Now
x23 O y = (e0 + (e0 + x23)) y
= e0 y + (ejf +x23) y
= e0 y + (e0 + xfs y
=
= V
If there is a t < 2s such that x* y = y, then the smallest such t must divide
2s. But then t must be a power of two that satisfies
xtOy = y.
83
By the reverse of the above argument, we must then have
(e0 +i)i0j/ = O.
But we know that this is not so.
Theorem 5.28 provides the following means of counting cycles for odd
parity rules. We simply determine the level structure of the tree for the
corule, count the number of configurations in the block levels that round up
to a given power of two, and then divide power of two ceiling by that power
of two. The next theorem formally specifies this process.
Theorem 5.29 Let x odd(ra) and j n such that (e0 + x) lvl(j). Then
the state transition graph has cycles of period 2l whenever
0<2l< \h(j)]2
and all cycles have periods of this form. Furthermore, for such j and l, if we
let c(j,l) denote the number of cycles of period 2l, then
M
/jO)
W,)= E E 2,'i2.
\a=2i1 + l t=T/>j(sl)+l
Where M = min{2i,/i(j)}.
Proof By Theorem 5.28, all periods are powers of 2 and the period 2l occurs
if and only if there is an s with 0 < s < h(j) such that [s]2 = 2h
In order to determine the number of cycles of period 2l, it is only necessary
to determine the total number of configurations in the levels that round up
to 2l then divide this number by 2l.
The first summation ranges over the block levels of the tree for eo + x that
round up to 2l. The upper limit of this summation is M because the height of
84
the tree may not be a power of 2. The second summation ranges over the basic
levels contained in the block level referenced in the first summation. The
term 2t~1 is the number of nodes in the basic level referenced by the second
summation. This accounts for all nodes on cycles of period 2l. Division by
2l then yields the number of cycles.
Clearly, if x, y 6 odd(ra) such that their corules have equal kernels, then
they will have isomorphic state transition graphs, while if their corules have
different kernels then their state transition graphs will differ in the number
of 1cycles. This argument serves to prove the final result of this section.
Proposition 5.30 Let x odd(n) and j 6 n such that (e0 t x) G lvl(j),
then the number of rules with state transition graphs isomorphic to that ofx
is #(lvl(j)).
This completes the proof that the level structure of rule 60 on a space
of dimension 2m provides a means to determine the possible isomorphism
classes of state transition graphs for members of Zm. Since cardinalities
of the basic levels are known, we immediately obtain the number of rules
associated with any isomorphism class.
5.5 Example Algorithms
State transition graphs for two members of C(2,16) are determined in this
section. In the first example, we let Xq = 1100101000011000. Since this rule
has even parity, it is nilpotent and its state transition graph is a tree. In order
to determine the structure of this tree it is only necessary to determine the
basic level at which Xq resides. This is accomplished by repeatedly applying
85
the following procedure to generate inverse images with respect to <$_ until
an odd parity rule is obtained. Since complimentary configurations have a
common image under rule 60, Xi(0) may be defined arbitrarily. Then, given
i > 0, define
Xi (i 1) if x0(i) = 0
xi (i 1) + 1 if xq (i) = 1.
Sites in such a configuration will differ from their left neighbors at exactly
those i for which Xq (i) = 1.
Table 5.1 illustrates the process of taking inverse images with respect to
<5_. The first application of the above procedure yields the configuration Xi,
which also has even parity. The process of taking inverse images is iterated
until an odd parity configuration is obtained at X3
Table 5.1 Examples of Pre Images for 6
x0 11001 0 1000011000
x: 0 1110 0 111110 1111
x2 0101110101001010
x3 1001011001110011
Since the process was repeated 3 times, we conclude that Xo resides at
level 16 3 = 13, and has. a kernel of order 23 = 8. Block level 0 for
Xq = {0}, block levels 1 through 5 each consist of 3 basic levels, and block
level 6 contains only basic level 16. The number of nodes at each block level
for the rule is simply obtained by summing the numbers of nodes in each of
its constituent basic levels. This situation is illustrated in table 5.2. Since Xq
86
moves configurations down by 3 basic levels, the external nodes of the tree
are obtained from basic levels 14, 15, and 16.
We next determine the graph for yo = 0100101000011000. This rule has
odd parity, and hence, is invertible. To obtain a count of the cycles in its
graph, we must first determine the level of y0 + e0. But yo + e0 = Xo, and this
is the rule considered in the previous example. We thus partition the block
levels of the tree for Xq into sets that round up to the same power of 2. We
then determine the total number of configurations associated with each class
and divide by the appropriate power of 2 to obtain the number of cycles of
that period. This process is illustrated in table 5.3. In this example, the 8
configurations at levels 0 and 1 reside on 1cycles. The 56 configurations at
level 2 yield 56/2 = 28, 2cycles. At levels 3 and 4, we have a total of 4032
configurations resulting in 1008, 4cycles. Finally, the 61440 configurations
at levels 5 and 6 yield 7680, 8cycles.
87
Table 5.2 Level Structure 1100101000011000
Basic Block Internal External Total
Level # Nodes Level Nodes Nodes Nodes
16 32768 6 0 32768 32768
15 16384 5 4096 24576 28672
14 8192
13 4096
12 2048 4 3584 0 3584
11 1024
10 512
9 256 3 448 0 448
8 128
7 64
6 32 2 56 0 56
5 16
4 8
3 4 1 7 0 7
2 2
1 1
0 1 0 1 0 1
88
Table 5.3 Cycle Structure for 0100101000011000
Basic Total Block Nodes at Total
Level Nodes Level Level Nodes Period Cycles
16 32768 6 32768 61440 8 7680
15 16384 5 28672
14 8192
13 4096
12 2048 4 3584 4032 4 1008
11 1024
10 512
9 256 3 448
8 128
7 64
6 32 2 56 56 2 28
5 16
4 8
3 4 1 7 8 1 8
2 2
1 1
0 1 0 1
89
6. Squares of Binary Linear Rules
6.1 Introduction
Properties relating to the operation of squaring binary, linear rules are
studied in this chapter. First four classes of linear operators on circulant
spaces are defined, then the circulant space structure preserved by each class
is identified. It is furthermore shown that the composition of two operators
of the same type is also an operator of that type (each class may therefore be
said to be transitive). The operation that maps a member of ZÂ£ to its square
is shown to be linear, and matrices for this operation are identified. Finally,
the four operations introduced in the next section are used to developed
structure pertaining to the operation of squaring linear rules.
Throughout this chapter, it is assumed that l,m,n Â£ Z+ with n = Im.
Given this relation, if i Â£ n, then we may write i = jl + r, where j Â£m and
r Â£ l. Conversely, for each such j and r, an expression of the form jl + r
yields an element of n. It is thus possible to replace a summation indexed
by elements of n with a pair of summations indexed by elements of l and m.
This substitution is used in several of the proofs presented in this chapter.
6.2 Circulant Space Homomorphisms
Of the four linear operators that are defined in this section, the first three
are injective, while the last collapses structure. The definitions are stated so
90
that the first three operations have C(2, l) as their domain and C(2, n) as their
range, while the last operator has domain equal to C(2,n) and range equal
to C(2,l). Each operator is subscripted by a pair of integers, with the first
integer identifying the dimension of its domain. For each injective operator,
the dimension of its range is yielded by the product of the subscripts, and
the dimension of the range of the last operator is obtained by dividing the
first subscript by the second.
Definition 6.1 Define : C(2, l) C(2,n) by
$i,7nS(i) 1 x(i/m) if 77i  i
1 otherwise
Definition 6.2 Define C(2,n) by
= x(i mod l) Vi E n.
Vi E n.
Definition 6.3 Define :C(2, l) > C(2,n) by
, v x(i) if i El
Oi,mx(i) = < ViEn.
I 0 otherwise
The first of the injective operators spreads a configuration out by inserting
m1 zeros after each entry, the second repeats a configuration m times, and
the last copies a configuration once then pads the remainder of the image
with zeros.
For example, if Z = 4, m 3, and n 12, then these operators map
x = (a, b, c, d) E C(2,4) into C(2,12) as follows:
$4,30*0 = (a, 0,0, b, 0,0, c, 0,0, d, 0,0),
$4,30*0 = (a,.&,c,d,a,6,c,d,a,6,c,d),
4,30*0 = (a, &, c,d, 0,0,0,0,0,0,0,0).
91
Definition 6.4 Define AnjJn : C(2, n) C(2,1) by
An,m(x)(i) = x(jl + i)V i G Z.
i&m
In order to explain the behavior of this operator, we partition n into
m segments of length Z, and associate members of Z with offsets into the
segments. Given x G C(2,n), y G C(2, Z), and i G Z, AntTn(y)(i) is the sum
over all segments of the valuations of x at offset i into those segments. For
example, let
n = 12, m = 3, and l = 4.
Now if
x = (a,b,c,d,ej,g,h,i,j,k,l) e C(2,12),
Then
Ai2,3(a;) (o + e + Z,6 + / + j, c + <7 + fc,d + Zi + Z) G C(2,4).
When m 1, A]7n is the identity, while it is the summation homomor
phism when m = n.
A series of technical results concerning these operators are now presented.
We begin with $j,m) which preserves all circulant space structure.
Proposition 6.5 rng= {a: G C(2,n)  m\i =$ x(i) = 0 V i G n}.
Proof (C) This is immediate from the definition.
(D) Let y G C(2, n) such that y(i) = 0 whenever vn\i and define x G C(2, Z)
by
s(j) = v(mj)Vj Z.
Clearly
= y.
92
Next we see that preserves the operation of conjugation.
Proposition 6.6 If x Â£ C(2,l) then
^l,m{x) *&l,m{x).
Proof Let x Â£ C(2, l). First notice that since m \ n, we have
m  i <=> m  i V i Â£ n.
Thus if m \ n, then
Â§i,m(x)(i) = 0.
It only remains to consider Â§liTn(x)(mj), where j Â£ l. Again, since m \ n, we
have
mj = ml mj = m(l j).
This yields
$i,m(x)(mj) = Â§l>m(x){mj)
= x{j)
= x{j)
= Â§l,m{x)(mj).
The next theorem shows that $/)7n is injective and preserves all circulant
space operations.
Theorem 6.7 maps C(2, l) isomorphically onto its range.
Proof Let rc0, Â£ C(2,l), and define yo,y\ Â£ C(2, n) by
ys = Ql,m{Xs)'tf S Â£ 2.
93
To establish injectivity, let r G l, and assume that
x0(r) ^(r).
Then
Vo(rm) / yi(rm).
Since scalar multiplication is obtained by a finite number of additions,
linearity is established once it is shown that addition is preserved. By Propo
sition 6.5, we need only consider i G n of the form i = mj, where j G l. In
this case,
$j,n(zo + 3i)(0 = (x0 + xi)(j)
= Z0(j)+Xi(j)
= ^*2,771 (^o) (0 T $2,771 (Zl)(i).
Next consider circulant multiphcation. If i, j G n, then
(m  j and m \ (j + i)) =$ m  i.
Thus if m\i, then given j G n, either
m \j or m \ (i + j).
In either case,
yo{j)yi(i + j) = 0,
and hence,
Vo yi{i) = Y ItoC7)!/i(* + j) = 0
jn
Finally, assume that m \ i, and evaluate yo y\(i) .If i = rm, then
m\ j = y0(j) = yi(i+j) = 0.
94

PAGE 1
ALGEBRAIC PROPERTIES OF LINEAR, BINARY CELLULAR AUTOMATA by John Weigand B.A., University of Colorado, 1971 A thesis submitted to the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Computer Science 1996 I
PAGE 2
This thesis for the Master of Science degree by John Weigand has been approved by John Clark Tom Altman Date (
PAGE 3
Weigand, John (M.S., Computer Science) Algebraic Properties of Linear, Binary Cellular Automata Thesis directed by Assistant Professor Jay Rothman ABSTRACT Algebraic properties for linear cellular automata over Z2 are developed in this thesis. These properties are then used in the characterization of state transition graphs for this class of rules. The case n = 2m is treated first, and it is shown that odd parity rules in this space are invertible, while even parity rules are nilpotent. The operation of squaring linear rules is studied, and these results are applied to the characterization of idempotent linear rules over Z2 for any n. Idempotent rules are used to generate direct sum decompositions of the state space, and it is shown that linear rules are "well behaved" with respect to these decompositions. It is furthermore shown that state transition graphs for rules defined on spaces of arbitrary dimension may be characterized by applying the techniques developed for: the case n = 2m termwise to these decompositions This abstract accurately represents the content of the candidate's thesis. I recommend its publication. Signed Jay Rothman lll
PAGE 4
CONTENTS Chapter 1. Introduction 0 0 0 0 0 0 0 0 0 0 0 0 1.1 An Informal Introduction to Cellular Automata 1.2 History of Cellular Automata .......... 1.3 1.4 2. 2.1 2.2 2.3 2.4 3. 3.1 3.2 3.3 3.4 3.5 4. 4.1 4.2 4.3 Applications Overview of Thesis Fundamental Concepts Introduction Notation ... I 0 I 0 0 I I o I 0 I I o o 0 I o o o o o o 0 OneDimensional Cellular Automata Linear Cellular Automata Circulant Algebra ..... Introduction . Matrix Operations Circulant Spaces 0 I I I I o I I I 0 o I I I I I I o o I 0 I I o 0 1 o The Summation Homomorphism State Transition Graphs Rule 60 ........... I I I o o I I I I I o o I I I I I I o I I I I Introduction Basic Properties of Rule 60 Behavior of 8_ on C(2, 2m) .. lV 1 1 4 8 9 12 12 12 13 18 25 25 25 36 41 43 50 50 50 59
PAGE 5
Chapter 5. State Transition Graphs for C(2, 2m) ............... 5.1 5.2 5.3 5.4 5.5 6. 6.1 6.2 6.3 6.4 7. 7.1 7.2 7.3 Introduction o I I o 0 o o o o I I 0 0 0 Properties of Odd Parity Rules State Transition Graphs for Even Parity Rules State Transition Graphs for Odd Parity Rules Example Algorithms ...... Squares of Binary Linear Rules Introduction Circulant Space Homomorphisms Properties of the Squaring Operator An Embedding of C(2, l) into C(2, 2l) Idempotent Binary Rules ..... Introduction General Properties of Projections . . Characterization of Projections on C(2, k) 7.4 The Lattice of Projections ... 7.5 Direct Sum Decompositions 7.6 An Isomorphic Structure 8. Structure of C(2, n) ..... 8.1 8.2 8.3 8.4 8.5 Introduction 0 Establishment of a Reference Conjugate Level Structures C(2, k) Invertible Rules Product Graphs v 64 64 67 70 81 85 90 90 90 105 116 119 119 119 121 127 137 152 157 157 158 175 178 183
PAGE 6
Chapter 9. Conclusions 9.1 9.2 Summary Related Problems References Vl 187 187 188 190
PAGE 7
1. Introduction 1.1 An Informal Introduction to Cellular Automata Cellular Automata provide mathematical models for spacially and tempo rally discrete dynamical systems. An informal definition of cellular automata is presented in this section, and a rigorous definition of onedimensional cel lular automata is presented in the next chapter. A cellular automaton is an ordered pair consisting of a state space and a global map. If A is a finite, nonempty set, then it is said to be a state alphabet, and its members are defined to be state symbols. If n > 0, then zn is said to be an ndimensionallattice, and members of zn are called sites or cells. Given a state alphabet and a lattice, an assignment of symbols from the state alphabet to the cells of the lattice is called a configuration or a state, and the set of all possible configurations is called a state space. While it is not necessary that state alphabets possess algebraic structure, they are usually finite rings. Global maps are operations on state spaces In order to identify this class of operators, the concepts of neighborhood, neighborhood state, and local map must first be presented. A neighborhood is simply a finite nonempty subset of zn' and a neighborhood state is an assignment of symbols from the state alphabet to the sites in a neighborhood. For a fixed neighborhood and state alphabet, a local map is a function from the set of neighborhood states to the state alphabet. If Lis a local map associated with a neighborhood N 1
PAGE 8
and state alphabet A, then the global map GL, which operates on the state space X = Azn may be defined as follows. If X E X and c E zn, then a neighborhood stateS may be defined by S(b) = x(c +b) 'r/ bE N. Informally, S is determined by the states of the cells in the neighborhood of cell c. Finally, G L : X X is defined by GL(x)(c) = L(S) 'r/ x EX, c E zn. Upon applying a global map to a configuration, the valuation of the result at any given cell is thus yielded by the action of the local map on the neigh borhood state associated with that cell. The following simple example should clarify the preceding definition. The behavior John Conway's gameoflife, which is the best known example of a cellular automaton, may be described as follows. The cells may be thought of as squares on an infinite chess board which is the lattice. We may associate each square with a member of Z x Z, thereby formalizing the lattice structure and providing a coordinate system. The state alphabet for this automaton is the set of binary digits, so that at any point in time, each cell is associated with either a 0 or a 1 (off or on). The neighborhood for this automaton is yielded by N = {(i,j) E z X z I i,j E {1,0, 1}}. Each cell may thus be associated with a nine cell neighborhood that consists of that cell and the eight cells that share an edge or corner with it. The local map, which assigns a binary digit to each of the 29 = 512 possible neighborhood states, is defined as follows. If a cell is off, then it remains off 2
PAGE 9
unless exactly three of its eight neighboring cells are on, in which case the cell is set on. If the cell is on, then it remains on if and only if either two or three of its neighboring cells are on. Application of the local map to each square of the board then yields the global map. There are many variations on the above definition of cellular automata. First lattices need not be infinite in extent. For example, if m, n E z+, then serves as an example of a finite lattice. Lattices need not even be rectangular; honeycomb patterns with hexagonal cells have been used. There are also variations on the way in which local maps are defined. Local maps may be defined so that they are dependent upon state values of neighboring cells at times prior to the current time. Such local maps are said to possess memory. It is also possible that local maps yield a probability distribution on the state alphabet. The state symbol associated with such a local map is then selected randomly with respect to the distribution. Cellular automata whose local maps are defined in this way are called probabilistic cellular automata. The local map for the gameoflife is easily specified by simple rules in spite of the fact that there are 512 different neighborhood states. Generally, local maps are defined by tables in which all neighborhood states and their associated state symbols are specified. It should be noted that the number of global maps associated with a particular state alphabet and neighborhood may be very large, even when the alphabet and neighborhood are small. For example, there are 2512 different local maps associated with the binary alphabet and nine cell neighborhood used in the gameoflife. While there are many variations on the structure of cellular automata, even the simplest classes are not yet well understood. The class of cellular automata for which the state alphabet is Z2 the cells are arrayed in one 3
PAGE 10
dimension, the lattice is finite, and the global map is linear is clearly much more amenable to mathematical analysis than most of the variations pre sented above, yet many questions concerning this class remain unanswered. 1.2 History of Cellular Automata The first cellular automaton was introduced by John von Neumann [70] in the late 1940s. He was looking for a rigorous mathematical model of a Turing machine that additionally had the capability of being able to replicate itself. The lattice for this automaton is Z x Z, and the state alphabet consists of 29 symbols. This alphabet is not a ring, but some of the symbols still possess algebraic properties, because they act as OR, and AND gates. Von Neumann completed the general design of this automaton and spec ified most of the operations of this machine in detail, but some difficult timing issues associated with tape operations were left unresolved. After von Neumann's death, Arthur Burks studied his manuscripts, then edited and published the above cited work. He also noticed that certain design features associated with selfreproduction could be utilized in the tape oper ations, thereby eliminating the timing problems. Burks then published the improved design. He conjectured that von Neumann must have been aware of these improvements himself, because he had incorporated them into his design of the constn.iction unit. Von Neumann's friend and associate Stanislaw Ulam also did pioneering research on cellular automata. He used early electronic computers to model the iteration of global maps on various starting configurations. The resulting patterns, which were suggestive of growth patterns of crystals, showed that 4
PAGE 11
cellular automata could be used to generate complex geometric structures. Ulam's work was years ahead of its time, and it is only in the last decade it has been advanced. It is important to note that von Neumann and Ulam were two of the most prolific mathematicians of the twentieth century. The remainder of the early work on cellular automata was primarily con cerned with problems in automata theory. Burks, Thatcher, Moore, Holland and Myhill all made contributions in this area. Works of these researchers, and the above mentioned work of Ulam may be found in Burks [72]. In 1968, E.F. Codd [71] exhibited of a cellular automaton capable of universal computation and selfreproduction that only required an eight symbol state alphabet. In the 1970s interest in cellular automata automata theory dwindled, and the field remained quiet until the early 1980s. In the thirty years since Ulam first used computers to perform cellular automata simulations, they had be come extremely powerful. In particular, processor speeds had increased dra matically, and and graphics capabilities had become very sophisticated. This allowed modern computer scientists and mathematicians to perform exhaus tive studies of certain classes of cellular automata. It should be noted how ever, that even with todays massively parallel computers, the combinatorial properties of cellular automata are such that exhaustive searches are only possible in special cases. In the last ten years, the study of cellular automata has undergone ex plosive growth. Computer simulation techniques have become very sophis ticated, and results from diverse areas of mathematics have been applied to cellular automata theory. Stephen Wolfram [2] [4] is one of the better known mathematicians in5
PAGE 12
volved in the resurgence of interest in cellular automata theory. He used computers to gather statistical data on cellular automata then used these empirical results to formulate general theory. He was concerned with the classification of rules in terms of both algebraic properties and the phe nomenological results of computer simulations. In 1984 Martin, Odlyzko, and Wolfram [1] published a paper in which the theory of linear cellular automata was studied within the context of polynomials over finite fields. Graph theory is another branch of mathematics that has been successfully applied to the study of cellular automata. Given a cellular automaton for which the state space is finite, a directed graph may be constructed by using the configurations as nodes, and directing an arc from node x to node y if the transition rule maps x to y. This digraph is called the state transition graph for the automaton. Given a node in a state transition graph, its trajectory under repeated application of the rule may be traced from node to node simply by following arcs. Since the state space is finite, this process must eventually result in a state being repeated. Furthermore, since cellular automata are deterministic, once such a repeating state has been reached, the system becomes periodic. The states which may be repeated thus reside on cycles in the graph, while the others reside in trees connected to the cycles. The classification of state transition graphs is currently one of the primary areas of study in cellular automata theory. The above cited work of Martin, Odlyzko, and Wolfram was one of the first contributions to the solution of this problem. In 1985, Guan and He [27] solved the classification problem for linear cellular automata over finite fields, by studying eigen values of circulant matrices over those fields. In 1992 Wuensch and Lesser [75] published an atlas of basins of attraction for state transition graphs of onedimensional cellular 6
PAGE 13
automata. DeBrujin graphs may also be used in the study of cellular automata. Voorhees [28] incorporates them into algorithms which may be used to de termine predecessors of configurations with respect to certain classes of rules, and Sutner [48] utilizes them in a quadratic time algorithm which determines reversibility of onedimensional cellular automata. The problem of reversibility of cellular automata of higher dimensions was shown to be undecidible by Kari [20]. He accomplished this by reducing an unsolvable problem con cerned with determining if a certain class of tilings of the plane is possible to the reversibility problem. Information theoretic techniques may also be applied to the study of cel lular automata. Certain cellular automata may be endowed with measures which are preserved by the transition rule. Ergodic properties may then be studied within this context. Cellular automata that exhibit selforganizing behavior may be used to model processes whose asymptotic behavior corre sponds to reverse entropy. Since cellular automata transform strings, they may be used to model productions in formal language theory. In this way cellular automata may be classified in terms of the classes of formal languages which they leave invariant. This is a brief summary of some of the branches of mathematics that have been applied to the study of cellular automata. In addition, much of the current research in cellular automata theory is performed by computer simulations. This has resulted in the development of new algorithms and data structures. In particular, genetic algorithms are proving increasingly useful in finding cellular automata rules that possess particular properties. 7
PAGE 14
Richards [16] presents an interesting example in which genetic algorithms are used to find a local map that can be used to model .the growth of a particular type of crystal. 1.3 Applications The advances in microprocessor technology in the 1980s finally made it feasible to use cellular automata as models for physical processes. The problems best suited for modeling by cellular automata are those in which evolution of the state space is determined by local interactions. Examples include problems concerning turbulence, diffusion, wave propagation, crystal growth and particle interactions. Artificial life is another area of research that draws heavily on cellular automata theory. Here cellular automata have been used to model biological systems from microscale molecular and cellular behavior to macroscale processes such as the spread of diseases and predator prey relationships. 1.4 Overview of Thesis In this thesis, algebraic properties of linear cellular automata defined on Z2 are studied. A cellular automaton is linear if its state space is a module and its global map is a linear transformation. These notions will be formally presented in detail in Chapter 2. Most of the theory developed in this thesis concerns relationships between graph theoretic and algebraic properties of linear cellular automata. While a great deal of theory has already been developed concerning state transition 8
PAGE 15
graphs for cellular automata, very little work has been devoted to the problem of describing the algebraic properties of several different rules within the context of the state transition graph for one particular rule. This thesis addresses this problem by developing theory in a space whose members may be considered to be both configurations and global maps. In addition to yielding efficient methods for determining the structure of state transition graphs for a large class of rules, this approach exposes previously unknown algebraic structure of linear cellular automata. In Chapters 2,3, and 4 several well known results concerning cellular automata are presented. Although these results are often alluded to in journal articles, they are seldom formally developed. In the interest of completeness, all properties of cellular automata required for the theory presented in this thesis are formally developed. The results presented in Chapters 5 through 8, pertain to relationships between algebraic and graph theoretic properties of linear cellular automata. The following as a summary of the material treated in this thesis Chapter 2 The mathematical notation used in this thesis is introduced first. Then onedimensional cellular automata are formally defined, and their basic algebraic properties are developed. Finally linear cellular automata are identified, their matrices are characterized, and several technical results concerning them are established. Chapter 3 In this chapter, circulant spaces are defined and it is shown that the theory of linear cellular automata may be presented within this context. While the theory presented in this chapter has been developed in other contexts, its use in this thesis provides a novel approach to the study cellular automata. 9
PAGE 16
Chapter 4 The structures of the state transition graphs for rule 60 (this rule is defined in Chapter 4) over a binary space of dimension 2m are characterized. The graphs for this class of rules are shown to be a complete binary trees whose heights equal the dimension of the space These graphs will be used in Chapter 5 as the reference point for the development of algebraic properties of linear rules which operate on zr. Chapter 5Given a fixed value of m, it is shown that the structure of a state transition graphs for a member of the binary circulant space of dimension 2m may be obtained from the structure of the graph for rule 60. For such dimensions, the algebra is particularly simple, because all global maps are either invertible or nilpotent, with odd parity rules being invertible, while even parity rules are nilpotent. The graphs associated with these classes of rules are thus either collections of cycles or trees respectively. Chapter 6The theory of squaring linear rules is developed in this chapter. It is shown that there are two general structures associated with this operation, depending on the parity of the dimension. This operation is shown to be linear, and the general forms of the matrices for the two cases are identified. Chapter 7 Idempotent members of circulant spaces are characterized in this chapter. Since a rule is idempotent if it equals its own square, the results developed in this chapter are based on those established in Chapter 6. It is shown that idempotent operators may be used to obtain direct sum decompositions of circulant spaces. Also it is established that idempotent maps may be endowed with a natural partial ordering thereby yielding a distinguished decomposition, and that circulant space operations are well behaved with respect to this decomposition. Finally the structure of this decomposition for a space of dimension 2n is shown to be obtainable from 10
PAGE 17
that for a space of dimension n. Chapter 8The results of Chapters 4, 5, 6 and 7 are merged in this chapter. If l is odd and the terms of the canonical decomposition of C(2, l) are fields, then it is shown that any global map on a space of dimension l2r, where r 0, splits into a sum of nilpotent and invertible components. Techniques developed in Chapter 5 are then adapted so that they may be used in this context Chapter 9 In this chapter the results established in this thesis are briefly summarized and several generalizations of these results are suggested. Partic ular attention is paid to the question of whether or not the theory developed in Chapter 8 can always be applied to circulant spaces of any dimension. 11
PAGE 18
2. Fundamental Concepts 2.1 Introduction In this chapter notational conventions are introduced, and basic theory of cellular automata is developed. Since this thesis treats the theory of linear cellular automata, special attention is paid to this case. While most of the results presented in this chapter are well known, they are generally cited in journal articles without proof. Since these results are important, and proofs are infrequently published, complete proofs of the fun damental properties of cellular automata required for this thesis are presented in this chapter. 2.2 Notation The notation used in this paper is based on set theory. We begin by defining w = {0, 1,2, ... }. w is said to be the set of finite ordinal numbers. Each ordinal number is equal to the set of ordinals that precede it. Thus 0 = 0, and more generally, if nEw, then n = {0, 1, ... n 1}. We furthermore define z+ = w\{0}. If k E z+, then we define zk = (k, +, ). 12
PAGE 19
It is well known that Zk is a ring, and if k is prime, then Zk is a field In cellular automata theory vectors are often denoted by strings. For example, 0, 1, 1, 0)" and "10110" are alternate notations. String notation provides for the use of underbars to represent repeating sequences. Thus 132 represents the string that repeats the sequence 132. Underbars will most often be used to represent constant strings such as .Q and 1. The following notational conventions will also be observed. If Sis a set, then "P(S)" denotes its power set, and "#(S)" denotes its cardinality. The symbol "D" is read as "end of proof", and "3" is read as "such that". 2.3 OneDimensional Cellular Automata Formal definitions of onedimensional cellular automata are presented in this section. First it is necessary to introduce some concepts pertaining to linearity LetS be a nonempty set, and define is a module of dimension #(S) over Zk, and Sis said to be the index set for this module. If k is a prime, then is also a vector space. Let S and T be nonempty sets. A function is said to be linear if for each x, y E Zk, and j E k, A(x + y) = A(x) +A(y), and A(jx) = jA(x). 13
PAGE 20
Generally, in order to establish that a transformation on a module is linear it is necessary be show that it preserves scalar multiplication. ,However, since multiplication by a scalar from zk may be obtained by iterated additions, linearity of a transformation follows upon showing that addition is preserved. Similarly, in order to show that a subset of module is a submodule, it is only necessary to show that it is closed with respect to addition. Definition 2.1 Let S be a non empty set. If i E S and z E z+, then define by ek,s,i(j) = 8i,i V j E S. (ek,S,i)iES is defined to be the canonical basis for zr This definition, while precise, often requires more symbols than are nec essary. If k is known from context, then the notation "es,/' suffices. If Sis also known, then the conventional "e/' may be used. Let k,n E z+, and define z;: is defined to be thendimensional state space over zk. In cellular automata theory members of z;: are called configurations, and members of n are called sites or cells. If x E z;: and i En, then x(i) represents component i of x. Furthermore, if j E n, then the expression i + j is evaluated modulo n. Notice that we have used the term dimension in two different senses. z;: is onedimensional in the sense that the components of any member may 14
PAGE 21
be thought of as being situated along a line, while this space clearly has dimension n as a module. The meaning of this term will be clear from the context in which it is used. Two classes functions are required in order to define a cellular automaton. First the local map must be specified. This function is then used to define the global map. Before defining local maps, we must formalize the concept of neighborhood. Qefinition 2.2 Let r E z+. Define r = { r, r + 1, ... 'r1, r }. r is said to be the set of radius r indices. Definition 2.3 Let k, r E z+. Define N(k,r) ={a I a : Zk} N(l, r) is said to be the space of radius r neighborhoods over Zk. Definition 2.4 Let k, r E z+ and define T(k,r) = {rlr: N(k,r) Zk} T(k, r) is said to be the space of Zk valued, radius r local maps. Since N(k, r) is the set of functions from r to Zk, it is a module of di mension 2r + 1. Furthermore, it contains k2r+l elements. This implies that T(k, r) is a module of dimension k2r+l that contains kk2r+l elements. Spaces of local maps may clearly be very large, even for modest values of k and r. 15
PAGE 22
Definition 2.5 Let k, n, r E z+. Define v : X n N (k' r) by v(x, i)(s) = x(i + s), \:1 x E i En, s E f. v is defined to be the radius r neighborhood extraction operator on Zk, and v(x, i) is defined to be the radius r neighborhood of x at i. The neighborhood extraction operator simply copies segments of vectors centered at a site onto vectors of smaller dimension. Thus if x, y E Zk and i E n, then the process of adding x and y pointwise then extracting the neighborhood about i yields the same result as does that of first extracting the neighborhoods about i separately and then adding them. The following proposition follows immediately from this observation. Proposition 2.6 The operation of neighborhood extraction is linear. Given a configuration x E Zk, and a site i En, v associates this pair with the member of N(k,r). This allows global maps to be defined in terms of local maps as follows. Definition 2.7 Let, k,r,n E z+, with 2r + 1 T E N(k,r). Define by AT(x)(i) = T(v(x, i)) \:1 X E and \:1 i En, AT is said to be the global map on zk defined by T. 16
PAGE 23
Definition 2.8 Let, k, r, n E z+ with 2r + 1 n and define A(k,r,n) = {A7 IT E T(k,r)}. A( k, r, n) is said to be the space of radius r cellular automaton rules on Zk. The following proposition follows immediately from the definitions. Proposition 2.9 Let k, r, n E z+ with 2r + 1 n, i,j E n, and A E A(k, r, n). Then v(x,i) = v(y ,j) =::::::;. A(x)(i) = A(y)(j) The evaluation of a cellular automaton operator at a site in a configuration is thus determined by the valuations of the configuration in the neighborhood of that site and not by its position. Technically, cellular automata rules are elements of T(k, r), but cellular automata operators are often called rules and equated with the local maps that define them. This relationship may be expressed in terms of the following isomorphism. Definition 2.10 Let, k, r, n E z+ with 2r + 1 n and define (k,r,n: T(k,r) A(k,r,n) by For each n E z+, this operator simply pairs local maps with the global maps which they define. The next theorem shows that A(k, r, n) is a vector space with respect to pointwise addition, and that (k,r,n is a vector space isomorphism. 17
PAGE 24
Theorem 2.11 Let, k, r, n E z+ with 2r + 1 n. If To, Tl E T(k, r), then Proof Let x E Z/: and i E n. Then (k,r,n(To)(x)(i) + (k,r,n(TI)(x)(i) To(v(x,i)) + T1(v(x,i)) (To+ T1)(v(x, i)) (k,r,n(To + T1)(x)(i). 0 We may now define onedimensional cellular automata. Definition 2.12 Let k,r,n E z+, T E T(k,r), and Ar E A(k,r,n). The ordered pair (Z/:, Ar) is defined to be a onedimensional cellular automaton. 2.4 Linear Cellular Automata Linear global maps possess a great deal of structure. In this section linear local maps are identified, and it is shown that a global map is linear if and only if its defining local is. We begin by defining dot products, and establishing some of their basic properties. These results are similar to familiar results concerning dot products on Euclidean spaces. Definition 2.13 Let k E z+ and letS be a finite, nonempty set. Define by < x,y Lx(s)y(s), "i/ x,y E sES Then < x, y > is said to be the dot product of x andy. 18
PAGE 25
Proposition 2.14 < > is linear in both arguments. Proof Let x,y,z E ZJ:. Then < X' y + z > = LX ( 8) (y + z) ( 8) sES L x(8)(y(8) + z(8)) ses L(x(8)y(8) + x(8))z(8) ses L x(8)Y(8) + L x(8)z(8) sES sES < x, y > + < x, z > Scalar multiplication is preserved since multiplication by an element of Zk corresponds to a finite number of additions. Linearity with respect to the first argument follows by symmetry 0 \ Since local maps are functions from N(k, r) to Zk, they are functionals. The following theorem characterizes the linear functionals on N(k, r). Theorem 2.15 Let k E z+. LetS be a finite, nonempty set. If then F is linear if and only if there exists X E such that F(y) =< y x > Vy E Zf. Proof ({:=::)If X E then< ,X> is linear by Proposition 2.14. ( ==>) Assume that F is linear, and define X E by x(8) = F(e8 ) V 8 E S. 19
PAGE 26
Now let y E and show that F(y) =< y, X>. First notice that Next, F(y) F(Ly(s)es) sES sES sES LY(s)x(s) sES < y,x >. 0 Corollary 2.16 If k, r E z+ andrE T(k, r), then r is linear if and only if there exists a E N ( k, r) such that r({J) =< {3, a> V f3 E N(k, r). Proof Simply substitute N(k, r) for Sin the theorem. 0 Definition 2.17 If k,r E z+, T E T(k,r) and a E N(k,r) such that r({J) =< {3, a> V f3 E N(k, r), then a is said to generate r. Corollary 2.16 states that there is a natural correspondence between mem bers of N ( k, r) and the subset ofT ( k, r) that consists of the linear local It has already been shown that N ( k, r) is a module. The next theorem asserts that the set of linear local maps constitute a submodule of T(k, r) that is isomorphic to N(k, r) via this correspondence. 20
PAGE 27
Theorem 2.18 Letk,r E z+, a0,a1 E N(k,r) andT0,T1 E T(k,r) such that ai generates Tj 'II j E 2. Then To+ T 1 is a linear map. Furthermore, To+ T 1 is generated by ao + a1. Proof It suffices to show that Now (To+ T1)(f3) =< /3, ao + a1 > '1/ f3 E N(k, r). To(/3) + T1 (/3) < fJ,ao > + < f3,a1 > < /3, ao + a1 > D Since the operation of neighborhood extraction is linear, it is easily shown that the linearity of a global map follows from that of its defining local map. Theorem 2.19 Let k,r,n E z+, T E T(k,r) and ATE A(k,r,n). Then AT is linear if and only if T is linear. Proof ({:::::=) Assume T is linear and let x, y E ZT:, i E n. Then AT(x + y)(i) T(v(x + y, i)) T(v(x,i) + v(y,i)) T(v(x, i)) + T(v(y, i)) AT(x)(i) + AT(y)(i). (=:::::;..)Assume that Tis not linear. Then there exists a,/3 E N(k,r) such that T(a + {3) =j:. T(a) + T(j3). 21
PAGE 28
Define X E by x(i) = { ;(s) if i = s, where s E r otherwise. Notice that negative values of s are evaluated modulo n. xis defined so that its neighborhood at site 0 is equal to a, while it is constant at 0 outside of this neighborhood. If we define y E similarly in terms of (3, then Ar(x + y)(O) r(v(x + y, 0)) r(v(x, 0) + v(y, 0)) r(a + (3) =fr( a) + r(f3) r(v(x, 0)) + r(v(y, 0)) Ar(x)(O) + Ar(Y)(O). D Definition 2.20 Let, k, r, n E z+ and define .C(k,r,n) ={A E A(k,n,r) J A is linear} .C(k, r, n) is said to be the space of ndimensional, radius r linear cellular automata rules over k. Since the set of linear local maps is a submodule ofT(k,r), and the operation of pairing a global map with its defining local map preserves addition, it immediately follows that .C(k,r,n) is a submodule of A(k,r,n). Generally, in order to evaluate a cellular automaton operator at a con figuration, it is necessary to extract the neighborhood about each site, then retrieve the valuation of the local map from a table. This procedure is both 22
PAGE 29
difficult to model mathematically, and computationally intensive. Linear rules are easily modeled mathematically. Furthermore, they may be efficiently implemented on computers if the property established in the next theorem is utilized. Theorem 2.21 Letk,r,n E z+,a E N(k,r),T E T(k,r), andAr E A(k,r,n) such that a generates T. If X E zk and i E n, then r Ar(x)(i) = L x(i + s)a(s). s=r Proof Ar(x)(i) T(v(x,i)) < v(x,i),a > r L v(x,i)(s)a(s) s=r r L x(i + s)a(s). D s=r For example, consider the radius one binary local map that is defined by the dot product with respect to the vector (1,0,1). This rule sets the valuation at site i to 1 if the valuations at sites i 1 and i + 1 are different and 0 if they are the same. If we let A denote the global map defined by this rule, then for any configuration x on which A is defined, A(x)(i) = x(i1) + x(i + 1) holds for each site i of x. Table 2.1 lists the linear members of T(2, 1) and their generators The rows of this table correspond to the eight linear members of T(2, 1). The 23
PAGE 30
column headings for the rule definition are the neighborhoods, and the entry corresponding to a row and column yields the valuation of the corresponding rule at the corresponding neighborhood. That entry is obtained by perform ing the dot product of the neighborhood and the generator for the rule. The decimal equivalent of the eight digit binary number yielded by the defining entries for a rule is listed in the index column of the table. Notice that the operation of adding generators corresponds to the operation of adding rows of the table. This is the property established by Theorem 2.18. Table 2.1 Linear Members of T(2,1) Index Gen Rule 111 110 101 100 011 010 001 000 0 000 0 0 0 0 0 0 0 0 60 110 0 0 1 1 1 1 0 0 90 101 0 1 0 1 1 0 1 0 102 011 0 1 1 0 0 1 1 0 170 001 1 0 1 0 1 0 11 0 150 111 1 0 0 1 0 1 1 0 204 010 1 1 0 0 1 1 0 0 240 100 1 1 1 1 0 0 0 0 24
PAGE 31
3. Circulant Algebra 3.1 Introduction Since Zk is a module, each linear rule may be associated w1th a matrix, and hence, the set of radiusone linear rules which operate on Zk generates a sub ring of the ring of order n matrices over Zk. In this chapter this sub ring is characterized, and it is shown that the operations of matrix addition and multiplication, as well as the multiplication of a vector by a matrix may be expressed in terms of binary operations on Zf:. Several technical properties concerning these operations are then established. 3 2 Matrix Operations In this section matrices and their basic operations are defined. While the definitions presented in this section are technically different from the usual definitions of matrices, these differences are essentially notational. Since ordinal notation is used, we note that row and column numbering begins at zero. Definition 3.1 Let k, m, n E z+. is said to be the space of n X m matrices over zk. We next define matrix addition and multiplication. Definition 3.2 Let k l, n, m E z+ I and define: 25
PAGE 32
(A+ B)(i,j) = A(i,j) + B(i,j) \fiE n, j Em, A, BE A+ B is said to be the matrix sum of A and B. AoB(i,j) = LA(i,s)B(s,j) \fiE n, j E l, A E BE zr;:xl. sEm A o B is said to be the matrix product of A and 13. When expressing matrix products the symbol "o" will generally be omit ted, so that matrix multiplication will simply be denoted by juxtaposition of terms. Definition 3.3 Let k, m, n E z+, A E and define by AT(j,i) = A(i,j), \1 (j,i) Em x n. AT is said to be the transpose of A. Definition 3.4 Let k,m,n E z+, A E and X E Define by AxT(i) = LA(i,j)x(j) \fiE n. jEm AxT is said to be multiplication of the vector xT by the matrix A 26
PAGE 33
Multiplication of x T by A clearly corresponds to multiplication of matrices where xT is assumed to be a matrix with a single column. At the end of this section it will be shown that the class of matrices introduced in the next definition yields the smallest subring generated by the radiusone, linear rules on Definition 3.5 Let k, n E z+. Then: 1. Define eire : + by circ(x)(i,j) = x(ji) 'i/ i,j En and x E eire is said to be the circulant matrix operator on 2. If X E then eire( X) is said to be the circulant matrix generated by X. 3. Define M(k,n) = ({circ(x) I x E Zk},+,o). M(k,n) is said to be the ring of order n circulant matrices over Zk. After introducing some preliminary results, it will be shown that M(k, n) is indeed a ring. It will furthermore be shown that matrix operations may be defined in terms of generating vectors. Proposition 3.6 M(k, n) = {A E I A(i + 1,j + 1) = A(i,j) 'i/ i,j En}. Proof Let x E Zk and i,j En. Then circ(x)(i + 1,j + 1) 27 x(j + 1(i + 1)) x(ji) circ(x)(i,j).
PAGE 34
(2) Let A E such that A(i + 1,j + 1) = A(i,j) 'Vi,j En, and define X E Zk by x(j) = A(O,j), \:f j En. By induction on the rows of A, we now show that circ(x) =A. First, if i = 0, then A(i,j) A(O,j) x(j) x(j0). Next, assume that the theorem holds for row i, where i < n1, and let j En. Then A(i + 1,j) A(i,j1) x((j1)i) x(j(i + 1)). D The proof of this proposition contains a proof that the generator of a circulant matrix is row zero of that matrix. This observation serves to prove the next corollary. Corollary 3. 7 The circulant operator is injective. The proof of Proposition 3.6 also shows that given i,j En, row i + 1 is a rotation of row i one position to the right, and column j + 1 is a. rotation of column j one position downward. 28
PAGE 35
We next show that addition of circulant matrices corresponds to addition of generators. Then, since Zk is a vector space, M(k, n) must a subspace of '77nxn /Uk Proposition 3.8 lfx,y E Zk, then circ(x + y) = circ(x) + circ(y). Proof Given i,j En, circ(x + y)(i,j) (x+y)(ji) x(j i) + y(j i) circ(x)(i,j) + circ(y)(i,j). 0 Corollary 3.9 M(k,n) is a subspace Convolution is a binary operation that arises in many different contexts. We next show that multiplication of circulant matrices corresponds to con volution of their generators. In this way, linear rules may be equated with configurations. In following chapters, this blurring of the distinction between rules and configurations will provide a means to express the algebraic prop erties of a rule in terms of its position in the state transition graph associated with another rule. Definition 3.10 Define by x y(i) = Lx(l)y(i l) Vx,y E Zk, i En. lEn x y is defined to be the convolution of x andy. 29
PAGE 36
Theorem 3.11 Let x, y E Z'k. Then circ(x)circ(y) = circ(x y). Proof Define z E Z'k by z(i) = circ(x)circ(y)(O,i)Vi En. Now, given j En, z(j) circ(x )circ(y) (0, j) L circ(x)(O, s)circ(y)(s,j) sEn Lx(sO)y(js) sEn X* y(j). To complete the proof, we show show that circ(x)circ(y) has the structure of a circulant matrix as follows. If i, j E n, then circ(x)circ(y)(i + 1,j + 1) = L circ(x)(i + 1, s)circ(y)(s,j + 1) sEn L x(s(i + 1))y((j + 1)s) sEn Lx(ti)y(jt) where t = s1 tEn L circ(x)(i, t)circ(y)(t,j) tEn circ(x )circ(y) ( i,j). D The next two propositions show that convolution is commutative, and that e0 is the multiplicative identity on Zf:. 30
PAGE 37
Proposition 3.12 If x, y E Zk, then X* y = y *X. Proof If x, y E Zk and i En, then X*Y(i) = Lx(s)y(is) sEn Lx(it)y(t) where t =is tEn LY(t)x(it) tEn Y*X(i). 0 Proposition 3.13 eo* X= X \/x E zk. Proof Let X E zk and i E n. Then eo* x(i) = L eo(s)x(is) sEn L Oo,sx(is) sEn x(i). 0 The above results may now be combined to show that M(k, n) is a mutative ring. Theorem 3.14 M(k, n) is a commutative subring oj'zzxn. Proof M(k, n) is a subspace by Corollary 3.9, and closed under multiplication by Proposition 3.11. Proposition 3.13 shows that e0 is the identity with respect to convolution, and it is easily seen that eo generates the identity matrix. Finally, Proposition 3.12 establishes commutivity. 0 31
PAGE 38
Corollary 3.7 shows that eire is injective and, surjectivity follows by def inition. Corollary 3.9 shows that it preserves addition, and Proposition 3.11 shows that multiplication is preserved. This argument serves to prove the next theorem. Theorem 3.15 eire: (Zk, +, *) M(k,n) is a ring isomorphism. Theorems 3.14 and 3.15 show that the ring operations on M(k,n) may be naturally associated with the operations of addition and convolution on C(k, n). We now use this isomorphism to show that multiplication of a vector by a circulant matrix corresponds to a linear combination of rotations of that vector. Since ( ei)iEn is a basis for zk' Proposition 3.9 shows that (eire( ei) )iEn is a basis for M(k,n). The next two propositions show that this basis forms a cyclic group with respect to convolution, with each ei acting as a rotation on zk. Proposition 3.16 Let n E z+ and i,j En. Then Proof Let m E n. L l) lEn ei(i)ei(mi), That e;(mi) = { ifj=mi otherwise 32
PAGE 39
follows immediately from the definition of ej. This finally yields if m = i + j otherwise. 0 Proposition 3.17 Let i E n and X E Then given j E n, ei x(i) = x(j + i). Proof Application of the definition of convolution yields ei x(j) = L ei(l)x(j + l) lEn L 8ilx(j + l) lEn x(j +i). 0 Just as multiplication of circulant matrices may be expressed in terms of generators, given x,y E circ(x)yT may be expressed in terms of X andy as follows. Definition 3.18 Define by x 0y = L:x(s)y(i + s) 'ViE n. sEn x 0 y is defined to be the circulant product of x and y. Theorem 3.19 If x, y E Zk, then (x 0 y)T = circ(x)yT. 33
PAGE 40
Proof Let x,y E Zk and i En. Now circ(x)yT(i) = ,Lcirc(x)(i,s)y(s) sEn L x(si)y(s) sEn L x(t)y(i + t), where t = si tEn X 8 y(i). D Linear rules have been characterized, but their matrices have not. First, in order to assign a vector to a rule of radius r, we require that the rule be defined on a space of dimension at least 2r + 1. This insures that neighborhoods do not "wrap around" and overlap themselves. By Theorem 3.19, we need only define a vector such that circulant multiplication of each member of Zk by that vector yields the same function as does application of its associated rule. Theorem 3.20 Let, k,r,n E z+,a E N(k,r),r E T(k,r) andAr E (k,r,n) such that T defines AT and T =<,a>. Define Xa E zk by Xa(i) = { 0, a(i), if i r or i n r ifr < i < nr. Then, given y E Zk, Ar(Y) = Xa 0 Y Proof If i E n, then r Ar(Y)(i) = L y(i + s)a(s) s=r r L y(i + s)xa(s) s=r 34
PAGE 41
r nr1 L y(i + s)xa(s) + L y(i + l) 0 s=r l=r+1 r nr1 L y(i + s)xa(s) + L y(i + l)xa(l) s=r l=r+1 LY(i + l)xa(l) lEn LXa(l)y(i + l) lEn Xa 0 y(i) 0 N(k, r) is closed under addition, but not multiplication. For example, the linear rule generated by 001 E N(k, 1) shifts each configuration one position to the left, while its square 00001, which shifts configurations two places to the left, is a member of N(k, 2)\ N(k, 1). By Theorem 3.20, a subset of N(k, r) may be equated with elements of ZJ:. Thus, if n 2:: 3, then N(k, 1) s; +, *), and hence, there must be a smallest subring of (ZJ:, +, *) that contains it. The next theorem shows that this ring is all of (ZJ:, +, *). Theorem 3.21 If k, n E z+, with n 2:: 3, then N(k, 1) generates (Zk' + *). Proof First notice that 001 E N(k, 1). By Theorem 3.20, this generator corresponds to e1 E Zk'. By Proposition 3.16, Thus the ring generated by N(k, 1) must contain 35
PAGE 42
Since this is a basis for +,*),we see that N(k, 1) generates +, *). 0 3.3 Circulant Spaces Vector addition is defined pointwise for elements of multiplication of circulant matrices is performed on pairs of elements from and operation on a vector by a circulant matrix involves one argument from and one from All three of these operations thus have different domains. Matrix multiplication maps into while the other operations have as their range. In spite of these differences, it is possible to consolidate all three of these operations into one abstract structure. This is so because circulant matrices are defined in terms of vectors. Definition 3.22 Let k, n E z+, and define C(k, n) = +, *, 0). C(k, n) is defined to be then dimensional circulant space over Zk. This consolidation of operations into one structure provides a context within which it is possible to investigate relationships between the opera tions of convolution and circulant products. The most important of these relationships is based on the concept of conjugation of a configuration. Definition 3.23 Let X E and define X E by x(i) = x(i) 'ViE n. x( i) is said to be the conjugate of x. 36
PAGE 43
It is clear that We now show that conjugation distributes over all circulant space operations Proposition 3.24 If k, n E z+, and x, y E then Proof If i En, then X+ y(i) (x + y)( i) x( i) + y( i) x(i) + y(i). o Proposition 3.25 Given k, n E z+ and x, y E Proof Let i En. Then X* y(i) X* y( i) L x(l)y( il) !En Lx(l)y(i(l)) !En "Lx(l)y(i l) lEn The next corollary extends Proposition 3.25 to the operation of exopnen tiation. 37
PAGE 44
Corollary 3.26 If X E and i E z+' then xi = '5;i. Proof The case i = 1 is obvious and yields a base for the induction. For i > 1, the induction step follow.s by letting xil =yin the proposition. D Theorem 3.27 Ifx,y E Z"k,then X *Y =x(!)y. Proof Given i E n, X* y(i) L x(l)y(i l) lEn L:x(l)y(i(l)) lEn L:x(l)y(i + l) !En x0y(i). o Corollary 3.28 For x, y E Z"k, Proof This follows from the reflexivity of conjugation. D Finally, we show that conjugation distributes over Circulant multiplication. Theorem 3.29 For x, y E 38
PAGE 45
Proof x0y X*Y X*Y X*Y x0y. 0 In matrix theory, it is well known that given a pair of conformable matri ces and a vector, the result obtained by first multiplying the matrices then operating on the vector is the same as the result obtained by first operating on the vector by the right matrix then operating on the resulting vector by the left matrix. The next theorem simply restates this property in terms of convolution and circulant multiplication. Theorem 3.30 Given k, n E z+ and x, y, z E Zk', Proof (x y) 0 z = x 0 (y 0 z). (X*Y)*Z (x y) z X* (Y* z) x 0 (y 0 z). 0 In the literature on cellular automata, it is common to see a diagram of the evolution of a onedimensional automaton under a rule, where the initial configuration is displayed on the top line and each succeeding line is the result of applying the rule to the line above. Patterns for many rules 39
PAGE 46
are well known. It is often useful to know the pattern obtained by raising a rule to powers, but these are rarely published. The next theorem shows how to determine this structure for a rule from the evolution of e0 under its conjugate. Theorem 3.31 Let X E ZJ: and mE z+. Then Proof First let m = 1. In this case, application of Theorem 3.27 yields X X*ea x0eo. Next assume that the result holds form1. Then x (xm1 0 eo) x 0 (xm1 0 eo) xm 0 ea. 0 The space of circulant matrices is closed under transposition. In fact, the next theorem asserts that conjugation of configurations corresponds to transposition of associated matrices Theorem 3.32 If x E ZJ:, then circ(x) = circ(x)T. 40
PAGE 47
Proof Let X E zk and i, j E n. Then If X E Zk, then while circ(x) ( i, j) x(ji) x(ij) circ(x)(j, i) circ(x)T (i,j). D circ(x): Thus x and circ(x) have domains and ranges. The next two defi nitions, which are technically abuses of notation, establish notations for the kernels and ranges of members of Zk when they are equated with their asso ciated circulant matrices. Definition 3.33 Let k,n E z+, X E and define ker (X) = {y E I X 0 y = Q}. Definition 3.34 Let k, n E z+' X E zk and define rng (X) = {y E 13 Z E 3 X 0 Z = y}. (3.1) 3.4 The Summation Homomorphism The linear functional presented in this section simply sums the valua tions of a configuration. This operation will be used extensively in the next chapter. 41
PAGE 48
Definition 3.35 Let k, n E z+ and X E Zk'. Define by E(x) = Lx(i). i En Ex is said to be the summation of x. Theorem 3.36 E : (Zk', +, *) + (Zk! +, ) is a ring homomorphism. Proof The operation of addition is clearly preserved because it is commu tative. We next show that convolution is preserved. Let x, y E Zi:. Then ien L:l::x(l)y(i z) iEn len Lx(l) LY(i l) lEn iEn Lx(l)E(y) len E(y) Lx(l) len E(y)E(x) E(x)E(y) o Corollary 3.37 If x, y E Zi: then E(x 0 y) = E(x)E(y). Proof Clearly E(x) = E(x). 42
PAGE 49
. Next notice that x0y =X*Y, and apply the theorem. D If k = 2 ; then this operation returns 0 for configurations that map an even number of indices to 1, and 1 for configurations that map an odd number of indices to 1, that is, it returns the parity of a configuration. The next definition formalizes the notion of parity. Definition 3.38 Let n E z+ and define 1. even(n) = ({x E C(2,n) I Ex= 0}, *)is defined to be the simi group of ndimensional, even parity configurations. 2. odd(n) = ({x E C(2,n) I Ex= 1},*) is defined to be the simi group of ndimensional, odd parity configurations. It is an immediate consequence of Theorem 3.36 that these sets are indeed semi groups. 3.5 State Transition Graphs Any cellular automaton for which the state space is finite may be asso ciated with a directed graph, called a state transition graph. The nodes of this graph are the configurations of the state space, and an arc exists from node y to node z if the automaton rule maps y to z. Each node thus has outdegree equal to one. Given any configuration, the rule may be applied to it resulting in another configuration to which the rule may again be ap plied. Since the state space is finite, this process must eventually result in a 43
PAGE 50
repetition. If a node is eventually repeated, it is defined to be an attractor state. Such a node, and all of the nodes occurring between it and the first repetition, induce a cyclic subgraph. This subgraph is called an attractor. Clearly, each element of an attractor is also an attractor state. The remain ing states are called transient states. For a particular automaton, transient states may or may not exist, but if they do exist, then some of them will not have preimages; these states are called GardenofEden states. Given any attractor state, the subgraph induced by that state and the transient states that eventually map to it is a tree. This tree is defined to be the transient tree rooted at that node. The subgraph that consists of an attractor and all of the subtrees rooted at those attractor nodes is called a basin of attraction. The basins of attraction are also the weakly connected components of the state transition graph. The next definition formalizes these concepts Definition 3.39 Let k, n E z+ and X E C(k, n). Define: 1. G(x) = (C(k,n),E(x)), where E(x) = {(y,x0y) IY E C(k,n)}. G(x) is said to be the state transition graph for x. 2. atr(x) = {y E C(k, n) 13 r E z+ 3 xr 0 y = y }. atr(x) is said to be the attractor space for x. 3. trn(x) = C(k, n) \ atr(x). trn(x) is said to be the transient space for x. 4. goe(x) = {y E C(k, n) I {z E C(k, n) I x 0 z = y} = 0}. goe(x) is said to be the set of GardenofEden states for x. 44
PAGE 51
Definition 3.40 Let k, n E z+ and X E C(k, n). 1. Define f..Lx : C(k, n) t w by f..Lx(Y) min{r E w lxr 0y E atrx} f..Lx(Y) is said to be the x level of y. 2. ,Define Px : atr(x) t z+ by Px(Y) is said to be the x period of y. The restriction of x to atr(x) is invertible, and the inverse of y E atr(x) is yielded by x p,(y)l 0 y. This ch9ice clearly works as an inverse image, and it must be unique since any attractor state which maps toy must be in the same attractor as y, and X3 0 y =j:. y whenever 0 < s < Px(y). Definition 3.41 Let y E atr(x). Define: 1. Y;(y) = {z E trn(x) 13 r E z+ 3 xr 0 z = y} U{y}. Vx(y) is said to be the vertex set of the transient tree rooted at y. 2. Ex(Y) = {(z,x 0 z) I z E Y;(y)\{y} }. Ex(Y) is said to be the edge set for the transient tree rooted at y. 3. Hx(Y) = (Yz(y), Ex(Y)). Hx(Y) is said to be the transient tree rooted at y. To see that Hx(Y) is indeed a tree, first notice that it contains no cycles since each vertex other then y has outdegree equal to one, and given a node z E Hx((y), f..Lx(z) > f..Lx(x 0 z). 45
PAGE 52
Finally, it is weakly connected because each node is connected to y. It is clear that the set of leaves of Hx(Y) is equal to Vx(y) n goe(x). Since x 0 .Q = .Q V x, it follows that .Q E atr(x). This fact insures us that the following definition always makes sense. Definition 3.42 Define nil(x) = Vx(.Q). nil(x) is said to be the space of nil states for x. It follows from this definition that nil(x) is the set of nodes upon which x acts as a nilpotent operator. Since the null space of x is the set of nodes which map to .Q under one application of x, it must be contained in nil(x). The next proposition assertsthat nil(x) is indeed a subspace of C(k, n). Proposition 3.43 If y, z E nil(x), then y + z E nil(x). Proof Lett= max{J.Lx(Y), J.Lx(z)}. Then It is also easy to show that atr(x) is a subspace of Zk. Proposition 3.44 If y, z E atr(x), then y + z E atr(x). Proof Lett= J.Lx(Y)J.Lx(z). Then 46
PAGE 53
The restrictions of x to its nil and attractor spaces result in simple state transition graphs. The action of x on nil(x) yields in a tree with a self loop at Q, while its action on atr(x) yields a collection of cycles. The next theorem states that given any linear rule, the state space decomposes into the direct sum of its nil and attractor states. Once the structure of the two resulting state transition graphs is known then the graph for x is obtained by simply attaching a copy of the nil tree at each attractor node. Theorem 3.45 If x E C(k, n), then C(k, n) = atr(x) ffi nil(x). Proof Let y E C(k,n), t = f..tx(Y), and Yo E atr(x) such that t 1:'\ t 1:'\ X X Define Y1 = YYo Clearly, y0 exists and is unique, since the restriction of x to atr(x) is invertible. It is also clear that y = y0 + y1 To complete the proof, it must be shown that y1 E nil(x), and that the decomposition is unique. We first show that xt 8 y1 = Q. Now xt 0y +xt 0yo xt 0y + xt 0y Q. To establish uniqueness, assume that y = Zo + Zt, 47
PAGE 54
where zoE atr(x) and z1 E nil(x). If s = max{f.Lx(Yl), f.Lx(zl) }, then Since there is a unique v E atr(x) such that X8 0 v = y, it follows that Yo= zo. This, in turn, implies that The Corollary 3.46 follows immediately from the theorem and properties of direct sum decompositions. Corollary 3.46 #(atr(x))#(nil(x)) = kn. We close this chapter by showing that the state transition graph for a linear rule is obtained by attaching a copy of its nil tree at each member of its attractor space. Theorem 3.47 If x E C(k, n) andy E atr(x), then Proof Assume that t 0. Since the restriction of x to atr(x) is invertible, there exists Yt E atr(x) such that xt 0 Yt = y. Now, define 48
PAGE 55
by = Yp.,(z) + z. Since C(k, n) = atr(x) EB nil(x), is injective. To see maps into Hx(Y) let z E Hx(ll), and s = J.Lx(z). Then y + .Q. If z E H x (.Q) \.Q, then Ys1 +X 0z This shows that adjacency is preserved. To complete the proof, we show that is surjective as follows. Since is injective, Hx(Y) is at least as large as Hx(.Q). Since y is an arbitrary element of atr(x), Corollary 3.46 implies that Hx(Y) is no larger than Hx(.Q). 0 49
PAGE 56
4 Rule 60 4 1 Introduction In Chapter 2 rule 60 was shown to be linear This rule sets a site on if and only if its current valuation is different from that of its left neighbor Rule 60 thus ((flags" the positions at which the configuration changes value as it is read in increasing order. In this chapter, basic properties of rule 60 are developed. This rule is particularly well behaved when it operates on spaces whose dimensions are a power of two. In this case, the graph for rule 60 is a binary tree. In the next chapter it will be shown that the structure of the state transition graph for any member of C(2, 2m) may be expressed entirely in terms of the structure of the graph associated with rule 60. 4.2 Basic Properties of Rule 60 In this section it will be shown that the theory developed in the previous chapter extends naturally to operators on spaces of infinite dimension. Some technical results are developed concerning rule 60 as an operator on These results are then be applied to the study of rule 60 as an operator on spaces of finite dimension We first define neighborhood extraction operators for doubly infinite sequences 50
PAGE 57
Definition 4.1 Let r, k E z+, and define 1/: X z!N(k, r) by v(x,i)(s) = x(i +s)Vx E zt i E Z, and s E f. Given any local map, the neighborhood extraction operator links it to a global map in the infinite dimensional case exactly as it does when the dimension is finite. Similarly, a global map is linear exactly when its associated local map is. The local map, rule 60, defines operations on many different state spaces, and these operations are technically different functions. It is often possible to equate a local map with the global map that it generates, but in this section we must simultaneously consider the global maps generated by rule 60 on different spaces. We thus define D yields a set of indices that may be used to identify the different state spaces upon which rule 60 operates. Now, givenS E D we let Rs,so denote the global map on generated by rule 60. The next proposition identifies the kernel of rule 60, and its corollary establishes when two configurations have the same image. Proposition 4.2 If S E D, then ker (Rso,s) = {.Q,l}. 51
PAGE 58
Proof Let X E and i E S. It follows immediately from the definition of rule 60 that Rs,6o(x)(i) = 0 {==> x(i) x(i1). Clearly, x(i) = x(i1) for each i exactly when xis a constant. 0 Definition 4.3 Let X E Zf and define X E by x(i) = x(i) + 1, 'ViES. x(i) is said to be the compliment of X Corollary 4.4 If x, y E then Rs,6o(x) = Rs,6o(Y) y E {x, x}. Proof First notice that x = x + 1. Since R8 60 is linear, x andy will map to the same vector if and only if they are in the same coset of the kernel. 0 Repeated application of a rule causes information contained in the initial configuration to propagate through the state space. The radius of the rule provides an upper bound for the rate of transmission of information. De pending on the particular properties of the rule, this upper bound may or may not be achieved. By starting with a configuration of the form ei E and repeatedly applying a rule, an envelope identifying the range of sites that may be on at any point in time is generated. The shape of this envelope is defined to be the light cone for the rule. For example, figure 4.1 illustrates the light cone generated by 31 iterations of rule 60, for which the initial con figuration is e0 Numbered rows correspond to configurations at indicated 52
PAGE 59
times, black cells correspond to values of 1, and white cells correspond to values of 0. We see that the rule does not propagate information to the left, while it propagates information to the right at a rate of 1 site per unit of time. The next proposition formally establishes these properties. 0 1 2 3 4 5 5 7 a 9 10 11 12 13 14 15 15 17 18 19 20 21 22 23 24 25 25 27 28 29 30 31 Figure 4.1 Light Cone for Rule 60 Proposition 4.5 The following properties hold for each t 0: 1. = 0 \;/ i < 0. 2. = 1. 3. = 0 \;/ i > t. 4. = 1. 53
PAGE 60
Proof First, if t = 0, then =eo, and hence, all properties hold for this case. This provides bases for inductive proofs of each of the four properties. 1. Assume that the assertion holds fort, and let i < 0. Then 1) + ' 0+0 0. 2. Assume that the assertion holds fort. Then 1) + 0+1 1. 3. Assume that the assertion holds fort. If i > t + 1, then 1) + 0+0 0. D 4. Assume that the assertion holds fort. Then Rt+1 (ea)(t + 1) Z,60 + 11) + Ri,60(ea)(t + 1) 1+0 1. 54
PAGE 61
This establishes the maximum range of sites over which may equall. The next proposition asserts that 60(ea) = 1 over the entire range I whenever tis of the form 2m 1. While the rigorous proof of this proposition is somewhat tedious, the concept is very simple. Notice that in figure 4.1 the proposition holds for each such t. In particular, when t = 15, sites 0 through 15 are on. Since rule 60 "flags" changes in a configuration, only sites 0 and 16 are on at t = 16. The resulting configuration is thus e0 + e16 Now assume that only site 0 is on at t = 16. Since this is exactly the situation at t = 0, the evolution from t = 16 through t = 31 must be exactly the same as the evolution from t = 0 through t = 15. Thus at t = 31 sites 0 through 15 must be on. Similarly, if we assume that only site 16 is on at t = 16, then at t = 31, sites 16 through 31 must be on. Since rule 60 is linear, the result at t = 31 of both sites 0 and 16 being on at t = 16 is obtained by adding the independent results. This shows that all of sites 0 through 31 must be on at t = 31. The proof of the next proposition simply generalizes this argument. Proposition 4.6 If m 0, and t =2m 1, then = 1 0:::; i:::; t. Proof Proceed by induction on m. First, if m = 0, then t = 0, and hence, The proposition clearly holds in this case. Next assume that it holds for t = 2m 1. To establish it for t = 2m+1 1, first evaluate By I Proposition 4.5, if i < 0 or i > t + 1 ifi E {O,t+ 1}. 55
PAGE 62
It only remains to consider 1 i t. In this case, This now yields Since we have Ri 60(eo)(i1) + Ri 60(eo)(i) ' 1+1 0. 2m+1 1 = 2t + 1, Ri,so ( Ri:s1o (eo)) + et+I) By the induction hypothesis, = 1 0 i t. Since et+I is the translation of eo by t + 1, we have = 1 t + 1 i 2t + 1. This now yields The actions of rule 60 on and Z2 are compared next. Since two different spaces are being considered, we continue to link global maps to the 56
PAGE 63
state spaces upon which they operate, via subscripts. Similarly, subscripts are used to identify the spaces associated with basis elements. Proposition 4. 7 Let n E z+ and t, i E n. Then ( en,o) ( i) = ( ez,o) ( i). Proof If t = 0, then en,o(i) = Doi = ez,o(i), 'ViE n. This establishes a base for the induction Next assume that the proposition holds fortE n1. If i > 0, then by the induction hypothesis 1) + 1) + Site 0 is now the only remaining position at which the proposition could fail to hold. To this case notice that 1 = n 1 ( mod n), and 1) = 0. This shows that = 1. D We now show that the property established by Proposition 4. 7 does not hold when t = n. 57
PAGE 64
Proposition 4.8 If n E z+, then Proof = 0. 1) + 1+1 0. 0 The next definition introduces notations for rules 60 and 102 when they are equated with members of Z2, and the following proposition shows that these definitions are reasonable. Definition 4.9 Let n E z+. Define: 1. 8_ E Z2 by ifiE{O,n1} otherwise if i E {0, 1} otherwise. Proposition 4.10 If n E z+, then 8_ and Rn,60 define the same function on Z2. Similarly, 8+ and Rn,1o2 define the same function on Z2. Proof By symmetry, it suffices to prove the proposition for 8_ and Rn,ao. Let y E Z2 and i E n. Then 8_ Gy(i) = L8(l)y(i+l) lEn 58
PAGE 65
8_(0)y(i + 0) + 8_(n 1)y(i + (n 1)) y(i) + y(i1) Rn,60 (y )( i) 0 Next, the summation homomorphism is used to characterize both the range of 8_ and its GardenofEden states. Theorem 4.11 rng (8_) = even(n). Proof Clearly, = 0, and hence, given y E Z2, 0 y) = = 0. Thus, each x E rng (8_) has even parity. The result now follows upon noting that [ker8_: 1] = 2, and that the even parity rules account for exactly half of Z2. 0 Corollary 4.12 The GardenofEden states for 8_ are the odd parity configurations 4.3 Behavior of 8_ on C(2, 2m) For the remainder of this chapter we study the operation of 8_ on spaces whose dimensions are powers of two We therefore assume that m, n E z+, and that the relation n = 2m holds in all definitions and theorems. We begin by showing that 8_ is a nilpotent operator on C(2, 2m). 59
PAGE 66
Theorem 4.13 8".!:._ 0 e0 = .Q. Proof By Propositions 4.6 and 4.7, 8n1 !';\ e = 1. 'V 0 Now apply Proposition 4.2 to obtain 8_ 01 = .Q. D. Corollary 4.14 If i E n, then Proof Notice that ei is the translation of e0 by i, and hence, 8".!:.. 0 ei is the translation of 8".!:.. 0 e0 by i. D Corollary 4.15 If X E then Proof Clearly Thus, by the linearity of 8_, 0x = .Q. x = Lei. :r(i)=l L 0ei :r(i)=l .Q. 0 Since 8_ is linear, .Q is a fixed point, and hence, the state transition graph for 8_ must have a self loop at .Q. Corollary 4.15 shows that the remainder of the graph must be a tree. Also, since ker (8_) = {.Q,l}, this tree must be binary. Notation for the levels in this tree is introduced next. 60
PAGE 67
Definition 4.16 Define .A : + Z by .A(x) = min{t 2::0 8x =.Q}, Vx E .A(x) is defined to be the basic level ofx. Furthermore, givenj E n+1, define lvl(j) = {x E I .A(x) = j}. lvl(j) is said to be basic level j of Z2. The next theorem establishes the cardinalities of the basic levels. Theorem 4.17 Let j En+ 1. Then #(lvl(O)) = { 1 2i1 Proof Clearly, only .Q satisfies if j = 0 otherwise Since ker (8_) = {.Q,l}, and .Q E lvl(O), we must have lvl(1) = {1}. Again, since ker (8_) = {.Q,l}, it follows that #(lvl(j)) ::;#(lvl(j1)) for 2::; j::; n. This last statement, and the fact that #(lvl(1)) = 1 imply #(lvl(j)) ::; 2il for 1 ::; j ::; n. 61
PAGE 68
This establishes an upper bound for the cardinality of each level. To complete the proof, it is only necessary to show that in order for the tree to contain all of Z2, each level must be full. This is established as follows 2n n1 1+ 2:::2! l=O n 1 + L2j_1. 0 j=l Since all levels are full leaves only occur at level n Also each internal node has exactly two predecessors. More generally, if >.(x) = j < n, then x has 2nj predecessors with respect to 5':._i and all of them are leaves. Proposition 4.18 characterizes the action of powers of 8_ on basic levels. This result is based on the fact that basic levels are defined in terms of the action of 8_. Proposition 4.18 If j, lEn+ 1 and x E lvl(l) then: 1. If j ::; l, then 0 x E lvl(lj). 2. If j 2:: l, then 0 x E lvl(O). Proof 1. The assertion clearly holds for j = 0, so assume that it holds for j < l. Then 0x) = lj > 0. Since 0 x = 8_ 0 0 x), it is clear that 0x = lj 1 = l(j + 1). 62
PAGE 69
2. By (1), 0x =Q. Since Q is a fixed point for 8_, it follows that 0 x = Q whenever j ;::: l. 0 We complete this chapter with a characterization of kernels of powers of 8_ in terms of basic levels. Definition 4.19 Let lEn+ 1 and define l Kz = U lvl(j) j=O Corollary 4.20 If lEn+ 1, then Kz = ker 63
PAGE 70
5. State Transition Graphs for C(2, 2m) 5.1 Introduction The state transition graphs for rule 60 on spaces of dimension 2m were characterized in Chapter 4. In this chapter it is shown that the structure of the state transition graph for each member of zr is obtainable from the structure of the graph for rule 60. Figures 5.1 and 5.2 provide examples of graphs for two members of C(2, 4). Application of rule 60 corresponds to circulant multiplication by 8_, which in the current context equals 1001. Figure 5 1 illustrates the state transition graph for this rule. This graph is actually a digraph, but arrow heads on arcs are not required because, by convention the direction of flow is towards the attractor. Notice that this graph is a binary tree of height 4 with a loop at .Q. The nodes of this tree may be viewed as configurations upon which 8_ acts, and each such configuration also represents a rule that operates on C(2, 4), and hence, has a state transition graph of its own. This concept is extremely important, as the primary results presented in this thesis are obtained by exploiting the dual nature of members of circulant spaces. Several properties of rule 1001 are illustrated in figure 5.1. First since the graph is a binary tree with 0000 as its root, this rule must be nilpotent. The kernel consists of the constant configurations 0000 and 1111, and hence com plimentary configurations map to the same image. Furthermore, all leaves of this tree have odd parity, while all internal nodes have even parity. 64
PAGE 71
Figure 5.1 State Transition Graph for 1001 Level 0001 1110 0100 1011 0010 1101 0111 1000 4 3 2 0101 1 0 Figure 5.2 State Transition Graph for 0001 Level 1000 0111 4 0010 1101 1100 3 0011 2 0101<=>1010 1111 1 c 0000 0 c 65
PAGE 72
In addition, the following properties of state transition graphs for mem bers of C(2, 4) which are determined by this tree are not apparent by simple inspection. A member of C(2, 4) is invertible if its parity is odd and nilpotent if its parity is even. More generally, the order of the kernel of each rule is determined by its level in this tree. Each of the 4 rules at level 3 have kernels of order 2, 0101 and 1010, which are at level 2, both have kernels of order 4, the kernel of 1111 has order 8, and finally, the entire space is the kernel of 0000. Thus the leaves each possess kernels of order 1, and at successively lower levels, the orders of the kernels double. Even parity rules at the same level not only have kernels of equal order; they have isomorphic state transition graphs. While all of the odd parity rules are leaf nodes, they do not all have isomorphic graphs. Since the graphs for invertible rules consist of collections of cycles, in order to classify these graphs it is only necessary to determine which cycle lengths may occur, and then count the number of occurrences of each. For example, figure 5.2 depicts the graph for 0001, which rotates each configuration 1 position to the right. Again, arrow heads on the arcs are implicit because, within attractors, flow is assumed to be in the clockwise direction. Notice that the levels benerated by rule 1001 are preserved by rule 0001. In fact, each odd parity member of C(2, 4) preserves this level structure. The graph for 0001 is isomorphic to the graphs for rules 1110, 1011 and 0100, and no other rules have graphs with this structure. To express this relationship in terms of levels, simply add 1000 to each of these rules, resulting in 1001, 0110, 0011, and 1100 respectively. These rules clearly constitute level 3 of the graph for 8_. Similarly, 1101 and 0010 have isomorphic graphs and 66
PAGE 73
the addition of 1000 to each of them yields the rules at level 2. Addition of 1000 to 0111 yields 1111, which is the only rule at level 1, and the graph for 0111 is unique. Finally, the graph for 1000 consists of 16 self loops and 1000+ 1000=0000, which is the only rule at level 0. Thus, although not every pair of leaf nodes have isomorphic graphs, the graphs associated with two such nodes are isomorphic if and only if addition of 1000 to each of them results in even parity rules at the same level. The remainder of this chapter is devoted to showing that generalizations of these properties hold in arbitrary spaces of dimension 2m. Thus, for the remainder of this chapter we assume that m, n E .z+, and n = 2m. 5.2 Properties of Odd Parity Rules Corollary 4.12 states that the odd parity configurations are the leaves of the tree for 8_. In this section, it is shown that multiplication by odd parity rules preserves the level structure of this tree. This fact then leads to a simple proof that odd parity rules are invertible. Since L: is a ring Homomorphism from ( Z2, +, *) to ( .Z2, +, ), it follows that even(n) and odd{n) are both closed under convolution and circulant multiplication. It is now easy to show that odd parity rules leave basic levels invariant. Proposition 5.1 Let x E odd( n) and y E Z2. Then A(x 0 y) = A(y). Proof Proceed by induction on basic levels, starting with level nand work ing downward. First, let y E lvl(n). Since lvl(n) = odd(n), and convolution 67
PAGE 74
preserves parity, we must have x 0 y E lvl(n). Next, assume that the proposition holds for lvl(l), with l > 0. If y E lvl(l1), then, because the tree for 8_ is full, :3 z E lvl(l) such that 8_ 0 z = y. By the induction hypothesis, >.(x0z)=l, and hence, >.(8_ 0 (x 0 z)) = l1. Finally, x0y x0(8_0z) (x 8_) 0 z (8*x)0z 8_ 0 (x 0 z) E lvl(l1). 0 Corollary 5.2 Let, X E odd(n) andy E Then >.(x y) = >.(y). Proof Because = we have x E odd(n). Now, upon noting that X*Y =x0y, 68
PAGE 75
we may apply the proposition. 0 A graph theoretic argument next establishes the invertibility of odd parity rules. Theorem 5.3 If x E odd( n), then x is invertible Proof Let x E odd(n). Since Z2 is finite, it is only necessary to show that xis injective. So let y E ker (x) and show that y = .Q. By Proposition 5.1, .A(y) = .A(x 0 y) = .A(.Q) = 0. Clearly, only .Q E lvl(O). 0 The next theorem shows that any member of Z2 is reachable from any other configuration at the same level via the action of some odd parity rule. Theorem 5.4 Let lEn+ 1 and x, y E lvl(l). Then :3 z E odd(n), such that y = z 0 x. Proof We proceed by induction on levels, starting at the top of the tree. Let l = n. Clearly, Now x, y, x1 E odd(n). y0 (x10x) y0 (x1 x) y0eo Y* eo y. 69
PAGE 76
Next let l < n, and assume that the proposition is true for l + 1. Then there exist xo, Yo E lvl(l + 1) such that 8_ 0 xo = x and 8_ 0 Yo = y. By the induction hypothesis, there exists z E odd(n) such that Now z 0 Xo =Yo z0x z0(8_0xo) (z 8_) 0 Xo (8_ z) 0 xo 8_ 0 (z 0xo) 8_ 0Yo y. D The results presented in this section constitute all of the theory of odd parity rules required for the characterization of state transition graphs for even parity rules. Once even parity rules have been treated, we will return to the characterization problem for odd parity rules. 5.3 State Transition Graphs for Even Parity Rules In this section it is shown that each even parity rule is nilpotent. The graph for a nilpotent rule is a tree with a self loop at .Q, and the indegree of a node in such a tree is equal to either 0, for GardenofEden states, or 70
PAGE 77
the order of the kernel. Since odd parity rules preserve basic levels and convolution is commutative, it follows that the product of an odd parity rule and a power of 8_ must also be nilpotent. The level structure for a power of 8_ is easily expressed in terms of basic levels, and hence, so is the level structure of a configuration of the form x, where x E odd(n). Upon showing that each even parity rule may be expressed as such a product, it is very easy to determine both the structure of the state transition graph for individual rules and number of different rules possessing any particular structure. Definition 5.5 Let l E n + 1 and define Since eo E odd(n), and e0 is the multiplicative identity in Z2, we have 8r:_l = e0 or:_z E Bz V l E n + 1. It will be shown that these sets yield a partition of Z2, which equals the partition generated by the levels of the tree associated with 8_. These two characterizations of this partition provide insight into the basic structure of state transition graphs for members of Z2. Proposition 5.6 Let l,j En+ 1, y E B1 and z E lvl(j). Then: 1. j 2: n l ::::::::> y 0 z E lvl(j(n l)) 2. j ::::; n l ::::::::> y 0 z E lvl(O). Proof Both (1) and (2) hold for or:_! because levels are defined in terms of 8_. The results for arbitrary elements of B1 follow upon noting that odd parity rules preserve basic levels. D 71
PAGE 78
Corollary 5. 7 If l, j E n + 1 such that l f: j then Proof Let l, j En+ 1 and x, y E odd(n) such that X 5'}_l = y By the proposition, (x 5'}_1 ) 0 e0 E lvl(n l) and (y 0 e0 E lvl(nj). This is possible only if l = j. D Corollary 5.8 Let lEn+ 1 andy E B1 Then nl ker (y) = U lvl(j). j=O Corollary 5. 9 Let l E n + 1 and y E B1 Then [ker (y) : 1) = 2nl. Proof Clearly lvl(O) = {.Q} and if j > 0, then #(lvl(j)) = 2il. Since basic levels are disjoint, it follows that nl 1 + :L2jl j=l 1 + 2nl 1 72
PAGE 79
Proposition 5.6 makes use of the fact that odd parity rules preserve basic levels. More generally, any assertion concerning the behavior of elements of B1 with respect to basic levels holds for all elements of B1 once it is shown to hold for 8":..1 The following proposition provides another example of the usefulness of this property. Proposition 5.10 If l E (n + 1)\ {0} andy E B1 then y is nilpotent. Proof Let l E (n + 1), x E odd(n), andy= x We may now choose t E z+ such that tl 2: n. Since convolution is commutative, But, =Q. D We next show that B1 = lvl(l) for each lEn. It then easily follows that all even parity rules are nilpotent. This result, furthermore, provides a simple means by which the kernel of any even parity rule may be determined. Proposition 5.11. If lEn+ 1, then #(Bt) 2: #lvl(l). Proof Let l E n + 1 and define Wt = or:_l 0 eo. Clearly, Wt E lvl(l). 73
PAGE 80
If y E lvl(l), then, by Theorem 5.4, 3 zy E odd(n) such that zy 0 w1 = y. If Yo, Y1 E lvl(l), and they are distinct, then and hence This shows that the number of different valuations of e0 with respect to members of B1 is at least as large as the number of members of lvl(l). This establishes the inequality. D In summary, the following inequalities have now been shown to hold: > #( u!En+l Bl) since each B1 E!En+l #(Bl) since the B 1 are disjoint > E!En+l #(lvl(l)) by Proposition 5.6 since the basic levels partition Since the first and last terms of this sequence are equal, the two in equalities must actually be equalities. Several technical results may now be established. Proposition 5.12 Given lEn+ 1, #(Bl) = #(lvl(l)). Proof This follows immediately from the preceding sequence of inequali ties. D 74
PAGE 81
Proposition 5.13 (B1 ) 1En+l partitions Z2. Furthermore, for each l E n + 1, Bt = {x E I (ker (x) : 1] = 2nl}. Proof By Corollary 5 .7, the B1 are pairwise disjoint. They must then partition Z2 because their cardinalities sum to its cardinality. The second part of the proposition now follows from the definition of the B1 0 Corollary 5.14 The only rule whose kernel is all of Z2 is .Q, and for j > 0, #({xI (ker(x): 1] = 2i} = 2njl. Proof The corollary clearly holds for j = 0 so let j > 0. Then, by Propo sition 5.13, {x I (ker (x) : 1] = 2j} = Bnj, and, by Proposition 8.16, #(Bnj) = #(lvl(nj)). Finally, apply Theorem 4.17. 0 All rules have now been shown to factor into the product of an odd parity rule and where l E n + 1. The next theorem shows that the order of the kernel of a rule is determined by its basic level. Since even parity rules are nilpotent, the structures of their state transition graphs are determined by the order of their kernels. The problem of determining the structure of a graph for an even parity rule therefore reduces to the problem of determining its basic level. Theorem 5.15 If lEn+ 1, then B1 = lvl(l). 75
PAGE 82
Proof Let lEn+ 1. Since #(B1 ) = #(lvl(l)), it suffices to show that B1 C lvl(l). First notice that 8+ has the same level structure as 8_, because 8+ = e1 8_, and e1 E odd(n). Clearly, and = e0 = 0 e0 E lvl(l). Next if x E odd(n), then show that x E lvl(l). Now by Corollary 5.2, x_ E lvl(l). 0 This shows that the partition of Z2 into basic levels coincides with the partition generated by taking two rules to be equivalent if their kernels have the same order. Since each nilpotent rule is a product of an odd parity rule and a power of 8_, their level structures must be obtainable from that of 8_ In order to identify level structures for trees associated with even parity rules we define a partition of Z2 for each internal basic level, and then show that the level structure for any even parity rule is yielded by the partition associated with the level at which that rule resides. We begin by defining a function that assigns to each internal basic level, the height of the tree associated with any member of that level. Definition 5.16 Define h:n+n by h(j) = I \:1 j E n. I nJ 76
PAGE 83
Proposition 5.17 Let x E lvl(j). Then: 1. xhCi) 0 y = Q 'tf y E Z2. 2. xh(j)l 0 y =/: Q 't/ y E lvl(n). Proof 1. Clearly, h(j)(nj) = I (nj) n. InJ We need only consider fl:_i E lvl(j) If y E Z2, then By the preceding comment, 2. Now, Thus This yields (fl:_i)h(j) = 8:_, where t = n + 8 for some 8 0. h(j) = + _r __ where 0:::; r < nj. nJ nJ n r h(j) 1 = . + . 1. nJ nJ (nj)(h(j)1) (nj) + _r 1) nJ nJ n+r(nj) < n. But then, 77
PAGE 84
Clearly, D This shows that if x E lvl(j), then h(j) is the height of the tree associated with x. Definition 5.18 LetS be a non empty set and let r E z+. Define p: r t P(S)\{0} such that S = U P(i), and i :;f l ===} P(i) n P(l) = 0. iEr P is defined to be an order r partition of S. This definition differs from the usual definition of a partition only in that the members are ordered. It has been established that given l En+ 1, each member of level nl has the form x where x E odd(n). If l > 0, then x is nilpotent, and hence its state transition graph is a tree. Furthermore, since odd parity rules preserve levels, the action of such a rule on basic levels, is the same as that of This property provides for the definition of a class of partitions of in terms of basic levels as follows. Definition 5.19 Let j E n. 1. Define 1/Ji : h(j) + 1 + n by ;(!) = { j)l 1/Ji is defined to be the level j delimiter. 78 if l < h(j) if l = h(j).
PAGE 85
2. lfl .. E h(j) + 1, then define { {0} blvlj(l) = () if l = 0 if l > 0. blvli is defined to be block partition j of Z2, and blvlj(l) is defined to be level l of block partition j. Proposition 5.20 If j En, then blvli is an order h(j) + 1 partition of Z2. Proof If l E h(j) + 1, then blvli(l) is nonempty, because it is a union of basic levels. To see that the blvlj(l) are disjoint and cover all of Z2, notice that '1/Ji is strictly monotonically increasing with '1/Ji(O) = 0 and '1/Ji(h(j)) = n. 0 Block partition j contains only .Qat level 0, and unions of nl consecutive basic levels for higher levels, with the exception that the highest level will contain less than nllevels whenever (n l) f n. Corollary 5.21 Let j E n and l E h(j) + 1. Then { 1 if l = 0 #(blvlj(l)) = 1/J;(l) 8 _1 Ls=t/J;(l1)+1 2 otherwzse. Proof This expression simply sums the cardinalities of the basic levels used to form the members of blvli(l). 0 The final theorem of this section asserts that the level structure of the tree associated with an even parity rule x coincides with the block partition associated with the basic level of x. 79
PAGE 86
Theorem 5.22 Let, j E n and x E lvl(j); If l E h(j) + 1 andy E blvli(l), then If furthermore, l > 0, then Proof Let j E n. Since odd parity rules preserve level structure, we need only consider tl:_i E lvl(j). Let l E h(j) + 1 and y E blvli(l). If l = 0 then the result is obvious, so assume l > 0. We lmow that y E lvl(s), where Since we must have To establish the second part of the theorem, assume that l > 0. Then (nj)(l1) = '1/Ji(l1) < s, where s is as above. This implies 80
PAGE 87
Definition 5.23 Let j En and define >..j : + h(j) + 1 by This function clearly assigns toy its level with respect to any x E lvl(j). 5.4 State Transition Graphs for Odd Parity Rules Now that even parity rules have been studied, the structures of graphs for odd parity rules may be determined. First it is necessary to establish two technical results that hold for binary rules of any finite dimension. The first is a variation on a well known result from the theory of finite fields. Proposition 5.24 Let r E z+, s 2: 0 and x, y E Then Proof Proceed by induction on s. The case s = 0 is obvious. Assume the theorem holds for s Then (x + y)2s (x + y)2s (x2s + y2s) (x2s + y2s) Definition 5.25 Let r E z+ and x E Z2. Define e0 + x to be the corule of X. 81
PAGE 88
Because eo + (e0 + x)) = x, it makes sense to refer to a corule pair. Furthermore, since corules differ only at site 0, one rule of the pair has even parity while the other has odd parity. The next proposition asserts that the set of fixed points for a rule equals the kernel of its corule. Proposition 5.26 Let r E z+ and x, y E z;. Then Proof x0y=y::::=? (eo+x)0y=Q.. (eo + x) 0 y = 0 ::::=? eo 0 y + x 0 y = Q. ::::=? y+x0y=Q. ::::=? X 0 y = y. 0 Odd parity rules are invertible, and hence their state transition graphs consist of a set of cycles. We next show that if x E odd( n) and y E Z2, then the x period of y is obtained by determining the level of y in the tree for e0 + x, then rounding that number up to the next power of two. We first formally define the notion of rounding up to the next power of two. Definition 5.27 Let s 0, and define !sl2 is defined to be the power of two ceiling of s. If x E odd(n) then x is invertible, and hence atr(x) = Z2. We may therefore apply Definition 3.40, to obtain that Px(Y) yields the x period of y for each y E Z2. 82
PAGE 89
Theorem 5.28 Let x E odd(n) and j En such that (eo+ x) E lvl(j). Then given y E Z2, Proof First assume In this case, y E ker (eo + x) and, by Proposition 5.26, y is a fixed point for x. Next, let Then We thus have Now eo 0 y + ( + x2s) 0 y eo 0 y +(eo+ x)2s 0 y y+.Q y. If there is a t < 28 such that xt 0 y = y, then the smallest such t must divide 28 But then t must be a power of two that satisfies 83
PAGE 90
By the reverse of the above argument, we must then have But we know that this is not so. 0 Theorem 5.28 provides the following means of counting cycles for odd parity rules. We simply determine the level structure of the tree for the corule, count the number of configurations in the block levels that round up to a given power of two, and then divide power of two ceiling by that power of two. The next theorem formally specifies this process. Theorem 5.29 Let x E odd(n) and j En such that (eo+ x) E lvl(j). Then the state transition graph has cycles of period 21 whenever and all cycles h(we periods of this form. Furthermore, for such j and l, if we let c(j, l) denote the number of cycles of period 21 then ( M '1/Jj(s) ) c(j, z) = 2:: 2:: 2t1 s=211+1 t='I/Jj(s1)+1 Where M = min{21,h(j)}. Proof By Theorem 5.28, all periods are powers of 2 and the period 21 occurs if and only if there is an 8 with 0 :5 s :5 h(j) such that r 812 = 21 In order to determine the number of cycles of period 21 it is only necessary to determine the total number of configurations in the levels that round up to 21 then divide this number by 21 The first summation ranges over the block levels of the tree for e0+x that round up to 21 The upper limit of this summation is M because the height of 84
PAGE 91
the tree may not be a power of 2. The second summation ranges over the basic levels contained in the block level referenced in the first summation. The term 2tl is the number of nodes in the basic level referenced by the second summation. This accounts for all nodes on cycles of period 21 Division by 21 then yields the number of cycles. 0 Clearly, if x, y E odd(n) such that their corules have equal kernels, then they will have isomorphic state transition graphs, while if their corules have different kernels then their state transition graphs will differ in the number of 1cycles. This argument serves to prove the final result of this section. Proposition 5.30 Let x E odd(n) and j E n such that (e0 + x) E lvl(j), then the number of rules with state transition graphs isomorphic to that of x is #(lvl(j)). This completes the proof that the level structure of rule 60 on a space of dimension 2m provides a means to determine the possible isomorphism classes of state transition graphs for members of zr. Since cardinalities of the basic levels are known, we immediately obtain the number of rules associated with any isomorphism class. 5.5 Example Algorithms State transition graphs for two members of C(2,16) are determined in this section. In the first example, we let x0 = 1100101000011000. Since this rule has even parity, it is nilpotent and its state transition graph is a tree. In order to determine the structure of this tree it is only necessary to determine the basic level at which x0 resides. This is accomplished by repeatedly applying 85
PAGE 92
the following procedure to generate inverse images with respect to 8_ until an odd parity rule is obtained. Since complimentary configurations have a common image under rule 60, X1 (0) may be defined arbitrarily. Then, given i > 0, define if x0(i) = 0 if xo(i) = 1. Sites in such a configuration will differ from their left neighbors at exactly those i for which xo(i) = 1. Table 5.1 illustrates the process of taking inverse images with respect to 8_. The first application of the above procedure yields the configuration x1 which also has even parity. The process of taking inverse images is iterated until an odd parity configuration is obtained at x3 Table 5.1 Examples of Pre Images for 8_ x0 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 x1 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 x2 0 1 0 1 1 1 0 1 0 1 0 0 1 0 1 0 X3 1 0 0 1 0 1 1 0 0 1 1 1 0 0 1 1 Since the process was repeated 3 times, we conclude that x0 resides at level 16 3 = 13, and has. a kernel of order 23 = 8. Block level 0 for x0 = {.Q}, block levels 1 through 5 each consist of 3 basic levels, and block level 6 contains only basic level16. The number of nodes at each block level for the rule is simply obtained by summing the numbers of nodes in each of its constituent basic levels. This situation is illustrated in table 5.2. Since x0 86
PAGE 93
moves configurations down by 3 basic levels, the external nodes of the tree are obtained from basic levels 14, 15, and 16. We next determine the graph for Yo = 0100101000011000. This rule has odd parity, and hence, is invertible. To obtain a count of the cycles in its graph, we must first determine the level of Yo+ e0 But Yo+ e0 = x0 and this is the rule considered in the previous example. We thus partition the block levels of the tree for x0 into sets that "round up" to the same power of 2. We then determine the total number of configurations associated with each class and divide by the appropriate power of 2 to obtain the number of cycles of that period. This process is illustrated in table 5.3. In this example, the 8 configurations at levels 0 and 1 reside on 1cycles. The 56 configurations at level 2 yield 56/2 = 28, 2cycles. At levels 3 and 4, we have a total of 4032 configurations resulting in 1008, 4cycles. Finally, the 61440 configurations at levels 5 and 6 yield 7680, 87
PAGE 94
Table 5.2 Level Structure 1100101000011000 Basic Block Internal External Total Level #Nodes Level Nodes Nodes Nodes 16 32768 6 0 32768 32768 15 16384 5 4096 24576 28672 14 8192 13 4096 12 2048 4 3584 0 3584 11 1024 10 512 9 256 3 448 0 448 8 128 7 64 6 32 2 56 0 56 5 16 4 8 3 4 1 7 0 7 2 2 1 1 0 1 0 1 0 1 88
PAGE 95
Table 5.3 Cycle Structure for 0100101000011000 Basic Total Block Nodes at Total Level Nodes Level Level Nodes Period Cycles 16 32768 6 32768 61440 8 7680 15 16384 5 28672 14 8192 13 4096 12 2048 4 3584 4032 4 1008 11 1024 10 512 9 256 3 448 8 128 7 64 6 32 2 56 56 2 28 5 16 4 8 3 4 1 7 8 1 8 2 2 1 1 0 1 0 1 89
PAGE 96
6. Squares of Binary Linear Rules 6.1 Introduction Properties relating to the operation of squaring binary, linear rules are studied in this chapter. First four classes of linear operators on circulant spaces are defined, then the circulant space structure preserved by each class is identified. It is furthermore shown that the composition of two operators of the same type is also an operator of that type (each class may therefore be said to be transitive). The operation that maps a member of to its square is shown to be linear, and matrices for this operation are identified. Finally, the four operations introduced in the next section are used to developed structure pertaining to the operation of squaring linear rules. Throughout this chapter, it is assumed that l, m, n E z+ with n = lm. Given this relation, if i En, then we may write i = jl + r, where j Em and r E l. Conversely, for each such j and r, an expression of the form jl + r yields an element of n. It is thus possible to replace a summation indexed by elements of n with a pair of summations indexed by elements of l and m. This substitution is used in several of the proofs presented in this chapter. 6.2 Circulant Space Homomorphisms Of the four linear operators that are defined in this section, the first three are injective, while the last collapses structure. The definitions are stated so 90
PAGE 97
that the first three operations have C(2, l) as their domain and C(2, n) as their range, while the last operator has domain equal to C(2, n) and range equal to C(2, l). Each operator is subscripted by a pair of integers, with the first integer identifying the dimension of its domain. For each injective operator, the dimension of its range is yielded by the product of the subscripts, and the dimension of the range of the last operator is obtained by dividing the first subscript by the second. Definition 6.1 Define 4>1,m : C(2, l) C(2, n) by { x(i/m) ci>l,mX(t) = 0 otherwise if m I i ViE n. Definition 6.2 Define W1,m: C(2, l) t C(2, n) by Wl,mx(i) = x(i mod l) ViE n. Definition 6.3 Define 81,m : C(2, l) C(2, n) by if i E l { x(i) 8!,mX(t) = O ViE n. otherwise The first of the injective operators spreads a configuration out by inserting m1 zeros after each entry, the second repeats a configuration m times, and the last copies a configuration once then pads the remainder of the image with zeros. For example, if l = 4, m. = 3, and n = 12, then these operators map x = (a, b, c, d) E C(2, 4) into C(2, 12) as follows: (a,O,O,b,O,O,c,O,O,d,O,O), (a,b, c, d, a, b, c, d, a, b, c, d), 84,3(x) (a,b,c,d,O,O,O,O,O,O,O,O). 91
PAGE 98
Definition 6.4 Define An,m : C(2, n) t C(2, l) by An,m(x)(i) = Lx(jl + i) V' i E l. jEm In order to explain the behavior of this operator, we partition n into m segments of length l, and associate members of l with offsets into the segments. Given X E C(2, n), y E C(2, l), and i E l, An,m(Y)(i) is the sum over all segments of the valuations of x at offset i into those segments. For example, let n = 12, m = 3, and l = 4. Now if x = (a, b, c, d, e, J,g, h, i,j, k, l) E C(2, 12), Then A12,3(x) = (a+e+i,b+f+j,c+g+k,d+h+l) E C(2,4). When m = 1, An,m is the identity, while it is the summation homomor phism when m = n. A series of technical results concerning these operators are now presented. We begin with z,m, which preserves all circulant space structure. Proposition 6.5 rng( x(i) = 0 V' i En}. Proof This is immediate from the definition. (2) Let y E C(2, n) such that y(i) = 0 whenever m f i and define x E C(2, l) by x(j) = y(mj) V' j E l. Clearly z,m(x) = y. 0 92
PAGE 99
Next we see that
PAGE 100
To establish injectivity, let r E l, and assume that Then Yo(rm) :1 Yl(rm). Since scalar multiplication is obtained by a finite number of additions, linearity is established once it is shown that addition is preserved. By Propo sition 6.5, we need only consider i En of the form i = mj, where j E l In this case, cl>t,m(xo + xi)(i) (xo + xi)(j) Xo(j) + X1 (j) cl>l,m(xo)(i) + ci>l,m(xi)(i). Next consider circulant multiplication. If i, j En, then ( m IJ and m I (j + i)) m I i. Thus if m f i, then given j En, either m f j or m f ( i + j). In either case, Yo(j)yl(i + j) = 0, and hence, Yo 0 YI(i) = LYo(j)yi(i + j) = 0. jEn Finally, assume that m I i, and evaluate Yo 0 y1 ( i) If i = rm, then m f j Yo(j) = Y1 ( i + j) = 0. 94
PAGE 101
Thus L z,m(xo)(t)z,m(xt)(i + t) = L z,m(xo)(t). tEn tEn mit Application of this substitution now yields Yo 0 Y1 (i) = L z,m(xo)(t)z,m(xi)(i + t) tEn mit sEl sEl xo8x1(r) z,m(Xo 0 x1)(i). Preservation of convolution follows because z,m preserves both conjugation and circulant multiplication. 0 This shows that z,m preserves all circulant space structure. Transitivity is established next. Proposition 6.8 If r, s E z+ such that s = rn, then z rm = n r 0 z m ' Proof First notice that dmn (z,rm) = dmn (z,m) = C(2, l), rng (z,rm) = rng (n,r) = C(2, s), and finally rng(z,m) = C(2,n) = dmn(n,r). 95
PAGE 102
The composition is thus well defined and the proposition asserts equality of functions with the same domain and range. Now let x E C(2, l) and i E s. If rm f i, then
PAGE 103
Proposition 6.10 If x E C(2, l), then Proof Let x E C(2, l) and i En, then we may write Thus It now follows that i = sl + r where s E m and r E l. i = ml(sl + r) = (ms)lr. Wz, m(x)(i) Wz, m(x)( i) x(i mod l) x(r) x(r) Wz,m(x)(i). D Theorem 6.11 W1,m is injective and preserves linear structure. lfm is odd, I then Wz,m also preserves convolution and circulant multiplication while if m is even, then X* y = x 0y = Q 'Vx,y E Wz, m(C(2,l)). Proof Let xo, x1 E C(2, l) and define Yo, Y1 E C(2, n) by Let i En. To establish injectivity of Wz,m, simply notice that Xs(j) = Ys(j) 'V s E 2, j E l. 97
PAGE 104
Thus if Xo # x1 then Yo =/; Y1 To see that Wt,m preserves linear structure, let j E l and i En such that j = i mod l. Then Wz,m(Xo + xt)(i) (xo + xt)(j) xo(j) + x1(j) Wz,m(xo)(i) + Wz,m(xi)(i). It immediately follows that scalar multiplication is also preserved. Now con sider circulant multiplication. Let i E n. In the following summation over t E n we make the substitution t = sl + r, then sum overs Em andrE l. We also assume that j = i mod l. Now Yo 0 Y1(i) = LYo(t)yl(i + t) ten L LYo(sl + r)y1(i + (sl + r)) sEm rel L L:xo(r)xl(j + r) sEm rEl mL:x0(r)x1(j+r) rEI m(xo 0 x1)(i). Since multiplication by m is performed modulo 2, this establishes the result for circulant multiplication. Furthermore, since Wz,m preserves conjugation, the analogous result holds for convolution. 0 Finally, transitivity is established. 98
PAGE 105
Proposition 6.12 If r, 8 E z+ such that s = rn, then Proof As with the Proposition 6 8 all operators have the appropriate do mains and ranges. Notice that since l I n we have This yields t mod l = (t mod n) mod l Vt E 8. Wn,r(Wt,m(X) )(t) Wt,m(x)(t mod n) x((t mod n) mod l) x(t mod l) Wt,rm(x)(t). D Wt,m clearly preserves less structure than 1,m, because multiplicative structure is preserved only for odd values of m. Next we see that 81,m always preserves linear structure, but never multiplicative structure. While el,m preserves the least structure of the three injective operators, it will still prove useful in the characterization of square roots of configurations. We begin by establishing its range. Proposition 6.13 rng(81,m) = {x E C(2,n) I i > l => x(i) = 0 ViE n}. Proof (5;) This is immediate from the definition. (2) Let y E C(2, n) such that y(i) = 0 whenever i l and define x E C(2, l) by x(i) = y(i) Vj E l. Then 8t,m(x) = y. D 99
PAGE 106
Theorem 6.14 81,m : C(2, l) t C(2, n) is injective and preserves linear structure. Proof Let xo, Xt E C(2, l) and define Yo, y1 E C(2, n) by 81,m is easily shown to be injective. Simply notice that Xs(j) = Ys(j), V s E 2j E l. Thus if x0 =/= x1 then Yo =/= y1 To establish that addition and scalar multipli cation are preserved, notice that if i En\ l, then y(i) = 0 Vy E rng (8!,m). We need only consider i E l. In this case, 8l,m(Xo + Xt)(i) (xo + Xt)(i) xo(i) + Xt(i) 8!,m(xo)(i) + 8!,m(xr)(i). D Since this operator copies a 'configuration once then pads the remainder of the range with zeros, establishment of transitivity is trivial. To see that multiplicative structure is not preserved, let m > 1. If y E rng (8!,m) with y(l) =/= 0, then y(n1) =/= 1, 100
PAGE 107
and hence x tf. rng (8z,m). This shows that rng (81,m) is not closed with respect to conjugation. Since e1 E rng (8z,m) and ei = ez tf. rng (8z,m), it follows that rng (8z,m) is not closed with respect to convolution. To see that circulant multiplication is not preserved, notice that given x E C(2, n), x 8 e0 = x e0 = x. The final operator in this section is now shown to be a circulant space homomorphism. Preservation of conjugation is established first. Proposition 6.15 If x E C(2, n) and i E l, then An,m(x)(i) = An,m(x)(i). Proof Let x E C(2, n), andy E C(2, l) such that y = An,m(x). Since j = 0 :=} (mj) mod m = 0, it follows that mj ranges over all values of mas j does. Thus if i E l, then y(i) = y( i) :Lx(jli) jem :Lx((mj)l + i) jem An,m(x)(i). 0 Theorem 6.16 An,m : C(2, n) C(2, l). Furthermore, rng (An,m) = C(2, l). 101
PAGE 108
Proof Let Xo, X1 E C(2, n), Yo, Y1 E C(2, l) such that An,m(xs) = Ys 'V s E 2. Let i E l. We first consider linear structure. (Yo+ yl)(i) Yo(i) + Yl(i) :Lx0(jl + i) + :Lx1 (jl + i) jEm jEm :L)xo + x1)(jl + i) jEm An,m(Xo + xl)(i). To show that circulant multiplication is preserved, we again make the substitution sl + r = t, where t E n, s E m, and r E l. Then L(xo 0 x1)(jl + i) jEm L :Lxo(t)x1 (jl + i + t) jEm tEn L L L:xo(sl + r)x1 (jl + i + sl + r) jEmsEm rEI rEI sEm jEm rEI sEm jEm L L Xo(sl + r)An,m(xl)(i + r) rEI sEm L An,m(xo)(r)An,m(xl)(i + r) rEI An,m(xo) 0 An,m(xl)(i). 102
PAGE 109
Combining this result with proposition 6.15, proves that convolution is also preserved. We finally show that the range of An,m is all of C(2, l). Let y E C(2, l), i En, and define x E C(2, n) by x(i) = { if i E l otherwise. Then, given i E l, An,m(x)(i) L:x(jl + i) jEm x(i) + L x(jl + i) j>O x(i). 0 Corollary 6.17 Ifx E C(2,l), then An,m(8t,m(x)) =X. Proof Notice that for each i E l, el,m(x)(i) = x(i), while if j E n\l, then el,m(x)(j) = 0. The result now follows from the definition of An,m 0 The final proposition pertaining to this operator establishes transitivity. Proposition 6.18 If r, s E z+ such that l = rs, then An,rm = At,r 0 An,m 103
PAGE 110
Proof The range of An,m is C(2, l) as is the domain of A!,r This shows that the composition is well defined. The functions are comparable because C(2, n) is domain of both An,m and An,rm, while An,rm and A!,r both have ranges equal to C{2, s). Given c E rm we may write c = dr + b where d E m, and b E r. Letting i E s, we now have An,rmX(i) Lx(cs+i) cErm LLx((dr + b)s +i) bEr dEm LLx(drs + bs +i) bEr dEm L An,m(x)(bs + i) since rs = l bEr A!,r(An,m(x))(i). D Each of the operators defined in this section has been shown to be linear, and hence each may be represented by a matrix with respect to canonical bases. While these matrices are not circulant, their forms are somewhat suggestive of circulant matrices The following four matrices represent the the operators corresponding to the examples presented at the beginning of this chapter. We begin with the matrix for A12,a 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 104 1 0 0 0 1 0 0 0 1 0 0 0
PAGE 111
The following matrices represent 4 3 'l14 3 and 84 3 respectively. 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 6.3 Properties of the Squaring Operator Proposition 5.24 established the linearity of the squaring operator. In this section matrices associated with this operation are presented, and the four linear operators defined in the previous section are used to identify structure associated with the operation of squaring linear rules. This theory includes the characterization of rules that possess square roots and the identification of those square roots. Definition 6.19 Let n, 8 E z+, and let An,s denote the matrix associated with exponetiation of ndimensional configurations by 28 If 8 = 1, the nota tion An may be used. An is said to be the n dimensional squaring matrix. If x E C(2, n) and i En, then we recall that x x(i) = Lx(k)x(ik). kEn 105
PAGE 112
Now if j E n, such that j + j = i, then x(j)x(j) occurs in this sum. Since binary digits are idempotent, we have x(j)x(j) = x(j). If i j = r =1j, then x(j)x(r) and x(r)x(j) occur independently in the calculation of x x(i). Since they are equal, and arithmetic is performed modulo two, they must cancel. Thus to compute x x(i) it is only necessary to sum x(j) over the set of solutions to the equation 2j = i. This motivates the following definition. Definition 6.20 Let n E z+ and i E n. Define Sn,i = {j E n I 2j mod n = i}. The above comments serve to prove the next proposition. Proposition 6.21 If n E z+ and i E n, then x x(i) = L x(j). jESn,i The nature of Sn,i depends on the parity of the dimension. The next definition introduces a permutation that identifies Sn,i when the dimension is odd. Definition 6.22 Let l E z+, such that l is odd. Define Uz : l t l by Uz(j) = 2j mod l't/ j E l. Uz is said to be the squaring permutation of order l. 106
PAGE 113
Proposition 6.23 If l E zk is odd then CTt is a permutation. Proof It suffices to show that Ut is surjective. Let i E l. If i is even, then i /2 is an integer and 2(i/2) = i. If i is odd then i + l is even, and hence 2((i + l)/2} = i + l = i(mod l). 0 Inverse images via 0"1 were identified in the proof of this proposition. Corollary 6.24 Given i E l, { ;2 O"/l(i) = '/, (l + i)/2 if i is even if i is odd The next proposition links u1 to the operation of squaring members of C(2, l). Proposition 6.25 If l E z+ is odd, i E l, and x E C(2, l), then Proof u!1(i) is a solution to 2j = i. Since u1 is a permutation, this solution Is umque. 0 Theorem 6.25, clearly shows that A1 must be the permutation matrix associated with u1 This matrix is defined by At(i,j) = 1 :::::::? i = Ut(j) 'ViE l. 107
PAGE 114
Furthermore, we know from basic linear algebra that A1AT l l. Clearly, Ai1 corresponds to the operation of taking square roots. For exam ple, letting l = 7, and noting that row and column numbering of matrices begins at zero, we have 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 A1 = 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 A12 = 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 In this example, A ATA1 7,27 7 This occurs because is the identity permutation. Since CTt determines squares of members of C(2, l), we see that the oper ations of squaring and extracting square roots in spaces of odd dimension are inverses. This is not so when the dimension is even. The next theorem characterizes Sn i for this case. 108
PAGE 115
\ \ Proposition 6.26 Let n E z+ be. even. Then given x E C(2, n) and i En, Sn i = { {x(i/2), + i)/2)} 0 if i is even if i is odd. Proof If i is even then both i/2 and i/2 + n/2 are clearly solutions to 2j = i. If j E n such that j {0, n/2} then 2j 0 mod n, and hence 2(i/2 + j) i mod n. This establishes the proposition if i is even. Next assume that i is odd. Clearly, for each j E n, 2j is even. Because n is even, 2j mod n must also be even. Thus 2j = i has no solutions. 0 The squaring matrices for spaces of even dimension are characterized next. Corollary 6.27 If n is even, then An is defined by An(i,j) = { 1 0 ifi is even and 2j = i otherwise. While continuing to maintain the equality n = lm, we furthermore let r E z+ and assume that m = 2r. The theory of exponentiation of elements of C(2, n) by 28 where s :::; r is studied next. The following example illustrates the pattern for this operation. Let x E C(2, 12), and consider x4(i) where i E {3, 6, 8}. First 109 
PAGE 116
since 3 is odd and x4 is itself a square. Next, 6 is even and This is so because 3 and 9 are both odd. Finally, x4(8) = x2(4) + x2(10) = x(2) + x(8) + x(5) + x(ll). This is the only case for which x(i) may possibly be nonzero x4(8) is a sum of 4 valuations of x, and one of these is at index 2 = 8/4. The remaining values are offset from index 2 by multiples of 3 = 12/4. The next proposition shows these properties hold in general. Proposition 6.28 Let l, m, n, r, s E z+ be as above, and let t = n/ (28). If i En then, 8 { ""'3 E 2s X(i/(28 ) + j't) x2 (i) = 'ViE n. otherwise Proof We proceed by induction on s. The case s = 1 has already been established, so let s > 1, and that the proposition holds for s1. First assume that 28 f i. If i is odd then since So let i be even. Now i/2 is an integer, and 28l f i/2. 110
PAGE 117
Furthermore, since 28 I n, 28l I n/2, and hence, 2 8 1 f (i + n)/2. By the induction hypotheses, x2l (i/2) = x2l ((i + n)/2) = 0. This yields x2 (i) = 0. Next assume that 28 I i. Then x2 (i) x2l (i/2) + x2l ((i + n)/2) G!:, +2jt) +2jt) L X ( ;8 + jt) + LX ( ;8 + ; + jt) ;e:z ;e:z 2lj 2lj LX (;8 +jt) +LX (;8 +t+jt) ;e:z ;e:z :Zij 21j LX (i/28 + jt). D jE25 The following matrices yield the operations of squaring and exponentia tion by four on C(2, 8). 111
PAGE 118
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 Aa = 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Aa,2 = 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 The next proposition utilizes 1 2 in the characterization of squares in C(2, 2l). Proposition 6.29 If l, n E z+ with n = 2l, then rng(z,2) = {x21 x E C(2,n)}. Proof (2) Proposition 6.5 states that rng (z,2) = {x En 12 f i ===> x(i) = 0}, while Proposition 6.28 shows that each square is a member of this set. Let y E rng ( z,2). Say X E C(2, l) andy = z,2(x ). 112
PAGE 119
Now let z = 8z,2(x). If i E l, then z2(2i) = z(i) + z(i + l) = z(i). But z( i) = x( i) = y(2i). Thus For example, if l = 3 and x = (a, b, c) E C(2, 3), then Y = a,2(x) = (a, 0, b, 0, c, 0), and z = 8a,2(x) = (a, b, c, 0, 0, 0). Clearly, z2 =(a+ 0, 0, b + 0, 0, c + 0, 0) = y. Since the squaring operator is not surjective when the dimension is even, and C(n, 2) is finite, it cannot be injective. The next proposition identifies its kernel. Proposition 6.30 If l, n E z+ such that n = 2l then {x E C(2, n) I x2 = 0} = rng ('llz,2). 113
PAGE 120
Proof Let y E C(2, n) and i E l. Then y2(2i)=O y(i)+y(i+l)=O y(i)=y(i+l) ::Jx E C(2,l) such that y = W1 ,2 (x). 0 The squares in spaces of even dimension have been identified, and given such a configuration, we know how to construct one square root. We also know the kernel of the squaring operator. Since squaring is linear, the set of square roots of a square is a coset of the kernel. The next theorem uses this information to identify the set of square roots of a given square. Theorem 6.31 Let l, n E z+ such that n = 2l. Let X E C(2, l) andy E C(2,n) such that q'?1 ,2 (x) = y. Then {z E C(2, n) I z 2 = y} = el,2(x) + rng (Wt,2). Proof It has already been shown that and rng(Wt,2) = {x E C(2,n) I x 2 =.Q}. Finally notice that 8 1 2 (x) + rng (\111 2 ) is a coset of the kernel of the squaring operator. 0 If we let #(C(2, l)) = d, then, since z,2 and 81 ,2 are injective, #(rng (1,2)) = #(rng (8t,2)) =d. Furthermore, #(C(2, 2l)) = d2 114
PAGE 121
' It h,as now been establishedthat C(2, l) is a subspace of C(2, 2l) via the action of <1>1 2 This accounts for d members of C(2, 2l). In addition, each member of this subspace has d square roots. Since this accounts for all members of C(2, 2l), we see that much of the algebraic structure of C(2, 2l) is obtainable from the structure of C(2, l). This property will be heavily exploited in the following two chapters. We now show that the last of the four operators defined in the previous section is also closely related to the operation of squaring. Consider the following example. Let x = (a, b, c, d, e, f) E C(2, 6). Clearly, x2 =(a+ d, 0, b + e, 0, c + f, 0), and As,2(x) = (a+d,b+e,c+f). We also know that 3,2(a + d, b + e, c +f) = (a+ d, 0, b + e, 0, c + j, 0). This example suggests that An,2 and the squaring operator are isompophic operations. The next theorem shows that this relationship holds for expo nentiation by any powers of two that divides n. Theorem 6.32 Let l, m, n, r E z+ such that m = 2r and n = lm. Then, for anyx E C(2,n), 115
PAGE 122
Proof Let i En. If m f i, then Also, in this case, l,m(Y)(i) = 0 'Vy E C(2, l). So assume i = mj, where j E l. By Theorem 6.28, xm(i) = Lx(j + sl). sEm But, the right side of this expression is the definition of A1,m(x)(j). Now apply the definition of 1,m D Corollary 6.33 Given s, n E z+' the mapping X I+ X28 is a circulant space endomorphism on C(2, n). Theorem 6.16 asserts that An,m preserves circulant space operations. Since exponentiation by powers of two also preserves circulant operations, we now have an alternate proof of this theorem when m = 2r. 6.4 An Embedding of C(2, l) into C(2, 2l) In the previous section it was shown that the set of squares in C(2, 2l) equals the range of 1 ,2 and that each square has exactly 21 roots. The next theorem simply formalizes this statement. Theorem 6.34 Let l, n E z+, with n = 2l. Then C(2, n) = U {y I y2 = 1,2(x)}. xEC(2,!) Furthermore, the union is disjoint. 116
PAGE 123
We next use this theorem to show that invertible and nilpotent members of C(2, 2l) may be determined once the corresponding members of C(2, l) have been identified. Theorem 6.35 Let l E z+. Let X E C(2, 2l). 1. x is invertible
PAGE 124
have established that for any r E z+, one half of the elements of C(2, 2r) are invertible and one half are nilpotent. This agrees with the result obtained in Chapter 5. The following theorem further links the structure of C(2, l) with that of C(2, 2l). It essentially asserts that given x E C(2, l) and z E C(2, 2l) such that z2 =
PAGE 125
7. Idempotent Binary Rules 7.1 Introduction Rules that are equal to their own squares are called idempotents or pro jections. In this chapter idempotent operators are characterized, and several technical results are established. The main result asserts that a distinguished direct sum decomposition of C(2, k) may be expressed in terms of ranges of projections. It is furthermore shown that circulant space operations are "well behaved" with respect to this decomposition. This theory will be used in the next chapter in the study of state transition graphs for members of C(2, 2rl), where l is odd and r > 0. As in the last chapter, we assume that n = lm. In addition we assume that l is odd and r E w such that m = 2r. Finally we assume that k is an arbitrary member of z+. 7.2 General Properties of Projections In this section basic properties of projections are developed within the context of rings of linear operators. Definition 7.1 Let R be a ring. If A E R such that A2 =A then A is said to be idempotent. When R is a ring of operators on a vector space, idempotents are also 119
PAGE 126
called projections. The next proposition justifies this terminology. Proposition 7.2 Let R be a ring of linear operators on a vector space V. If A E R, then A2 =A Av = vVv E rng (A) Proof ( ==}) Assume thatA2 = A and v E rng (A) say Au = v. Since A2=A, Av A2u Au v. ( {::::::::) Assume that the hypothesis and let u E R. Then A2(u) = AAu =Au. Thus A= A2 o Idempotent operators occur naturally in pairs that sum to the identity. The next theorem establishes this fact, and furthermore shows that such a pair provides a direct sum decomposition of the underlying space. Proposition 7.3 Let R be a ring of linear operators on a vector space and let I be the identity in R. If A E R such that A2 =A, then 1. (IA)2 =IA. 2. V = rng (A) EB rng (IA). 120
PAGE 127
Proof 1. If A2 = A, then I22IA+A2 I2A+A IA. 2. Clearly A+ (I A)= I. Thus, by symmetry, it suffices to show that. rng (A) = ker (I A) Let v E V. Now (IA)v = 0 Iv = Av v=Av v E rng (A) D 7.3 Characterization of Projections on C(2, k) Theory developed in the previous chapter may now be used to identify idempotent members of C(2, k). Idempotent members of C(2, k) will be denoted by the Greek letter "1r". This symbol will often be subscripted or accented. Furthermore, this notation is reserved for idempotents. Definition 7.4 Let k E z+ and define P(k) = {7t E C(2, k) l1r2 = 1r }. P(k) is defined to be the space of idempotent, kdimensional, binary config urations. 121
PAGE 128
Before entering into the characterization of P(k), some simple examples of projections are presented. Proposition 7.5 Let k E .z+, 1. Q, eo E P(k). 2. If k is odd, 1, e0 E P(k), while if k is even, then l, e0 P(k). Proof 1. Clearly, Q2 = Q, and e6 =eo. 2. Since 1 = eo + e0 it is only necessary to establish the result for 1. If i E k, then I: 1(j)1( i + j) jEk Since multiplication by k is performed module 2, the result follows. D This shows that spaces of even dimension always contain at least two idempotents, while spaces of odd dimension contain at least four. There are instances for both even and odd dimension where these minimums are obtained. The next proposition shows that fundamental behavior of 1 and eo may be expressed in terms of parity. Proposition 7.6 Let l E .z+ be odd. Then: 122
PAGE 129
1. rng (1) = HLl}. 2. If x E C(2, l), then 10 x = .Q x E even(l). 3. rng (eo) = even(l). 4 If X E odd(l), then eo 0 X= X. Proof 1. Let x E C(2, l) and i E l. Then l0x(i) Ll(j)x(i + j) jE! :Lx(i + j) jE! 2. This follows immediately from (1). 3. First notice that if x E C(2, l), and i E l, then eo 0 x(i) :Leo(J)x(i + j) jE! L:x(i + j) jEI NO :Lx(r) rEI r;o!i + x(i). The last equality follows since x(i) was omitted from the sum in the immediately preceding equality, and x(i) + x(i) = 0. Now if = 0, then eo 0 x(i) = x(i). 123
PAGE 130
This shows that rng (e0 ) 2 even(l). If L:x = 1, then eo 0 x(i) = x(i) + 1. To complete the proof, notice that complimentation changes parity when the dimension is odd. 4. This result was established in the proof of (3). D Since 1 + e0 = e0 we have the direct sum decomposition C(2, l) = rng (1) ffi rng (eo). This decomposition will be called the parity decomposition of C(2, l). The parity decomposition provides a nontrivial example of a direct sum decomposition of C(2, l) that is generated by a pair of idempotent members. In order to developed the general theory of such decompositions, we must first identify the idempotents. We begin by examining the squaring permutation. Definition 7. 7 Let l be odd. Then: 1. Let i E l and define [i]1 = {af(i) 1 j E z+}. (i]1 is defined to be the orbit of i with respect to (]'l 2. Define orb (l) = {[i]! I i E l}. orb (l) is defined to be the orbit partition of l generated by(]'! The following table defines (]'l for all odd values of l between 1 and 21. 124
PAGE 131
Table 7.1 Definitions of u1 by Cycles Dim I Cycles 1 (0) 3 (0) (12) 5 (0) (1 2 4 3) 7 (0) (1 2 4) (3 6 5) 9 (0) (3 6) (1 2 4 8 7 5) 11 (0) (1 2 4 8 5 10 9 7 3 6) 13 (0) (1 2 4 8 3 6 12 11 8 5 10 7) 15 (0) (5 10)(1 2 4 8) (3 6 12 9) (7 14 13 11) 17 (0) (1 2 4 8 16 15 13 9) (3 6 12 7 14 11 5 10) 19 (0) (1 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10) 21 ( 0) ( 7 14) ( 3 6 12 ) ( 9 18 15) ( 1 2 4 8 16 11) ( 5 10 20 19 1 7 13) The next proposition shows how u1 may be used to construct the idempotent members of C(2, l). This will be followed be a proof that there is a bijection between P(l) and P(2rz), for each r E z+. Proposition 7.8 = {7r E C(2,l) I [i]L = [j]L ::::::::}7r(i) = 7r(j)Vi,j E l}. Proof Let i,j E l such that i =I j and let [i]1 = (j]1 say t( ) J = (J"l '/. where t 1. If 71" E P( l) then 125
PAGE 132
But This implies 7r(i) = 7r(j). Conversely, if 7r is constant over each orbit of then it follows by the reverse of the above argument that 1r = 1r2 D Corollary 7.9 #(P(l)) = 2#(orb(l)). Proof There are clearly 2#(orb(t)) ways of assigning a binary digit to each element of orb (l) D Proposition 7.10 If r > 0, then Proof It is only necessary to show that P(2k) = (f}k,2(P(k)) 'V k E z+, because this property alone establishes a base for an induction, and this property along with transitivity of if} establishes the induction step. So let 7ro E P(2k). Since 7ro equals its own square, we must have Say, 126
PAGE 133
Since k,2 preserves convolution, we must also have 1rr = 1r1 This shows that
PAGE 134
Proposition 7.13 If 1r0 1r1 E P(k),then 7fo < 1f1 :::=} rng (7ro) rng (1r1). Proof (==}) Assume 7fo< 1r1 and let x E rng (7ro). Then 7fo 8 x = x, and hence (1r1 1fo) 8 X= X. But Assume that rng (7ro) rng (7rl) and let X E C(2, k). Now because it follows that (1r1 7ro) 8 x = 1f1 8 (7ro 8 x) = 7fo 8 x. 0 Corollary 7.14 (P(k), <) is a partial ordering. Proof By the proposition, 7f tt rng ( 7f) yields a relation preserving surjec tion from ( P ( k), <) to ( { rng ( 7f) I 7f E P ( k) }, Since set inclusion is clearly a partial ordering, establishment of injectivity will complete the proof. Now if 7fo, 1f1 E P(k), then 128
PAGE 135
Each positive integer factors uniquely into the product of an odd number and a power of two. We next show that if two integers have the same odd component, then the partial orderings on the sets of idempotents in the circulant spaces of those dimensions are isomorphic. Proposition 7.15 If s, t E z+, then is a poset isomorphism. Proof By Corollary 7.11, 8 ,2t provides a bijection between P(s) and P(s2t). Since s,2t preserves convolution, it must also preserve the partial ordering. D P(k) closed with respect to convolution, and the product of two projec tions has the additional property of being their greatest lower bound. These facts are established in the next two propositions. Proposition 7.16 If 1r 0 1r 1 E P(k), then 1To 1r1 E P(k). Furthermore, and Proof Since convolution is commutative, ( ) 2 2 21To 1T1 = 1To 1T1 1To 1T1. 129
PAGE 136
To complete the proof, show that Let x E rng ('rro 1r 1). This is equivalent to (7ro 1r1) 8 X= X. By symmetry, it suffices to show that X E rng (7ro). Now Thus 7ro 8 x 7ro 8 ((7ro 1r1) 8 x) (7ro (7ro 1r1)) 8 x (7r5 7rl) 8 X (7ro 1r1) 8 x X. 7ro 8 X = 1T"1 8 X = X. Proposition 7.17 /f7ro,7r1,7r2 E P(k) such that 1r2< 7ro,7r1,then Proof Assume the hypothesis. This means that 130
PAGE 137
Thus Squaring is a linear operation on C(2, k). Thus if 1r 0 1r 1 E P(k), then This proves the following proposition. Proposition 7.18 P(k) is closed with respect to addition. An alternate proof of this proposition follows upon noting that the sum of two configurations in C(2, l), each of which is constant over the orbits of u1 must also be constant over those orbits. By combining Propositions 7.16 and 7.18 we see that 7ro, 1r1 E P(k) ===} 7ro + 1r1 + 7ro 1r1 E P(k). We next show that this expression yields the least upper bound for 7ro and 7rl Proof 131
PAGE 138
1. Assume the hypothesis. By symmetry it is only necessary to show that 1To 1T2. Then 1To 1To + 1To 1T1 + 1To 1To 1T1 1To + 1To 1!'1 + 1To 1T1 1To. 2. Assume the hypotheses. Then In the theory of partial orderings, the terms "join" and "meet" are used in place of "least upper bound" and "greatest lower bound" respectively. The uniqueness of joins and meets follows from the anti symmetry property of partial orderings. Propositions 7.17 and 7.19 assure us that the following definitions make sense Definition 7.20 Let 1r0 1r1 E P(k) and define 1. 1To V 1T1 = 1To + 1r1 + 1To 1T1 to be the join of 1To and 1r1 2. 1To A 1T1 = 1To 1r1 to be the meet of 1To and 1r1 A partial ordering with joins and meets is defined to be a lattice. The proof of the following theorem is already complete. 132
PAGE 139
Theorem 7.21 (P(k), <, V, A) is a lattice . In the course of developing the lattice structure of P(k), it was established that this set is closed with respect to addition and convolution. We next show that it is closed with respect to conjugation. From this it will follow that it is closed with respect to circulant multiplication. A lemma showing that the orbit partition is closed with respect to negation is presented first Lemma 7.22 If l odd and i E l, then [i)z E orb (l). Proof This lemma simply states that the set of negatives of members of an orbit is also an orbit. Given i E l, it follows from the definition of [i]1 that i, 2i, 4i, 8i, ... E [i]1, and all of [i]z is obtained in this way Similarly, [i]l = { i, 2i, 4i, 8i, ... }. This shows that [i]1 = [i]z. 0 Since orb (l) partitions l, given i E l, either [i]z = [i]z or [i]z n[i]z = 0. Inspection of table 7.1 shows that both situations may occur. Proposition 7.23 Let k E z+. If 1r E P(k) then 1f E P(k). Proof Let 1r E P(k) and first assume that k is odd. Now 1r is constant over each orbit, and by Lemma 7.22, 1f must also be constant over each orbit. If k is even, then simply notice that ci> k m preserves conjugacy. 0 133
PAGE 140
Proposition 7.24 If 1r E P(k), then rng (1f) = rng ( 1r ). Proof Since it follows that 7r 0 y = y 1f 0 y = y. D While P(k) is always closed under addition and convolution, it cannot be closed under complimentation if k is even, because in this case idempotents must evaluate to zero in all odd positions. However, since lis odd, Theorem 7.27 will establish that P(l) is closed with respect to complimentation and, since circulant multiplication may be obtained from conjugation and convo lution, it will also follow that P(l) is a subcirculant space of C(2, l). Since lf>z,m preserves all circulant space operations, we will have proved the next theorem. Theorem 7.25 P(k) is a subcirculant space oJC(2,k) 'Vk E z+. It is sometimes useful to simplify a partial ordering by removing some of the elements of the relation, while keeping enough structure so that the original relation may be recovered by taking the transitive closure of the simplified relation. The relation presented in the next definition provides such a simplification of (P(k), <). Definition 7.26 Let 1r0 E P(k) and 1r1 E P(k)\{1r0}. Define 1r1 to be an immediate predecessor oj1r0 if given 1r E P(k), 134
PAGE 141
If 1r1 is an immediate predecessor of 1r0 we then write "1r1 1r0 ". The next theorem completes the proof of Theorem 7.25 Theorem 7.27 If l is odd and 1r E P(l), then: 1. 7r E P(l). 2. If 1r E P ( l) n even( l) then rng (if) = {Q, 1} EB rng ( 1r) and 1r 7r. Proof 1. If 1r E P(l), then 7r2 = (7r + 1)2 = 7r2 + 1 7r + 1 7r + 12 = 7r + 1. 2. Let 1r E P(l) n even(l). Since 1r E even(l), rng (1r) even(l). Thus {Q,1} EB rng{1r) is defined. Now if x E even(l), then This implies Similarly, 7r8x+18x 1r 8x + Q. (1r + 1) 8 (x + 1) 7r 8 X+ 18 X+ 7r 81 + 181 7r 8 X + Q + Q + 1. 135
PAGE 142
Thus ( 7!" + 1) 0 (X + 1) = X + 1 <==? 7!" 0 X = X. To complete the proof, notice that 7!" 7r because their ranges differ in dimension by only one. 0 Next t:Q.e semi groups (odd( l), *) and (even( l), *) are shown to be isomor phic via the operation of complimentation. Upon combining this result with Theorem 7.27 it follows that (odd(l) n P(l), ) and (even(l) n P(l), ) are isomorphicsubrelations of (P(l), ). Theorem 7.28 Complimentation provides an isomorphism between (even( l), *) and (odd(l), *). Proof It has already been shown that complimentation is a bijection. To see that convolution is preserved, let x, y E odd(l). Since 1 is self conjugate, the previous theorem yields 1 x = 1 y = 1. Thus, (X + 1) (y + 1) X*Y+1+1+1 X*Y+1. D The identity on the C(2, l) is eo. Since e0 has odd parity, it must also be the identity on odd(l). The next corollary establishes the identity on even(l). Corollary 7.29 e0 is the identity on even(l). An even parity projection may only be preceded by another even parity projection. This is so because if 7!"0 7!"1 E P(l) with 1r1 E even(l), then' 7ro 7!"1 E even(l). 136
PAGE 143
But, by definition, 7ro = 7ro 1r1 whenever 1r 0 < 1r 1 By contraposition an odd parity projection may only be succeeded by an other odd parity projection. These properties hold in all dimensions, because 1,m preserves both convolution and parity 7.5 Direct Sum Decompositions It is possible to decompose C(2, k) into a direct sum of ranges of projec tions. For example, given any 1r E P(k), we have C(2, k) = rng (1r) EB rng (eo 1r). In this section direct sum decompositions of C (2, k) into ranges of idempotent rules are characterized and it is shown that circulant space operations are "well behaved" with respect to them. The following proposition establishes a condition under which a decomposition can be refined. Proposition 7.30 Let 1r 0 1r 1 E P(k) such that 1r 1 < 7ro. Then, defining yields Proof Since 1r1 < 1r 0 we have 137
PAGE 144
Thus Given x E rng (rr0 ) it follows that X 1ro 0 X To complete the proof, it is only necessary to show that So assume Since 1r1 < 7ro, we also have 7ro 0x = x. This yields 7ro 0 X + 7rl 0 X x+x Q. 0 Corollary 7.31 If the direct sum decomposition C(2,k) = E9rng (1ri) jEr 138
PAGE 145
is such that there exists j0 E r and rr' E P(k) such that rr' < 7rj0 then the decomposition may be refined so that C(2, k) = EB rng (rrj) EB rng (rr') rng (7rj0 rr'). jEr #io This corollary provides a means of refining direct sum decompositions of C(2, k), and a variation of this refinement process will be used to show that the set of minimal projections, to be defined next, provides a distinguished basis for P(k). Definition 7.32 Let k E z+ and define M(k) = {rr E P(n)\ {.Q} 1rr' 7r ===* rr' = .Q}. M(k) is said to be the set of minimal members of P(k). While we continue to denote arbitrary members of P(k) by the symbol "rr", members of M(k) will be denoted by the symbol "x". Since elements of M(k) are binary sequences, they possess a natural ordering. Whenever the notation "Xi E M(k)" is used, i will indicate the position of Xi with respect to this ordering. We now show that the set minimal projections always yields a direct sum decomposition of C (2, k). From this result, it easily follows that M(k) is a basis for P(k). Theorem 7.33 If k E z+, then C(2, k) = EB rng (x). xeM(k) 139
PAGE 146
Proof Two steps are required for this proof. First it must be shown that C(2, k) may be expressed as a direct sum of ranges of minimal projections. Then we must establish that any such decomposition must involve all members of M(k). To begin, notice that C(2, k) = rng (eo), and this yields a trivial decom position. If e0 E M(k), then we are done. Otherwise, Proposition 7.30 and its corollary assure us that a finer decomposition may be obtained. If the resulting pair of projections are not both minimal, then the process may be repeated. Since there are only a finite number of projections, this process must terminate with a direct sum decomposition, C(2, k) = E9 rng (Xi), where S M(k). xes To complete the proof, assume that 3 E M(k)\S. Given x' E S, we must have x f. x', because both X and x' are minimal. But we also know that x< eo. Thus at some point in the process, there must be a 1r0 E P(k) such that X < 1T'o but when 1r0 is split into a sum, say we have both 140
PAGE 147
This means that Since x E M(k), it follows that But, since X < 1r0 we have X X* 1ro .Q. This is a contradiction. D Definition 7.34 Let k E .z+. 1. Define ffix;eM(k) rng (Xi) to be the canonical direct sum decomposition of C(2, k). 2. M(k) is said to be the canonical basis for P(k). Most of the work required to show that M(k) is indeed a basis was done in Theorem 7.33. Theorem 7.35 M(k) is a basis for P(k). Proof To establish linear independence, let Xi E N!(k) and x E rng (Xi)\ {.Q}. 141
PAGE 148
Now X 0 x = x and, by Theorem 7.33, it follows that Xi 0 x = .Q, whenever j :f. i. Thus no member of M(k) may be a linear combination of the others. We now show that M(k) spans P(k). Let 1r E P(k)\{.Q}, and define s1r = {xi e M(k) 1 Xi < 1r }. The refinement process used in the proof of Theorem 7.33 may be applied to rng (1r), yielding the result rng (1r) = E9 rng (Xi). XiES In other words This theorem shows that each member of P(k)\{.Q} is the sum of its predecessors in M ( k). Since .Q has no predecessors in M ( k), such a sum is not defined for this case. We therefore adopt the convention that a summation of configurations over the empty set yields .Q. We now have a bijection between members of P(k) and subsets of M(k), and an expression for the cardinality of P(k) in terms of orbits of the squaring permutation. The next theorem simply combines these results. Theorem 7.36 If l,n,r E z+ such that lis odd, and n = l2r, then #(M(n)) =#(orb (l)). Proof By Corollary 7.9 #(P(n)) = 2#(orb(l)), 142
PAGE 149
and, by Theorem 7.35, #(P(n)) = 2#(M(n)). 0 It is well known that given a nonempty set, its power set is a lattice, in which the order relation is set containment, and joins and meets are yielded by set union, and intersection respectively. We next show that the bijection established by Theorem 7.35 is a lattice isomorphism. Theorem 7.37 Given k E z+, the following relationships hold: 1. eo = .Z::::x;EM(k) Xi 2. If S M(k), then eo+ .Z::::x;es Xi = .Z.:.::x;EM(k)\S Xi 3. Define"': (P(M(k)), U, n) t (P(k), <,A, V). by K(8) = L Xi X;ES Then "' is a lattice isomorphism. Proof 1. Since the minimal projections yield a direct sum decomposition of C(2, k), for each x E C(2, k) we have 2. Add .Z::::x;es Xi to both sides of the expression in (1). 143
PAGE 150
3. That "'is bijective follows from Theorem 7.35. Now let S, T s; M(k), and define By theorem 7.13, This clearly yields showing that the partial orderings match. If then x= L Xi0x, X;EM(n) 1rs0x= LXi0x. X;ES Application of 1rT next yields 1rT 0 (7rs 0x) = L Xi 0x. x;eSnT This matches the meet operations of the lattices. To establish the same property for join operations, first notice that LXi+ LXi X;ES X;ET L Xi X;ES6.T The last equality holds since addition is performed modulo two. Now smce (S n T) = 0, 144
PAGE 151
we must have 1rs+1rT+1rs*1rT= L Xi X;ESUT The expression on the left is the join operation_in (P(k), <, AV). D Proposition 7.38 If l is odd, then M(l) n odd(l) = {1}. Proof First rng (1) has dimension one, and hence 1 E M(l). If 1r E M(l) n odd(l), then But this means that 1< 1r. D Not every subset of P(k) generates a direct sum decomposition of C(2, k); either part of C(2, k) may not be accounted for, or ranges of projections may overlap. We next identify the collections of projections that do generate decompositions. Definition 7.39 Let k,r E z+. 1. Let (Bj)iEr be a sequence of pairwise disjoint subsets of M(k). If M(k) = Ujer sj, then .(Sj)jEr is said to be a decomposition sequence for C(2, k). If, furthermore, for each j E r there is atE r such that then the sequence is said to be symmetric. 145
PAGE 152
2. Define D(k) = {(Sj)jEr I (Sj)jEr is a decomposition sequence for C(2, k)}. Clearly, M(k) is always a decomposition sequence. The next proposition shows that it is also symmetric. Proposition 7.40 Let k E z+ and X E M(k). Then X E M(k) .Proof Let X E 1\II(k). Clearly, X =I= .Q. Now if 1f< x, then ., 1f< X This is only possible if 1r E {.Q, x} and this is equivalent to wE {.Q, x}. o The sets of projections that yield direct sum decompositions of C(2, k) may now be characterized in terms of decomposition sequences. Theorem 7.41 Let k, r E z+ and let (Sj)jEr be a sequence of subsets of M(k). If for each j E r, 11"j E P(k) is defined by 11"j = L:xiES; Xi, then C(2, k) = E9 rng (1rj) (Sj)jEr E D(k). jEr Proof (:::::::}) Assume that (Sj )jEr is not a decomposition sequence. If the Sj do not cover C(2, k), then let Xi E M(k)\ U Sj, and x E rng (Xi) \{.Q}. jEr Since the members of M(k) are linearly independent, x fl. E9 rng (1rj). jEr 146
PAGE 153
If there are distinct j, t E r, and x E M(k) such that then ({::=) Assume that (S3)3Er is a decomposition sequence. Since we must then have Us3 = M(k), jEr L'lrJ =eo. jEr To complete the proof, it is only necessary to show that ranges of distinct projections have trivial intersections. This follows immediately from the linear independence of M(k) and the fact that the SJ are disjoint. D Given a direct sum decomposition of a vector space, we know from basic linear algebra that vector addition may always be performed termwise with respect to the summands. The remaining results of this section establish that aspects of multiplicative behavior may also be described within the context of direct sum decompositions. Theorem 7.42 rng (1r) is an ideal for each 1r. E P(k). Proof Let x E rng (1r) ,y E C(2, k), and show that 1r leaves X*Y fixed. Now 7r0(X*Y) 7f* (X*Y) (1f x) y (7r0X)*Y =X*Y D 147
PAGE 154
Proposition 7.43 If 1r E P(k), x E rng (1r), andy E rng (eo1r), then X* y = .Q. Proof By Theorem 7.42 Theorem 7.44 Let r E z+ and (Sj)jEr E D(k). If 1rj = l.:.::x;ES; Xi V j E r, then x y = L((1rj 0 x) (1rj 0 y)). jEr Proof By Theorem 7.37, if j0 E r, then eo+ 1rjo = 2:: 'Trj. jEr Nio Now, application of Proposition 7.43 to yields xy = 0x) 2:: L((1rj 0 x) *(1ft 0 v)) jEr tEt L((1rj 0 x) *(1rj 0 y)). D jEr This shows that convolution may be performed within summands of a di rect sum decomposition. The next theorem asserts that members of the range of a projection essentially operate on the range of the conjugate projection. Theorem 7.45 Let r E z+ and (Sj)jEr E D(k). If 1rj = 2.:.:: Xi E Sj V j E r then x 0 y = 2:)(1rj 0 x) 0 (1rj 0 y)). jEr 148
PAGE 155
Proof x0y X*Y L(1ft 0 x) *(1ft 0 y) tEr L (1ft 0 x) 0 (1ft 0 y) tEr L(1ft 0 x) 0 (1ft 0 y). D tEr ByProposition 7.15, 1f0X=X {::=:::> X E rng ( 7f) 2. By Proposition 6.36 If x, y E C(2, k) and z E C(2, 2k) such that 149
PAGE 156
then Since we may substitute
PAGE 157
the result holds for .Q. By the same argument, if we let t = #(rng (en,O7r)), then .Q must have t square roots in rng (k,2 (ek,o7r)). Also, C(2, k) must contain st elements and C(2, 2k) must contain (st)7 elements. Next, let x E rng (7r) and Xo = k,2(x). By Proposition 7.46, x 0 has st square roots. If then Furthermore, Thus, for each Yo E rng (2k,2(7r)) such that Y6 = xo, there are t choices for satisfying and only one of these yields a member of rng ( k,2 ( 7r)). Thus there are exactly st /t = s choices for Yo. 0 This theorem provides a means by which the structure of C(2, 2k) may be developed in terms of C(2, k). Thus if lis odd and the structure of C(2, l) is known, then given r > 0, an induction may be used to determine structure 151
PAGE 158
in C(2, l2r). In fact, this induction provides the key to the theory developed in the next chapter. 7.6 An Isomorphic Structure Several of the results presented in this chapter to spaces of odd dimension have previously been within the context of cyclic codes. Some of these results are briefly treated in this section. The reader is referred to Pless [76] for a rigorous development of this theory. We begin by defining the structure within which cyclic codes are studied,, and that it is isomorphic to +, *). The symbols "x" and "y" have been used to denote members of C(2, n), but, because the theory of cyclic codes is presented in terms of polynomial rings, the symbol "x" is used to denote an indeterminant, and members of C (2, l) are denoted by lower case letters from the beginning of the alphabet. These conventions are in effect for this section only. Let l be an odd integer, and consider the polynomial ring We wish to show that the function a tt L a( i)xi iEI yields an isomorphism from to (Z+2[x]/(x11). This function is clearly a bijection. Addition in (Z2[x]/(x1 1) is performed termwise, and it follows easily 152
PAGE 159
that iEl iEl iEl Multiplication in (;z+2[x]/(x1 1) is obtained by multiplying polynomials then dividing the product by x1 1 and taking the remainder. Since it is clear that x1 = 1 mod ( x1 1), we see that reduction modulo x1 1 may be obtained by evaluating exponents modulo l. Given a, bE C(2, l) and i E l, we have a* b(i) = L a(j)b(ij) jEl i l1 L a(j)b(ij) + L a(j)b(n + ij), j=O j=i+1 where ordinary integer arithmetic is used in the last equality. If we let L c(i)xi = (L. a(k)xk L b(j)xi) mod (x1 1), I iEl kEl jEl then, for each i E l we obtain i l1 c(i) = L a(j)b(ij) + L a(j)b(n + ij). j=O j=i+1 This establishes the isomorphism. A cyclic code in is simply a subspace that is invariant with respect to shifts. If 1r E P(l) and a E then a E rng ( 1f) {:::::::::> 1f 0 a = a. But 153
PAGE 160
:==:::? (e1 1r) 0 a= e18 a :==:::? 1r 0 (e1 0 a)= e1 0 a. This shows that the range of each member of P(l) yields a cyclic code. In the context of Z2[x]/(x1 1), it is an established fact that a subspace yields a cyclic code if and only if that subspace is a principle ideal that is generated by a divisor of x1 1. It is furthermore known that each such ideal contains an idempotent. This yields a bijection between P(l) and the set of subsets divisors of x1 1. If these ideals are partially ordered by set inclusion, then the minimal ideals are generated by the products whiCh consist of all but one divisor of x1 1, while within the context of C(2, l) these minimal ideals are ranges of members of M(l). If we write l II ...... l x 1 = f;(x), and!; = (x 1)/ J;, jEs where each fi is irreducible, then we may pair X E M(l) with fi, where Jj generates rng (x). In the above cited work, it is shown that the ideal generated by Jj is a field that is isomorphic to GF(2t) where tis the degree off;. Such an ideal clearly has dimension t. Since the minimal projections yield a direct sum decomposition of C(2, l), we have established the following theorem. Theorem 7.48 The minimal projections yield a decomposition of C(2, l) which consists of fields, with the dimensions of the terms in onetoone cor respondence with the degrees of the irreducible divisors of x1 1. Tables 7.2 and 7.3 identify the prime factorizations of x1 1 and the structure of the minimal decompositions of C(2, l) into fields for al values of l between 1 and 21. 154
PAGE 161
Table 7.2 Factorization of 1 + x1 1 + x1 I Factorization 1 +x1 (1 + x) 1 +x3 (1 + x)(1 + +x + x 2 ) 1 +x5 (1 + x )(1 + x + x 2 + x 3 + x4 ) 1 +x7 (1 + x) (1 + x + x 3 ) (1 + x 2 + x 3 ) 1 +x9 (1 + x)(1 + +x + x 2)(1 + x 3 + x 6 ) 1 +x11 (1 + x)(1 + x + + x10) 1 +x13 (1 + x)(1 + x + + x12) 1 +xls (1 + x)(1 + x + x2)(1 + x 2 + x 3 + x4 ) (1 + x + x4)(1 + x 3 + x4 ) 1 +x17 (1 + x)(1 + x + x 2 + x4 + x 6 + x 7 + x 8 ) (1 + x 3 + x4 + x 5 + x 8 ) 1 +x19 (1 + x)(1 + x + .. + x18) 1 +x21 (1 + x)(1 + x + x 2)(1 + x 2 + x 3)(1 + x + x 3 ) (1 + x 2 + x4 + x 5 + x6)(1 + x + x 2 + x4 + x 6 ) 155
PAGE 162
Table 7.3 Minimal Decomposition of C(2, l) I Dim I Decomposition 1 lF 21 3 lF 21 EBlF 22 5 lF 2 1 EBlF 2 4 7 lF 21 E9 lF 23 E9 lF 23 9 lF 21 E9 lF 22 E9 lF 26 11 lF 21 E9 lF 210 13 lF 21 E9 lF 212 15 lF 21 E9 lF 22 E9 lF 24 E9 lF 24 E9 lF 24 17 lF 21 E9 lF 28 E9 lF 28 19 lF 21 E9 lF 218 21 lF 21 E9 lF 22 E9 lF 23 E9 lF 23 E9 lF 26 E9 lF 26 156
PAGE 163
8. Structure of C(2, n) 8.1 Introduction State transition graphs for members of C(2, 2r) were studied in Chapter 5. In this chapter the techniques developed in Chapter 5 are generalized and applied to the study of spaces of other dimensions. Throughout this chapter, we assume that l, m, n E z+ and r E w such that l is odd, m = 2r and n = lm. We furthermore assume that k is an arbitrary member of z+. The theory developed in this chapter relies heavily on the fact that the ranges of members of M(l) are fields. This field structure provides a means by which the parity arguments used in Chapter 5. These parity arguments may, in turn, be used to show that the range of each minimal projection contains a tree whose level structure may be used in the classificatiqn of members of that space in much the same way that the tree associated with rule 60 was used in Chapter 5. The following changes in terminology are in effect for this chapter. If 1r E P(k), then, since 7f is the identity for rng (1r), we consider any x E rng ( 1r) to be invertible if it has an inverse with respect to 7f. Furthermore, if x E rng (1r), then x essentially operates on rng (1r) in the sense that x0z = .Q whenever z E rng ( e0 + 1f). We thus adopt the convention that ker (x) = {y E rng (1r) I x 0 y = .Q} .. 157
PAGE 164
Also, if rng (x) = rng (1f), then we say that x is surjective. If it is not explicitly stated that x is a member of the range of a projection, then the usual notions of invertibility, kernel, and surjectivity apply. 8.2 Establishment of a Reference In Chapter 5 theory pertaining to C(2, 2r) was expressed in terms of the level structure of the binary tree associated with 8_. While it was always possible to use 8_ to obtain a tree in Chapter 5, there is no single rule that can be used to generate all trees in the current context. However, if x E M(l), then there exists there exists a nilpotent x E rng (ci>1,m(X)) whose restriction to rng (z,m(X)) has a state transition graph that is a tree of height m and indegree equal to the order of rng (x). The structure of this tree is developed in this section. We must first show that the range of each projection is a ring. Proposition 8.1 Let k E z+' 7r E P(k), and X E rng (7r). Then: 1. 1r E rng (1r). 2. 7r *X= X. Proof 1. It suffices to show that 1r 07f = 1r. Now 'if. 158
PAGE 165
2. Simply notice that x is left fixed by 1r, and The following theorem has now been proved. Theo!em 8.2 If k E z+ and 1r E P(k). Then rng (1r) is a .ring. Definition 8.3 If k E z+' 7r E P(k), and X E rng (7r), then X is said to be 7r invertible if there exists t > 0 such that xt = 1f. If x is 1r invertible, then define ordrr(x) = min{t > 0 I xt = 1f}. ordrr(x) is said to be the 1r order of x. While "1r" occurs as a subscript in these definitions, it will generally be omitted. Proposition 8.4 Let k E z+, 7ro E P(k), and 1r1 E P(2k) such that 1r1 = n,2(xo), then X1 is 1f'1 invertible. Proof Lett= ordrr0(xa). Since
PAGE 166
Theorem 8.5 Let k E z+, 7ro E P(k), and 1r1 E P(2k) such that 1r1
PAGE 167
2. Let i be odd. Any square root of
PAGE 168
the existence of trees that are contained in the terms of the decomposition and possess properties similar to those of the tree associated with 8_. We begin by introducing notation for some of the required components of this construction. These definitions will remain in effect for the remainder of this chapter. Let l be odd, and select Xo E M(l). Given r > 0, we now define Xr = l,2r(Xo). For r E w, define Finally, define Dr = #(rng (Xr)). Clearly, for each r E w, Dr = Df. The next theorem shows that An,2r maps Wr onto its base. Theorem 8.8 Let r E w. Then An,2r(Wr) = Wo. Proof First let x E Wr and show that An,2r(x) E Wo. Since Wr is closed with respect to convolution, we .have Apply Theorem 8.6 to obtain Now notice that 162
PAGE 169
Proceed by induction to show that An,2r maps vVr onto vV0 The condition holds for r = 0, because An,1 is the identity. Let r > 0 and assume that the result has been established for r1. Let u E Wo and v E Wrl such that An,2r1 (v) = U. We may choose wE Wr such that This equality is equivalent to The result now follows from the transitivity of <1>. D Proof Let uo, u1 E z,2(vVo) and vo, v1 E Wz,2(W1). Then since #(z,2(Wo)) = #(Wz,2(Wo)) =Do, and #(rng (1r1)) = it suffices to show that Uo = v0 and u 1 = v1 whenever uo +u1 = Vo +v1 But this follows upon showing that u 1 = v 1 So assume that u0 + u 1 = vo + v 1 and let i E l. If i is odd, then, since uo, Vo E rng ( <1.> 1,2), uo(i) = vo(i) = 0. We must then have if i is even, then i + l is odd, and hence u1(i + l) = v1(i + l). 163
PAGE 170
u1(i + l) = u1(i), and v1(i + l) = v 1 (i). This shows that u1 = v1 0 Lemma 8.10 Let r > 0. If y E W1,2r(W0 ) such that y(i) = 0 for each odd i E 2l, then y = Q. Proof First assume that r = 1, and let y E W1 2(vV0). If y(i) = 0 for each odd i E 2l, then y E 1 ,2(W0). It follows immediately from Lemma 8.9 that Next assume that r > 1. Let z E W0 and i E 2rl. If i is odd, then so is i mod 2l. It follows by transitivity that \ll1,2r(z)(i) = Wz,2(z)(i mod 2l). By the first part of the proof, we know that the term on the right must be nonzero for some i. 0 For the remainder of this chapter we assume that the following definitions are in effect. For each r E w, we recursively define Xr E vVr as follows. Define Xo = Q. Next select X! E wl so that XI =f. Q and xi = Q. Finally, let r > 1, and select Xr. E Wr so that x; = z2r1,2(Xr1). Each Xr will be used to construct a tree in W r, and each Xr will determine a tree in Wr. These trees provide an analogue to the tree generated by rule 60. Proposition 8.11 Given r E w, x;r = Q. 164
PAGE 171
Proof Proceed by induction on r. First x0 = .Q by definition. Next, assume that = .Q. We then have .Q. D Proof Apply Theorem 8.6 D The next theorem shows that for each r E w, Xr generates a tree in Wr with indegree equal to #(W0). It is this result that provides for the generalization of techniques developed for the case l = 1. Theorem 8.13 Given r E w, ker (xr) = Wz,2r(Wo). Proof The theorem holds for s = 0, because x0 = .Qand W1 2o is the identity. Next let r > 1. (2) The induction step follows by Theorem 6.36 and the transitivity of w. Assume that such that Xr 0 y = .Q. To establish a contradiction, we proceed by induction on r. First, let r = 1. By Lemma 8.9, we may write y = u + v, where u E Wz,2(Wo), v E z,2(Wa). Since y tj. W 1 2 (W0), we must have 165
PAGE 172
Because It follows by linearity that Notice that 1, and assume that the theorem has been established for r1. Notice that y2 =/= .Q, because y 'liz2r1,2(Wr1). Now Xr 0 y = .Q implies Thus there exists y' E Wr_1 such that This implies Xr1 0 Y1 = .Q. By the induction hypothesis, we have Lemma 8.10 now implies that 3 i E l2r1 such that i is odd and y'(i) =/= 0. 166
PAGE 173
Since y' E W1,2r1(Wo),
PAGE 174
Definition 8.14 Let r E w and define Ar: Wr t w by >.r(Y) is said to be the r level of y. Furthermore, given t E 2r + 1, define lvl(Wr,t) is said to be basic levelt ofWr. Notice that both .>.r and lvl(Wr, t) are defined in terms of Xr, and, for r > 0, there are multiple choices for Xr. Thus the question remains as to whether or not the definitions are uniquely determined. This problem will be resolved in the next section. Proposition 8.15 Let r E w and t E 2r + 1. Then: 1. #(lvl(Wr, 0)) = 1. 2. #(lvl(Wr, t)) = (Dol)D61 Proof 1. Clearly, lvl(Wr, 0) = {.Q}. 2. Let t = 1. The result follows for this case because Next let 2 t 2r, and assume that 168
PAGE 175
Since #(ker (xr) =Do, each member of lvl(Wr, t 1) can have at most Do predecessors. This implie s To see that equality must hold for each t, first notice that zr 1 + L #(lvl(Wr, t)) =Dr= Dr. t=1 Thus zr Dr < 1 + L(Dot=1 zr 1 +(Do 1) t=1 1 +(Do1)/tDo1) Definition 8.16 Lett E 2r + 1 and define t K(vVr, t) = U lvl(Wr,j). j=O K(Wr, t) is said to be the tlevel kernelspace ofWr. Notice that the definition of K(Wr, t) is obtained by exchanging the roles of Xr and Xr Proposition 8.17 Given t E 2r + 1, 169
PAGE 176
Proof Apply Proposition 8.15 to obtain t #(K(Wr, t)) = 1 + L #(lvl(Wr,j)) j=l t 1 +(Do 1) :LD61 j=l 1 +(Do1)(D61)/(Do1) The next proposition asserts that the set of internal nodes of the tree associated with Xr equals the kernel of the A operator. This corresponds to the fact that the even parity nodes are the internal nodes of the tree for 8_. Proposition 8.18 Let r E w andy E Wr. Then Proof Define m = 2r and n = lm Given z E Wr, An,m(Xr 0 z) .Q 0 An,m(z) .Q. (2) Since #(ker(xr)) = Do,we must have #(rng (xr)) = Ds/ Do. Since An,m maps W r onto W o, it must map precisely Dr/ Do members of vVo to .Q. 0 170
PAGE 177
Corollary 8.19 If y E Wr, then An,m(Y) # .Q ::=} y E lvl(Wn2r). Proof Notice that rng (xr) = K(Wr, 2rI ). Corollary 8.20 If y E lvl(Wr, 2r), then y is invertible. Proof By Corollary 8.19, An,m(Y) # .Q, and hence, it is invertible. Since l,m is an embedding, Theorem 8.6 tells us that y2r is invertible. This, in turn, implies that y is invertible. 0 When l = 1, the odd parity rules preserve levels within the tree associated with 8_, and given a pair of configurations at the same level, there exists an invertible rule that maps one to the other. The next proposition generalizes these properties. Proposition 8.21 Let r E w and t E 2r + 1. Then: 1. Given x E lvl(Wr, 2r), 2. Given y, z E lvl(Wr t), there exists x E lvl(liVr, 2r) such that X* y = Z. Proof Define m = 2r and n = lm. 1. We proceed by induction on levels, beginning with level 2r. So let We then have An,m(x), An,m(Y) E Wo \{.Q}. 171
PAGE 178
Since W0 is a field, this implies and this is equivalent to X* y E lvl(W r, 2r). Next assume that the proposition holds fort> 0 and let y E lvl(Wr, t1). Then there exists Yo E lvl(Wr, t) such that Y = Xr 8 By the induction hypothesis, X* Yo E lvl(Wr, t), and hence, (xr) 8 (x *Yo) E lvl(Wr, t1). But, since convolution is commutative, Xr *X* Yo X* Xr *Yo x (xr 8 Yo) X* y. 2. We again use induction, starting at the top of the tree. Let y, Z E lvl(Wr, 2r). 172
PAGE 179
Define x = Z*y1 Clearly, z = X*Y Next assume that the holds for t > 0 and let y, z E lvl(Wr, t1). There exist y0 z0 E lvl(Wr, t) such that Xr 0 Yo = y and Xr 0 Zo = z. By the induction hypotheses there exists x E lvl(Wr, 2r) such that x *Yo= zo. Now, X y X* Xr 'Yo z. 0 Proposition 8.22 Let r E w, and t E 2r + 1. Then Proof First, proceed by induction on t to show that the proposition holds for Xr Lett= 0. Then Next, assume that the theorem holds for t < 2r, and consider xt+1 By applying the induction hypothesis we obtain Lett E 2r + 1 and x E 2r). By (1) of Proposition 8.21 173
PAGE 180
It follows immediately from (2) of the same proposition that This establishes the equality. D Proposition 8.23 Let r E w, t E 2r + 1, x E lvl(vVr, t), andy = x Then ker (y) = K(Wr, t). Proof If z E K(Wr, t), then xt0z=0 r x; z = .Q xt 0z = 0 r z E K(Wr, t). D Proposition 8.24 For each r > 0, x; = z2r1,2('Xr1) This follows immediately from the definitions of Xr, Xr and the fact that z2r1,2 preserves conjugation. D We next show that conjugation provides an isomorphism between opera tions on Wr by members of Wr and operations on Wr by members of Wr. Proposition 8.25 Let r E w, and y,z E Wr. Then Xr 0 Y = Z Xr 0 Y = Z. Proof By symmetry, it suffices to show that Xr 0 Y = Z ==} Xr 0 Y = Z. If Xr 0y = z, then Xr y = Z. 174
PAGE 181
Conjugating both sides now yields Xr 0y =X. 0 Corollary 8.26 If y E Wr, then y E lvl(vVr, t) t = rnin{j I 0 y = Q.}. 8.3 Conjugate Level Structures In the previous section it was shown Xr operates on Wr, while Xr operates on Wr. These rules are both nilpotent, and have graphs that are trees of height 2r and degree D0 Conjugation provides an isomorphism between these graphs, and, in particular, it matches members of corresponding levels. For the case l = 1 it was shown that operations by members of C(2, 2r) were well behaved with respect to the tree structure associated with 8_. In this section, variations on those techniques are used to describe the behavior of rules in terms of the level structures of these conjugate trees. Members of W r are distinguished by the presence of an over bar, with each y E W r corresponding toy E Wr. By each result presented in this section has an equivalent version expressed in terms of members of Wr operating on Wr. The next proposition shows that the invertible members of W r preserve the level structure of Wr. This corresponds to the fact that odd parity rules preserve the level structure for 8_, when the dimension is a power of two. Theorem 8.27 Let r E w, and t E 2r + 1. Let x E lvl(vVr, 2r), andy E lvl(Wr, t). Then x 0 y E lvl(vVr, t). 175
PAGE 182
Proof Notice that x0y = X*Y Now by Proposition 8 .21, X* y E lvl(Wr, t). 0 In Chapter 5, it was shown that the level of a rule in the tree for 8_ determines the order of its kernel. Proposition 8.23 serves to establish that property in the current context. It was also shown in Chapter 5 that when a rule acted on a configuration the configuration moved downward in the tree by the same number of levels as the rule resided below the top Theorem 8.21 established this property for the case where the rule was a leaf. The next theorem establishes this property for the remaining configurations. Theorem 8.28 Let j,t E w, with t > 0. Ifx E lvl(Wr,2rt), andy E lvl(Wr,j), then: 1. If t > j, then x 0 y = Q. 2. Ift :5 j, then x 0 y E lvl(Wr,jt). Proof First notice that we may write and 1. Assume t;::: r. Then and hence x 0 y = z 0 (x; 0 y). 2rt 1'":\ 0 Xr ...:.; Y = _, x0y = .Q. 176
PAGE 183
2. Assume t :::; j, Then x; 8 y E lvl(l!Vr,jt). By Theorem 8.21, we must have x 8 y E lvl(Wr,jt). D Corollary 8.29 lfx E lvl(Wr, 2rt), then xWftl = Q. Proof Given y E vVr, each application of x moves y t levels closer to Q, and there are only 2r levels. D Corollary 8.30 kerx = K(Wr, t). Corollary 8.31 #(kerx) = D&. We thus see that rules below level 2r are nilpotent, with the level of the rule determining the order of its kernel. We also see that if a rule resides t levels below the top, then each of its levels consists of a union oft consecutive levels with respect to Xr. The state transition graph for such a rule is thus a tree, and the structure of this tree is entirely determined by the indegree of its internal nodes. The indegree is, in turn, determined by the level of the rule in the tree associated with Xr. Corollary 8.31 characterizes lvl(Wr, 2rt) in terms of orders of kernels of rules. This establishes that the notations for levels introduced in definition 8.14 are independent of the choice of Xr 177
PAGE 184
8.4 Invertible Rules Given x E lVr, it has been shown that xis invertible exactly when and furthermore this occurs exactly when Since 1fr is both the identity in W r and the projection onto Wr, given x E lvl(Wr, 28 ) and y E Wr, there must be some c > 0 such that XC 0 y = y. In Chapter 5 it was shown that the cycle structure for an odd parity rule is directly obtainable from the level structure of its corule. The solution for the current generalizes this process. Definition 8.32 Let r E .z+, and define: 2. Ir = lflz,m(Wo). Notice that Nr consists of the members of W r that are mapped to Q by An,m, and has cardinality nr 1 Since we are assuming that W0 is a field, Ir is also a field, and like W0 Ir contains Do members. The next theorem allows us to split any member of Wr into nilpotent and invertible parts. Notice that we continue to assume that m = 2r, and n = lm. Theorem 8.33 Wr = Nr E9 Ir 178
PAGE 185
Proof W 0 is a vector space over Z2 Thus its cardinality is a power of two, say = 2a. Furthermore, since W0 is a field, its non zero members constitute a multiplicative cyclic group of order 2a 1. By isomorphism, the same conditions hold for Ir. Since #(Ir)#(Nr) = D0 it suffices to show that given z E VVr, there exists zo E Nr and z1 E lr such that z = zo + z1 Let z E Wr. We first determine z1 Define Clearly, y E Ir. If y = .Q, then z is nilpotent and we may let z1 = .Q. Other wise, y is invertible. Also ord(y) is odd, because 2a 1 is odd. Furthermore, y has a unique square root in Ir In fact, it is yielded by yrord(Y)/21). After repeating this process r times we arrive at the unique m th root ofy in Ir We select this root for z1 In order that z = z0+z1 we must have z0 = z+z1 To complete the proof, we need only show that z0 is nilpotent. First, if z1 = .Q, then z0 = z, which is nilpotent. So assume that z1 "/:.Q. Now, y+y .Q. 0 Our goal now is to show that for each z E lvl(Wr, 2r), its cycle structure is easily determined via this decomposition. The next lemma shows that when two configurations which reside at different levels are added, their sum resides at the maximum of their levels. Lemma 8.34 Let s, t E 2r + 1 such that s < t. Let y E lvl(Wr, s) and z E lvl(vVr, t). Then y + z E lvl(Wr, t). 179
PAGE 186
Proof First, let t = 2r. 'Then By linearity, and this implies Next let t < 2r, and define j = 2r t. We may choose z0 E lvl(Wr, 2r) and Yo E lvl(Wr, s + j) such that 8 z0 = z and 8 Yo = y. By the first part of the proof, Then 8 (Yo+ zo) E lvl(Wr, t). But, by linearity, We next expand Definition 3.40 so that it applies to members of Wr restricted to W r. Definition 8.35 Let z E lvl(Wr, 2r) andy E Wr. Define pz(y) = min {J > o 1 zj 0 y = y}. pz(y) is said to be the z period of y. 180
PAGE 187
Definition 8.36 Let z E K(Wr, 2r) andy E Wr. Define f.liz(Y) = min{j > 0 I xi 0 y = Q}. rz(y) is said to be the _z level of y. In Chapter 5, it was shown that the cycle structure of an invertible rule was obtainable from the level structure of its corule. The next theorem shows that a generalization of this procedure may be applied termwise in field based decompositions. Theorem 8.37 Let z E lvl(Wr, 2r), zo E Nr and z1 E Ir such that z = zo + z1. Let c = ord(z1), and 2i = f J.Lz0(y)h. Let yEWs\ {Q}. Then Pz(Y) = c2i. Proof First show that :zc2i 0 y = y. If i < c, then Thus c1 ( ) c2i + L C (d2i (ci)2i) 0 zl zl zo y. i=O (ci)V 0 O zo yzc2i 0 Y x;; 0y y. 181
PAGE 188
If c2j is not the minimal period for y, then the minimal period must divide c2j. If d < j, then by the same argument as above, But in order that zf2 ; = 1f8 it is necessary that c I d2j, and this is impossible, because d < c, and (c, 2j) = 1. Thus, if the period is strictly smaller than c2j, it must be of the form d2r where d I c, and r < j. The strategy here is to use Lemma 8.34 to show that when (zr + zr)d 8 y is expanded, the sum consisting of all but the leading term must reside at a level strictly between 0 and the level of y. This is then shown to be impossible if zd2r is to leave y fixed. Ford and r as above, If 0 i d2, then 0 ( +)d2r Zo Zl ..:.; y ((zl + zo)2r)d 8y (zr + z6r)d 0 y < J.Lzo ( 8 y) < (((dl)r 2r) ) J.Lzo Z1 Zo 8 Y < J.Lzo (y) Application of Lemma 8.34 yields 0
PAGE 189
If c = d, then While, if d < c then In either case, we have a contradiction. 0 This shows that for z as above, the structure of its state transition graph is obtained from the tree structure for the graph of z0 and the order of the cycle generated by z1 Since W r is a field, the order of such a cycle must divide Do 1, and, for c I D0 1, the number of generators for cycles of order cis (c). Where ""is the Eulerphi function. 8.5 Product Graphs In Chapter 3 it was shown that, for any x E C(2, n), the space C(2, n) decomposes into a direct sum of atr(x) and nil(x). We next characterize these subspaces in terms of the canonical direct sum decomposition of C (2, n). Define Dn = #(M(n)). Since M(n) possesses a natural ordering, its members may be written with subscripts indicating their position in this ordering. Thus, given i E Dn, Xi E M(n). Also, given i En, we define ?: = j, where Xi= Xi This provides a means to designate conjugates of projections in terms of their subscripts. 183
PAGE 190
Definition 8.38 Let x E C(2, n) and define: 1. Ax= {i E Dn I An,m(Xi(x)) f. .Q}. 2. Ex = {i E Dn I An,m(Xi(x)) = .Q}. Clearly, Ax identifies the components of x which are invertible, and Ex identifies the nilpotent components. Theorem 8.39 If x E C(2, n), then: 1. atr(x) = EBieA., rng (Xi) 2. nil(x) = EBieB., rng (Xi). Proof 1. (2) Clearly, if i E Ax, then rng (x:r) atr(x). The result now follows because atr(x) is closed under addition. If y E atr(x)\ EBieA,; rng (xr), then there is an i E Ex such that Xi 0 y f. 0. Let Xi = Xi 0 x and Yi = Xi 0 y. Then given t > 0, and hence, y cannot be periodic with respect to x. 2. (2) As in (1), if i E Ex,' then rng (xr) nil(x). 184
PAGE 191
and the result follows by the closure of addition. If y E nil(x)\ EBiEB., rng (xr), then there is an i E Ax such that Xi 0 y =/:0. Let Then y cannot be mapped to .Q under iteration by x. Let x, y E C(2, n). Given i E Ax define Given t > 0, in order that x't 0 y' = y' it is both necessary and sufficient that Ci It for each i E Ax. Thus the x'period of y' is equal to D. For each i, there are ci nodes on the orbit of Yi with respect to Xi This yields a total of niEA., Ci ways of selecting one node from each orbit. This collection of orbits thus yields niEA, Ci/ D cycles of period D. The problem of actually counting cycles is very difficult, because. there may be many different finite sequences of integers that have the same least common multiple. We next consider the problem of determining the structure of transient trees. Let x, y E C(2, n). Given i E Bx define 185
PAGE 192
4. hi= min{t > 0 J 0 Yi = .Q} and H = max{hi}iEBx. We clearly have x'H 0 y' = .Q. and a full H iterations are required to map y' to .Q. In order that y' be internal, it is necessary and sufficient that each Yr be internal. Thus the number of internal nodes in the tree associated with the operation of x' on y' must equal the product of the number of internal nodes in each term. If each Yr is internal, then the in degree at y' is yielded by TiiEBx bi' 186
PAGE 193
9. Conclusions 9.1 Summary Theory pertaining to linear global maps on was developed in this thesis. A class of algebraic structures called circulant spaces were defined, and it was shown that the theory of linear rules could be studied within this context. By working in circulant spaces it was possible to equate a state space with the set of linear rules that operate on it. This approach provided a means by which novel graph theoretic methods could be applied to the study of linear rules. In spaces of dimension 2m, rule 60 was used as a reference point from which state transition graphs for all members of C(2, 2m) could be classified. The graph for rule 60 was shown to be a binary tree, and it was established that the structure of the state transition graph of any even parity rule is known once the level of that rule in the tree associated with rule 60 is known. It was furthermore established that the structure of an odd parity rule may obtained by adding the identity rule to it and then determining the level of the resulting even parity rule. These results were then used to obtain efficient methods for determining the structure of state transition graphs for individual members of C(2, 2m). Next the problem of applying these techniques to spaces of other dimen sions was addressed. Theory pertaining to the operation of squaring linear rules was developed, and applied to the study of idempotent rules. For each n E z+, it was shown that idempotents could be used to obtain direct sum 187
PAGE 194
decompositions of C(2, n). The idempotents in any space possess a natural partial ordering, and it was established that the minimal members of this poset yield a particularly well structured decomposition. If we write n = 2rz, where l is odd, then there is a natural isomorphism between the idempotent members of C(2, l) and the idempotents in C(2, n). Since ranges of minimal idempotents in C (2, l) are fields, a great deal of theory has already been de veloped concerning them. The isomorphism between spaces of idempotents in C(2, l) and C(2, n) then provided a means to study idempotents on spaces of arbitrary dimension. 9.2 Related Problems There are several other problems suggested by this thesis, with most of them involving generalizations to other contexts. These generalizations involve either consideration of other state alphabets or array dimensions. Since two is prime, the problem of determining the structure of state transition graphs for members of C(p,pm) is a natural generalization of the same problem for C(2, 2m). While it was not presented in this thesis, this problem has been solved, and the solution is indeed a generalization of that for C(2, 2m). The nextlevel of generalization beyond this concerns the clas sification of state transition graphs for members of C(p, n). This problem appears to be very difficult because the theory of the squaring operation is much more difficult in this case than it is for members of C(2, n). This in turn leads to difficulties in studying projections and direct sum decompositions. A wider generalization is provided by spaces whose state alphabets are finite fields of nonprime order. Spaces whose dimensions are powers of either 188
PAGE 195
the orders or the characteristics of these fields may prove amenable to study, while the study of spaces of arbitrary dimension appears to be extremely difficult The second class of generalizations involves spaces whose array dimen sions are greater than one. For example, the operations of convolution and circulant multiplication extend naturally to As with onedimensional arrays, the case n = 2m may prove to be especially simple. Spaces with array dimension larger than two could also be studied, and other fields or rings could be used as state alphabets. Infinite lattices of various dimensions could also be used. In this case there must be some restriction as to the configurations that would be allowed to act as rules, because convolution and circulant multiplication are not defined when both terms have infinite support. Discret e measures could be defined on state alphabets, and these measures could, in turn, be used to generate product measures on state spaces. Measure preserving properties of rules could then be studied. In Chapter 7 circulant space theory was shown to be related to coding theory. Linear, binary codes are subs paces of Z2, and cyclic binary codes are linear binary codes that are additionally closed with respect to the shift opeation. It appears that there are many mathematical problems that fall within the realms of linear cellular automata and coding theory. 189
PAGE 196
References [1] 0. Martin, A. Odlyzko, and S. Wolfram, "Algebraic Properties of Cel lular Automata", Communications in Mathematical Physics, 93 (1984) 219258. [2] S. Wolfram, "Universality and Complexity in Cellular Automata", Phys ica D, 10, (1984) 135. [3] N.Packard and S wolfram, "TwoDimensional Cellular Automata", Journal of Statistical Physics, 38 Nos 5/6 (1985) [4] S.Wolfram, "Twenty Problems in the Theory of Cellular Automata", Physica Scripta, T9 (1985) 170183. (5] S. wolfram, "Computation Theory in Cellular Automata", Communi cations in 1\!Iathematical Physics, 96 (1984) 1517. [6] S. Wolfram, "Random Sequence Generation by Cellular Automata", Advances in Applied 1\!Iathematics, 7 (1986) 123169. [7] B. Voorhees, "Nearest Neighbor Cellular Automata over Z2 with Peri odic Boubdry Conditions", Physica D, 45 (1990) 2635. [8] E. Jen, "Aperiodicity in OneDimensional Cellular Automat_a", Physica D, 45 (1990) 318. [9] R. Fisch, "Cyclic Cellular Automata and Related Processes", Physica D, 45 .(1990) 1925. 190
PAGE 197
[10] S. Takahashi, "Cellular Automata and Multifractals: Dimension Spectra of Linear Cellular Automata", Physica D, 45 (1990) 3648. [11] A. Barbe, "A Cellular Automaton Ruled by an Eccentric Conservation Law", Physica D 45 (1990) 4962. [12] W. Li, N. H. Packard, and C. G. Langton, "Transition Phenomana in Cellular Automata Rule Space", Physica D, 45 (1990) 7794. [13] W. K. Wooters and C, G. Langton "Is There a Phase Transition for Deterministic Cellular Automata?", Physica D, 45 (1990) 95104. [14] H. Chate and P. Manville, "Criticallity in Cellular Automata", Physica D, 45 (1990) 122135. [15] H. Gutowitz, "A Heierarchical Classification of Cellular Automata", Physica D, 45 (1990) 136156. [16] F. C. Richards, "Extracting Cellular Automata Rules From Experiman tal Data", Physica D, 45 (1990) 180202. [17] E. Fredkin, "Digital Mechanics", Physica D, 45 (1990) 254270. [18] 0. Martin, "Critical Dynamics of OneDimensional Irreversible Sys tems", Physica D, 45 (1990) 345354. [19] T. Taffoli and H. Margolis, "Invertible Cellular Automata: A Review", Physica D, 45 (1990) 229253. [20] J. Kari, "Reversibility of 2D Cellular Automata is Undecidable", Physica D, 45 (1990) 379385. 191
PAGE 198
[21] K. Culik and L. P. Hurd, "Computation Theoretic Aspects of Cellular Automata" Physica D, 45 (1990) 357378 . [22] K Sutner "Classifying Circular Cellular Automata Physica D, 45 (1990) 386395. [23] K. Kulik and L. P. Hurd, "Formal Languages and Cellular Automaton Behavior", Physica D, 45 (1990) 396403. [24] M.Garzon, "Cellular Automata and Discrete Neural Networks", Physica D, 45 (1990) 431440. [25] E. Jen, "Scaling of Preimages in Cellular Automata", Complex Systems, 1 (1987) 10451062. [26] E. Jen, "Enumerations of Preimages in Cellular Automata", Complex Systems 3 (1989) 421.:...456. [27] P. Guan andY. He, "Exact Results for Deterministic Cellular Automata with Additive Rules", Journal of Statistical Physics, 43 (1986) 463478. [28] B. Voorhees, "Division Algorithm for Cellular Automata Rules", Com plex Systems, 4 (1990) 587597. [29) B. Voorhees "Predecessor States for Certain Cellular Automata Evolu tions", Communications in Mathematical Physics, 117 (1988) 431439. [30] B. Voorhees, "A Note on Injectivity of Additive Cellular Automata", Complex Systems, 8 (1994) 151159. [31) B. Voorhees, "Predecessors of Cellular Automata States I,, Physica D, 68 (1993) 283292. 192
PAGE 199
[32] B. Voorhees, "Predecessors of Cellular Automata States II", Physica D, 73 (1994) 136151. [33] B. "Predecessors of Cellular Automata States III" Physica D, 73 (1994) 152'167. [34] H. Ito, "Intriguing Properties of Global Structure in Some Classes of Finite Cellular Automata", Physica D, 31 (1988) 318338. [35] M. DuboisViolette and Alain Rouet, "A Mathimatical Classification of the OneDimensional Deterministic Cellular Automata", Communica tions in Mathematical Physics, 112 (1987) 627631. [36] T. Head, "OneDimensional Cellular Automata: Injectivity From Un ambiguity", Complex Systems, 3 (1989) 343348. [37] N. Pitsianis, G L. Bleris, Ph. Tsalides, A. Thanailakis, H. C Card, "Algebraic Theory of Boundes OneDimensional Cellular Automata", Complex Systems, 3 (1989) 209227. [38] A. D. Robinson, "Fast Computation of Additive Cellular Automata", Complex Systems, 1 (1987) 211216. [39) B. Sheth, P. Nag, R. W. Hellearth, "Binary Addition on Cellular Au tomata", Complex Systems, 5 (1991) 479486. [40] E. Fachini, L. Vassallo, "Cellular Automata with Regular Behavior", Complex Systems, 4 (1990) 385399. [41] A. Ilanchinski, P Halpern, "Structurally Dynamic Cellular Automata", Complex Systems, 1 (1987) 503527. 193
PAGE 200
[42] R. Bartlett, M. Garzon, "Distribution of Linear Rules in Cellular Automata Rule Space", Complex Systems, 6 (1992) 519532. [43] R. Bartlett, M Garzon, "Monomial Cellular Automata", Complex Sys tems, 7 (1994) 367388. [44] J. Pederson, "Cellular Automata as Algebraic Systems", Complex Sys tems, 6 (1992) 237250. [45] P. Halpern, G Caltagirone, "Behavior of Topological Cellular Au tomata", Complex Systems, 4 (1990) 623651. [46] K. Culik, S. Dube, "Fractal and Recurrent Behavior of Cellular Au. tomata", Complex Systems, 3 (1989) 253267. [47] K. Sutner, "On 0'Automata", Complex Systems, 2 (1998) 128. [48] K. Sutner, "De Bruijn Graphs and Linear Cellular Automata", Complex Systems, 5 (1991) 1930. [49] K. Sutner, "Additive Automata on Graphs", Complex Systems, 2 (1988) 649661. [50] P. Binder, C. Twining, D. Sherrington, "PhaseSpace Study of Bistable Cellular Automata", Complex Systems, 5 (1991) 127137. [51] P. Binder, "A Phase Diagram of Elementary Cellular Automata", Com plex Systems, 7 (1993) 241247. [52] K. Lindgren, "Correlations and Random Information in Cellular Au tomata", Complex Systems, 1 (1987) 529543. 194
PAGE 201
[53] K. Lindgren, M. G. Nordahl, "Universal Computation in Simple One Dimensional Cellular Automata", Complex Systems, 4 (1990) 299318. [54] K. Lindgren, M. G. Nordahl "Complexity Measures and Cellular Au tomata", Complex Systems, 2 (1988) 409440. [55] M. Biafore, "Universal Computation in FewBody Automata" Complex Systems, 7 (1993) 221239. [56] L. P. Hurd, "Recursive Cellular Automata Invariant Sets", Complex Systems, 4 (1990) 119129. [57] L. P. Hurd, _"Nonrecursive Cellular Automata Invariant Sets", Complex Systems, (1994) . [58] M. G. Nordahl, "Formal Languages and Finite Cellular Automata", Complex Systems, 3 (1989) 6378 [59] B. Schonfisch, "Propagation of Fronts in Cellular Automata", Physica D, 80 (1995) 435450. [60] B. Sheth, P. Nag, R. W. Hellwarth, "Driver Mechanisms in Cellular Automata", Complex Systems, 5 (1991) 487496. [61] C. Bays, "lassification of Semitotalistic Cellular Automata in Three Di mensions", Complex Systems, 2 (1988) 235254. [62] C. Langton, "Virtual State Machines in Cellular Automata", Complex Systems, 1 (1987) 257271. [63] L Levine, "Regular Language Invariance under OneDimensional Cel lular Automata Rules", Complex Systems, 6 (1992) 163178. 195
PAGE 202
[64] K. Culik, S.Yu, "Undecidability of CA Classification Schemes", Complex Systems, 2 (1988) 177190. [65] J. Milnor, "On the Entropy Geometry of Cellular Automata", Complex Systems, 2 (1988) 357386. [66] D. Hillman, "The Structure of OneDimensional Cellular Automata", Physica D, 52 (1991) 277292. [67] T. Rogers, C. Want, "Emulation and Subshifts of Finite Type in Cellular Automata", Physica D, 70 (1994) 396414. [68] M. Biafore, "Cellular Automata for NanometerScale Computation", Physica D, 70 (1994) 415435. [69] J. Urias, "Arithmetic Representations of Cellular Automata", Physica D, 68 (1993) 437446. [70] J. von Neumann, ed A. Burks 1966, Theory of SelfReproducing Automata, (University of Illinois, Urbana). [71] E. F. Codd, 1968, Cellular Automata, (Acedemic, New York). [72] A. Burks 1970, Essays on Cellular Automata, (University of Illinois, Urbana). [73] S. Lang, 1971, Algebra, (Columbia University, New York). [74] D. G. Hoffman, D. A. Leonard, C. C. Lindner, K. T. Phelps, C. A. Rodger, J. R. Wall, 1991, Coding Theory The Essentials, (Marcel Dekker, New York) 196
PAGE 203
[75] A. Wuensch, M. Lesser, 1992, Tbe Global Dynamics of Cellular Automata, (AddisonWesley, Reading, MA). [76] V. Pless, 1989, Introduction to tbe Tbeory of ErrorCorrecting Codes, (Wiley, New York). 197
PAGE 204
REFERENCES [1] Michael Albertson, Bela Bollobas, and Susan Tucker. Independence ratio and maximum degree of a graph. Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, XVII:4350, 1976. [2) R. L. Brooks. On coloring the nodes of a network. Proceedings of the Cambridge Philosophical Society, 37:194197, 1941. [3) Simeon Fajtlowicz. The independence ratio for cubic graphs. Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, XIX:273277, 1977. [4] Simeon Fajtlowicz. On the size of independence in graphs. Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, XXI:269274, 1978. [5] Simeon Fajtlowicz. Independence, clique size and maximum degree. Com binatorica, 4(1):3538, 1984. [6] Kathryn Fraughnaugh. PhD thesis University of Houston, 1982. [7) Kathryn L. Fraughnaugh and Stephen Locke. 11/30 finding large indepen dent sets in connected trianglefree 3regular graphs. Journal of Combina torial Theory, 65(no. 1):5172, 1995. [8] Kathryn L. Fraughnaugh and Stephen Locke. Finding independent sets in trianglefree graphs. SIAM Journal Discrete Math, 9(no. 4):674681, 1996. [9] Kathryn L. Fraughnaugh and Stephen Locke. Lower bounds on size and independence in K4free graphs. Journal of Graph Theory, 26(no. 2):6171, 1997. [10) R. E. Greenwood and A. M. Gleason. Combinatorial relations and chro matic graphs. Canadian Journal of Math, 7:17, 1955. [11] Jerrold Griggs and Owen Murphy. Edge density and independence ratio in trianglefree graphs with minimum degree three Discrete Math, 152(no. 13):157170, 1996. 195
PAGE 205
[12] Christopher Carl .Heckman and Robin Thomas. A new proof of the in dependence ratio of trianglefree cubic graphs. Discrete Math, 233(no. 13):233237, 2001. [13] Kathryn Fraughnaugh Jones. Minimum independence graphs with maxi mum degree four. Graphs and Applications, pages 221230, 1982. [14] Kathryn Fraughnaugh Jones. Independence in graphs with maximum de gree four. Journal of Combinatorial Theory Series B, 37(no. 3):254269, 1984. [15] Kathryn Fraughnaugh Jones. Size and independence in trianglefree graphs with maximum degree three. Journal of Graph Theory, 14(no. 5):525535, 1990. [16] Stephen Locke and Feng Lou. Finding independent sets in K4free 4regular connected graphs. Journal of Combinatorial Theory Series B, 71(no. 1), 1997. [17] Brendan D. MacKay and Stanislaw P. Radziszowski. R( 4, 5) = 25. Journal of Graph Theory, 19(3):309322, 1995. [18] Stanislaw P. Radziszowski. Small ramsey numbers. Electrinoc Journal of Combinatorics, www.combinatorics.org, 2006. [19] Stanislaw P. Radziszowski and Donald L. Kreher. Minimum trianglefree graphs. Ars Combinatoria, 31:8592, 1991. [20] Peter Sandberg. PhD thesis, University of South Carolina, 1998. [21] William Staton. PhD thesis, University of Houston, 1977. [22] William Staton. Some ramseytype numbers and the independence ratio. Transactions of the American Mathematical Society, 256:353370, 1979. [23] Douglas B. West. Introduction to Graph Theory. Prentice Hall, 1996. 196
