1 Introduction↩︎

The concept of self-organized criticality was introduced in [1] with the sandpile model as its paradigmatic example. Beyond its physical relevance, sandpiles have been extensively studied under the lens of complexity theory as a type of cellular automaton [2]–[4]. A central question in this context is how hard it is to compute the future global states of the model. This is captured by the prediction problem: given a distribution of sand grains and a target cell, does the target cell eventually topple? Early results by Moore and Nilsson [2] show a dichotomy: in one-dimensional sandpiles, the problem can be decided efficiently in parallel (it belongs to \(\text{{\fontfamily{cmss}\selectfont NC}}^3\)); while for three or more dimensions, it becomes a P-complete problem, leaving the two-dimensional case open and remains open to this day. The main issue is that P-completeness proofs (in this context) rely on embedding non-planar monotone Boolean circuits on the sandpile grid, therefore two dimensions is intuitively not enough. This was formalized by Gajardo and Goles [5] by proving that no crossing gate is possible on two-dimensional sandpile (with the von Neumann or Moore neighborhoods). Crossing gates simulate two signals crossing, enabling connections between other circuit components. Crossing gates are therefore crucial when proving P-completeness in the context of two-dimensional cellular automata [6]–[9] and are typically the hardest component to construct. The latter motivated a line of research focusing on embedding arbitrary Boolean circuits into two-dimensional sandpiles under different settings [8], [10]–[13]. This work is intended to contribute to this line of research with a particular focus on crossing gates.

1.0.0.1 Contribution.

Our contribution consists in three main results. First, we define the notions of primal and weighted grids. In a \(\mathcal{P}\)-primal grid, each cell has at most one out-neighbor from \(\mathcal{P}\). In a weighted \(\mathcal{P}\)-grid, the neighborhood is defined as a multiset over \(\mathcal{P}\), therefore the distribution of grains to the neighbors can differ from the uniform distribution, but is identical across all cells. We prove that a \(\mathcal{P}\)-primal grid admits a crossing gate if and only if there exists a weighted \(\mathcal{P}\)-grid that allows a crossing gate. This result tackles one of the research directions proposed by Concha-Vega et al. [8] related to non-uniform sandpiles.

Secondly, we ask whether all crossing gates have exactly two edges (of their toppling graphs) that cross, motivated by observation of the known crossing gates in the literature. We give a negative answer by showing a neighborhood that always needs more crossings edges.

Finally, we show that the equivalence fails for general decompositions (in non-primal and non-uniform grids), by giving counter-examples for both implications.

1.0.0.2 Outline

This article is organized as follows. In Section 2, we give an overview of the necessary concepts and previous results relevant to our work. Our results are then presented in Sections 3, 4, and, 5 respectively. Finally, we conclude in Section 6.

2 Preliminaries↩︎

2.1 Sandpile automaton↩︎

A two dimensional sandpile is a cellular automaton defined on a \(\ell \times \ell'\) grid, where each cell contains a nonnegative number of sand grains. We denote the set of cells by \(V := \llbracket 1, \ell \rrbracket \times \llbracket 1, \ell' \rrbracket\). A configuration is a function \(c: V \rightarrow \mathbb{N}\) that assign to each cell the number of grains it contains. When a cell has too many grains, it topples and sends some of its grains to neighboring cells; this defines the dynamics of the system. Each cell \(u \in V\) is associated with a neighborhood \(\mathcal{N}_u \subseteq \mathbb{Z}^2 \backslash \{(0, 0)\}\). A cell is stable if it contains less than \(|\mathcal{N}_u|\) grains; otherwise, it is unstable and topples, sending one grain to each of its neighbors \(v = u + \delta\) where \(\delta \in \mathcal{N}_u\). We extend the notion of stability to configurations by saying that a configuration is stable if all its cells are stable. Formally, applying one parallel step of this rule to a configuration defines the following update function \(T\):

\[T(c)(u) = c(u) - |\mathcal{N}_u| H(c(u) - |\mathcal{N}_u|) + \sum_{v \in V} \mathcal{N}_v (u - v) H(c(v) - |\mathcal{N}_{v}|)\]

Where \(H(x) := 1\) if \(x \geq 0\) and \(0\) if \(x<0\), is the Heaviside step function. Most works consider that all cells have the same neighborhood; we call such grids uniform. This neighborhood is typically assumed to span \(\mathbb{Z}^2\). We allow \(\mathcal{N}_u\) to be a multiset i.e., a toppling cell may send multiple grains to the same neighbor. Grids with multiset neighborhoods are called weighted (see Figure 5 left).

To simplify the study of uniform sandpiles, we introduce a sink vertex denoted \(s\), which never topples. Whenever a cell has neighbors outside of the grid boundaries, it sends the corresponding grains to \(s\). Likewise, any neighbors that would have sent grains from outside the grid are redirected to \(s\). Under this convention, each cell has as many out-neighbors as in-neighbors, so uniform grids can be assumed to be Eulerian.

Two uniform grids have been greatly studied in the literature [2], [5], [14]: the uniform grid with the von Neumann neighborhood, the four cardinal adjacent cells, and with the Moore neighborhood, the eight adjacent cells (Figure 1).

Dhar has shown that configurations on uniform grids with von Neumann or Moore neighborhoods can always be stabilized by applying \(T\) a polynomial number of times, and that a non-deterministic sequential application of topplings (one-by-one) does not impact the resulting stable configuration [14]. This result can be extended to any uniform grid: a configuration on a uniform grid can always be stabilized in a polynomial number of topplings (\(\#\text{grains} \cdot \ell^4\)). Figure 2 presents an example of stabilization.

2.2 Toppling prediction and crossings↩︎

We focus on the decision problem of predicting whether a given cell will topple during the stabilization of a configuration as formalized below. As non-uniform grid are not always stabilizable, and stabilization may not occur in polynomial time, we restrict this problem to uniform grids.

Moore and Nilsson [2] proved that PRED is P-complete for 3-dimensional sandpiles with the von Neumann or Moore neighborhoods. In contrast, for 1-dimensional sandpiles, the prediction problem is in NC(polylogarithmic time with a polynomial number of processors) for the von Neumann neighborhood.

To prove the P-completeness of 3-dimensional PRED, they use a reduction from the Monotone Circuit Value Problem. The circuit is embedded in a sandpile configuration using gadgets that implement, the OR and AND operations. These gadgets are connected by wires, which consist of sequences of stable cells holding a maximal number of grains. A true signal is represented as the chain reaction of toppling along a wire: when a cell topples, it destabilizes the next cell, thereby propagating the signal.

However, their construction does not apply for 2-dimensional sandpiles because the non-planarity of the circuits is required for P-completeness [15]. Moreover, Gajardo and Goles [5] showed that 2-dimensional uniform grids with von Neumann or Moore neighborhoods cannot implement signal crossings using toppling chains (and no other encoding of circuit is currently known). Formally, they proved that no crossing gate exists in 2-dimensional Moore or von Neumann grids. Intuitively, a crossing gate is a gadget that allows toppling wires to cross without interfering with each other.

A more precise definition can be found in [8]. When studying crossing gates, it is useful to consider the toppling graphs of the crossing gate, which represent the order in which topplings occur justifying that this parallel definition will also capture sequential dynamics. Figure 3 presents an example of a simple crossing gate with its two toppling graphs.

One important fact that justifies the previous definition is that, when a single grain is added to each cell along an edge, no cell topples more that once. Gajardo and Goles proved this fact for von Neumann and Moore neighborhoods, but the result holds for all Eulerian grid. To see why, consider the first cell to topple twice. It cannot be an interior cell, because initially it is stable and can receive at most \(|\mathcal{N}_u|\) grains if all its incoming neighbors have toppled. The designated cell initially receive one additional grain, but since it has an incoming edge from the sink \(s\), which never topples, it cannot topple twice either.

Gajardo and Goles [5] proved that intersections between the toppling graphs are useless and that crossing gates can always be constructed such that the North-toppling and West-toppling graphs have disjoint vertex sets. This result was later extended to Eulerian grids by Nguyen and Perrot [11].

In the next sections, we will present our contribution about the link between non-uniform and weighted crossing gates.

3 Trading primal non-uniformity for weighted uniformity↩︎

In this section, we present our main result: a primal non-uniform grid admits a crossing gate if and only if there exists a weighting of these neighborhoods that admits a crossing gate on a uniform grid.

3.0.0.1 Remark.

If \(|\mathcal{P}| = 1\), then the grid is uniform and the model is trivial. Hence, we are mainly interested in the case \(|\mathcal{P}| > 1\), which we simply call \(\mathcal{P}\)-primal grids.

The existence of a crossing gate on a \(\mathcal{P}\)-primal grid is closely related to the planarity of the \(\mathcal{P}\)-grid. Indeed, if there is a \(\mathcal{P}\)-primal grid that admits a crossing gate, as it transports grains from the North to the South, and from the West to the East distinctly, then the \(\mathcal{P}\)-grid is necessarily non-planar. Conversely, if a \(\mathcal{P}\)-grid is non-planar, we can use the directions that cross to create a crossing gate on a \(\mathcal{P}\)-primal grid. The fact that each cell has only one neighbor will ensure that the configuration transports grains independently. The last notion we need in order to state our theorem is that of a weighted neighborhood.

We see that the proof only considers crossing gates with a unique edge-crossing. This is because, as we can choose the weighting, we can increase the weights of the two crossing directions in order to make them independent of the other neighbors (as used in the proof). We will see in the next section that gates with more complicated crossing exist.

4 Intertwined crossing gates↩︎

Consider the neighborhood \(\mathcal{N}_i = \{(1,1), (-1,-1), (0,-1), (1,-1), (0,-2)\}\) (Figure 6). It admits a crossing gate (Figure 7). However, contrary to the previous section, the two wires cross with multiple steps. We argue that for every possible crossing gate on a uniform grid with neighborhood \(\mathcal{N}_i\), there will always be a cell in the middle of the crossing. Formally, we say that two edges cross if, by drawing segments between the cell center, the segments (including the center endpoints) intersect. We consider the end-extremity to be part of the seggment but not the start-extremity (to avoid counting the vertical edge twice).

For the proof of the next result, we use the following notation. Let \(a,b \in V\) be two cells, \(\mathcal{N}\) a neighborhood, \(d \in \mathcal{N}\) a direction, and \(c\) a crossing gate for the \(\mathcal{N}\)-grid with toppling graphs \(G_n\) and \(G_w\). We write \(a \stackrel{d}{\to} b\) to indicate that \(a + d = b\) and that \((a,b)\) is an edge of \(G_n\) or \(G_w\), depending on the context.

5 Counter-examples to general decomposition↩︎

As shown in Section 3, non-uniformity and weighting can be traded. However, as demonstrated in Section 4, this equivalence only captures simple crossings. We attempted to generalize the notion of primal-grid into a broader decomposition. This exploration led to the identification of counter-examples demonstrating that crossing gates are not easily composable. In this section we exhibit those counter-examples.

To generalize the previous definition of primal grids, we consider decompositions of arbitrary shape rather than restricting to primal directions. Let \(S\) be a set of (possibly weighted) neighborhoods, we are interested in the relation between non-uniform grid composed of neighborhoods of \(S\), and uniform grids whose neighborhoods are multisets on \(S\). Our results indicate that the existence of crossing gates in one setting does not imply their existence in the other, revealing fundamental differences between these grid constructions

Our techniques are applicable only to grids satisfying the following property: adding one on one edge, each cell topples at most once during stabilization. This property does not hold in general for non-uniform grids. To circumvent this limitation, in this section we consider a variant of the sandpile dynamics in which each cell is allowed to topple at most once.

6 Conclusion and perspectives↩︎

To conclude, in section 3, we established a characterization of weighted uniform crossing gates in terms of a simpler class of structures, which we call primal crossings. However, this characterization does not capture more complex crossings, like the intertwined crossings of section 4. Finally, in Section 5, we show that the above equivalence does not extend to more general settings, where the decomposition into simpler but not primal structures fails. We emphasize that Theorem 1 facilitates \({\fontfamily{cmss}\selectfont P}\)-completeness proofs, as the construction of the remaining components for reductions from CVP is typically straightforward.

While crossing gates are a central ingredient in proving P-completeness for cellular automata, their absence does not rule out P-completeness, since there may exist other ways of encoding signals than just creating chains of topplings or reductions may exist beyond chain-like toppling structures.

Moreover, even when the equivalence preserves the existence of crossing gate, it does not preserves the computational complexity: on primal grids, grain movement is highly restricted allowing efficient NC algorithms for the prediction problem. In contrast, weighted grids appear to support significantly richer dynamics and are natural candidates for P-completeness.

We leave open what we consider our Holy Grail: the complexity of prediction in 2-dimensional uniform sandpiles with von Neumann or Moore neighborhoods. More broadly, this work raises structural questions about crossing gates: in particular, it is unclear whether there exist families of grids requiring arbitrarily large numbers of crossing edges, or whether deciding the existence of a crossing gate is even decidable in general.

References↩︎