Модель песчаной кучи

Модель песчаной кучи (англ. sandpile model) — классическая модель теории самоорганизованной критичности, связанная со многими областями математики.

Стабильная песчаная куча, получившаяся из 30 миллионов песчинок, помещённых в центральную клетку. Белый, зелёный, фиолетовый и золотистый цвета соответствуют 0, 1, 2 и 3 песчинкам в узле сетки

Описание и свойства модели

В простейшем варианте модель формулируется следующим образом. Рассмотрим квадратную сетку. На этой сетке расположена песчаная куча: в каждом узле этой сетки помещается стопка из нескольких песчинок. Если на некотором узле в стопке 4 песчинки или больше, то куча нестабильна, и происходит обвал (англ. toppling): из этого узла в 4 соседних узла перемещается по 1 песчинке. Обвалы происходят до тех пор, пока куча не станет стабильной, то есть в каждом узле не окажется менее 4 песчинок; при этом получившаяся песочная куча не зависит от того, в каком порядке происходили обвалы[1].

Естественно ввести на множестве стабильных песчаных куч операцию «сложения»: чтобы получить сумму двух куч, нужно поместить в каждый узел сетки все песчинки из соответствующего узла в первой и во второй куче, а затем произвести необходимые обвалы, чтобы снова получилась стабильная куча. С такой операцией сложения множество песчаных куч становится коммутативным моноидом[2]. Нейтральный элемент — такая куча, которая при прибавлении к любой другой куче не меняет её, — это пустая сетка без единой песчинки.

Не обязательно рассматривать модель песчаной кучи именно на квадратной сетке. Можно вместо квадратной сетки взять другую (в этом случае обвал должен происходить не при 4 песчинках в узле, а при числе песчинок, равном числу соседей), например, треугольную, или вообще различные бесконечные неориентированные или ориентированные графы или мультиграфы. Кроме того, можно рассматривать и песчаные кучи на конечном графе, если некоторые узлы в нём являются стоками (англ. sink) — попадая в них, песчинки не накапливаются, а пропадают.

Нейтральный элемент группы песчаных куч на сетке 300×205. Чёрный, зелёный, фиолетовый и золотистый цвета соответствуют 0, 1, 2 и 3 песчинкам в узле сетки

Множество стабильных песчаных куч на конечном графе (например, конечной прямоугольной сетке, окружённой со всех сторон вершинами-стоками) также будет конечным. В конечном коммутативном моноиде можно выделить определённое подмножество (а именно, его минимальный идеал), которое будет группой относительно той же самой операции (в данном случае, сложение куч). Такая группа называется для данного графа группой песчаной кучи графа, входящие в неё кучи называются возвратными (англ. recurrent). Однако нейтральный элемент в этой группе, вообще говоря, отличается от нейтрального элемента моноида. Более того, группа песчаных куч примечательна в том числе тем, что нейтральный элемент в ней выглядит совершенно не тривиально и даже проявляет черты фрактала[3].

Сложение двух возвратных песчаных куч на сетке 3×3. В результате последовательности обвалов нестабильная куча в конце концов становится стабильной, и притом тоже возвратной. Показано две различные последовательности обвалов из множества возможных; все они, однако, приводят к одному и тому же результату, причём этот результат в данном случае совпадает с одним из слагаемых, поскольку другое слагаемое в данном случае — нейтральный элемент группы
Нейтральный элемент группы песчаных куч на большой квадратной сетке

Связи модели песчаной кучи с различными областями математики глубоки и многообразны[1]. Размер области, затронутой обвалами при добавлении к случайной песчаной куче ещё одной песчинки, подчиняется степенному распределению[4], что характерно для критических явлений. Можно считать нестабильную кучу, в которой происходят обвалы, клеточным автоматом. Обвал в песчаной куче можно описать с помощью матрицы Кирхгофа, что через матричную теорему о деревьях связывает порядок группы песчаных куч с количеством остовных деревьев на графе (существует и непосредственная биекция), а также с теоремой Римана — Роха для графов. Вычисление плотности песчинок в куче, которая получается из многих песчинок, насыпанных в один узел бесконечной квадратной сетки, связано с сеткой Аполлония. В песочных кучах на конечной квадратной сетке можно получить тропические кривые[5].

Примечания

  1. Levine and Peres, 2017, 1. The abelian sandpile model.
  2. Corry and Perkinson, 2018, 6.1.1. Additive structure.
  3. Járai, 2018, p. 252.
  4. Corry and Perkinson, 2018, 12.4. Self-organized criticality.
  5. Kalinin et al, 2018, Tropical Curves in Sandpiles.

Литература

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.