Kévin Perrot

Éric Rémila

On the emergence of regularities on one-dimensional decreasing sandpiles 1

Keywords: Sandpile models, discrete dynamical system, fixed points, emergence

Decreasing sandpiles model the dynamics of configurations where each position i ∈ N contains a finite number of stacked grains h i , such that h i ≥ h i+1 (decrease property). Grains move according to a decreasing local rule R = (r 1 , r 2 , . . . , r p ) such that r j ≥ r j+1 , meaning that r j grains move from columns i to i + j for all 1 ≤ j ≤ p, if it does not contradict the decrease property. We are interested in the fixed point reached starting from a finite number of grains on a unique column.

, we proved the emergence of wave patterns periodically covering fixed points, for rules of the form (1, . . . , 1) (Kadanoff sandpile models). The present work is a significative extension: for large classes of decreasing sandpile model instances, we prove the emergence of patterns of various shapes periodically covering fixed points. We introduce new automata to analyze their asymptotic structure, and use the least action principle. The difficulty of understanding the behavior of sandpile models, despite the simplicity of the rules, is what makes the problem challenging.

Introduction

Understanding and explaining regularity properties on discrete dynamical systems (DDSs) rapidly becomes a puzzling problem, and formally proving the global behavior of a DDS defined with local rules is at the heart of our comprehension of natural phenomena [START_REF] Chazelle | Natural algorithms[END_REF][START_REF] Grauwin | Competition between collective and individual dynamics[END_REF][START_REF] Weaver | Science and Complexity[END_REF]. A lot of simply stated conjectures, often issued from simulations, remain open (among the famous examples is the Langton's Ant [START_REF] Gajardo | Complexity of Langton's ant[END_REF][START_REF] Gale | Further travels with my ant[END_REF]). These conjectures are usually based on the notion of "emergence", where, after a transient segment, some intriguing regularities appear. In this paper, we formally prove a specific case of emergence, whose support is the sandpile model.

Sand is a mean of visualizing some discrete dynamical systems, and various sandpile models may be defined. They basically describe the movements of square/cubic sand grains according to "simple" local rules in discrete space and time, and are paradigmatic models for the phenomena of emergence: they may exhibit surprisingly "complex" global behaviors. We start from a finite number of grains stacked on a single column (as they would fall from an hourglass), and try to predict the asymptotic shape of the stable configurations reached at the end of the dynamical evolution.

Sandpiles in one-dimension

One-dimensional sandpile configurations can be represented as a sequence (h i ) i∈N of non-negative integers, h i being the number of sand grains stacked on column i. The initial configuration h = (N, 0 ω ) is such that h 0 = N and h i = 0 for i > 0. In other words, the dynamical system is initialized with N grains on column 0 and no grain elsewhere. The set of configurations reachable from this particular initial configuration received great attention for its lattice structure [START_REF] Duchi | Bidimensional Sand Pile and Ice Pile Models[END_REF][START_REF] Durand-Lose | Parallel transient time of one-dimensional sand pile[END_REF][START_REF] Formenti | Advances in symmetric sandpiles[END_REF][START_REF] Goles | Games on line graphs and sand piles[END_REF][START_REF] Goles | Sandpile models and lattices: a comprehensive survey[END_REF]. The analogy with an hourglass is developed in Section 2.4 of [START_REF] Perrot | Strong emergence of wave patterns on Kadanoff sandpiles[END_REF].

In the Kadanoff sandpile models (KSMs) of parameter p, at each transition a fixed number p of grains move. If a transition occurs in column i, then p grains leave column i and one land on column i + j for 1 ≤ j ≤ p. To preserve the non-increasing property of configurations, a transition on column i is allowed if and only if h ih i+1 ≥ p + 1.

Decreasing sandpile models (DSMs) generalize KSMs (details in Section 2). A positive non-increasing vector R = (r 1 , r 2 , . . . , r p ) is given to describe the way grains fall (the rule): if a transition occurs at column i, then p j=1 r j grains fall from column i and r j grains land on column i + j for 1 ≤ j ≤ p. A transition on column i is allowed if and only if h ih i+1 ≥ p j=1 r j + r 1 (since r is non-increasing, this condition preserves the non-increasing property of configurations). KSMs correspond to rules of the form (1, . . . , 1).

Different update policies may be applied: asynchronous, sequential, parallel, block-sequential, etc [START_REF] Noual | Boolean networks synchronism sensitivity and XOR circulant networks convergence time[END_REF], but in any case one easily sees that a given finite sandpile always converges to a unique fixed point, denoted by π(N ), where no more transition is possible (details in Section 2.2). The goal of this paper is to understand the structure of this fixed point.

Overview of the paper

In a previous paper [START_REF] Perrot | Strong emergence of wave patterns on Kadanoff sandpiles[END_REF], we completely described the asymptotic shape of configurations π(N ) for KSMs:

• they are covered by small wave patterns periodically repeated,

• except near column 0 where the configuration do not present any clear order, on an initial segment of asymptotically null relative size (and asymptotically infinite absolute size),

• and there is at most one couple of consecutive wave patterns which has a separation, of one column.

In the present paper, we extend this kind of result to DSMs. Of course, these two papers have some common points. In each of them, we start by relaxing the rule application, allowing to pass through transient configurations which are not non-increasing (Section 3). Then, in a first part we study the class of stable configurations which can be reached this way and, nevertheless, are also non-increasing (π(N ) is one of them). The study of these configurations can be decomposed into two subparts, which interestingly correspond to the dual feature of sand flows: fluid and continuous on a macroscopic point of view, solid and discrete on a microscopic point of view. During this step (Section 4), we cannot really say that new technical ideas are introduced compared to [START_REF] Perrot | Strong emergence of wave patterns on Kadanoff sandpiles[END_REF]. Nevertheless it is necessary to understand our progression, and important improvements in the presentation have been done:

• the role of the key-sequence ∆ 2 v has been clarified, which allows to simplify the macroscopic part of the study,

• the tricky microscopic part of the study has been decomposed in a sequence of facts, in the goal of a better readability,

• an automaton which controls the structure of stable configurations has been introduced (for KSMs, the corresponding automaton is trivial, and therefore did not need to be exhibited; at the opposite, it is very useful for general decreasing sandpile models).

Afterwards, in a second part we have to select the stable configuration π(N ) among stable configurations considered in the previous part. To do this, arguments used for general DSMs (based on the least action principle) are completely different from those used in [START_REF] Perrot | Strong emergence of wave patterns on Kadanoff sandpiles[END_REF] for KSMs (based on avalanche properties). From this study, we can split the states of the previous automaton, and therefore construct a thinner automaton controlling the structure of π(N ) (Section 5).

Finally, we use the latter automaton to get simple descriptions of π(N ) for three classes of decreasing sandpile rules (Section 6):

• when p ≤ 7,

• when r 1 is large (regarding r 2 , . . . , r p ),

• when r 1 is small (regarding r 2 , . . . , r p ).

KSMs appear as a very particular specification where r 1 is small. The simple description of fixed points is obtained from a study of the structure of thin automata. Given a decreasing sandpile rule we prove that π(N ) can be decomposed in three parts: from left to right,

• an unexplained part of negligible length (compared to other parts),

• a first periodic part (for which the sequence of values h i -h i+1 is periodic),

≥ r+r 1 with r = p j=1 r j .
Figure 1: The rule (2, 1) can be applied at column i if and only if ∆h i ≥ 5. For convenience, right will be referred to as the direction of grains fall.

• a second periodic part. These parts are linked by words of bounded length, and of course followed by the infinite part without any grain, on the right.

The results above extend the work of [START_REF] Perrot | Strong emergence of wave patterns on Kadanoff sandpiles[END_REF] in a large way. We shortly conclude with a discussion of the limits and future possibilities of this approach (Section 7).

Decreasing Sandpiles

The model

Decreasing sandpiles are discrete dynamical systems defined as follows. Configurations are made of sequences of sand columns, mathematically represented as non-increasing sequences of integers h = (h i ) i∈N such that h i is the number of grains stacked on column i, and we have a transition rule that makes grains move from column to column when the slope is too sharp. The slope at i is defined as the difference of height ∆h i = h ih i+1 . A decreasing sandpile rule is described by a p-tuple R = (r 1 , r 2 , . . . , r p ) with r 1 ≥ r 2 ≥ • • • ≥ r p > 0, and makes r = p j=1 r j grains fall from column i if the slope ∆h i is greater or equal to r + r 1 , and r j of those grains land on column i + j, as depicted on Figure 1. The slope must be greater or equal to r + r 1 so that the sandpile configuration remains a non-increasing sequence: as r grains leave column i and r 1 grains land on column i + 1, the slope at i is diminished by r + r 1 units, and must remain non-negative. The fact that the slope at other columns remains non-negative is ensured thanks to the non-increasing property of the rule R. Definition 1. A decreasing sandpile model (DSM) is a discrete dynamical system defined by the following two elements.

• Configurations. A configuration h is an ultimately null non-increasing sequence of integers, i.e. an element h of Z N such that:

there exists an integer k such that, for all i > k we have h i = 0, and for each i ∈ N, h ih i+1 = ∆h i ≥ 0.

The number of grains N of h is the sum

N = i∈N h i .
• Transition rule. A positive and non-increasing p-tuple r = (r 1 , r 2 , . . . , r p ) i.e. with r

1 ≥ r 2 ≥ • • • ≥ r p > 0. Let r = p j=1 r j .
From a configuration h such that for an integer i we have ∆h i ≥ r + r 1 , a transition at i leads to the configuration h such that:

-h i = h i -r, -h i+j = h i+j + r j for 1 ≤ j ≤ p.
In such a case, we denote

h i → h ,
Note that the rule application at i (which we also call fire at i) conserves the number of sand grains. We also denote h → h when the fired column is not given, and * → its reflexive and transitive closure. When ∆h i ≥ r + r 1 we say that column i is unstable. A configuration is stable, or a fixed point, if and only if it has no unstable column, and is finite if it contains a finite number of grains. We denote 0 ω the infinite sequence of 0. The DSMs we consider in Definition 1 are non-deterministic: the rule is applied once at each time step (it corresponds to an asynchronous update policy). An example of evolution to a fixed point is given on Figure 2.

Remark 1. The classical one-dimensional sandpile rule is the 1-tuple (1), and the Kadanoff sandpile rule with parameter p is the p-tuple (1, 1, . . . , 1).

To gain locality in the representation of configurations, that is, to gain independence on the position within the configuration, we conveniently represent them as sequences of slopes ∆h = (∆h i ) i∈N . In this representation, for example, the fixed point of Figure 2 is ∆π(26) = (4, 3, 1, 2, 1, 0 ω ). When not specified, the sequence of slopes is the default representation we will use to encode configurations throughout the paper. When we don't need to consider any particular representation, we will denote c a generic configuration.

Fixed points

As the models are non-deterministic, we first establish here the uniqueness of the fixed point for finite configurations (see [START_REF] Perrot | Technique et Science Informatiques -Automates cellulaires et réseaux d'automates : le rôle central de l'irrégularité[END_REF] for a more detailed presentation).

Proposition 1. Every configuration c converges to a unique fixed point π(c). Sketch of the Proof. The result follows from the conjunction of two facts (see for example [START_REF] Baader | Term rewriting and all that[END_REF]). Diamond property. Assume that, from a configuration c, two columns i and j with i = j are unstable, such that c

E(h) = i≥0 hi j=1 j = i≥0 h i (h i + 1)
2 .

The energy of a grain is its height, and the energy of the configurations is the sum of grain energies. One easily checks that this energy function on configurations verifies:

• the energy strictly decreases during each transition,

• the energy of any configuration is non-negative.

This proves the termination of the evolution on configurations.

The aim of the present paper is to describe the fixed point reached from the configuration (N, 0 ω ). Let us abuse notation and also denote N this initial configuration, to be consistent with the notation π(N ).

Our results

In a previous work we analyzed the fixed point for Kadanoff rules given by p-tuples (1, 1, . . . , 1), and get the following result (• is a concatenation symbol added for clarity). Words denoted w i are a shorthand for w i (N ), as they depend on the number of grains N but this value is clear from the context. Theorem 1 ([21]). For the Kadanoff rule of parameter p > 1, we have

∆π(N ) = w 1 • (p • . . . • 2 • 1) a • 0 • (p • . . . • 2 • 1) b • 0 ω with a, b ∈ N and |w 1 | in O(log N ).
∆π(N ) denotes the sequence of slopes of the fixed point. The width of a configuration is the maximal index of a non-empty column: w(∆h) = max{k | ∆h k > 0}. One can easily prove (see [START_REF] Perrot | Strong emergence of wave patterns on Kadanoff sandpiles[END_REF]) that w(∆π(N )) is in Θ( √ N ), so the result above describes the quasi-totality of ∆π(N ). Studying some other examples, we conjecture the following generalization of Theorem 1.

Conjecture 1. Given a transition rule R = (r 1 , r 2 , . . . , r p ), there exist five words w 1 , w 2 , w 3 , w 4 , w 5 such that for all integer N ≥ 0 we have In this paper, we prove this conjecture for a large set of rules (r 1 , r 2 , . . . , r p ). More precisely, for any rule we exhibit a finite state automaton which controls the sequence ∆π(N ) starting from a column in O(log N ). In numerous cases, this automaton has only two cycles, which proves the conjecture. More precisely, we have the following theorem.

∆π(N ) = w 1 • (w 2 ) a • w 3 • (w 4 ) b • w 5 • 0 ω with a, b ∈ N, |w 1 | in O(log N ),
Theorem 2. Conjecture 1 holds in the following cases.

• p small: p ≤ 7.

• r 1 large: for each (r 2 , . . . , r p ), there exists a constant M such that when r 1 ≥ M then Conjecture 1 holds.

• r 1 small: for each (r 2 , . . . , r p ), there exists a constant m such that when r 1 ≤ m then Conjecture 1 holds.

Though, for almost all rules we picked at random, our approach allowed to prove Conjecture 1, we have found some specific rules where the above mentioned automaton has more than two cycles. This yields that our arguments are not sufficient to completely prove the conjecture, and thus it remains open in the general case.

Rule extension and shot sequence

3.1. Shot sequence and lattice structure Definition 2. Given a decreasing sandpile model, we denote C(N ) the set of reachable configurations from (N, 0 ω ). Formally,

C(N ) = {c | (N, 0 ω ) * → c}.
In this subsection we concentrate on configurations of the set C(N ), in order to define a third representation of configurations (with height and slope sequences) called shot sequence, which is relative to the initial configuration (N, 0 ω ). The shot sequence of a configuration c ∈ C(N ) is the sequence s = (s i ) i∈N where s i is the number of times the rule has been applied on column i, in the evolution from (N, 0 ω ) to c. For example, the shot sequence of the stable configuration on Figure 2 is s = (5, 1, 1, 0 ω ). The next property is straightforward to obtain.

Proposition 2. The shot sequence of each configuration in C(N ) is unique.

More interestingly, following the developments of [START_REF] Goles | The structure of a linear chip firing game and related models[END_REF], decreasing sandpile models have a graded lattice structure. First a lemma on how to construct the meet.

Lemma 1. Let s and s be the shot sequences of two configurations in C(N ). Then there exists a configuration of C(N ) whose shot sequence (s i ) i∈N is such that s i = max{s i , s i } for all i ∈ N.

Proof. The proof follows exactly the lines of Section 3 from [START_REF] Goles | The structure of a linear chip firing game and related models[END_REF].

The order → on C(N ) is thus closed by inf, and contains a maximal element (N, 0 ω ), it is consequently a lattice (see for example [START_REF] Davey | Introduction to Lattices and Order[END_REF]). The gradation is given by the function s → s i from C(N ) to N. Theorem 3. C(N ) endowed with * → has a graded lattice structure.

Main equations

For a given configuration in C(N ), the three representations h (heights), ∆h (slopes) and s (shot sequence) are obviously linked. In particular, counting grains which come and go on column i, we get ∀i ≥ p, h i = -rs i + r 1 s i-1 + r 2 s i-2 + . . . + r p s i-p .

In order to extend the above relation, we set s -p = N rp s -j = 0 for 1 ≤ j and j = p which emulates the fact that column 0 is the only column receiving N units of sand grains: r p units for each virtual rule application at -p (notice that N rp is not necessarily an integer, but it has no consequences). With this convention, we can claim that ∀i ≥ 0, h i = -rs i + r 1 s i-1 + r 2 s i-2 + . . . + r p s i-p .

(1)

We will not use directly this equation, but two equivalent forms (for ultimately null sequences) using derivatives of the shot sequence s. The sequence ∆s is defined by ∀i ≥ -p, ∆s i = s is i+1 and the sequence ∆ 2 s is defined by ∀i ≥ -p, ∆ 2 s i = ∆s i -∆s i+1 .

The first equality is obtained by finite derivation, i.e. by the difference between two consecutive equations of type [START_REF] Baader | Term rewriting and all that[END_REF]. ∀i ≥ 0, ∆h i = -r∆s i + r 1 ∆s i-1 + r 2 ∆s i-2 + . . . + r p ∆s i-p .

(

) 2
The second one is obtained from Equation (2) by substitution. Notice that ∆s i-= ∆s i + i k=i-∆ 2 s k and r = p k=1 r k . We get for all i ≥ 0,

∆h i = -r∆s i + r 1 (∆s i + ∆ 2 s i-1 ) + r 2 (∆s i + ∆ 2 s i-1 + ∆ 2 s i-2 ) + . . . + r p (∆s i + p j=1 ∆ 2 s i-j ) i.e. ∀i ≥ 0, ∆h i = r∆ 2 s i-1 + (r 2 + . . . + r p )∆ 2 s i-2 + . . . + r p ∆ 2 s i-p . (3)
We will focus on the shot sequence. We slightly reinforce Conjecture 1, by the following similar conjecture on ∆ 2 v. Note that Conjecture 1 is a consequence of Conjecture 2 and Equation (3).

Conjecture 2. Given a transition rule R = (r 1 , r 2 , . . . , r p ), there exist five words w 1 , w 2 , w 3 , w 4 , w 5 such that for all integer N ≥ 0, the sequence ∆ 2 s corresponding to π(N ) can be written as Our goal is to prove Conjecture 2.

∆ 2 s = w 1 • (w 2 ) a • w 3 • (w 4 ) b • w 5 • 0 ω with a, b ∈ N, |w 1 | in O(log N ),

Rule extension

In the study of decreasing sandpile models, it is useful in a first step to relax some conditions in two manners: first allow not non-increasing ultimately null sequences for configurations, and second allow a transition at i even when ∆h i < r + r 1 . To gain in clarity, let us add notations to differentiate valid firings (all the firings considered so far) from invalid firings. Notation 1. c i → c denotes a valid firing where ∆h i ≥ r +r 1 . However, c i c will denote a possibly invalid firing, where the condition ∆h i ≥ r + r 1 is not ensured. Given a decreasing sandpile model and N ∈ N, we denote C(N ) + the set of (not necessarily non-increasing) configurations which are reachable from (N, 0 ω ). Formally,

C(N ) + = {c | (N, 0 ω ) * c}.
The set Π(N ) is the subset of C(N ) + formed by generalized configurations which are stable and non-increasing. Notice that C(N ) + is an infinite set, while C(N ) and Π(N ) both are finite subsets of C(N ) + . We have

Π(N ) ∩ C(N ) = {π(N )}.
We can extend the definition of shot sequence to configurations of C(N ) + , and Equation (1) still holds for any configuration of C(N ) + .

Remark 2. For all non-negative ultimately null sequence s, there exists a unique configuration c of C(N ) + such that s is the shot sequence of c. Moreover, if c, c ∈ C(N ) + with respective shot sequences s and s , we have the equivalence

c * c ⇐⇒ ∀i ≥ 0, s i ≤ s i .
By a simple derivation of Equality (3), we also have the following characterization of elements of Π(N ).

Remark 3. Let c ∈ C(N ) + with s the shot sequence of c, then c ∈ Π(N ) if and only if ∀i ≥ 0, 0 ≤ r∆ 2 s i-1 + (r 2 + . . . + r p )∆ 2 s i-2 + . . . + r p ∆ 2 s i-p < r + r 1 . (4)

Study of static constraints on stable configurations

In the remaining of the paper we assume that p ≥ 2. Indeed, the special case when p = 1 can be easily reduced to the classical SPM case where r 1 = 1, for which ∆h and ∆ 2 s are well known, see for example [START_REF] Goles | Games on line graphs and sand piles[END_REF]. Let us fix a decreasing sandpile rule R = (r 1 , . . . , r p ). By definition, the sequence of slopes of any configuration in Π(N ) belongs to the language 0 + 1 + . . . + (r + r 1 -1) * 0 ω .

This section concentrates on restricting the language of configurations in Π(N ) via a static study of fixed points. That is, we will basically make use of Equation ( 3) and the fact that configurations of Π(N ) are stable, non-increasing, and ultimately null. The developments will lead to the definition of an automaton (depending on R) recognizing the sequence of slopes of all configurations in Π(N ).

Remark 4. Our scope is restricted to configurations of the set Π(N ). Hence h and s will always denote the respective sequences of heights and shots of a configuration belonging to Π(N ). This will only be recalled in Theorem 4, concluding the section.

From Equation (3), we are going to construct a recurrence equation describing fixed points from left to right: given (∆ 2 s j ) i-p<j<i we will express (∆ 2 s j ) i-p+1<j<i+1 .

In order to study its convergence, it will be presented in matrix form as a dynamical system from Z p-1 to Z p-1 , which we will call perturbed weighted linear system (Subsection 4.1). This new discrete dynamical system will describe the fixed point from left to right, and at each step a new value (at i in the example above) will be computed with the following process: take a linear transformation of the current values, and add the discrete perturbation ∆hi r . We will study the convergence of the perturbed weighted linear system (Subsections 4.2, 4.3 and 4.4), leading to the definition of the above mentioned automata (called recurrence automata), accepting sequences of slopes of configurations in Π(N ), starting from a column of index logarithmic in the number of grains (Subsection 4.5).

The main objective of this paper is to study π(N ) ∈ Π(N ). Talking about all the configurations of Π(N ) is not a goal in itself, but a fundamental step which reflects the fact that constraints we exploit in this section are quite general: using static equations we set up restrictions on the language of sequences of slopes applying to any configuration in Π(N ).

The perturbed weighted linear system

For p ≥ 2, we can rewrite Equation ( 3) to get the recurrence relation

∆ 2 s i-1 = - 1 r (r 2 +. . .+r p )∆ 2 s i-2 +(r 3 +. . .+r p )∆ 2 s i-3 +. . .+r p ∆ 2 r i-p + ∆h i r .
(5) To put the recurrence relation [START_REF] Duchi | Bidimensional Sand Pile and Ice Pile Models[END_REF] in matricial form, let

∆ 2 S i =      ∆ 2 s i-p+1 . . . ∆ 2 s i-2 ∆ 2 s i-1      M R =      0 1 0 . . . 0 0 1 r p r p + r p-1 . . . r p + r p-1 + • • • + r 2      .
We also define ∆S i = t (∆s i-p+1 , . . . , ∆s i-1 , ∆s i ) with t X the transpose of vector X, especially for Subsection 4.3.

Remark 5. Note that ∆ 2 S i ∈ Z p-1 can be computed from ∆S i alone. As an example, if ∆S i = t (5, 5, 4, 4, 3) then ∆ 2 S i = t (0, 1, 0, 1). To avoid confusion, also remark that ∆ 2 s i is not the last component of ∆ 2 S i , but the last component of ∆ 2 S i+1 .

With E p-1 = t (0, . . . , 0, 1), Equation (5) becomes

∆ 2 S i = - 1 r M R ∆ 2 S i-1 + ∆h i r E p-1 . (6)
We call the system of Equation ( 6) perturbed weighted linear system, from Z p-1 to Z p-1 . It is composed of two parts.

• A linear map M R : R p-1 → R p-1 , which
shifts all the values one row upward, -for the last component, computes a weighted linear combination.

• A perturbation added to the last component, so that the result lies in Z.

Initialization of the dynamical system

With the convention used in Equation ( 1) for negative values of s, we can initialize the perturbed weighted linear system for p > 2 with

∆ 2 S -1 =        ∆ 2 s -p ∆ 2 s -p+1 . . . ∆ 2 s -3 ∆ 2 s -2        =        s -p -2s -p+1 + s -p+2 s -p+1 -2s -p+2 + s -p+3 . . . s -3 -2s -2 + s -1 s -2 -2s -1 + s 0        =        N rp 0 . . . 0 s 0        (7)
For the particular case p = 2, the starting point ∆ 2 S -1 is reduced to the value N rp + s 0 . In any case ∆ 2 S -1 is pretty well known: s 0 remains an uncertainty but for configurations of the set Π(N ) we can actually bound it quite tightly with

N r + r 1 ≤ s 0 ≤ N r , (8)
the left inequality coming from the fact that we can begin the evolution by N r+r1 valid firings at column 0 (hence if we do not perform them then the resulting configuration is unstable); and the right inequality from the fact that column 0 never receives grains and loses r grains each time it is fired, hence after N r firings it is empty (and if its sand content is negative then it is impossible to get a non-increasing integer sequence that is ultimately null, two requirements to be a configuration of Π(N )).

From Equation (8) we get the double inequality

N r + r 1 ≤ ∆ 2 S -1 ∞ ≤ N r + N r p ≤ 2N r p . (9)
Equation ( 9) will play a role in the study of the convergence time. An example of dynamics of the perturbed weighted linear system can be seen on Figure 3.

Properties of the discrete perturbation

Here are the only two facts we will consider in this subsection. They directly come from the definitions, and can be considered as static constraints:

• configurations of Π(N ) are stable (Equation ( 10)),

• (h i ) i∈N , (∆h i ) i∈N , (s i ) i∈N , (∆ 2 s i ) i∈N are integer sequences (Equation (11)). All columns of Π(N ) are stable, hence 0 ≤ ∆h i < r + r 1 , or equivalently ∀i ≥ 0, 0 ≤ ∆h i r < 1 + r 1 r ≤ 2. ( 10
)
The discrete perturbation is therefore bounded, but there is more than that. As mentioned above, the perturbed weighted linear system evolves in Z p-1 , but the result of the linear transformation (whose matrix is -1 r M R ) may sometimes not It illustrates the dynamics of the perturbed weighted linear system, and its convergence to values such that ∆ 2 s i ∈ {0, 1}. Note the addition of virtual elements (∆s i ) i∈{-1,...,-p} (unfilled bullets on the left side).

be an integer. Consequently the perturbation added must lead to an integer, because ∆ 2 s i-1 ∈ Z. Let us denote by L R the line vector formed by the last row of matrix M R , i.e.

L R = (r p , r p + r p-1 , . . . , r p + r p-1 + . . . + r 2 ).

We necessarily have

- 1 r L R ∆ 2 S i-1 + ∆h i r ∈ Z ⇐⇒ ∆h i ≡ L R ∆ 2 S i-1 mod r, (11)
which means that, knowing ∆ 2 S i-1 , there is at least one and at most two choices for ∆h i (from the bounds of Equation ( 10)). This will be an important argument in the construction of recurrence automata (Subsection 4.5).

Convergence at a large scale

In this subsection we are going to prove that the system converges rapidly to a bounded region, independent of the number N of grains involved. The introduction of the sequence ∆ 2 s allows a simpler proof than in [START_REF] Perrot | Strong emergence of wave patterns on Kadanoff sandpiles[END_REF] of the next lemma.

Lemma 2. There exist a positive real α (not depending on N ) and an integer

n 0 in O(log N ) such that, for all i ≥ n 0 we have |∆ 2 s i | ≤ α.
Proof. We first have to study M R . We recall that, for each (complex) square matrix A, the spectrum of A, denoted by Sp(A), denotes the set of eigenvalues of A, and the spectral radius of A, denoted by ρ(A), is the maximum moduli of values in Sp(A). The matrix M R is a companion matrix of characteristic polynomial

R(x) = r p + (r p + r p-1 ) x + . . . + (r p + r p-1 + . . . + r 2 ) x p-2
We use a classical result due to Eneström and Kakeya (see for example [START_REF] Gardner | Some generalizations of the eneströmkakeya theorem[END_REF]): if P (x) = n k=0 a k x k is a (real) polynomial with all a k > 0, then the modulus of every root λ verifies min 0≤k<n-1

a k a k+1 ≤ |λ| ≤ max 0≤k<n-1 a k a k+1 .
Applied to R(x), we get 1 r ≤ |λ| ≤ r-1 r , since each coefficient a of R is such that 1 ≤ a < r and the sequence of coefficients of R is (strictly) increasing with the degree. In particular, ρ(M R ) ≤ r-1 r < 1. We will use a matrix norm, i.e. a norm on the matrix space such that, for each pair A, B of matrices and each vector U , we have AB ≤ A B and A U ∞ ≤ A U ∞ . For any > 0 and any matrix A, there exists a matrix norm such that A < ρ(A) + (see for example [START_REF] Isaacson | Analysis of Numerical Methods[END_REF] Theorem 3 page 12). If we apply it with A = M R , then there exists such that ρ(M R ) + < 1, for which we get M R < 1.

Iterating the recurrence relation [START_REF] Durand-Lose | Parallel transient time of one-dimensional sand pile[END_REF] and substituting, we have

∆ 2 S i = - 1 r i+1 M i+1 R ∆ 2 S -1 + i j=0 ∆h j r i+1-j M i-j R E p-1 .
Using the norm matrix, we get

∆ 2 S i ∞ ≤ M R r i+1 ∆ 2 S -1 ∞ + 1 r i j=0 ∆h j M R r i-j E p-1 ∞ .
It holds that ∆h

j ≤ r + r 1 , E p-1 ∞ = 1, ∆ 2 S -1 ∞ ≤ 2N rp and M R ≤ 1, thus ∆ 2 S i ∞ ≤ 2N r p r i+1 + r + r 1 r i j=0 1 r i-j ≤ 2N r p r i+1 + r + r 1 r 1 1 -1 r . As a consequence, for i ≥ log N log r we have ∆ 2 S i ∞ ≤ 2 r p r + r + r 1 r -1
which is the result.

Convergence at a small scale

We know that rapidly, the value ∆ 2 s i enters in a bounded region, and afterwards stays inside. We now study what happens in this bounded region. We use an indirect way by studying the sequence (∆s i ) i∈N .

Notation 2. Recall that ∆S i = t (∆s i-p , . . . , ∆s i-2 , ∆s i-1 ). Let m i = 1 r (r p , . . . , r 1 )∆S i denote the mean of ∆S i weighted by (r p , . . . , r 1 ), and m i (resp. m i ) denote the minimal (resp. maximal) value of ∆S i .

With these notations Equation (2) can be rewritten as

∀i ≥ 0, ∆s i = m i - ∆h i r . ( 12
)
Lemma 3. For any positive integer i, there exists d ≤ (m im i + 1)p, such that for all k ≥ i + d we have ∆ 2 s k ∈ {0, 1}.

A similar lemma stands in [START_REF] Perrot | Strong emergence of wave patterns on Kadanoff sandpiles[END_REF]. We have tried to improve the readability of the proof by decomposing it in a sequence of facts.

Proof. We divide our progression in facts. From Fact 2, we can deduce Fact 3, which is the initialization of the induction of Fact 5. On the other hand, the inequality of Fact 4 is necessary for the induction step of Fact 5. At the end, Facts 1 and 5 allow to conclude the proof of Lemma 3 Fact 1. We have the inequality

∀i ≥ 0, ∆s i ≥ m i -1. ( 13
)
Proof of Fact 1. We have

∀i ≥ 0, ∆s i = m i - ∆h i r ≥ m i - ∆h i r .
We also know that ∆hi r < 1 + r1 r ≤ 2 by Equation ( 10), therefore ∆s i > m i -2, i.e. ∆s i ≥ m i -1 since ∆s i is an integer.

Fact 2. The sequence (m j ) j∈N is non-increasing.

Proof of Fact 2. We obviously have m j+1 ≤ max{m j , ∆s j }. From Equality [START_REF] Goles | Games on line graphs and sand piles[END_REF] we have ∆s j ≤ m j ≤ m j , thus max{m j , ∆s j } = m j . This implies that m j+1 ≤ m j , thus the sequence (m j ) j∈N is non-increasing. Fact 3. There exists d ≤ (m im i + 1)p, such that either ∆S i+d is a uniform vector, or ∆s i+d < m i+d .

Proof of Fact 3. We prove that if the first case does not hold, then the second does. Assume that for each d ≤ (m im i + 1)p, ∆S i+d is not a uniform vector. In this case, we have ∆s i+d ≤ m i+d < m i+d , which gives ∆s i+d ≤ m i+d -1, since ∆s i+d and m i+d both are integers. Since the sequence (m i+d ) 0≤d ≤(mi-m i +1)p is non-increasing (Fact 2), for any integer d with d ≤ d ≤ (m im i + 1)p, we also have ∆s i+d ≤ m i+d -1 ≤ m i+d -1.

Thus for 0 ≤ d ≤ (m im i )p, every p iterations the maximal value has strictly decreased: m i+d -1 ≥ m i+d +p . It follows, repeating the argument, that for any integer > 0 such that d + p ≤ (m i -m i +1)p, we have m i+d -≥ m i+d + p . In particular (taking d = 0 and = m im i + 1), we get

m i -1 = m i -(m i -m i + 1) ≥ m i+(mi-m i +1)p . Thus m i > m i+(mi-m i +1)p ≥ ∆s i+(mi-m i +1)p .
See Figure 4 for an illustration.

At this point we are sure that, at least once, the perturbed weighted linear system must have computed a new value strictly smaller than the p -1 previous values. Indeed, let

d 0 = min d | ∆s i+d = min{∆s i+d | 0 ≤ d ≤ (m i -m i + 1
)p} be the smallest integer d such that 0 ≤ d ≤ (m im i + 1)p and, for any integer d with 0 ≤ d ≤ (m im i + 1)p, we have ∆s i+d ≤ ∆s i+d . From the previous inequality we have

m i > ∆s i+(mi-m i +1)p ≥ ∆s i+d0 .
It follows that we have ∆s i+d0 < m i+d0 , since by minimality of d 0 the p values ∆s j with i + d 0p ≤ j ≤ i + d 0 -1 are such that ∆s j > ∆s i+d0 .

∆s j i j m i m i m i -1 ∆s i+d0 + 1 ∆s i+d0 i + d 0 (m i -m i + 1)p
∀j ≥ 0, m j+1 ≤ m j - r 1 r (m j -∆s j ). (14)
In particular,

• when ∆s j = m j we have m j+1 ≤ m j ,

• when ∆s j < m j we have m j+1 ≤ m j -r1 r . Proof of Fact 4. By definition, we have the following equalities.

m j+1 = 1 r p k=1 r k ∆s j+1-k = 1 r p k=2 (r k -r k-1 + r k-1 )∆s j+1-k + r 1 ∆s j = 1 r p k=2 (r k -r k-1 )∆s j+1-k + p k=2 r k-1 ∆s j+1-k + r 1 ∆s j = 1 r p k=2 (r k -r k-1 )∆s j+1-k + p-1 k =1 r k ∆s j-k + r 1 ∆s j = 1 r p k=2 (r k -r k-1 )∆s j+1-k + p k =1 r k ∆s j-k -r p ∆s j-p + r 1 ∆s j . We have r k -r k-1 ≤ 0 and, for 2 ≤ k ≤ p + 1, m j ≤ ∆s j+1-k . Therefore, (r k -r k-1 )m j ≥ (r k -r k-1 )∆s j+1-k and -r p ∆s j-p ≤ -s p m j which give p k=2 (r k -r k-1 )∆s j+1-k -r p ∆s j-p ≤ p k=2 (r k -r k-1 )m j -r p m j = -r 1 m j . Moreover, p k =1 r k ∆s j-k = rm j . We can conclude that m j+1 ≤ 1 r rm j + r 1 (∆s j -m j )
which is the announced inequality.

Fact 5. Let d be given by Fact 3. The sequence (∆s k ) k≥i+d is non-increasing.

Proof of Fact 5. We will prove by induction on k that, for each j such that i + d ≤ j ≤ k, we have ∆s j ≤ ∆s j-1 . It holds for k = i + d. Now assume that the property is true for a fixed integer k, with k ≥ i + d. This implies the following properties:

• the finite sequence (m j ) i+d≤j≤k+1 is non-increasing,

• for each j such that i + d ≤ j ≤ k + 1, we have m j = ∆s j-1 .

If ∆S k+1 is a uniform vector, then ∆s k+1 ≤ m k+1 = ∆s k and we are done. Otherwise, let k be the largest integer such that k < k and ∆s k > ∆s k (notice that k exists and is larger or equal to kp + 2, from the induction hypothesis, because ∆S k+1 is assumed not to be a uniform vector). Since 10)), we have m k +1 -1 -r1 r < ∆s k +1 from Equation [START_REF] Goles | Games on line graphs and sand piles[END_REF]. On the other hand, from Inequality [START_REF] Goles | The structure of a linear chip firing game and related models[END_REF]

∆h k +1 r < 1 + r1 r (Relation (
we get m k +2 ≤ m k +1 -r1 r , since ∆s k +1 < m k +1 by maximality of k . Consequently, m k +2 ≤ m k +1 - r 1 r < ∆s k +1 + 1.
Thus, since (m j ) i+d≤j≤k+1 is non increasing, we have

∆s k+1 ≤ m k+1 ≤ m k +2 < ∆s k +1 + 1 = ∆s k + 1
which gives ∆s k+1 ≤ ∆s k , since ∆s k+1 and ∆s k are integer values. This finishes the induction.

To conclude the proof of Lemma 3, remark that Fact 5 can be rewritten as: for k ≥ i + d -1, we have ∆ 2 s k ≥ 0. Moreover, from Fact 5, Inequality [START_REF] Goles | Sandpile models and lattices: a comprehensive survey[END_REF] gives for k ≥ i + d, that ∆s k ≥ ∆s k-1 + 1, which can be rewritten as: for k ≥ i + d -1, we have ∆ 2 s k ≤ 1. This finishes the proof, since all values ∆ 2 s k are integers.

Overall convergence

We can combine the developments of Subsections 4.2 and 4.3 to get a global result on the convergence of the perturbed weighted linear system. We can also easily add a constraint. Let us recall that L R denotes the line vector of Z p-1 defined by L R = (r p , r p + r p-1 , . . . , r p + r p-1 + . . . + r 3 , r p + r p-1 + . . . + r 2 ).

Equality (3) can be rewritten as

∀i ≥ 0, ∆h i+1 = L R ∆ 2 S i + r∆ 2 s i . ( 15
)
Proposition 3. There exists a column n 1 in O(log N ), such that for all i ≥ n 1 we have ∆ 2 s i ∈ {0, 1}.

Moreover, if ∆ 2 s i = 1 then L R ∆ 2 S i < r 1 .
Proof. From Lemma 2, there exist a constant α and a column n 0 in O(log N ) such that m n0m n0 < α. We can therefore apply Lemma 3, giving an index d in O(m n0m n0 ), thus d is a constant, such that the conclusion of Lemma 3 is verified for

n 1 = n 0 + d in O(log N ).
For the second part, remark that when ∆ 2 s i = 1, Equation ( 15) becomes ∆h i+1 = L R ∆ 2 S i + r. Since the stability gives ∆h i+1 < r 1 + r, we get that L R ∆ 2 S i < r 1 . Remark 6. Note that this result is in accordance with the example of Figure 3: from column 7 the sequence (∆ 2 s i ) i≥7 belongs to {0, 1} ω .

Recurrence automata

Proposition 3 gives, after an exponentially quick convergence, i.e., for a column n 1 ∈ O(log N ), a very restricted set of possibilities for the sequence (∆ 2 s i ) i≥n1 . Let us recall that this sequence represents a configuration in Π(N ), and knowing (∆ 2 s i ) i≥n1 allows to reconstruct the sequence (∆h i ) i≥n1+p of slopes (using Equation ( 15)). The aim is now to introduce convenient tools to work on these restrictions of language: recurrence automata, recognizing exactly the possible sequences (∆ 2 s i ) i≥n1 induced by Proposition 3 (in the literature, such automata are also referred to as Rauzy graphs of the corresponding language). We will thereafter work on these automata, in order to add more restrictions leading to a more precise characterization of the shape of the fixed point π(N ) ∈ Π(N ).

Let us provide the reader with intuitions on the coming definition. States of the automata will correspond to vectors ∆ 2 S i which are elements of {0, 1} p-1 (to lighten the notations, we present state vectors as words), and transitions to iterations of the perturbed weighted linear system: when going from ∆ 2 S i to ∆ 2 S i+1 , we will label the transition with the last bit of ∆ 2 S i+1 , i.e. ∆ 2 s i . According to Proposition 3, there are at most two possible transitions from one state, depending on the value of L R ∆ 2 S i . We will have a transition from one state q representing a ∆ 2 S i to another state q representing ∆ 2 S i+1 if three conditions are verified:

• q and q must have most components in common (because the shifting of ∆ 2 S i accounts for a large part of ∆ 2 S i+1 ),

• we have ∆ 2 s i = 1 only when it is possible according to Proposition 3,

• and the label of the transition is ∆ 2 s i .

Let us finally say a word about the initial and accepting states. With the asymptotic bound of Proposition 3, we do not know from which state to begin, and will therefore consider the whole set of states as potential initial states. As we are interested in recognizing the significant part2 of the sequence (∆ 2 s i ) i∈N starting from some index, we will only consider words ending with 1, which correspond to taking all states ending with 1 as final states.

Definition 3. Given a decreasing sandpile rule R = (r 1 , . . . , r p ), let A R be its recurrence automaton, which is the finite state automaton defined by:

• the set of states Q R = {0, 1} p-1 ,
• the alphabet Σ = {0, 1},

• the set of transitions → R : Q R × Σ × Q R where q a -→ A R q , with q = q 1 q 2 . . .q p-1 and q = q 1 q 2 . . .q p-1 , if and only if the following three conditions hold:

(C 1 ) q 1 q 2 . . .q p-2 = q 2 q 3 . . .q p-1 ,

(C 2 ) q p-1 = 1 only if L R q < r 1 , (C 3 ) a = q p-1 , • the set of initial states is S R = Q R = {0, 1} p-1 ; • the set of final states is T R = {0, 1} p-2 × {1}.
Let L(A R ) denote the language of finite words recognized by A R .

An example of recurrence automaton is given on Figure 5. In these automata, a transition corresponds to an iteration of the perturbed weighted linear system, and goes from a state q corresponding to a ∆ 2 S i , to a state q corresponding to ∆ 2 S i+1 . States are therefore associated with equivalence classes of ∆ 2 S i ∈ {0, 1} p-1 . There are at most two transitions according to the newly computed ∆s i :

• one if ∆s i equals ∆s i-1 (a 0 is appended to the state),

• one if ∆s i equals ∆s i-1 -1 (a 1 is appended to the state).

Furthermore, the second transition exists if and only if it does not contradict Proposition 3. Theorem 4 can therefore be considered as a convenient rephrasing of Proposition 3, and a step towards an asymptotic characterization of (∆ 2 s i ) i∈N . Theorem 4. For all ∆ 2 s ∈ Π(N ), there exists a column n 2 in O(log N ) such that the significant part of (∆ 2 s i ) i≥n2 belongs to L(A R ). We point out that the recurrence automaton only depends on the transition rule, and not on the number N of grains initially stacked on column 0. Defining recurrence automata is a step towards an asymptotic characterization of (∆ 2 s i ) i∈N according to the rule R and the number of grains N . Indeed, Theorem 4 states that the sequence (∆ 2 s i ) i∈N of π(N ) is, starting from an index logarithmic in N , recognized by the recurrence automata A R . Many words are recognized by A R , and it remains to restrict this set of possibilities in order to characterize precisely π(N ).

Recurrence automata can be simplified using the notion of ultimately relevant state. A state is recurrent if there exists a directed cycle containing this state. A state is ultimately relevant if there exists a path from a recurrent state to this state (the set of recurrent states is included in the set of ultimately relevant states). States that are not ultimately relevant will never be visited after a constant number of iterations (when p is fixed), therefore we will work on the simplified automata A R , that is the restriction of A R obtained by only keeping ultimately relevant states, and transitions between ultimately relevant states.

Theorem 5. For all ∆ 2 s ∈ Π(N ), there exists a column n 3 in O(log N ) such that the significant part of (∆ 2 s i ) i≥n3 belongs to L(A R ).

Proof. The theorem above is a straightforward consequence of Theorem 4. Since A R contains 2 p-1 states, it suffices to take n 3 = n 2 + 2 p-1 . Once an ultimately relevant state is reached, then all the successive states are necessarily ultimately relevant too, and such a state is reached after at most 2 p-1 steps.

Study of fixed points through the least action principle

In the previous section, we have limited the possible shapes of elements in Π(N ). This limitation is based on the recurrence relation, which expresses the stability of configurations in Π(N ). We now reinforce the limitation using the least action principle, which gives a particular position for π(N ) within the set Π(N ).

Least action principle

Theorem 6 (Least action principle). For all c ∈ Π(N ), we have π(N ) * c.

A Fey, L. Levine and Y. Peres give in [START_REF] Fey | Growth rates and explosions in sandpiles[END_REF] a proof of Theorem 6 in a more general framework. We give below a short proof for DSMs.

Proof. Let c 0 , c 1 , . . . , c t be a sequence of configurations of C(N ) such that, c 0 = (N, 0 ω ), c t = π(N ), and for each k, 0 ≤ k < t, there exists a column i k such that c k i k → c k+1 . We will prove by induction on k that for any c ∈ Π(N ) we have c k * c.

The initialization k = 0 is given by definition of Π(N ). Now, let k < t and assume that c k * c. Assume moreover that the number of firings at column i k is equal for configurations c k and c. By definition, column i k is unstable for c k . Since no other firing is done at i k , column i k is also unstable for c, which is a contradiction. Therefore, the number of firings at i k for c k is strictly smaller than the number of firings at i k for c, which straightforwardly gives c k+1 * c, and finishes the induction.

A particular consequence is that π(N ) = c k * c.

Theorem 6 claims that π(N ) is the minimum of the ordered set (Π(N ), * ), while Theorem 3 claims that π(N ) is the maximum of the ordered set (C(N ), * → ).

Least action principle and 10 01 flip

The least action principle seems difficult to use as expressed by Theorem 6, therefore we introduce the following lemma which gives a criterion for a word to be the significant part of π(N ). This criterion is less precise (in terms of characterization) than the least action principle, but we will see that it is useful to restrict the set of words accepted by recurrence automata.

Lemma 4 (necessary criterion for factors of π(N )). Let w = w 2 10 w 3 01 w 4 be a word on the alphabet {0, 1} with |w 2 | ≥ p, accepted by the recurrence automaton A R . If w is a suffix of the significant part of the shot sequence ∆ 2 s related to π(N ), then

• when w 4 = , w = w 2 01 w 3 10 w 4 is not accepted by A R ,

• when w 4 = , w = w 2 01 w 3 1 is not accepted by A R .

Proof. Assume that w0 ω is a suffix of the sequence ∆ 2 s of π(N ), thus ∆ 2 s = w 1 w0 ω , where w 1 is a finite word in the alphabet Z. Consider the ultimately null sequence v such that ∆ 2 s = w 1 w 0 ω . We have

∆ 2 (s -s ) = 0 |w1|+|w2| 1(-1) 0 |w3| (-1)1 0 ω thus we get ∆(s -s ) = 0 |w1|+|w2|+1 (-1) 0 |w3|+1 1 0 ω and s -s = 0 |w1|+|w2|+2 1 |w3|+2 0 ω . Since ∆ 2 s |w1|+|w2|+|w3|+4 = 1 and ∆ 2 s i ≥ 0 for i > |w 1 |, it follows that ∆s |w1|+|w2|+|w3|+4 = 1 and ∆s i > 0 for |w 1 | < i ≤ |w 1 | + |w 2 | + |w 3 | + 4.
Repeating the argument, we get that s |w1|+|w2|+|w3|+4 = 1 and s i > 0, for

|w 1 | < i ≤ |w 1 | + |w 2 | + |w 3 | + 4. It follows that s = s -0 |w1|+|w2|+2 1 |w3|+2 0 ω is non negative.
Consequently there exists a configuration c of C(N ) + whose shot sequence is s . Moreover, from Remark 2 we have c * π(N ), since ∀i ≥ 0,

s i ≤ s i .
To finish, assume for the contradiction that w is accepted by A R . Then, in this case, c is stable. Indeed, Inequality (4) is satisfied for any i ≥ 0:

• for i ≤ |w 1 |, since s j = s j for all j with 0 ≤ j ≤ |w 1 |,
• for i > |w 1 |, because of the acceptance by the recurrence automaton.

From the least action principle, we deduce that π(N ) * c, which enforces that c = π(N ), a contradiction.

Fixed point automata

We will now use the criterion of Lemma 4 to select words satisfying it, among words accepted by A R . The main idea is that if u10u and u01u both are strict prefixes of words accepted by A R , and A R gives two choices for the next bit, then u10u 1 is the only possible prefix which is compatible with π(N ), because any word accepted by A R with prefix u10u 0 would contradict Lemma 4. Informally, the indeterminism of A R can be dropped in the described situation.

Activity level

The idea above is formalized in an automaton by the activity level of words, a tool giving the position of the leftmost pattern 10 which can be flipped (from 10 to 01) while preserving acceptance of the word.

Precisely, a finite word w is said acceptable if w is a prefix of a word w accepted by A R . Notice that when w is acceptable, w0 is also acceptable, and the fact that w1 is acceptable or not only depends on the p -1 last bits of w.

Given a finite acceptable word u10u , we say that the pattern 10 is active in u10u if the word u01u is also acceptable. In this case, we say that |u | is the activity level of the pattern 10. The activity level (w) of an acceptable word u is defined as the largest activity level of one of its active patterns 10. If u has no such an active pattern, then by definition we let (w) = -1.

Lemma 5. Let w be an acceptable word.

• Activity level of w0:

when (w) = -1 and the last bit of w is 0, we have (w0) = -1, in any other case we have (w0) = (w) + 1.

• Activity level of w1, when w1 is acceptable:

-if (w) = -1 then (w1) = -1, -if (w) ≥ p -1 then (w1) = (w) + 1, -if 0 ≤ (w) ≤ p -2, then w = u10u with |u | = (w), and * if u01u 1 is acceptable, then (w1) = (w) + 1, * otherwise (w1) = -1.
Proof. All results above are direct consequences of definitions, except the very last case, when w = u10u with |u | = (w) ≤ p-2 and u01u 1 is not acceptable.

To conclude in this case we have to argue that there cannot exist any other active pattern. Assume that u can be decomposed in u = v10v . Remark that, since u01u 1 is not acceptable, then u10v01v 1 is not acceptable (by monotony of the function U → L R U ). This means that w1 contains no active pattern 10.

Corollary 1. Let w be an acceptable word such that w1 is acceptable.

• If 0 ≤ l(w) ≤ p -2 then w = u10u with |u | = l(w)
, and w0 is acceptable if and only if u01u 1 is not acceptable.

• If l(w) ≥ p -1 then w0 is not acceptable.

Proof. For the first item, since every word of A R ends with a 1, if w0 is acceptable then it would be possible to simultaneously flip the 10 pattern between u and u , and the pattern 01 introduced after w, contradicting Lemma 4.

For the second item, if l(w) ≥ p -1 then w = u10u , and since w1 is acceptable and |u | ≥ p -1 we know that u01u 1 is also acceptable. We can argue as in the first case: the fact that w0 is acceptable would contradict Lemma 4.

Definition of fixed point automata

Given a state q = q 1 q 2 . . .q p-1 in {0, 1} p-1 , for 0 ≤ ≤ p -3 (respectively = p -2) the flipped state f (q, ) is the element q = q 1 q 2 . . .q p-1 of {0, 1} p-1 such that

• q p--2 q p--1 = 01 (respectively q 1 = 1),

• q i = q i for i / ∈ {p --2, p --1} (respectively i = 1).
And the truncated state q is the element q 2 q 3 . . .q p-1 of {0, 1} p-2 .

Definition 4. Given a decreasing sandpile rule R = (r 1 , r 2 , . . . , r p ), let B R be its fixed point automaton, which is the finite state automaton defined by:

• the set of states Q R ⊆ {0, 1} p-1 × {-1, 0, 1, 2, . . . , p -1}, such that a pair (q, ) with q = q 1 q 2 . . .q p-1 is a state of Q R if all the following three conditions hold:

(C 1 ) = -1 =⇒ q p-1 = 1 (C 2 ) 0 ≤ ≤ p -3 =⇒ q p--2 q p--1 = 10 (C 3 ) = p -2 =⇒ q 1 = 0 • the alphabet Σ = {0, 1},
• the set of transitions

→ B R : Q R × Σ × Q R where (q, ) a -→ B R (q ,
) if and only if all the following eleven conditions hold:

(C 1 ) q 1 q 2 . . .q p-2 = q (C 2 ) q p-1 = 1 =⇒ L R q < r 1 (C 3 ) a = q p-1 (C 4 ) ( = -1 ∧ q p-2 q p-1 = 10) =⇒ = -1 (C 5 ) ( = -1 ∧ q p-2 q p-1 = 10) =⇒ = 0 (C 6 ) (0 ≤ ≤ p -2 ∧ q p-1 = 0) =⇒ = + 1 (C 7 ) = p -1 =⇒ = p -1 (C 8 ) (0 ≤ ≤ p -2 ∧ q p-1 = 1 ∧ L R f (q, ) < r 1 ) =⇒ = + 1 (C 9 ) (0 ≤ ≤ p -2 ∧ q p-1 = 1 ∧ L R f (q, ) ≥ r 1 ) =⇒ = -1 (C 10 ) (0 ≤ ≤ p -2 ∧ L R f (q, ) < r 1 ) =⇒ q p-1 = 1 (C 11 ) ( p -1 ∧ L R q < r 1 ) =⇒ q p-1 = 1 • the set of initial states is S R = Q R • the set of final states is T R = {(q, ) ∈ Q R | q p-1 = 1}.
Let L(B R ) denote the language of finite words recognized by B R .

An example of fixed point automaton is given on Figure 6. As at the end of the previous section, we can simplify it by keeping only the ultimately relevant states of the automaton, which gives the automaton denoted B R .

Since we want to have a finite state automaton, the activity level cannot be completely encoded. Thus, the semantics of a level p -1 of the automaton is that the real activity level is actually at least p -1. With the above encoding,

• Conditions (C 1 ) to (C 3 ) guarantee the consistency between a possible activity level and the state,

• Conditions (C 1 ) to (C 3 ) ensure the stability,

• Conditions (C 4 ) to (C 9 ) translate informations of Lemma 5 about the evolution of the activity level in the automaton,

• Theorem 7. Let s be the shot sequence of π(N ), there exists a column n 4 in O(log N ) such that the significant part of (∆ 2 s i ) i≥n4 belongs to L(B R ).

Proof. This is a direct consequence of Lemma 5 and Corollary 1. Now we want to use the fixed point automaton in order to get a proof of Conjecture 2. That is, we have to study the structure of B R . This is detailed below.

Evolution of the activity level

If we project the automaton by only considering the evolution of activity levels, then we have an automaton whose state set is the level set {-1, 0, 1, 2, . . . , p-1}, and transitions are the following:

• for -1 ≤ ≤ p -2 we have → B R + 1 and → B R -1, • p -1→ B R p -1.
When level p -1 is reached, then the level remains equal to p -1. In other words, level p -1 is a sink for the automaton. Also notice that once a state of level p -1 is reached, then the automaton is deterministic (details in Subsection 5.3.4).

According to these remarks, we can decompose the study of B R into the study of two smaller automata.

• The final part of B R , which is the restriction of B R to states whose activity level is p -1. From (C 2 ) and (C 11 ), this automaton is deterministic (it can be seen as a sub-automaton of the recurrence automaton).

• The transient part of B R , which is obtained from B R by merging all states whose activity level is p -1 in a unique sink state denoted by S p-1 (we will not need to consider whether this sink state is final or not).

We have the following proposition. Remark that the final part of B R always contains at least one cycle. We have done a sequence of random tests from which we conjecture that the final part of B R always contains a unique cycle, though we are not yet able to prove it.

Ultimately relevant bifurcation states

Ultimately relevant bifurcation states play a key-role in the analysis of the automaton. Let us identify ultimately relevant states which possibly are bifurcation states (i.e. states from which two transitions are possible).

We have previously remarked that the final part of the fixed point automaton is deterministic: we have L R q < r 1 ⇐⇒ q p-2 = 1. The only bifurcation states are (recall that q = q 2 q 3 . . .q p-1 ):

• states (q, -1) such that L R q < r 1 ; in this case we have (q, -1)→ B R (q1, -1) and (q, -1)→ B R (q0, 0),

• states (q, ), with 0 ≤ ≤ p -2, such that L R q < r 1 and L R f (q, ) ≥ r 1 ; in this case we have (q, )→ B R (q1, -1) and (q, )→ B R (q0, + 1).

One easily sees that states of the first type are not ultimately relevant (except possibly when q = 1 p-1 ). Indeed, let (q, -1) be such that L R q < r 1 and assume that this state is ultimately relevant. If (q , )→ B R (q, -1), then the activity level -1 of (q, -1) implies q p-1 = 1 from Condition (C l1 ). Now suppose for the contradiction that ≥ 0. Then the premises of Condition (C 8 ) or (exclusive) of Condition (C 9 ) hold. Given that = -1, premises of Condition (C 8 ) cannot hold, hence premises of Condition (C 9 ) hold: L R f (q , ) ≥ r 1 , which contradicts L R q < r 1 . Therefore we have = -1 and q p-1 = 1, which enforces that L R q < L R q (except if q = q = 1 p-1 ). We can repeat this argument to construct a sequence (q n ) n of states such that L R q i+1 < L R q i for all i, which is a contradiction.

Thus all ultimately relevant bifurcation states (except (1 p-1 , -1), only if L R 1 p-1 < r 1 ) are of the second type. The case where L R 1 p-1 < r 1 corresponds to r 1 big and Subsection 6.2.1 details why Conjecture 2 holds for such rules.

Equivalence between rules

We recall that for a rule R = (r 1 , r 2 , . . . , r p ) we denote by L R the vector (r p , r p + r p-1 , . . . , r p + r p-1 + . . . + r 2 ). Here we prefer to express L R as L R = (∆r p , 2∆r p + ∆r p-1 , . . . , (p -1)∆r p + (p -2)∆r p-1 + . . . + ∆r 2 ) where for each i, 1 ≤ i ≤ p, ∆r i = r ir i+1 (with the convention r p+1 = 0). This can be written as

L R = ∆ 1 R M p , where ∆ 1
R is the row vector (∆r p , ∆r p-1 , . . . , ∆r 2 ) of N p-1 and M p is the (p -1) × (p -1) matrix defined as

M p =        1 2 3 p -1 0 1 2 . . . p -2 0 0 1 p -3 . . . . . . . . . 0 0 0 . . . 1        . Definition 5. For each rule R = (r 1 , r 2 , . . . , r p ), the bottom B R of R is the set B R = {q ∈ {0, 1} p-1 | L R q < r 1 }.
We say that two rules R and R are equivalent if B R = B R .

Notice that two equivalent rules generate the same recurrence and fixed point automaton. For a fixed integer p, the number of equivalence classes is finite. Thus this equivalence relation is a tool which, for p being fixed, allows to reduce the study of all rules (there is an infinite set of rules) to a finite set of cases.

Nevertheless the number of equivalence classes is a priori rather large. An obvious bound is 2 2 p-1 . In practice we can treat less cases using the following definition. Definition 6. Let q and q be two elements of {0, 1} p-1 . We say that q q if for any rule R of length p, we have L R q ≤ L R q .

The definition above uses a universal quantification for R which is not easily tractable. This is why we give an alternative definition, in the proposition below.

Proposition 5. Let q, q ∈ {0, 1} p-1 . Then q q if and only if M p q ≤ M p q .

Proof. Assume that M p q ≤ M p q . Notice that M p q ≥ 0 and, for each rule R,

∆ 1 R ≥ 0. Thus we get ∆ 1 R M p q ≤ ∆ 1 R M p q , i.e. L R q ≤ L R q . Conversely, assume that M p q ≤ M p q , i.e. there exists a component index k such that (M p q) k > (M p q ) k . Let E k = (E k 1 , . . . , E k p-1 ) be the row vector of {0, 1} p-1 such that E k j = 1 if j = k
, and E k j = 0 otherwise. We have

E k M p q = (M p q) k > (M p q ) k = E k M p q .
Thus, if R is such that ∆ 1 R = E k (for example if r 1 = 3, r i = 2 for 2 ≤ i ≤ pk -1 and r i = 1 for pk ≤ i ≤ p -1), then we have L R q ≤ L R q , i.e. q q . Corollary 2. The pair ({0, 1} p-1 , ) is a poset.

Proof. Reflexivity and transitivity are trivial. For antisymmetry, if q q and q q then M p q ≤ M p q and M p q ≤ M p q. Thus M p q = M p q which gives q = q since M p is invertible. Remark 7. If q q and q ∈ B R , then q is also an element of B R . In other words, B R is a down-set of the poset ({0, 1} p-1 , ).

For p ≤ 4, the relation is actually a total order on {0, 1} p-1 , which allows to compute easily the number of equivalence classes: 2 p-1 Finally, for any decreasing sandpile rule R of N p , 0 p is an element of B R .

Applications

In this section we use fixed point automata to prove Conjecture 2 when p is small, r 1 is large, and r 1 is small, giving Theorem 2. The sequence (∆ 2 s i ) i∈N will refer to the second difference (or discrete derivative) of the shot sequence of π(N ).

Case when p is small

For a given value p, we now consider each possible down-set, and therefore exhaustively design fixed point automata for all equivalence classes. We have been able to check that Proposition 4 holds for any rule with 2 ≤ p ≤ 7.

Theorem 8. Conjecture 2 holds for p ≤ 7.

Proof. The proof is an exhaustive analysis of the fixed point automaton for each equivalence class, with the help of a computer. For all 2 ≤ p ≤ 7, we first compute the poset ({0, 1} p-1 , ) and enumerate its down-sets. Then for each down-set, we construct the corresponding automaton according to Definition 4, and enumerate the cycles of its transient and final part. It appears that for each down-set, the condition of Proposition 4 is satisfied: the transient and final part of the fixed point automaton have at most one cycle, which gives the result. Our sagemath [START_REF]The Sage Developers[END_REF] program and the trace of its execution (which takes approximately two minutes on a standard laptop, as of 2017) is available online [START_REF] Perrot | Conjecture 2 for small p[END_REF].

The number of down-sets of the poset ({0, 1} For p = 8 (trace available online [START_REF] Perrot | Conjecture 2 for small p[END_REF]) we found 60 down-sets for which the fixed point automaton has two cycles in its transient part (all have one cycle in their final part). An example is the down-set for which the fixed point automaton has the following two cycles in its transient part:

(0011001, 2) → (0110011, -1) → (1100110, 0) → (1001100, 1) → (0011001, 2) and (0010110, 0) → (0101101, -1) → (1011010, 0) → (0110100, 1) → (1101001, 2) → (1010010, 3) → (0100101, 4) → (1001011, -1) → (0010110, 0) and the following cycle in its final part:

(0101010, 7) → (1010101, 7) → (0101010, 7).

For p = 9, the call to the sagemath method Poset.order ideals lattice (computing the set of all down-sets) exceeds the memory capacity of our machine.

Proof. There is only one ultimately relevant bifurcation state which is (1 p-1 , -1), and all other transitions are deterministic:

• if ≥ 0 then (q, ) → B R (q0, ) since B R = B + 0 , so it would not fulfill Condition (C 10 ): the automaton follows deterministic transitions labeled by the value 1 (and the activity level is increased until p -1),

• if = -1 then the argument is the same as in Section 5.3.4: either it leads to a state (q0, ) with = 0, or q = q1 = 1 p-1 is the only ultimately relevant state.

As a consequence the only cycles of the automaton B R are the two loops

• (1 p-1 , -1)→ B R (1 p-1 , -1) • (1 p-1 , p -1)→ B R (1 p-1 , p -1)
and there is a unique path of ultimately relevant states

(1 p-1 , -1)→ B R (1 p-2 0, 0)→ B R (1 p-3 01, 1)→ B R . . . → B R (1 p-1 , p -1).
Therefore L(B R ) is composed of words with at most one letter 0, and the result follows from Theorem 7.

Case when

B R = B + 3
In this case the fixed point automaton is again understandable in simple terms. There is only one ultimately relevant bifurcation state which is (1 2 01 p-4 , p -4), from which the automaton can either (if transition labeled 1 is taken) enter a deterministic cycle of p -3 transitions that goes back to (1 2 01 p-4 , p -4), or (if transition labeled 0 is taken) follow two deterministic transitions and enter a deterministic limit cycle of p -1 transitions. Any other state deterministically converges to one of these, and we have the following result.

Proposition 7. Given a transition rule R such that B R = B + 3 , there exists a column n in O(log N ) such that the sequence (∆ 2 s i ) i≥n is an element of (01 p-3 ) * (01 p-4 + )(01 p-3 ) * .

Proof. From the argument of Section 5.3.4 and the definition of B + 3 , the only ultimately relevant bifurcation state is (1 2 01 p-4 , p -4) (l = p -4 is given by Conditions (C l1 ), (C l2 ) and (C l3 )). Let us study the set Q acc of states accessible from (1 2 01 p-4 , p -4).

• (1 2 01 p-4 , p -4)→ B R (101 p-3 , -1) and (101 p-3 , -1) * → B R (1 2 01 p-4 , p -4) by a sequence of p -3 deterministic transitions.

• (1 2 01 p-4 , p-4)→ B R (101 p-4 0, p-3), then (101 p-4 0, p-3) * → B R (1 p-4 011, p-1) by a sequence of 2 deterministic transitions, and (1 p-4 011, p -1) * → B R (1 p-4 011, p -1) by a cycle of p -2 deterministic transitions.

(iii) When q j = 1, = pj and j + k + 1 ≤ p -1, then q j+k+1 = 1.

Proof. We prove the three items by induction, one after the other.

(i) We prove by induction on i that, after i automaton steps, the first item holds for j ≥ p -1i. For i = 0, the result is obvious. Assume, for the induction, that the result holds for a fixed i ≥ 0.

Let (q, ) be a state obtained after i + 1 steps, with q = q 1 q 2 . . .q p-1 . Let (q 0 q 1 . . .q p-2 , ) be a predecessor of (q, ), and let j ≥ 1 be such that j ≥ p-2-i and q j = 1. Since (q 0 q 1 . . .q p-2 , ) is obtained after i steps, we can apply the induction hypothesis on (q 0 q 1 . . .q p-2 , ): for 1 ≤ k ≤ k -1 and j + k ≤ p -2 we have q j+k = 0.

If j + k -1 ≤ p -2, then we have the result. If j + k -1 ≥ p -1 (i.e. k ≥ pj), we have to prove that q p-1 = 0. This is ensured by the fact that L R q 0 q 1 . . .q p-2 ≥ L R E j+1 ≥ L R E p-p +1 ≥ r 1 .

The first inequality comes from the fact that the function U → L R U is nondecreasing, the second inequality holds since k ≤ pj, and the last inequality is in the hypothesis.

This gives the induction, and therefore the result since one can take i = p.

(ii) Afterwards, we prove by induction on i that, after p + i automaton steps, the second item holds for j ≥ p -1i. For i = 0, the result is obvious. Assume, for the induction, that the result holds for a fixed i ≥ 0.

Let (q, ) be a state obtained after p + i + 1 steps, with q = q 1 q 2 . . .q p-1 . Let (q 0 q 1 . . .q p-2 , ) be a predecessor of (q, ), and let j ≥ 1 be such that j +k ≥ p-2 and q j = 1. Since (q 0 q 1 . . .q p-2 , ) is obtained after p + i steps, we can apply the induction hypothesis on (q 0 q 1 . . .q p-2 , ) which gives the result.

If j+k = p-1, then using the first item, we have q 0 q 1 . . .q p-2 = E j+1 = E p-k , and moreover (to satisfy Conditions (C l1 ),(C l2 ) and (C l3 )), ∈ {-1, p -1, pj -1}. We consider the three cases:

• if = p -1 then q p-1 = 1 and = p -1;

• if = pj -1 then remark that f (E p-k , pj -1) = E p-k+1 / ∈ B R , which gives (q p-1 = 0 ∧ = pj) ∨ (q p-1 = 1 ∧ = -1);

• if = -1 then q p-2 = 1 which enforces that j + 1 = p -1 = j + k. This gives k = 1, which is a contradiction since k ≥ p .

This gives the announced equivalence, therefore the induction, and the result since one can take i = p.

(iii) Finally, we prove by induction on i that, after 2p+i automaton steps, the third item holds for j ≥ p -1i. For i = 0, the result is obvious. Assume, for the induction, that the result holds for a fixed i ≥ 0.

Let (q, ) be a state obtained after 2p + i + 1 steps, with q = q 1 q 2 . . .q p-1 . Let (q 0 q 1 . . .q p-2 , ) be a predecessor of (q, ), and let j ≥ 1 be such that j + k + 1 ≥ p -2 and q j = 1. Since (q 0 q 1 . . .q p-2 , ) is obtained after 2p + i steps, we can apply the induction hypothesis on (q 0 q 1 . . .q p-2 , ) which gives the result.

If j+k+1 = p-1, we necessarily have = -1 = p-j-1 = k+1. Moreover, from the first item, we have q 0 q 1 . . .q p-2 = E p-k-1 . Thus by application of the fixed point automata conditions, this gives q p-1 = 1 (since f (E p-k-1 , k + 1) = E p-k ∈ B R ), which gives the induction, and the result.

In other words, the lemma above means that, in (∆ 2 s i ) i≥n , two values 1 are separated by at least k -1 values 0, and at most k values 0. One can easily check that if there exists a factor 10 k 1, then the following part is deterministic (since the level p -1 is reached), and in this part there cannot be another factor 10 k 1. As a consequence, with Theorem 7 we get the following result.

Theorem 10. When E p-k ∈ B R and E p-k+1 / ∈ B R , with p 2 ≤ k < p, there exists a column n in O(log N ) such that the sequence (∆ 2 s i ) i≥n is an element of (10 k-1 ) * (0 + )(10 k-1 ) * 0 ω .

Therefore, Conjecture 2 holds when B R is small.

Conclusions and perspectives

We have presented a general method to understand decreasing sandpile models, leading to a precise description of the emerging patterns on fixed point for three families of rules: when p is small, r 1 is big, and r 1 is small (Theorem 2). This method succeeds for a large number of other rules, but Conjecture 2 remains open on its complete generality.

A first improvement could be to have a better understanding of the cycle structures inside fixed point automata. However, using fixed point automata as we have presented them cannot succeed in any case. For p = 8 we found some examples where the fixed point automaton contains three cycles, and as consequence we need some other arguments to prove (or infirm) the conjecture.

Remark that we do not completely exploit the meaning of the least action principle (Theorem 6), but a weaker yet more tractable criterion (Lemma 4). An improvement could be to find a criterion which reflects more precisely the least action principle, and remains tractable.

On the other hand, we do not exclude the possibility that Conjecture 2 is false for a rule, with p large, which has not been discovered until now.

Figure 2 :

 2 Figure 2: Evolution from the initial configuration (26, 0 ω ) with rule (2, 1), converging to the fixed point π(26) = (11, 7, 4, 3, 1, 0 ω ).

i→

  c and c j → c . Then there exists a common successor of c and c , denoted c , such that c j → c and c i → c . Termination. For any configuration h, the energy E(h) is defined by

  and |w 2 |, |w 3 |, |w 4 |, |w 5 | all in O(1).

  and |w 2 |, |w 3 |, |w 4 |, |w 5 | all in O(1).

Figure 3 :

 3 Figure 3: Sequence (∆s i ) i∈N for the rule (7, 5, 2, 1) and the fixed point for N = 12 345 grains.It illustrates the dynamics of the perturbed weighted linear system, and its convergence to values such that ∆ 2 s i ∈ {0, 1}. Note the addition of virtual elements (∆s i ) i∈{-1,...,-p} (unfilled bullets on the left side).

Figure 4 :

 4 Figure 4: The darken area pictures the set of constraints that the proof of Fact 3 establishes on the sequence (∆s j ) i≤j≤i+(m i -m i +1)p .

Fact 4 .

 4 It holds that

Figure 5 :

 5 Figure5: Recurrence automaton A R for R = (7, 5, 2, 1). Ultimately irrelevant states are shaded. The language accepted by the automaton contains (10 + 010 + 0010) * 1. This is is not sufficient to prove Conjecture 2.

Figure 6 :

 6 Figure6: Fixed point automaton B R for rule R = (7, 5, 2, 1). Ultimately irrelevant states are shaded. Compared to the recurrence automaton Figure5, we can see that the cycle 010 → 100 → 001 → 010 has been "unfolded", and now links the ultimately relevant transient part (first cycle) to the ultimately relevant final part (second cycle). We can conclude that Conjecture 2 holds for this rule.

Proposition 4 .

 4 If the final and transient parts of B R both contain at most one cycle, then Conjecture 2 holds.

  p-1 , ) is given in the following table.

	p	2 3 4 5	6	7	8
	number of down-sets 2 4 8 19 59 297 3177

the significant part of an ultimately null sequence x = (x i ) i∈N is the word formed by the prefix (x i ) i≤j of x such that x j = 0, and for i > j, x i = 0.

Acknowledgements

The work of Kévin Perrot was funded mainly by his salary as a French State agent, affiliated to Aix-Marseille Univ, Univ. de Toulon, CNRS, LIS, UMR 7020, Marseille, France, and Univ. Côte d'Azur, CNRS, I3S, UMR 7271, Sophia Antipolis, France. The work of Éric Rémila was funded mainly by his salary as a French State agent, affiliated to Univ. de Lyon, CNRS, UJM St-Etienne, GATE LSE, UMR 5824, St-Etienne, France This work was also partially supported by IXXI (Complex System Institute, Lyon), ANR projects Subtile, Dynamite and QuasiCool (ANR-12-JS02-011-01), Modmad Federation of U. St-Etienne, FONDECYT Grant 3140527, Núcleo Milenio Información y Coordinación en Redes (ACGO), PEPS JCJC INS2I 2017 project CGETA, PACA Project FRI-2015 01134, ANR-18-CE40-0002 FANs project, ECOS-Sud C16E01 project, STIC AmSud CoDANet 19-STIC-03 (Campus France 43478PD) project, and IDEXLYON (project INDEPTH) within the Programme Investissements d'Avenir (ANR-16-IDEX-0005).

Case when r 1 is big, i.e. B R is big

We use fixed point automata and equivalence between rules to have a better description of fixed points in a infinite class containing some particular cases. We can assume that p ≥ 8, since the cases when p ≤ 7 have been previously treated.

Note that for any q ∈ {0, 1} p-1 \ {101 p-3 , 01 p-2 , 1 p-1 }, we have

is big, then the fixed point automaton is limited by the number of transitions.

We divide the case when B R is big into four cases, depending on which elements of

To proceed, we successively prove the following items.

1. there exists a unique ultimately relevant bifurcation state (q, ), 2. in the transient part of the fixed point automaton, we have:

where in each transition sequence, only the first one is non deterministic, 3. for each state (q , ), there exists a state (q , ) such that (q, ) * → B R (q , ) and (q , ) * → B R (q , ).

We give details for two examples, the two others are analogous. By Propositions 6 and 7 we will have the following result. Theorem 9. Conjecture 2 holds when B R is big.

Case when

In this case the fixed point automaton is understandable in simple terms. There is only one ultimately relevant bifurcation state which is (1 p-1 , -1), and the rest of the ultimately relevant states of the automaton follow deterministic transitions labeled by the value 1, hence the following result. Proposition 6. Given a rule R such that B R = B + 0 = {0, 1} p-1 , there exists a column n in O(log N ) such that the sequence (∆ 2 s i ) i≥n is an element of

Thus Q acc is formed by two cycles each of length p -2, those cycles are linked by a directed path of length 2, and each element of Q acc is ultimately relevant. The language induced by states of Q acc is therefore (101 p-4 ) * (01 p-3 ) * , which corresponds to the statement of the lemma.

We now finish the proof by showing that from any state (q, ) / ∈ Q acc , in at most 3p transitions, whatever the chosen path, a state of Q acc is reached.

3 , and (q, ) = (101 p-3 , -1), one easily checks that (q, ) * → B R (1 p-4 011, p -1) by a sequence of at most p deterministic transitions.

• If q ∈ B + 3 , then for each = -1 there exists q ∈ {0, 1} p-1 \ B + 3 and ∈ {-1, 0, 1, 2, . . . , p -1}, such that (q, ) * → B R (q , ) by a sequence of at most p deterministic transitions.

• Starting from (q, -1) with q ∈ B + 3 , in at most p transitions, whatever the chosen path, a state (q , ) is reached such that, either q ∈ B + 3 and = 0, or q ∈ {0, 1} p-1 \ B + 3 . As a consequence Q acc is the set of ultimately relevant states, and the result follows from Theorem 7.

A similar proposition and proof holds when B R = B + i with i ∈ {1, 2, 3}.

6.3. Case when r 1 is small, i.e. B R is small Recall that E k denotes the vector of {0, 1} p-1 such that E k j = 1 if j = k, and E k j = 0 if j = k. By convention E 0 = 0 p-1 . Note that k ≤ k implies that E k E k .

Let p = p 2 , we say that B R is small when

Let k, with p ≤ k ≤ p -1, be the unique integer such that

The following Lemma describes the structure of the ultimately relevant part of the fixed point automaton when B R is small. Lemma 6. Let (q, ) be an ultimately relevant state of B R when B R is small. Then the following holds.

(i) When q j = 1, then q j+k = 0 for all 1 ≤ k ≤ k -1 (and j + k ≤ p -1).

(ii) When q j = 1 and j + k ≤ p -1, we have q j+k = 0 ⇐⇒ = pj.

Declaration of interests

X The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

☐The authors declare the following financial interests/personal relationships which may be considered as potential competing interests:


M Voidey
email: mvoidey@chu-besancon.frlesauteursnedéclarentpasdeconflit

MD Anne Sophie Gauthier
email: asgauthier@chu-besancon.fr

MD Voidey Mélanie

Keywords: phytophotodermatosis, parsnip, photoprotection Résumé phytophotodermatose, panais, protoprotection phytophotodermatosis, parsnip, photoprotection

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Les phytophotodermatoses sont caractérisées par une éruption cutanée résultant du contact avec des composés photosensibilisants présents dans diverses plantes et d'une exposition solaire [START_REF] Bowers | Phytophotodermatitis[END_REF][START_REF] Kavli | Phytophotodermatitis[END_REF]. Il s'agit d'une réaction phototoxique indépendante du système immunitaire.

Les coupables les plus courants sont le céleri, les citrons et certaines oranges, ainsi que les herbes naturelles.

La phase aiguë de l'éruption cutanée est caractérisée par un oedème et un érythème et peut laisser une hyperpigmentation résiduelle séquellaire [START_REF] Kung | Phytophotodermatitis: bulla formation and hyperpigmentation during spring break[END_REF].

Nous rapportons un cas pédiatrique d'une phytodermatose du visage chez un enfant de 5 mois développée après l'ingestion de panais cuit.

Observation

Un enfant de 6 mois sans antécédent a été pris en charge aux urgences pédiatriques pour érythème phlycténulaire péribuccal. L'interrogatoire a mis en évidence l'ingestion d'une purée de panais cuit prise en extérieure au printemps 12h avant l'éruption. Le reste de l'examen clinique était sans particularité notamment il n'existait pas d'altération de l'état général ni de fièvre. La prise en charge a consisté en une éviction solaire et au rappel des mesures de photoprotection. Une application topique de pommades émollientes et hydratantes. L'évolution sous traitement a été favorable avec diminution progressive de l'érythème et disparition complète sans séquelle à 3 mois (Figure 1).

Discussion

Les cas décrits de phytophotodermatose au panais sont peu fréquents.

Plusieurs familles de plantes sont connues pour provoquer des réactions phototoxiques, et l'un des agents chimiques le plus souvent responsables est la furocoumarine, en particulier les isomères du psoralène, présents dans les agrumes, notamment les citrons [START_REF] Bowers | Phytophotodermatitis[END_REF].

Les lésions induites peuvent être douloureuses en lien avec la nécrose induite de l'épiderme.

Le traitement est principalement symptomatique. L'hyperpigmentation résiduelle est fréquente (4).

Conclusion

Devant toute éruption cutanée après exposition solaire, l'interrogatoire permet le plus souvent de faire le diagnostic et de retrouver l'agent causal. Le traitement repose essentiellement sur la photoprotection.

Les auteurs ne déclarent aucun conflit d'intérêt

Figure 1 : Phytophotodermatose au panais : évolution des lésions cutanées sur 2 mois. A : J1 : éruption érythémato-bulleuse périorale survenue 12h après l'ingestion de panais cuit. B : J3, augmentation de l'érythème. C : J4, évolution vers une lésion croûteuse. D : J5, récidive de lésions bulleuses. E : J9, diminution de l'érythème. F : M2, petit érythème persistant.