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

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

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

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

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

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

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

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

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

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

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

Это уже напоминает механизм возникновения вспышек болезней в настолке «Пандемия», хоть и отдалённо.
А если в нескольких клетках одновременно оказалось по 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$ . Теперь повторяем то же самое рассуждение до тех пор, пока от одной из последовательностей ничего не останется —, а значит, и от второй тоже, ибо пустая последовательность обвалов означает, что куча стабильна.

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

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

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

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

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

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

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

Возьмём кучи на конечном поле, чтобы и множество стабильных куч было конечным. Заметим, что песчаная куча, у которой в каждой клетке лежит максимальной количество песчинок (то есть 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 песчинками в клетке окрашены в чёрный, зелёный, фиолетовый и золотистый цвета.
На КДПВ — то же для поля 1000×500, и на иллюстрации сложения куч 3×3 тоже показан тамошний нейтральный элемент.
То есть понимаете. Группы бывают разные, но нейтральные элементы в них обычно выглядят совершенно нейтрально. В группе каких-нибудь чисел по сложению нейтральный элемент — число 0, в группе ненулевых действительных или комплексных чисел по умножению — число 1, в группе векторов по сложению — нулевой вектор, в группе перестановок — перестановка «всё на своих местах», в группе движений — «ничего не трогать». А тут — вот такая красота! Которую попробуй ещё рассчитай.

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

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

Moritz Lang, CC BY-SA 4.0
Доказательства этого факта конкретно для нейтрального элемента на квадратной сетке вроде бы нет. Зато для кучи, осыпавшейся из многих частиц в одной клетке, доказано существование (препринт, статья) и фрактальность (препринт, статья) фигуры, получающейся при стремлении количества песчинок к бесконечности с одновременной подгонкой масштаба.

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

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

Код для 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]}]]

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

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

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

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

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

Код

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

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

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

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

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

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

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