沙堆模型

此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。

The identity element of the sandpile group of a rectangular grid. Yellow pixels correspond to vertices carrying three particles, lilac to two particles, green to one, and black to zero.

The identity element of the sandpile group of a rectangular grid. Yellow pixels correspond to vertices carrying three particles, lilac to two particles, green to one, and black to zero.

矩形网格沙堆群的单位元。黄色像素对应的顶点携带三个粒子，淡紫色对应两个粒子，绿色对应一个，黑色对应零。

The Abelian sandpile model, also known as the Bak–Tang–Wiesenfeld model, was the first discovered example of a dynamical system displaying self-organized criticality. It was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper.

Choose a random vertex (x_i,y_i)\in\Gamma according to some probability distribution (usually uniform). 

选择一个随机顶点(x _ i，y _ i)在伽马根据一些概率分布(通常是均匀的)。

Add one grain of sand to this vertex while letting the grain numbers for all other vertices unchanged, i.e. set
z_i(x_i,y_i)=z_{i-1}(x_i,y_i)+1 and
z_i(x,y)=z_{i-1}(x,y) for all (x,y)\neq(x_i,y_i).

向这个顶点添加一粒沙子，同时让其他顶点的粒子数保持不变，即。设置 < br/> z _ i (x _ i，y _ i) = z _ { i-1}(x _ i，y _ i) + 1和 < br/> z _ i (x，y) = z _ { i-1}(x，y)为所有(x，y) neq (x _ i，y _ i) 。

The model is a cellular automaton. In its original formulation, each site on a finite grid has an associated value that corresponds to the slope of the pile. This slope builds up as "grains of sand" (or "chips") are randomly placed onto the pile, until the slope exceeds a specific threshold value at which time that site collapses transferring sand into the adjacent sites, increasing their slope. Bak, Tang, and Wiesenfeld considered process of successive random placement of sand grains on the grid; each such placement of sand at a particular site may have no effect, or it may cause a cascading reaction that will affect many sites.

If all vertices are stable, i.e. z_i(x,y)<4 for all (x,y)\in\Gamma, also the configuration z_i is said to be stable. In this case, continue with the next iteration.

如果所有的顶点都是稳定的，即。Z _ i (x，y) < 4对于 Gamma 中的所有(x，y) ，配置 z _ i 也被认为是稳定的。在这种情况下，继续下一个迭代。

If at least one vertex is unstable, i.e. z_i(x_u,y_u)\geq 4 for some (x_u,y_u)\in\Gamma, the whole configuration z_i is said to be unstable. In this case, choose any unstable vertex (x_u,y_u)\in\Gamma at random. Topple this vertex by reducing its grain number by four and by increasing the grain numbers of each of its (at maximum four) direct neighbors by one, i.e. set
z_i(x_u,y_u) \rightarrow z_i(x_u,y_u) - 4,, and
z_i( x_u \pm 1, y_u \pm 1) \rightarrow z_i( x_u \pm 1, y_u\pm 1) + 1 if ( x_u \pm 1, y_u\pm 1)\in\Gamma.
If a vertex at the boundary of the domain topples, this results in a net loss of grains (two grains at the corner of the grid, one grain otherwise).

如果至少有一个顶点是不稳定的，即。Z _ i (x _ u，y _ u) geq 4对于 γ 中的某些(x _ u，y _ u) ，整个构型 z _ i 被认为是不稳定的。在这种情况下，随机选择 Gamma 中的任意不稳定顶点(x_u，y _ u) 。通过减少四颗粒数和增加一颗粒数(最多四颗)来推翻这个顶点。设置 < br/> z _ i (x _ u，y _ u) right tarrow z _ i (x _ u，y _ u)-4，以及 < br/> z _ i (x _ u pm 1，y _ u pm 1) right tarrow z _ i (x _ u pm 1，y _ u pm 1) + 1 if (x _ u pm 1，y _ u pm 1) in Gamma。< br/> 如果一个顶点在畴的边界倾斜，这将导致晶粒的净损失(两个晶粒在网格的角落，否则一个晶粒)。

The model has since been studied on the infinite lattice, on other (non-square) lattices, and on arbitrary graphs (including directed multigraphs). It is closely related to the dollar game, a variant of the chip-firing game introduced by Biggs.

z(v) \to z(v) - \deg(v)

Z (v) to z (v)-deg (v)

z(u) \to z(u) + 1 for all u\sim v, u\neq s.

Z (u) to z (u) + 1 for all u sim v，u neq s.

Definition (rectangular grids)

The sandpile model is a cellular automaton originally defined on a [math]\displaystyle{ N\times M }[/math] rectangular grid (checkerboard) [math]\displaystyle{ \Gamma\subset\mathbb{Z}^2 }[/math] of the standard square lattice [math]\displaystyle{ \mathbb{Z}^2 }[/math].

The cellular automaton then progresses as before, i.e. by adding, in each iteration, one particle to a randomly chosen non-sink vertex and toppling until all vertices are stable.

然后，细胞自动机的进展如前，即。通过在每次迭代中向随机选择的非汇点添加一个粒子并进行倾斜，直到所有顶点都稳定。

To each vertex (side, field) [math]\displaystyle{ (x,y)\in\Gamma }[/math] of the grid, we associate a value (grains of sand, slope, particles) [math]\displaystyle{ z_0(x,y)\in\{0,1,2,3\} }[/math], with [math]\displaystyle{ z_0\in\{0,1,2,3\}^\Gamma }[/math] referred to as the (initial) configuration of the sandpile.

The definition of the sandpile model given above for finite rectangular grids \Gamma\subset\mathbb{Z}^2 of the standard square lattice \mathbb{Z}^2 can then be seen as a special case of this definition: consider the graph G=(V,E) which is obtained from \Gamma by adding an additional vertex, the sink, and by drawing additional edges from the sink to every boundary vertex of \Gamma such that the degree of every non-sink vertex of G is four. In this manner, also sandpile models on non-rectangular grids of the standard square lattice (or of any other lattice) can be defined: Intersect some bounded subset S of \mathbb{R}^2 with \mathbb{Z}^2. Contract every edge of \mathbb{Z}^2 whose two endpoints are not in S\cap\mathbb{Z}^2. The single remaining vertex outside of S\cap\mathbb{Z}^2 then constitutes the sink of the resulting sandpile graph.

有限矩形网格 Gamma 子集的上述沙堆模型的定义可以看作是这个定义的一个特例: 考虑图 g = (v，e) ，它是从 Gamma 中得到的，通过增加一个顶点，即汇，并通过从汇到每个边界的每个顶点绘制额外的边，使得 g 的每个非顶点的度为4。用这种方式，也可以定义标准正方格子(或任何其他格子)的非矩形网格上的沙堆模型: 将 mathbb { r } ^ 2的某个有界子集 s 与 mathbb { z } ^ 2相交。收缩 mathbb { z } ^ 2的每个边，其两个端点不在 s cap mathbb { z } ^ 2中。S cap mathbb { z } ^ 2之外的单个剩余顶点构成沙堆图的下沉。

The dynamics of the automaton at iteration [math]\displaystyle{ i\in\mathbb{N} }[/math] are then defined as follows:

1. Choose a random vertex [math]\displaystyle{ (x_i,y_i)\in\Gamma }[/math] according to some probability distribution (usually uniform).

In the dynamics of the sandpile automaton defined above, some stable configurations (0\leq z(v)<4 for all v\in G\setminus\{s\}) appear infinitely often, while others can only appear a finite number of times (if at all). The former are referred to as recurrent configurations, while the latter are referred to as transient configurations. The recurrent configurations thereby consist of all stable non-negative configurations which can be reached from any other stable configuration by repeatedly adding grains of sand to vertices and toppling. It is easy to see that the minimally stable configuration z_m, where every vertex carries z_m(v)=deg(v)-1 grains of sand, is reachable from any other stable configuration (add deg(v)-z(v)-1\geq 0 grains to every vertex). Thus, equivalently, the recurrent configurations are exactly those configurations which can be reached from the minimally stable configuration by only adding grains of sand and stabilizing.

在以上定义的沙堆自动机的动力学中，一些稳定的构型(0 leq z (v) < 4)经常出现，而另一些构型只能出现有限次数(如果有的话)。前者称为循环配置，而后者称为瞬态配置。因此，轮回结构由所有稳定的非负结构组成，这些结构可以通过反复向顶点添加砂粒和倾斜而从任何其他稳定结构中得到。显而易见，最小稳定结构 zm，其中每个顶点携带 z _ m (v) = deg (v)-1沙粒，可以从任何其他稳定结构(向每个顶点添加 deg (v)-z (v)-1 geq 0沙粒)到达。因此，等价的回归构型正是那些只需加入砂粒并进行稳定化即可从最小稳定构型得到的构型。

1. Add one grain of sand to this vertex while letting the grain numbers for all other vertices unchanged, i.e. set
   [math]\displaystyle{ z_i(x_i,y_i)=z_{i-1}(x_i,y_i)+1 }[/math] and
   [math]\displaystyle{ z_i(x,y)=z_{i-1}(x,y) }[/math] for all [math]\displaystyle{ (x,y)\neq(x_i,y_i) }[/math].

1. If all vertices are stable, i.e. [math]\displaystyle{ z_i(x,y)\lt 4 }[/math] for all [math]\displaystyle{ (x,y)\in\Gamma }[/math], also the configuration [math]\displaystyle{ z_i }[/math] is said to be stable. In this case, continue with the next iteration.

Not every non-negative stable configuration is recurrent. For example, in every sandpile model on a graph consisting of at least two connected non-sink vertices, every stable configuration where both vertices carry zero grains of sand is non-recurrent. To prove this, first note that the addition of grains of sand can only increase the total number of grains carried by the two vertices together. To reach a configuration where both vertices carry zero particles from a configuration where this is not the case thus necessarily involves steps where at least one of the two vertices is toppled. Consider the last one of these steps. In this step, one of the two vertices has to topple last. Since toppling transfers a grain of sand to every neighboring vertex, this implies that the total number of grains carried by both vertices together cannot be lower than one, which concludes the proof.

并非所有非负稳定构型都是循环的。例如，在一个至少由两个连通的非汇点组成的图上的每个沙堆模型中，每个稳定的结构，其中两个顶点携带零沙粒是非递归的。为了证明这一点，首先要注意的是沙粒的增加只能增加两个顶点共同承载的沙粒的总数。为了达到两个顶点都携带零粒子的配置，而实际情况并非如此，因此必然涉及到两个顶点中至少有一个被推翻的步骤。考虑这些步骤中的最后一个。在这个步骤中，两个顶点中的一个必须最后倒下。由于倾倒把一粒沙子转移到每个相邻的顶点，这意味着两个顶点共同承载的沙粒总数不能低于一粒，这就证明了。

1. If at least one vertex is unstable, i.e. [math]\displaystyle{ z_i(x_u,y_u)\geq 4 }[/math] for some [math]\displaystyle{ (x_u,y_u)\in\Gamma }[/math], the whole configuration [math]\displaystyle{ z_i }[/math] is said to be unstable. In this case, choose any unstable vertex [math]\displaystyle{ (x_u,y_u)\in\Gamma }[/math] at random. Topple this vertex by reducing its grain number by four and by increasing the grain numbers of each of its (at maximum four) direct neighbors by one, i.e. set
   [math]\displaystyle{ z_i(x_u,y_u) \rightarrow z_i(x_u,y_u) - 4, }[/math], and
   [math]\displaystyle{ z_i( x_u \pm 1, y_u \pm 1) \rightarrow z_i( x_u \pm 1, y_u\pm 1) + 1 }[/math] if [math]\displaystyle{ ( x_u \pm 1, y_u\pm 1)\in\Gamma }[/math].
   If a vertex at the boundary of the domain topples, this results in a net loss of grains (two grains at the corner of the grid, one grain otherwise).

1. Due to the redistribution of grains, the toppling of one vertex can render other vertices unstable. Thus, repeat the toppling procedure until all vertices of [math]\displaystyle{ z_i }[/math] eventually become stable and continue with the next iteration.

Given a configuration z, z(v)\in\mathbb{N}_0 for all v\in G\setminus\{s\}, toppling unstable non-sink vertices on a finite connected graph until no unstable non-sink vertex remains leads to a unique stable configuration z^\circ, which is called the stabilization of z. Given two stable configurations z and w, we can define the operation z*w \to (z+w)^\circ, corresponding to the vertex-wise addition of grains followed by the stabilization of the resulting sandpile.

给定一个构形 z，z (v)在 mathbb { n } _ 0中，对 g 集上的所有 v，在没有不稳定的非汇点存在的情况下，在有限连通图上倾斜不稳定的非汇点，得到一个唯一的稳定构形 z ^ circ，称为 z 的稳定化。给定两个稳定的构型 z 和 w，我们可以定义操作 z * w to (z + w) ^ circ，对应于颗粒的顶点相加和由此产生的沙堆的稳定。

The toppling of several vertices during one iteration is referred to as an avalanche. Every avalanche is guaranteed to eventually stop, i.e. after a finite number of topplings some stable configuration is reached such that the automaton is well defined. Moreover, although there will often be many possible choices for the order in which to topple vertices, the final stable configuration does not depend on the chosen order; this is one sense in which the sandpile is abelian. Similarly, the number of times each vertex topples during each iteration is also independent of the choice of toppling order.

Given an arbitrary but fixed ordering of the non-sink vertices, multiple toppling operations, which can e.g. occur during the stabilization of an unstable configuration, can be efficiently encoded by using the graph Laplacian \Delta=D-A, where D is the degree matrix and A is the adjacency matrix of the graph.

给定非汇聚顶点的一个任意但固定的顺序，多个顶点采样操作，它可以。在不稳定配置的稳定化过程中，可以通过使用图 Laplacian Delta = d-a 有效地进行编码，其中 d 是度矩阵，a 是图的邻接矩阵。

Definition (undirected finite multigraphs)

Deleting the row and column of \Delta corresponding with the sink yields the reduced graph Laplacian \Delta'. Then, when starting with a configuration z and toppling each vertex v a total of \mathbf{x}(v)\in\mathbb{N}_0 times yields the configuration z-\Delta'\boldsymbol{\cdot}~\mathbf{x}, where \boldsymbol{\cdot} is the contraction product. Furthermore, if \mathbf{x} corresponds to the number of times each vertex is toppled during the stabilization of a given configuration z, then

删除与汇对应的 Delta 行和列，得到简化图 Laplacian Delta’。然后，当以一个配置 z 开始并将每个顶点 v 在 mathbb { n } _ 0中的总和为 mathbf { x }(v)时，产生配置 z-Delta’粗体符号{ cdot } ~ mathbf { x } ，其中粗体符号{ cdot }是收缩积。此外，如果 mathbf { x }对应于在给定配置 z 的稳定过程中每个顶点被推翻的次数，则

To generalize the sandpile model from the rectangular grid of the standard square lattice to an arbitrary undirected finite multigraph [math]\displaystyle{ G=(V,E) }[/math] without loops, a special vertex [math]\displaystyle{ s\in V }[/math] called the sink is specified that is not allowed to topple. A configuration (state) of the model is then a function [math]\displaystyle{ z:V\setminus\{s\}\rightarrow\mathbb{N}_0 }[/math] counting the non-negative number of grains on each non-sink vertex. A non-sink vertex [math]\displaystyle{ v\in V\setminus\{s\} }[/math] with

z^\circ=z-\Delta'\boldsymbol{\cdot}~\mathbf{x}

Z ^ circ = z-Delta’粗体符号{ cdot } ~ mathbf { x }

[math]\displaystyle{ z(v)\geq \deg(v) }[/math]

In this case, \mathbf{x} is referred to as the toppling or odometer function (of the stabilization of z).

在这种情况下，mathbf { x }被称为倾斜或里程计函数(表示 z 的稳定性)。

is unstable; it can be toppled, which sends one of its grains to each of its (non-sink) neighbors:

Under the operation *, the set of recurrent configurations forms an abelian group isomorphic to the cokernel of the reduced graph Laplacian \Delta', i.e. to \mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta', whereby n denotes the number of vertices (including the sink). More generally, the set of stable configurations (transient and recurrent) forms a commutative monoid under the operation *. The minimal ideal of this monoid is then isomorphic to the group of recurrent configurations.

在运算 * 下，递归构形的集合构成一个同构于约化图 laplace Delta’上核的阿贝尔群，即同构于约化图 laplace Delta’的上核。对于 mathbf { z } ^ { n-1}/mathbf { z } ^ { n-1} Delta’ ，其中 n 表示顶点数(包括接收器)。更一般地说，稳定构型集(瞬态和回归)在运算下形成交换幺半群。这个幺半群的极小理想于是同构于一组回归构型。

[math]\displaystyle{ z(v) \to z(v) - \deg(v) }[/math]

[math]\displaystyle{ z(u) \to z(u) + 1 }[/math] for all [math]\displaystyle{ u\sim v }[/math], [math]\displaystyle{ u\neq s }[/math].

The group formed by the recurrent configurations, as well as the group \mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta' to which the former is isomorphic, is most commonly referred to as the sandpile group. Other common names for the same group are critical group, Jacobian group or (less often) Picard group. Note, however, that some authors only denote the group formed by the recurrent configurations as the sandpile group, while reserving the name Jacobian group or critical group for the (isomorphic) group defined by \mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta' (or for related isomorphic definitions). Finally, some authors use the name Picard group to refer to the direct product of the sandpile group and \mathbb{Z}, which naturally appears in a cellular automaton closely related to the sandpile model, referred to as the chip firing or dollar game.

由回归构形形成的群，以及与之同构的群 mathbf { z } ^ { n-1}/mathbf { z } ^ { n-1} Delta’ ，通常称为沙堆群。相同群的其他公共名称有临界群、雅可比群或(少见) Picard 群。注意，有些作者只把由回归构形形成的群称为沙堆群，而把雅可比群或临界群保留为 mathbf { z } ^ { n-1}/mathbf { z } ^ { n-1} Delta’(或相关的同构定义)所定义的(同构)群。最后，一些作者使用 Picard group 来指代 sandpile group 和 mathbb { z }的直接产物，后者自然出现在与 sandpile 模型密切相关的细胞自动机中，被称为芯片点火或美元游戏。

The cellular automaton then progresses as before, i.e. by adding, in each iteration, one particle to a randomly chosen non-sink vertex and toppling until all vertices are stable.

Given the isomorphisms stated above, the order of the sandpile group is the determinant of \Delta', which by the matrix tree theorem is the number of spanning trees of the graph.

给定上述同构，沙堆群的顺序是 Delta’的行列式，根据矩阵树定理，它是图的生成树数目。

The definition of the sandpile model given above for finite rectangular grids [math]\displaystyle{ \Gamma\subset\mathbb{Z}^2 }[/math] of the standard square lattice [math]\displaystyle{ \mathbb{Z}^2 }[/math] can then be seen as a special case of this definition: consider the graph [math]\displaystyle{ G=(V,E) }[/math] which is obtained from [math]\displaystyle{ \Gamma }[/math] by adding an additional vertex, the sink, and by drawing additional edges from the sink to every boundary vertex of [math]\displaystyle{ \Gamma }[/math] such that the degree of every non-sink vertex of [math]\displaystyle{ G }[/math] is four. In this manner, also sandpile models on non-rectangular grids of the standard square lattice (or of any other lattice) can be defined: Intersect some bounded subset [math]\displaystyle{ S }[/math] of [math]\displaystyle{ \mathbb{R}^2 }[/math] with [math]\displaystyle{ \mathbb{Z}^2 }[/math]. Contract every edge of [math]\displaystyle{ \mathbb{Z}^2 }[/math] whose two endpoints are not in [math]\displaystyle{ S\cap\mathbb{Z}^2 }[/math]. The single remaining vertex outside of [math]\displaystyle{ S\cap\mathbb{Z}^2 }[/math] then constitutes the sink of the resulting sandpile graph.

Transient and recurrent configurations

The original interest behind the model stemmed from the fact that in simulations on lattices, it is attracted to its critical state, at which point the correlation length of the system and the correlation time of the system go to infinity, without any fine tuning of a system parameter. This contrasts with earlier examples of critical phenomena, such as the phase transitions between solid and liquid, or liquid and gas, where the critical point can only be reached by precise tuning (e.g., of temperature). Hence, in the sandpile model we can say that the criticality is self-organized.

模型背后最初的兴趣起源于这样一个事实，即在格子模拟中，它被吸引到其临界状态，在这个临界状态下，系统的相关长度和系统的相关时间趋于无穷大，没有任何系统参数的微调。这与早期的临界现象的例子相反，例如固体和液体或液体和气体之间的相变，其中临界点只能通过精确的调节(例如，温度)才能达到。因此，在沙堆模型中，我们可以说临界是自组织的。

In the dynamics of the sandpile automaton defined above, some stable configurations ([math]\displaystyle{ 0\leq z(v)\lt 4 }[/math] for all [math]\displaystyle{ v\in G\setminus\{s\} }[/math]) appear infinitely often, while others can only appear a finite number of times (if at all). The former are referred to as recurrent configurations, while the latter are referred to as transient configurations. The recurrent configurations thereby consist of all stable non-negative configurations which can be reached from any other stable configuration by repeatedly adding grains of sand to vertices and toppling. It is easy to see that the minimally stable configuration [math]\displaystyle{ z_m }[/math], where every vertex carries [math]\displaystyle{ z_m(v)=deg(v)-1 }[/math] grains of sand, is reachable from any other stable configuration (add [math]\displaystyle{ deg(v)-z(v)-1\geq 0 }[/math] grains to every vertex). Thus, equivalently, the recurrent configurations are exactly those configurations which can be reached from the minimally stable configuration by only adding grains of sand and stabilizing.

Once the sandpile model reaches its critical state there is no correlation between the system's response to a perturbation and the details of a perturbation. Generally this means that dropping another grain of sand onto the pile may cause nothing to happen, or it may cause the entire pile to collapse in a massive slide. The model also displays 1/ƒ noise, a feature common to many complex systems in nature.

一旦沙堆模型达到临界状态，系统对扰动的响应和扰动的细节之间就没有相关性了。一般来说，这意味着将另一粒沙子丢到桩上可能不会导致任何事情发生，或者可能导致整个桩在一次大规模的滑动中坍塌。该模型还显示了噪声，这是自然界中许多复杂系统共有的特征。

Not every non-negative stable configuration is recurrent. For example, in every sandpile model on a graph consisting of at least two connected non-sink vertices, every stable configuration where both vertices carry zero grains of sand is non-recurrent. To prove this, first note that the addition of grains of sand can only increase the total number of grains carried by the two vertices together. To reach a configuration where both vertices carry zero particles from a configuration where this is not the case thus necessarily involves steps where at least one of the two vertices is toppled. Consider the last one of these steps. In this step, one of the two vertices has to topple last. Since toppling transfers a grain of sand to every neighboring vertex, this implies that the total number of grains carried by both vertices together cannot be lower than one, which concludes the proof.

This model only displays critical behaviour in two or more dimensions. The sandpile model can be expressed in 1D; however, instead of evolving to its critical state, the 1D sandpile model instead reaches a minimally stable state where every lattice site goes toward the critical slope.

此模型仅在两个或多个维度中显示关键行为。沙堆模型可以用一维来表示; 然而，一维沙堆模型不是演化到临界状态，而是达到最小稳定状态，其中每个格点都朝向临界坡度。

Sandpile group

Given a configuration [math]\displaystyle{ z }[/math], [math]\displaystyle{ z(v)\in\mathbb{N}_0 }[/math] for all [math]\displaystyle{ v\in G\setminus\{s\} }[/math], toppling unstable non-sink vertices on a finite connected graph until no unstable non-sink vertex remains leads to a unique stable configuration [math]\displaystyle{ z^\circ }[/math], which is called the stabilization of [math]\displaystyle{ z }[/math]. Given two stable configurations [math]\displaystyle{ z }[/math] and [math]\displaystyle{ w }[/math], we can define the operation [math]\displaystyle{ z*w \to (z+w)^\circ }[/math], corresponding to the vertex-wise addition of grains followed by the stabilization of the resulting sandpile.

For two dimensions, the associated conformal field theory is suggested to be symplectic fermions with central charge c = −2.

对于二维空间，相关的共形场论被认为是中心电荷 c =-2的辛型费米子。

Given an arbitrary but fixed ordering of the non-sink vertices, multiple toppling operations, which can e.g. occur during the stabilization of an unstable configuration, can be efficiently encoded by using the graph Laplacian [math]\displaystyle{ \Delta=D-A }[/math], where [math]\displaystyle{ D }[/math] is the degree matrix and [math]\displaystyle{ A }[/math] is the adjacency matrix of the graph.

Deleting the row and column of [math]\displaystyle{ \Delta }[/math] corresponding with the sink yields the reduced graph Laplacian [math]\displaystyle{ \Delta' }[/math]. Then, when starting with a configuration [math]\displaystyle{ z }[/math] and toppling each vertex [math]\displaystyle{ v }[/math] a total of [math]\displaystyle{ \mathbf{x}(v)\in\mathbb{N}_0 }[/math] times yields the configuration [math]\displaystyle{ z-\Delta'\boldsymbol{\cdot}~\mathbf{x} }[/math], where [math]\displaystyle{ \boldsymbol{\cdot} }[/math] is the contraction product. Furthermore, if [math]\displaystyle{ \mathbf{x} }[/math] corresponds to the number of times each vertex is toppled during the stabilization of a given configuration [math]\displaystyle{ z }[/math], then

[math]\displaystyle{ z^\circ=z-\Delta'\boldsymbol{\cdot}~\mathbf{x} }[/math]

The stabilization of chip configurations obeys a form of least action principle: each vertex topples no more than necessary in the course of the stabilization.

芯片结构的稳定遵循一种最小作用原理: 在稳定过程中，每个顶点的倾斜程度不超过必要的程度。

In this case, [math]\displaystyle{ \mathbf{x} }[/math] is referred to as the toppling or odometer function (of the stabilization of [math]\displaystyle{ z }[/math]).

This can be formalized as follows. Call a sequence of topples legal if it only topples unstable vertices, and stabilizing if it results in a stable configuration. The standard way of stabilizing the sandpile is to find a maximal legal sequence; i.e., by toppling so long as it is possible. Such a sequence is obviously stabilizing, and the Abelian property of the sandpile is that all such sequences are equivalent up to permutation of the toppling order; that is, for any vertex v, the number of times v topples is the same in all legal stabilizing sequences. According to the least action principle, a minimal stabilizing sequence is also equivalent up to permutation of the toppling order to a legal (and still stabilizing) sequence. In particular, the configuration resulting from a minimal stabilizing sequence is the same as results from a maximal legal sequence.

这可以正式化如下。调用一个合法的顶点序列，如果它只顶点不稳定的顶点，并稳定，如果它的结果是一个稳定的配置。稳定沙堆的标准方法是找到一个最大的法律顺序，也就是说，尽可能地推倒。这样的序列具有明显的稳定性，沙堆的阿贝尔性质是所有这样的序列都等价于倾斜序列的置换，也就是说，对于任何顶点 v，在所有合法的稳定序列中 v 的次数都是相同的。根据最小作用原理，最小稳定序列等价于倾覆序列的置换。特别地，由最小稳定序列产生的构型与由最大法律序列产生的构型是相同的。

Under the operation [math]\displaystyle{ * }[/math], the set of recurrent configurations forms an abelian group isomorphic to the cokernel of the reduced graph Laplacian [math]\displaystyle{ \Delta' }[/math], i.e. to [math]\displaystyle{ \mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta' }[/math], whereby [math]\displaystyle{ n }[/math] denotes the number of vertices (including the sink). More generally, the set of stable configurations (transient and recurrent) forms a commutative monoid under the operation [math]\displaystyle{ * }[/math]. The minimal ideal of this monoid is then isomorphic to the group of recurrent configurations.

More formally, if \mathbf{u} is a vector such that \mathbf{u}(v) is the number of times the vertex v topples during the stabilization (via the toppling of unstable vertices) of a chip configuration z, and \mathbf{n} is an integral vector (not necessarily non-negative) such that z-\mathbf{n}\Delta' is stable, then \mathbf{u}(v) \leq \mathbf{n}(v) for all vertices v.

更形式化地说，如果 mathbf { u }是一个向量，使得 mathbf { u }(v)是在一个芯片组态 z 的稳定(通过不稳定顶点的顶点取样)期间顶点 v 颠倒的次数，而 mathbf { n }是一个积分向量(不一定非负) ，使得 z-mathbf { n } Delta’是稳定的，那么对于所有顶点来说，bf { u }(v) leq mathbf { n }(v)是稳定的。

The group formed by the recurrent configurations, as well as the group [math]\displaystyle{ \mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta' }[/math] to which the former is isomorphic, is most commonly referred to as the sandpile group. Other common names for the same group are critical group, Jacobian group or (less often) Picard group. Note, however, that some authors only denote the group formed by the recurrent configurations as the sandpile group, while reserving the name Jacobian group or critical group for the (isomorphic) group defined by [math]\displaystyle{ \mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta' }[/math] (or for related isomorphic definitions). Finally, some authors use the name Picard group to refer to the direct product of the sandpile group and [math]\displaystyle{ \mathbb{Z} }[/math], which naturally appears in a cellular automaton closely related to the sandpile model, referred to as the chip firing or dollar game.

Animation of the sandpile identity on square grids of increasing size. Black color denotes vertices with 0 grains, green is for 1, purple is for 2, and gold is for 3.

增大尺寸方形网格上沙堆识别的动画。黑色表示顶点与0颗粒，绿色是为1，紫色是为2，金是为3。

Given the isomorphisms stated above, the order of the sandpile group is the determinant of [math]\displaystyle{ \Delta' }[/math], which by the matrix tree theorem is the number of spanning trees of the graph.

The animation shows the recurrent configuration corresponding to the identity of the sandpile group on different N\times N square grids of increasing sizes N\geq 1, whereby the configurations are rescaled to always have the same physical dimension. Visually, the identities on larger grids seem to become more and more detailed and to "converge to a continuous image". Mathematically, this suggests the existence of scaling-limits of the sandpile identity on square grids based on the notion of weak-* convergence (or some other, generalized notion of convergence). Indeed, existence of scaling limits of recurrent sandpile configurations has been proved by Wesley Pegden and Charles Smart

动画显示了在不同 n 乘以 n 个增大尺寸 n geq1的正方形网格上，与沙堆群同一性相对应的轮回结构，其中的结构被重新调整为始终具有相同的物理尺寸。在视觉上，更大的网格上的身份似乎变得越来越详细，并且“汇聚成一个连续的图像”。在数学上，这表明了基于弱 * 收敛概念(或其他一些广义收敛概念)的方形网格上沙堆恒等式的缩放极限的存在性。实际上，韦斯利 · 佩格登和查尔斯 · 斯玛特已经证明了循环沙堆结构尺度限制的存在性

Self-organized criticality

. In further joint work with Lionel Levine, they use the scaling limit to explain the fractal structure of the sandpile on square grids.

.在与莱昂内尔 · 莱文的进一步合作中，他们使用尺度极限来解释方形网格上沙堆的分形结构。

Main article: Self-organized criticality

The original interest behind the model stemmed from the fact that in simulations on lattices, it is attracted to its critical state, at which point the correlation length of the system and the correlation time of the system go to infinity, without any fine tuning of a system parameter. This contrasts with earlier examples of critical phenomena, such as the phase transitions between solid and liquid, or liquid and gas, where the critical point can only be reached by precise tuning (e.g., of temperature). Hence, in the sandpile model we can say that the criticality is self-organized.

Once the sandpile model reaches its critical state there is no correlation between the system's response to a perturbation and the details of a perturbation. Generally this means that dropping another grain of sand onto the pile may cause nothing to happen, or it may cause the entire pile to collapse in a massive slide. The model also displays 1/ƒ noise, a feature common to many complex systems in nature.

30 million grains dropped to a site of the infinite square grid, then toppled according to the rules of the sandpile model. White color denotes sites with 0 grains, green is for 1, purple is for 2, gold is for 3. The bounding box is 3967×3967.

3000万颗颗粒落在无限方格网的一个位置，然后根据沙堆模型的规则被推倒。白色表示0颗粒的网站，绿色表示1，紫色表示2，金色表示3。包围盒为3967 × 3967。

There exist several generalizations of the sandpile model to infinite grids. A challenge in such generalizations is that, in general, it is not guaranteed anymore that every avalanche will eventually stop. Several of the generalization thus only consider the stabilization of configurations for which this can be guaranteed.

沙堆模型对无限网格有几种推广。这种概括中的一个挑战是，总的来说，不能保证每次雪崩最终都会停止。因此，一些推广只考虑能够保证这一点的构型的稳定性。

This model only displays critical behaviour in two or more dimensions. The sandpile model can be expressed in 1D; however, instead of evolving to its critical state, the 1D sandpile model instead reaches a minimally stable state where every lattice site goes toward the critical slope.

A rather popular model on the (infinite) square lattice with sites (x,y)\in\mathbb{Z}^2 is defined as follows:

在 mathbb { z } ^ 2中，在(infinite)方格上定义了一个相当流行的位置(x，y)的模型如下:

For two dimensions, the associated conformal field theory is suggested to be symplectic fermions with central charge c = −2.

Begin with some nonnegative configuration of values z(x,y)\in \mathbf{Z} which is finite, meaning

从 mathbf { z }中值 z (x，y)的一些非负配置开始，这意味着

Properties

\sum_{x,y}z(x,y)<\infty.

(x，y) < infty.

Least action principle

The stabilization of chip configurations obeys a form of least action principle: each vertex topples no more than necessary in the course of the stabilization.

This can be formalized as follows. Call a sequence of topples legal if it only topples unstable vertices, and stabilizing if it results in a stable configuration. The standard way of stabilizing the sandpile is to find a maximal legal sequence; i.e., by toppling so long as it is possible. Such a sequence is obviously stabilizing, and the Abelian property of the sandpile is that all such sequences are equivalent up to permutation of the toppling order; that is, for any vertex [math]\displaystyle{ v }[/math], the number of times [math]\displaystyle{ v }[/math] topples is the same in all legal stabilizing sequences. According to the least action principle, a minimal stabilizing sequence is also equivalent up to permutation of the toppling order to a legal (and still stabilizing) sequence. In particular, the configuration resulting from a minimal stabilizing sequence is the same as results from a maximal legal sequence.

The Bak–Tang–Wiesenfeld sandpile was mentioned on the Numb3rs episode "Rampage," as mathematician Charlie Eppes explains to his colleagues a solution to a criminal investigation.

数学家查理 · 埃普斯向他的同事们解释了一个犯罪调查的解决方案，贝克-唐-维森菲尔德沙堆在 Numb3rs 节目“暴怒”中被提到。

More formally, if [math]\displaystyle{ \mathbf{u} }[/math] is a vector such that [math]\displaystyle{ \mathbf{u}(v) }[/math] is the number of times the vertex [math]\displaystyle{ v }[/math] topples during the stabilization (via the toppling of unstable vertices) of a chip configuration [math]\displaystyle{ z }[/math], and [math]\displaystyle{ \mathbf{n} }[/math] is an integral vector (not necessarily non-negative) such that [math]\displaystyle{ z-\mathbf{n}\Delta' }[/math] is stable, then [math]\displaystyle{ \mathbf{u}(v) \leq \mathbf{n}(v) }[/math] for all vertices [math]\displaystyle{ v }[/math].

The computer game Hexplode is based around the Abelian sandpile model on a finite hexagonal grid where instead of random grain placement, grains are placed by players.

计算机游戏 Hexplode 是基于有限六边形网格上的阿贝尔沙堆模型，在这个模型中，颗粒由玩家放置，而不是随机的颗粒放置。

Scaling limits

Animation of the sandpile identity on square grids of increasing size. Black color denotes vertices with 0 grains, green is for 1, purple is for 2, and gold is for 3.

The animation shows the recurrent configuration corresponding to the identity of the sandpile group on different [math]\displaystyle{ N\times N }[/math] square grids of increasing sizes [math]\displaystyle{ N\geq 1 }[/math], whereby the configurations are rescaled to always have the same physical dimension. Visually, the identities on larger grids seem to become more and more detailed and to "converge to a continuous image". Mathematically, this suggests the existence of scaling-limits of the sandpile identity on square grids based on the notion of weak-* convergence (or some other, generalized notion of convergence). Indeed, existence of scaling limits of recurrent sandpile configurations has been proved by Wesley Pegden and Charles Smart

. In further joint work with Lionel Levine, they use the scaling limit to explain the fractal structure of the sandpile on square grids.

Generalizations and related models

     | author = Per Bak

作者: Per Bak

Sandpile models on infinite grids

| year = 1996

1996年

文件:Sandpile on infinite grid, 3e7 grains.png

30 million grains dropped to a site of the infinite square grid, then toppled according to the rules of the sandpile model. White color denotes sites with 0 grains, green is for 1, purple is for 2, gold is for 3. The bounding box is 3967×3967.

| title = How Nature Works: The Science of Self-Organized Criticality

自然是如何运作的: 自组织临界性的科学

There exist several generalizations of the sandpile model to infinite grids. A challenge in such generalizations is that, in general, it is not guaranteed anymore that every avalanche will eventually stop. Several of the generalization thus only consider the stabilization of configurations for which this can be guaranteed.

| publisher = Copernicus

| publisher = Copernicus

| location = New York

| 地点: 纽约

A rather popular model on the (infinite) square lattice with sites [math]\displaystyle{ (x,y)\in\mathbb{Z}^2 }[/math] is defined as follows:

| isbn = 978-0-387-94791-4

| isbn = 978-0-387-94791-4

}}

}}

Begin with some nonnegative configuration of values [math]\displaystyle{ z(x,y)\in \mathbf{Z} }[/math] which is finite, meaning

[math]\displaystyle{ \sum_{x,y}z(x,y)\lt \infty. }[/math]

     |author1=Per Bak |author2=Chao Tang |author3=Kurt Wiesenfeld | year = 1987

1 = Per Bak | author2 = Chao Tang | author3 = Kurt Wiesenfeld | year = 1987

| title = Self-organized criticality: an explanation of 1/ƒ noise

| title = 自组织临界性: 对噪音的解释

Any site [math]\displaystyle{ (x,y) }[/math] with

| journal = Physical Review Letters

| journal = Physical Review Letters

[math]\displaystyle{ z(x,y)\geq 4 }[/math]

| volume = 59

59

is unstable and can topple (or fire), sending one of its chips to each of its four neighbors:

| issue = 4

第四期

[math]\displaystyle{ z(x,y) \rightarrow z(x,y) - 4, }[/math]

| pages = 381–384

381-- 384

[math]\displaystyle{ z( x \pm 1, y) \rightarrow z( x \pm 1, y) + 1, }[/math]

| doi = 10.1103/PhysRevLett.59.381

| doi = 10.1103/physrvlett. 59.381

[math]\displaystyle{ z(x, y \pm 1) \rightarrow z( x, y \pm 1 ) + 1. }[/math]

| bibcode=1987PhRvL..59..381B | pmid=10035754}}

1987/phrvl. . 59. . 381 b | pmid = 10035754}

Since the initial configuration is finite, the process is guaranteed to terminate, with the grains scattering outward.

     |author1=Per Bak |author2=Chao Tang |author3=Kurt Wiesenfeld | year = 1988

1 = Per Bak | author2 = Chao Tang | author3 = Kurt Wiesenfeld | year = 1988

| title = Self-organized criticality

自组织临界性

A popular special case of this model is given when the initial configuration is zero for all vertices except the origin. If the origin carries a huge number of grains of sand, the configuration after relaxation forms fractal patterns (see figure). When letting the initial number of grains at the origin go to infinity, the rescaled stabilized configurations were shown to converge to a unique limit.

| journal = Physical Review A

| journal = Physical Review a

| volume = 38

38

Sandpile models on directed graphs

| issue = 1

1

The sandpile model can be generalized to arbitrary directed multigraphs. The rules are that any vertex [math]\displaystyle{ v }[/math] with

| pages = 364–374

364-- 374

[math]\displaystyle{ z(v)\geq \deg^{+}(v) }[/math]

| doi = 10.1103/PhysRevA.38.364

| doi = 10.1103/PhysRevA. 38.364

is unstable; toppling again sends chips to each of its neighbors, one along each outgoing edge:

|pmid=9900174 | bibcode=1988PhRvA..38..364B

9900174 | bibcode = 1988PhRvA. . 38. . 364 b

[math]\displaystyle{ z(v) \rightarrow z(v) - \deg^{+}(v) + \deg(v,v) }[/math]

}}

}}

and, for each [math]\displaystyle{ u\neq v }[/math]:

[math]\displaystyle{ z(u) \rightarrow z(u) + \deg(v,u) }[/math]

where [math]\displaystyle{ \deg(v,u) }[/math] is the number of edges from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ u }[/math].

| location=Providence, RI | publisher=American Mathematical Society | isbn=978-1-4704-1021-6 | year=2013 | citeseerx=10.1.1.760.283 }}

| location = Providence，RI | publisher = American Mathematical Society | isbn = 978-1-4704-1021-6 | year = 2013 | citeserx = 10.1.1.760.283}

In this case the Laplacian matrix is not symmetric. If we specify a sink [math]\displaystyle{ s }[/math] such that there is a path from every other vertex to [math]\displaystyle{ s }[/math], then the stabilization operation on finite graphs is well-defined and the sandpile group can be written

[math]\displaystyle{ \mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta' }[/math]

as before.

The order of the sandpile group is again the determinant of [math]\displaystyle{ \Delta' }[/math], which by the general version of the matrix tree theorem is the number of oriented spanning trees rooted at the sink.

Category:Self-organization

类别: 自我组织

Category:Phase transitions

类别: 阶段转变

The extended sandpile model

Category:Dynamical systems

类别: 动力系统

Sandpile dynamics induced by the harmonic function H=x*y on a 255x255 square grid.

Category:Critical phenomena

范畴: 关键现象

To better understand the structure of the sandpile group for different finite convex grids [math]\displaystyle{ \Gamma\subset\mathbb{Z}^2 }[/math] of the standard square lattice [math]\displaystyle{ \mathbb{Z}^2 }[/math], Lang and Shkolnikov introduced the extended sandpile model in 2019. The extended sandpile model is defined nearly exactly the same as the usual sandpile model (i.e. the original Bak–Tang–Wiesenfeld model ), except that vertices at the boundary [math]\displaystyle{ \partial\Gamma }[/math] of the grid are now allowed to carry a non-negative real number of grains. In contrast, vertices in the interior of the grid are still only allowed to carry integer numbers of grains. The toppling rules remain unchanged, i.e. both interior and boundary vertices are assumed to become unstable and topple if the grain number reaches or exceeds four.

Category:Nonlinear systems

类别: 非线性系统

Category:Cellular automaton rules

分类: 细胞自动机规则

This page was moved from wikipedia:en:Abelian sandpile model. Its edit history can be viewed at 沙堆模型/edithistory