Damien Regnault

Nicolas Schabanel

Éric Thierry

On the analysis of "simple" 2D stochastic cellular automata †

Keywords:

). This paper confirms the relevance of the later approach (definition of energy functions and identification of competing regions). Switching to the Moore neighborhood however strongly complicates the description of intermediate configurations. New phenomena appear (particles, wider range of stable configurations). Nevertheless our methods allow to analyze different stages of the dynamics. It suggests that predicting the behavior of this automaton although difficult is possible, opening the way to the analysis of the whole class of totalistic automata.

Introduction

Cellular automata are attractive models for complex systems in various fields, like physics, biology or social sciences. Their relevance is supported by many observations of natural phenomena which closely match the dynamics of some cellular automaton, as illustrated by Fig. 1. An example of challenging issue in biology is to predict the expression of genes in a set of cells which share the same gene regulatory network. Cellular automata can be used to model such systems [START_REF] Ermentrout | Cellular automata approaches to biological modelling[END_REF][START_REF] Silva | A cellular automata model for cell differentiation[END_REF]. For example consider the simple gene regulatory networks where a gene exerts a feedback inhibition of its expression. The state of a cell is whether it expresses this gene or not. Assuming that each cell starts expressing the gene when less (a) The pattern growth of the shell of the widespread species Conus textile is governed by a mathematical function presenting similarities with the CA Rule 30 above.

t = 4h15 t = 4h45 t = 5h00

Pictures extracted from [START_REF] Mott | Stomatal patchiness and task-performing networks[END_REF] (b) Leaves have to solve a dilema: opening their stomata to ingest CO 2 but not too much to avoid letting go too much water. In [START_REF] Mott | Stomatal patchiness and task-performing networks[END_REF] the authors show by analyzing statistical parameters that the patterns arising during the control of the opening of the stomata when facing a sudden drop in humidity are space and time correlated identically as several known cellular automata. One explanation would be the absence of central nervous system implying that the aperture has to be chosen by local consensus in a rather slow process (more than five hours).

Fig. 1: Cellular automata as models in biology.

than half of its neighbors (including itself) express it, and that otherwise it stops expressing it, leads to the Minority rule [START_REF] Demongeot | Genetic regulation networks: circuits, regulons and attractors[END_REF]. If cells are assembled into a two-dimensional grid, it yields 2D Minority. Such a model is of course an extreme simplification of any real phenomena but understanding a simple rule like Minority is already challenging and a key step step towards the study of more involved interaction networks. The development of mathematical tools to predict the dynamics of such models appears as an essential complement to simulations. Surprisingly, such simple rule already exhibits an astonishingly rich behavior which is investigated in this paper.

The 2D Minority automaton belongs to the class of threshold cellular automata with negative feedback (a cell tends to flip its state unless it is stabilized by its neighboring cells). The threshold automata have been intensively studied under synchronous dynamics (at each time step, all the cells update simultaneously) [START_REF] Goles | Neural and automata networks, dynamical behavior and applications[END_REF]. However transitions in regulatory networks are rather slow: switching between activated and inhibited takes about 10 minutes as well as traveling from one cell to a neighboring one (see for instance [START_REF] Prochiantz | Processus morphogénétiques. Lectures at the Collège de France[END_REF]); synchronicity is thus highly unlikely. As a consequence, models for natural phenomena rather update asynchronously. Furthermore, because of the slowness of the transitions, one should also focus on transitory regimes and not only consider permanent regime. Empirical studies [START_REF] Bersini | Asynchrony induces stability in cellular automata based models[END_REF][START_REF] Buvel | Structure in asynchronous cellular automata[END_REF][START_REF] Fatès | An experimental study of robustness to asynchronism for elementary cellular automata[END_REF][START_REF] Huberman | Evolutionary games and computer simulations[END_REF][START_REF] Kanada | Asynchronous 1d cellular automata and the effects of fluctuation and randomness[END_REF][START_REF] Schönfisch | Synchronous and asynchronous updating in cellular automata[END_REF] have shown how the behavior can change drastically when introducing asynchronism. However only few mathematical analyses are available and they mainly concern one-dimensional stochastic cellular automata [START_REF] Fatès | Fully asynchronous behavior of doublequiescent elementary cellular automata[END_REF][START_REF] Fatès | Asynchronous behavior of doublequiescent elementary cellular automata[END_REF][START_REF] Fukś | Non-deterministic density classification with diffusive probabilistic cellular automata[END_REF][START_REF] Fukś | Probabilistic cellular automata with conserved quantities[END_REF]. Providing analyses of 2D rules remains a real challenge. For instance the mean-field approach does not succeed in approximating tightly such stochastic dynamics [START_REF] Balister | Large deviations for mean fields models of probabilistic cellular automata[END_REF] and a closer look to the geometrical structure might be unavoidable. Fig. 2 illustrates for three 2D cellular automata the differences between the synchronous dynamics and the fully asynchronous dynamics where one single random cell updates at each time step (or equivalently, where each cell has its own Poisson clock of rate 1 which Life Some random outer-totalistic Minority Synchronous dynamics Fully asynchronous dynamics Fig. 2: Typical configurations observed during the evolution of some 2D cellular automata (Moore neighborhood). Similar stripes emerge in asynchronous regime even if their synchronous behavior differ drastically.

triggers its updates). Some related stochastic models like Ising models or Hopfield nets have been studied under asynchronous dynamics (e.g. our model of asynchronism corresponds to the limit when temperature goes to 0 in the Ising model). These models are acknowledged to be harder to analyze when it comes to two-dimensional topologies [START_REF] Mccoy | The Two-Dimensional Ising Model[END_REF] or negative feedbacks [START_REF] Rojas | Neural Networks: A Systematic Introduction[END_REF].

For all these reasons 2D Minority under fully asynchronous dynamics turns out to be an interesting and challenging candidate for mathematical analyses. This paper focuses on the Moore neighborhood: each fired cell updates to the minority state among its eight neighbors and itself. It carries on a work initiated in [START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D minority[END_REF][START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority[END_REF] where 2D Minority was analyzed for the von Neumann neighborhood (four neighbors instead of eight). One might have hoped for minors adjustments to deal with the Moore neighborhood, however the results do not come out so easily. Simulations discussed in Section 3 show that new patterns (wider variety of striped patterns) and new phenomena occur (particle-like behaviors). Several key ideas presented in [START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority[END_REF] (definition of an appropriate energy function, definition of borders and regions) apply, but their use requires some innovations. We show that the initial stage of the dynamics is characterized by a fast energy drop (Theorem 9). Borders isolate striped regions competing with one another and we manage to prove how final stable (horizontally or vertically) stripes configurations are reached almost surely from typical configurations occuring at the end of the process. Furthermore, we prove that this convergence occurs in polynomial time (Theorem 17). In the proof, we show that as the regions crumble, inflate or retract, the overall structure admits a recursive description which persists over time. The proofs of the study of such dynamical systems, known as complex systems, involve unavoidable tedious case studies and one of the important contribution of this paper is to set up a compact, possibly elegant, and thus safe framework to deal with these enumeration of cases (see Fig. 12, and 14 for instance). We also state conjectures and list open problems in the perspective of a complete analysis of this automaton. Note that in the course of the paper, we present an interesting combinatorial characterization of the stable configurations for 2D Minority for the Moore neighborhood (Theorem 6). As far as we know, it has only been solved for the von Neumann neighborhood [START_REF] Goles | Neural and automata networks, dynamical behavior and applications[END_REF].

Definitions

We consider in this paper the 2D 2-state cellular automaton Minority under fully asynchronous dynamics over finite configurations with periodic boundary conditions. Definition 1 (Configuration) We are given two positive integers n and m, let N = nm. We denote by T = Z n × Z m the set of cells and Q = {0, 1} the set of states (0 stands for white and 1 for black in the figures). We consider the Moore neighborhood: two cells (i, j) and

(k, l) are neighbors if max(|i - k| n , |j -l| m ) 1 (where |i -j| p denotes the distance in Z p ). A n × m-configuration c is a function c : T → Q; c ij is the state of the cell (i, j) in configuration c.
Definition 2 (Stochastic 2D Minority) We consider the fully asynchronous dynamics of 2D Minority. Time is discrete and let c t denote the configuration at time t; c 0 is the initial configuration. The configuration at time t + 1 is a random variable defined by the following process: a cell (i, j) is selected uniformly at random in T and its state is updated to the minority state in its neighborhood (we say that cell (i, j) fires at time t), all the other cells remain in their current state:

c t+1 ij =    1 if (c t ij +c t i-1,j + c t i+1,j + c t i,j-1 + c t i,j+1 +c t i-1,j+1 + c t i-1,j-1 + c t i+1,j-1 + c t i+1,j+1
) 4 0 otherwise and c t+1 kl = c t kl for all (k, l) = (i, j). A cell is said active if its state would change if fired.

Definition 3 (Convergence)

A configuration c is stable if it remains unchanged under the dynamics, i.e., if all its cells are inactive. We say that the random sequence (c t ) converges almost surely from an initial configuration c 0 = c if the random variable T = min{t : c t is stable} is finite with probability 1. We say that the convergence occurs in polynomial time on expectation if E[T ] p(N ) for some polynomial p.

Simulations

Typical behavior. Click on the icons to open our website [14] for animated sequences. Like other 2D automata (such as Game of Life [START_REF] Bersini | Asynchrony induces stability in cellular automata based models[END_REF][START_REF] Fatès | Perturbing the topology of the game of life increases its robustness to asynchrony[END_REF]), the asynchronous behavior of 2D Minority differs radically from its synchronous dynamics. In particular, [START_REF] Goles | Neural and automata networks, dynamical behavior and applications[END_REF] proved that the synchronous dynamics eventually leads to stable configurations or cycles between two conjugated configurations. The latter case is the typical behavior in synchronous simulations where one can observe big flashing islands (Figure 2). On the contrary, as can be observed in Figure 3, the configurations are very stable over time in fully asynchronous regime and present very rapidly striped patterns (horizontal or vertical) that tend to extend and merge one with another until one gets over the others and ends up covering the whole configuration (when at least one of the dimensions n or m is even). One of the goals of this paper is to explore how these stripes arise and end up covering the whole configuration. Note also that the stripes arise as well in many other asynchronous automata especially in totalistic cellular automata (see Section 1 and Figure 2).

Very rarely a random initial configuration may converge to more exotic stable configurations. Figure 9 gives some examples of more or less exotic stable configurations under 2D minority dynamics. Borders and Particles. Part of the richness of 2D Minority under fully asynchronous behavior is due to some specific configurations where "particles" can be observed. Several patterns can be identified as particles although for now we do not have a formal definition. We say that there is a border between two diagonally neighboring cells if they are in the same state (more details in the next section). Active cells are always located near the borders. When the borders draw a pattern (where red spots indicate active cells), then, depending of which of the two active cells fires the pattern will move in different directions: forward or backward . Such patterns which "move" along borders can thus be called particles. In some configurations, the set of all the borders form a network of "rails" carrying several particules. These particules follow random walks along the rails and vanish when they collide. Note that the dynamics is a lot more intricate than 2D random walks because the rails are modified by the passage of the particules and if two rails become too close, a whole part of the rail network collapses. Figure 4 illustrates this phenomenon. Configurations with particles and rails are rarely reached from a random initial configuration. Nevertheless, we have to consider them when we study the convergence and these phenomena turn out to be extremely difficult to analyze mathematically. Such a system of particles does not exist in asynchronous 2D minority with von Neumann neighborhood [START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority[END_REF] nor in related models like the ferromagnetic Ising model or Hopfield networks with positive feedback.

E t = 0 t = N t = 2N t = 3N t = 5N t = 10N t = 20N t = 40N t = 60N t = 80N t = 100N t = 120N

Energy, Borders, Diamonds and Stable Configurations

Borders, Diamonds and Stripes

The following definitions allow to highlight the underlying structure of a configuration with respect to the dynamics. These tools turn out to be a key step to prove the convergence. Note that as opposed to the von Neumann neighborhood in [START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority[END_REF], the definition of the borders is no longer straightforward from the transition table for the Moore neighborhood.

Definition 4 (Stripes) If n and m are even, a set of cells R is said to be tiled with even horizontal stripes (resp. odd horizontal, even and odd vertical stripes) if c ij = i mod 2 (resp. i + 1, j, j + 1 mod 2), for all cells (i, j) ∈ R. Note that cells whose whole neighborhood is striped are inactive.

Definition 5 (Borders and diamonds) We say that there is a border between two diagonally neighboring cells (i, j) and (i ± 1, j ± 1) if they are in the same state, i.e., if c ij = c i±1,j±1 .

If n and m are even, we say that a cell (i, j) is even (resp. odd) if i + j is even (resp. odd). We say that the border between two cells is blue if the cells are even, and green otherwise; furthermore, we say that there is a diamond over cell (i, j) if its state does not coincide with even vertical stripes, i.e., if c ij = j mod 2; the diamond is blue if the cell is even and green otherwise (see Figure 5).

Proposition 1 (Borders are boundaries) The borders are the exact boundary of regions tiled with stripes patterns (odd/even horizontal/vertical). Moreover, when n and m are even, the blue (resp. green) borders are the exact boundary of the regions covered by the blue (resp. green) diamonds.

Proof: We first prove the second fact. Assume that n and m are even, and let us prove that blue borders are the boundary of the regions covered by blue diamonds. We say that two blue diamonds are neighbors if they are placed on diagonally neighboring cells. By definition, two even diagonally neighboring cells share a border iff they are in the same state, i.e., by definition, iff one is covered by blue diamond, and the other is not. It follows that the blue borders are exactly the boundary of the connected component of OTM511(M-Min) 16x32 (a = 0.000) T = 3.00 ( 1536 steps) E = 344 E Fig. 5: A typical 16 × 32 toric configuration after 3N fully asynchronous steps, with its blue and green borders and diamonds. Red and purple spots indicate active cells (purple is for cells with potential 3).

the blue diamonds, and the same holds for green borders and green diamonds. It follows that the regions delimited by the borders are of 4 types, depending if they are covered or not by blue diamonds and/or by green diamonds:

• diamond-free regions consist in even vertical stripes (c ij = j mod 2);

• regions covered by blue diamonds only consist in odd horizontal stripes (c ij = i + 1 mod 2);

• regions covered by green diamonds only consist in even horizontal stripes (c ij = i mod 2);

• regions covered by both blue and green diamonds correspond to odd vertical stripes (c ij = j + 1 mod 2). The result holds as well when n or m is odd, since duplicating the configuration along the odd dimensions yields an even size configuration with the same regions.

2

Since cells whose neighborhood is striped are inactive, the only active cells in a configuration may be found along the borders.

Energy

As in Ising model [START_REF] Mccoy | The Two-Dimensional Ising Model[END_REF] or Hopfield networks [START_REF] Rojas | Neural Networks: A Systematic Introduction[END_REF], we define a natural global parameter that one can consider to be the energy of the system since it counts the number of interactions between neighboring cells in the same state. This parameter will provide key insights on the evolution of the system.

Definition 6 (Potential)

The potential v ij of cell (i, j) is the number of its neighboring cells in the same state as itself minus 2. (i) By definition, if v ij 1, then the cell is in the minority state in its own neighborhood and is thus inactive (its state will not change when fired); whereas, if v ij 2 then the cell is active and its state will change if fired. Note that a configuration c is stable iff for all cell (i, j) ∈ U , v ij 1. Fact 2 When an active cell (i, j) is fired, its new potential is

v ij := 4 -v ij . Note that if v ij = 2, its potential remains unchanged.
Proof: By definition, an active cell with potential v has 8 -(v + 2) = 6 -v neighbors of the same state.

If the cell updates, its state flips and its new potential is

6 -v -2 = 4 -v. 2 Definition 7 (Energy) Let say that a subset of cells R is a fat if for each cell (i, j) ∈ R, there exists a 2 × 2 square Q included in R containing (i, j), i.e. such that (i, j) ∈ Q ⊆ R. The energy E R of set R in a given configuration is defined as: E R = (i,j)∈R v ij .
We denote by E the energy of the whole configuration c.

Simulation report on the evolution of the energy.

Figure 6 shows the decay of the energy with time obtained by averaging 100 trajectories (the plain red line together with its standard deviation, the two dotted red lines) starting from random 50 × 50 initial configurations. It also displays four trajectories leading to typically observed type of stable configurations. As in the von Neumann fully asynchronous dynamics analyzed in [START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority[END_REF][START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D minority[END_REF], we observe that after an initial drop (proved in Section 5.1), the energy slowly decays until a stable configuration is reached (typically of small energy and covered by stripes). Note that during the slow decay phase, the energy does not always decrease as the configuration evolves. Indeed, we will show in Section 5.2 that considering the energy is not enough to prove the convergence of the process. The following propositions (3, 4 and 5) give essential properties of the energy function.

The next proposition shows that the energy is non-negative for almost every subset of cells of a configuration. This means that there cannot be too many cells with negative potential. This implies that the decrease of energy over time (Proposition 4 and Theorem 9) is not due to the increase of the number of cells with negative potential, but to the decrease of the potentials of the cells with positive potential, which explains intuitively why the striped patterns which have minimum energy (Proposition 5) arise very rapidly.

Proposition 3 (Energy is non-negative) For any fat subset of cells R of size q: 0 E R 6q.

Proof: Since the potential of each cell is at most 6, clearly E 6N . Now, we rearrange the potentials locally within region R. Place an edge between any two neighboring cells in the same state. The potential of a cell is by construction its degree in the resulting graph minus 2. We now color the edges in blue or red. We say that three cells (i, j)-(i + , j)-(i, j + η), for some , η ∈ {1, -1}, form a L if there are all in the same state and if the cell (i + , j + η) is in the opposite state. Each L contains exactly 3 edges, two on the sides and one diagonal. All the edges are blue except the diagonals of each L which are paint in red.

An L with its red diagonal

The reassigned diagonal For each L, we reassign the extremities in R of its red edge to the cell (i + , j + η) (this may increase its degree by up to 2 depending on the number of extremities belonging to R before the reassignment). We can verify on Figure 8 that since every cell with potential 0 belongs to a square in R (R is fat), whatever this square is, the cell has degree at least 2 after reassigning the extremities of the red edges (even if the cell loses red edges during the reassignment). Consider now a cell with potential 1. Its degree decreases only if it gives at least one red edge to one of its neighbors. Since each cell has a blue edge (the side of the L) for every red edge, its degree could drop below 2 only if it owns two red edges sharing the same blue edge, but in that case, its potential would be exactly 1 and it would then have 5 neighbors next to each other in the opposite state from which it would receive at least one extremity of a red edge in R. It follows that after the reassignment, every node has degree 2 which implies that E R 0.

2

Cells with potential

v = -2

Cells with potential

v = -1 Cells with potential v = 0 degree 2 v 0 degree 2 v 0 degree 3 v 1 degree 4 v 2 degree = 2 v = 0 degree 2 v 0 degree 2 v 0 degree 2 v 0 degree 3 v 1
Fig. 8: The neighborhoods of cells with potential 0 and the reassigned red diagonal edges together with bounds on their new degrees and potentials after reassignment within a fat subset of cells.

The following easy fact will be very handy in order to prove the convergence of the dynamics.

Proposition 4 (Energy is non-increasing) Under fully asynchronous dynamics, the energy is a nonincreasing function of time and decreases each time a cell with potential 3 fires.

Proof: Let (i, j) be the cell fired at time t.

If v t ij 1, the configuration is unchanged. If v t ij
2, the state c ij changes and only the potentials of cell (i, j) and of its neighbors are affected:

v t+1 ij = 4 -v t ij
, and for the v t ij + 2 neighbors in the same state as (i, j) their potentials decrease by 1 and for the other 6 -v t ij neighbors their potential increase by 1. It follows that the overall energy varies by:

-v t ij + 4 -v t ij -(v t ij + 2) + (6 -v t ij ) = 8 -4v t ij 0 (< 0 if v t ij 3). 2
Striped configurations are stable and correspond to the minimum energy configurations.

Proposition 5 (Minimum energy configurations)

The energy of a configuration c is 0 iff c is a striped configuration.

Proof: Clearly, if c is a striped configuration, its energy is 0. Suppose now that c's energy is zero. Recall the edge reassignment given in the proof of Proposition 3: as illustrated in Figure 8, after reassigning the red edges, every node of non-positive potential has degree 3 if its neighborhood is not striped, and all the other nodes have degree 2. Since the energy is equal to the sum of the degrees minus 2N , it follows that if x denotes the number of cells with non-positive potential whose neighborhood is not striped, E x. Since E = 0, x = 0. Thus, all the cells have non-negative potential, and their potentials must sum up to zero; the only possibility left is thus that all the cells belong to a striped neighborhood which implies that c is striped.

Stable Configurations

As opposed to the von Neumann fully asynchronous dynamics in [START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority[END_REF], stable configurations under the Moore neighborhood exhibit rather complex structures as shown on Figure 9. Although there is a great variety of stable configurations, a common structure can be extracted and they can be characterized thanks to the borders. We first describe the stable configurations when n and m are even and deduce from there the structure of the stable configurations in the general case by doubling the odd dimension. Figure 10 gives examples of stable configurations of each type.

Theorem 6 (Stable configurations) When at least one of n and m is even, there are three types of stable configurations:

• Type I: the borders are parallel straight (diagonal) lines such that: two lines of the same color are at 1 -distance 4; the number of lines of each color along each row (resp., column) of the configuration has the same parity as m (resp., n).

• Type II: all the blue and green borders are all pairwise interlaced either horizontally according to the pattern , or vertically according to ; the pairs of interlaced borders are at 1 -distance 2 from each other; and the number of interlaced pairs has the parity of n if interlaced horizontally, and of m otherwise.

• Type III: the borders define a bicolor (horizontal/vertical stripes) underlying toric grid as in Figure 11(a) such that:

the segments of borders between two intersections are straight lines at distance at least 2 from each other; two borders of the same color cannot intersect;

H H' H' V V' V V' H H' V' V V' H V H' A C A' C A' B' C A A B' C A' B B' A' A H a 16
T = 0.00 ( 0 steps) E = 104 E H H' H' V V' H V' A' A' D A D D A D A V H' V' V H H V'
a 7 × 24 stable configuration of type III (odd height regions are highlighted in red) the number of borders of each color crossed by every row (resp. column) in the configuration has the same parity as m (resp. n); the borders of opposite colors intersect at the corners of the cells only (never at their centers), and always according to the (possibly overlapping) patterns given in Figure 11(b). Furthermore, no stable configuration can have both crossings of types C and D and if a region has a crossing of type C (resp., D ), all the crossings at the same vertical (resp., horizontal) level in the underlying grid are of type C (resp., D ); moreover, the number of such horizontal (resp., vertical) levels of C-(resp., D-) crossings equals the parity of m (resp. n).

Reciprocally, any n × m-configuration of type I, II or III is a stable configuration.

Proof: The proof consists in carefully enumerating the neighborhoods present in stable configurations, by enumerating first all the neighborhoods of inactive cells (see left part of Figure 12 below) and then extending these neighborhoods (numbered A1, B1-2, C1-6, and D1-10, see Figure 12), given that every cell has to be inactive, until either a contradiction is reached (an active cell is found, marked with a red cross) or until no more information can be inferred. The right part of Figure 12 presents the complete proofs of extension for each possible neighborhood. It follows that the only patterns that take part to a stable configuration are C5, C6, D2, D4, D5, D6, D8 and D10, listed on Figure 12. One can partition these surviving patterns in five categories:

• stripes: C6.

• infinite parallel lines wrapping around the torus: D2.

• straight segments of borders: C5 and D4.

H V H' V' A' H V H' V' Type H V H' V' ROT, SYM, 0/1 A Type H V H' V' B Type SYM, 0/1 ROT H V H' V' SYM, 0/1 B'
Type even number of turns (zero or more)

for each border odd number of turns (one or more) for each border

Potential v = -2 Potential v = -1 Potential v = 0 Potential v = 1 A1 B1 B2 C1 C2 C3 C4 C5 C6 D1 D2 D3 D4 D5 D6 D7 D8 D9 D10
Enumeration of the neighborhoods of inactive cells = neighborhood compatible with stable config.

... ... = active cell (incompatible with stable config.)

= neighborhood compatible with stable config.

= i th deduction assuming cell(s) under is (are) inactive i i Proofs of compatibility with stable configurations Fig. 12: Proofs of the enumeration of the neighborhoods compatible with a stable configuration (after symmetries).

• intersections of borders of opposite colors:

with vertical patterns on the sides and horizontal patterns on top and bottom: D5 and D6;

with horizontal patterns on the sides and vertical patterns on top and bottom: D10.

• interlaced green and blue borders: D8, which can only be combined with D10.

Now, there are three cases:

• There is no border intersection in the configuration: the only possible patterns are: Stripes (C6), straight lines (C5 and D4), and infinite parallel borders (D2). It follows that the borders of configuration consists in parallel lines as described in Type I in the theorem. Furthermore it is clear that any configuration verifying the conditions of Type I in Theorem 6 is stable.

• There is a horizontal (or vertical) line of interlaced borders of opposite colors: the only compatible patterns are thus: Stripes (C6) and interlaced borders (D8). Indeed, as we will see below, as soon as two borders intersect according to patterns D5, D6, or D10, the borders define a grid that cover the whole torus which is incompatible with a horizontal (or vertical) line of interlaced borders going across the configuration. It follows that, in that case, the configuration has to be of Type II as described in the theorem. Again, it is clear that any configuration satisfying the condition of Type II in Theorem 6 is stable (since it is made only of stable patterns).

• Two borders intersect: First, consider all the possible intersection types. Crossings D5 and D6, which consists of vertical patterns of opposite parity on the sides and horizontal patterns of opposite parity on top and bottom, are refered as A'-and A-crossings in the theorem; note that these two crossing do not change the orientation of the borders of each colors: their direction (NE-SW or NW-SE) is unchanged after an A(')-crossing. Now, we have to analyze the pattern D10. D10 can be combined with a chain of D8 patterns of arbitrary length (from 0 to the size of the configuration minus 2). If D10 is combined with an even number (possibly zero) of patterns D8, we obtain the crossings of types B and B' in the theorem, with horizontal pattern of opposite parity on the sides and vertical patterns of opposite parity on top and bottom; note that the direction of the borders of each colors is unchanged by crossing a B(')-crossing. Now, if D10 is combined with an odd number of patterns D8, we obtain a C-or a D-crossing whether if they are combined horizontally or vertically. C-and D-crossings differs from the other crossings on two important aspects: first, both borders take a ±90 • turn at this crossing; and second, as opposed to B(')-crossings, in C-crossing (resp., D-) the two horizontal (resp. vertical) patterns on the sides (resp. on top and bottom) have the same parity whereas the two vertical (resp., horizontal) patterns have opposite parity. Now, since borders go straight diagonally outside crossings, and since each crossing has 4 borders exiting from it in the four diagonal directions, if we forget about the color of the borders and merge the crossing into a single point, we conclude that the colorless borders of the configuration form a grid made of the parallel colorless borders heading NW-SE and parallel colorless borders heading NE-SW. Furthermore this grid structure has its faces labelled "horizontal" pattern or "vertical" as claimed in the theorem. Moreover, if there is a C-crossing in the configuration, since it is the only crossing which has horizontal patterns of the same parity on its side, all the crossing at the vertical of this crossing in the underlying grid have to be C-crossings. Furthermore, since the face on the top and bottom of a C-crossing are made of rows of cells of odd length (since borders extend diagonally, the length of a row varies by +2, 0 or -2 from one row to the next and its parity is preserved), the number of C-crossings at a given horizontal level of the underlying grid has necessarily the same parity as m. It also follows that if there is a C-crossing in the configuration, there will not be any D-crossing. The same holds with D-crossing by rotating the configuration. It follows that if a stable configuration is not of type I or II, it is of type III. And since a configuration of type III only contains stable patterns, such a configuration is necessarily stable.

This characterization allows to generate any stable configuration for the Moore Minority cellular automaton. It is remarkable that such a simple rule creates such sophisticated combinatorial structures. 2

Corollary 7 If n and m are odd, there exists no stable configuration; in particular, the dynamics never converges when n and m are odd.

Proof: Assume that n and m are both odd. Let us review the three types of stable configurations given in Theorem 6. Stable configurations of type II are impossible since it requires at least one even dimension so that the stripes wrap around. Stable configurations of type III are impossible since it would require both Cand D-crossings which are both incompatible. Now, consider by contradiction a stable configuration of type I. Since both dimension are odd, every border wraps around each dimension an odd number of times. Consider one horizontally-striped region delimited by two consecutive borders. It also has to wrap around each dimension an odd number of times. But since the parity of the stripes has to flip each time it wraps around the x-axis, the stripes cannot match together when it wraps around the y-axis (see Figure 13). 2 stripes mismatch , or the 8 × 8-pattern (see Figure 9). Proof: Since in a stable configuration all the cells are inactive, their potentials are at most 1 and E N . Proposition 5 gives the only configuration (after symmetries) of minimum energy 0 which is also stable. Now, consider stable configurations with maximum energy E = N . All cells must have potential 1, i.e. have exactly 3 neighbors of the same color as themselves. It follows that patterns C5 and C6 in Figure 12 are no more allowed and the configuration has to be tiled only by patterns D2, D4, D5, D6, D8 and D10.

• Consider a type I stable configuration of energy N . Since every border has to be at 1 -distance 4 from any other border of the same color, in order to avoid pattern C5, every border has to be next to a border of the opposite color (pattern D2). Furthermore, in order to avoid stripped pattern C6, two consecutive pairs of border of opposite color have to be at distance exactly 3 from each other, which yields to a configuration tiled by the 8 × 8-pattern .

• Consider now a type II stable configuration of energy N . In order to avoid striped pattern C6, every pair of interlaced borders of opposite colors has to be at 1 -distance exactly 2 from each other, yielding a configuration tiled by the 2 × 4-pattern .

• Consider now a type III stable configuration of energy N . Given the underlying grid in Figure 11( . Otherwise, the configuration only contains Acrossings (i.e. no A -crossings), and Figure 14(b) shows the chain of deductions demonstrating that the configuration is tiled by the 8 × 8-pattern (since the configuration does not contain any A -crossings, the four missing crossings at the border of Figure 14

Convergence analysis

In this section, we give our results on the existence and speed of the convergence of the dynamics towards a stable configuration from an arbitrary initial configuration. As opposed to the von Neuman dynamics study in [START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D minority[END_REF], we are here only able to describe the first steps and the last steps of the convergence because of the existence of particles following sophisticated guided random walks (see Section 3). These results rely on the study of the energy function which is combined with an other parameter to obtain a variant (Lyapunov function) which allows to reduce the study of the randomly evolving 2D shape (presenting a surprisingly sophisticated combinatorial structure) to an one-dimensional random walk. The section ends with challenging conjectures on the overall convergence of the process.

Initial energy drop

According to simulations (see Figure 6), the energy of a configuration drops very fast during the first steps and then slowly decays until a stable configuration is reached, most of the time a striped configuration of minimal or near-minimal energy. The following theorem provides a bound on the speed of the initial energy drop.

Theorem 9

The energy of any configuration of size N is at most N + 2N/3 after O(N 2 ) fully asynchronous minority updates on expectation.

Proof: First, if a configuration c has an energy E > 2N , there exists at least one cell with potential 3 and firing such a cell decreases the energy by at least 4. Moreover firing any cell with potential 2 does not change the energy. Since a cell with potential 3 is fired with probability 1/N , the energy decreases by at least 4 after at most O(N ) steps on expectation. Consequently the energy drops below 2N after at most O(N 2 ) steps on expectation.

Suppose now that N +2N/3 < E 2N , one cannot guarantee the existence of a cell with potential 3 any longer: either such a cell exists or all cells have a potential 2. In this latter case, one can prove the existence of a good pattern, namely two adjacent cells with potential 2 and in opposite states. Suppose the absence of such a pattern. Let b 2 (resp. b 1 ) be the number of black cells of potential 2 (resp. 1) and w 2 , w 1 be the same for white cells. Then consider a bipartite graph composed of the black cells with potential 2 on one side and of the white cells of potential at least 1 on the other side. We draw an edge between any pair of black and white cells if they are adjacent in the configuration. Each of the b 2 black cells is adjacent to 4 of the w 1 white cells. Conversely, each of the w 1 white cells is adjacent to at most 8 black cells. It follows that the number of edges drawn is at least 4b 2 and at most 8w 1 . Thus

4b 2 8w 1 . Symmetrically, 4w 2 8b 1 . It follows that N = b 1 + w 1 + b 2 + w 2 3(b 2 + w 2 )/2. But we have N + 2N/3 < E b 1 + w 1 + 2(b 2 + w 2 ) = N + b 2 + w 2 which yields 2N/3 < b 2 + w 2
and contradicts the previous inequality. Now that the existence of a cell of potential 3 or of two adjacent cells with potential 2 in opposite states is ensured, consider the following variant based on the energy: Ψ = 3E -N 3 , where N 3 is the number of cells of potential 3. It is bounded by 0 Ψ 6N . Let N 2,2 (resp. N 2,3 ) be the number of pairs of adjacent cells with potentials 2 (resp. potentials 2 and 3) in opposite (resp. identical) states, then the expected variation of E is -3 × 4N 3 /N and the expected variation of

N 3 is (N 3 - N 2,2 + N 2,3 )/N . Since N 2,3 8N 3 , the expected variation of Ψ is (-12N 3 + 9N 3 -N 2,2 )/N = (-3N 3 -N 2,2 )/N -2/N if E > N + 2N/3.
By applying a stopping time evaluation (see for instance [START_REF] Fatès | Fully asynchronous behavior of doublequiescent elementary cellular automata[END_REF][START_REF] Grimmet | Probability and Random Process[END_REF]), after at most O(N 2 ) steps on expectation, E drops below N +2N/3 or Ψ drops below N +2N/3 which also implies that E is below N + 2N/3. 2

The last steps of convergence

From now on, we assume that n and m are even. As mentioned above, in simulations, striped regions arise quickly, then extend, compete with each other, merge until only one covers the whole configuration. In this section, we provide an analysis of the very last steps of the convergence to this stable configuration: the case where there remains only one single horizontally striped region within a vertically striped background, which we will call a standard configuration (Definition 9). We then show that the background ends up covering the whole configuration in polynomial time on expectation. This involves studying the randomly evolving shape defined by the horizontal striped regions which presents a surprisingly sophisticated combinatorial structure.

Recall that every configuration is completely determined by its set of diamonds, which simply displays the difference of the configuration with an arbitrary imaginary striped background. When starting from what we call a standard configuration (Definition 9), we analyze how additions/deletions of diamonds occur and how the set of diamonds evolves. We decompose the evolving configuration into interacting islands (Definition 10) of green and blue diamonds and show that their boundaries extend from the hollows and are dug from the corners. Once disclosed the structure of the set of islands (valid configurations recursively described in Definition 11 and Figure 17), we analyze a combination of the energy with the area of the random shape, which is shown to decrease to 0 as the random set of diamonds tends to vanish. Interestingly enough, we show that the horizontally striped region can flip the parity of its stripes (see Figure 22) but cannot extend further than its initial surrounding rectangle (Definition 8). This reveals the impressive richness of the dynamics of fully asynchronous Minority, even in the (apparently) simplest initial situation.

Valid configurations

Definition 8 (Surrounding rectangles) A blue rectangle (resp. green rectangle) is a rectangle such that its sides are parallel to the diagonals and its corners are centered on odd (resp. even) cells. A blue or green rectangle is enclosing a set of diamonds D if all the diamonds are contained in the rectangle, and it is surrounding D if it is the smallest enclosing rectangle of that color for D (see illustration Figure 15). Definition 9 (Standard initial configuration) We say that a configuration is standard if it consists in a finite set of diamonds of the same color forming a rectangle (i.e., a set of diamonds of the same colors whose borders match its surrounding rectangle). See the initial configuration in Figure 22 for an example of standard configuration.

We will show that any standard configuration converges almost surely to the background configuration after a polynomial number of steps on expectation. Furthermore, we are able to describe recursively the structure of the configurations reachable from a standard configuration (valid configurations). This recursive definition allows to define a proper Lyapunov function for the process proving its convergence to the background configuration. This recursive description might be of particular interest in order to compute other global parameters such as the entropy of the system at any given time which might help understanding in deeper details the convergence process.

Definition 10 (Island) Two diamonds are neighbors if they are of the same color and at 1 -distance 2 of each other. A set D of diamonds is:

• connected if D is connected for the neighborhood relationship.

• convex if for all ∈ {1, -1} and for any pair of diamonds centered on cells (i, j) and (i + k, j + k) in D, the diamonds centered on cells (i + , j + ) for 0 k belong to D as well.

• an island if it is connected and convex.

Definition 11 (Valid configurations) A valid configuration or valid diamonds set is recursively defined as follows:

• a set of diamonds consisting of an island is a valid configuration,

• the composition of two valid diamond sets D 1 and D 2 enclosed by two rectangles R 1 and R 2 of some given colors laying next to each other according to the patterns given in Figure 16, is a valid configuration.

A configuration is valid if its corresponding set of diamonds is valid. Each valid configuration is recursively described by a construction tree: a binary tree where each leaf is an island and each internal node stands for a join operation whose two edges pointing to its children are labeled by the two, blue or green, joint rectangles enclosing the two valid diamond sets described by the left and right subtrees.

Note that two rectangles of different colors are not allowed to lay one on top of the other. Figure 17 gives an example of a valid configuration. Note that the rectangles used in the composition in steps 4 and 5 do not fit one into the other. However the rectangles can be resized such that two rectangles on a branch of the construction tree either fit one into the other if they have the same color or fit up to a one square shift if they have different colors (like in steps 3 and 4). A valid configuration can be represented by several construction trees. The next lemma gives a rule to rearrange construction trees (i.e. rearrange the sequence of joins). This will be handy for Proposition 14.

Lemma 10 (Corner lemma) Consider a valid configuration with a decomposition tree in which (see Figure 18):

• a rectangle R 3 is joint to several other rectangles into a rectangle R 1 ;

• R 1 and R 3 share the same east-corner on which lies a diamond (R 1 , R 3 and the diamond are thus all of the same color);

• R 1 is then joint from its east-corner to another rectangle R 2 .

Then, there exists a decomposition tree of the valid configuration which first joins R 2 and R 3 .

Proof: The proof is quite straightforward but requires careful handling. It proceeds in two claims. As illustrated in Figure 18, let K 1 = R 3 , . . . , K k+1 = R 1 be the sequence of rectangles enclosing the diamonds enclosed by R 3 in the decomposition tree, and L 1 , . . . , L k the sequence of rectangles to which they are joint to within R 1 according to some join operations from Figure 16.

Claim 10.1 Every K j rectangle touches or covers the north-east and south-east sides of R 3 and R 1 .

This claim holds simply because each the K j have to enclose the diamond at the east-corner of R 3 . Now, we can extend each of these rectangles K j to the north-east and south-east so that it encloses the diamonds enclosed in R 2 as well. Let us denote by K 1 , . . . , K k the resulting sequence of rectangles.

If R1 and R2 have the same color:

Simple joins:

R 1 R 2 R 1 R 2
Shifted joins:

R 1 R 2 R 1 R 2 R 1 R 2 R 1 R 2
If R2 consists of a diamond line of the same color as R1: Line joins: for all x in {0,...,(length (in diamonds) of the side of R1)-1}

R 1 R 2 x R 1 R 2 x R 1 R 2 x R 1 R 2 x

If R1 and R2 have opposite colors: Heterogenous joins:

Shifted heterogeneous joins:

R 1 R 2

The corners at the junction are both covered by a diamond matching the color of the corresponding englobing rectangle

R 1 R 2 R 1 R 2 R 1 R 2
Fig. 16: Valid combinations of valid configurations (the underlying cells of the automaton are shown at the junction of the rectangles). Note that two rectangles of different colors are not allowed to lay one on top of the other. Fig. 17: An example of a large valid configuration with one of its tree decompositions and its surrounding rectangles. Note that the rectangles used in consecutive steps of the composition do not necessarily fit one into the other, as in steps 4 and 5.

Claim 10.2 One can provide a valid construction of the diamonds enclosed in R 1 by first joining R 3 and R 2 and then joining L j to K j for j = 1, . . . , k. Furthermore these joins are exactly the same as the ones joining R 1 and R 2 , and L j and K j , respectively, with the exception that some Line join operations may have to be requalified Shifted joins and reciprocally in the cases shown in Figure 19: when the join operation occurs at the north-east or south-east border of R 1 , in which case rectangle L j might be (safely) truncated to a line-rectangle L j (Figure 19(b)).

The proof of the claim consists in remarking first that the join between R 1 and R 2 is in fact a join between R 3 and R 2 since they join at the corner. Thus, one can apply the exact same join between R 3 and R 2 (no need to requalify the join here). Second, remark that the area of rectangle R 1∪2 -(R 1 ∪ R 2 ) is diamondfree since the part of the configuration considered is the result of the join the diamonds in R 1 and R 2 . Thus each rectangle L j can safely be truncated to L j = L j ∩ * R 1 , where L j ∩ * R 1 denotes the largest rectangle of the same color as L j contained in both L j and R 1 . Now, recall that K j is the same sequence as K j except that it includes the diamonds in R 2 as well. The border in contact between each L j and K j is exactly the same as between L j and K j , thus the same join can be applied, with the exception that some line or shifted joins may have to be requalified in the cases shown on Figure 19. We have thus obtained a valid decomposition tree that constructs the diamonds in R 1 and R 2 by first joining R 3 and R 2 .

Corner Lemma

K j R 1 R 2 R 3 K j R 1∪2 R 1∪2 R 2 R 3 K j-1 R 1∪2 K j R 1 R 3 R 2 R 1 R 3 K j R 1∪2 R 2 K j-1 L j L j L 1 L j L j L j-1 Lj-1 L j-2 L k L j-1 L k
Fig. 18: Reorganization of the decomposition tree of a valid configuration by the Corner Lemma 10.

K j R 2 R 1 L j

No diamond here

No diamond here

K j R 3
(a) Requalifying the line join L j 1 K j to a shifted join

L j 1 K j K j R 2 L j L j R 1 R 3 K j

No diamond here

No diamond here (b) Requalifying the shifted join L j 1 K j to a line join L j 1 K j Fig. 19: The two cases where one need to requalify the join in Claim 10.2.

Closure of valid configurations

The set of valid configurations is closed under the fully asynchronous Minority dynamics. Since one single cell fires at each time step, each time an active cell is fired, one diamond is added or removed. Since there are horizontal stripes inside each island, the cells which are not at the border are inactive. All the deletions and additions of diamonds occur at the border. In the following, we will now focus on the diamond set and forget the underlying configuration, as mention before this is strictly equivalent. Let us now characterize the active cells in terms of diamonds. Let us start with two easy but handy facts.

Lemma 11 In a valid configuration, no diamond can lay on top of another diamond.

Proof: A diamond laying below another one is necessarily of the opposite color (its cell has the opposite parity). The only join operation (Figure 16) that places two diamonds of opposite colors next to each other is the heterogeneous joint and in that case the diamonds are one to the left of the other.

2

Note that the lemma above just says that no region is tiled with odd vertical stripes in a valid configuration.

Let us say that the NE-, E-, SE-, NW-, W-and SW-neighboring cells of cell (i, j) are the cells along the sides of the cell (i, j) and the N-and S-neighboring cells are the ones on top and below it.

Lemma 12 In a valid configuration, the potential v ij of cell (i, j) equals:

• 4 minus the number diamonds over its neighboring cells, if (i, j) holds a diamond;

• the number of diamonds over the cells along its sides minus the number of diamonds over the neighboring cells on top and below, otherwise;

Proof: By Lemma 11, if there is a diamond over (i, j), no diamond lies on top or above (i, j). In that case, the state of (i, j) mismatches the states of the cells above and below and matches the states of its cells along its sides unless they are covered by a diamond. Thus the number of its neighbors in the same state as itself is 6 minus the number of diamonds over its neighboring cells. Now, if the cell does not have a diamond, its state matches the state of the cells above and below unless they bear a diamond, and mismatches the one of the cells along its sides unless they bear a diamond. The result follows. 2

Proposition 13 In a valid configuration, there are exactly 13 kinds of active cells, after horizontal, vertical and black/white (ii) symmetries. (iii) These active cells are grouped in two categories in Figure 20: five adding cells that create a new diamond when fired, and height deleting cells that delete its diamond when fired.

Proof: Consider a deleting cell. This active cell is covered by a diamond and according to Lemma 12, its potential is 4 minus the number of diamonds placed over its cells along its sides. So there are at most (ii) The black/white symmetry is equivalent to flipping the green/blue color of each diamond, since it is equivalent to shift the background configuration by 1 to the left. (iii) 90 • rotations are not allowed since they would affect the background.

Deleting cells

Adding cells

Isolated

v = 4 v = 3                             
Fig. 20: The only actives cells after symmetries in a valid configuration (the red or purple spot indicates whether the center active cell has potential 2 or 3 respectively).

2 diamonds over these neighbors. This yields after symmetries the eight different kinds of deleting cells listed in Figure 20.

Consider an adding cell. W.l.o.g., assume that the cell is even (and thus that its diamonds would be blue). This active cell is not covered by a diamond and according to Lemma 12, its potential is the number of diamonds over its cells along its sides minus the number of diamonds over the cells above and below. Since the cell is active, the number of diamonds over its neighboring cells along its sides has thus to be at least 2 plus the number of diamonds above or below it. Moreover, since no diamond may lay one on the top of other in a valid configuration, there cannot be more than two diamonds along each side and necessarily of the same color (either one or two blue diamonds, or one green diamond). Furthermore, there cannot be more than two blue diamonds along the sides. Indeed, since the center cell is not covered by a diamond, no join operation in Figure 16 allows to join three or four blue diamonds placed along the sides: this would require a non-convex island, and the configuration would not be valid. This holds as well in presence of green diamonds on top or below. It follows that adding cells in a valid configuration have exactly two diamonds along its sides and no diamond on top or below. This yields after symmetries the five kinds of cells listed in Figure 20.

2

Proposition 14 (Closure) A valid configuration always yields a valid configuration after a minority update.

Proof: Each active cell is at the junction of one (isolated, peninsula, deleting and possibly adding corner, deleting bridge), two (heterogeneous bridge, possibly adding corner, adding bridge) or three (isolated bridge) islands. Since each of these joins has a diamond in the corner, one can consider by applying once or twice the corner lemma (Lemma 10) that these joins are the first made in the decomposition tree of the valid configuration. Figure 21 shows for each active cell, how one can modify locally the construction tree to demonstrate that the configuration remains valid whenever an active cell is fired.

It follows that valid configurations includes all the configuration reachable from a standard configuration. Figure 22 shows for instance a (unlikely) sequence of updates that flips the parity of the horizontal stripes of a rectangle, a phenomemon that could not be observed with the von Neumann neighborhood studied in [START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority[END_REF][START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D minority[END_REF]. It turns out that the reciprocal is false and some valid configurations may not be obtained from a standard configuration and Figure 23 exhibits such a configuration. It would be possible to characterize the exact set of the configurations reachable from a standard configuration by refining the heterogeneous join in Figure 16 (by imposing that a series of these joins occur as one single step) but this would have limited interest for us since the proof of convergence in the folowing section applies Time Fig. 22: Example of an horizontally striped region flipping its parity under asynchronous updates (very unlikely in simulation, still). to any valid configuration and thus holds on an even larger class than the only descendants of standard configurations.

R 3 R 3 R 1 R 2 R 2 R 1 R 3 R

Polynomial expected convergence time for standard configurations

Any cell with potential 3 is active and irreversible in the sense that firing this cell decreases the energy and thus this cell cannot switch back its state unless its neighborhood changes. The existence of irreversible active cell guarantees that the configuration progresses toward a fixed point since the energy decreases with probability Ω(1/N ) at each time step. We used this local argument to prove our bound on the initial energy drop. However, as soon as the energy is below the threshold N , stable configurations of that energy level exist, and the existence of irreversible active cells can no more be ensured. (iv) Indeed, in the simulations, one observes that the configuration goes thru long period of time where its energy remains constant (see for instance the long plateaus observed in the trajectories displayed in Figure 6). Through, during these long periods of the time where the energy remains unchanged, the configuration evolves by updating a lot of reversible cells that follows some kind of random walks along the borders until some of them meets and creates the necessary irreversible active cell that will allow to decrease the energy and step forward to a stable configuration. We need thus to quantify the evolution of the configuration during these long plateaus of the energy. It turns out that one can quantify the progress of the configuration during these periods by simply counting the number of diamonds of the configuration. Combining these two quantities, the energy and the number of diamonds, yields a proper variant (Lyapunov function) for

E[∆Φ] = E[∆Φ 1 ] + E[∆Φ 2 ] + δ -6/N + δ
where δ is the corrective term induced by the cells touching both configurations c 1 and c 2 after the join. Figure 24 reviews for each join operation which cells may have their contribution changed. • A simple join may create at most one adding isolated bridge and two adding corners, all other cells are unchanged. Thus, δ 3/N .

• A shifted join or a line join may create at most one adding bridge, all other cells are unchanged. Thus, δ 1/N .

• A shifted heterogenous join may create at most two adding heterogeneous bridges, all other cells are unchanged. Thus δ 1/N .

• Finally, an heterogeneous join may not create any new active cell. However, the activity of the two cells covered by a diamond at the corners of the join may change as follows. Before the join, each of them were either an isolated cell, a deleting corner or a deleting peninsula. Once the join is made, according to figure 20: if it was an isolated cell, then it becomes an heterogeneous peninsula; if it was a deleting corner, it becomes inactive; and if it was a (deleting) peninsula, it becomes a deleting heterogeneous bridge. It follows that the increase for the expected variation of the variant is δ 2/N .

It follows that in any case, E[∆Φ] -6/N + 3/N = -3/N . 2

We can now state the main theorem of this section. Example 1 Consider an initial configuration made of a rectangle of 2 × a blue diamonds. The expected convergence time is then at least aN because there are exactly 2 active cells on the smallest row of the rectangle at any time until only one row remains, event that requires at least a cells to be fired in the right order and thus at least aN time on expectation. It follows that the bound Θ(AN ) is tight up to some constant factor.

Conjectures

According to our simulations, all configurations converge to a stable configuration when n or m is even.

Unfortunately apart from the important but specific case detailed in Section 5.2, we have no proof of this result in the general case. One difficulty lies in the analysis of particles in the configurations presented in Section 3.

Conjecture 18

From any initial configuration c 0 , the dynamics converges to a stable configuration after at most 2N 3N +1 steps on expectation. Moreover when n and m are even, the convergence occurs on polynomial time on expectation.

The first statement is based on the following sequences of updates : I) as long as there are active cells without diamond, choose one of them and fire it; II) as long as there are active cells with a diamond on it, choose one of them and fire it. The idea is to apply repetitively these two sequences. We conjecture that after each of these sequences, the energy always decreases (with the exception of the very first sequence). As a consequence, the whole process should eventually yield a stable configuration. We furthermore conjecture that only three of these sequences are enough to reach to a stable configuration. It turns out that proving these results is quite challenging and requires a deep understanding of the global interactions between the so-called particles and the borders.

Conclusion

The behavior of 2D Minority with the Moore neighborhood under fully asynchronous dynamics is surprisingly rich and difficult to analyze. The approach of [START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority[END_REF] for the von Neumann neighborhood reveals to be useful here. However the analysis of the energy and of the competing regions requires a very accurate comprehension of the combinatorics emerging from this automaton. It turns out to be more complex for the Moore neighborhood. A key to complete the analysis seems to find the most appropriate definitions for particles and rails, in order to explain precisely how they evolve. One can impute some difficulties to properties of the neighborhood graph: the neighborhood relationship is bipartite in the case of von Neumann but no more in the case of Moore. In Ising models, the planarity of the underlying graph of spins also plays an important role in the difficulty to analyze the model [START_REF] Istrail | Statistical mechanics, three-dimensionality and np-completeness: I. universality of intractability for the partition function of the ising model across non-planar lattices[END_REF]. Understanding a simple rule like Minority is a key step in understanding more complex models based on cellular automata. The development of mathematical tools to predict the dynamics of such models appears as an essential complement to simulations.

Note that automatic tools could be developed to assist the construction of the proofs proposed here. One can easily interpret the proofs in Figures 12 and 14 as certificates that could be at least checked/drawn automatically and even maybe generated automatically as well. This would help a lot in handling the huge case enumerations that we have to face in order to find the right structure to analyze stochastic cellular automata. Note that the surprisingly complex structures emerging from such a "simple" dynamics as Moore Minority (cf., the structure of fixed points or the recursive structures of valid configurations) tells us that if automatic checker/drawer might be easily developed, generating automatically these proofs remains quite a challenge.

Our work here is mainly exploratory and consists in describing the kind of complex behavior one can observe in fairly simple 2D stochastic cellular automata. Clearly, the bounds we obtain are sometimes very loose, as the upper bound on the expected last of the initial energy drop which should rather be connected to some coupon collector process rather than a random walk. Finer probabilistic tools can then probably be considered to improve the analysis of this specific case. However for the slow convergence phase, understanding precisely the emerging combinatorial structure seems unavoidable and has revealed some interesting and challenging new random processes (the guided particles) that we believe to be worth to investigate on their own. Note that these particles are not specific to Minority but emerge in many other outer-totalistic automata (see for instance the outer-totalistic Moore automata OTM39, OTM105, OTM125, OTM244, or OTM229 [START_REF] Schabanel | Asynchronous outer-totalistic cellular automaton simulator[END_REF]). Sometimes these particles take very complex form such as bubbles of random noise, guided along the frontier between neighboring striped regions (see automata OTM244 and OTM229 [START_REF] Schabanel | Asynchronous outer-totalistic cellular automaton simulator[END_REF]). Understanding the precise behavior of these particles appears thus to be an important step in order to explore the behavior of even the simplest automata one may encounter in nature, as well as a very stimulating field of investigations.

  ) 48x48 (a = 0.000) T = 120.00 ( 276480 steps) E = 0

Fig. 3 :

 3 Fig. 3: A typical execution of stochastic 2D Moore minority with N = 48 × 48 cells.

  -A sequence of updates in a configuration starting with 4 particles where two of them move along rails and ultimately vanish after colliding with each other .4.b -A sequence of updates where the rails cannot sustain the pertubations due to the movements of the particles: at some point, rails get to close with each other, new active cells appear, and part of the rail network collapses .

Fig. 4 :

 4 Fig. 4: Some examples of the complex behavior of particles in a 20 × 20 configuration.

Fig. 6 :

 6 Fig. 6: Evolution of the energy function as time flies: in red, the mean energy with its error bars; in other colors (sky blue, marine blue, dark purple and green), four trajectories leading to typically observed stable configurations.

Fig. 7 :

 7 Fig. 7: The two extremities of the diagonal red edge in the L are locally reassigned to the vertex of the 2 × 2 pattern outside the L.

Fig. 9 :

 9 Fig. 9: Examples of stable configurations for 2D Minority at various levels of energy.

  × 32 stable configuration of type III (the columns (in the underlying grid) of odd width regions are highlighted in red) OTM511(Minority) 11x22 (a = 0.000) T = 0.00 ( 0 steps) E = 176 E an 11 × 22 stable configuration of type I OTM511(Minority) 11x22 (a = 0.000) T = 0.00 ( 0 steps) E = 176 E an 11 × 22 stable configuration of type II OTM511(Minority) 7x24 (a = 0.000)

Fig. 10 :

 10 Fig. 10: Examples of stable configuration illustrating most of the possibilities.

  Crossings between green and blue borders Straight (diagonal) blue or green borders (a) Underlying grid of Type III stable configurations / Region where each column of cells has an even/odd height and / (resp. and / ) denote horizontally (resp. vertically) striped region of identical/opposite parity / Region where each row of cells has an even/odd length

Fig. 11 :

 11 Fig. 11: Composition of Type III stable configurations (Theorem 6)

Fig. 13 : 8 × 8

 1388 Fig. 13: illustration of the proof of Corollary 7 on a 7 × 21 toric configuration.

8

 8 a) and since the only crossing with vertical region on the sides are Aand A -crossing (see Figure 11(b)), the configuration has at least one Aor A -crossing. If the configuration contains an A -crossing (pattern D5), then Figure 14(a) shows the chain of deduction demonstrating that the configuration is tiled by the 8 ×

  (b) have to be A-crossings). i the i-th deduction based on the fact that the cell(s) under the circle has exactly 3 neighboring cells of its own color i:Dk the i-th deduction based on the fact that pattern Dk is the only stable pattern matching the neighborhood of the cell(s) under the circle Chain of deductions for configuration with an A -crossing. Chain of deductions for configuration without A -crossing.

Fig. 14 :

 14 Fig. 14: Chains of deductions for Type III stable configurations of maximum energy (proof of Proposition 8).

Fig. 15 :

 15 Fig.15:A configuration with its blue and green surrounding rectangles (red and purple spots indicate active cells).

Fig. 21 :

 21 Fig. 21: A valid configuration yields a valid configuration after a minority update.

Fig. 23 :

 23 Fig.23: Example of a valid configuration that cannot be obtained from a standard configuration.

Fig. 24 :

 24 Fig. 24: Cells whose neighborhood may change are displayed in orange for each join operation. Red spots with question marks are drawn on the only possibly new active cells after each join operation.

Theorem 17 1 .

 171 Every valid configuration converges to the background configuration in finite time with probability The expected convergence time is O(A • N ) = O(N 2 ), where A is the number of diamonds covering the configuration initially (A N ). Proof: By Lemma 16, as long as the configuration is not the stable background configuration, E[∆Φ] -3 N . Since the only cells with non-zero potential are next to a diamond, E = O(A) and thus Φ = O(A). The stable configuration with vertical stripes is the only configuration with Φ 0. The process converges then in finite time to the background configuration with probability 1 and the expected convergence time is at most O(A • N ). 2

(i) The offset -2 is convenient since its ensures that the minimum energy of a configuration is zero (see Proposition 3 below).

(iv) This zone of energy N where stable and unstable configurations coexists is usually referred as glass phase in physics.

Acknowledgements

We would like to thank Philippe Flajolet and all the members of the ALEA community for the creation of the school ALEA that takes place every year at the CIRM (Luminy, France) and where we have learned a lot on probability theory in the best possible conditions.

valid configurations that decreases on expectation until a stable configuration is reached.

Among the 13 active cells encountered in valid configurations and listed in Figure 20, only three are irreversible and these are all deleting cells (i.e. erasing a diamond when fired): isolated, heterogeneous peninsula and peninsula cells. All the other active cells are reversible and every adding cell has thus his deleting pendant. Intuitively, this bias explains that reversible cells follow some kind of random walks until some irreversible cell emerges. Let us now prove how the random walks of reversible cells along the borders irremediably conducts to the emergence of irreversible ones.

The variant. Let A be the number of diamonds in the valid configuration. Let Φ = A + E/4 be the variant associated to a valid configuration. Let us denote by E[∆Φ] the expected variation of Φ for the configuration after a fully asynchronous minority update.

The variation of Φ is totally determined by the active cells:

• adding and deleting active cells contribute by +1/N and -1/N each respectively to E[A];

• active cells of potential 2 do not contribute to E[E/4] since firing them leaves the energy unchanged;

• active cells of potential 3 (peninsula and heterogeneous peninsula cells, see Proof: The argument is similar to [START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D Minority[END_REF][START_REF] Regnault | Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D minority[END_REF]. If the island consists in one single (isolated) cell, then E[∆Φ] = -1/N -2/N = -3/N . Now, consider an island with two or more diamonds. Its only active cells are (deleting) peninsulas, (adding or deleting) corners and deleting bridges. The energy is only affected by peninsulas which decrease it by -4 if fired. Each deleting bridge contributes by -1/N to E[∆Φ] and can thus be safely ignored. it follows that:

where the angles are considered along the perimeter of the island. The last equality follows from the fact that for polyominoes the difference between the number of salient and reflex angle is exactly 4.