Sandpiles!

“If you keep your head in the sand, you don’t know where the kick’s coming from.”

-Herbie Mann, jazz flautist

There’s nothing like a social scientist to take a wind out of your math-researching sails. Yesterday, I was sitting in a coffee shop doing some work when a man sitting nearby took off his headphones to make a comment on my t-shirt—my favorite t-shirt—which proudly displays a colorful fractal image and the words “Fractal Geometry” on its front.

“Is this the kind of thing you’re into?” he asked, pointing at my shirt and then to the few math textbooks I’d been reading. “You do math in your spare time?” Excited by the opportunity to talk math on a weekend, I immediately volunteered that yes, I did do math for fun, and that I was starting to do some research.

“Math research?” he said, looking puzzled, “Can you even do that?”

“Sure. Why not?”

“Oh, I dunno. I do research on the housing market, which is changing all the time. Math just seems pretty absolute.”

“That’s fair; unfortunately, math is taught that way quite a bit, but you can definitely still do research. Mathematicians ask questions and try to answer them—just like any other research. Check this out.” I showed him some of the pretty sandpile pictures I’d been looking at on my laptop.

“Oh cool, what are you studying?” he asked, as I scrolled through a few pages.

“Sandpiles. I’m studying…sandpiles.” He nodded his head and smirked a little before turning back to his coffee.

“Wow. Looks crazy. I’ll let you get back to that.”

As soon as I’d said the word “sandpiles,” I realized how silly it must have sounded. I thought about trying to get the guy’s attention again to further explain myself, but the moment was lost. His headphones were back on, and he was already busy typing on his laptop. If only I had chosen to research something that sounded less childish. Maybe then I’d have had a chance at keeping his attention.

Luckily, within the blogosphere, I have a captive audience to with which I can share my sandpiling discoveries. In the remainder of this post, I’ll introduce what I’ve learned thus far about sandpiles in the form of a general overview. At this point, my knowledge is limited to the work of authors that have come before me. My hope is that, in the coming weeks, I’ll have something that is my own.

What is a sandpile?

A sandpile is exactly what it sounds like—it’s a pile of sand. Examined at any given moment, such a pile is fairly uninteresting, consisting of individual grains distributed in smaller piles across a surface; however, observed over a period of time, the behavior of a sandpile closely resembles other dynamical systems that arise within a variety of natural phenomena, including electrical networks, gravitational fields, earthquakes, quasars and the distribution of matter in the Universe (Dhar, Bak et. al).

What these systems have in common is a tendency towards what is called self-organized criticality, or SOC. The term, coined by (Bak et. al) in their 1988 article titled “Self-Organized Criticality,” describes two basic characteristics present within dynamical processes mentioned above; first, criticality refers to the unpredictable evolution of a dynamical system to a predictable and stable, critical state which is invariant under the specifics of that evolution; second, self-organization describes how, even in the presence of high degrees of spatial and temporal freedom, the critical state can be determined by a small set of parameters.

In the same article, (Bak et. al) introduced sandpiles to model SOC through a series of numerical simulations, where avalanches, called “topplings,” were created by randomly adding individual grains of sand to a pile over time. Their sandpile model was basic in its structure and design, and paved the way for all subsequent sandpile research. Beginning with a finite N x N lattice of points to act as the resting surface of a sandpile, they assigned each column of points in the lattice a critical sand height z­­­_c based on an ideal sandpile slope (z_c > z_c+1 ).

Following an original distribution of sand on the lattice, grains were randomly added to the pile. Toppling occurred any time a lattice point reached its critical height, at which point two grains of sand would be sent to neighboring lattice points, one to the “right” and one “up,” often resulting in lengthy chain reactions. Simulations would end when piles had reached a critical state such that the height of each lattice point (x , y), denoted z(x , y), was less than its critical height, and that the introduction of a grain of sand, regardless of it’s location, would result in the same state. As the authors noted in their paper, critical states were only guaranteed in the presence of a sink, which was identified with all lattice points (N , y) and (x , N). Below, I’ve included an example of a critical sandpile from their original simulation:

As the research of (Bak et. al) relied heavily upon empirical data collected from simulations, their results were mostly qualitative. This is not to say that their work wasn’t valuable to mathematicians. Most notably, (Bak et. al) hypothesized that critical states were invariant under the order of avalanches, an idea which would go on to inspire years of mathematical research.

Following the advent of the (Bak et. al) sandpile, other mathematicians began constructing their own sandpile models, which soon led sandpile research into familiar mathematical territory. In 1989, Dhar constructed a sandpile model, again using a lattice structure, but with an adjusted toppling condition and critical height structure which deviated from the gradient structure of (Bak et. al). Under his toppling condition, toppling lattice points sent grains to neighbors in all four directions, and all four edges of the lattice were identified with a sink. As it turned out, Dhar’s sandpile model was highly algebraic in structure and, using foundations of Markov processes, he was able to divide the set of stable sandpiles into two classes: recurrent and transient. Recurrent sandpiles, as he first described them, were stable piles which would recur under repeated application of sand to any single location. That is, for any recurrent pile C, there existed an integer m_i such that a_i^m C=C for all i (where the operation a_i C indicates that a grain is added to pile C at lattice point i) Further, he was able to prove that the set of all stable sandpiles, when restricted to recurrent piles, formed an abelian group with nontrivial identity under the operation aC.

Following Dhar, research on sandpiles has only grown in its sophistication and subtlety. In the following weeks, I hope to fully unpack the work of Dhar and move into more modern sandpile research, which studies piles on a wide variety of connected graphs, and comes under an equally large variety of names (chip-firing, burning, the dollar game, and more).

My goals for future posts:

-Prove that Dhar’s classification of stable piles into recurrent and transient sets is legitimate

-Prove Dhar’s lemma that the operation aC is abelian

-Verify an algorithm for the construction of an identity element I under the operation aC.

-Show that the set of stable sandpiles of a lattice forms a commutative monoid.

-Impose a structure of ideals onto the set of stable sandpiles of a lattice and show that the minimal ideal of that monoid forms a group of recurrent sandpiles.

-Find out what a Tutte polynomial is.

-Find a way to make pretty pictures like this one, the identity element of a recurrent sandpile group of a 523 x 523 lattice, taken from (Levine, Propp).