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 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 in a finite alphabet using a translational invariant rule. More precisely, a CA is a continuous map on the compact space which commutes with all translations with . By the Curtis-Hedlund-Lyndon theorem, the new state at a grid point depends only on , where F is a finite neighborhood of n. As for any dynamical system , 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 , also and the attractor is a compact set on which all invariant measures of 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 . Associated with each interval is a value . For , a Sturmean configuration is given by

where is a vector of d rotation numbers, is a parameter, and is the location of a cell in the lattice . Here is the characteristic function of a set H, which is 1 for and 0 for . Periodicity can be established by taking rational numbers . It can be seen in a constructive way that the CA rule applies to the interval data J. The translation back to the lattice 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 of intervals. It is a measure for the memory needed to store a configuration. Of course, if the numbers are all rational, then there is an upper bound for the number of intervals. If one rotation number is irrational, the number of intervals will in general grow indefinitely. How fast can it grow? Let be the influence region of and assume , where each is a finite union of half open intervals with . An interval configuration J consists of half open intervals. We claim that the number of intervals has a polynomial upper bound . To prove this it is enough to show the claim for n=1 and then replace by . If with is the set of boundary points of the partition J, then the set of boundary points of the new partition is contained in the set which contains not more than elements. If has radius r, then has a radius and . We can therefore define a growth rate of complexity

It satisfies because . The actual growth rate can of course be smaller. See [4] for examples where and . From all of the numerical experiments that we have performed, it is reasonable to believe that the limit actually exists. Of course, if are all rational then . 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 the dynamics is not recurrent even though it is reversible.

The number 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 has entropy , while in the almost periodic setup for every J because 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 . 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 has an inverse which is obtained by evolving the particle configuration, where the directions of the particles are reversed. The theoretical bound gives and . Experiments with almost periodic lattice gas automata were done in [4, 11]. We measured values for the HPP model. The value seems to be quite independent of the initial condition J. If , the dynamics is not recurrent event hough the system is reversible. We observe a weak convergence of the measures to a multiple of the Lebesgue measure. This uniform mixing of intervals is expected to hold whenever and indicate that the system does approach equilibrium, a fact which is expected to happen for some CA used in fluid dynamics [15].