Эффективные компьютерные методы исследования моделей в квантовой механике и статистической физике, основанных на диаграммах Юнга тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Дужин Василий Сергеевич

• Дужин Василий Сергеевич
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Дужин Василий Сергеевич

Введение

Глава 1. Физические и математические модели

1.1 Обменное взаимодействие

1.2 Математические модели

1.3 Диаграммы Юнга

1.4 Граф Юнга и граф Шура

1.5 Размерность диаграммы

1.6 Нормализованная размерность диаграммы

1.7 Марковские процессы на двумерных графах Юнга и Шура

1.7.1 Центральные процессы и процесс Планшереля

1.7.2 Процесс Ричардсона

1.7.3 Обобщенный процесс Ричардсона

1.7.4 Равномерная мера на диаграммах Юнга

1.8 Трехмерные диаграммы Юнга

1.9 Марковские процессы на трехмерных градуированных графах

1.10 Асимптотика

вероятностей путей на трехмерных градуированных графах

1.10.1 Способы нормировки размерностей трехмерных диаграмм

1.11 Предельные формы диаграмм Юнга в марковских процессах

на двумерных графах Юнга, Шура и на трехмерном графе Юнга

1.11.1 Предельные формы двумерных диаграмм Юнга

1.11.2 Предельные формы диаграмм Юнга в трехмерном случае

Глава 2. Построение и анализ последовательностей диаграмм Юнга

2.1 Жадные последовательности

2.1.1 Жадные последовательности на двумерном графе Юнга

2.1.2 Жадные последовательности на графе Шура

2.1.3 Жадные последовательности на трехмерном графе Юнга

2.1.4 Гипотеза об эквивалентности жадных последовательностей

Стр.

2.2 Построение неприводимых и проективных представлений симметрической группы S(п) с большими размерностями

2.2.1 Переборные алгоритмы

2.2.2 Стратегии поиска диаграмм Юнга с большими размерностями

2.2.3 Поиск двумерных

стандартных диаграмм Юнга с большими размерностями

2.2.4 Поиск двумерных

строгих диаграмм Юнга с большими размерностями

2.3 Исследование

осцилляций функции нормализованной размерности диаграмм Юнга

2.3.1 Осцилляции нормализованных

размерностей двумерных строгих диаграмм Юнга

2.3.2 Осцилляции нормализованных

размерностей двумерных стандартных диаграмм Юнга

2.3.3 Осцилляции

нормализованных размерностей трехмерных диаграмм Юнга

2.4 Исследование ро ста нормализованных

размерностей диаграмм Юнга в различных марковских процессах

2.4.1 Пределы

нормализованных размерностей двумерных диаграмм Юнга

2.4.2 Пределы

нормализованных размерностей трехмерных диаграмм Юнга

2.5 Распределение вероятностей на фронте диаграммы

2.5.1 Двумерный случай. Планшерелевская статистика

2.5.2 Трехмерный случай. Псевдопланшерелевская статистика

2.6 Геометрические свойства трехмерных диаграмм Юнга из

жадной и случайных псевдопланшерелевских последовательностей

2.6.1 Исследование асимптотики количества угловых клеток

2.6.2 Исследование асимптотики длины поперечника

2.6.3 Исследование

асимптотики количества кластеров из угловых клеток

2.6.4 Предельные формы диаграмм жадной

и случайной псевдопланшерелевских последовательностей

Стр.

Глава 3. Компьютерное исследование

преобразования Шютценберже и соответствия RSK

3.1 Преобразование Шютценберже

3.1.1 Алгоритм быстрого преобразования Шютценберже

3.1.2 Некоторые приложения преобразования Шютценберже

3.1.3 Связь между преобразованием

Шютценберже и центральными марковскими процессами

3.2 Соответствие Робинсона—Шенстеда—Кнута (RSK)

3.3 Связь между

преобразованиями Шютценберже и Робинсона-Шенстеда-Кнута

3.4 Численные эксперименты с преобразованиемRSK

3.4.1 Зависимость значения первого элемента входной последовательности от координат конца пути Шютценберже

3.4.2 Исследование положения единицы

в перестановках, двойственно эквивалентных по Кнуту

Заключение

Список литературы

Список рисунков

Список таблиц

Приложение А. Описание пакета программ

А.1 Перечень методов классов Diagram, Diagram3D, Process

А.2 Исходный код основных функций

А.2.1 Некоторые

функции для работы с двумерными диаграммами Юнга . . .120 А.2.2 Некоторые

функции для работы с трехмерными диаграммами Юнга

Введение диссертации (часть автореферата) на тему «Эффективные компьютерные методы исследования моделей в квантовой механике и статистической физике, основанных на диаграммах Юнга»

Введение

Методы исследования многих моделей современной математической физики основаны на комбинаторике диаграмм и таблиц Юнга с использованием марковских процессов на двумерном и трехмерном графах Юнга. Примером является квантовое описание явления ферромагнетизма в полупроводниках, которое впервые было предложено Гейзенбергом в 1928 г [1] и развивалось в работах Бете, Изинга и Бакстера. В 1972 г. Родни Бакстер [2; 3] дал решение трехмерной модели ферромагнетизма (XYZ модели Гейзенберга). Фаддеев Л. Д. увидел, что ряд формул Бакстера напоминает хорошо знакомые ему формулы из метода обратной задачи. Полученные на этом пути в работе [4] результаты позволили интерпретировать формулы Бакстера, используя операторы на диаграммах Юнга. Это позволило упростить и алгебраизовать формулы Бакстера и дать их полное доказательство. Физический интерес представляет изучение асимптотических свойств этой модели и, в особенности, основного состояния — состояния с наименьшей энергией и младших возбужденных состояний.

Эвристический метод нахождения точных решений задачи о периодической цепочке взаимодействующих частиц со спином 1/2 (ХХХ-модель Гейзенберга [5—7]), возникающий в случае изотропной ферромагнитной цепочки, основан на применении анзаца Бете. С помощью этого анзаца решения задачи связываются с периодическим оператором Кокстера—Лапласа, действующим в векторном пространстве, порожденном таблицами Юнга, состоящими из двух строк. Спектр оператора Кокстера—Лапласа и его собственные векторы описывают физические характеристики состояний такой изотропной ферромагнитой цепочки.

Периодический оператор Кокстера—Лапласа определяется некоторой двухстрочной диаграммой Юнга из п клеток и элементом группового кольца Ьп = п1 — + 52 +... + Sn) симметрической группы 5п, где I это тождественная перестановка, Si для % Е [1 ,п — 1] кокстеровские транспозиции (%,% +1) и дополнительная транспозиция 5п вида (п, 1), меняющая числа п и 1 местами. Спектр этого оператора соответствует спектру гамильтониана исходной системы. Сложность вычисления этого спектра обусловлена тем фактом, что этот оператор действует в пространстве огромной размерности, базис которого занумерован всеми двухстрочными таблицами Юнга заданной формы. Например, размерность пространства, в котором

действует оператор Ьп, соответствующий прямоугольной диаграмме Юнга размера 2 • п, равна числу Каталана Сп = п!(ПП+1)!. Тем не менее, подход, основанный на эффективной реализации операций линейной алгебры в векторных пространствах, порожденных таблицами Юнга фиксированной формы, позволил определить спектры соответствующих операторов Лапласа для всех п ^ 30. В матричном представлении последний из этих операторов имел бы размер С15 х С15 = 2674440 х 2674440.

В статье [8] описана связь широко используемых в квантовой статистической механике статистик Ферми и Бозе с плоскими разбиениями и их предельными формами. В частности, А. М. Вершиком было показано, что равномерная статистика на множестве двумерных диаграмм Юнга заданного размера эквивалентна статистике двумерного Бозе-газа.

Д. А. Павловым была исследована асимптотика роста размерностей максимальных неприводимых представлений симметрической группы Б(п) [9], а также были изучены предельные формы типичных двумерных и трехмерныхдиаграмм Юнга, построенных с помощью процесса Ричардсона.

В работе [10] исследовано поведение частиц, соответствующее случайному марковскому процессу на двумерном графе Юнга со статистикой Ричардсона. Здесь впервые была установлена предельная форма диаграмм Юнга данного случайного процесса, соответствующего динамике поведения частиц в этой модели. Функция, описывающая предельную форму для процесса Ричардсона, определяет одновременно и функцию плотности распространения частиц в этой физической модели.

Исследование асимптотического поведения марковских процессов на градуированных графах имеет приложения в таких областях науки, как теория представлений (центральные меры, описание характеров симметрической группы, поиск неприводимых представлений симметрической группы S(п) с максимальными размерностями [11] и др. задачи асимптотической теории представлений), статистическая физика (трехмерная модель Изинга [12]), построение точных решений интегрируемых систем дифференциальных уравнений в частных производных, описывающих интегрируемые модели квантовой механики [13], построение дискретных моделей для уравнений квантовой механики [14—16], исследование информационных потоков в телекоммуникационных сетях [17; 18] и др. Для изучения поведения ферромагнетиков при нулевой температуре важными являются характеристики роста трехмерных диаграмм Юнга [19]. Применение комбинаторного аппарата диаграмм Юнга приводит к интересным связям между физикой кристаллов и физикой инстантонов [20—22].

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

В рамках диссертации разработаны методы и алгоритмы исследования случайных марковских процессов на двумерном и трехмерном графах Юнга. Отдельный интерес представляют последовательности двумерных диаграмм Юнга, генерируемые центральным процессом Планшереля. При этом до сих пор не существует описания всех центральных процессов на трехмерном графе Юнга. Для невырожденного центрального процесса, который также существует и в трехмерном случае, не известны точные формулы его переходных вероятностей. Некоторые его асимптотические свойства могут быть изучены с помощью специального асимптотически центрального процесса, а метод вычисления его копереходных вероятностей предложен в данной диссертации.

В работе [23] впервые был поставлен вопрос о поиске диаграмм Юнга с максимальными размерностями. Дж. Маккеем [24] была выдвинута гипотеза о существовании неприводимых представлений симметрической группы с аномально большими размерностями, атакже перебором были получены первые 75 диаграмм с максимальными размерностями. В работе [11] были получены границы нормализованных размерностей для типичных планшерелевских диаграмм Юнга, там же была опровергнута гипотеза МакКея. При этом в этой статье была выдвинута гипотеза о существовании предела таких нормализованных размерностей. Последовательность диаграмм с максимальными размерностями была продолжена до 130 этажа графа Юнга в работе [9], там же была построена последовательность из первых 310 диаграмм Юнга с наибольшими размерностями среди всех симметричных диаграмм и диаграмм, отличающихся не более чем на одну клетку от симметричных. В работах [25; 26] описаны алгоритмы, с помощью которых была построена последовательность диаграмм Юнга со сверхбольшими размерностями, включающая все известные диаграммы с максимальными размерностями, до 106-го уровня графа Юнга. Для случая строгих диаграмм Юнга результат аналогичного эксперимента

описан в [27]. В работе [28] были даны оценки пределов нормализованных размерностей двумерных диаграмм Юнга с максимальными размерностями. В статье [29] был предложен рандомизированный вариант преобразования Шютценберже [30], с помощью которого была построена последовательность из 1000 трехмерных диаграмм Юнга со сверхбольшими размерностями.

Целью данной работы является разработка методов и алгоритмов для исследования асимптотического поведения марковских процессов на двумерных и трехмерных градуированных графах. Для достижения поставленной цели необходимо было решить следующие задачи:

1. Разработка, обоснование и тестирование эффективных вычислительных методов и алгоритмов

а) построения неприводимых и проективных представлений симметрической группы S(п) со сверхбольшими размерностями с применением параллельных вычислений на кластере.

б) исследования жадных последовательностей диаграмм в марковских процессах на двумерных и трехмерных градуированных графах с применением параллельных вычислений на кластере.

в) исследования копереходных вероятностей на трехмерном графе Юнга с применением параллельных вычислений на кластере.

2. Создание комплексов проблемно-ориентированных программ для проведения численного эксперимента с целью исследования

а) размерностей неприводимых представлений симметрической группы S (п).

б) жадных последовательностей диаграмм Юнга.

в) копереходных вероятностей для центральной меры на градуированных графах.

3. Проведение комплексного исследования гипотезы о пределе нормализованных размерностей планшерелевских диаграмм Юнга, выдвинутой А. М. Вершиком [11], в рамках численного эксперимента [28] со сверхбольшими последовательностями диаграмм Юнга на современном вычислительном кластере.

Научная новизна:

1. С помощью разработанных в рамках диссертационного исследования алгоритмов впервые были построены последовательности из 106 неприводимых и проективных представлений симметрической группы 5(п) со сверхбольшими размерностями.

2. Впервые был предложен подход для вычисления копереходных вероятностей центрального процесса на трехмерном графе Юнга, основанный на рандомизированном варианте преобразования Шютценберже [29].

3. Впервые построена последовательность трехмерных диаграмм Юнга со сверхбольшими размерностями [29].

4. Было выполнено исследование свойств жадных последовательностей двумерных и трехмерных диаграмм Юнга [27].

Практическая значимость

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

Результаты диссертации уже были использованы в учебном процессе при создании бакалаврского курса «Специальные разделы алгебры», предназначенного для студентов направлений 01.03.02 «Прикладная математика и информатика» и 09.03.04 «Программная инженерия».

Методология и методы исследования. В асимптотической комбинаторике существуют различные методы исследования задач, связанных с поведением таблиц Юнга для различных марковских процессов. К этим методам в частности относится использование алгоритма Робинсона—Шенстеда—Кнута (RSK) и преобразования Шютценберже [30].

В настоящей работе были реализованы генераторы последовательностей из следующих марковских процессов:

- процесс Ричардсона на 2D и 3D графах Юнга и Шура;

- процесс Планшереля на двумерных графах Юнга и Шура;

- псевдопланшерелевский процесс на трехмерном графе Юнга.

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

нормированы. Метод нормировки двумерных стандартных диаграмм Юнга был введен в [11]. В рамках данной диссертации были предложены формулы для нормализованных размерностей на графе Шура [27] и трехмерном графе Юнга [31; 32].

Существуют различные методы моделирования случайных последовательностей диаграмм Юнга с планшерелевским распределением. В частности, в работе [9] такие последовательности генерировались с помощью алгоритма Робинсона——Шенстеда——Кнута. В настоящем диссертационном исследовании эта задача решалась посредством реализации марковских цепей на графе Юнга. Это позволило построить последовательности диаграмм Юнга намного большей длины.

Для вычисления копереходных вероятностей центрального случайного процесса на трехмерном графе Юнга был использован метод, основанный на использовании преобразования Шютценберже. В диссертации была предложена его рандомизированная модификация, применение которой позволило генерировать случайные таблицы Юнга заданной формы с равномерным случайным распределением [29].

Основные положения, выносимые на защиту:

1. Разработаны и реализованы в виде комплекса программ оригинальные алгоритмы построения последовательностей двумерных и трехмерных диаграмм Юнга со сверхбольшими размерностями.

2. С помощью компьютерных экспериментов установлено, что произвольная пара последовательностей жадного ветвления, построенная на двумерном или трехмерном графе Юнга, объединяется через конечное число шагов [27; 28; 31; 32].

3. Предложен метод вычисления копереходных вероятностей на произвольном градуированном графе с помощью рандомизированного преобразования Шютценберже [29].

4. Доказано, что путь Шютценберже для произвольной таблицы Юнга является последовательностью активных клеток в предложенном в данной работе алгоритме быстрого преобразования Шютценберже

5. Доказано, что размерности диаграмм Юнга, получаемых с помощью предложенного в данном диссертационном исследовании алгоритма встряски с глубиной 1, обладают размерностями, большими чем у исходных диаграмм, или равными им.

Достоверность Вычислительные результаты, полученные в ходе выполнения диссертационной работы, были основаны на использовании строгих методов

математического моделирования и находятся в соответствии с результатами, полученными другими авторами.

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

Оценки пределов нормализованных размерностей двумерных диаграмм Юнга с максимальными размерностями, полученные в [28], лежат в пределах диапазона, полученного А. М. Вершиком [11].

Апробация работы. Основные результаты работы докладывались на:

- международной конференции по приложениям компьютерной алгебры (ACA-2016) (Кассель, Германия);

- международной конференции по приложениям компьютерной алгебры (ACA-2017) (Иерусалим, Израиль);

- международной конференции по приложениям компьютерной алгебры (ACA-2018) (Сантьяго-де-Компостела, Испания);

- международной конференции по полиномиальной компьютерной алгебре (PCA) (ММИ имени Эйлера, Санкт-Петербург, 2015, 2016, 2017, 2018, 2019);

- международной конференции Computer Assisted Mathematics (CAM-2019) (СПбГЭТУ «ЛЭТИ», Санкт-Петербург, 2019);

- международном рабочем совещании по компьютерной алгебре (Дубна, 2015,2016,2018,2019);

- семинаре по теории представлений и динамическим системам (ПОМИ им. СтекловаРАН, Санкт-Петербург, 2016);

- семинаре по математическому моделированию РУДН (Москва, 2018);

- семинаре по алгоритмической математике (СПбГЭТУ «ЛЭТИ», Санкт-Петербург, 2017,2018).

Личный вклад. Вклад соискателя в работах, выполненных в соавторстве, заключается в:

- Разработке и реализации алгоритмов, связанных с двумерными и трехмерными диаграммами Юнга;

- Проведении численного моделирования марковских процессов на градуированных графах;

- Исследовании свойств жадных последовательностей двумерных и трехмерных диаграмм Юнга;

- Получении оценок для пределов нормализованных размерностей типичных и жадных последовательностей диаграмм Юнга;

- Разработке и реализации алгоритма рандомизированного преобразования Шютценберже на двумерных и трехмерных таблицах Юнга.

Публикации. Основные результаты по теме диссертации изложены в 15 печатных изданиях, 6 из которых изданы в журналах, рекомендованных ВАК, 8 —— в тезисах докладов на международных конференциях.

Объем и структура работы. Диссертация состоит из введения, трёх глав, заключения и одного приложения. Полный объём диссертации составляет 128 страниц, включая 48 рисунков и 10 таблиц. Список литературы содержит 84 наименования.

Глава 1. Физические и математические модели 1.1 Обменное взаимодействие

Объектом моделирования в настоящей диссертации является квантовое явление ферромагнетизма, обычно описываемое в рамках теории обменного взаимодействия. Для описания явлений, связанных с ферромагнитным или антиферромагнитным упорядочиванием в кристаллах обычно используют предложенное Дираком выражение гамильтониана обменного взаимодействия спинов, содержащего скалярное произведение операторов спина и й2 :

Я12 = -3128182, (1.1)

где ,112 — обменный интеграл, знак которого определяет тип взаимодействия: ■112 > 0 соответствует ферромагнитному упорядочиванию, а .112 < 0 — антиферромагнитному. Само понятие обменного взаимодействия непосредственно основано на концепции спина, возникшей в конце 20-х годов прошлого века в работах Дирака, Паули, Уленбека, Гаудсмита, Гейзенберга и других. Работам этих авторов предшествовала модель, предложенная в 1920 году Вильгельмом Ленцем, а позднее развитая Эрнстом Изингом (1925 год), в которой рассматривается одномерная решётка спинов, ориентированных вдоль одного выбранного направления. Она далеко не сразу получила признание, но к 40-м годам прошлого века было показано, что хотя она и не объясняет явление ферромагнетизма , но тем не менее хорошо описывает магнетизм двухэлементных сплавов (Ханс Бете, 1938), а область ее применения гораздо шире и не ограничивается только магнитными явлениями [33].

1.2 Математические модели

В 1926 году В. Гейзенбергом была предложена квантовая модель цепочки атомов с двумя уровнями энергии. В такой цепочке взаимодействие происходит только между соседними атомами, а сама модель является упрощенной моделью одномерного кристалла. В приближении слабого взаимодействия в первом порядке теории возмущений кулоновские и магнитные силы между соседними элементами

цепочки являются причиной расщепления средних значений энергии в каждой паре соседних атомов, спины которых параллельны или антипараллельны. При этом также происходит обмен спиновых состояний в парах соседних электронов цепочки. Учет усредненных магнитных сил, действующих вдоль некоторого направления анизотропии, приводит к выражению для гамильтониана этой анизотропной модели, которая называется ХХ2 цепочкой Гейзенберга. В 1931 году Хансом Бете был предложен метод (анзац Бете), формально позволяющий находить спектр энергии и собственные векторы оператора гамильтониана в этой задаче. С помощью этого анзаца такая задача была сведена к решению некоторой системы трансцендентных уравнений. Эта система уравнений позже получила название системы уравнений Бете. Им также было показано, что собственные векторы и собственные значения гамильтониана, то есть волновые функции и соответствующие им уровни энергии, могут быть представлены в некотором специальном виде как суперпозиции экспонент, занумерованных разбиениями натуральных чисел. Как хорошо известно, множество такие разбиений находится во взаимно-однозначном соответствии с множеством стандартных диаграммам Юнга. Это объясняет появление диаграмм и таблиц Юнга в исследовании квантовых изотропных и анизотропных моделей ферромагнетиков, а также связь этих моделей с комбинаторикой диаграмм Юнга. Метод, предложенный Бете, оказался успешно применимым не только к описанию одномерных цепочек Гейзенберга, но и к самым разнообразным квантовым моделям систем более высокой размерности, например, к шестивершинной модели двумерной классической статистической физики.

Модель Гейзенберга описывает фундаментальную точно интегрируемую задачу о периодической цепочке N взаимодействующих частиц со спином 1/2. Если учитывается взаимодействие только ближайших соседей, тогда состояние такой системы в случае изотропной цепочки частиц (ХХХ-модель Гейзенберга,

[5]) описывается гамильтонианом:

7 М

Н = -+ °к+х + ^^ш), (1.2)

к=1

где 7 > 0 в случае ферромагнитной изотропной цепочки и ,7 < 0 в случае антиферромагнитной, а о£ — это операторы спина для к-го узла этой цепочки. Операторы

спина можно представить в виде тензорного произведения матрицы Паули находящейся в качестве к-го сомножителя, и (Ж — 1) двумерных единичных матриц:

-а40®- 401)® (0 0) ®- 40 0) (13)

^-^-'

к-1 М-к

Сами матрицы Паули -а для а £ [ху,(] выглядят так:

--(; 0} - -(: —)• - -(0 —10 (»>

Решение такой задачи сводится к приведению к диагональному виду матрицы

гамильтониана, то есть нахождению её спектра. Матрица гамильтониана является квадратной матрицей с 2М количеством строк. Конечно, физический интерес представляет асимптотика спектра в пределе при N ^ ж.

В 1931 г. Ханс Бете предложил эвристический метод нахождения точного решения для изотропной ферромагнитной цепочки частиц, который получил впоследствии название анзац Бете. Он рассмотрел состояние цепочки с т спинами, ориентированными вниз, и (Ж — т) спинами, ориентированными вверх. Обозначим за хк для 1 ^ к ^ т координаты узлов цепочки со спинами вниз (при этом х1 < х2 < ... < хт, 1 ^ хк ^ N). Анзац Бете состоит в предположении о том, что волновая функция такого состояния представляет суперпозицию экспонент:

/ т \

Ф-Х)А-• ехр хА , (1.5)

- V 3=1 )

где р1, р2, рт обозначает некоторую совокупность неравных чисел, а - — это

произвольная перестановка этих т чисел. Доказательство того, что волновая функция может быть представлена в виде суперпозиции экспонент, а также способы нахождения фактических значений амплитуд Аст и чисел рз, характеризующих собственные значения энергии и волновые функции системы, можно найти в [5].

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

данном случае можно зафиксировать некоторую двухстрочную диаграмму Юнга из п клеток и использовать стандартное представление Юнга—Яманути (см. [34]), для которого существуют простые явные формулы для матричных элементов кокстеровских образующих симметрической группы.

Рассмотрим теперь периодический оператор Кокстера—Лапласа для симметрической группы, действующий в пространстве представления, определенного некоторой двухстрочной диаграммой Юнга из п клеток [35]:

Ьп = п1 — (51 + 52 +... + ), (1.6)

где I — это тождественная перестановка, для к <Е [1,п — 1] —кокстеровские транспозиции (г,г + 1) и дополнительная транспозиция Бп вида (п, 1) меняющая числа п и 1 местами. Если обозначить (1.6) за оператор Ь, действующий в векторном пространстве, порожденном всеми таблицами Юнга фиксированной формы, тогда существует замечательная связь между ним и гамильтонианом (1.2) (см. [6]):

Я = 4(2Ь—п1), (1.7)

которая связывает описанную ранее фундаментальную задачу квантовой механики о решениях ХХХ цепочки Гейзенберга с представлениями симметрических групп, диаграммами и таблицами Юнга.

1.3 Диаграммы Юнга

Диаграммы Юнга являются одним из фундаментальных комбинаторных объектов. Они дают графическое представление разбиений натуральных чисел, рассмотренных Леонардом Эйлером еще в 18 веке [36]. Каждая диаграмма соответствует определенному разбиению натурального числа на положительные слагаемые.

Двумерная стандартная диаграмма Юнга представляет собой конечный набор клеток, расположенных в виде строк, выровненных по левому краю, длина которых не возрастает [37; 38]. Существуют различные способы представления диаграмм Юнга. В данной работе была использована так называемая французская нотация: диаграмма отображается в верхнем правом квадранте. Диаграмма Юнга формы Л = (11,12,..,1к), где 11 ^ 12 ^ ... ^ 1к, содержит к столбцов, ¿-й столбец состоит из I, клеток. Высоты столбцов (11,12,...,1к) образуют разбиение числа п [39], равного 11 + + .. + 1к. Количество клеток в каждом столбце соответствует слагаемому в

разбиении натурального числа. На рис. 1.1 изображены примеры диаграмм Юнга, которые соответствуют разбиениям (3,2,2,2,2,2), (6,5,2,2,1,1), (5,4,2,1) и (6).

а) б) в) г)

Рисунок 1.1 — Двумерные диаграммы Юнга

Строгой диаграммой Юнга называется диаграмма Юнга, не имеющая столбцов одинаковой высоты. На рис. 1.1 изображены: а), б) — стандартные диаграммы Юнга; в), г) — строгие диаграммы Юнга. Строгие диаграммы соответствуют так называемым строгим разбиениям натуральных чисел. Разбиение ¡1,12,...,1к числа п называется строгим, если оно не содержит одинаковых компонент.

Размер диаграммы п равен количеству клеток из которых она состоит. Шириной диаграммы называется количество столбцов в диаграмме, высотой диаграммы — количество строк.

Заметим, что в некоторых случаях бывает удобнее рассматривать диаграммы Юнга, применяя нормированные координаты Вершика—Керова. Эта система координат (и, V) получается из прямоугольной системы координат (х, у) поворотом осей на 45° по часовой стрелке. Красной линией (рис. 1.2) выделена форма диаграммы

Список литературы диссертационного исследования кандидат наук Дужин Василий Сергеевич, 2020 год

Список литературы

1. Heisenberg W. Zur Theorie des Ferromagnetismus // Zeitschrift fur Physik. — 1928.-Sept.-Vol. 49,no. 9/10.-P. 619-636.

2. Baxter R. J. Partition function of the Eight-Vertex lattice model // Annals of Physics. —1972. —Т. 70, № 1. —С. 193—228.

3. Baxter R. J. One-dimensional anisotropic Heisenberg chain // Annals of Physics. — 1972. — Т. 70, № 2. — С. 323—337.

4. Тахтаджян Л. А., Фаддеев Л. Д. Квантовый метод обратной задачи и XYZ модель Гейзенберга// УМН. —1979. — Т. 34,5(209). — С. 13—63.

5. Изюмов Ю. А., Скрябин Ю. Н. Статистическая механика магнитоупорядочен-ных систем. — М.: Наука, 1987. — 264 с.

6. Tsilevich N.V. Spectral properties of the periodic Coxeter Laplacian in the two-row ferromagnetic case//Зап. научн. сем. ПОМИ. —2010. — Vol. 378. — P. 111—132.

7. Tsilevich N.V. On the behavior of the periodic Coxeter Laplacian in some representations related to the antiferromagnetic asymptotic mode and continual limits // Зап. научн. сем. ПОМИ.—2011. —Vol. 390. —P. 286—298.

8. Vershik A. M. Statistical mechanics of combinatorial partitions, and their limit shapes. //Fund Anal. Appl. —1996. — Vol. 30. — P. 90—105.

9. ВершикА. М., Павлов Д. А. Численные эксперименты в задачах асимптотической теории представлений // Зап. научн. сем. ПОМИ. — 2009. — Т. 373. — С. 77-93.

10. Rost H. Non-equilibrium behaviour of a many particle process: Density profile and local equilibria//Probability Theory and Related Fields. —1981. — Vol. 58, no. 1. — P. 41-53.

11. Вершик А. М., Керов С. В. Асимптотика максимальной и типичной размерностей неприводимых представлений симметрической группы // Функциональный анализ и его приложения. —1985. — Т. 19, № 1. — С. 25—36.

12. Cerf R., Kenyon R. The Low-Temperature Expansion of the Wulff Crystal in the 3D Ising Model // Communications in Mathematical Physics. — 2001. — Vol. 222, no. 1. —P. 147—179.

13. Боголюбов Н. М. Перечисление плоских разбиений и алгебраический анзац Бете//ТМФ. — 2007. — Т. 150,№2. —С. 193—203.

14. FeynmanR. P., HibbsA. R. Quantum Mechanics andPathlntegrals. —McGraw-Hill College, 1965.-365 p.

15. Hoyle F., Narlikar J. V. Cosmological Models in a Conformally Invariant Gravitational Theory—II: A New Model // Monthly Notices of the Royal Astronomical Society. —1972. — Vol. 155, no. 3. —P. 323—335.

16. Gersch H. A. Feynman's relativistic chessboard as an Ising model // Int. J. Theor. Phys. —1981. — Vol. 20, no. 7. — P. 491—501.

17. Попова А. Е. Новые вероятностные меры на двумерных и трёхмерных диаграммах Юнга // Наука и современность —2014: сборник материалов XXX Международной научно-практической конференции / под ред. П. ред. Черно-ваС. С.—Новосибирск: ИздательствоЦРНС,2014. —С. 171—176.

18. Попова А. Е. Диаграммы Юнга в теории макросистем : дис.... канд. физ.-мат. наук: 05.13.01. — Воронеж, 2016. —118 с.

19. Okounkov A., ReshetikhinN. Correlation function of Schur process with application to local geometry of arandom 3-dimensional Young diagram// J. Amer. Math. Soc. — 2003. - Vol. 16. -P. 581-603.

20. Nekrasov N.Seiberg-Witten prepotential from instanton counting // Adv. Theor. Math. Phys. — 2003. — Vol. 7, no. 5. — P. 831—864.

21. Okounkov A., Nekrasov N.Seiberg-Witten Theory and Random Partitions // The Unity of Mathematics. Progress in Mathematics. Т. 244 / под ред. P. Etingof, V. Retakh, I. M. Singer. —Boston,MA: Birkhauser Boston, 2006. — С. 525—596.

22. Okounkov A., ReshetikhinN., Vafa C. Quantum Calabi-Yau and Classical Crystals // The Unity of Mathematics: In Honor of the Ninetieth Birthday of I.M. Gelfand / под ред. P. Etingof, V. Retakh, I. M. Singer. — Boston, MA : Birkhauser Boston, 2006. — С. 597-618.

23. Baer R. M., Brock P. Natural sorting over permutation spaces // Math. Comp. — 1968. - Vol. 22. -P. 385-410.

24. McKay. J. The Largest Degrees ofIrreducible Characters ofthe Symmetric Group// Math. Comp. — 1976. — Vol. 30, no. 135. — P. 624—631.

25. Васильев Н. Н., Дужин В. С. Построение неприводимых представлений симметрической группы S(N) с большими и максимальными размерностями // Информационно-управляющие системы. — 2015. — Т. 76, № 3. — С. 17—22.

26. Дужин В. С., ЧудновскаяА. А. Поиск диаграммЮнгас большими размерностями // Компьютерные инструменты в образовании. — 2019. — № 4. — С. 33—43.

27. Vasiliev N. N., Duzhin VS. A Study of the Growth of the Maximum and Typical Normalized Dimensions of Strict Young Diagrams // Journal of Mathematical Sciences. — 2016. — Vol. 216. — P. 53—64.

28. Duzhin V. S., Vasilyev N.N.Asymptotic Behavior of Normalized Dimensions of Standard and Strict Young Diagrams - Growth and Oscillations // Journal of Knot Theory and Its Ramifications. — 2016. — Vol. 25. — P. 19—34.

29. Дужин В. С., Васильев Н. Н. Рандомизированное преобразование Шютцен-берже и вычисление копереходных вероятностей центрального процесса на трехмерном графе Юнга // Теория представлений, динамические системы, комбинаторные методы. XXXI, Зап. научн. сем. ПОМИ. — 2019. — Т. 485. — С. 90-106.

30. SchutzenbergerM.P. QuelquesremarquessuruneconstructiondeSchensted//Math. Scandinavica. —1963. —Vol. 12.—P. 117—128.

31. VasilievN.N.,Duzhin VS. Numerical Study ofthe Asymptotics ofPathProbabilities in a Markov Process Close to a Central One on the 3D Young Graph // Journal of Mathematical Sciences. —2017. — Vol. 224. — P. 214—220.

32. Duzhin V., VasilyevN.Modeling of an Asymptotically CentralMarkovProcesson3D YoungGraph//MathematicsinComputer Science.— 2017.—'Vol. 11.—P. 315—328.

33. Mattis D. C. The theory of magnetism made simple: An introduction to physical concepts and to some useful mathematical methods. — New York: World Scientific Publishing Company, 2006. — 567 p.

34. КапланИ.Г. Симметрия многоэлектронных систем.—М.: Наука, 1969.—407 с.

35. AshkadovD., VasilievN.OnevaluationsofspectrumandmatrixelementsofCoxeter-Laplace operators in vector spaces generated by Young tableaux // International Conference "Polynomial Computer Algebra 2012". —2012. — P. 13.

36. EulerL. Introductioinanalysininfinitorum. Tomusprimus. —Lausannae: Marcum-MichaelemBousquet, 1748.

37

38

39

40

41

42

43

44

45

46

47

48

49

50

Фултон У. Таблицы Юнга и их приложения к теории представлений и геометрии. — М. : МЦНМО, 2006.

Смирнов Е. Ю. Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы. —М. : МЦНМО, 2014.

ЭндрюсД. Теория разбиений. —М. : Наука, 1982.

Берштейн М. А., Мерзон Г. А. Диаграммы Юнга, пути на решётке и метод отражений // Матем. просв. — 2014. — № 18. — С. 112—141.

Frame J. S., Robinson G. d., Thrall R. M. The hook graphs of the symmetric group // Canad J. Math. —1954. — Vol. 6. — P. 316—325.

Макдональд И. Симметрические функции и многочлены Холла. — М. : Мир, 1985.

ВершикА. М. Формула крюков и связанные с нею тождества// Зап. научн. сем. ЛОМИ. —1989. —Т. 172. —С. 3—20.

Greene C., Nijenhuis A., Wilf H. A probabilistic proof of a formula for the number of Young tableaux of a given shape // Advances in Math. — 1979. — Vol. 31. — P. 104-109.

СпивакА. В. Формула крюков // Квант. — 2009. — Т. 3. — С. 44—47.

Петров Л. Случайные блуждания на строгих разбиениях // Зап. научн. сем. ПОМИ. — 2009. — Т. 373. — С. 226—272.

Petrov F. Polynomial Approach to Explicit Formulae for Generalized Binomial Coefficients // European Journal of Mathematics. — 2016. — Т. 444, № 2. — С. 226-272.

Иванов В. Н. Размерность косых сдвинутых диаграмм Юнга и проективные характеры бесконечной симметрической группы // Зап. научн. сем. ПОМИ. — 1997. — Т. 240. — С. 115-135.

Назаров М. Л. Ортогональный базис в неприводимых проективных представлениях симметрической группы // Функциональный анализ и его приложения. —1988. — Т. 22, № 1. — С. 77—78.

ВершикА. М., Керов С. В. Асимптотика меры Планшереля симметрической группы и предельная форма таблиц Юнга// ДАН СССР. —1977.—Т. 233, № 6. — С. 1024-1027.

51. Вершик А. М., Керов С. В. Асимптотическая теория характеров симметрической группы // Функциональный анализ и его приложения. — 1981. — Т. 15, №4. —С. 15—27.

52. Бородин А. М. Мультипликативные центральные меры на графе Шура // Зап. научн. сем. ПОМИ. —1997. — Т. 240. — С. 44—52.

53. Richardson D. Random growth in a tesselation // Proc. Cambridge Phil. Soc. — 1973. — Vol. 74. — P. 515—528.

54. MacMahon P. A. Combinatory analysis. Vol. 2. — Chelsea Pub. Co., 1960. — 642 p.

55. BratleyP., McKay J. K. S. Algorithm 313: Multi-dimensional partition generator// Comm. ACM. —1967. — 'Vol. 10,no. 10.—P. 666.

56. Knuth D. E. A note on solid partitions // Math. Comp. — 1970. — Vol. 24. — P. 955—961.

57. Mustonen V., RajeshR. Numerical Estimation of the Asymptotic Behaviour of Solid Partitions of an Integer // J. Phys. A: Math. Gen. — 2003. — Vol. 36, no. 24. — P. 6651—6659.

58. Destainville N., Govindarajan S. Estimating the Asymptotics of Solid Partitions // J. Stat.Phys.—2015. —Vol. 158. —P. 950—967.

59. Kreuzer M., Robbiano L. Computational Linear and Commutative Algebra. — Springer, 2016. — 332 p.

60. Mora T., Robbiano L. The Grobner fan of an ideal // Journal of Symbolic Computation. — 1988. — Vol. 6, no. 2. — P. 183—208.

61. Павлов Д. А. Полиномиальные модели, основанные на диаграммах Юнга : дис. ... канд. физ.-мат. наук: 05.13.18. — Москва,2012. —143 с.

62. Васильев Н. Н., ТерентьевА. Б. Моделирование мер, близких к центральным, на трехмерном графе Юнга // Зап. научн. сем. ПОМИ. — 2015. — Т. 432. — С. 68-82.

63. Ivanov V. Plancherel measure on shifted Young diagrams // Representation Theory, Dynamical Systems, and Asymptotic Combinatorics. Vol. 217. — Providence, RI : Amer. Math. Soc., 11/2006. —P. 73—86.

64. Matsumoto S. Polynomiality of shifted Plancherel averages and content evaluations// Annales Mathématiques Blaise Pascal.—2017.—Vol. 24, no. 1. — P. 55—82.

65. Temperley H. Statistical mechanics and the partition of numbers. The form of the crystal surfaces. //Proc. Cambridge Phil. Soc. —1952. — Vol. 48. —P. 683—697.

66. Duzhin V., Vasilyev N.The greedy sequences of Young diagrams produced by Markov processes on 2D and 3D Young graphs // International Conference "Polynomial Computer Algebra 2017". — 2017.

67. Vasilyev N., Duzhin V. Greedy trajectories of Plancherel processes on two dimensional Young and Schur graphs // Proceedings of the XXII Conference on Applications of Computer Algebra (ACA 2016). — 2016.

68. Vasilyev N. N., Duzhin V. S. The sequences of the greedy branching in 2D and 3D Young graphs [Электронный ресурс] // 19th Workshop on Computer Algebra DUBNA-2016: материалы международной конференции. — Dubna: JINR, 2016. — Режим доступа: http://compalg.jinr.ru/Dubna2016/abstracts2016_files/ Vasilyev%20Duzhin.pdf (Дата обращения: 01.12.2019).

69. Vasilyev N. N., Duzhin V. S. Computation of irreducible representations of symmetric group S(n) with large and maximal dimensions [Электронный ресурс] // 18th Workshop on Computer Algebra DUBNA-2015: материалы международной конференции. — Dubna: JINR, 2015. — Режим доступа: http://compalg.jinr.ru/Dubna2015/abstracts2015_files/Vasiliev.pdf (Дата обращения: 01.12.2019).

70. Vasilyev N. N., Duzhin V. S. Computation of maximal dimensions of irreducible representations of symmetric groups S(n) // International Conference "Polynomial Computer Algebra 2015". — 2015.

71. Duzhin V., Vassilyev N.Growth and oscillations of normalized dimensions of standard and strict Young diagrams // International Conference "Polynomial Computer Algebra 2016".-2016.

72. Буфетов А. И. Решение гипотезы Вершика — Керова об энтропии меры Планшереля // Успехи математических наук. — 2010. — Vol. 65, no. 1. — P. 181-182.

73. Stanley R., Fomin S. Enumerative Combinatorics: — Cambridge University Press, 1999. — (Cambridge Studies in Advanced Mathematics; v. 2).

74. Robinson G. d. On the representations of the symmetric group // American Journal of Math. —1938. — Vol. 60. — P. 745—760.

75. Schensted C. Longest increasing and decreasing subsequences // Canadian Journal ofMath. —1961. —Vol. 13. —P. 179—191.

76. Knuth D. E. Permutations, matrices, and generalized Young tableaux. // Pacific J. Math. — 1970. — Vol. 34, no. 3. — P. 709—727.

77. Kerov S. V., Vershik A. M. The characters of the infinite symmetric group and probability properties of the Robinson-Schensted-Knuth algorithm // SIAM J. Algebraic Discrete Methods. —1986.—'Vol. 7, no. 1.—P. 116—124.

r

78. Romik D., Sniady P. Jeu de taquin dynamics on infinite Young tableaux and second class particles // Annals of Probability: An Official Journal of the Institute of Mathematical Statistics. — 2015. — Vol. 43, no. 2. —P. 682—737.

79. Васильев Н. Н. ,ДужинВ. С., Кузьмин А. Д. Исследование свойств классов эквивалентности перестановок с помощью обратного преобразования Робинсона — Шенстеда — Кнута // Информационно-управляющие системы. — 2019. — Т. 98, № 1. — С. 11-22.

80. Vassiliev N. N., Duzhin V. S. Randomized Schutzenberger transformation and uniformly random generator of Young tableaux [Электронный ресурс] // 20th Workshop on Computer Algebra DUBNA-2018: материалы международной конференции. — Dubna: JINR, 2018. — Режим доступа: http://compalg.jinr.ru/Dubna2018/abstracts2018_files/1313_Duzhin.pdf (Дата обращения: 01.12.2019).

81. Duzhin V., Vasilyev N.Schutzenberger transformation on graded graphs: Implementation and numerical experiments // International Conference "Polynomial Computer Algebra 2018". — 2018.

82. Duzhin V., Vassiliev N. Schutzenberger transformation on the three-dimensional Young graph // Proceedings of the XXIV Conference on Applications of Computer Algebra (ACA 2018). - 2018.

83. Kerov S. V. Transition Probabilities for Continual Young Diagrams and the Markov Moment Problem//Funct. Anal. Appl. — 1993. — Vol. 27, no. 2. — P. 104—117.

84. Knuth D. E. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching.—USA: Addison Wesley Longman Publishing Co., Inc., 1998. — 800 с.

Список рисунков

1.1 Двумерные диаграммы Юнга................................................17

1.2 Диаграмма Юнга в системе

координат Вершика—Керова и в прямоугольной системе координат ... 17

1.3 Первые 6 уровней графа Юнга и графа Шура................................19

1.4 Двумерные таблицы Юнга....................................................19

1.5 Сдвинутые двумерные таблицы Юнга...................21

1.6 Примеры трехмерных диаграмм Юнга...................28

1.7 Начало трехмерного графа Юнга......................28

1.8 Нормализованные размерности

жадного и случайного путей псевдопланшерелевского процесса.....32

1.9 Фронт двумерной диаграммы Юнга....................33

1.10 Предельные формы двумерных диаграмм Юнга ............................34

2.1 Начало жадного пути из корня графа Юнга ..................................37

2.2 Нормализованные размерности максимальных диаграмм

и диаграмм из жадной последовательности, а также их разности.....42

2.3 Блок-схема алгоритма встряски.......................44

2.4 Блок-схема алгоритма ветвей ................................................45

2.5 Нормализованные размерности стандартных диаграмм,

полученных жадным алгоритмом и алгоритмами встряски и ветвей . . . 46

2.6 Нормализованные размерности строгих диаграмм,

полученных жадным алгоритмом и алгоритмами встряски и ветвей . . . 48

2.7 Нормализованные размерности строгих

диаграмм из жадной и типичной планшерелевских последовательностей 49

2.8 Нормализованные размерности жадной и типичной планшерелевских последовательностей диаграмм от 900 тысяч до миллиона клеток .... 50

2.9 Нормализованные размерности

жадной последовательности диаграмм от 900 тысяч до миллиона клеток 50

2.10 Разности нормализованных

размерностей в жадной последовательности строгих диаграмм Юнга . . 51

2.11 Разности нормализованных размерностей в жадной последовательности строгих диаграмм Юнга, умноженные на л/и. ... 52

2.12 Первые 12 уровней разностей нормализованных размерностей.....53

2.13 Разности нормализованных

размерностей для случаев добавления клетки в 6-ю и 9-ю строки.....53

2.14 Некоторые особые уровни разностей

нормализованных размерностей и соответствующие им номера строк . . 54

2.15 Разности нормализованных размерностей в

жадной по следовательно сти стандартных диаграмм, умноженные на л/и 56

2.16 Нормализованные разно сти

нормализованных размерностей диаграмм в трехмерном жадном пути . 57

2.17 Диаграммы из жадной последовательности размера 1827,1836,1837 . . 58

2.18 Нормализованные разности

нормализованных размерностей диаграмм в трехмерном жадном пути . 59

2.19 Усредненные значения и дисперсии нормализованных

размерностей типичных по мере Планшереля диаграмм.........60

2.20 Сходимость нормализованных размерностей

к возможному пределу для жадных последовательностей диаграмм Юнга 61

2.21 Нормализованные размерности диаграмм Юнга, построенных

с помощью процесса Ричардсона (100 последовательностей длины 5 • 106) 62

2.22 Нормализованные размерности диаграмм Юнга, построенных

с помощью процесса Ричардсона (последовательность длины 8 • 107) . . 63

2.23 Оценки пределов

жадного и случайного путей псевдопланшерелевского процесса ..... 64

2.24 Распределения вероятностей

на фронте двумерной диаграммы Юнга из жадной последовательности . 65

2.25 Распределения вероятностей

на фронте трехмерной диаграммы Юнга из жадной последовательности 66

2.26 Трехмерная диаграмма Юнга из 1000 клеток................67

2.27 Нормированное количество

угловых клеток в псевдопланшерелевских последовательностях ..... 68

2.28 Нормированные длины

поперечников диаграмм в псевдопланшерелевских последовательностях 69

2.29 Нормированное

количество кластеров в псевдопланшерелевских последовательностях . 69

2.30 Сравнение предельных форм

диаграмм из жадной и псевдопланшерелевской последовательностей . . 70

2.31 Контур фронта и максимального замкнутого сечения

псевдопланшерелевской диаграммы Юнга из 15 миллионов клеток ... 71

3.1 Пути Шютценберже всех прообразов таблицы Юнга размера 106.....75

3.2 Нормализованные

размерности трехмерных диаграмм Юнга в жадной последовательности 85

3.3 Частотные гистограммы координат последних клеток путей Шютценберже и распределение вероятностей на фронтах диаграмм Юнга 86

3.4 Связь между значениями первых элементов входящих бесконечных последовательностей и предельными углами наклона нервов таблиц Q . 89

3.5 Гистограммы частот значений первого элемента последовательности . . 91

3.6 Математические

ожидания и среднеквадратические отклонения значений первого элемента последовательностей, получаемых обратным алгоритмом RSK 92

3.7 Расстояния между точками пересечения с предельным фронтом

прямых с углами наклона 6 и нервов таблиц Q размера а) 104 и б) 105 . . . 93

Список таблиц

1 Значения обычной и нормализованной

размерностей для двух стандартных диаграмм Юнга размера n = 45 ... 23

2 Примеры, в которых

алгоритмы встряски и ветвей дают большие размерности диаграмм по сравнению с размерностями диаграмм из жадной последовательности 47

3 Соответствие между уровнями

и номерами строк диаграммы Юнга, в которые были добавлены клетки . 52

4 Примеры разбиений для некоторых максимальных диаграмм Юнга . . . 55

5 Максимальные размерности плоских разбиений с размерами от 1 до 33 . 81

6 Первые

65 членов жадной последовательности трехмерных диаграмм Юнга . . . 82

7 Использованные псевдонимы типов данных ................ 111

8 Перечень функций класса Diagram ..................... 111

9 Перечень функций класса Diagram3D ...................115

10 Перечень функций класса Process ...................... 118

Приложение А Описание пакета программ

В ходе выполнения диссертационной работы был реализован программный пакет на языке C++, позволяющий работать с двумерными и трехмерными диаграммами Юнга и таблицами Юнга. Также реализована возможность моделирования различных марковских процессов на диаграммах. Функции, реализованные в данном проекте, позволяют добавлять и удалять клетки диаграмм, вычислять пересечения пары диаграмм, вычислять переходные вероятности в используемых марковских процессах и т.д. Для выполнения некоторых сложных задач были реализованы параллельные вычисления.

Программный пакет включает в себя реализацию следующих классов:

1. Diagram — Двумерная стандартная диаграмма Юнга

2. StrictDiagram — Двумерная строгая диаграмма Юнга

3. Diagram3D — Трехмерная диаграмма Юнга

4. Process — Марковский процесс

5. Sequence — Последовательность двумерных диаграмм Юнга

6. Sequence3D — Последовательность трехмерных диаграмм Юнга

7. Schutzenberger — Преобразование Шютценберже

8. Strategy — Стратегии поиска диаграмм с большими размерностями

В таблице 7 приведены использованные в коде псевдонимы типов данных C++.

Координаты клеток трехмерных диаграмм Юнга задаются с помощью структуры tu:

struct tu {

uint64 x, y, z;

tu() : x(0), y(0), z(0) { }

tu(uint64 xx, uint64 yy, uint64 zz) : x(xx), y(yy), z(zz) { }

};

Исходный код программного пакета до ступен по адре су http://bit.ly/39eMMrd.

Таблица 7—Использованные псевдонимы типов данных

Имя Идентификатор типа C++

псевдонима

uint64 unsigned long long

di std::deque<uint64>

mi std::map<uint64, double>

pu std::pair<uint64, uint64>

pd std::pair<double, double>

vi std::vector<uint64>

vd std::vector<double>

vvi std::vector<vi>

vvd std::vector<vd>

vpu std::vector<pu>

vvpu std::vector<vpu>

mdd std::map<double, double>

mpu std::map<pu, double>

mpp std::map<pu, pu>

mppd std::map<pu, pair<double, uint64> >

dpu std::deque<pu>

lpu std::list<pu>

dtu std::deque<tu>

mtu std::map<tu, uint64>

А.1 Перечень методов классов Diagram, Diagram3D, Process

Ниже приведены перечни основных методов классов Diagram, Diagram3D и Process с кратким описанием их назначения. Более подробное описание классов не приведено, поскольку полный список содержит более 500 методов.

Таблица 8 — Перечень функций класса Diagram

Функция Комментарий

Diagram() Diagram(Diagram* copy_from) Конструктор, инициализирующий диаграмму Конструктор, инициализирующий диаграмму по диаграмме copy from

Продолжение таблицы 8

Функция

double calc_point_plansh_prob(uint64 line)

void calc_point_plansh_ prob_rat(uint64 line, int* num, int* den)

double calc_corner_plansh_prob(uint64 line)

uint64 calc_plansh_probs(uint64 num = 0, mi* best_p=NULL)

void calc_max_prob(uint64* line, double* prob)

int add(uint64 line, bool calculate_alpha = false) int add_with_ probsum (uint64 line, bool calculate_alpha = false) int add_max()

int add_max_with_ probsum()

int add_kth(uint64 k)

int remove(uint64 line, double prob = -1) int remove_min()

mi* get_points()

mi* get_corners()

void calc_n_min_corners (uint64 num, mi* c)

uint64 get_height() uint64 get_height(uint64 line) uint64 get_width() uint64 get_width(uint64 line) uint64 get_size()

double get_corners_ div_diameter()

di* get_rows() di* get_cols()

Комментарий

Вычисление планшерелевской вероятности угловой клетки дополнения в строке line Вычисление планшерелевской вероятности угловой клетки дополнения в строке line (как рациональное число)

Вычисление планшерелевской вероятности угловой клетки в строке line (вероятность перехода из диаграммы размера n— 1) Вычисление планшерелевских вероятностей всех угловых клеток дополнения Поиск угловой клетки дополнения с наибольшей планшерелевской вероятностью Добавление клетки в строку line Добавление клетки в строку line (с модификацией суммы логарифмов вероятностей) Добавление клетки с максимальной планше-релевской вероятностью Добавление клетки с максимальной планше-релевской вероятностью (с модификацией суммы логарифмов вероятностей) Добавление клетки с k-й наибольшей вероятностью

Удаление клетки из строки line Удаление клетки с минималной планшерелевской вероятностью

Получение переченя угловых клеток дополнения

Получение переченя угловых клеток Сохранение num угловых клеток с наименьшей планшерелевской вероятностью в c Получение высоты диаграммы Получение высоты столбца line Получение ширины диаграммы Получение ширины строки line Получение размера диаграммы Получение отношения количества угловых клеток к поперечнику Получение переченя строк Получение переченя столбцов

Функция Комментарий

uint64 get_last_added() Получение номера строки последней добав-

ленной клетки

void calc_all_tabs(set<vi>* tabs, vi tab = vi(0), Вычисление всех таблиц Юнга заданной

Diagram diag = Diagram()) формы

void calc_size_from_rows() Вычисление размера диаграммы по списку

строк

double comp_dim(Diagram* diag) Сравнение размерности данной диаграммы и

диаграммы diag

uint64 get_hook(uint64 x, uint64 y) Вычисление длины крюка с вершиной в x,y

bool is_flat() Проверка, состоит ли диаграмма только из

одной строки

void set_rows(di r) Инициализация перечня строк

void init() Инициализация диаграммы диаграммой

размера 1

voidinit(Diagram* copy_from) Инициализация диаграммы диаграммой

copy_from

void init_by_rows (di r) Инициализация диаграммы по перечню строк

void init_by_cols(di c) Инициализация диаграммы по перечню

столбцов

voidinit_by_tab(dpu&tab,constuint64LEN=0) Инициализация диаграммы таблицей tab

int rows_correctness() Проверка корректности перечня строк

int rowcol_correctness() Проверка соответствия между перечнями

строк и столбцов

void add_prob_sum(double psum) Модификация значения нормализованной

размерности

void get_legal_points (Diagram* target, mi* Определение переченя угловых клеток

leg_P) дополнения, находящихся в пределах диа-

граммы target

void remove_illegal_points (Diagram& target) Удаление угловых клеток дополнения,

находящихся вне пределов диаграммы target

bool is_equal_to(Diagram* comp) Проверка эквивалентности диаграмме comp

bool is_equal_to_cols(di c) Проверка эквивалентности c и длин столбцов

диаграммы

void calc_cols_from_rows() Определение длин столбцов по длинам строк

void calc_rows_from_cols() Определение длин строк по длинам столбцов

void calc_pointscorners_ from_rows() Определение перечней угловых клеток и уг-

ловых клеток дополнения по перечню строк

double hook_prod_ratio (Diagram* diag2) Вычисление отношения произведений длин

крюков данной диаграммы и диаграммы diag2

bool is_symmetric() Проверка симметричности диаграммы

Продолжение таблицы 8

Функция

bool is_symmetric_to (Diagram* diag2)

bool consists_of(uint64 x, uint64 y)

double get_c()

double calc_c_slow()

void calc_exact_dim(mpz_t dim)

double calc_planch_stadev()

double calc_planch_maxdiff() void print()

void print_cols(ostream &output = cout) void print_rows_ASCII()

void print_rowsdim() void print_rowcols() void print_verbose()

void print_points(const char* FNAME=NULL) void print_corners(ostream &output = cout) void print_corners_with_ braces(ostream &output = cout)

void print_corners_for_ gnuplot(uint64 exper_num, uint64 diag_num, uint64 depth, bool print_to_cout = false)

void print_corners_for_ gnuplot_all_boxes (const char* data_fname) void print_corners_for_ gnuplot_skewed(const char* data_fname)

void print_corners_for_ gnuplot_contour_only (const char* data_fname) void print_to_gif(bool contour, const char* gifname, uint64 maxX = 0, uint64 maxY = 0, const char* added=, const char* removed=) void print_to_eps(const char* epsname)

Комментарий

Проверка симметричности по отношению к диаграмме diag2

Проверка принадлежности клетки ^у) диаграмме

Получение нормализованной размерности Вычисление нормализованную размерность Вычисление точной размерности (с исползо-ванием длинной арифметики) Вычисление среднеквадратического отклонения высот столбцов от планшерелевской кривой

Вычисление максимальной разности высот столбцов и планшерелевской кривой Вывод в консоль длин строк Вывод в консоль длин столбцов Вывод длин строк в виде символов (1 символ = 1 клетка)

Вывод длин строк и размерности

Вывод длин строк и столбцов

Вывод длин строк, столбцов, а также перечней

угловых клеток и угловых клеток дополнения

Вывод перечня угловых клеток дополнения

Вывод перечня угловых клеток

Вывод перечня угловых клеток

Вывод перечня угловых клеток в формате gnuplot

Вывод перечня угловых клеток в формате gnuplot

Вывод перечня угловых клеток в формате gnuplot (сдвинутая диаграмма) Вывод перечня угловых клеток в формате gnuplot (для вывода фронта диаграммы) Сохранение диаграммы в графическом виде

e.gif)

Сохранение диаграммы в графическом виде (*.eps)

Функция Комментарий

void print_to_png(const char* FNAME_PNG, bool verbose = false, const int TYPE = 0, const pu SIZE = pu(0,0), const int NOTATION = 0, mpp* TAB = NULL) void print_to_png(cfg& CFG) void print_hooks_to_png (const char* FNAME_PNG) void print_max_pl(FILE* f =NULL) Сохранение диаграммы в графическом виде Сохранение диаграммы в графическом виде (*™;> Сохранение длин крюков клеток диаграммы в графическом виде (*.png) Вывод в файл информации о клетке с максимальной планшерелевской вероятностью

Таблица 9 — Перечень функций класса Diagram3D

Функция

Diagram3D(bool standard = true)

void init(bool standard = true)

voidinit(Diagram3D* copy_from)

void init_by_cols(vvi c)

void init_by_rows(vvi r) void init_by_bars(vvi b)

void calc_size_from_cols()

void calc_rows_from_cols()

void calc_cols_from_rows()

void calc_bars_from_cols()

void calc_cols_from_bars()

void calc_pointscorners()

void print_all()

void print_rows(ostream &output = cout, bool print_endl = true)

Комментарий

Конструктор, инициализирующий диаграмму

Инициализация диаграммы диаграммой размера 1

Инициализация диаграммы диаграммой сору_йот

Инициализация диаграммы по перечню горизонтальных столбцов Инициализация диаграммы по перечню строк Инициализация диаграммы по перечню вертикальных столбцов Определение размера диаграммы по длинам горизонтальных столбцов Определение длин строк по длинам горизонтальных столбцов

Определение длин горизонтальных столбцов по длинам строк

Определение длин вертикальных столбцов по длинам горизонтальных столбцов Определение длин горизонтальных столбцов по длинам вертикальных столбцов Вычисление угловых клеток и угловых клеток дополнения

Вывод длин строк, столбцов, а также перечней угловых клеток и угловых клеток дополнения Вывод длин строк

Продолжение таблицы 9

Функция

void print_cols(ostream &output = cout, bool print_endl = true)

void print_bars(ostream &output = cout) void print_points(ostream &output = cout) void print_corners(ostream &output = cout) void print_outer_cubes (const char* fname) void print_to_img(const char* fname_png, bool new_color = false, pu new_cube = pu(0, 0), uint64MAX_XYZ = 0) void print_to_img(cfg& CFG)

static map<uint64, map<vvi, mpz_t> > calc_all_dimensions (bool STANDARD, const uint64 MAX_LEVEL) static void print_all_dimensions (bool STANDARD, const uint64MAX_LEVEL) double calc_planch_sum (double alpha = 1)

double calc_planch_prob (uint64 z, uint64 y, double alpha = 1)

void calc_planch_probs (double alpha)

double calc_planch_weight (uint64 z, uint64 y)

void fill_cluster(uint64 z, uint64 y, uint64 x)

uint64 calc_clusters_number()

uint64 calc_clusters_number (map<tu, int>&

nearby)

int add(constuint64 z, const uint64 y)

int add(const pu place)

int remove(const uint64 z, const uint64 y)

int remove(const pu place)

void add_point(uint64 z, uint64 y)

void add_corner(uint64 z, uint64 y)

void remove_invalid_point (pu coord, vvi&

target_rows)

void remove_invalid_points (vvi& target_rows)

Комментарий

Вывод длин горизонтальных столбцов

Вывод длин вертикальных столбцов Вывод координатугловых клеток дополнения Вывод координатугловых клеток Вывод координат клеток фронта диаграммы Сохранение диаграммы в графическом виде

(*.png)

Сохранение диаграммы в графическом виде

(*.png)

Вычисление размерностей всех трехмерных диаграмм Юнга до уровня MAX_LEVEL включительно

Вывод размерностей всех диаграмм до уровня MAX_LEVEL включительно Вычисление суммы псевдопланшерелевских весов

Вычисление псевдопланшерелевской вероятности в клетке ((x,y)) Вычисление псевдопланшерелевских вероятностей

Вычисление псевдопланшерелевского веса в клетке(x,y)

Обход кластера, состоящего из угловых клеток, начиная с клетки (x,y,z) Вычисление числа кластеров Вычисление числа кластеров

Добавление клетки Добавление клетки Удаление клетки Удаление клетки

Добавление угловой клетки дополнения Добавление угловой клетки Удаление угловой клетки дополнения с координатами coord, если он находится вне пределов target_rows

Удаление угловых клеток дополнения, находящихся вне пределов target_rows

Функция

void rescale_probs()

uint64 get_size() mpu* get_points()

mpu* get_corners() vvi* get_cols()

vvi* get_rows()

vvi* get_bars()