Size of a sandpile.

Question

Introduction

There is a structure called sandpile. Let us introduce it in the following way. Suppose we have a set of whole points $\mathbb{Z}^2$. Next, we have a function $g:\mathbb{Z}^2 \rightarrow\mathbb{N}$, which shows how many grains are in the point $(x,y).$ Also, there is a number of a maximum possible grains in a point which leaves point stable. We will denote this number through $T$ (threshold). Now execute the following algorithm:

1. if $g(x,y) > T$ then subtract 4 grains from $(x,y)$ and add one grain to each neighbor of $(x,y)$ i.e. $(x\pm 1, y)$ and $(x, y\pm 1)$.
2. if there is no points with $g(x,y) > T$ then terminate. Else, start with step 1.

Simple example with $T=4$ and starting amount of grains $S$ (seed) at $(2,2)$ equals to 11 showed below. $$\begin{pmatrix} 0 & 0 & 0\\ 0 & 11 & 0\\ 0 & 0 & 0 \end{pmatrix} \rightarrow \begin{pmatrix} 0 & 2 & 0\\ 2 & 3 & 2\\ 0 & 2 & 0 \end{pmatrix}$$ More information about this here

Question

Suppose we have sandpile with $T=t$ and $S=n_0$ at (0,0). Let us denote such sandpiles through $\Delta(n_0;t)$. My question is

Given a sandpile $\Delta(n_0;t)$ find the size of this sandpile, where $$\text{size} := |\Delta(n_0;t)| =\max_{g(x,y)>0}|x|=\max_{g(x,y)>0}|y|$$

Tries

Some reasons lead me to the answer $$|\Delta(n_0;t)| \leq 3\log_{4}\frac{n_0}{t} + 1,$$ but empirical results say that for sufficiently large $n_0$ it is not true.

Pictures

Here are some pictures I made with Sage. The darker color the more grains in pixel. The first three pictures with threshold equals to 4, two last - 3.

EDIT: 1D sandpiles

Starting from the suggestion to look at 1-dim sandpile it is possible to say that there is nothing special (i.e. interesting) about that. It is almost obvious how they (1-dim SP's) look like (take a guess). More over, one can calculate the size of 1-dim SP: $$\Delta_{1}(n_0; t) \sim \frac{n_0}{2t}$$

Answer 1

So this doesn't answer the question fully but gives some ideas that are too long for comments.

Note that it seems (and I haven't proved this) that the area covered will always be pretty much a diamond centered at the origin i.e. $$\begin{pmatrix}0&0&x&0&0\\0&x&x&x&0\\x&x&x&x&x\\0&x&x&x&0\\0&0&x&0&0\end{pmatrix}$$ This covers $2n^2+2n+1$ places where $n=|\Delta(n_0;t)|$. A very rough upper bound then would come from assuming all the places contain 1 grain. This gives $(2n^2+2n+1)=n_0$ and solving for $n$ you would get very very roughly $O(\sqrt{n_0})$ asymptotically. Now a much more reasonable estimate though not a bound would be guessing pretty much all of them are full i.e. you solve $t(2n^2+2n+1)=n_0$ which gets you something on the order of $O(\sqrt{n_0/t})$ While this doesn't seem like it will be a perfect bound it seems more reasonable then a $\log$.

I will try to explain. Assuming the process behaves fairly reasonably, and I don't see why it shouldn't, assuming $n_0$ is much bigger then $t$ it seems the middle of the diamond should be mostly $t$'s. There might be dips though and that seems tricky to quantify, since the behavior doesn't seem to be very smooth. Looking at your original $t=4$ you can get the middle to be anything from $1-4$ depending on the remainder.

Thinking about this further though the choice of $4$ for $t$ might also be special given that $4$ is the number of neighbors.

Answer 2

This estimate for $T = 3$ works pretty good.

I asssumed the shape is a circle. Its area is $A = \pi r^2$.

Now, the number of grains in the entire pile doesn't change, so I assumed the average number of grains per cell is $\left \lceil T / 2 \right \rceil = 2$.

Solving for $r$ gives

$$r = \sqrt{ \frac{n_0}{2 \pi} }$$

This is just a rough estimate, but it seems to work quite well.

Here is a table of values I calculated with my formula and the exact values (for $T = 3$).

This seems to indicate that the average number of grains isn't quite two, but it is still quite good. This may be improved by multiplying with $0.9341$.