Подсчет количества атомов с одной особой точкой
Описание файла
PDF-файл из архива "Подсчет количества атомов с одной особой точкой", который расположен в категории "". Всё это находится в предмете "модели вычислений" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
11.1ВведениеИстория вопросаПонятие атома было введено А.Т. Фоменко для качественного изучения гамильтоновых систем (см. [1]). Атомописывает бифуркацию торов Лиувилля в прообразе критического значения функции морса, определенной на симплектическом многообразии. В случае систем с двумя степенями свободы возникают трехмерные изоэнергетичексиемногообразия (при H=const). Тем самым 3-атомы ( то есть трехмерные атомы (см. [1], [2])) классифицируют особенности слоений Лиувилля.
В [1], [2] доказано, что трехмерные атомы однозначно, с точностью до гомеоморфизма,кодируется двумерными атомами.А.Т. Фоменко была поставлена задача:”Описать 2-атомы, соответствующие функциям с вырожденными критическими точками”. В качестве первого важного шага было решено исследовать атомы с одной вырожденной критической точкой степени 2n. Оказывается, что изучение 2-атомов можно свести к изучению хордовых диаграмм (сточностью до симметрии).В [3], [4] вычислено количество хордовых диаграмм с точностью до поворотов (см.
[3], Khruzin) и поворотов исимметрий (см. [4], Манойло). В работах [3] и [4] вопрос о хордовых диаграммах, соответствущих ориентируемыматомам не ставился.Также есть работы по построению алгоритмов нахождения на компьютере хордовых диаграмм с точность доповоротов, например в статьях |5| и |6|. В результате работы алгоритмов выдаются кодировки подходящих хордовыхдиаграмм. В.О.Мантуров в статье |7| с помощью языка Mathematica 3.0 перечислил хордовые диаграммы с 2nвершинами и привел их для n = 5.Для обычных (не черно-белых) хордовых диаграмм их количество, найденное в данной работе совпадает с результатами работ |3|, |4| для небольших размерностей (до n=5).
Отметим, что количество хордовых диаграммрастет очень быстро, например количество хордовых диаграмм с точностью до поворотов при n = 12 равно13176573910, как указано в работе |5| Joe Sevada. Ассимптотика роста найдена A.Khruzin в работе |3| и равна(2n − 1)!!/(2n) для хордовых диаграмм с точностью до поворотов и (2n − 1)!!/(4n) для хордовых диаграмм с точностью до поворотов и симметрий. Нестрого причины появления таких чисел таковы: количество хордовых диаграммс фиксированной нумерацией вершин равно (2n − 1)!!, при n → ∞ практически все хордовые диаграммы не имеютсимметрий и имеют период 2n, а любая хордовая диаграмма, имеющая период 2n и не имеющая осей симметрийучаствует в выражении (2n − 1)!!) ровно 2n раза с точностью до поворотов и 4n раза с точностью до поворотов исимметрий.
Аналогично, количество черно-белых диаграмм с точностью до поворотов равно n!/(2n) и с точностьюдо поворотов и симметрий — n!/(4n), т.к. количество черно-белых хордовых диаграмм с фиксированной нумерацией вершин равно n! (берем первую черную вершину, ей соответствует одна из n белых, следующей черной — однаиз n − 1 белой и т.д.). Отсюда можно сделать вывод, что доля количества классов эквивалентности ориентируемыхn!n!/ 4n→ ∞ и (2n−1)!!/ 2n→ ∞ при n → ∞.вырожденных атомов среди всех атомов стремится к 0, так как (2n−1)!!4n2nДля хордовых диаграмм с фиксированным направлением обхода и началом отсчета можно рассматривать ориентируемые поверхности им соответствующие, получающиеся приклейкой неперекрученных ленточек вместо хордк границе диска и дальнейшей заклейкой граничных окружностей дисками.
Таким образом, каждой хордовой диаграмме можно поставить в соответствие число — род соответствующей хордовой диаграмме поверхности. ФормулаХарера-Загира дает характеристическую функцию числа хордовых диаграмм рода g (см. |8|), а также в работе |9|показано, что эти числа распределены нормально с математическим ожиданием (n − ln n)/2 и дисперсией (ln n)/4.Понятие атома также представляет интерес для теории узлов и комбинаторики. Например в теории инвариантов Васильева черно-белые хордовые диаграммы, рассматриваемые в теореме 3.1.1 соответствуют хордовымдиаграммам с четными хордами.1.2Результаты данной работыВ нашей работе был проведен анализ 2-атомов с одной критической точкой. Задача была сведена к дискретнойпутем доказательства существования биекции между классами эквивалентности 2-атомов (с точностью до гомеоморфизма) и множеством хордовых черно-белых хордовых диаграмм (с точностью до поворотов и симметрий).Доказательство приведено в Утверждении 2.2.1.Для получения количества хордовых диаграмм степени 2n (с точностью до поворотов и отражений) в основубыли взяты труды [3] и [4], как результат сформулирована Теоремы 3.1.1.
В Теореме 3.1.1 получены рекуррентныесоотношения, на что Никоновым И.М. было замечено, что возможно представление данных формул в нерекуррентном виде, в следствии чего была получена Теорема 3.1.2Также в работе приведены примеры подсчета классов эквивалентностей вырожденных 2-атомов с одной критической точкой для небольших n.122.1Постановка проблемыОпределение атомаДля начала введем понятия вырожденного седлового атома с одной вершиной.Определение 2.1.1 (Вырожденный седловой атом с одной вершиной степени 2n (2-атом)). Упорядоченная пара(P, K), где P - компактная связная двумерная поверхность с краем, а K - это вложенные в нее граф, у которогоодна вершина и n ребер (n > 2), называется “вырожденным седловым атомом с одной вершиной”, если:1) каждая из компонент связности P \K гомеоморфна кольцу I × S, где I — это полуинтервал, а S — этоокружность;2) каждое кольцо можно покрасить в один из двух цветов так, что к каждому ребру графа K в поверхности Pпримыкали кольца разных цветов.
Степень атома определим, как число 2n.При таком определение легко наследуется понятия “ориентируемости” и “эквивалентности” из классическойтеории поверхностей.Определение 2.1.2. Ориентируемый атом Атом является ориентируемым, если ориентируема соответствующая поверхность P .Определение 2.1.3 (Эквивалентность двух атомов).
Атомы являются эквивалентными, если существует гомеоморфизм соответствующих пар (цвета раскраски при этом можно одновременно менять на противоположные).Теперь мы можем рассматривать классы эквивалентности 2-атомов и возникает естественный вопрос: скольковсего классов эквивалентности? Для решения данной задачи мы разобъем её, естественным образом, на задачиподсчета отдельно количества классов эквивалентности ориентируемых 2-атомов и неориентируемых.Для полноценного сведения задачи к комбинаторной очень удобным оказалось понятия хордовой диаграммы ичерно-белой хордовой диаграммы.2.2Сведение задачи к хордовым диаграммамОпределение 2.2.1 (Хордовая диаграмма с 2n вершинами). Хордовой диаграммой с 2n вершинами называетсямножество из 2n точек в вершинах правильного многоугольника и окружности, которой они принадлежат,занумерованных по часовой стрелке натуральными числами от 1 до 2n, с проведенными между ними отрезками,называемыми хордами и разделяющими точки на пары.
Точку с номером 1 называют началом отсчета. Причеммногоугольник задан на стандартной плоскости R2 , его центр совпадает с точкой (0, 0) и вершина с номером 1имеет координату (0, 1).Хордовые диаграммы можно отождествлять с 2-атомами с одной особенностью, в то время, как для описанияориентируемых 2-атомов наилучшим образом подходит поняте “черно-белой хордовой диаграммы”:Определение 2.2.2 (Черно-белая хордовая диаграмма с 2n вершинами). Черно-белой хордовой диаграммой с 2nвершинами называется хордовая диаграмма с раскрашенными поочередно в черный и белые цвета вершинами, вкоторой каждая хорда соединяет вершины только разного цвета.Замечание 1.
Раскраска не фиксирована, то есть ее можно одновременно менять на противоположную у всехвершин. Нам будет важно только то, что хорды соединяют вершины из разных классов. Следующие определениявводятся аналогично для черно-белых диаграмм.Заметим также, что так как 2-атомы мы рассматриваем с точностью до гомеоморфизма, то и на множестве всеххордовых диаграмм нужно ввести некоторые симметрии: поворот на угол 2πkn относительно центра окружности иотражение относительно основного диаметра.Определение 2.2.3 (Эквивалентность двух 2-атомов).
Две хордовые диаграммы называются эквивалентнымис точностью до поворотов и отражений, если существует поворот или отражение относительно оси, проходящей через начало координат, h : R2 → R2 (или их композиция), переводящая первую хордовую диаграмму вовторую (без учета нумерации вершин).Рационально будет рассматривать не все хордовые диаграммы, а классы эквивалентности относительно перечисленных выше симметрий.Теперь покажем сходство двух множеств: множества классов эквивалентности вырожденных седловых атомовс одной вершиной степени 2n и множества классов эквивалентности хордовых диаграмм с 2n вершинами (классыэквивалентности относительно введеных на множествах симметрий).2Утверждение 2.2.1.
Существует естественная биекция между множеством классов эквивалентности вырожденных седловых атомов с одной вырожденной точкой и множество классов эквивалентности хордовыхдиаграмм с 2n вершинами.Доказательство. Построим отображение из класса эквивалентных атомов в класс эквивалентных, с точностьюдо поворота и симметрий, хордовых диаграмм и покажем, что оно является биекцией. Рассмотрим гомеоморфныйокрестности критической точки атома степени 2n диск в стандартной плоскости R2 с центром в начале координат ирадиусом 1. На границе диска задана последовательность точек пересечения ребер графа K и диска, перенумеруемточки по часовой стрелке числами от 1 до 2n, выбрав любую из них в качетсве первой.
Известно, какие пары точексоединены ребром в графе K, а значит и в последовательности нумерованных вершин. Построим соответствующемуатому хордовую диаграммы с точностью до поворотов и отражений. На окружности радиуса 1 в стандартнойплоскости расположим точки в вершинах правильного многоугольника, зануме- руем их по часовой стрелке так,что вершина с номером 1 имеет координату (0, 1) и построим хорды между вершинами с теми номерами, которыесоединены реб- ром графа K в последовательности перенумерованных вершин на диске.
Покажем проводимыепреобразования на примере:(a)(b)(c)Рис. 1: Пример построения отображения: (d) пример вырожденного седлового атома степени 6; (c) соответствиемежду полуребрами графа K вырожденного атома и вершинами хордовой диаграммы; (a) соответствующая атомухордовая диаграмма.Покажем корректность построенного отображения, для этого нужно показать, что эквивалентные атомы перейдут в эквивалентные с точностью до поворотов и симметрий хордовые диаграммы.Гомеоморфизм атомов можно ограничить на окрестность критической точки, поэтому, если рассмотреть длядвух эквивалентных атомов соответствующие им диски и построенные по ним хордовые диаграммы, то хордовыедиаграммы могут отличаться друг от друга поворотом и отражением(ввиду неоднозначности выбора точки началаотсчета и направления обхода на граничных окружностях дисков).Докажем биективность построенного отображения.
Для любой заданной хордовой диаграммы построим единственный с точностью до гомеоморфизма соответствующий ей атом. Пусть есть хордовая диаграмма с 2n вершинами, “перебрасываем ребра во внешнюю сторону окружности”, проводим отрезки, соединяющие вершины с началомкоординат. На этом этапе получаем граф K и окрестность критической точки атома, к которой впоследствии будемприклеивать ленточки. Временно раскрасим вершины хордовой диаграммы в черный и белый цвета в шахматномпорядке.