- PVSM.RU - https://www.pvsm.ru -

Фракталы в песках, или Больше трёх не собираться

Мы поговорим о модели песчаной кучи. Песок (не настоящий, модельный), пересыпаясь, создаёт вот такие картинки:

Фракталы в песках, или Больше трёх не собираться - 1

Песчаные кучи можно складывать (это легко, если вы привыкли складывать всякие штуки) и вычитать (а вот это уже нетривиально).

А ещё можно использовать эту штуку в качестве Hello world вместо игры «Жизнь».

Песчаные кучи

Возьмём квадратное клетчатое поле. В каждой клетке этого поля могут лежать песчинки. Например, это может выглядеть так:

Фракталы в песках, или Больше трёх не собираться - 2

Теперь добавим одну песчинку в ту клетку, где их три:

Фракталы в песках, или Больше трёх не собираться - 3

А теперь внимание — самое главное правило:

Если в клетке оказываются четыре песчинки, они распределяются по четырём соседним клеткам.

Как говорят, происходит обвал (toppling). Вот так:

Фракталы в песках, или Больше трёх не собираться - 4

Очень естественное правило. Хотя на песок вообще-то не очень похоже, скорее уж на правило «больше трёх не собираться»: если граждан угораздило собраться вчетвером в одной клетке, они разбегаются в разные стороны.

Таким образом может возникнуть каскад обвалов — при осыпании песчаной кучи обвалы происходят до тех пор, пока не останется нестабильных клеток с 4 или больше песчинками, т. е. пока не получится стабильная песчаная куча:

Фракталы в песках, или Больше трёх не собираться - 5

Это уже напоминает механизм возникновения вспышек болезней в настолке «Пандемия», хоть и отдалённо.

А если в нескольких клетках одновременно оказалось по 4 песчинки или больше, тогда что? В каком порядке производить обвалы? Ответ: это неважно.

Доказательство

В самом деле, возьмём какую-нибудь нестабильную песчаную кучу и две возможные последовательности обвалов в нестабильных клетках, приводящие к стабильным кучам (и мы хотим доказать, что получаются одинаковые кучи): $x_1,ldots,x_n$ и $y_1,ldots,y_k$ ($x_1$ и т. д. здесь обозначает клетку, в которой происходит обвал). Рано или поздно во второй последовательности обвалов тоже должна встретиться клетка $x_1$, ведь иначе она так и не останется нестабильной, т. е. есть какая-нибудь клетка $y_j=x_1$. Заметим, что если в двух нестабильных клетках могут случиться обвалы подряд — сначала в одной, потом в другой, причём вторая была нестабильной ещё до первого обвала, — то они могут случиться и в обратном порядке с тем же результатом. Поэтому можно протащить обвал $y_j$ в самое начало последовательности, не меняя итоговый результат, получая: $y_j,y_1,ldots,y_{j-1},y_{j+1},ldots,y_k$. Поскольку $y_j=x_1$, мы теперь можем считать, что начинаем не с исходной кучи, а после обвала $x_1$, и сравнивать последовательности обвалов $x_2,ldots,x_n$ и $y_1,ldots,y_{j-1},y_{j+1},ldots,y_k$. Теперь повторяем то же самое рассуждение до тех пор, пока от одной из последовательностей ничего не останется — а значит, и от второй тоже, ибо пустая последовательность обвалов означает, что куча стабильна.

Если кинуть много-много песчинок в одну клетку бесконечного поля и дать им осыпаться, получится вот такая мандала:

Фракталы в песках, или Больше трёх не собираться - 17

Здесь «много-много» — это 30 миллионов, и клетки с 0, 1, 2, 3 песчинками обозначены пикселями белого, зелёного, фиолетового и золотистого цвета. На YouTube есть видео [1], можно посмотреть, как это выглядит в динамике.

Складываем и вычитаем

Благодаря тому, что последовательность обвалов неважна, можно определить операцию сложения стабильных песчаных куч: накладываем одну на другую, складывая песчинки из соответствующих клеток, и даём осыпаться. На бесконечном поле тогда нужно позаботиться о введении согласованных координат на обоих кучах-слагаемых. Можно рассматривать и песчаные кучи на конечном клетчатом поле — когда песчинки осыпаются за его край, они пропадают навсегда (ещё говорят, что за краем такого поля расположены клетки-стоки (sink), или одна большая клетища, неважно). Ниже показан пример сложения двух песчаных куч на поле 3×3. Как видно, две разные последовательности обвалов приводят к одному и тому же результату.

Фракталы в песках, или Больше трёх не собираться - 18

На торе тоже можно, но в нём всё равно придётся сделать хоть одну клетку-сток, чтобы было куда утекать песку, иначе последовательность обвалов может быть бесконечной.

Получается, что множество стабильных песчаных куч на заданном поле (конечном или бесконечном) обладает структурой коммутативного моноида: их можно складывать между собой (причём это сложение коммутативно и ассоциативно), а роль ноля выполняет пустое поле без единой песчинки. Вычитать кучи так просто нельзя: может получиться отрицательное количество песчинок. Впрочем, аналог вычитания мы сейчас тоже сконструируем, но не для всех куч, а только для избранных.

Немного алгебры. Идеалом в коммутативном моноиде называется такое его подмножество, которое инвариантно относительно прибавления любых элементов этого моноида, в том числе не из идеала. То есть если вы принадлежите идеалу, то уже из него не вылезете, что бы вы к себе не прибавляли. Например, множество натуральных чисел — тоже коммутативный моноид, только относительно умножения, и идеалом в нём является, например, множество чётных чисел: на что чётное число не умножай, всегда получится чётное. Минимальный идеал — пересечение всех (непустых) идеалов, сам тоже является идеалом. В примере с натуральными числами пересечение всех непустых идеалов — пустое множество. Однако в случае конечных коммутативных моноидов это не так. Есть теорема про минимальный идеал в конечном коммутативном моноиде, согласно которой он является группой (относительно той же операции, которая задана на моноиде): есть нейтральный элемент (аналог ноля), и у каждого элемента есть обратный, то есть вместе со сложением задано вычитание. В общем случае это доказывается занудно, но нас интересуют только песчаные кучи.

Возьмём кучи на конечном поле, чтобы и множество стабильных куч было конечным. Заметим, что песчаная куча, у которой в каждой клетке лежит максимальной количество песчинок (то есть 3; назовём её просто «куча 3»), принадлежит любому идеалу в моноиде стабильных песчаных куч, поскольку к любой стабильной куче можно прибавить другую, специально подобранную стабильную кучу, чтобы получилась куча 3 (обвалы делать не потребуется). Значит, минимальный идеал порождён кучей 3: чтобы его получить, нужно взять кучу 3 и поприбавлять к ней по очереди всевозможные стабильные песчаные кучи. Получится определённое подмножество множества всех стабильных куч; оно не содержит, например, пустого поля. Песчаные кучи из этого подмножества называются возвратными (recurrent).

Итак, общая алгебра говорит нам, что множество возвратных песчаных куч — группа. Стало быть, в ней есть обратные и нейтральный элементы. Нейтральный элемент (neutral element, identity element) — это такая возвратная куча, которая при прибавлении её к любой другой возвратной куче не меняет её. Кстати, на иллюстрации сложения куч выше как раз показано прибавление нейтрального элемента.

Чтобы получить нейтральный элемент, нужно кинуть в каждую клетку вдвое больше максимального количества песчинок (то есть 6), дать осыпаться, потом вычесть количество песчинок в каждой клетке из 6, дать осыпаться результату.

Почему?

Обозначим (нестабильную) кучу с 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 песчинок в клетке, т. е. чтобы результат был гарантированно возвратной кучей. Больше — можно, но тогда стабилизация будет рассчитываться ещё дольше, а результат будет тот же самый.

А вычитать-то как?

Если нейтральный элемент I = (6−6°)° — аналог ноля, прибавление которого к любой возвратной куче не меняет её, то аналогом вычитания кучи R в группе возвратных песчаных куч будет прибавление обратного элемента R−1 — такой возвратной кучи, которая при прибавлении к R даёт I: (R−1+R)° = I. Таким требованиям удовлетворяет куча (2×(6−6°)−R)°, где 2× означает удвоение количества песчинок во всех клетках без последующего осыпания.

Вот так выглядит нейтральный элемент группы (возвратных) песчаных куч на поле 1024×1024; клетки с 0, 1, 2, 3 песчинками в клетке окрашены в чёрный, зелёный, фиолетовый и золотистый цвета.

Фракталы в песках, или Больше трёх не собираться - 19

На КДПВ — то же для поля 1000×500, и на иллюстрации сложения куч 3×3 тоже показан тамошний нейтральный элемент.

То есть понимаете. Группы бывают разные, но нейтральные элементы в них обычно выглядят совершенно нейтрально. В группе каких-нибудь чисел по сложению нейтральный элемент — число 0, в группе ненулевых действительных или комплексных чисел по умножению — число 1, в группе векторов по сложению — нулевой вектор, в группе перестановок — перестановка «всё на своих местах», в группе движений — «ничего не трогать». А тут — вот такая красота! Которую попробуй ещё рассчитай.

Закономерности

Как в нейтральном элементе, так и в куче, осыпавшейся из многих песчинок в одной клетке, видны претензии на самоподобие. Кроме того, хотя детали меняются при изменении размеров поля, картинка в целом — как будто сшитая из салфеток Серпинского фрактальная карта областей, заполненных простыми периодическими паттернами, — остаётся неизменной и лишь детализируется при увеличении размеров поля.

Фракталы в песках, или Больше трёх не собираться - 20

Moritz Lang, [2] CC BY-SA 4.0 [3]

Доказательства этого факта конкретно для нейтрального элемента на квадратной сетке вроде бы нет. Зато для кучи, осыпавшейся из многих частиц в одной клетке, доказано существование (препринт [4], статья [5]) и фрактальность (препринт [6], статья [7]) фигуры, получающейся при стремлении количества песчинок к бесконечности с одновременной подгонкой масштаба.

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

Фракталы в песках, или Больше трёх не собираться - 21

Авторы доказательства (препринт [8], статья [9]) любезно предоставили алгоритм, описывающий соответствующую фигуру, который при упрощённой реализации даёт такую картинку — сравните с изображением выше:

Фракталы в песках, или Больше трёх не собираться - 22

Код для Wolfram Mathematica

Основывается на 4-м разделе статьи. Обратите внимание, что в определении ask и 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]}]]

В изогнутых треугольниках, формирующих фракталоподобные картинки, видны (особенно на КДПВ) не только более-менее однородные периодические паттерны, но и одномерные ветвящиеся «дефекты». Похоже, это тропические кривые [10]. Во всяком случае, известно (препринт [11], статья [12]), что если на конечное поле с 3 песчинками в каждой клетке кинуть ещё несколько отдельных песчинок, в результате осыпания образуется картина графа, который представляет собой именно тропическую кривую, проходящую через докинутые песчинки.

Фракталы в песках, или Больше трёх не собираться - 23

Вариации и обобщения

Искушённые клеточноавтоматоведы уже задумались: можно же считать соседями клетки и те, что имеют с ней лишь общий угол («окрестность Мура»). Обвал в таком случае должен происходить при достижении 8 песчинок в клетке. Что ж, 5 миллионов песчинок в центральной клетке превращаются в такую фигуру (цвета: 0 — белый, 1, 2, 3, 4, 5, 6, 7):

Фракталы в песках, или Больше трёх не собираться - 24

Разумеется, можно рассматривать и не только квадратные клетки, но и иные регулярные структуры. Соответствующие картинки есть в галерее [13] на страничке одного из авторов упомянутых выше статей.

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

Код

Игра «Жизнь» всегда была одной из моих любимых задач при изучении нового языка программирования. Но она уже начала приедаться, поэтому когда я прочитал о песчаных кучах, то решил, что это симпатичная задача, подходящая, чтобы попрактиковаться в одном симпатичном языке, да ещё малоизвестная (как я думал) — может, я вообще первый буду, кто это на Расте запрограммирует! Ага, щаз. Песчаные кучи даже в Google Play есть — раз [14], два [15]. Так что и на Rust пара реализаций на Гитхабе нашлись; но они не оч. Моя реализация — на github.com/colt-browning/sandpile [16]. Можно пользоваться прямо в командной строке (хотя, боюсь, система с польской записью аргументов получилась сложноватой), можно как библиотекой. Осыпание в общем случае выполняется довольно прямолинейным образом, однако для важных частных случаев предусмотрены оптимизированные процедуры.

Вопрос — ответ

Зачем всё это нужно?

Общепринятый ответ. Здесь пора упомянуть модель Бака—Тана—Визенфельда. Иногда её смешивают с моделью песчаной кучи, однако точнее будет сказать, что это надстройка над песчаным фреймворком: мы берём песчаную кучу на квадратном поле и кидаем в неё по одной песчинке в случайные клетки, наблюдая каждый раз, как происходит осыпание и сколько клеток затронет лавина обвалов (видео [17]). С какой бы конфигурации мы не начали, рано или поздно придём к возвратным кучам. Численные эксперименты показывают, что распределение размеров лавин — степенное. В природных системах отклик на флуктуацию обычно затухает в среднем экспоненциально, а степенное распределение возникает в состояниях, называемых критическими — например, вблизи фазового перехода. Однако чтобы попасть в фазовый переход, обычно нужно провести «тонкую настройку» параметров системы (температуры и давления, например, или там вероятности наличия ребра в графе, если мы говорим про задачу о перколяции на решётке или модель Эрдёша—Реньи [18] — там тоже есть фазовые переходы). А в модели БТВ степенной закон появляется сам, без тонкой настройки. Это называют самоорганизованной критичностью. БТВ не то чтобы придумали модель песчаной кучи, но именно с их работы песок прочно прописался в науке под флагом самоорганизованной критичности: мол, если мы поймём, как именно возникает самоорганизованная критичность в песке, то это поможет понять, откуда она в принципе может браться в природе (а в природе степенные законы не вполне ясного происхождения тоже встречаются). Кажется, степенной закон для модели БТВ на квадратной сетке пока не установлен строго, но есть много [19] близких теоретических результатов (вот ещё [20] из недавнего) и, конечно, численных и даже натурных экспериментов.

Честный ответ. Да вы только посмотрите на картинки, какая красота!

Ты всё это с Википедии списал, и картинки оттуда скачал

Не списал и скачал с, а написал и закачал в.

Где ещё почитать про песок?

Автор: Browning

Источник [23]

Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/matematika/351439

Ссылки в тексте:

[1] видео: https://www.youtube.com/watch?v=Ip542yQVtO0

[2] Moritz Lang,: https://commons.wikimedia.org/wiki/File:Scaling_sandpile_identity.gif

[3] CC BY-SA 4.0: https://creativecommons.org/licenses/by-sa/4.0/deed.ru

[4] препринт: https://arxiv.org/abs/1105.0111

[5] статья: https://doi.org/10.1215/00127094-2079677

[6] препринт: https://arxiv.org/abs/1208.4839

[7] статья: https://doi.org/10.1007/s00039-016-0358-7

[8] препринт: https://arxiv.org/abs/1708.09432

[9] статья: https://doi.org/10.1007/s00023-020-00898-1

[10] тропические кривые: https://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%BE%D0%BF%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B3%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%8F

[11] препринт: https://arxiv.org/abs/1509.02303

[12] статья: https://doi.org/10.1016/j.crma.2015.11.003

[13] галерее: http://www.math.cmu.edu/~wes/sandgallery.html

[14] раз: https://play.google.com/store/apps/details?id=com.Sharp.Sandpiles

[15] два: https://play.google.com/store/apps/details?id=com.crashingbooth.abeliansandpile

[16] github.com/colt-browning/sandpile: https://github.com/colt-browning/sandpile

[17] видео: https://www.youtube.com/watch?v=zHoiZtyA82E

[18] модель Эрдёша—Реньи: https://ru.wikipedia.org/wiki/%D0%9C%D0%BE%D0%B4%D0%B5%D0%BB%D1%8C_%D0%AD%D1%80%D0%B4%D1%91%D1%88%D0%B0_%E2%80%94_%D0%A0%D0%B5%D0%BD%D1%8C%D0%B8

[19] много: http://indico.ictp.it/event/8644/material/3/0.pdf

[20] вот ещё: https://doi.org/10.1214/17-EJP111

[21] Laplacian growth, sandpiles, and scaling limits: https://doi.org/10.1090/bull/1573

[22] Песочная модель: http://mathcenter.spb.ru/nikaan/misc/draft-rus.pdf

[23] Источник: https://habr.com/ru/post/494580/?utm_source=habrahabr&utm_medium=rss&utm_campaign=494580