Фракталы в песках, или Больше трёх не собираться +64
Математика, Rust
Рекомендация: подборка платных и бесплатных курсов Smm - https://katalog-kursov.ru/
Мы поговорим о модели песчаной кучи. Песок (не настоящий, модельный), пересыпаясь, создаёт вот такие картинки:
Песчаные кучи можно складывать (это легко, если вы привыкли складывать всякие штуки) и вычитать (а вот это уже нетривиально).
А ещё можно использовать эту штуку в качестве Hello world вместо игры «Жизнь».
Песчаные кучи
Возьмём квадратное клетчатое поле. В каждой клетке этого поля могут лежать песчинки. Например, это может выглядеть так:
Теперь добавим одну песчинку в ту клетку, где их три:
А теперь внимание — самое главное правило:
Если в клетке оказываются четыре песчинки, они распределяются по четырём соседним клеткам.
Как говорят, происходит
обвал (toppling). Вот так:
Очень естественное правило. Хотя на песок вообще-то не очень похоже, скорее уж на правило «больше трёх не собираться»: если граждан угораздило собраться вчетвером в одной клетке, они разбегаются в разные стороны.
Таким образом может возникнуть каскад обвалов — при осыпании песчаной кучи обвалы происходят до тех пор, пока не останется
нестабильных клеток с 4 или больше песчинками, т. е. пока не получится
стабильная песчаная куча:
Это уже напоминает механизм возникновения вспышек болезней в настолке «Пандемия», хоть и отдалённо.
А если в нескольких клетках одновременно оказалось по 4 песчинки или больше, тогда что? В каком порядке производить обвалы? Ответ: это неважно.
ДоказательствоВ самом деле, возьмём какую-нибудь нестабильную песчаную кучу и две возможные последовательности обвалов в нестабильных клетках, приводящие к стабильным кучам (и мы хотим доказать, что получаются одинаковые кучи):
и
(
и т. д. здесь обозначает клетку, в которой происходит обвал). Рано или поздно во второй последовательности обвалов тоже должна встретиться клетка
, ведь иначе она так и не останется нестабильной, т. е. есть какая-нибудь клетка
. Заметим, что если в двух нестабильных клетках могут случиться обвалы подряд — сначала в одной, потом в другой, причём вторая была нестабильной ещё до первого обвала, — то они могут случиться и в обратном порядке с тем же результатом. Поэтому можно протащить обвал
в самое начало последовательности, не меняя итоговый результат, получая:
. Поскольку
, мы теперь можем считать, что начинаем не с исходной кучи, а после обвала
, и сравнивать последовательности обвалов
и
. Теперь повторяем то же самое рассуждение до тех пор, пока от одной из последовательностей ничего не останется — а значит, и от второй тоже, ибо пустая последовательность обвалов означает, что куча стабильна.
Если кинуть много-много песчинок в одну клетку бесконечного поля и дать им осыпаться, получится вот такая мандала:
Здесь «много-много» — это 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. Можно пользоваться прямо в командной строке (хотя, боюсь, система с польской записью аргументов получилась сложноватой), можно как библиотекой. Осыпание в общем случае выполняется довольно прямолинейным образом, однако для важных частных случаев предусмотрены оптимизированные процедуры.
Вопрос — ответ
Зачем всё это нужно?
Общепринятый ответ. Здесь пора упомянуть модель Бака—Тана—Визенфельда. Иногда её смешивают с моделью песчаной кучи, однако точнее будет сказать, что это надстройка над песчаным фреймворком: мы берём песчаную кучу на квадратном поле и кидаем в неё по одной песчинке в случайные клетки, наблюдая каждый раз, как происходит осыпание и сколько клеток затронет лавина обвалов (
видео). С какой бы конфигурации мы не начали, рано или поздно придём к возвратным кучам. Численные эксперименты показывают, что распределение размеров лавин — степенное. В природных системах отклик на флуктуацию обычно затухает в среднем экспоненциально, а степенное распределение возникает в состояниях, называемых критическими — например, вблизи фазового перехода. Однако чтобы попасть в фазовый переход, обычно нужно провести «тонкую настройку» параметров системы (температуры и давления, например, или там вероятности наличия ребра в графе, если мы говорим про задачу о перколяции на решётке или
модель Эрдёша—Реньи — там тоже есть фазовые переходы). А в модели БТВ степенной закон появляется сам, без тонкой настройки. Это называют самоорганизованной критичностью. БТВ не то чтобы придумали модель песчаной кучи, но именно с их работы песок прочно прописался в науке под флагом самоорганизованной критичности: мол, если мы поймём, как именно возникает самоорганизованная критичность в песке, то это поможет понять, откуда она в принципе может браться в природе (а в природе степенные законы не вполне ясного происхождения тоже встречаются). Кажется, степенной закон для модели БТВ на квадратной сетке пока не установлен строго, но есть
много близких теоретических результатов (
вот ещё из недавнего) и, конечно, численных и даже натурных экспериментов.
Честный ответ. Да вы только посмотрите на картинки, какая красота!
Ты всё это с Википедии списал, и картинки оттуда скачал
Не списал и скачал с, а написал и закачал в.
Где ещё почитать про песок?