Chip-Firing Revisited: A Peek Into The Third Dimension

Year: 2022 Authors: Martin Skrodzki; Ulrich Reitebuch

Core claim

Three-dimensional chip-firing on cubical, face-centered, cube-centered, and knight-move neighborhoods produces distinct, visually rich stable patterns and divergence thresholds.

Topics

chip-firing, three-dimensional lattices, stable states, visualization, sandpiles

Domains

graph theory, discrete dynamical systems, combinatorics, lattice geometry, generative art, data visualization, mathematical visualization

Methods

iterative firing process, uniform backgrounds, color mapping, lattice neighborhood comparison

Media

JavaView, digital images, 3D grids

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2022 Conference Proceedings

Chip-Firing Revisited: A Peek Into The Third Dimension

Martin Skrodzki ${}^1$ and Ulrich Reitebuch ${}^2$

${}^1$ CGV, TU Delft, the Netherlands; mail@ms-math-computer.science

${}^2$ Institut für Mathematik, Freie Universität Berlin, Germany; ulrich.reitebuch@fu-berlin.de

Abstract

Chip-firing was first introduced as a probabilistic game. Subsequently, it was generalized to arbitrary graph configurations and investigated mostly with regard to two-dimensional quad-grid layouts. In this paper, we lift chip-firing to the third dimension. Aside from the arising three-dimensional shapes, we are interested in the internal, two-dimensional structures. Furthermore, we explore the different shapes obtained by chip firing processes on various neighborhoods, such as the face-centered and the cube-centered grid as well as on a neighborhood inspired by knight moves.

Chip-Firing

The game of chip-firing belongs to the class of solitaire games. It was first introduced as probabilistic abacus by Arthur Engel in 1975, see [5]. Its one-dimensional version was later independently invented by Joel Spencer in 1986 [11]. The generalized version is played on a graph $G$ without loops. Initially, each vertex $\nu$ of $G$ is given a number $c_{\nu }\in \mathbb{N}$ of chips. Then, the following process, called firing, is repeated iteratively:

1. Pick a vertex $\nu$ that has at least as many chips as neighbors, i.e., $c_{\nu }\ge \mathrm{deg}(\nu )$ .
2. Then, for each neighbor $w$ of $\nu$ , increase $c_w$ by one and decrease $c_{\nu }$ by $\mathrm{deg}(\nu )$ .

In case there is no vertex that can fire, the configuration is said to be in a stable state. Consider Figure 1 for a visualization of this process. In the example given in the figure, seven chips are distributed on a graph with five vertices and seven edges. The vertices then fire in the order: ${\nu }_0,{\nu }_1,{\nu }_4$ .

If the number of chips initially distributed is less than the number of edges of $G$ , the game is always finite [2]. Furthermore, it can be shown that reaching a stable state is independent of the order in which the vertices are selected to fire [2]. Note that in the example in Figure 1, a stable state is reached after firing three vertices, and the firing order of vertices ${\nu }_1$ and ${\nu }_4$ can be exchanged without impacting the final result.

Chip-firing models have also been independently described by Bak, Tang, and Wiesenfled under the name of Abelian Sandpiles. See [8] for similarities and differences between the two descriptions as well as for a

Figure 1: Example for a chip-firing process on a graph with five nodes ${\nu }_0$ to ${\nu }_4$ . Initially, they hold $c_{{\nu }_0}=5$ , $c_{{\nu }_1}=c_{{\nu }_4}=1$ , and $c_{{\nu }_2}=c_{{\nu }_3}=0$ chips. A stable state is reached after three vertices fired in the order ${\nu }_0,{\nu }_1,{\nu }_4$ . In the stable state, the vertices have $c_{{\nu }_0}=3$ , $c_{{\nu }_1}=c_{{\nu }_4}=0$ , and $c_{{\nu }_2}=c_{{\nu }_3}=2$ chips.

Skrodzki and Reitebuch

(a) Background: 0. (d) Background: 3. Figure 2: Two-dimensional visualizations of the chip-firing process on uniform backgrounds and initial chips within a disk or a square. Reproduction with kind permission of Bruce Torrence.

(b) Background: 1. (e) The piece “Sandpile Fractile Disk” by B. Torrence [12].

(c) Background: 2. (f) The piece “Sandpile Fractile Square” by B. Torrence [12].

detailed discussion of the mathematical background and see [4] for a brief introduction to sandpiles. There are two previous Bridges publications that discuss artistic explorations of chip-firing. Gary Greenfield explores patterns emerging from the one-dimensional version of chip-firing in the form of a cellular automaton [6, 7]. John Lind interprets the chip-firing process as a discretization of the Laplacian and uses it to create music [9].

To visualize the process of two-dimensional chip firing on the square grid, we start by placing a number of chips on the origin. Furthermore, we choose to place a uniform number of chips on all other vertices of the grid, which we call the background. Then, we follow the procedure described above and finally color all those vertices that have been fired to at least once according to the number of chips they have. This results in Figures 2a to 2c when using backgrounds 0, 1, and 2, respectively. Note that each vertex on an infinite square grid has four neighbors. Thus, providing a background of 3 results in infinitely many fire events and no stable state is reached. Hence, for background 3, we stop the process after a number of steps and report the current state, see Figure 2d. Alternatively, we could either apply the background to only a finite section of the grid (see the discussion of Bruce Torrence’s work below) or we could work on a finite square grid and have a background of $-\infty$ at the boundary vertices, which then act as sinks. All three approaches will qualitatively lead to the same structures.

For our visualization, we employ the following coloring scheme. It is inspired by “cold,” blue vertices that are far from firing, i.e., that have few chips, to “hot,” red vertices that are about to fire. More specifically, for a neighborhood with vertices of valence $n$ , when going from 0 to $n-1$ chips, we pass from dark blue, via cyan, green, to yellow. For vertices having more than $n-1$ chips, we pass from yellow via red to white, indicate the glowing readiness of this vertex to fire. This color scheme will be used throughout the paper.

Chip-Firing Revisited: A Peek into the Third Dimension

(a) Background: 0. (d) Background: 3. Figure 3: Running chip-firing on a cubical grid with six neighbors on various uniform backgrounds.

(b) Background: 1. (e) Background: 4.

(c) Background: 2. (f) Background: 5.

To name another artistic work, Bruce Torrence has presented two pieces in the 2018 Bridges Conference Art Gallery, see Figures 2e and 2f, which are both based on chip-firing [12]. Instead of providing a uniform background, Torrence chooses to place a number of chips on the origin, three chips on all vertices within either a disk radius of 400 or within a square of diagonal length 900 around the origin, while choosing background 0 elsewhere. In contrast to our coloring scheme, here, 0 chips is light blue, 1 is burnt orange, 2 is yellow, and 3 is dark blue, cf. the cover image of Klivan’s book [8]. It would now be possible to exploit even more background patterns, yet, for the remainder of this paper, we will consider a different generalization.

Three-Dimensional Chip-Firing

The visualizations considered so far employ planar graphs for the chip-firing process. Thus, the final, stable states obtained can be visualized as two-dimensional pictures. However, there is no inherent reason within the definition of chip firing why to do so. Hence, in the following, we will discuss a generalization of chip-firing to the third dimension. Consider [3] for a discussion of the symmetries of sandpiles on the hypercube.

A straightforward setup for three-dimensional chip firing is a cubical grid, i.e., the vertices are given by ${\mathbb{Z}}^3$ . While each vertex has four neighbors in the two-dimensional quad grid, it has six neighbors in the three-dimensional cubical grid as each vertex has a neighbor left/right, top/bottom, and front/back. Hence, while the two-dimensional images of Figure 2 have colors for vertices with zero, one, two, and three chips, the three-dimensional version needs six colors for zero to five chips.

Similar to the two-dimensional setup, we can place different backgrounds on the grid. As with the two-dimensional visualization, placing different such backgrounds has a significant effect on the shape of the final object, see Figure 3. When placing chips only at the origin and nowhere else (background 0), we obtain a sphere-like shape with visible squares around the coordinate axes, Figure 3a. Increasing the

Skrodzki and Reitebuch

(a) Background: 0.

(b) Background: 1.

(c) Background: 2.

(d) Background: 3.

(e) Background: 4.

(f) Background: 5. Figure 4: Clipping the solid shapes from Figure 3 at $x=0$ to reveal the rich symmetries inside. The cutting plane is shown as a highlight in the lower-right corner.

background to 1, i.e., initially placing a single chip on all vertices of the grid except for the origin, the shape becomes less spherical, but develops more locally linear patches, Figure 3b. This trend continues for growing backgrounds until background 3 yields a shape that approximates a polyhedron with 18 faces, Figure 3d. Finally, background 4 yields an approximation of the cube, Figure 3e. All presented results are run on a number of chips such that the final shapes are roughly of the same size.

Note that, as in the two-dimensional case, a background of vertex valence minus one, i.e., five chips is not possible in this scenario as it would lead to infinitely many fire events without convergence to a stable state. Thus, again, we report an image by stopping the fire process after a certain amount of steps. In the two-dimensional case, with the front expanding in the directions of the quad-grid, we obtained a kite. Now, in this three-dimensional case, as the front of the shape expands along the cubical grid, the resulting shape ends up being an octahedron, Figure 3f.

Aside from changes in the graph-structure, a three-dimensional pattern poses its own visualization challenge. Namely, when showing graph vertices on the outer layers of the pattern, it is not possible to simultaneously examine the internal structure. Hence, rendering each vertex of the cubical grid as a cube of a color corresponding to the number of chips finally placed at this vertex does allow to examine only the outer shape, see Figure 3. A solution to this problem comes in the form of slicing: Instead of showing the entire geometry, we only display parts of it and render other parts transparent. Thereby, we can ‘cut’ into the arrangement and display its outer form as well as its interior structure.

In order to explore the symmetric patterns inside the shapes shown in Figure 3, we choose to clip at the plane $x=0$ . That is, we render all those vertices transparent that have strictly positive $x$ -coordinate. The

Chip-Firing Revisited: A Peek into the Third Dimension

(a) Background: 0.

(b) Background: 1.

(c) Background: 2.

(d) Background: 3.

(e) Background: 4.

(f) Background: 5.

(g) Background: 6.

(h) Background: 7.

(i) Background: 8.

(j) Background: 9.

(k) Background: 10.

(1) Background: 11. Figure 5: Running chip-firing on a face-centered cubical grid on various uniform backgrounds.

Skrodzki and Reitebuch

(a) Cubic

(b) Face-centered cubic

(c) Body-centered cubic Figure 6: The different neighborhoods investigated for the three-dimensional chip firing process.

(d) Knight-half grid.

result is shown in Figure 4 both as a three-dimensional view of the cut and as an orthogonal view onto the cutting-plane. Note that these symmetric configurations do not correspond to two-dimensional chip-firing images. That is, because each vertex shown on the cutting plane has been influenced in the firing process by vertices that are not part of the plane. Therefore, this approach creates a broader range of imagery than two-dimensional chip firing does. While these might be replicable via near-miss two-dimensional setups, the occurring three-dimensional structures are unique to the third dimension. They resemble Archimedean solids, yet, it remains unclear why the different backgrounds create these.

Chip-Firing on Different Graphs

So far, this paper was concerned with visualizations of chip-firing on two-dimensional quad-grids ${\mathbb{Z}}^2$ , see Figure 2, and three-dimensional cube-grids ${\mathbb{Z}}^3$ , see Figure 3. However, the definition of chip firing allows for the process to be run on any graph, grid, or lattice. In the two-dimensional case, Wesley Pegden has compiled a collection of images obtained from the chip-firing process on various planar graphs, see [10]. Similarly, we can perform the chip-firing process on various three-dimensional lattices. In the following, we will explore three different neighborhood relations.

First, we consider the face-centered cubic neighborhood lattice. Here, we consider all those vertices of ${\mathbb{Z}}^3$ such that the sum of their coordinates is even, i.e., the set of vertices is given by

Neighborhoods go in the directions of face-diagonals of the cube. Therefore, each vertex has four neighbors per dimension, i.e., twelve neighbors in total, see Figure 6b for an illustration. The resulting shapes and clipping planes for the possible backgrounds 0 to 11 are shown in Figure 5. As we have observed with the two-dimensional and three-dimensional pictures, for the case of valence minus one, the vertices of the final shape are placed exactly on the vectors indicating the neighborhood, see Figure 5l. As before, this state does not stabilize by itself and has to be stopped by hand. Also, we continue to observe that going back one more step, the faces of the final shape point in the directions indicated by the neighborhood, see Figure 5k.

Next, we turn to the body-centered cubic neighborhood lattice. This consists of all those vertices of ${\mathbb{Z}}^3$ such that all three coordinates are even or uneven, i.e., the set of vertices is given by

In this lattice, neighborhoods run in the direction of space-diagonals of the cube, see Figure 6c. Hence, each vertex has eight neighbors. The resulting three-dimensional shapes and their clipping plane images are shown in Figure 7. The previous observations still hold: The shape in Figure 7g has its faces and the shape in Figure 7h has its vertices at positions indicated by the neighborhood directions.

Chip-Firing Revisited: A Peek into the Third Dimension

(a) Background: 0.

(b) Background: 1.

(c) Background: 2.

(d) Background: 3.

(e) Background: 4.

(f) Background: 5.

(g) Background: 6.

(h) Background: 7. Figure 7: Running chip-firing on a body-centered cubical grid on various uniform backgrounds.

As a last experimental set, we consider a neighborhood inspired by the movements of the knight in chess. That is, we consider all vertices in ${\mathbb{Z}}^3$ , but we connect each vertex to neighbors in the following way: For each vertex $\nu$ , its neighbors in ${\mathbb{Z}}^3$ are given as

That is, along each coordinate plane, each vertex has four neighbors, i.e., twelve in total, opposed to the full three-dimensional knight neighborhood which consists of 24 neighbors. See Figure 6d for an illustration of this neighborhood choice. We choose this reduced neighborhood as it carries less symmetries, hence it provides a more interesting study case, particularly in comparison to the other cases presented, see Figure 8 for a selection of results. Among these are those for the (hand-stopped) background 11 and background 10 most

(a) Background: 2. Figure 8: Running chip-firing on a knight-tour-inspired neighborhood on various uniform backgrounds.

(b) Background: 7.

(c) Background: 10.

(d) Background: 11.

interesting as these correspond to a slightly distorted icosahedron and dodecahedron, respectively. Again, this is encoded in the directions of the neighborhood relation.

Finally, note that in the two-dimensional case, there are grids on $n$ neighbors where a uniform background already falls into an infinite progress with backgrounds smaller than $n-1$. For instance, the regular triangle grid diverges at background 4 after two initial fires from the origin. Correspondingly, the three-dimensional lattices with neighborhood $n$ considered in this paper diverge starting from background 5 (cubical grid, $n=6$), 6 (cube-centered grid, $n=8$), 8 (knight grid, $n=12$), and 9 (face-centered grid, $n=12$). Predicting which neighborhoods lead to divergence starting from what background size is left as an open problem.

We hope that this glimpse into the world of three-dimensional chip-firing inspires the reader to perform their own experiments. While we constructed our visualizations in the software JavaView, Ahmed Bou-Rabee [3] also provides an implementation at https://github.com/nitromannitol/arbitrarydim_sandpiles. We encourage you to give it a (two-dimensional) try and create your own chip-firing images.

Acknowledgements

This research was partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – grant no. 455095046. We would like to thank Bruce Torrence again for allowing us to reproduce his artwork [12].

References

• [1] P. Bak, C. Tang, and K. Wiesenfeld. “Self-organized criticality: An explanation of the 1/f noise.” Physical Review Letters, vol. 59, no. 4, 1987, pp. 381–384.
• [2] A. Björner, L. Lovász, and P. W. Shor. “Chip-firing games on graphs.” European Journal of Combinatorics, vol. 12, no. 4, 1991, pp. 283–291.
• [3] A. Bou-Rabee. “Dynamic dimensional reduction in the Abelian sandpile.” arXiv preprint, arXiv:2009.05968, 2020.
• [4] J. Ellenberg. “The Amazing, Autotuning Sandpile.” Nautil.us, vol. 23, no. 1, 2015, https://nautil.us/issue/23/dominoes/the-amazing-autotuning-sandpile.
• [5] A. Engel. “The Probabilistic Abacus.” Educational Studies in Mathematics, vol. 6, no. 1, 1975, pp. 1–22.
• [6] G. R. Greenfield. “Chip Firing Transient,” digital print. 2019 Joint Mathematics Meetings Art Gallery Baltimore, USA, Jan. 16–19, 2019, http://gallery.bridgesmathart.org/exhibitions/2019-joint-mathematics-meetings/gary-greenfield.
• [7] G. R. Greenfield. “Generative Art from One-Dimensional Chip-Firing Automata.” Bridges Conference Proceedings, Linz, Austria, Jul. 6–20 2019, pp. 115–122.
• [8] C. J. Klivans. The mathematics of chip-firing. CRC Press, 2018.
• [9] J. A. Lind. “Sandpiles and Synthesizers: Listening to the Discrete Laplacian.” Bridges Conference Proceedings, Linz, Austria, Jul. 6–20 2019, pp. 453–456.
• [10] W. Pegden. “Sandpile galleries.” Available online at https://www.math.cmu.edu/~wes/sand.html, accessed Jan 10, 2022.
• [11] J. Spencer. “Balancing vectors in the max norm.” Combinatorica, vol. 6, no. 1, 1986, pp. 55–65.
• [12] B. Torrence. “Sandpile Fractile Disk” and “Sandpile Fractile Square”, archival digital prints. 2018 Bridges Conference Art Gallery Stockholm, Sweden, Jul. 25–29, 2018, http://gallery.bridgesmathart.org/exhibitions/2018-bridges-conference/bruce.