Эргодичность центральных мер на пространстве путей в графе Юнга — Фибоначчи

1 Введение 2
2 Подготовка к доказательству гипотезы 5
3 Доказательство Теоремы 2 27
4 Доказательство Следствия 5 46
5 Доказательство Следствия 6 48
6 Подготовка ко второй части доказательства гипотезы 58
7 Волшебные таблицы 123
8 Доказательство Теоремы 3 140
9 Доказательство Теоремы 4 152
10 Завершение доказательства гипотезы 198
11 Благодарности 203
Список литературы 204
Купить

Рассмотрим слова над алфавитом {1,2} с данной суммой цифр п. Как известно, их количество есть число Фибоначчи Fn+1 (F0 = 0, F1 = 1, Ffc+2 = Fk+1 + Fk), и это самая распространённая комбинаторная интерпре­тация чисел Фибоначчи. Также можно думать о разбиениях полосы 2 х п на домино 1 х 2 и 2 х 1, сопоставляя двойки парам горизонтальных домино, а единицы вертикальным домино.
Введём на этом множестве слов частичный порядок: будем говорить, что слово x предшествует слову у, если после удаления общего суффикса в слове у остаётся не меньше двоек, чем в слове x остаётся цифр.
Это действительно частичный порядок, более того, соответствующее ча­стично упорядоченное множество является модулярной решёткой, извест­ной как решётка Юнга - Фибоначчи.
Рисунок.
Графом Юнга - Фибоначчи (он изображён на рисунке выше) называют диаграмму Хассе этой решётки. Это градуированный граф, который мы представляем растущим снизу вверх начиная с пустого слова. Градуиров­кой служит функция суммы цифр. Опишем явно, как устроены ориентиро­ванные рёбра. Рёбра “вверх” из данного слова x ведут в слова, получаемые из x одной из двух операций:
1. заменить самую левую единицу на двойку;
2. вставить единицу левее чем самая левая единица.
Этот граф помимо модулярности является 1-дифференциальным, то есть для каждой вершины исходящая степень на 1 превосходит входящую степень.
Изучение градуированного графа Юнга - Фибоначчи было иницииро­вано в 1988 году одновременно и независимо такими математиками, как Ричард Стенли [9] и Сергей Владимирович Фомин [7].
Причина интереса к нему в том, что существует всего две 1-дифференциальных модулярных решётки, вторая — это решётка диаграмм Юнга, имеющая ключевое значение в теории представлений симметрической группы.
Центральные вопросы о градуированных графах касаются центральных мер на пространстве (бесконечных) путей в графе. Эта точка зрения после­довательно развивалась в работах Анатолия Моисеевича Вершика, к недав­нему обзору которого [4] и приводимой там литературе мы отсылаем чита­теля.
Среди центральных мер выделяют те, которые являются пределами мер, индуцированных путями в далёкие вершины — так называемую границу Мартина графа.
Граница пространства путей графа Юнга - Фибоначчи изучалась в ра­боте Фредерика Гудмана и Сергея Васильевича Керова (2000) [5].
Они использовали алгебраический формализм Окады [6].
Как следует из самого определения, асимптотический вопрос о грани­це напрямую связан с перечислительным вопросом о числе путей между двумя вершинами графа. Отметим важную общую работу С. В. Фомина [8] о перечислении путей в градуированных графах, в которой приводит­ся ряд общих тождеств и указывается связь помимо прочего с обобщением алгоритма Робинсона - Шенстеда - Кнута.
Гудман и Керов обходятся без явных формул для числа путей, хотя, как указал автору Павел Павлович Никитин, из их рассуждений и можно их извлечь — но количество слагаемых оказывается экспоненциальным по длине меньшего из слов. Формула с полиномиальным числом слагаемых была получена в работе [1], (сокращённая версия которой опубликована как [2]). Ниже используются ссылки на оба текста.
Керов и Гудман доказали, что список интересующих нас центральных мер исчерпывается следующими мерами:
1) Мера Планшереля: мера множества путей, проходящих через данную вершину v, равна ^("ПГ) , где d(u,v) - количество путей “вниз” из v в и.
2) Меры /'. ;,wg, параметризующиеся некоторой бесконечной последова­тельностью вершин графа Юнга-Фибоначчи. Нам удобнее другое эк­вивалентное определение в терминах некоторого бесконечного слова w (содержащего “достаточно мало” двоек) и числа fl 2 (0,1]. См. по­дробнее Лемму 1.
Доказательство эргодичности меры Планшереля было получено Керовым и Гнединым [3]. Оно основано на следующей Лемме: мера Планшереля сосредоточена на путях, вершины которых содержат “достаточно много” двоек. Мы доказываем аналогичное утверждение для остальных мер /'.„■.<, откуда стандартным рассуждением получается эргодичность.
Основной результат первой части этой работы — Теорема 2 и ей След­ствия 5 и 6. Во второй части статьи Следствия 5 и 6 используются “как чёр­ный ящик” для доказательства Теорем 3 и 4. Из Теорем 3 и 4 стандартным рассуждением получается главный результат данной работы - Следствие 14.
Купить