Deterministic Abelian Sandpile and Square-Triangle Tilings

Abstract

The Abelian Sandpile Model, seen as a deterministic lattice automaton, on two-dimensional periodic graphs, generates complex regular patterns displaying (fractal) self-similarity. In particular, on a variety of lattices and initial conditions, at all sizes, there appears what we call an exact Sierpinski structure: the volume is filled with periodic patterns, glued together along straight lines, with the topology of a triangular Sierpinski gasket. Various lattices (square, hexagonal, kagome, …), initial conditions, and toppling rules show Sierpinski structures which are apparently unrelated and involve different mechanisms. As will be shown elsewhere, all these structures fall under one roof, and are in fact different projections of a unique mechanism pertinent to a family of deterministic surfaces in a four-dimensional lattice. This short note gives a description of this surface, and of the combinatorics associated to its construction.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Let $\Lambda$ be the lattice in dimension 4, tensor product of two copies of the triangular lattice, $\Lambda =\langle e_{1},e_{2},e_{3},e_{4},e_{5},e_{6}\;\vert \sum _{1\leq i\leq 3}e_{i} =\sum _{4\leq i\leq 6}e_{i} = 0\rangle _{\mathbb{Z}}$. Consider the two-dimensional cell complex containing all the vertices and edges of $\Lambda$, and, as (oriented) faces, the triangles of the two lattices and the parallelograms spanned by pairs $(e_{1},e_{4})$, $(e_{2},e_{5})$ and $(e_{3},e_{6})$. We choose the orientation such that the cycles $(e_{1},e_{2},e_{3})$, $(-e_{1},-e_{2},-e_{3})$ and $(e_{1},-e_{4},-e_{1},e_{4})$ are upward faces, and similarly with (123) → (456) and (14) → (25), (36). We call a surface a connected and simply-connected collection of faces in the cell complex above, with all upward faces.

Embeddings of $e_{1},\ldots,e_{6}$ in $\mathbb{R}^{2}$ satisfying the forementioned orientation constraints correspond to projections of the four-dimensional cell complex on a two-dimensional real space, such that surfaces are mapped injectively. An example of such an embedding is $(e_{1},\ldots,e_{6}) = (\omega ^{3},\omega ^{11},\omega ^{7},\omega ^{0},\omega ^{8},\omega ^{4})$, where $\omega ^{k} = (\cos \frac{k\pi } {6},\sin \frac{k\pi } {6} )$. In this case, surfaces correspond to tilings of regions of the plane, composed only of squares and triangles of unit sides, and along directions multiple of π∕6. These tilings are called square-triangle tilings in the literature.

Any other projection is topologically equivalent, provided that $e_{1} + e_{2} + e_{3} = e_{4} + e_{5} + e_{6} = 0$ and the orientation of the faces is preserved. We call valid such a projection. The set of valid projections is an open portion of an algebraic projective variety. We call degenerate projections those on the boundary of this open set. Under degenerate projections, the image of some faces is a segment or a point.

A seminal work of de Brujin for Penrose–Ammann lozenge tilings [2] has first illustrated the possibility that projections of deterministic surfaces from a high-dimensional periodic cell-complex could explain features of two-dimensional aperiodic incommensurable tilings. The square-triangle case discussed here shows a similar phenomenon.

Square-triangle tilings have also distinguished properties, among which is a relation with Algebraic Geometry, generalising the well-known connection between lozenge tilings and Schur functions (see e.g. [1]). The algebra of Schur functions has ubiquitous three-index structure constants $c_{\lambda,\mu }^{\bar{\nu }}$, called Littlewood–Richardson (LR) coefficients [16]. When the Young diagrams λ, μ, $\bar{\nu }$ are boxed in a rectangle (d − n) × n (as is the case, e.g., when they label cells of the Schubert variety), there exists a relation (Poincaré duality) which acts as complementation at the level of diagrams, $\nu \leftrightarrow \bar{\nu }$, and the LR coefficients are symmetric in all three indices if the upper one is complemented, $c_{\lambda,\mu }^{\bar{\nu }} =: c_{\lambda,\mu,\nu }$. As shown by P. Zinn-Justin [21] and Purbhoo [20], the LR coefficients correspond to the enumerations of square-triangle tilings over triangoloids whose three sides are built from λ, μ and ν, respectively. Two degenerate projections of these surfaces reduce to portions of the square and of the triangular lattice. As degenerate projections transform some faces into segments or points, the bijective correspondence is preserved only if extra integer labelings, encoding the disappeared faces, are added to the resulting structures. These limiting tilings, together with the auxiliary labelings, correspond to the original Littlewood–Richardson rule [16] in the square case, and to the Knutson–Tao (discrete) honeycombs [11, 12] in the triangular case.

2 ASM and Square-Triangle Tilings

The purpose of this paper is to illustrate another unsuspected feature specific of square-triangle tilings, namely of encoding the exact Sierpinski structures that arise in the Deterministic Abelian Sandpile Model. These structures have been identified on various regular two-dimensional lattices, under various abelian toppling rules, initial conditions and deterministic evolution protocols, and square-triangle tilings describe them in a unified way.

The first occurrences of such structures have been presented, by the authors, in [3, 19], while the observation of approximated versions of these structures (reproduced at a coarse-grained scale, but locally deformed by some one-dimensional defects) is much older [18], and has first been made, only on the square lattice, for the two most natural deterministic protocols: the evaluation of the identity configuration in simple geometries [6, 13, 17], and the relaxation of a large amount of sand put at the origin, in the (elsewhere empty) infinite lattice [7, 8, 14, 15].

The ‘universal role’ of the square-triangle tiling, in different ASM realisations, should sound surprising, as the generic projection gives incommensurable parallelogram-triangle tilings and does not live on a discrete two-dimensional lattice, as is instead the case for the sandpile models we consider. What comes out is that, in a remarkable analogy with the mechanism discussed above for the combinatorics of the Littlewood–Richardson rule and Knutson–Tao honeycombs, different lattice ASM realisations occur at different “rational” points in the set of valid projections (and its boundary, of degenerate projections).

As this short paper is within a series, we do not give here an introduction to the Abelian Sandpile Model. The interested reader can consult the beautiful review by Deepak Dhar [5], who first established a large part of the theory. For aspects of the model more strictly related to the features discussed here, the reader can refer to the PhD thesis of one of the authors [19], or the shorter papers [3] and [4]. Here we will only concentrate on the aspects concerning the surfaces in the square-triangle tiling corresponding to the exact Sierpinski structures in the ASM.

The sandpile configurations are height vectors $\vec{z} =\{ z_{i}\}$, with variables $z_{i} \in \mathbb{N}$ associated to vertices i of a graph G = (V, E). There exists a notion of stable configuration, and a more restrictive notion of recurrent one. Transient is a synonimous for non-recurrent. There exists a notion of forbidden sub-configuration (FSC), and a stable configuration is recurrent iff it has no FSC. More generally, a configuration is recurrent over $W \subseteq V (G)$ if it has no FSC contained within W, thus making recurrency a local notion (like instability). Local recurrency and instability are dual notions, if we set in the wider frame of multitoppling ASM, as first shown in [4]. The toppling matrix $\Delta$ encodes the dynamics of the sandpile, and determines a subdivision of $\mathbb{Z}^{V (G)}$ into equivalence classes. There exists exactly one stable recurrent configuration within each class. Unstable configurations $\vec{z}$ can be relaxed to stable ones, $\vec{w} = \mathcal{R}\vec{z}$. Stable transient configurations can be projected to the unique recurrent representative in the class, $\vec{w} = \mathcal{P}\vec{z}$. The operators $\mathcal{R}$ and $\mathcal{P}$ correspond to find the fixed point of iterated maps, $\mathcal{R}_{0}$ and $\mathcal{P}_{0}$, corresponding to “rounds” of the procedure.¹

A number of structures and operations on square-triangle tilings can be introduced, that will reproduce, under the various projection procedures, the forementioned counterparts in the various ASM realisations. We dub all these features of the square-triangle setting with the “axiomatic” attribute, as the reason for their names emerges only when the projection procedure is explicitated. Note that we are not able to reproduce all the relevant features of the sandpile model. In particular, we are not able to reproduce the a _i operators (nor their counterparts $a_{i}^{\dag }$ defined in [4]). The main things we are able to reproduce are summarised by the following list:

• The notion of (ASM-)equivalence of configurations is trivialised at the axiomatic level: two tilings are equivalent if they have the same boundary.

• The axiomatic notion of FSC correspond to cycles in the tiling satisfying certain local rules.

• We have an axiomatic notion of $\mathcal{P}_{0}$, consisting in a local deformation along the cycles of maximal FSC’s (w.r.t. inclusion).

• Similarly, we can certify that regions encircled by certain cycles will undergo a round of relaxation. This gives an axiomatic local notion of unstable subconfiguration (USC).²

• We have an axiomatic notion of $\mathcal{R}_{0}$, consisting in a local deformation along the cycles of maximal USC’s (w.r.t. inclusion).

• We have a recursive description of the Sierpinski structures at the axiomatic level. As these structures in the ASM determine the classification of patches and propagators in certain backgrounds [19], this induces a corresponding classification of axiomatic patches and propagators.

• A choice of vectors e ₁,…,$e_{6} \in \mathbb{R}^{2}$, and of “masses” $\{m_{123},m_{456},m_{14},m_{25},m_{36}\}$ for the five types of tiles, induces a notion of density for the patches. This allows to state an axiomatic version of the Dhar–Sadhu–Chandra incidence formula, first introduced, for the ASM, in [7].

3 Sierpinski Structures

Let $\mathbf{s} = (\mathbf{s_{k},\ldots,s_{1},s_{0}})$ be a finite string of positive integers, and $n(\mathbf{s}) =\sum _{i}3^{i}s_{i}$. A Sierpinski structure is labeled by a string s, and n(s) is its size. Structures of the same size are equivalent.

An abstract Sierpinski gasket of index k is defined as follows. At index 0, it is just a dark upward triangle. At index k + 1, it is obtained from the gasket at index k by subdividing all dark upward triangles into three dark upward and one light downward triangles, all of half the side. Light triangles which are there at index k, will remain unchanged at all k′ > k. A light triangle has index k if it first appeared in a gasket at index k + 1. A gasket of index k has 3^k dark triangles, and 3^h light triangles of index h, for 0 ≤ h < k. See Fig. 1.

Fig. 1

Top: The labeling of the light triangles; Bottom left: the Sierpinski gasket of index k = 3; Bottom right: The structure of the patches, and the role of the parameter s

In the sandpile setting, the triangles of the gasket will determine polygonal regions filled with a biperiodic patterns, called patches [18]. Patches may be recurrent, transient or marginal, depending on their behaviour under the burning test (see [3]).

In a Sierpinski structure identified by s, all the dark triangles correspond to transient patches, of triangular shape, with a side of s _k unit tiles. Light triangles of index h correspond to polygonal regions filled with recurrent patches. These regions have the aspect of triangoloids with concave sides, the sides being polygonal lines composed of $2^{k-h} - 1$ segments. The packing of unit tiles depends in a certain fixed way on the integer k − h and the variables s _h′ for h′ > h, and has no extra freedom, with an exception: starting at the vertices of the triangoloids, we can have a band of a patch with marginal density, of width s _h − 1.³ The three bands meet at a triangular transient patch.

A transient patch contains a FSC only if “sufficiently large”, namely if it contains at least 7 unit tiles, packed in a shape

. Thus, a triangle of side up to 3 units filled with a transient patch, i.e. the shape

, may still be part of an overall recurrent configuration. This has a consequence on our Sierpinski structures: a structure with label s is recurrent if and only if 1 ≤ s _h  ≤ 3 for all h ≤ k. These are the structures ultimately appearing in sandpile protocols.

Each region of the Sierpinski structure is filled with a periodic pattern. The geometry of every region, including the number and location of the unit tiles, is determined through a recursive procedure. Also the shape of the unit tiles, and their content in terms of elementary squares and triangles, are determined recursively. At this aim it is useful to introduce a labeling of the regions of the Sierpinki gasket. We label the dark upward triangles with words in the alphabet {a, b, c}, and the light downward triangles with the same word as the dark triangle that originated them. When a triangle of label w is split, the three new triangles, in the three directions, have labels wa, wb and wc. We also give labels to the three external regions of the triangles, as a ⁻¹, b ⁻¹ and c ⁻¹. See Fig. 1.

A triangle with label w has three larger adjacent light triangles, in the three directions, that have labels α(w), β(w) and γ(w). These three functions can be defined as follows. Let α _w , β _w and γ _w the rightmost position along w such that, at its right, there are no more a, b or c, respectively; let us call w |  _ℓ the truncation of w to its first ℓ letters; let us understand that $aa^{-1} = bb^{-1} = cc^{-1} = 1$. Then $\alpha (w) = w\vert _{\alpha _{w}}a^{-1}$, and so on.

Complex tiles arise from the superposition of more elementary ones. Only three tiles are indecomposable, and must be given as input. These tiles correspond to the three square orientations in our square-triangle tilings. The corresponding tilings appear outside the triangle, at the three sides. The unit tile of label w is composed of the superposition of two copies of the tiles of labels α(w), β(w) and γ(w). Unless w = 1, one of these three words has higher degree than the other (say α(w)). In this case, the six tiles do not overlap, with the only exception that the two α(w) tiles do overlap exactly on a α(α(w)) tile. If w = 1, no tiles overlap. Each tile has 12 special positions along its boundary, which determine the translation vectors of the recurrent, transient and marginal tilings involving it, and the new tile inheritates its owns positions from those of the three subtiles. This mechanism is illustrated in Fig. 2.

Fig. 2

The tile associated to w = cba. The interior orange lines describe the decomposition into α(w), β(w) and γ(w) tiles. The overlap, composed of a α(α(w)) tile and two light triangles, is in the middle. The triangles outside the tile denote the 12 special positions. Here we have $u(P) =\ \big((\underline{6}1),(\underline{2}\underline{6}1\underline{6}),(434\underline{2}\underline{6}1\underline{6}\underline{2}),$ $(34),(\underline{5}343),(\underline{1}6\underline{1}\underline{5}343\underline{5})\big)$

4 Dual Tiles

Our construction in terms of the vectors e ₁, …, e ₆ has a number of covariances that allow to shorten our description

C ₃ -covariance (2π∕3 rotations):

$(e_{1},e_{2},e_{3},e_{4},e_{5},e_{6}) \rightarrow (e_{2},e_{3},e_{1},e_{5},e_{6},e_{4})$;

exchange $\mathbf{(123) \leftrightarrow (456)}$ (π∕2 rotations):

$(e_{1},e_{2},e_{3},e_{4},e_{5},e_{6}) \rightarrow (e_{4},e_{5},e_{6},-e_{1},-e_{2},-e_{3})$;

central symmetry (π rotations):

$(e_{1},e_{2},\cdots \,,e_{6}) \rightarrow (-e_{1},-e_{2},\cdots \,,-e_{6})$.

We call polygon a closed curve that is the boundary of some square-triangle tiling. A polygon P is determined by a cyclic sequence in the alphabet $\{1,\ldots,6,\underline{1},\ldots,\underline{6}\}$, where 1, $\underline{1}$ stand for + e ₁, − e ₁, and so on. We use the shortcuts $\blacktriangle$, $\blacktriangledown$, $\triangleright$ and $\triangleleft$ for the polygons (123), $(\underline{1}\underline{2}\underline{3})$, (456) and $(\underline{4}\underline{5}\underline{6})$, respectively.

A centrally symmetric polygon P is determined by a sequence of the form $P = (i_{1}i_{2}\ldots i_{k}\underline{i_{1}}\,\underline{i_{2}}\ldots \underline{i_{k}})$, where $\underline{\underline{i}} = i$. We use the shortcut $(i_{1}i_{2}\ldots i_{k}\Vert )$ in such a case.

A polygon P is a dual tile if both the triple of polygons $(P,\blacktriangle,\blacktriangledown )$ and the triple $(P,\triangleright,\triangleleft )$ (in these proportions) tile periodically the plane. We call a transient / recurrent hex tiling a tiling of the two forms above, respectively.

The three fundamental parallelogram tiles are dual tiles. The dodecagon, $(1\underline{6}\underline{2}43\underline{5}\Vert )$, is another example. All the tilings associated to dual tiles, except those deriving from the fundamental parallelograms, have the topology of a hexagonal tiling: each polygon P is neighbour to other 6 P’s. The fundamental triangles are at the 6 triple points, with alternating orientations cyclically along each P.

To each word w as in the previous section can be associated a dual tile P(w), which is centrally symmetric. The three fundamental parallelograms are $(41\Vert ) = P(a^{-1})$ and so on. The dodecagon is $(1\underline{6}\underline{2}43\underline{5}\Vert ) = P(1)$.

A pair of polygons (P, Q) is a dual pair if the sextuplet $(P,Q,\blacktriangle,\blacktriangledown,\triangleright,\triangleleft )$ (in these proportions) tiles the plane. We call a sq-oc tiling a tiling obtained as above. Neglecting triangles (e.g., replacing them with Y -shapes), such a tiling has the square-octagon topology: any Q tile is neighbour to 4 P ones, and any P tile is neighbour to 4 P’s and 4 Q’s, alternating.⁴ The fundamental triangles are at the triple points of the square-octagon topology. Each P and Q tile is adjacent to 8 and 4 triangles, respectively, alternating dark / light, and, within dark and light ones, of opposite orientations.

For each w, the pairs of tiles $\big(P(\alpha (w)),P(w)\big)$, $\big(P(\beta (w)),P(w)\big)$ and $\big(P(\gamma (w)),P(w)\big)$ are dual pairs. For example, the dodecagon and any of the fundamental parallelograms form a dual pair.

Exceptionally, and analogously to what happens for hex tilings, also all pairs of fundamental parallelograms are dual pairs, although with a different topology, and with no ordering.

As a consequence, each tile P = P(w) appears in two hex tilings, three sq-oc tilings as ‘octagon’, and infinitely many sq-oc tilings as ‘square’. The union of the positions of triple points among all these tilings has cardinality 12. These 12 special positions break the perimeter of the tile into open paths, related by the central symmetry (see again Fig. 2). Thus, a list of 6 paths, $u(P) = (u_{1},\ldots,u_{6})$, determines simultaneously the perimeter and the special positions, and $P = (1u_{1}\underline{6}u_{2}\underline{2}u_{3}4u_{4}3u_{5}\underline{5}u_{6}\Vert )$.

The recursive construction, at the level of these paths, leads to the formulas (completed by C ₃-covariance)

$$\displaystyle\begin{array}{rcl} & (u_{1}\underline{6}u_{2})_{w} = (u_{1}\underline{6}u_{2}\underline{2}u_{3})_{\beta (w)}\;\underline{6}\;(\underline{u_{6}}1u_{1}\underline{6}u_{2})_{\gamma (w)} & {}\\ &\left \{\right.\begin{array}{lc} (u_{1})_{w} = (u_{1})_{\alpha (w)} & \vert \alpha (w)\vert> \vert \beta (w)\vert \\ (u_{2})_{w} = (u_{2})_{\beta (w)} & \vert \alpha (w)\vert <\vert \beta (w)\vert \\ (u_{1})_{w} = (u_{2})_{w} = \varnothing &\qquad \alpha (w) = a^{-1},\beta (w) = b^{-1}.\end{array} & {}\\ \end{array}$$

The geometry of these paths is such that:

• The sq-oct patches based on a (P, Q) dual pair may be adjacent to both recurrent and transient hex patches, based both on P and on Q, although with a restriction on the direction of the (straight) boundary.

• The hex transient tiling based on P(w) can be adjacent to the hex recurrent tiling based on P(w′), if w′ is a prefix of w.

This ultimately leads to the consistency of the construction of the Sierpinski structures (see Fig. 3).

Fig. 3

Four classes of equivalent configurations: Left: three deterministic configurations, of size n = 6. The two on top are stable but transient, and the one on the bottom is recurrent but unstable. Applying $\mathcal{P}$ and $\mathcal{R}$, respectively, we obtain our axiomatic Sierpinski structure, (on the right at s = (1, 2, 2), thus n(s) = 17). The patch structure is highlighted by the orange construction lines, showing the same topology of the Sierpinski gasket in Fig. 1