— КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
ДИСКРЕТНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ С СИММЕТРИЯМИ: КОМПЬЮТЕРНЫЙ АНАЛИЗ*
© 2008 г. В. В. Корняк
Объединенный институт ядерных исследований Лаборатория информационных технологий 141980 г. Дубна Московской обл.
E-mail: kornyak@jinr.ru Поступила в редакцию 01.06.2007 г.
Дискретные динамические системы и мезоскопические решеточные модели рассматриваются с точки зрения их групп симметрий. Указаны универсальные особенности поведения детерминистических динамических систем, обусловленные наличием нетривиальных симметрий. Выявлена групповая природа солитоно-подобных движущихся структур типа "космических кораблей" в клеточных автоматах. Изучение решеточных моделей также существенно облегчается при учете групп их симметрий. Для группового анализа систем обоих типов написана программа на языке Си. Программа, в частности, строит и исследует фазовые портреты по модулю группы симметрий дискретных динамических систем, ищет динамические системы, обладающие особыми свойствами, такими, как, например, обратимость. В случае мезоскопических решеточных моделей программа вычисляет микроканонические распределения и ищет фазовые переходы. Представлены некоторые вычислительные результаты и наблюдения.
1. ВВЕДЕНИЕ
Привлекательной чертой симметрийного анализа конечных дискретных систем является его полнота. В отличие от непрерывных систем, описываемых дифференциальными уравнениями, эффективный групповой анализ которых возможен только для пренебрежимо малой части всех мыслимых симметрий (точечные и контактные симметрии Ли, симметрии Бэклунда и Ли-Бэклунда, спорадические примеры так называемых нелокальных симметрий), в дискретном случае можно рассмотреть все возможные симметрии.
Кроме того, имеется множество философских и физических аргументов в пользу того, что для фундаментальной физики на малых (планков-
* Работа частично финансировалась за счет грантов №07-01-00660 Российского фонда фундаментальных исследований и №5362.2006.2 Министерства образования и науки Российской Федерации.
ских) расстояниях дискретное описание подходит лучше непрерывного. При этом математический континуум возникает как логический предел при рассмотрении больших совокупностей дискретных структур.
В основе как дифференциальных уравнений, так и клеточных автоматов лежит идея локальности: поведение системы в целом определяется взаимодействием ее близко расположенных друг к другу частей. Можно показать [1, 2], что любой набор дискретных точек, принимающих значения из конечных множеств, обладает некоторым свойством локальности. Более конкретно, рассмотрим набор из N точек, символически 6 = ..., ждг}. Каждая точка Х{ может принимать значения в своем собственном множестве значений = { ,..., в?'}, или, используя канонические обозначения, = = {0,..., (ц — 1}. Обозначая декартово произведение <31 х • • • X <3N символом , мы определяем отношение на области 6 как произвольное подмножество Я5 С С^^. В [1, 2] мы пока-
зали, что любое такое отношение К5 естественным образом обладает структурой абстрактного симплициального комплекса - одной из математических абстракций локальности.
В частных случаях эти дискретные отношения но, абстрактных симплициалъных комплексах можно свести к системам полиномиальных уравнений (если все точки жг- принимают значения в одном и том же множестве <3 с чи~ слом элементов, равным степени простого числа = рк) или к клеточным автоматам (если область 6 можно разложить на конгруэнтные симплексы с одним и тем же отношением на каждом симплексе, причем это локальное отношение является функциональным). В схему дискретных отношений укладываются также дискретные динамические системы, более общие, чем клеточные автоматы. Решеточные модели в статистической механике можно интерпретировать как ансамбли дискретных отношений.
В данной статье мы изучаем зависимость поведения дискретных динамических систем на графах (одномерных симплициальных комплексах) от симметрий графов. Мы описываем программу на языке Си для дискретного симме-трийного анализа и результаты ее применения к клеточным автоматам и мезоскопическим решеточным моделям.
2. СИММЕТРИИ РЕШЕТОК И ФУНКЦИИ НА РЕШЕТКАХ
Пространством дискретной динамической системы является решетка Г. Под словом 11 решетка" традиционно понимают регулярную систему точек в некотором непрерывном метрическом пространстве. Наиболее типичным является следующее определение: решетка - это дискретная подгруппа Г группы Ли О такая, что фундаментальная область С/Г имеет конечный объем относительно С-инвариантной меры. Частный случай этого определения используется, например, в известной монографии [3] - здесь группой О является подгруппа трансляций эвклидовой группы. Менее тривиальный пример - широко используемая при изучении решеточных моделей в статистической механике [4] решетка Бете. Эта решетка представляет собой дерево Кэли, т.е. связный аци-
клический /г-валентный граф (в теории решеточных моделей к называется координационным числом). Решетки Бете можно интерпретировать как дискретные подгруппы группы Ли изометрий гиперболической плоскости Р8Ь(2,К). Иногда решетками называют множества вершин правильных многоугольников (многогранников), образующих покрытия многообразий различных размерностей. Однако такого рода определения далеко не покрывают все случаи использования термина "решетка" в прикладной математике и математической физике (в книге [4] изучаются модели на таких, например, решетках, как решетки кагоме или вообще на произвольных графах). Во многих задачах, связанных с системами дискретных точек, ни метрические отношения между точками, ни даже наличие непрерывного многообразия, содержащего эти точки, не имеют никакого значения. Существенным является только понятие "соседства" между парами точек. Все рассматриваемые в данной статье задачи относятся к этой категории.
Поэтому мы определяем решетку как неориентированный регулярный граф без петель и кратных ребер Г, группа симметрии которого Агй (Г) действует транзитивно на множестве У(Г) его вершин. Требование транзитивности соответствует интуитивному понятию "пространства", подразумевающему, что всегда можно перейти от точки к точке с помощью "движений" в пространстве. Иногда имеет смысл добавлять дополнительные условия к этому определению. Например, для рассматриваемых ниже симметричных клеточных автоматов естественно предполагать, что группы симметрий решеток, на которых эти автоматы определены, действуют транзитивно не только на вершинах, но и на ребрах. Такие решетки называются симметрическими графами [5].
Для наглядности и упрощения изложения мы иногда будем представлять наши решетки погруженными в какие-либо непрерывные пространства типа сферы или тора (и в этом случае можно говорить о "размерности" решетки, имея ввиду размерность соответствующего многообразия), однако такое представление в нашем контексте не имеет фундаментального значения. Аналогичным образом, ребра графов в
ДИСКРЕТНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ С СИММЕТРИЯМИ Решетки, группы, орбиты: исленные характеристики
Решетка И01 |Aut (Г)| 0 = д\ПГ) 1 orbits
Тетраэдр 4 24 16 5
Гексаэдр 8 48 256 22
Икосаэдр 12 120 4096 82
Додекаэдр 20 120 1048576 9436
Графен 6x4 Тор 24 48 16777216 355353
Графен 6x4 Бутылка Клейна 24 16 16777216 1054756
Треугольная 4x6 24 96 16777216 180070
Квадратная 5x5 25 200 33554432 172112
Фуллерен Сво 60 120 1152921504606846976 и 1018 9607679885269312 и 1016
иллюстрациях изображаются линиями только для наглядности. Содержательно ребро графа -это всего лишь неупорядоченная пара вершин.
Группа автоморфизмов графа с га вершинами может содержать до га! элементов. Однако алгоритм МакКея [6], основанный на эффективно организованном дереве поиска, сводит вычисления к построению небольшого (не более чем га — 1, но обычно гораздо меньше) числа образующих группы.
Для изучения симметрий динамических систем на решетке Г необходимо рассмотреть действие группы Аи1 (Г) на пространстве £ = (^-значных функций на Г, где <3 = {0, - - -, д — 1} - множество значений, которые могут принимать вершины графа. Мы будем называть элементы пространства £ состояниями или (позже, в разделе 5) микросостояниями. Группа Аи1 (Г) действует нетранзитивно на пространстве £, расщепляя это пространство на непересекающиеся орбиты различных размеров:
N„.
£= У Ог.
г = 1
Действие группы Aut(Г) на пространстве £ определяется формулой
(дер) (х) =ср[д
Здесь х £ ^(Г), <~р (х) £ £, д £ Аи1;(Г). Полное число орбит в £ можно посчитать с помощью
леммы Бернсайда
Aorbits —
1
|Aut (Г) I ^ ,
1 v 71 3eAut(r)
N9 ,
д cycles
где N^ les - число циклов (включая циклы единичной длины) в д.
Большая группа симметрий позволяет представить динамику на решетке более компактно. Например, группой симметрий графов икосаэдра, додекаэдра и фуллерена Сво является симметрическая группа S51. Это означает, что информация о поведении любой динамической системы на этих решетках может быть сжата примерно в |S51 = 120 раз.
В таблице приведена некоторая числовая информация о решетках, изображенных на рис. 1, и их группах автоморфизмов: число вершин |У(Г)|, размер группы автоморфизмов |Aut (Г)|, полное число состояний Q = |£| = (здесь
q = 2) и число групповых орбит Norbas в пространстве состояний.
Решетки, обозначенные на рис. 1 как "Гра-фен 6x4", "Треугольная 4 X 6" и "Квадратная 5x5", можно замкнуть в регулярный граф, отождествляя противоположные стороны прямо-
1 Традиционно группой симметрий соответствующих многогранников считается группа икосаэдра являющаяся 60-элементной дискретной подгруппой группы ЭО(3). Группа совпадает со знакопеременной группой А5. Добавляя отражения к мы получаем в два раза большую (и, следовательно, более эффективную для наших целей) группу Эб .
Тетраэдр
Гексаэдр
Икосаэдр
Додекаэдр
Графен 6x4
Треугольная 4x6 Квадратная 5x5 Фуллерен Сбо
Рис. 1. Решетки таблицы.
угольников множеством различных способов. Наиболее естественные из них соответствуют погружениям в тор и бутылку Клейна. Вычисления показывают, что только погружения в тор приводят к транзитивным группам ав
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.