Complexity of Two-Dimensional Patterns

In dynamical systems such as cellular automata and iterated maps, it is often useful to look at a language or set of symbol sequences produced by the system. There are well-established classification schemes, such as the Chomsky hierarchy, with which we can measure the complexity of these sets of sequences, and thus the complexity of the systems which produce them. In this paper, we look at the first few levels of a hierarchy of complexity for two-or-more-dimensional patterns. We show that several definitions of regular language or local rule that are equivalent in d=1 lead to distinct classes in d2. We explore the closure properties and computational complexity of these classes, including undecidability and L, NL, and NP-completeness results. We apply these classes to cellular automata, in particular to their sets of fixed and periodic points, finite-time images, and limit sets. We show that it is undecidable whether a CA in d2 has a periodic point of a given period, and that certain local lattice languages are not finite-time images or limit sets of any CA. We also show that the entropy of a d-dimensional CA's finite-time image cannot decrease faster than t ^–d unless it maps every initial condition to a single homogeneous state.     

Statistical mechanics of probabilistic cellular automata

We investigate the behavior of discrete-time probabilistic cellular automata (PCA), which are Markov processes on spin configurations on ad-dimensional lattice, from a rigorous statistical mechanics point of view. In particular, we exploit, whenever possible, the correspondence between stationary measures on the space-time histories of PCAs on ^d and translation-invariant Gibbs states for a related Hamiltonian on ( ^d+1). This leads to a simple large-deviation formula for the space-time histories of the PCA and a proof that in a high-temperature regime the stationary states of the PCA are Gibbsian. We also obtain results about entropy, fluctuations, and correlation inequalities, and demonstrate uniqueness of the invariant state and exponential decay of correlations in a high-noise regime. We discuss phase transitions in the low-noise (or low-temperature) regime and review Toom's proof of nonergodicity of a certain class of PCAs.     

Strict entropy production bounds and stability of the rate of convergence to equilibrium for the Boltzmann equation

We first consider the Boltzmann equation with a collision kernel such that all kinematically possible collisions are run at equal rates. This is the simplest Boltzmann equation having the compressible Euler equations as a scaling limit. For it we prove a stability result for theH-theorem which says that when the entropy production is small, the solution of the spatially homogeneous Boltzmann equation is necessarily close to equilibrium in the entropie sense, and therefore strongL ¹ sense. We use this to prove that solutions to the spatially homogeneous Boltzmann equation converge to equilibrium in the entropie sense with a rate of convergence which is uniform in the initial condition for all initial conditions belonging to certain natural regularity classes. Every initial condition with finite entropy andp ^th velocity moment for some p>2 belongs to such a class. We then extend these results by a simple monotonicity argument to the case where the collision rate is uniformly bounded below, which covers a wide class of slightly modified physical collision kernels. These results are the basis of a study of the relation between scaling limits of solutions of the Boltzmann equation and hydrodynamics which will be developed in subsequent papers; the program is described here.On leave from School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332.On leave from C.F.M.C. and Departamento de Matemática da Faculdade de Ciencias de Lisboa, 1700 Lisboa codex, Portugal.     

Spectral Gap for Multi-species Exclusion Processes

We consider a multi-species generalization of the symmetric simple exclusion process in homogeneous and non-homogeneous hypercubes of Z ^d . In this model, the hyperplanes of configurations with given numbers of particles of each species are not necessarily irreducible. We give a sufficient condition of the dynamics to make them irreducible. In addition, assuming the irreducibility of them, we show some estimates of the spectral gap (the absolute value of the second largest eigenvalue of the generator), which plays an important role in the study of hydrodynamic limit.     

Large Deviations for Probabilistic Cellular Automata II

We obtain an upper large deviations bound which shows that for some models of probabilistic cellular automata (which are far away from the product case) the lower large deviation bound derived in Eizenberg and Kifer J. Stat. Phys. 108: 1255–1280 (2002) is sharp, and so the corresponding large deviations phenomena cannot be described via the traditional Donsker–Varadhan form of the action functional. For models which are close to the product case we derive approximate large deviations bounds using the Donsker–Varadhan functional for the product case.     

An Asymptotic Expansion and Recursive Inequalities for the Monomer-Dimer Problem

Let λ _d (p) be the p monomer-dimer entropy on the d-dimensional integer lattice ℤ ^d , where p∈[0,1] is the dimer density. We give upper and lower bounds for λ _d (p) in terms of expressions involving λ _d−1(q). The upper bound is based on a conjecture claiming that the p monomer-dimer entropy of an infinite subset of ℤ ^d is bounded above by λ _d (p). We compute the first three terms in the formal asymptotic expansion of λ _d (p) in powers of  \frac1d\frac{1}{d}. We prove that the lower asymptotic matching conjecture is satisfied for λ _d (p). Converted to a power series in p, our “formal” expansion shows remarkable validity in low dimensions, d=1,2,3, in which dimensions we give some numerical studies.     

Eigenvalues of Laplacian with Constant Magnetic Field on Non-Compact Hyperbolic Surfaces with Finite Area

We consider a magnetic Laplacian −Δ _A = (id + A)^* (id + A) on a non-compact hyperbolic surface M with finite area. A is a real one-form and the magnetic field dA is constant in each cusp. When the harmonic component of A satisfies some quantified condition, the spectrum of −Δ _A is discrete. In this case, we prove that the counting function of the eigenvalues of −Δ _A satisfies the classical Weyl formula, even when dA=0.     

How to Prove Dynamical Localization

Let H be a self-adjoint operator on l ²(Z ^d ) or L ²(R ^d ) with pure point spectrum on some interval I. We establish general necessary and sufficient conditions for dynamical localization for a given vector and on the interval of energies I. The sufficient conditions we obtain improve the existing ones such as SULE or WULE and can be useful in applications. Received: 16 November 2000 / Accepted: 14 February 2001     

Realizability of Point Processes

There are various situations in which it is natural to ask whether a given collection of k functions, ρ _j (r ₁,…,r _j ), j=1,…,k, defined on a set X, are the first k correlation functions of a point process on X. Here we describe some necessary and sufficient conditions on the ρ _j ’s for this to be true. Our primary examples are X=ℝ ^d , X=ℤ ^d , and X an arbitrary finite set. In particular, we extend a result by Ambartzumian and Sukiasian showing realizability at sufficiently small densities ρ ₁(r). Typically if any realizing process exists there will be many (even an uncountable number); in this case we prove, when X is a finite set, the existence of a realizing Gibbs measure with k body potentials which maximizes the entropy among all realizing measures. We also investigate in detail a simple example in which a uniform density ρ and translation invariant ρ ₂ are specified on ℤ; there is a gap between our best upper bound on possible values of ρ and the largest ρ for which realizability can be established.     

Ising models on hyperbolic graphs

We consider Ising models on a hyperbolic graph which, loosely speaking, is a discretization of the hyperbolic planeH ² in the same sense asZ ^d is a discretization ofR ^d . We prove that the models exhibit multiple phase transitions. Analogous results for Potts models can be obtained in the same way.     

Self-organisation in Cellular Automata with Coalescent Particles: Qualitative and Quantitative Approaches

This article introduces new tools to study self-organisation in a family of simple cellular automata which contain some particle-like objects with good collision properties (coalescence) in their time evolution. We draw an initial configuration at random according to some initial shift-ergodic measure, and use the limit measure to describe the asymptotic behaviour of the automata. We first take a qualitative approach, i.e. we obtain information on the limit measure(s). We prove that only particles moving in one particular direction can persist asymptotically. This provides some previously unknown information on the limit measures of various deterministic and probabilistic cellular automata: 3 and 4-cyclic cellular automata [introduced by Fisch (J Theor Probab 3(2):311–338, 1990; Phys D 45(1–3):19–25, 1990)], one-sided captive cellular automata [introduced by Theyssier (Captive Cellular Automata, 2004)], the majority-traffic cellular automaton, a self stabilisation process towards a discrete line [introduced by Regnault and Rémila (in: Mathematical Foundations of Computer Science 2015—40th International Symposium, MFCS 2015, Milan, Italy, Proceedings, Part I, 2015)]. In a second time we restrict our study to a subclass, the gliders cellular automata. For this class we show quantitative results, consisting in the asymptotic law of some parameters: the entry times [generalising K ?rka et al. (in: Proceedings of AUTOMATA, 2011)], the density of particles and the rate of convergence to the limit measure.     

Evolution of the population of outer 6s and 5d shells in rare-earth metals

The shifts of the Kα ₁ and Kβ ₁ lines of all rare-earth (RE) metals (from La to Lu) have been measured experimentally by the x-ray shift method. The population of the RE-metal 6s and 5d shells has been determined by comparing the experimental and theoretical shifts obtained within the Dirac-Fock (Koopmans) model. Trivalent metals exhibit a monotonic cross-over from the 6s ^≈25d ^≈1 to 6s ^≈15d ^≈2 configuration with increasing atomic number. Fiz. Tverd. Tela (St. Petersburg) 41, 1361–1362 (August 1999)     

Ergodicity of probabilistic cellular automata: A constructive criterion

We give a sequence of criteria (of increasing complexity) for the exponential ergodicity of discrete time interacting particle systems. Each criterion involves estimating the dependence on initial conditions of the process on finite space-time volumes. It generalizes and improves the existing single site condition and is the analog of the Dobrushin-ShlosmanC _v condition in equilibrium statistical mechanics. Our dynamic criterion may also be used to prove the uniqueness of Gibbs state in situations where theC _v condition fails. As a converse we prove that if there is a certain form of convergence to the stationary measure faster thann ^–d , wheren is the time andd is the dimension of the lattice, then our condition holds for some space-time volumes and hence the convergence must be exponentially fast.     

Reversibility of 1D Cellular Automata with Periodic Boundary over Finite Fields $\pmb{ {\mathbb{Z}}}_{p}$

The reversibility problem for linear cellular automata with null boundary defined by a rule matrix in the form of a pentadiagonal matrix was studied recently over the binary field ℤ₂ (del Rey and Rodriguez Sánchez in Appl. Math. Comput., 2011, doi:). In this paper, we study one-dimensional linear cellular automata with periodic boundary conditions over any finite field ℤ _p . For any given p≥2, we show that the reversibility problem can be reduced to solving a recurrence relation depending on the number of cells and the coefficients of the local rules defining the one-dimensional linear cellular automata. More specifically, for any given values (from any fixed field ℤ _p ) of the coefficients of the local rules, we outline a computer algorithm determining the recurrence relation which can be solved by testing reversibility of the cellular automaton for some finite number of cells. As an example, we give the full criteria for the reversibility of the one-dimensional linear cellular automata over the fields ℤ₂ and ℤ₃.     

Ergodic endomorphisms of compact abelian groups

We show that for a surjective endomorphism of a compact abelian group ergodicity is equivalent to a condition which impliesr-mixing for allr1, and we characterize such maps algebraically. This is then used in proving the ergodicity of an extensive class of endomorphisms of the binary sequence space. As a simple corollary it is found that one-dimensional linear cellular automata and the accumulator automata arer-mixing for allr1.This work was supported in part by grants from NSERC     

Exponential Decay of Correlations for Strongly Coupled Toom Probabilistic Cellular Automata

We investigate the low-noise regime of a large class of probabilistic cellular automata, including the North-East-Center model of Toom. They are defined as stochastic perturbations of cellular automata belonging to the category of monotonic binary tessellations and possessing a property of erosion. We prove, for a set of initial conditions, exponential convergence of the induced processes toward an extremal invariant measure with a highly predominant spin value. We also show that this invariant measure presents exponential decay of correlations in space and in time and is therefore strongly mixing.     

Mean-Field Driven First-Order Phase Transitions in Systems with Long-Range Interactions

We consider a class of spin systems on ℤ ^d with vector valued spins (S _x ) that interact via the pair-potentials J _x,y S _x ⋅S _y . The interactions are generally spread-out in the sense that the J _x,y 's exhibit either exponential or power-law fall-off. Under the technical condition of reflection positivity and for sufficiently spread out interactions, we prove that the model exhibits a first-order phase transition whenever the associated mean-field theory signals such a transition. As a consequence, e.g., in dimensions d≥3, we can finally provide examples of the 3-state Potts model with spread-out, exponentially decaying interactions, which undergoes a first-order phase transition as the temperature varies. Similar transitions are established in dimensions d = 1,2 for power-law decaying interactions and in high dimensions for next-nearest neighbor couplings. In addition, we also investigate the limit of infinitely spread-out interactions. Specifically, we show that once the mean-field theory is in a unique “state,” then in any sequence of translation-invariant Gibbs states various observables converge to their mean-field values and the states themselves converge to a product measure.     

A New Class of Cellular Automata with a Discontinuous Glass Transition

We introduce a new class of two-dimensional cellular automata with a bootstrap percolation-like dynamics. Each site can be either empty or occupied by a single particle and the dynamics follows a deterministic updating rule at discrete times which allows only emptying sites. We prove that the threshold density ρ _c for convergence to a completely empty configuration is non trivial, 0<ρ _c <1, contrary to standard bootstrap percolation. Furthermore we prove that in the subcritical regime, ρ<ρ _c , emptying always occurs exponentially fast and that ρ _c coincides with the critical density for two-dimensional oriented site percolation on ℤ². This is known to occur also for some cellular automata with oriented rules for which the transition is continuous in the value of the asymptotic density and the crossover length determining finite size effects diverges as a power law when the critical density is approached from below. Instead for our model we prove that the transition is discontinuous and at the same time the crossover length diverges faster than any power law. The proofs of the discontinuity and the lower bound on the crossover length use a conjecture on the critical behaviour for oriented percolation. The latter is supported by several numerical simulations and by analytical (though non rigorous) works through renormalization techniques. Finally, we will discuss why, due to the peculiar mixed critical/first order character of this transition, the model is particularly relevant to study glassy and jamming transitions. Indeed, we will show that it leads to a dynamical glass transition for a Kinetically Constrained Spin Model. Most of the results that we present are the rigorous proofs of physical arguments developed in a joint work with D.S. Fisher.     

From dilute to dense self-avoiding walks on hypercubic lattices

A field-theoretic representation is presented to count the number of configurations of a single self-avoiding walk on a hypercubic lattice ind dimensions with periodic boundary conditions. We evaluate the connectivity constant as a function of the fractionf of sites occupied by the polymer chain. The meanfield approximation is exact in the limit of infinite dimensions, and corrections to it in powers ofd ^–1 can be systematically evaluated. The connectivity constant and the site entropy calculated throughout second order compare well with known results in two and three dimensions. We also find that the entropy per site develops a maximum atf1–(2d)^–1. Ford=2 (d=3), this maximum occurs atf~0.80 (f~0.86) and its value is about 50% (30%) higher than the entropy per site of a Hamiltonian walk (f=1).