Laure Marêché

FIXATION FOR U-ISING AND U-VOTER DYNAMICS WITH FROZEN VERTICES

Keywords: Primary 60K35; Secondary 82C20, 82C22, 60J27 U-Ising dynamics, U-voter dynamics, fixation, frozen vertices, universality classification, zero-temperature stochastic Ising model, voter model, bootstrap percolation

Fixation for U-Ising and U-voter dynamics with frozen vertices

Laure Marêché

Introduction

The voter model is a statistical mechanics model introduced by Holley and Liggett in [START_REF] Holley | Ergodic theorems for weakly interacting infinite systems and the voter model[END_REF], which can represent the evolution of the opinion of a population of individuals which are influenced by their neighbors, and tend to change their opinion to agree with them. In the most basic form of the voter model, individuals are represented by vertices of the graph Z d , d ∈ N * , called sites. Each site can have one of two opinions, called states, which we denote by + and -, and each site, at rate 1, chooses randomly the state of one of its 2d neighbors and adopts it. This model is simple, yet interesting, and it received a lot of attention (see [START_REF] Thomas | Stochastic interacting systems: contact, voter and exclusion processes, volume 324 of Grundlehren der mathematischen Wissenschaften, A series of comprehensive studies in mathematics[END_REF], especially the Notes and References part).

A closely related model is the zero-temperature stochastic Ising model, a special case of the famous stochastic Ising model, which describes the behavior of a magnetic material. In the zero-temperature stochastic Ising model, each vertex of Z d can be either at state + or at state -, and tries to agree with its neighbors, but the dynamics is different. A site will change state at rate 1 if more than d of its neighbors have the opposite state, at rate 1/2 if exactly d of its neighbors have the opposite state, and will never change state otherwise. This model was also studied a lot (see the review in Section 5 of [START_REF] Morris | Monotone cellular automata in Surveys in combinatorics[END_REF], as well as [START_REF] Hubert Lacoin | Zero-temperature 2D stochastic Ising model and anisotropic curveshortening flow[END_REF] and the references within it).

One of the most important questions about the zero-temperature stochastic Ising model is that of fixation. For a given site, is there a time after which it remains forever in state + (or -), in which case we say it fixates at + (respectively at -) at this time? Or is there always a later time at which the site changes state, in which case it is called a flipper ? If all vertices are initially independently at + with some probability p ∈ (0, 1), in dimension 1 the results of Arratia [START_REF] Arratia | Site recurrence for annihilating random walks on Z d[END_REF] prove that almost surely all sites are flippers. However, in higher dimension, the problem is harder. It is conjectured that for d ≥ 2, if p = 1/2 almost surely all sites are flippers, and if p > 1/2 almost surely all sites fixate at + (since the model is symmetric, this would imply that for p < 1/2 almost surely all sites fixate at -), but this conjecture is far from proven. Almost sure fixation at + for all sites was only proven for p close to 1, by Fontes, Schonmann and Sidoravicius [START_REF] Luiz | Stretched exponential fixation in stochastic Ising models at zero temperature[END_REF], and the fact that almost surely all sites are flippers for p = 1/2 was proven only in dimension 2, by Nanda, Newman and Stein [START_REF] Nanda | Dynamics of Ising spin systems at zero temperature[END_REF].

In order to understand better the zero-temperature stochastic Ising model, Chalupa, Leath and Reich [START_REF] Chalupa | Bootstrap percolation on a Bethe lattice[END_REF] introduced another model they called bootstrap percolation. In bootstrap percolation, any site of Z d can be either healthy or infected, infected sites ramain infected, and a healthy site becomes infected when it has at least a given number r of infected neighbors. Bootstrap percolation is very helpful in the study of the zero-temperature stochastic Ising model, because it can be seen that the vertices that can be put at + in the latter are those that can be infected by the former when r = d and the initial infected sites are the sites initially at +. Bootstrap percolation turned out to be very interesting in itself, and a lot of work was done on it (see Sections 2 to 4 of [START_REF] Morris | Monotone cellular automata in Surveys in combinatorics[END_REF] for a review).

A natural generalization of bootstrap percolation is the following, often called U-bootstrap percolation. An update family on Z d will be a collection U = {X 1 , ..., X m } such that m ∈ N * and for each i ∈ {1, ..., m}, X i is a finite nonempty subset of Z d \ {0}. The X i , i ∈ {1, ..., m} are called update rules. Let U be such an update family, it allows us to define the following U-bootstrap percolation dynamics. Each site of Z d can still be either healthy or infected, and sites change state in discrete time according to the following rules: for each t ∈ N * , a site that was infected at time t -1 remains infected at time t, and a site x that was healthy at time t -1 is infected at time t if and only if there exists X ∈ U so that all sites of x + X were infected at time t -1. The bootstrap percolation with r neighbors is the U-bootstrap percolation dynamics corresponding to U = {sets of r neighbors of the origin}.

The diversity of the possible update families makes U-bootstrap percolation hard to study. However, Balister, Bollobás, Duminil-Copin, Morris, Przykucki, Smith and Uzzell, in their impressive works [START_REF] Balister | Subcritical U-bootstrap percolation models have non-trivial phase transitions[END_REF][START_REF] Bollobás | Universality of two-dimensional critical cellular automata[END_REF][START_REF] Bollobás | Monotone cellular automata in a random environment[END_REF], were able to establish a universality classification of the two-dimensional update families, dividing them into supercritical, critical and subcritical families and characterizing the behavior of U-bootstrap percolation for each class of update families. Later, Balister, Bollobás, Hartarsky, Morris, Smith and Szabó [START_REF] Balister | Universality for monotone cellular automata[END_REF][START_REF] Balister | Subcritical monotone cellular automata[END_REF][START_REF] Balister | The critical length for growing a droplet[END_REF][START_REF] Hartarsky | Subcritical bootstrap percolation via Toom contours[END_REF] proved a similar classification in higher dimension. The update family corresponding to the bootstrap percolation with d neighbors, hence to the classical zero-temperature stochastic Ising model, belongs to the critical class.

In light of this understanding of U-bootstrap percolation, Morris [START_REF] Morris | Bootstrap percolation, and other automata[END_REF] introduced generalizations of the voter model and of the zero-temperature stochastic Ising model in the spirit of U-bootstrap percolation, called U-voter dynamics and U-Ising dynamics. These models are Markov continuous-time dynamics in which each vertex of Z d can be either in state + or in state -. Independently for each x ∈ Z d , we consider a Poisson point process with intensity 1, called the clock at x. When the clock at x has a point at some t, we say the clock at x rings at time t. The U-Ising dynamics is then defined as follows (the definition introduced in [START_REF] Morris | Bootstrap percolation, and other automata[END_REF] was slightly different, but it is equivalent): for each x ∈ Z d , when the clock at x rings, if there exists X ∈ U so that all sites in x + X have the state opposite to the state of x, then x flips its state to agree with them; otherwise, nothing happens. The U-voter dynamics is defined thus: for each x ∈ Z d , when the clock at x rings, an update rule X ∈ U is chosen uniformly at random. If all sites in x + X are in the same state and disagree with the state of x, x changes its state to agree with them, otherwise nothing happens. The fact that these dynamics are well defined is not obvious, but is classical, and one can use the arguments in part 4.3 of [START_REF] Swart | A course in interacting particle systems[END_REF] to prove it.

The question of fixation in the U-Ising and U-voter dynamics was asked by Morris in [START_REF] Morris | Bootstrap percolation, and other automata[END_REF], but even less is known about it than about fixation in the classical zero-temperature stochastic Ising model. The only work in this direction is that of Blanquicett [START_REF] Blanquicett | Fixation for two-dimensional U-Ising and U-voter dynamics[END_REF], which showed that for some two-dimensional critical update families, if sites are initially independently at + with a probability close enough to 1, then almost surely all sites fixate at +. Obtaining results about fixation for all update families is expected to be even harder than for the classical zero-temperature stochastic Ising model.

In this paper, we tackle a fixation problem which was solved for the zero-temperature stochastic Ising model and study it for the U-Ising and U-voter dynamics. This question is that of fixation with frozen vertices. A dynamics with frozen vertices is defined as follows. Let ρ + , ρ -≥ 0 be so that ρ + + ρ -< 1. Sites of Z d will independently be frozen at + with probability ρ + , frozen atwith probability ρ -, and unfrozen with probability 1 -ρ + -ρ -. The initial states of the unfrozen sites are then defined according to a distribution µ, which may depend on the choice of the frozen vertices. The dynamics is then run as explained above, with clocks and choices of update rules independent from the choice of frozen vertices and the initial states, with the difference that frozen vertices cannot change state and always remain in the state they are frozen at.

The classical zero-temperature stochastic Ising model with frozen vertices on Z d was studied by Damron, Eckner, Kogan, Newman and Sidoravicius in [START_REF] Damron | Coarsening dynamics on Z d with frozen vertices[END_REF] (see also [START_REF] Damron | Coarsening with a frozen vertex[END_REF], where a dynamics with a single frozen vertex is considered). They proved that if ρ + > 0 and ρ -= 0 (no sites frozen at -), even if the probability that a site is frozen at + is very small and for any initial states of the unfrozen sites, almost surely all sites fixate at +. They also showed that for any ρ + > 0, if ρ -is small enough, the connected components of sites that do not fixate at + (that is flippers and sites that fixate at -) are almost surely finite. This is in contrast with the dynamics without frozen vertices, for which [START_REF] Luiz | Stretched exponential fixation in stochastic Ising models at zero temperature[END_REF] implies that all sites fixate atif the initial probability that a site is frozen at + is small enough.

In this work, we generalize the results of [START_REF] Damron | Coarsening dynamics on Z d with frozen vertices[END_REF] and improve on them in both the U-Ising and the U-voter dynamics. In the two-dimensional case, we managed to extend the findings not only to the class of dynamics which can be expected to behave like the classical zero-temperature stochastic Ising model, that is those with critical update families, but also to all those with subcritical update families and some with supercritical update families. We first prove that if ρ -= 0, almost surely all sites fixate at + (Theorem 5). Moreover, we show that if ρ -is small enough, there exists a deterministic time so that sites that have not fixated at + at this time form finite connected components (Theorem 7). This result is new even for the classical zero-temperature stochastic Ising model, and highlights the difference with the dynamics without frozen sites, since Camia, De Santis and Newman [START_REF] Camia | Clusters and recurrence in the two-dimensional zero-temperature stochastic Ising model[END_REF] proved that for the zero-temperature stochastic Ising model without frozen sites, at any time the connected components of + are finite almost surely. Finally, we study the possible existence of flippers. In the zero-temperature stochastic Ising model, if ρ -> 0 it is not hard to see, as [START_REF] Damron | Coarsening dynamics on Z d with frozen vertices[END_REF] did, that there is almost surely an infinite number of flippers. However, this is not the case for all update families. We were able to establish a universality classification sorting the update families into two classes so that if the update family belongs to the first class there is almost surely an infinite number of flippers, but if it belongs to the second class, when ρ -> 0 is small enough, almost surely there is no flipper (Theorem 9). We also deal with the one-dimensional case, which is simpler but not trivial, and prove similar results (Theorems 2 and 3).

The proofs rely partly on the important idea already present in [START_REF] Damron | Coarsening dynamics on Z d with frozen vertices[END_REF] that if a suitably chosen polygon has sites frozen at + around its corners, once the polygon is filled with + by the dynamics, all the vertices inside have fixated at +. However, this only works for non-supercritical update families, and even then the implementation of this idea is notably more difficult and technical that in [START_REF] Damron | Coarsening dynamics on Z d with frozen vertices[END_REF] because of the great variety of the update families. Dealing with supercritical update families and proving there are no flippers for a portion of the update families requires entirely novel arguments, outlined in Section 2.3.

This work unfolds as follows. We begin in Section 2 by giving more notation, stating the results and sketching the proofs. Section 3 contains the construction of the polygons used for the non-supercritical update families. In Section 4, we prove that the probability a given region of Z 2 is susceptible of fixating easily at + is high. In Section 5 we show our fixation results in the two-dimensional case (Theorems 5 and 7). In Section 6 we determine which two-dimensional update families exhibit flippers (Theorem 9). Finally, in Section 7 we deal with the one-dimensional case (Theorems 2 and 3).

Notation and results

Since the one-dimensional case is the simplest one, we begin by spelling out our results for this case, in Subsection 2.1. We then state our two-dimensional results in Subsection 2.2. In Subsection 2.3, we give an outilne of our proofs. Finally, in Subsection 2.4 we gather some notation that will be used throughout the paper.

2.1. One-dimensional case. This case is much simpler than the two-dimensional one, but it still demands some arguments. One first needs to see the connection between the U-Ising and U-voter dynamics and the U-bootstrap percolation with the same update family. One can see by recursion that each site that can be at state + at some time in the U-Ising or U-voter dynamics can be infected by the U-bootstrap percolation with initially infected sites the sites initially at state +. Indeed, if a site x switches its state to +, there is an update rule X so that the sites of x + X were at + before the switch. Therefore, for fixation at + to be possible for all sites of Z, this U-bootstrap percolation process must be able to infect all sites in Z, and this depends on the properties of the update family. One-dimensional update families are classified as follows.

Definition 1. A one-dimensional update family U is called • supercritical if there exists X ∈ U so that X ⊂ N * or X ⊂ -N * ; • subcritical otherwise.
If the update family is subcritical, the U-bootstrap percolation process is unable to infect all sites of Z, since when we have a large interval of initially healthy sites, no site of this interval can be infected. Consequently, for subcritical update families, the U-Ising and the U-voter dynamics will be unable to put at + all sites of Z. We thus study fixation at + only for supercritical update families. If there are no sites frozen at -, we were able to prove that fixation at + occurs for all sites of Z, which is the following result.

Theorem 2. If U is a supercritical one-dimensional update family, in the U-Ising and the U-voter dynamics, if 0 < ρ + < 1 and ρ -= 0, for any choice of initial distribution µ, almost surely all sites fixate at +.

If there are sites frozen at -, one cannot expect fixation at + for all sites of Z. However, it is not a priori obvious whether there will be flippers that change state an infinite number of times, or if all sites end up fixating either at + or at -. This actually depends on the update family, and we were able to show the following universality classification which describes the possible behaviors and is valid for both subcritical and supercritical update families. Theorem 3. If U is a one-dimensional update family, in the U-Ising and the U-voter dynamics, if 0 < ρ + < 1 and 0 < ρ -< 1 -ρ + , for any choice of initial distribution µ, there are two possible cases:

• if U contains two disjoint update rules, almost surely there is an infinite number of flippers;

• if U contains no disjoint update rules, almost surely there is no flipper.

2.2. Two-dimensional case. This case is much more complex than the one-dimensional case, in part because update families are more diverse. In order to state our results, we need to explain the classification of the two-dimensional update families introduced in [START_REF] Bollobás | Monotone cellular automata in a random environment[END_REF] by Bollobás, Smith and Uzzell. Let U be an update family on Z 2 . We denote ⟨•, •⟩ the scalar product on R 2 . For any direction u ∈ S 1 , for any a ∈ R, we define

H u = {x ∈ R 2 : ⟨x, u⟩ < 0} as the open • • × 0 {(-1, 0), (-1, 1)} • • × 0 {(-1, 0), (-1, -1)} Figure 1.
A two-dimensional supercritical update family with no disjoint update rules: U = {{(-1, 0), (-1, 1)}, {(-1, 0), (-1, -1)}}. The bullets represent the sites contained in the update rules.

half-plane opposed to u. We say u is a stable direction for U when there exists no X ∈ U so that X ⊂ H u ; otherwise u is called unstable. We then have the following. As in the one-dimensional case, a site can be put at + by the U-Ising or the U-voter dynamics only if it can be infected in the U-bootstrap percolation with initially infected sites the sites initially at +. Moreover, it was proven in [START_REF] Balister | Subcritical U-bootstrap percolation models have non-trivial phase transitions[END_REF] by Balister, Bollobás, Przykucki and Smith that if U is subcritical, there exists q c (U) > 0 so that if sites are initially independently infected with probability q < q c (U), then the U-bootstrap percolation is unable to infect all sites of Z 2 . Therefore we do not study subcritical models if the probability ρ + that a site is frozen at + is smaller than q c (U). Actually, technical reasons prevent us to prove our results for all ρ + > q c (U), so, like many results for subcritical update families, ours will hold for ρ + > qc (U), where qc (U) ≥ q c (U) was introduced by Hartarsky in [START_REF] Hartarsky | U-bootstrap percolation: critical probability, exponential decay and applications[END_REF] and is conjectured to be equal to q c (U) (its exact definition can be found in equation ( 4) of [START_REF] Hartarsky | U-bootstrap percolation: critical probability, exponential decay and applications[END_REF]). When there are no sites frozen at -, we have the following result of fixation at + for all sites of Z 2 . Theorem 5. Let U be a two-dimensional update family. In the U-Ising and the U-voter dynamics, if one of the following holds: U is supercritical, contains no disjoint update rules and 0 < ρ + < 1, or U is critical and 0 < ρ + < 1, or U is subcritical and qc (U) < ρ + < 1, then if ρ -= 0, for any choice of initial distribution µ, almost surely all sites fixate at +. Remark 6. There are a number of non-trivial supercritical update families with no disjoint update rules, for example U = {{(-1, 0), (-1, 1)}, {(-1, 0), (-1, -1)}} (see Figure 1). For the other class of supercritical update families, those containing two disjoint update rules, it is not clear whether fixation occurs. Indeed, as proven in Section 5.3 of [START_REF] Bollobás | Monotone cellular automata in a random environment[END_REF], one can find a finite set of sites which, if initially infected, allows the U-bootstrap percolation dynamics to propagate the infection to an infinite number of sites. Therefore, even if there is only a finite set of sites atin the U-Ising or the U-voter dynamics, this dynamics can potentially propagate theto an unlimited number of sites, by switching tothe sites that get infected in the order they get infected (see Remark 13 for a more detailed construction).

Except when mentioned otherwise, connectedness will be connectedness for the usual graph structure of Z 2 . When the probability ρ -that a site is frozen atis small, we were able to prove the existence of a deterministic time after which the connected components of sites that have not yet fixated at + are finite.

Theorem 7. Let U be a two-dimensional update family. In the U-Ising and the U-voter dynamics, if one of the following holds: U is supercritical, contains no disjoint update rules and 0 < ρ + < 1, or U is critical and 0 < ρ + < 1, or U is subcritical and qc (U) < ρ + < 1, then there exists ρ - 0 = ρ - 0 (U, ρ + ) > 0 so that for any 0 ≤ ρ -≤ ρ - 0 , for any choice of initial distribution µ, there exists a deterministic time T = T (U, ρ + ) < +∞ such that almost surely for any t ≥ T , the connected components of sites that have not fixated at + at time t are finite.

Remark 8. This cannot hold in the one-dimensional setting, since a singleis enough to break the connexity, and for any time there is a positive probability that a site initially athas not yet received a clock ring allowing it to switch to + before this time.

Theorem 7 means that "most" sites fixate at +, but does not imply all sites fixate at +. If ρ -> 0, we can expect some sites not to fixate at +, but it is not obvious whether there will be flippers. We were able to answer this question and to establish a universality classification of the update families describing the possible behaviors, which is the following.

Theorem 9. Let U be a two-dimensional update family. In the U-Ising and the U-voter dynamics, if one of the following holds: U is supercritical, contains no disjoint update rules and 0 < ρ + < 1, or U is critical and 0 < ρ + < 1, or U is subcritical and qc (U) < ρ + < 1, then for 0 < ρ -≤ ρ - 0 , for any choice of initial distribution µ, there are two possible cases:

• if U contains two disjoint update rules, almost surely there is an infinite number of flippers;

• if U contains no disjoint update rules, almost surely there is no flipper.

Remark 10. The U-Ising and U-voter dynamics are symmetric with respect to + and -, therefore similar theorems hold with the roles of + andreversed.

Remark 11. The results of [START_REF] Damron | Coarsening dynamics on Z d with frozen vertices[END_REF] for fixation in the classical zero-temperature stochastic Ising model with frozen vertices are also valid in dimension d ≥ 3, and a universality classification was proved for U-bootstrap percolation in dimension d ≥ 3, by Balister, Bollobás, Hartarsky, Morris, Smith and Szabó [START_REF] Balister | Universality for monotone cellular automata[END_REF][START_REF] Balister | Subcritical monotone cellular automata[END_REF][START_REF] Balister | The critical length for growing a droplet[END_REF][START_REF] Hartarsky | Subcritical bootstrap percolation via Toom contours[END_REF]. As in the two-dimensional case, update families are sorted according to the structure of the set of their stable directions, which are defined similarly, but with half-spaces instead of half-planes. Despite this, our arguments cannot be extended to higher dimension, even for update families in the same class as that of the classical zero-temperature stochastic Ising model. Let us explain why in the three-dimensional case. In this case, the update family corresponding to the zero-temperature stochastic Ising model is U = {sets of 3 neighbors of the origin}. For this update family, a cube filled with + whose corners are frozen at + has fixated at +, and this fact is the core of the argument of [START_REF] Damron | Coarsening dynamics on Z d with frozen vertices[END_REF]. However, if one adds to this update family the update rule {(1, -1, 0), (-1, 1, 0)}, then the set of stable directions remains the same, but one can see that the sites on the vertical edge of the cube with maximal abscissa and ordinate may switch toeven if the cube is filled with +. Therefore even complete knowledge of the set of stable directions is not enough. This suggests that the question of fixation in higher dimension may be much more complex than in the two-dimensional case.

2.3.

Outline of the proofs. We first explain the arguments used for the two-dimensional case. Their cornerstone is finding regions of Z 2 so that once the dynamics fills the region by chance, all sites in the region have fixated at +. For the classical zero-temperature stochastic Ising model, this was accomplished in [START_REF] Damron | Coarsening dynamics on Z d with frozen vertices[END_REF] by noticing that if a square has its four corners frozen at +, once the square is filled with +, all its sites have fixated at +. We extend this idea not only to critical update families (the class corresponding to the classical zero-temperature stochastic Ising model), but also to subcritical update families, by constructing a polygon such that if its "enlarged corners" are made of sites frozen at +, once the polygon is filled with +, all its sites have fixated at +. This is done in Section 3. For supercritical update families, it is impossible to construct such a polygon (see Remark 13), hence we need a new mechanism. For this, we notice that if there are no disjoint update rules, when a site x is put at +, there exists X ∈ U so that x + X is made of sites at +. As long as x + X is at +, for any X ′ ∈ U, since X and X ′ are not disjoint, x + X ′ contains at least a site of x + X, so x + X ′ is not entirely at -, thus x cannot be put atbefore one of the + of x + X disappears. Therefore a site x that is put at + thanks to sites x + X frozen or fixated at + will fixate at +, and fixation at + will propagate from the frozen sites. Thanks to these arguments, if the configuration of frozen sites is favorable, we can construct regions whose sites fixate at +. This will allow us to prove our fixation results, which is done in Section 5. Indeed, we can show that the probability that the configuration of frozen sites is favorable is so high (Proposition 16) that most of Z 2 will be favorable. Most of Z 2 thus fixates rather quickly, which allows to find a deterministic time T such that the connected components of sites that have not fixated at + at time T are finite, which is Theorem 7. We even obtain a slightly stronger result (Theorem 18), which yields that after time T , the dynamics only evolves on finite connected components isolated from each other by sites that have fixated at +. If ρ -= 0, once by chance the dynamics has filled one of these components with +, none of its sites can ever filp toanymore, which allows to prove almost sure fixation at + for all sites (Theorem 5).

Proving Theorem 9 about the existence of flippers requires an additional novel argument, given in Section 6. If there are two disjoint update rules X and X ′ and if ρ -> 0, it is easy to see there will be an infinite number of flippers, since a site x with x + X frozen at + and x + X ′ frozen atwill be a flipper. However, proving that there is no flipper if there are no disjoint update rules is more complex. To do this, we consider the dynamics in each of the aforementioned finite connected components. Then we craft events such that if one of these events occurs, all sites in the component have fixated at +, and prove that almost surely one of these events will occur sooner or later.

In the one-dimensional case, the arguments are similar, but simpler. Indeed, one does not need to construct regions which, once filled with + by the dynamics, have fixated at +. Instead, we notice that there is an infinite number of large intervals of sites frozen at +, and that their complement is composed of finite connected components that cannot interact with each other. Once we make this observation, the arguments that prove Theorems 5 and 9 allow to prove Theorems 2 and 3, which is done in Section 7.

2.4. Notation. We gather here some notation which will be used throughout the paper. For any set A, we denote by |A| the cardinal of A. We recall that ⟨•, •⟩ is the scalar product on R 2 . ∥.∥ 2 will denote the Euclidean norm on R 2 , and we will use the distance on R 2 associated to it. We denote also by ∥.∥ ∞ the sup norm. For any direction u ∈ S 1 , for any a ∈ R, we denote H u (a) = {x ∈ R 2 : ⟨x, u⟩ < a} the translation of the open half-plane H u by a, and Hu (a) = {x ∈ R 2 : ⟨x, u⟩ ≤ a} the corresponding closed half-plane.

Except in Section 7, U will be an update family on Z 2 . We assume U is either non-supercritical, or supercritical and contains no disjoint update rules. Since qc (U) can also be defined for supercritical and critical update families and is 0 for them (see Theorem 3.1 of [START_REF] Hartarsky | U-bootstrap percolation: critical probability, exponential decay and applications[END_REF]), we will often write "ρ + > qc (U)" as a more compact way to write "ρ + > 0 if U is supercritical and contains no disjoint update rule or if U is critical, and ρ + > qc (U) if U is subcritical". We define a constant r = r(U) = max{∥x∥ 2 | x ∈ X, X ∈ U} which represents the range of U. From now on, the U-bootstrap percolation with respect to the update family U will simply be called "bootstrap percolation". We also define bootstrap percolation on a domain D ⊂ Z 2 , which will always have healthy boundary conditions: the dynamics is the same as the U-bootstrap percolation dynamics explained in the Introduction, except that sites in Z 2 \ D remain always healthy. We notice that the bootstrap percolation dynamics is monotone: if one starts the dyamics with more infected sites, at any later time there will be more infected sites.

In the remainder of this paper, we will work with the U-voter dynamics, since the arguments for the U-Ising dynamics are similar and simpler. If at some time a given site is at + (respectively at -) and it is impossible for it to switch to -(respectively to +) again without having two clocks ring at the same time (which has probability 0), we say the 0 site is well fixed at + (respectively at -) at this time. Almost surely, once a site is well fixed, it has fixated. For all t ≥ 0, we denote by F t the σ-algebra of everything that happens in the dynamics up to time t, including the initial states of the sites and which sites are frozen.

D(a) a u 1 u 2 u 3 0 D ′ (a) a u 1 u 2 u 3

Non-supercritical update families: good droplets

In this section, we assume the update family U is not supercritical. The section is devoted to the construction of a polygon so that if its "enlarged corners" are frozen at +, once all the sites inside the polygon are at +, they have fixated at +. We will call such a polygon "good droplet". We now give the necessary notation. Since U is not supercritical, there is no open semicircle of unstable directions, which implies that there exist m = 3 or 4 stable directions u 1 , ..., u m such that the origin of R 2 is contained in the interior of the convex envelope of u 1 , ..., u m . We assume that m is minimal, and that u 1 , ..., u m are numbered counterclockwise. A droplet will a polygon with sides orthogonal to u 1 , ..., u m : for any a > 0, we set D(a) = m i=1 H-u i (a) (see Figure 2). We stress that these droplets are different from those that are generally used in the study of bootstrap percolation, which are of the form D ′ (a) = m i=1 H u i (a) (see also Figure 2). D ′ (a) satisfies that if the only initial infected sites are inside D ′ (a), there will never be infected sites outside D ′ (a), as the first such site x that would be infected would be outside an H u i (a) while the update rule x + X that infects it would be inside H u i (a), which is impossible since u i is a stable direction. Thus the sites inside D ′ (a) cannot influence the sites outside. To define D(a), we replaced the u i by -u i because we want the opposite: prevent the sites outside the droplet to influence sites inside the droplet. However, sites "at the corners" of D(a) will be surrounded mostly by sites in D(a) c , so they can be influenced by sites in D(a) c . This is why we will require the sites "at the corners" to be frozen.

In order to specify which sites exactly need to be frozen, we need more notation. We identify {1, ..., m} with Z/mZ, so u m+1 = u 1 . For any i ∈ {1, ..., m}, we set 3) an "enlarged corner of D(a) between the side of the polygon orthogonal to u i and the side orthogonal to u i+1 ". We say the droplet D(a) is good when for all i ∈ {1, ..., m}, all the sites of C i,i+1 (a) are frozen at +, and for any x ∈ Z 2 , we say x + D(a) is good when for all i ∈ {1, ..., m}, all the sites of x + C i,i+1 (a) are frozen at +. The following result is one of the most important ingredients for our proofs.

C i,i+1 (a) = ( H-u i (a) \ H -u i (a -r)) ∩ ( H-u i+1 (a) \ H -u i+1 (a -r)) (see Figure
H-u 2 (a) H -u 2 (a -r) H-u 1 (a) H -u 1 (a -r) D(a) C 1,2 (a) u 2 u 1 r r Figure 3. A representation of C 1,2 (a) = ( H-u 1 (a) \ H -u 1 (a -r)) ∩ ( H-u 2 (a) \ H -u 2 (a -r))
, here the "bottom left corner of D(a)". C 1,2 (a) is the shape with the solid thick outline, and D(a) the shape with the dashed thick outline. H-u 1 (a) and H -u 1 (a -r) are represented with hatchings: H -u 1 (a -r) is the region with dense hatchings, and H-u 1 (a) contains both this region and the region with the spaced hatchings. Similarly, H -u 2 (a -r) is the region in dark gray and H-u 2 (a) contains both this region and the region in lighter gray.

Proposition 12. There exists a 0 = a 0 (U, u 1 , .., u m ) < +∞ so that for any a ≥ a 0 , if D(a) is good, if no site of D(a) is frozen at -, and if at some time t ≥ 0 all sites in D(a) are in state +, then all sites in D(a) are well fixed at + at time t.

Proof. We prove the statement by contradiction. If some site of D(a) is not well fixed at + at time t, there exists x ∈ D(a) such that x can be the first site in D(a) to switch its state toafter time t. Then by the definition of the dynamics, there exists X ∈ U so that all sites in x + X are atjust before the switch. We will prove this is geometrically impossible. Since x is the first site in D(a) to change state, x + X ⊂ D(a) c . Moreover, all sites in x + X are at distance at most r from x, therefore x belongs to some H-u i (a) \ H -u i (a -r). Furthermore, since C i-1,i (a) and C i,i+1 (a) are frozen, x does not belong to them, hence x ∈ H -u i-1 (a -r) and x ∈ H -u i+1 (a -r). If m = 3, we then have x ∈ H -u j (a -r) for all j ̸ = i. We now show it in the case m = 4, where we have to deal with j = i + 2. Since D(1) has four sides of positive length, there exists some

ε = ε(u 1 , u 2 , u 3 , u 4 ) > 0 so that H-u 1 (1 -ε) ∩ H-u 3 (1 -ε) ∩ H-u 2 (1) ∩ H-u 4 (1) has still four sides of positive length. Then D(1) ∩ ( H-u 1 (1) \ H -u 1 (1 -ε)) and D(1) ∩ ( H-u 3 (1) \ H -u 3 (1 -ε)) are disjoint, thus D(a) ∩ ( H-u 1 (a) \ H -u 1 (a -aε)) and D(a) ∩ ( H-u 3 (a) \ H -u 3 (a -aε)) are disjoint. If a ≥ r/ε, this implies D(a) ∩ ( H-u 1 (a) \ H -u 1 (a -r)) and D(a) ∩ ( H-u 3 (a) \ H -u 3 (a -r)) are disjoint. Similarly, one can find some ε ′ = ε ′ (u 1 , u 2 , u 3 , u 4 ) > 0 so that if a ≥ r/ε ′ , D(a) ∩ ( H-u 2 (a) \ H -u 2 (a -r)) and D(a) ∩ ( H-u 4 (a) \ H -u 4 (a -r)) are disjoint. We set a 0 = max(r/ε, r/ε ′ ), then if a ≥ a 0 , since x ∈ D(a) ∩ ( H-u i (a) \ H -u i (a -r)), we have x ̸ ∈ D(a) ∩ ( H-u i+2 (a) \ H -u i+2 (a -r)), thus x ∈ H -u i+2 (a -r)). Consequently, x ∈ H -u j (a -r) for all j ̸ = i.
Since x ∈ H -u j (a -r) for all j ̸ = i, we have x + X ∈ H -u j (a) for all j ̸ = i. But x + X ⊂ D(a) c , hence x + X ⊂ H-u i (a) c = H u i (-a). However, x ∈ H-u i (a), so ⟨x, u i ⟩ ≥ -a, hence x + X ⊂ x + H u i , which contradicts the fact that u i is a stable direction, and ends the proof. □ Remark 13. If U is supercritical, a similar construction is impossible. Indeed, it was proven in Section 5.3 of [START_REF] Bollobás | Monotone cellular automata in a random environment[END_REF] that for supercritical update families, one can find a finite set of sites such that the bootstrap percolation dynamics starting with only these sites initially infected will propagate the infection at an unlimited distance along a given direction. In the U-voter dynamics, if such a set of sites is atand is positioned so that this direction points to a side of D(a), even if these sites are far away from D(a), themay propagate from these sites and enter D(a). Indeed, we can denote x 1 , x 2 , ... the sites that are infected by this bootstrap percolation dynamics in the order they are infected, excluding those that are already at -, and X 1 , X 2 , ... the respective update rules allowing to infect them. If there are successive clock rings at x 1 , x 2 , ... and the update rules chosen are X 1 , X 2 , ..., these sites will switch to -.

We also prove a technical lemma on the C i,i+1 (a) that will be needed later.

Lemma 14. There exists ã0 = ã0 (U, u 1 , .., u m ) < +∞ so that for any a ≥ ã0 , for any i ∈ {1, ..., m}, C i,i+1 (a) ⊂ D(a).

Proof. If m = 3, D(a) has 3 sides, and if m = 4 then D(a) has four sides, since if D(a) had less than four sides, the directions orthogonal to these sides would contain 0 in the interior of their convex envelope, which would contradict the minimality of m. We notice that for each i ∈ {1, ..., m}, for all a > 0 the C i,i+1 (a) are translations of each other. We denote

d i = max{∥y -y ′ ∥ 2 | y, y ′ ∈ C i,i+1 (1)
} the diameter of the C i,i+1 (a). For each i ∈ {1, ..., m}, we denote by c i,i+1 the site that is the "corner of D(1) between the side of the polygon orthogonal to u i and the side orthogonal to u i+1 ", defined by ⟨c i,i+1 , -u i ⟩ = 1 and ⟨c i,i+1 , -u i+1 ⟩ = 1. Since D(1) has m sides, for each j

̸ = i, i + 1, ⟨c i,i+1 , -u j ⟩ < 1. If we choose ã0 ≥ max{d i , d i 1-⟨c i,i+1
,-u j ⟩ | i, j ∈ {1, ..., m}, j ̸ = i, i + 1}, then for a ≥ ã0 , i ∈ {1, ..., m} and j ̸ = i, i + 1, the points in C i,i+1 (a) are at distance at most d i of ac i,i+1 , hence are in H-u j (a⟨c i,i+1 , -u j ⟩ + d i ) ⊂ H-u j (a). We deduce C i,i+1 (a) ⊂ D(a). □

Easily fixating regions: good blocks

The aim of this section is to describe regions of Z 2 , called good blocks (Definition 15), favorable enough so that we can prove they will likely fixate at +, and to prove that the probability a region is favorable is very high (Proposition 16). From now on, we consider both non-supercritical update families and supercritical update families with no disjoint update rules. For any L ∈ N * , we denote B L = {-L, ..., L} 2 . A block is a set of the form x + B L where x ∈ Z 2 . The definition of a good block will differ according to whether U is supercritical or not. If U is not supercritical, we set M = max{∥x∥ 2 | x ∈ D(1)} and M ′ = max{∥x∥ 2 | x ∈ D ′ (1)}, where D(1) and D ′ (1) were defined at the beginning of Section 3. For reasons that will be apparent later, we set K = 25 is U is supercritical and K = (2⌈(4M + 1)M ′ ⌉ + 1) 2 if U is not supercritical. Definition 15. Let L ∈ N * . For any x ∈ Z 2 , one says the block x + B L is good when the following conditions are satisfied.

• If U is supercritical and contains no disjoint update rules, all sites in x + B L are infectable by the bootstrap percolation in x + B 2L (with healthy boundary conditions) and initial infected sites the sites frozen at + in x + B 2L , and there is no site frozen atin x + B 2L . • If U is not supercritical, all sites in x + D(3L) are infectable by the bootstrap percolation with initial infected sites the sites frozen at + in x + D(4L), there is no site frozen atin x + D ′ (4LM + 1), and there exists 2L ≤ a ≤ 3L such that x + D(a) is good.

We remind the reader that the constants a 0 , ã0 were defined in Proposition 12 and Lemma 14. In the following, when we say a quantity depends on u 1 , ..., u m , this dependence will only apply for non-supercritical U.

Proposition 16. For any qc (U) < ρ + < 1, there exists ρ - 0 = ρ - 0 (U, u 1 , ..., u m , ρ + ) > 0 and L 0 = L 0 (U, u 1 , ..., u m , ρ + ) ≥ r, with L 0 ≥ max(a 0 , ã0 ) if U is not supercritical, such that for any 0 ≤ ρ -≤ ρ - 0 and for any x ∈ Z 2 , we have P(x+B L 0 is not good) ≤ 1/2 5K . Proof. Let qc (U) < ρ + < 1. We will deal differently with the non-supercritical case and with the supercritical case, though we need bootstrap percolation technology in both cases.

Case U supercritical with no disjoint update rules.

To deal with this case, we will use the tools developed in [START_REF] Bollobás | Monotone cellular automata in a random environment[END_REF] for supercritical bootstrap percolation. Since U is supercritical, there exists an open semicircle of unstable directions. We denote its center by u ∈ S 1 . We consider rectangles oriented in direction u: denoting u ⊥ ∈ S 1 a direction orthogonal to u, for any a, b > 0, the rectangle oriented in direction u with width a and length b will be R(a, b) = {x ∈ R | -a/2 ≤ ⟨x, u ⊥ ⟩ ≤ a/2, 0 < ⟨x, u⟩ ≤ b}. It was proven in Section 5.3 of [START_REF] Bollobás | Monotone cellular automata in a random environment[END_REF] that there exist some a > 0, b > 0, c < +∞ depending only on U so that for any x ∈ Z 2 , if x + R(a, b) is initially infected, for any b ′ > b the rectangle x + R(a, b ′ ) is infectable by the bootstrap percolation in x + R(a, b ′ + c) (the latter part is not explicitly stated in [START_REF] Bollobás | Monotone cellular automata in a random environment[END_REF], but can be seen in the proofs). Consequently, if L is large enough depending on a, b, c, for any x ∈ Z 2 , y ∈ x + B L , if there exists 1 ≤ n ≤ L/(2b) so that y -nbu + R(a, b) is initially infected, then y is infectable by the bootstrap percolation in x + B 2L (with healthy boundary conditions). Therefore, if we denote B y = {y is not infectable by the bootstrap percolation in x + B 2L with initial infected sites the sites frozen at + in x + B 2L } and k the maximum number of sites in a translation of R(a, b), which is bounded, then

P(B y ) ≤ (1 -(ρ + ) k ) ⌊L/(2b)⌋ . Thus P(∪ y∈x+B L B y ) ≤ (2L + 1) 2 (1 -(ρ + ) k ) ⌊L/(2b)⌋ . We choose L 0 = L 0 (U, u 1 , ..., u m , ρ + ) ≥ r so that (2L 0 + 1) 2 (1 -(ρ + ) k ) ⌊L 0 /(2b)⌋ ≤ 1/2 5K+1 , hence P(∪ y∈x+B L 0 B y ) ≤ 1/2 5K+1 . If we now set ρ - 0 = 1/(2 5K+1 (4L 0 + 1) 2 ), then for any 0 ≤ ρ -≤ ρ - 0 , we have P(x + B L 0 is not good) ≤ 1/2 5K . Case U non-supercritical. Let x ∈ Z 2 .
We first study the probability of finding a good droplet x + D(a). We assume L ≥ ã0 . Lemma 14 yields that for n ∈ {1, ..., ⌊L/(r + 1)⌋}, the x + C i,i+1 (2L + n(r + 1)) are contained in x + D(2L + n(r + 1)), and by their definition they are contained in x + D(2L + (n -1)(r + 1)) c . This implies the events {x + D(2L + n(r + 1)) is good} for n ∈ {0, ..., ⌊L/(r + 1)⌋} depend on disjoint sets of sites hence are independent. Furthermore, we notice that for each i ∈ {1, ..., m}, for all a > 0 the C i,i+1 (a) are translations of each other. We denote k i the maximum number of sites in any translation of C i,i+1 [START_REF] Arratia | Site recurrence for annihilating random walks on Z d[END_REF], which is bounded, and k = m i=1 k i . Then P(

⌊L/(r+1)⌋ n=1 {x + D(2L + n(r + 1)) is not good}) ≤ (1 -(ρ + ) k ) ⌊L/(r+1)⌋ . If we choose L 1 = L 1 (U, u 1 , ..., u m , ρ + ) ≥ ã0 so that (1 -(ρ + ) k ) ⌊L 1 /(r+1)⌋ ≤ 1/(3 • 2 5K ), for all L ≥ L 1 we have P({∃ 2L ≤ a ≤ 3L, x + D(a) is good} c ) ≤ 1/(3 • 2 5K ).
We now consider the probability that sites are infectable. To deal with it, we use Theorem 3.5 of [START_REF] Hartarsky | U-bootstrap percolation: critical probability, exponential decay and applications[END_REF], which states that since ρ + > qc (U), there exists a constant c = c(U, ρ + ) so that for any n ∈ N, we have P(0 is not infectable by the bootstrap percolation starting from sites frozen + in B n ) ≤ e -cn . Moreover, for y ∈ x + D(3L), we have y + B ⌊L/ √ 2⌋ ⊂ x + D(4L), hence P(y is not infectable starting from sites frozen + in x + D(4L)) ≤ P(y is not infectable starting from sites frozen + in y + B ⌊L/ √ 2⌋ ) ≤ e -c⌊L/ √ 2⌋ . In addition, remembering the definition of M, M ′ at the beginning of the section, there are at most (6M L + 1) 2 sites in x + D(3L), hence P( y∈x+D(3L) {y is not infectable starting from sites frozen + in x + D(4L)}) ≤ (6M L + 1) 2 e -c⌊L/ √ 2⌋ . We then set L 0 = L 0 (U, u 1 , ..., u m ) ≥ max(L 1 , a 0 , 1) so that

(6M L 0 + 1) 2 e -c⌊L 0 / √ 2⌋ ≤ 1/(3 • 2 5K ). If we now set ρ - 0 = 1 3•2 5K (2(4L 0 M +1)+1) 2 , then for any 0 ≤ ρ -≤ ρ - 0 , we have P(x + B L 0 is not good) ≤ 1/2 5K . □ Remark 17.
It is in the proof of Proposition 16 that we need ρ + > qc (U) instead of ρ + > q c (U) for subcritical dynamics.

5. Fixation at +: proof of Theorems 5 and 7

The goal of this section is to prove Theorem 5, which states fixation at + of all sites if ρ -= 0, and Theorem 7, which claims the existence of a deterministic time at which the connected components of sites not fixated at + are finite. In order to do that, we begin by showing Theorem 18, which roughly states that for any 0 ≤ ρ -≤ ρ - 0 , there exists a deterministic time so that the connected components of blocks containing sites not well fixed at this time are finite. This result is stronger than Theorem 7, and is central in the proof of Theorems 5 and 9, since it allows to consider only the dynamics in these finite connected components. At the end of this section, we prove Theorem 5. To state Theorem 18, we consider the blocks 2L 0 x + B L 0 for all x ∈ Z 2 , denoting B L 0 (x) = 2L 0 x + B L 0 . Blocks B L 0 (x) and B L 0 (y) will be considered neighbors when ∥x -y∥ ∞ = 1, which gives a graph with an associated notion of connectedness. We then have the following.

Theorem 18. For any qc (U) < ρ + < 1, there exists T 0 = T 0 (U, u 1 , ..., u m , ρ + ) < +∞ deterministic so that for any 0 ≤ ρ -≤ ρ - 0 , for any choice of initial distribution µ, almost surely the connected components of blocks containing sites that are not well fixed at + at time T 0 are finite.

Proof. We first give the idea of the proof. We will lower bound the probability that the dynamics fills a good block with + in a time interval of length 1, which allows to find T 0 so that for any good block, the probability that the dynamics fills the block with + before time T 0 is very high. We also show that roughly, if the sites of a good block are at + at some time, they are well fixed at + at this time, which will be Claim 19. Since by Proposition 16 blocks are likely to be good, the probability that a given block is full of sites well fixed at + at time T 0 is then close to 1 (to shorten the notation, for any T > 0, we say a block is T -fixed when all its sites are well fixed at + at time T ). We then want to use the following classical percolation argument: if there is an infinite connected component of non T 0 -fixed blocks, for any integer n there is a path of length n of such blocks, which has probability tending to 0 when n tends to +∞. However, one has to be careful in proving the latter part, since the events that the blocks are T 0 -fixed are not independent.

We now give the rigorous argument. We set qc (U) < ρ + < 1, 0 ≤ ρ -≤ ρ - 0 , µ an initial distribution. It is enough to find T 0 so that for any x ∈ Z 2 , almost surely the connected component of non T 0 -fixed blocks containing

B L 0 (x) is finite. Let x ∈ Z 2 , T > 0. If B L 0 (x)
is contained in an infinite connected component of non T -fixed blocks, for all n > 0 there exists a non T -fixed path of legnth n starting from B L 0 (x), that is a sequence B L 0 (x) = B L 0 (x 1 ), ..., B L 0 (x n ) of non T -fixed blocks such that the x i , i ∈ {1, ..., n} are all different and for each i ∈ {1, ..., n -1}, B L 0 (x i+1 ) is a neighbor of B L 0 (x i ). There are at most 8 n possible such paths, hence it is enough to find T 0 so that 8 n max γ P(γ is non T 0 -fixed) tends to 0 when n tends to +∞, where the max is taken on all possible paths of length n starting from B L 0 (x) and all x ∈ Z 2 .

Let γ be a path of length n starting from B L 0 (x). We will study max γ P(γ is non T 0 -fixed). We first need some notation. Remembering the definition of K, M, M ′ at the beginning of Section 4, if U is supercritical, we can find blocks B L 0 (x 1 ), ..., B L 0 (x ⌊n/K⌋ ) in γ so that for x i ̸ = x j we have 2L 0 x i +B 2L 0 and 2L 0 x j +B 2L 0 disjoint, and if U is not supercritical, we can find blocks B L 0 (x 1 ), ..., B L 0 (x ⌊n/K⌋ ) in γ so that for

x i ̸ = x j we have ∥x i -x j ∥ ∞ > (4L 0 M +1)M ′ L 0 hence 2L 0 x i + D ′ (4L 0 M + 1
) and 2L 0 x j + D ′ (4L 0 M + 1) are disjoint. In order to have the same notation in the supercritical case and the non-supercritical case, we denote

B i = 2L 0 x i + B L 0 , B ′ i = 2L 0 x i + B 2L 0 if U is supercritical, and B i = 2L 0 x i + D(3L 0 ), B ′ i = 2L 0 x i + D ′ (4L 0 M + 1) if U is not supercritical.
For each i ∈ {1, ..., ⌊n/K⌋}, we will define events G i,ℓ , ℓ ∈ N such that all sites in B L 0 (x i ) are at + at time ℓ if G i,ℓ occurs. We assume B L 0 (x i ) is good. Then we can prove that all sites in B i are infectable by the bootstrap percolation in B ′ i with healthy boundary conditions and initial infected sites the sites frozen at + in B ′ i . Indeed, if U is supercritical this comes from the definition of a good block. If U is not supercritical, this is because sites in B i are infectable by the bootstrap percolation starting from sites frozen at + in 2L 0 x i + D(4L 0 ) ⊂ B ′ i , hence starting from sites frozen at + in B ′ i , and in the bootstrap percolation starting from sites frozen at + in B ′ i , all sites outside B ′ i remain healthy since 2L 0 x i + D ′ (4L 0 M + 1) is constructed so the infection cannot escape it. Consequently, in both cases there exists m i ∈ N, a sequence x i,1 , ..., x i,m i of distinct sites in B ′ i and a sequence X i,1 , ..., X i,m i of update rules so that all sites in B i are either equal to one of the x i,j or frozen at +, for each j ∈ {1, ..., m i }, x i,j + X i,j ⊂ B ′ i , and all sites of x i,j + X i,j are either some x i,j ′ , j ′ < j or frozen at +. For each ℓ ∈ N * , we denote G i,ℓ the event "in the time interval (ℓ -1, ℓ], there are successive clock rings at each x i,j that is atat time ℓ -1, in increasing order, the update rule chosen for x i,j is X i,j , and no other clock ring happens in B ′ i ". If G i,ℓ happens, sites x i,1 , ..., x i,m i are at + at time ℓ (this uses the fact that none of them is frozen et -), so all sites in B L 0 (x i ) are at + at time ℓ. Moreover, we have the following. Claim 19. If x i,1 , ..., x i,m i are at + at time ℓ then all sites in B L 0 (x i ) are well fixed at + at time ℓ.

Proof of Claim 19. If U is not supercritical, if x i,1 , ..., x i,m i are at + at time ℓ, then all sites in 2L 0 x i + D(3L 0 ) are at + at time ℓ. Moreover, there exists 2L 0 ≤ a ≤ 3L 0 such that 2L 0 x i + D(a) is good. By Proposition 12 and the invariance by translation of the dynamics, all sites in 2L 0 x i + D(a) are well fixed at + at time ℓ, hence all sites in B L 0 (x i ) are well fixed at + at time ℓ. If U is supercritical and contains no disjoint update rules, we assume by contradiction that x i,1 , ..., x i,m i are at + at time ℓ but some sites among x i,1 , ..., x i,m i are not well fixed at + at this time. Then there exists an x i,j that can be the first of them to change its state toafter time ℓ. Sites in x i,j + X i,j are either frozen at + or some x i,j ′ , j ′ < j, hence are at + at the time of the switch. But U has no disjoint update rules, thus for any X ∈ U, x i,j + X contains at least a site at + at the time of the switch, therefore x i,j cannot change its state to -. We deduce that if x i,1 , ..., x i,m i are at + at time ℓ, then x i,1 , ..., x i,m i are well fixed at + at time ℓ, hence all sites in B L 0 (x i ) are well fixed at + at time ℓ.

□

We now study P(G i,ℓ |F ℓ-1 ) for any i ∈ {1, ..., ⌊n/K⌋}, ℓ ∈ N * . We denote b ′ the number of sites in B ′ i (which does not depend on i). If B L 0 (x i ) is good then conditionally on F ℓ-1 , the probability that G i,ℓ occurs is the probability that in a time interval of length 1, on a given set of sites of cardinal at most b ′ , there are successive clock rings, on another given set of sites of cardinal at most b ′ there are no clock rings, and when making a given number of update rules choices, smaller than b ′ , the results follow a given sequence. This is bigger than the probability of having successive clock rings on b ′ sites and no clock rings on b ′ other sites in a time interval of length 1, and obtaining a given sequence in b ′ update rules choices. Therefore there exists ε = ε(U, u 1 , ..., u m , ρ + ) > 0 so that for any i ∈ {1, ..., ⌊n/K⌋}, ℓ ∈ N * , we have

1 {B L 0 (x i ) is good} P(G i,ℓ |F ℓ-1 ) ≥ 1 {B L 0 (x i ) is good} ε.
We are now able to bound the probability that γ is non T -fixed for T ∈ N * . Indeed, if γ is non T -fixed, for all i ∈ {1, ..., ⌊n/K⌋}, 1 ≤ ℓ ≤ T so that B L 0 (x i ) is good, (G i,ℓ ) c occurs. We denote G γ = {i ∈ {1, ..., ⌊n/K⌋} | B L 0 (x i ) is good}, and for G ⊂ {1, ..., ⌊n/K⌋} we study P(G γ = G, ∩ i∈G,1≤ℓ≤T (G i,ℓ ) c ). In addition, G i,ℓ depend on clock rings and update rules choices in B ′ i , and the definition of the x i yields that the B ′ i are disjoint, hence the G i,ℓ are independent conditionally on F ℓ-1 . Consequently,

P(G γ = G, ∩ i∈G,1≤ℓ≤T (G i,ℓ ) c ) ≤ (1 -ε) |G| P(G γ = G, ∩ i∈G,1≤ℓ≤T -1 (G i,ℓ ) c ), hence P(G γ = G, ∩ i∈G,1≤ℓ≤T (G i,ℓ ) c ) ≤ (1 -ε) |G|T P(G γ = G).
Moreover, for any i ∈ {1, ..., ⌊n/K⌋}, the event {B L 0 (x i ) is good} depends only of the frozen sites inside B ′ i (this requires Lemma 14), and the B ′ i are disjoint, so these events are independent. By Proposition 16, we deduce

P(G γ = G, ∩ i∈G,1≤ℓ≤T (G i,ℓ ) c ) ≤ (1 -ε) |G|T (1/2 5K ) ⌊n/K⌋-|G| . If we choose T 0 = T 0 (U, u 1 , ..., u m , ρ + ) < +∞ so that (1 -ε) T 0 ≤ 1/2 5K , we obtain P(G γ = G, ∩ i∈G,1≤ℓ≤T 0 (G i,ℓ ) c ) ≤ (1/2 5K ) ⌊n/K⌋ .
Since there are at most 2 n choices for G, this implies 8 n P(γ is non T 0 -fixed) ≤ 8 n 2 n (1/2 5K ) ⌊n/K⌋ = 2 4n (1/2 5K ) ⌊n/K⌋ , which decays to 0 when n tends to +∞. This ends the proof of Theorem 18. □

We are now in position to prove Theorem 5.

Proof of Theorem 5. The idea behind the argument is that Theorem 18 shows that at time T 0 there are finite connected components of sites that have not fixated at + in an ocean of sites well fixed at +. When by chance the dynamics fills one of these connected components with +, no site atcan appear near it, so all sites in the component remain at + forever. We now give the rigorous argument. Let qc (U) < ρ + < 1, ρ -= 0, and µ be an initial distribution. Let x ∈ Z 2 . Thanks to Theorem 18, if x is not well fixed at + at time T 0 , almost surely x is contained in a block that is part of a finite connected component C of blocks containing sites not well fixed at + at time T 0 . Then the blocks in C c that are neighbors of elements of C contain only sites well fixed at + time T 0 . Moreover, Theorem 1 of [START_REF] Balister | Subcritical U-bootstrap percolation models have non-trivial phase transitions[END_REF] states that if all directions are stable, U is subcritical and q c (U) = 1. This implies qc (U) = 1, so one cannot choose qc (U) < ρ + < 1. Therefore in our case there exists an unstable direction u, and some X ∈ U with X ⊂ H u . We enumerate the sites in B∈C B as x 1 , ..., x n with ⟨x i , u⟩ nondecreasing. Then, similarly to what was done in the proof of Theorem 18, for each ℓ ∈ N * , we define G ℓ the event "in the time interval (T 0 + ℓ -1, T 0 + ℓ], there are successive clock rings at each x i that is atat time T 0 + ℓ -1, in increasing order, the update rule chosen for x i is X, and no other clock ring happens in B∈C B". If G ℓ occurs, all sites of B∈C B are at + at time T 0 + ℓ. They have then fixated at + at time T 0 + ℓ, as the first site y ∈ B∈C B to switch to statewould need X ′ ∈ U so that the sites of y + X ′ are at state -. Furthermore, as in the proof of Theorem 18, there exists δ > 0 random depending on F T 0 so that for all ℓ ∈ N * we have 1 {x not well fixed at T 0 } P(G ℓ |F T 0 +ℓ-1 ) ≥ 1 {x not well fixed at T 0 } δ, thus for all n ∈ N * we obtain P(x not well fixed at

T 0 , n ℓ=1 G c ℓ ) ≤ E((1 -δ) n
), which converges to 0 when n tends to +∞ by dominated convergence, thus almost surely one of the G ℓ occurs. This implies x almost surely fixates at +, which ends the proof of Theorem 5. □

Flippers: proof of Theorem 9

This section is devoted to the proof of Theorem 9 on the existence or non-existence of flippers. Let qc (U) < ρ + < 1, 0 < ρ -≤ ρ - 0 , and µ be an initial distribution.

6.1. First case: U contains two disjoint update rules X and X ′ . Almost surely, for each x ∈ Z 2 , t ≥ 0, there is a clock ring at x after time t so that X is chosen and a clock ring at x after time t so that X ′ is chosen. Moreover, almost surely there is an infinite number of sites x so that all sites in are x + X is frozen at + and all sites in x + X ′ are frozen at -. If x is one of these sites, then x is a flipper. Hence almost surely there is an infinite number of flippers.

6.2. Second case: U contains no disjoint update rules. We will show that almost surely there is no flipper. The idea of the proof is to use Theorem 18, which states that the connected components of blocks with sites not well fixed at + at time T 0 are finite, and to restrict our attention to one of these finite components. We will then prove that in this component, at some time all the possible flippers switch successively fromto +. Then, if x is one of these sites, since it was put to +, some x + X with X ∈ U is at +. Then for any X ′ ∈ U, since X and X ′ are not disjoint, x + X ′ contains at least a site of x + X, so x + X ′ is not entirely at -, thus x cannot be put athence cannot be a flipper. We now spell out the rigorous argument. Let x ∈ Z 2 . If x is well fixed at time T 0 , then x is not a flipper. Thanks to Theorem 18, if x is not well fixed at + at time T 0 , almost surely x is contained in a block that is part of a finite connected component C of blocks containing sites not well fixed at + at time T 0 . We denote C → the set of blocks in C c that are neighbors of elements of C. Then B∈C → B contain only sites well fixed at + time T 0 . In this proof, we will need the concept of ⊖-bootstrap percolation and ⊕-bootstrap percolation. The ⊖-bootstrap percolation (respectively ⊕-bootstrap percolation) has the same dynamics as the usual bootstrap percolation, apart that the sites frozen at + (respectively at -) in the U-voter dynamics are frozen in the healthy state.

Claim 20. For any t ≥ T 0 , the ⊖-bootstrap percolation process starting from the sites of B∈C B that are atat time t infects only sites in B∈C B.

Proof. We show this by contradiction. If the claim does not hold, let x ′ be a site of ( B∈C B) c infected by this process at the first step at which it is possible, then x ′ ∈ B∈C → B, so x ′ is well fixed at + at time T 0 . Moreover, the infectability of x ′ implies the existence of a sequence x 0 , ...x n = x ′ and X 1 , ..., X n ∈ U so that the x j , j ∈ {1, ..., n} are at + at time t but not frozen at +, and for any i ∈ {1, ..., n}, the sites of x i + X i are among the x j , j < i or sites of B∈C B atat time t. If after time t there are successive clock rings at x 1 , ..., x n , if the updates rules chosen are X 1 , ..., X n , and if there is no other clock ring in any of the x j , j ∈ {1, ..., n} or in B∈C B during this time, which is a possible event, then x ′ is atafterwards, which contradicts the fact it is well fixed at + at time T 0 and proves the claim. □

We will define events G ℓ , ℓ ∈ N * so that if one of the G ℓ occurs, there is no flipper in B∈C B. For any ℓ ∈ N * , we consider all the sites that are at + at time T 0 + ℓ -1 and can be infected by the ⊖-bootstrap percolation starting from the sites of B∈C B that are atat time T 0 + ℓ -1. All these sites are in B∈C B by Claim 20. We denote them x ℓ,1,1 , ..., x ℓ,1,k 1 ℓ , ordered so that for any i ∈ {1, ..., k 1 ℓ }, there exists X ℓ,1,i ∈ U so that the sites of x ℓ,1,i + X ℓ,1,i are among the x ℓ,1,j , j < i or sites of B∈C B atat time T 0 + ℓ -1. We then define G ℓ,1 as the event "in the time interval (T 0 + ℓ -1, T 0 + ℓ -1/2], there are successive clock rings at x ℓ,1,1 , ..., x ℓ,1,k 1 ℓ in increasing order, the update rules that are chosen are X ℓ,1,1 , ..., X ℓ,1,k 1 ℓ , and there is no other clock ring in B∈C B". Furthermore, we consider all the sites of B∈C B that are atat time T 0 + ℓ -1/2 and can be infected by the ⊕-bootstrap percolation in B∈C∪C → B starting from the sites of B∈C∪C → B that are at + at time T 0 + ℓ -1/2. We denote them x ℓ,2,1 , ..., x ℓ,2,k 2 ℓ , ordered so that for any i ∈ {1, ..., k 2 ℓ }, there exists X ℓ,2,i ∈ U so that the sites of x ℓ,2,i + X ℓ,2,i are among the x ℓ,2,j , j < i or sites of B∈C∪C → B at + at time T 0 + ℓ -1/2. We then define G ℓ,2 as the event "in the time interval (T 0 + ℓ -1/2, T 0 + ℓ], there are successive clock rings at x ℓ,2,1 , ..., x ℓ,2,k 2 ℓ in increasing order, the update rules that are chosen are X ℓ,2,1 , ..., X ℓ,2,k 2 ℓ , and there is no other clock ring in B∈C B". We now set G ℓ = G ℓ,1 ∩ G ℓ,2 . We will show the following.

Claim 21. For any ℓ ∈ N * , if G ℓ occurs, almost surely there is no flipper in B∈C B.

Proof. We can show by induction that any site of B∈C B that changes its state toafter time T 0 + ℓ -1 is infectable by the ⊖-bootstrap percolation process starting from the sites of B∈C B that are atat time T 0 + ℓ -1. Indeed, if x ′ is the n-th site to do so, there exists X ∈ U so that all sites in x ′ + X are atjust before the change. Since sites in B∈C → B are well fixed at + at time T 0 , x ′ + X ⊂ B∈C B, and the sites of x ′ + X were either atat time T 0 + ℓ -1 or changed their state toafter this time. In both cases, by the induction hypothesis they are infectable by the ⊖-bootstrap percolation starting from the sites of B∈C B that are atat time T 0 + ℓ -1, hence x ′ also is, since it is not frozen at +. A similar argument yields that any site in B∈C B that changes its state to + after time T 0 + ℓ -1/2 is infectable by the ⊕-bootstrap percolation in B∈C∪C → B starting from the sites of B∈C∪C → B that are at + at time T 0 + ℓ -1/2. Therefore if x ′ ∈ B∈C B is a flipper, it is infectable by these two processes.

We now assume G ℓ occurs. Then G ℓ,1 ensures x ′ is atat time T 0 + ℓ -1/2, and G ℓ,2 ensures x ′ switches to + between times T 0 +ℓ-1/2 and T 0 +ℓ. Since x ′ is a flipper, it will switch toafter time T 0 +ℓ. Let x ′′ be the first site to switch toat some time t ≥ T 0 + ℓ among the sites of B∈C B that switch to + between times T 0 + ℓ -1/2 and T 0 + ℓ.

There exists X ∈ U so that the sites in x ′′ + X were at + at the time of this switch to +. Since x ′′ + X ⊂ B∈C∪C → B, since sites in B∈C → B are well fixed at time T 0 , and by the structure of G 2,ℓ , sites in x ′′ + X are still at + at time T 0 + ℓ. They are still at + at time t, since if one of them had switched tobefore, it would have been infectable by the ⊖-bootstrap percolation starting from the sites of B∈C B that are atat time T 0 + ℓ -1, thus since G ℓ,1 occurs it would be atat time T 0 + ℓ -1/2, thus it would have switched at + between times T 0 + ℓ -1/2 and T 0 + ℓ, and x ′′ is the first such site to switch toafter time T 0 + ℓ. This implies sites of x ′′ + X are at + at time t. Moreover, we assumed U contains no disjoint update rules, so for any X ′ ∈ U, we have that x ′′ + X ′ contains a site of x ′′ + X, which is at + at time t. Hence x ′′ cannot switch its state toat time t, so there is a contradiction, which ends the proof of the claim. □

We conclude that for any ℓ ∈ N * , if G ℓ occurs, x is not a flipper. Consequently, it is enough to prove that almost surely, if x is not well fixed at time T 0 , one of the G ℓ , ℓ ∈ N * occurs. Furthermore, as in the proof of Theorem 18, there exists δ > 0 random depending on F T 0 so that for all ℓ ∈ N * we have 1 {x not well fixed at T 0 } P(G ℓ |F T 0 +ℓ-1 ) ≥ 1 {x not well fixed at T 0 } δ, thus for all n ∈ N * we obtain P(x not well fixed at T 0 , n ℓ=1 G c ℓ ) ≤ E((1 -δ) n ), which converges to 0 when n tends to +∞ by dominated convergence, thus almost surely if x is not well fixed at time T 0 one of the G ℓ occurs, which ends the proof of Theorem 9.

One-dimensional case: proof of Theorems 2 and 3

This section is devoted to the proof of Theorems 2 and 3 on one-dimensional update families. In this section, U will be an update family on Z. As in the two-dimensional case, we define the range of U as r = r(U) = max{|x| | x ∈ X, X ∈ U}. Let 0 < ρ + < 1. The following obvious fact will be key to our proofs, replacing the two-dimensional Theorem 18.

Lemma 22. For any x ∈ Z, almost surely there exists x r > x and x ℓ < x so that x r + 1, ..., x r + r and x ℓ -1, ...x ℓ -r are frozen at +. Proof of Theorem 2. We want to prove fixation at + for all sites of Z. The argument resembles the one used for the two-dimensional case: the dynamics in {x ℓ , ..., x r } is isolated from what happens outside by the sites frozen at +, and once by chance {x ℓ , ..., x r } is filled with +, then x ℓ , ..., x r will remain at +. Here U is supercritical; we assume there exists an update rule X ∈ U so that X ⊂ N * (the case X ⊂ -N * is similar). Let x ∈ Z. If x ℓ , ..., x r are at + at some time, they (and thus x) have fixated at + at this time, since for x ′ ∈ {x ℓ , ..., x r }, X ′ ∈ U, all sites of x ′ + X ′ are at +. We now prove that almost surely there will be some time at which x ℓ , ..., x r are at +. For any ℓ ∈ N * , we set G ℓ the event "in the time interval (ℓ -1, ℓ], there are successive clock rings at each site among x r , x r -1, ..., x ℓ that is atat time ℓ -1, in increasing order, the update rule chosen is always X, and no other clock ring happens in {x ℓ , ..., x r }". If G ℓ occurs, x ℓ , ..., x r are at + at time ℓ. Moreover, as in the proof of Theorem 18, there exists δ > 0 depending on x ℓ , x r so that P(G ℓ |F ℓ-1 ) ≥ δ. Hence P( n ℓ=1 G c ℓ ) ≤ E((1 -δ) n ) which tends to 0 when n tends to +∞ by dominated convergence, so almost surely some G ℓ occurs, then x ℓ , ..., x r are at + at time ℓ, therefore x fixates almost surely. □ Proof of Theorem 3. The argument is similar to and simpler than the one in the proof of Theorem 9, with {x ℓ , ..., x r } playing the role of B∈C B and {x ℓ -r, ..., x ℓ -1} {x r + 1, ..., x r + r} playing the role of B∈C → B. □

Figure 2 .

 2 Figure 2. Droplets D(a) and D ′ (a) in the case m = 3.

  Definition 4. The update family U on Z 2 is called • supercritical if there exists an open semicircle of unstable directions; • critical if it is not supercritical, but there exists a semicircle containing a finite number of stable directions; • subcritical otherwise.


David González-Andrade

Christian Lafforgue

Elena Durán-Valdeiglesias

Xavier Le Roux

Mathias Berciano

Eric Cassan

Delphine Marris-Morini

Aitor Velasco

Pavel Cheben

Laurent Vivien

Polarization-and wavelength-agnostic nanophotonic beam splitter