.PH ""
.nr Pt 1
.EQ
delim $$
gsize 12
define aA % {x sub i} %
define bB % {x sub j} %
define cC % {S sub i} %
define dD % {J sub i} %
define eE % {DELTA sub i} %
define fF % {d sub i} %
.EN
.am DE
.ls 2
.sp
..
.ds HP 12 12 12 12 12 12 12
.ds HF 3 3 3 3 3 3 3
.ls 1
.ce 99
.S 12
.B
Decreasing energy functions for some
cellular automata
.R
.sp
.I
E. Goles$"" sup *$
.R
.sp .2
Department of Mathematics
Engineering School
University of Chile
Casilla 170/3, Correo 3
Santiago, Chile
.sp
.I
A. M. Odlyzko
.R
.sp .2
AT&T Bell Laboratories
Murray Hill, NJ 07974
USA
.ce 0
.FS *)
Supported partially by AT&T Bell Laboratories and
Fondo Nacional de Ciencias de Chile 86-87, Santiago, Chile.
.FE
.sp 1.5
.ce
.B
ABSTRACT
.R
.sp
.P
.ls 2
The work of Ghiglia, Mastin, and Romero on a ``phase-unwrapping''
algorithm gives rise to the following operation: for any undirected
graph with arbitrary integer values attached to the vertices,
simultaneous updates are performed on these values, with the
value of a vertex being changed by one in the direction of the average
of the values of the adjacent vertices.
(When the average equals the value of a vertex, the value of the
vertex is incremented by one, unless all the neighbors have the
same value, in which case no change is made.)
Earlier work of Odlyzko and Randall showed that iterating this operation
always leads to a cycle of length one or two, but does not give a
bound on how many iterations might be needed to reach such a cycle.
This paper introduces a new ``energy function'' which does yield a
bound for the transient.
A novel feature of this energy is that it contains not only linear
and bilinear terms, as is common, but also terms involving the
minimum function.
.bp
.ls 1
.ce 99
.S 12
.B
Decreasing energy functions for some
cellular automata
.R
.sp
.I
E. Goles$"" sup *$
.R
.sp .2
Department of Mathematics
Engineering School
University of Chile
Casilla 170/3, Correo 3
Santiago, Chile
.sp
.I
A. M. Odlyzko
.R
.sp .2
AT&T Bell Laboratories
Murray Hill, NJ 07974
USA
.ce 0
.FS *)
Supported partially by AT&T Bell Laboratories and
Fondo Nacional de Ciencias de Chile 86-87, Santiago, Chile.
.FE
.sp
.H 1 "Introduction"
.ls 2
.P
Let $G$ be an undirected graph with vertices labelled $1 ^,...,^ n$, and
suppose that for each $i$, an integer $aA ^(0)$ is assigned at time 0
to vertex $i$.
A series of synchronous updates is performed on these values with the
rule that if $aA ^(t)$ is the value of vertex $i$ at time $t$, then
.DS 3
.EQ (1.1)
aA ^(t+1) ~=~ left {
matrix {
lcol {aA ^(t) ^-^ 1 above aA ^(t) above aA ^(t) ^+^ 1}
lcol {roman if ~cC ^(t) ~<~ 0, above roman if ~bB ^(t) ~=~ aA ^(t) ~{roman {for~all}} ~j ~member~ dD , above roman otherwise ,}
}
.EN
.DE
where
.pn 2
.PH "''- \\\\nP -''"
.DS 3
.EQ (1.2)
cC ^(t) ~mark =~ sum from {j ^member^ dD} ~bB ^(t) ~-~ fF ^aA ^(t) ^,
.EN
.sp
.EQ
dD ~lineup =~ "{" j: ~{roman vertex} ~j~ {roman {is~connected~"to"~vertex}} ~i "}" ^,
.EN
.sp
.EQ
fF ~lineup =~ | dD | ~=~ {roman {"degree"~of~vertex}} ~i ~.
.EN
.DE
This transformation was defined by Ghiglia, Mastin, and Romero [1]
for certain graphs that arose in their work on ``phase unwrapping'' (determination
of the phase of an analytic function from a set of values of the function
at a discrete grid).
Since the maximal value assigned to any of the vertices never increases,
and the minimal value never decreases, it is clear that iterating
the transformation leads to a configuration that repeats periodically.
Ghiglia et al. observed that for their graphs, the transformation always
ended up in a cycle of length 1 or 2.
Their algorithm was in fact designed on the assumption that the cycle
length is at most 2.
Later, Brickell and Purtill (unpublished) defined the transformation
for general graphs and conjectured that the period was always at most 2.
This conjecture was proved in [6], by utilizing an ``energy function''
derived from that used in [4].
However, the proof of [6] did not provide an upper bound for the transient
(the number of steps until the transformation enters a cycle), since
the energy function used there was not strictly decreasing.
.P
In this note we obtain an upper bound for the transient (Theorem 2 in Section 2).
The most interesting aspect of this bound is the method used.
The first results about periods of certain kinds of discrete iterations
having to be 1 or 2 were obtained in [5] by rather cumbersome combinatorial
methods.
Other methods were developed later [2,3,4,7,8,9,10].
The methods in [4] relied on an ``energy function;'' i.e., a function
associated to a configuration that could be shown to be bounded, yet
was strictly decreasing at each iteration not in the cycle.
The proof in [6] that the Ghiglia et al. iteration has period 1 or 2
relied on the use of the following energy function, adopted from those
used in [4]:
.DS 3
.EQ (1.3)
E sub 0 ^(t) ~=~ -~ sum from {i,j ^=^ 1} to n ~a sub ij ^aA ^(t) ~bB ^(t-1) ^,
.EN
.DE
where
.DS 3
.EQ (1.4)
a sub ij ~=~ left {
matrix {
lcol {1 above -^ fF above 0}
lcol {roman if ~i ~!=~ j ~roman but ~j ~member~ dD ^, above roman if ~i ~=~ j^, above roman if ~i ~!=~ j ~roman and ~j ~nomem~ dD ~.}
}
.EN
.DE
This energy function had the property that $E sub 0 ^(t+1) ~<=~ E sub 0 ^(t)$
for all $t$, but unlike the energy function of [4], equality
sometimes holds for $t$ not in the cycle, so that no upper bound for
the transient could be obtained from it.
On the other hand, this energy function involves only bilinear terms.
.P
The energy function we will use here is quite different, and is
given by
.DS 3
.EQ
E(t) ~mark =~ alpha ^E sub 0 ^(t) ~-~ 2^ sum from i=1 to n ~ min ( aA ^(t) ,
~aA ^(t-1))
.EN
.sp
.EQ (1.5)
~lineup -~ 2^ sum from i=1 to n ~sum from {j ^member^ dD} ~ min ( aA ^(t) ,
~bB ^(t-1))
.EN
.sp
.EQ
~lineup +~ sum from i=1 to n ~( aA ^(t) ~+~ aA ^(t-1)) ^,
.EN
.DE
where
.DS 3
.EQ (1.6)
alpha ~=~ 2 ~max from i ~d sub i ^+^ 4 ^.
.EN
.DE
The novelty of our method is that we use the minimum function in
the definition of (1.5), and that the terms with the minima in them appear
to be essential.
They allow us to show that $E(t+1) ~<=~ E(t) ^-^ 1$ for all $t$ not
in the cycle (Theorem 1), and this then leads to the upper bound
of Theorem 2 for the length of the transient.
(As we mention in Section 3, this upper bound is probably not best possible.)
.P
It is possible to bypass the use of the minimum function in (1.5).
The function $E(t)$ of (1.5) was derived by studying an encoding
(due to the first author and mentioned briefly in [6]) of the
iteration (1.1) into a transformation of a graph with only 0 and
1 values, for which the methods of [4], for example, could be applied.
However, the new graph is very large, and its size actually depends
on the initial assignment of $x sub 1 ^(0) ^,...,^ x sub n ^(0)$.
Thus this encoding does not show what is happening very clearly, and
the bound for the length of the transient it gives is weaker than
that of Theorem 2.
.H 1 "Main Results"
In this section we prove our main results, theorems 1 and 2.
.sp
.I
Theorem 1.
For the transformation defined by (1.1) and the energy function (1.5),
one has
.DS 3
.EQ
E(t+1) ~<=~ E(t) ^-^ 1 ~~for~any~~ t ~>=~ 1
.EN
.DE
unless $aA ^(t+1) ~=~ aA ^(t-1)$ for all $i$.
.R
.sp
\f2Proof\f1.
Because of the symmetry $a sub ij ~=~ a sub ji$, a quick calculation
shows that
.DS 3
.EQ (2.1)
DELTA ^E (t) ~: =~ E(t+1) ~-~ E(t) ~=~ sum from i=1 to n ~eE ^(t) ^,
.EN
.DE
where
.DS 3
.EQ
eE ^(t) ~=~ mark -~ alpha ( aA ^(t+1) ~-~ aA ^(t-1)) ~cC ^(t)
.EN
.sp
.EQ (2.2)
lineup +~ 2 ~ min ( aA ^(t) , ~aA ^(t-1)) ~-~ 2~ min ( aA ^(t+1) , ~aA ^(t))
.EN
.sp
.EQ
lineup +~ 2~ sum from {j ^member^ dD} ~ "{" min ( bB ^(t) , ~aA ^(t-1))
~-~ min ( bB ^(t) , ~aA ^(t+1)) "}"
.EN
.sp
.EQ
lineup +~ aA ^(t+1) ~-~ aA ^(t-1) ^,
.EN
.DE
with $cC ^(t)$ defined by (1.2).
What we will now show is that $eE ^(t) ~<=~ 0$ for all $i$ and $t$, and
that $eE ^(t) ~<=~ -^1$ for at least one $i$ if $t$ is not in a cycle.
.P
The first observation is that if
.DS 3
.EQ (2.3)
( aA ^(t+1) ~-~ aA ^(t-1)) ~cC ^(t) ~!=~ 0 ^,
.EN
.DE
then
.DS 3
.EQ
( aA ^(t+1) ~-~ aA ^(t-1)) ~cC ^(t) ~<=~ -^ 1 ^,
.EN
.DE
and so
.DS 3
.EQ
eE ^(t) ~<=~ -^ 1 ^,
.EN
.DE
because $alpha$ (given by (1.6)) is large.
.P
The next observation is that if $aA ^(t+1) ~=~ aA ^(t-1)$, then
$eE ^(t) ~=~ 0$.
Hence it only remains to consider the case when $aA ^(t+1) ~!=~ aA ^(t-1)$,
but $cC ^(t) ~=~ 0$.
We consider two subcases:
.sp
Case a).
$bB ^(t) ~=~ aA ^(t)$ for all $j ~member~ dD$.
In this case $aA ^(t+1) ~=~ aA ^(t)$, and therefore
.DS 3
.EQ
eE ^(t) ~mark =~ 2~ min ( aA ^(t) , ~aA ^(t-1)) ~-~ 2~ aA ^(t)
.EN
.sp
.EQ
~lineup +~ 2~ sum from {j ^member^ dD} ~ "{" min ( bB ^(t) , ~aA ^(t-1))
~-~ min ( bB ^(t) , ~aA ^(t)) "}"
.EN
.sp
.EQ
~lineup +~ aA ^(t) ~-~ aA ^(t-1) ~.
.EN
.DE
If $aA ^(t) ~>=~ aA ^(t-1)$, then, since $aA ^(t+1) ~=~ aA ^(t) ~!=~ aA ^(t-1)$,
we must have $aA ^(t) ~=~ aA ^(t-1) ~+~ 1$, so
.DS 3
.EQ
min ( bB ^(t) , ~aA ^(t-1)) ~-~ min ( bB ^(t) , ~aA ^(t)) ~<=~ 0
.EN
.DE
for all $j ~member~ dD$, and therefore
.DS 3
.EQ
eE ^(t) ~<=~ 1 ~-~ 2 ~=~ -^1 ~.
.EN
.DE
If $aA ^(t) ~<~ aA ^(t-1)$, then
$aA ^(t+1) ~=~ aA ^(t) ~=~ aA ^(t-1) ~-~ 1$, so
.DS 3
.EQ
eE ^(t) ~=~ -^ 1 ~.
.EN
.DE
Case b).
$bB ^(t) ~!=~ aA ^(t)$ for some $j ~member~ dD$.
In this situation
.DS 3
.EQ
aA ^(t+1) ~=~ aA ^(t) ~+~ 1 ^,
.EN
.DE
so, since $aA ^(t+1) ~!=~ aA ^(t-1)$, we must have
.DS 3
.EQ
aA ^(t+1) ~>=~ aA ^(t-1) ~+~ 1 ^,
.EN
.DE
and therefore for each $j ~member~ dD$,
.DS 3
.EQ
min ( bB ^(t) , ~aA ^(t-1)) ~-~ min ( bB ^(t) , ~aA (t+1)) ~<=~ 0 ^,
.EN
.DE
and for at least one $j ~member~ dD$, the difference above must
be $-^1$ or $-^2$.
Hence
.DS 3
.EQ
2~ sum from {j ^member^ dD} ~ "{" min ( bB ^(t) , ~aA ^(t-1)) ~-~ min ( bB
^(t) , ~aA ^(t+1)) "}" ~<=~ -^ 2 ~.
.EN
.DE
On the other hand,
.DS 3
.EQ
2~ min ( aA ^(t) , ~aA ^(t-1)) ~mark -~ 2~ min ( aA ^(t+1) , ~aA ^(t))
.EN
.sp
.EQ
+~ aA ^(t+1) ~-~ aA ^(t-1) ~lineup =~ 0 ~roman or~ 1 ^,
.EN
.DE
so that $eE ^(t) ~<=~ -^ 1$ in this case also.
\(sq
.P
We now turn to an investigation of the length of the transient.
If we assume that the initial values satisfy $-^ p ~<=~ aA ^(0) ~<=~ p$
for all $i$, then (1.3) and (1.5) show that
$| E(t) | ~=~ O( n alpha sup 2 ^p sup 2 )$, and so the length of
the transient is $O( n alpha sup 2 ^p sup 2 )$.
One can improve this bound somewhat.
.sp
.I
Theorem 2.
If $-^p ~<=~ aA ^(0) ~<=~ p$ for all $i$, then the iteration enters
a cycle after
.DS 3
.EQ (2.4)
<= ~ 10 ^alpha ^ p^e
.EN
.DE
updates, where $e$ denotes the number of edges in the graph.
.R
.sp
\f2Proof\f1.
We can clearly assume that the graph is connected, so that
$e ~>=~ n-1$.
We first note that for all $i$
.DS 3
.EQ (2.5)
| cC ^(t+1) ~-~ cC ^(t) | ~<=~ 2 fF ~.
.EN
.DE
Therefore, if $cC ^(t) ~>~ 2 fF$, then $cC ^(t-1) ~>~ 0$, and therefore
.DS 3
.EQ
aA ^(t+1) ~mark =~ aA ^(t-1) ~+~ 2 ^,
.EN
.sp
.EQ (2.6)
eE ^(t) ~<= ~mark -~ 2 ^alpha^ cC ^(t) ~+~ 2 fF ~<=~ -^ alpha | cC ^(t) | ~.
.EN
.DE
The bound (2.6) applies in the same way when $cC ^(t) ~<~ -^ 2 fF$.
Furthermore, if $| cC ^(t) | ~>=~ 2 fF$, then
$| cC ^(t+1) | ~<=~ | cC ^(t) |$.
The last observation implies that if $| cC ^(t) | ~<~ 4 fF$, then
$| cC ^(t+1) | ~<~ 4 fF$ as well.
.P
We now proceed to the proof of the theorem.
We have
.DS 3
.EQ
| E(t) | ~mark <=~ alpha | E sub 0 ^(t) | ~+~ 4 np ~+~ 2p ~ sum from i=1 to n ~fF
.EN
.sp
.EQ
~lineup =~ alpha | E sub 0 ^(t) | ~+~ 4p (n ^+^ e) ~.
.EN
.DE
Now
.DS 3
.EQ
E sub 0 ^(t) ~=~ -~ sum from j=1 to n ~bB ^(t-1) ~S sub j ^(t) ^,
.EN
.DE
so
.DS 3
.EQ
| E sub 0 ^(t) | ~<=~ 4p ~sum from j=1 to n ~d sub j ~+~ p~ sum from {j ^member^ A(t)}
~ | S sub j ^(t) | ^,
.EN
.DE
where
.DS 3
.EQ
A(t) ~=~ "{" j: ~ 1 ~<=~ j ~<=~ n, ~ | S sub j ^(t) | ~>=~ 4 d sub j "}" ~.
.EN
.DE
Hence
.DS 3
.EQ
| E(t) | ~<=~ 8^ alpha ^pe ~+~ 4p (n ^+^ e) ~+~ alpha ^p ~sum from {j ^member^ A(t)}
~ | S sub j ^(t) | ~.
.EN
.DE
By our previous observations, however, we have
.DS 3
.EQ
E(t+1) ~-~ E(t) ~<=~ -^ alpha ~sum from {j ^member^ A(t)} ~ | S sub j ^(t) | ^,
.EN
.DE
and $A(1) ~!supset~ A(2) ^!supset ... ^,$ so that
.DS 3
.EQ
| E( 2p ) | ~<=~ 8^ alpha ^ pe ~+~ 4p ( n ^+^ e) ^,
.EN
.DE
and the bound (2.4) of the theorem follows.
.H 1 "Concluding remarks"
The constant 10 in the bound (2.4) of Theorem 2 can easily be
improved.
However, it would be much more interesting to improve on the
main term $alpha ^pe$.
.bp
.ce
.B
References
.R
.sp
.AL
.LI
D. C. Ghiglia, G. A. Mastin, and L. A. Romero, Cellular automata
method for phase unwrapping, \f2J. Optical Soc. America A, 4\f1 (1987), 267-280.
.LI
E. Goles, Dynamics of positive automata networks, \f2Theoretical Comp. Sci. 41\f1
(1985), 19-32.
.LI
E. Goles, Antisymmetric neutral networks, \f2Discr. Appl. Math. 13\f1 (1986),
97-100.
.LI
E. Goles-Chacc, F. Fogelman-Soulie, and D. Pellegrin, Decreasing
energy functions as a tool for studying threshold functions,
\f2Discrete Appl. Math. 12\f1 (1985), 261-277.
.LI
E. Goles and J. Olivos, Compartment ite\*'ratif des fonctions a\*'
multiseuil, \f2Inform. Control 45\f1 (1980), 300-313.
.LI
A. M. Odlyzko and D. J. Randall, On the periods of some graph
transformations, \f2Complex Systems 1\f1 (1987), 203-210.
.LI
S. Poljak and M. Sura, On periodical behavior in societies with symmetric
influences, \f2Combinatorica 3\f1 (1983), 119-121.
.LI
S. Poljak and D. Turzik, Social influence models with ranking alternatives
and local election rules, \f2Math. Social Sci. 10\f1 (1985), 189-198.
.LI
S. Poljak and D. Turzik, On an application of convexity to discrete
systems, \f2Discr. Appl. Math. 13\f1 (1986), 27-32.
.LI
S. Poljak and D. Turzik, On pre-periods of discrete influence systems,
\f2Discr. Appl. Math. 13\f1 (1986), 33-39.
.LE