Что такое абелева песочная куча

Насыпьте песок в одно место — и вы ожидаете получить конус. Насыпьте песчинки на одну клетку сетки по правилу, что клетка с четырьмя песчинками отдаёт по одной каждому соседу, — и получится нечто куда более странное: узор безупречного порядка и бесконечной детализации. Модель песочной кучи появилась в физике как игрушечная модель лавин и землетрясений, а выросла в точку встречи теории вероятностей, комбинаторики и геометрии.

Круглая песочная куча из 262 144 песчинок на квадратной сетке в тёмно-коричневых, янтарных и кремовых тонах, с треугольниками и полосами с симметрией четвёртого порядка, повторяющимися на всех масштабах
Круглая песочная куча из 262 144 песчинок на квадратной сетке в тёмно-коричневых, янтарных и кремовых тонах, с треугольниками и полосами с симметрией четвёртого порядка, повторяющимися на всех масштабах

Правило

Возьмите сетку из клеток, в каждой из которых лежит несколько песчинок. Клетка устойчива, пока песчинок в ней меньше, чем соседей: на квадратной сетке с четырьмя соседями в ней может быть 0, 1, 2 или 3. Клетка с 4 и более песчинками обрушивается: она теряет 4 песчинки, а каждый из четырёх её соседей получает по одной. Обрушение может перевести соседа через порог, и тот в свою очередь обрушится, так что одна песчинка способна вызвать лавину любого размера. На конечной сетке песчинки, которые при обрушении уходят за край, теряются, поэтому любая лавина заканчивается. Пер Бак, Чао Тан и Курт Визенфельд предложили эту модель в 1987 году в статье под названием Self-organized criticality: an explanation of 1/f noise («Самоорганизованная критичность: объяснение шума 1/f»).

Почему порядок не важен

Если неустойчивы сразу две клетки, обрушение одной из них не мешает другой обрушиться позже, потому что обрушение только добавляет песчинки другим клеткам. Исходя из этого простого факта, Дипак Дхар показал в 1990 году, что итоговая устойчивая конфигурация не зависит от порядка обрушений, как и число обрушений каждой клетки. Он назвал модель абелевой — по свойству сложения a + b = b + a. Математики знают ту же игру как chip-firing; в 1991 году её изучали на произвольных графах Андерс Бьёрнер, Ласло Ловас и Питер Шор. Именно абелево свойство позволяет вычислять большие кучи: клетка может отдать весь свой избыток за один раз.

Самоорганизованная критичность

Магнит теряет намагниченность при одной строго определённой температуре — точке Кюри, и только вблизи таких критических точек одновременно возникают флуктуации всех размеров. Бак, Тан и Визенфельд задались вопросом, почему так много явлений в природе, от землетрясений до фликкер-шума в электронных схемах, демонстрируют такое критическое поведение, хотя никто их не настраивает. Их песочная куча и была предложенным ответом: бросайте песчинки наугад, и сетка сама приходит в критическое состояние. В этом состоянии большинство песчинок ничего не делают, немногие вызывают лавины через всю сетку, а промежуточные размеры подчиняются степенному закону. На бесконечной квадратной сетке средняя высота в этом состоянии равна ровно 17/8 = 2,125.

Группа песочной кучи

На конечной сетке устойчивые конфигурации, которые снова и снова возвращаются при случайном добавлении песчинок, называют рекуррентными. Если сложить две из них поклеточно и дать сумме обрушиться, получится другая рекуррентная конфигурация, и с таким сложением они образуют конечную группу — группу песочной кучи. Число её элементов равно числу остовных деревьев сетки, что связывает её с матричной теоремой Кирхгофа о деревьях 1847 года. Её нейтральный элемент — конфигурацию, которая при прибавлении ничего не меняет, — можно найти, стабилизировав по 6 песчинок в каждой клетке, вычтя результат из 6 и снова стабилизировав. Для квадратной сетки это поразительная картина: квадрат в середине, окружённый фрактальными узорами.

Фрактал одной кучи

Положите N песчинок на одну клетку бесконечной квадратной сетки и дайте им обрушиться. Куча разрастается в примерно круглую область, ширина которой растёт как квадратный корень из N: 65 536 песчинок расходятся на 189 клеток, 262 144 — на 375, а 1 048 576 — на 747. Внутри клетки укладываются в участки с правильными узорами — сплошные тройки, полосы или шахматный порядок, — ограниченные тонкими линиями, с более мелкими участками между крупными. Уэсли Пегден и Чарльз Смарт доказали в 2013 году, что с ростом N картина сходится к пределу, а вместе с Лайонелом Левином обнаружили, что узорами управляют аполлониевы упаковки кругов — круги, вложенные в промежутки между другими кругами.

Решётки и начальные слои

Песочная куча помнит сетку, на которой растёт. С диагоналями, когда у клетки 8 соседей и она обрушивается при 8 песчинках, куча получается компактнее, а её узор устроен иначе; на треугольной решётке с 6 соседями куча приобретает шестикратную симметрию шестиугольника. Если начать со слоя, в котором уже есть песчинки, картина тоже меняется. Энн Фей, Лайонел Левин и Юваль Перес показали в 2010 году, что на квадратной сетке куча всегда стабилизируется на слое из 2 песчинок на клетку, но на слое из 3 одна лишняя песчинка заставляет лавину длиться вечно.

Попробуйте сами

Откройте фрактал песочной кучи, чтобы бросить до 1 048 576 песчинок на одну клетку и смотреть в реальном времени, как они обрушиваются на квадратной решётке, квадратной решётке с диагоналями или треугольной решётке, на пустой сетке или на слое из 1 или 2 песчинок на клетку. Плитки показывают число обрушений, ширину и среднюю высоту, а легенда — сколько клеток содержат каждое число песчинок. Режим «Нейтральный» рисует нейтральный элемент группы песочной кучи для сетки n × n, а «Лавины» бросает песчинки по одной и строит график размеров лавин в двойном логарифмическом масштабе. Увеличивайте масштаб, пока каждая клетка не покажет своё число.

Часто задаваемые вопросы

Имеет ли модель песочной кучи отношение к настоящему песку?

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

Почему куча получается круглой, если сетка квадратная?

Обрушения разносят песчинки примерно так же, как распространяется тепло, а такое распространение обычно скругляет формы. Впрочем, куча не является точным кругом, а её внутренний узор сохраняет симметрию четвёртого порядка квадратной сетки.

Случаен ли узор?

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

Что означают цвета?

Каждый цвет — это число песчинок в клетке, от 0 до числа, на единицу меньшего количества соседей. Пока куча ещё обрушивается, клетки, которые вот-вот обрушатся, получают собственный цвет.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Открыть фрактал песочной кучи