{'fraction_non_alphanumeric': 0.04027808430809976, 'fraction_numerical': 0.0024277201500772457, 'mean_word_length': 3.8413461538461537, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Coding Distributive Lattices with Edge Firing Games

In this note, we show that any distributive lattice is isomorphic to the set of reachable configurations of an Edge Firing Game. Together with the result of James Propp, saying that the set of reachable configurations of any Edge Firing Game is always a distributive lattice, this shows that the two concepts are equivalent.

In this section, we prove that any distributive lattice is isomorphic to the configuration space of an EFG. The proof uses the theorem of Birkhoff for representation of distributive lattices [1]. We first state this theorem and the definitions needed. After this, we restrict ourselves to the EFGs which satisfy the following property: during any sequence of possible firings, each vertex is fired at most once. Such an EFG is said to be simple. We prove that any distributive lattice is isomorphic to the configuration space of such an EFG. Since, from [9], the configuration space of any EFG is a distributive lattice, we obtain as a corollary that any EFG is equivalent to a simple one.
Given a lattice L, an element a of L is a join-irreducible if there is a unique element b in L such that b ≺ a. If one considers the set J of all the join-irreducibles of a lattice L, then a natural order is induced by L over J: a ≤ b in J if and only if a ≤ b in L. See Figure 1 for an example.   In the sequel, we will only consider simple EFGs. Indeed, we will see that any EFG is equivalent to such an EFG. We begin by giving a lemma about simple EFGs, then we will prove our result.
Lemma 1 Let E be a simple EFG. Let C and C ′ be two configurations of E such that C ≥ C ′ . If σ and σ ′ are two sequences of firings which transform C into C ′ , then the set of fired vertices during σ is the same as during σ ′ .
Proof : Let S and S ′ be the sets of vertices fired respectively during the sequences σ and σ ′ . When we go from C to C ′ following σ, the orientation of the edges of the graph vary as follows: the edges between vertices not in S are not affected, the edges incident to a vertex in S are reversed (they were directed towards S in C, and are directed away from S in C ′ ), and the edges between two vertices in S have the same orientation in C and C ′ (they are reversed twice). From this, one can easily see that, if S ′ is not equal to S, then the sequence σ ′ cannot lead to the same configuration as σ, which proves the claim.
Notice that this lemma remains true if we consider EFGs which are not simple. This can be shown with a proof similar to the one concerning Chip Firing Games (see [2,5]). However, this proof would be much more complicated than the one given here, which is sufficient to make the note self-contained.
This lemma makes it possible to define the shot-set of any configuration C: s(C) is the set of vertices fired to reach C from the initial configuration. We can now prove our result: Theorem 2 Any distributive lattice is isomorphic to the configuration space of a simple Edge Firing Game.
Proof : Let L be a distributive lattice and J be the set of its join-irreducibles with the order induced by L. Let G = (V, E) be the undirected graph defined as follows: We claim that the configuration space of the EFG played on G, with initial configuration G 0 and with sink ⊥, is isomorphic to L. To prove this, we will first show that the EFG is simple (i.e. each vertex is fired at most once), and then we will show that the configuration space of the game and the lattice of the filters of J are isomorphic.
We first show by induction that each vertex is fired at most once. Let j be a maximal element. We will show that j is fired only once. It can be fired in G 0 since, by definition, all the edges incident to j are directed towards j. Once j has been fired, the edge {⊥, j} is directed from j to ⊥, and since ⊥ cannot be fired, it will never be directed towards j again. Therefore j can never be fired again. Let now j be an element covered by another element j ′ which can be fired only once. We will show that j can be fired at most once. It can be fired only after j ′ (the edge {j, j ′ } must be directed towards j). After the firing of j, the edge {j, j ′ } is directed towards j ′ , and since j ′ cannot be fired again, the edge will never be directed towards j again, and j cannot be fired again. Finally, the EFG is simple and thus, from Lemma 1, we can consider the shot-sets of its configurations. Now we prove that s, the function which associates its shot-set to a configuration, is an isomorphism between the set of configurations of the game and the set of filters of J. To do this, we will first show that, for any configuration C, s(C) is a filter, and then that, if C 1 , . . . , C k are the configurations covered by C, then the filters s(C 1 ), . . . , s(C k ) are exactly the ones covered by s(C). We will show these two steps simultaneously by induction. To prove these two steps, we also need to prove that the vertices which can be fired in configuration C are exactly the maximal elements of J \s(C). Therefore we will also prove this in the induction. The base case is the initial configuration G 0 : s(G 0 ) is the empty set, which is the maximal filter for reverse inclusion. The vertices which can be fired in G 0 are, by definition, the maximal elements of J, which are the maximal elements of J \ s(G 0 ), as expected. The induction step is as follows: if C is a configuration such that s(C) is a filter, and such that the vertices that can be fired are the maximal elements of J \s(C), we will show the following: if C 1 , . . . , C k are the configurations covered by C, then the sets s(C 1 ), . . . , s(C k ) are some filters, and they are exactly the filters covered by s(C). We will prove simultaneously that the vertices which can be fired in configuration C i are the maximal elements of J \ s(C i ). Let C be any configuration such that s(C) is a filter, and such that the vertices that can be fired are the maximal elements of J \ s(C). First notice that, in J, the filters covered by a filter F are exactly the sets F ∪ {x} for all x maximal in J \ F . Let C 1 , . . . , C k be the configurations covered by C. Each C i is obtained from C by the firing of a vertex j i , therefore s(C i ) = s(C) ∪ {j i }. Since, by induction hypothesis, the j i are the maximal elements of J \ s(C), the sets s(C i ) are exactly the filters covered by s(C), as expected. To complete the induction step we show that, for all i, the vertices that can be fired in configuration C i are exactly the maximal elements of J \ s(C i ). Any maximal element x of J \ s(C i ) can be fired because all the elements greater than x (including the elements covering x) have been fired. Therefore all the edges {x, x ′ } with x ≺ x ′ are now directed towards x (the edges {x, x ′ } with x ≻ x ′ have not been turned and are still directed towards x). Now we show that no vertex that is not maximal in J \ s(C i ) can be fired: if a vertex v is not maximal in J \ s(C i ), then at least one element u that covers v has not been fired, and the corresponding edge is directed away from v. This completes the induction step.
We have shown that, for any configuration C, s(C) is a filter, and that the configurations covered by C correspond exactly to the filters covered by s(C). Therefore the configuration space of the EFG is isomorphic to the lattice of the filters of the order induced over J, which by Theorem 1 is isomorphic to L.
This theorem is illustrated in Figure 2. Notice that, since the configuration space of any EFG is a distributive lattice, we obtain as a corollary that any EFG is equivalent to a simple one. Therefore, we finally have that distributive lattices, EFGs and simple EFGs are equivalent in terms of configuration spaces. Notice also that the proof is constructive, which gives a way to transform any EFG into a simple one.

Discussion and perspectives
The study on what kind of structures can be generated using discrete dynamical models is an active area of research, and it is now clear that lattices and distributive lattices often appear in this context. In particular, two important models which appear in physics, combinatorics, computer science and social science, the Chip Firing Game (CFG) and the Abelian Sandpile Model (ASM), have the following two properties: any distributive lattice can be obtained as the configuration space of these models, and all the configuration spaces one can obtain are Upper Locally Distributive (ULD) lattices. These two classes of lattices are strongly structured and very close, therefore we have a precise idea of what kind of configurations spaces are obtained with these models. However, no exact characterization is known, despite the fact that we know that they are all different. The result we prove in this note, together with the result from James Propp [9], shows that there is an equivalence between the distributive lattices and EFGs. Therefore, the EFG is strictly less powerful, in terms of the obtainable configuration spaces, than the ASM and the CFG.