📬 👩🏻‍🚒 🖕🏼 Fractals in the sand, or More than three do not gather 🍠 💘 👨🏼

We will talk about the sand heap model. Sand (not real, model), pouring over, creates these pictures:

Sand heaps can be added (this is easy if you are used to folding all kinds of things) and subtracted (but this is already not trivial).

You can also use this thing as a Hello world instead of the Life game.

Sand heaps

Take a square checkered field. Grains of sand may lie in each cell of this field. For example, it may look like this:

Now add one grain of sand to that cell where there are three of them:

And now attention is the most important rule:

If four grains of sand are in the cell, they are distributed over four neighboring cells.

As they say, there is a collapse (toppling). Like this:

A very natural rule. Although it doesn’t look like sand at all, it’s more likely to follow the rule “do not get together for more than three”: if four people in one cage managed to get together, they scatter in different directions.

In this way, a cascade of landslides can occur - when a sand heap is heaped, it will collapse until there are unstable cells with 4 or more grains of sand, that is, until a stable sand pile is obtained :

This already resembles the mechanism of outbreaks of disease in the pandemic ", Albeit remotely.

And if in several cells at the same time there were 4 grains of sand or more, then what? In what order to make landslides? Answer: it doesn’t matter.

Evidence

, - , ( , ):

x_{1}, \dots, x_{n}

$x_1,\ldots,x_n$

y_{1}, \dots, y_{k}

$y_1,\ldots,y_k$ (

x_{1}

$x_1$ . . , ).

x_{1}

$x_1$ , , . . -

y_{j} = x_{1}

$y_j=x_1$ . , — , , , — .

y_{j}

$y_j$ , , :

y_{j}, y_{1}, \dots, y_{j - 1}, y_{j + 1}, \dots, y_{k}

$y_j,y_1,\ldots,y_{j-1},y_{j+1},\ldots,y_k$ .

y_{j} = x_{1}

$y_j=x_1$ , , ,

x_{1}

$x_1$ ,

x_{2}, \dots, x_{n}

$x_2,\ldots,x_n$

y_{1}, \dots, y_{j - 1}, y_{j + 1}, \dots, y_{k}

$y_1,\ldots,y_{j-1},y_{j+1},\ldots,y_k$ . , — , , , .

If you throw many, many grains of sand into one cell of an endless field and let them crumble, you get such a mandala:

Here, "many, many" is 30 million, and cells with 0, 1 , 2 , 3 grains of sand are marked with pixels of white, green, purple and golden color. There is a video on YouTube , you can see how it looks in dynamics.

Add and Subtract

Due to the fact that the sequence of landslides is unimportant, it is possible to determine the operation of adding stable sand piles: we put one on top of another, stacking grains of sand from the corresponding cells, and let it crumble. On an infinite field, then you need to take care of introducing coordinated coordinates on both heap terms. It can be treated and sand heaps at the final checkered field - when the grains of sand crumble over the edge, they are lost forever (they say that the edge of the field located kletki sinks (sink), or one large kletischa, does not matter). Below is an example of the addition of two sand piles in a 3 × 3 field. As you can see, two different collapse sequences lead to the same result.

It is also possible on the torus, but in it you still have to make at least one drain cell so that the sand can flow away, otherwise the sequence of landslides can be infinite.

It turns out that the set of stable sand piles on a given field (finite or infinite) has the structure of a commutative monoid : they can be stacked together (moreover, this addition is commutative and associative), and the empty field without a single grain of sand plays the role of zero. You can’t subtract heaps so simply: you can get a negative amount of grains of sand. However, we will also construct an analog of subtraction, but not for all heaps, but only for the elite.

A bit of algebra. Idealin a commutative monoid is called a subset of it that is invariant with respect to the addition of any elements of this monoid, including not from the ideal. That is, if you belong to an ideal, then you will not come out of it, no matter what you add to yourself. For example, the set of natural numbers is also a commutative monoid, only with respect to multiplication, and the ideal in it is, for example, the set of even numbers: for which an even number does not multiply, you always get an even number. The minimum ideal is the intersection of all (nonempty) ideals; itself is also an ideal. In the example with natural numbers, the intersection of all nonempty ideals is an empty set. However, in the case of finite commutative monoids this is not so. There is a theorem on the minimal ideal in a finite commutative monoid, according to which it isby a group (with respect to the same operation that is specified on the monoid): there is a neutral element (analog of zero), and each element has an inverse, that is, subtraction is specified along with addition. In the general case, this is proved to be boring, but we are only interested in sand heaps.

Take heaps on the final field so that the set of stable heaps is finite. Note that the sand heap with the maximum number of grains of sand in each cell (that is, 3; let's call it simply “heap 3”) belongs to any ideal in the monoid of stable sand heaps, since you can add another specially selected stable heap to any stable heap a bunch to get a bunch of 3 (landslides do not need to be done). Hence, the minimal ideal is generatedheap 3: to get it, you need to take heap 3 and add to it in turn all kinds of stable sand heaps. This will result in a certain subset of the set of all stable heaps; it does not contain, for example, an empty field. Sand pile of this subset are called recurrent (recurrent).

So, general algebra tells us that many return sand piles are a group. Therefore, it has reverse and neutral elements. A neutral element (identity element) is a return heap that does not change it when added to any other return heap. By the way, the addition of a neutral element is just shown in the illustration of addition of heaps.

To get a neutral element, you need to throw in each cell twice as much as the maximum number of grains of sand (i.e. 6), let it crumble, then subtract the number of grains of sand in each cell from 6, let the result crumble.

Why?

() 6 6, , , °, ( ) . : I = (6−6°)° , R (R+I)° = R. R , R = (3+S)° - S.

(R+I)° = ((3+S)°+(6−6°)°)° = (3+S+6−6°)° — - , . , , . : (3+S+6−6°)° = ((3−6°)+6+S)° = ((3−6°)+6°+S)° = (3+S)° = R, !

, 6 A (R+(A−A°)°)° = R. 6 , A−A° 3 , . . . — , , .

How to subtract?

I = (6−6°)° — , , R R⁻¹ — , R I: (R⁻¹+R)° = I. (2×(6−6°)−R)°, 2× .

This is how the neutral element of the group of (return) sand piles looks in the field of 1024 × 1024; cells with 0, 1 , 2 , 3 grains of sand in the cell are colored in black, green, purple and golden.

On KDPV - the same for the field 1000 × 500, and the illustration of the addition of heaps 3 × 3 also shows the local neutral element.

That is, you understand. Groups are different, but the neutral elements in them usually look completely neutral. In the group of some addition numbers, the neutral element is the number 0, in the group of nonzero real or complex numbers in the multiplication the number is 1, in the group of addition vectors the zero vector, in the permutation group the permutation is “everything in its place”, in the group movements - "do not touch anything." And here - such a beauty! Which try still calculate.

Patterns

Both in the neutral element and in the heap that crumbled from many grains of sand in one cell, claims to self-similarity are visible. In addition, although the details change when the field is resized, the picture as a whole - as if a fractal map of areas filled with simple periodic patterns sewn from Sierpinski’s napkins - remains unchanged and only details when the field is enlarged.

Moritz Lang, CC BY-SA 4.0

There seems to be no evidence of this fact specifically for a neutral element on a square grid. But for a heap that crumbled from many particles in one cell, existence ( preprint , article ) and fractality ( preprint , article ) are proved) of the figure resulting from the tendency of the number of grains of sand to infinity with simultaneous adjustment of the scale.

In addition, the existence and fractality of a sand pile in a finite square field (more precisely, its limit for the number of cells in a field tending to ∞), which is a neutral element with added 1 grain of sand in each cell (with subsequent shedding, as usual), has been proved.

The authors of the proof ( preprint , article ) kindly provided an algorithm describing the corresponding figure, which, with a simplified implementation, gives such a picture - compare with the image above:

Code for Wolfram Mathematica

4- . , a_sk R , , -. 8 — L-, . , Clear[a].

qc = {{3, 0, 0}, {1 - I, 1 + I, 1}, {1 + I, 1, 1 - I}} / 3;
r = {{0, 1, 0}, {0, 0, 1}, {1, 0, 0}};
a[{}] = {0, -1, I};
a[{s___, k_}] := a[{s, k}] = qc.MatrixPower[r, k].a[{s}];
Graphics[Polygon /@ Table[ReIm @ a[s], {s, Tuples[Range[3], 8]}]]

In curved triangles forming fractal-like pictures, not only more or less homogeneous periodic patterns are visible (especially on the KDPV), but also one-dimensional branching “defects”. These seem to be tropical curves . In any case, it is known ( preprint , article ) that if several separate grains of sand are thrown on the final field with 3 grains of sand in each cell, a picture of the graph is formed as a result of shedding, which is a tropical curve passing through the grained grains of sand.

Variations and generalizations

Sophisticated cell-automation experts have already thought about it: one can also consider the cells to be neighbors and those that have only a common angle with it (“the vicinity of Moore”). The collapse in this case should occur when 8 grains of sand in the cage are reached. Well, 5 million grains of sand in the central cell turn into such a figure (colors: 0 - white, 1 , 2 , 3 , 4 , 5 , 6 , 7 ):

Of course, you can consider not only square cells, but also other regular structures . The corresponding pictures are in the gallery on the page of one of the authors of the above articles.

Moreover, sand can be scattered in general on any graph, including oriented ones: grains of sand are collected at the vertices, and a collapse occurs when the number of grains of sand in the vertex reaches the outgoing degree of the vertex (the number of edges emanating from it). But if you want to consider a group of sand piles on this graph, then it must be finite, it must have a sink top, and it should be possible to reach it from any vertex. However, if you read this paragraph at all, you probably already figured it out.

The code

The game "Life" has always been one of my favorite tasks when learning a new programming language. But she was already starting to bother, so when I read about the sand heaps, I decided that this was a nice task, suitable to practice in one nice language, and still little known (as I thought) - maybe I’ll be the first who it is Raste will program! Yeah, schaz. There are sand heaps even on Google Play - one , two . So on Rust, a couple of implementations on Github were found; but they are not very good. My implementation is at github.com/colt-browning/sandpile. You can use it directly on the command line (although, I'm afraid the system with the Polish argument writing turned out to be complicated), you can use it as a library. Shedding is generally performed in a fairly straightforward manner, but optimized procedures are provided for important special cases.

Question answer

Why is all this necessary?

Common answer. It’s time to mention the Buck – Than – Wiesenfeld model. Sometimes it is mixed with a sand heap model, but it will be more accurate to say that this is an add-on over a sand framework: we take a sand heap in a square field and throw one grain of sand at it into random cells, watching each time how the shedding occurs and how many cells the avalanche will affect landslides ( video) With whatever configuration we start, sooner or later we will come to return heaps. Numerical experiments show that the size distribution of avalanches is a power law. In natural systems, the response to fluctuations usually decays exponentially on average, and a power-law distribution occurs in states called critical — for example, near a phase transition. However, in order to get into the phase transition, it is usually necessary to “fine-tune” the system parameters (temperature and pressure, for example, or there are probabilities of an edge in the graph if we are talking about the percolation problem on the lattice or the Erdos – Renyi model- there are also phase transitions there). And in the BTV model, a power law appears itself, without fine tuning. This is called self-organized criticality. BTV did not just come up with a model of sand heap, but it was from their work that sand was firmly established in science under the flag of self-organized criticality: supposedly, if we understand how self-organized criticality arises in sand, it will help to understand where it can come from in principle nature (and in nature power laws of a not quite clear origin also occur). It seems that the power law for the BTV model on a square grid has not yet been strictly established, but there are many close theoretical results ( here are more recent results ) and, of course, numerical and even full-scale experiments.

Honest answer. Yes, you just look at the pictures, what a beauty!

You wrote off all this from Wikipedia, and downloaded pictures from there

I didn’t write off and download from, but wrote and uploaded to.

Where else to read about sand?

Laplacian growth, sandpiles, and scaling limits - 2017 review.
Sand model - notes from the course of the Summer School "Contemporary Mathematics" from the co-author of the result about tropical curves.

Fractals in the sand, or More than three do not gather