Next: Almost periodic particle dynamics Up: Complexity Growth in Almost Previous: Introduction


Almost periodic lattice gas automata

Lattice gas CA are used for numerical simulations of fluids. They provide a reasonable numerical method when the fluid has complex geometric boundary conditions. Almost periodic CA [4] can store and process large periodic configurations in a compressed form and allow for dealing with infinite aperiodic configurations. The size of the data used to store the configuration measures the complexity of the fluid. The growth rate of this information is a numerical quantity which can be determined. As in the case of the entropy for smooth dynamical systems, one cannot expect to compute it explicitly in general.

The term "almost periodicity" for CA is used as a synonym for minimality, a common terminology in mathematical physics that is different from the mathematical term of Bohr almost periodic functions considered in section 3: a configuration tex2html_wrap_inline310 is called almost periodic if no nontrivial closed shift invariant subset in the closure of the orbit of x exists. Almost periodicity is interesting since it occurs in nature, for example, in quasi-crystalline materials, where the centers of the atoms form almost periodic configurations. Mathematically, almost periodic initial conditions are a natural alternative to periodic or random initial conditions.

CA are dynamical systems which evolve a d-dimensional array of letters tex2html_wrap_inline316 in a finite alphabet tex2html_wrap_inline318 using a translational invariant rule. More precisely, a CA is a continuous map tex2html_wrap_inline320 on the compact space tex2html_wrap_inline322 which commutes with all translations tex2html_wrap_inline324 with tex2html_wrap_inline326 . By the Curtis-Hedlund-Lyndon theorem, the new state tex2html_wrap_inline328 at a grid point tex2html_wrap_inline330 depends only on tex2html_wrap_inline332 , where F is a finite neighborhood of n. As for any dynamical system tex2html_wrap_inline320 , one is interested in invariant sets such as attractors or periodic orbits. Such invariant sets are crucial for understanding the long term behavior of the dynamics and especially the behavior of averaged quantities over time. Since tex2html_wrap_inline340 , also tex2html_wrap_inline342 and the attractor tex2html_wrap_inline344 is a compact set on which all invariant measures of tex2html_wrap_inline320 have their support. K decomposes in general to smaller closed invariant sets. The minimal invariant subsets are by definition almost periodic and sometimes, we expect a minimal set that can be given by a Sturmean configuration which can be stored with a small amount of data. At a fixed time such a configuration is represented as a union of half open intervals tex2html_wrap_inline350 . Associated with each interval tex2html_wrap_inline352 is a value tex2html_wrap_inline354 . For tex2html_wrap_inline356 , a Sturmean configuration is given by

displaymath358

where tex2html_wrap_inline360 is a vector of d rotation numbers, tex2html_wrap_inline364 is a parameter, and tex2html_wrap_inline366 is the location of a cell in the lattice tex2html_wrap_inline368 . Here tex2html_wrap_inline370 is the characteristic function of a set H, which is 1 for tex2html_wrap_inline376 and 0 for tex2html_wrap_inline380 . Periodicity can be established by taking rational numbers tex2html_wrap_inline280 . It can be seen in a constructive way that the CA rule tex2html_wrap_inline320 applies to the interval data J. The translation back to the lattice tex2html_wrap_inline388 is only necessary when inspecting part of the phase space. Note also that with a nondeterministic rule there is still an evolution on the set of intervals.

An interesting quantity is the growth rate of the number tex2html_wrap_inline390 of intervals. It is a measure for the memory needed to store a configuration. Of course, if the numbers tex2html_wrap_inline280 are all rational, then there is an upper bound for the number of intervals. If one rotation number tex2html_wrap_inline280 is irrational, the number of intervals will in general grow indefinitely. How fast can it grow? Let tex2html_wrap_inline396 be the influence region of tex2html_wrap_inline320 and assume tex2html_wrap_inline400 , where each tex2html_wrap_inline402 is a finite union of half open intervals tex2html_wrap_inline404 with tex2html_wrap_inline406 . An interval configuration J consists of tex2html_wrap_inline410 half open intervals. We claim that the number of intervals tex2html_wrap_inline390 has a polynomial upper bound tex2html_wrap_inline414 . To prove this it is enough to show the claim for n=1 and then replace tex2html_wrap_inline320 by tex2html_wrap_inline420 . If tex2html_wrap_inline422 with tex2html_wrap_inline424 is the set of boundary points of the partition J, then the set of boundary points of the new partition tex2html_wrap_inline428 is contained in the set tex2html_wrap_inline430 which contains not more than tex2html_wrap_inline432 elements. If tex2html_wrap_inline320 has radius r, then tex2html_wrap_inline420 has a radius tex2html_wrap_inline440 and tex2html_wrap_inline442 . We can therefore define a growth rate of complexity

displaymath444

It satisfies tex2html_wrap_inline446 because tex2html_wrap_inline448 . The actual growth rate can of course be smaller. See [4] for examples where tex2html_wrap_inline450 and tex2html_wrap_inline452 . From all of the numerical experiments that we have performed, it is reasonable to believe that the limit actually exists. Of course, if tex2html_wrap_inline280 are all rational then tex2html_wrap_inline452 . In this case, the complexity bound shows that evolving intervals is as efficient as evolving CA traditionally. It is in general better, because evolving the intervals performs the CA computations in a compressed way. From the information point of view we should look at the number of intervals as a measure of complexity because it is an upper bound for the Chaitin complexity of the configuration. If tex2html_wrap_inline458 the dynamics is not recurrent even though it is reversible.

The number tex2html_wrap_inline460 seems not to be related to the entropy defined in [9] because looking at the CA dynamics on a thin subset of almost periodic configurations changes the dynamical properties considerably. For example, the one-dimensional shift on tex2html_wrap_inline462 has entropy tex2html_wrap_inline464 , while in the almost periodic setup tex2html_wrap_inline452 for every J because tex2html_wrap_inline470 implies that the number of intervals does not change. Let us look at the deterministic and reversible lattice gas automaton HPP [2, 3], where up to four particles can be at a cell moving along one of the basis vectors tex2html_wrap_inline472 . During an iteration step, a particle is advanced one cell in the direction of its velocity. When two particles collide with opposite velocity, both particles are scattered by a rotation of 90 degrees. This rule preserves the particle number, the total momentum, and the total energy, quantities that are also defined for aperiodic almost periodic situations. Note that the automaton is reversible because tex2html_wrap_inline320 has an inverse which is obtained by evolving the particle configuration, where the directions of the particles are reversed. The theoretical bound gives tex2html_wrap_inline476 and tex2html_wrap_inline478 . Experiments with almost periodic lattice gas automata were done in [4, 11]. We measured values tex2html_wrap_inline480 for the HPP model. The value tex2html_wrap_inline482 seems to be quite independent of the initial condition J. If tex2html_wrap_inline486 , the dynamics is not recurrent event hough the system is reversible. We observe a weak convergence of the measures tex2html_wrap_inline488 to a multiple of the Lebesgue measure. This uniform mixing of intervals is expected to hold whenever tex2html_wrap_inline458 and indicate that the system does approach equilibrium, a fact which is expected to happen for some CA used in fluid dynamics [15].

Next: Almost periodic particle dynamics Up: Complexity Growth in Almost Previous: Introduction

Oliver Knill
Mon Jun 29 14:18:53 CDT 1998