Алгебра

Алгебраическая комбинаторика

Цели урока

Освоить RSK-биекцию и теорему Шенстеда об LIS
Понять формулу крюка и числа Костки
Знать определение групп Кокстера и порядок Брюа
Понимать многочлены Кажданa-Люстига и их связь с геометрией флагов

Предварительные знания

Симметрические функции
Диаграммы Юнга
Группы и симметрии

Симметрические функции

Алгоритм patience sorting - сортировка картами в стопки - оказался RSK-биекцией. Формула крюка 1954 года стала фундаментом для пяти разных областей. Многочлены Кажданa-Люстига, введённые в 1979 году, предсказали геометрический результат, доказанный через год тремя независимыми методами. Алгебраическая комбинаторика предсказывает раньше, чем доказывает.

Алгоритмы: RSK → patience sorting → LIS за O(n log n) - используется в задачах выравнивания последовательностей в биоинформатике
Физика: многочлены Кажданa-Люстига определяют канонический базис в квантовых группах IBM Research
Комбинаторная теория: числа Костки K_{λμ} вычисляют кратности в спектрах квантовых спиновых цепочек
Геометрия: P_{u,w}(q) кодируют топологию клеток Шуберта в флаговых многообразиях SL_n/B

Сто лет от Янга до Кажданa

Альфред Янг в 1900 году ввёл диаграммы для описания неприводимых S_n-модулей. В 1954 году Frame, Robinson и Thrall доказали формулу крюка f^λ = n!/∏h(i,j). Клайн Шенстед в 1961 году установил связь LIS с RSK. Дональд Кнут в 1970 году обобщил RSK до соответствия матриц. В 1979 году Давид Кажданa и Джордж Люстиг ввели многочлены P_{u,w}. Через год Бейлинсон-Бернштейн и Брилинский-Кашивара доказали их ненотрицательность независимо, используя D-модули и перверсные пучки.

RSK-соответствие и формула крюка

1900 год. Альфред Янг вводит таблицы. 1954 год. Трое математиков доказывают формулу крюка. 1961 год. Кнут находит биекцию между перестановками и парами таблиц. Алгоритм поиска LIS за O(n log n) оказывается частным случаем. Комбинаторика и алгоритмы - одно.

Алгоритм LIS за O(n log n) - patience sorting - это ровно то, что делает RSK с первой строкой таблицы P. Число стопок карт = длина LIS = λ_1(P). Это единственная известная 'простая' биекционная причина алгоритма сортировки.

RSK: σ ↔ (P,Q). Чему равна длина первой строки P?

Теорема Шенстеда: λ_1(P) = LIS(σ), λ'_1(P) = LDS(σ). Первая строка кодирует наидлиннейшую возрастающую подпоследовательность.

Числа Костки и матрица перехода

Числа Костки K_{λμ} - число полустандартных таблиц формы λ с контентом μ. Они появляются как кратности в разложении GL(n)-представлений и как коэффициенты матрицы перехода между базисами Λ. Не случайные числа - фундаментальные инварианты.

K_{(2,1),μ} для всех μ⊢3

Вычисление чисел Костки

Разбиения 3: (3), (2,1), (1,1,1). SSYT формы (2,1): K_{(2,1),(3)}=0 (нет контента (3,0,0) - нельзя заполнить строго по столбцам), K_{(2,1),(2,1)}=1 (единственная: 1 1 / 2), K_{(2,1),(1,1,1)}=2 (таблицы: 1 2/3 и 1 3/2). Итого: s_(2,1) = m_(2,1) + 2·m_(1,1,1).

Число Костки K_{λμ} равно:

K_{λμ} = |SSYT(λ,μ)| и одновременно = кратность веса μ в GL(n)-модуле V_λ. Формула: s_λ = ∑_μ K_{λμ} m_μ.

Группы Кокстера и порядок Брюа

Группы Кокстера - алгебраический скелет геометрических симметрий. Симметрическая группа S_n - тип A_{n-1}. Гиперкубическая группа - тип B_n. Икосаэдр - тип H_3. Каждая задаётся генераторами и соотношениями. Теория Кокстера - язык для всего этого зоопарка.

S_3 = группа Кокстера типа A_2

Конкретный пример

S_3 = ⟨s_1, s_2 | s_1^2=s_2^2=1, (s_1 s_2)^3=1⟩. Порядок Брюа: id < s_1, s_2 < s_1s_2, s_2s_1 < s_1s_2s_1=s_2s_1s_2. Шесть элементов, решётка из шести уровней. Многочлен Кажданa-Люстига P_{id,w_0}(q)=1 для S_3.

Группа Кокстера задаётся генераторами s_i с условиями s_i^2=1. Какое дополнительное условие определяет её структуру?

Группа Кокстера: ⟨s_1,...,s_n | s_i^2=1, (s_i s_j)^{m_{ij}}=1⟩. Матрица Кокстера m_{ij} определяет тип: A_n (m=3), B_n (m=4), G_2 (m=6), ...

Многочлены Кажданa-Люстига и канонический базис

1979 год. Кажданa и Люстиг вводят странные многочлены. Их коэффициенты неотрицательны - но это не заметим, что из определения. Декаде уходит на доказательство. В итоге: связь с пересечениями когомологий, с теоремой BBD, с квантовыми группами. Многочлены оказываются окном в геометрию флагов.

Гипотеза Кажданa-Люстига (1979, доказана в 1980 Бейлинсоном-Бернштейном и Брилинским-Кашиварой): многочлены P_{u,w} имеют неотрицательные коэффициенты. Доказательство использует теорему BBD о разложении пересечений когомологий - один из глубочайших результатов алгебраической геометрии.

Многочлены Кажданa-Люстига P_{u,w}(q) определены для u ≤ w в порядке Брюа. Ненотрицательность их коэффициентов:

Ненотрицательность коэффициентов P_{u,w}(q) - теорема 1980 года. Доказательство через геометрию: коэффициенты = размерности когомологий IC-пучков, которые неотрицательны.

Связи с другими темами

Алгебраическая комбинаторика объединяет теорию групп, геометрию и алгоритмы.

alg-28-sym-func — extends

Итоги

RSK: σ ∈ S_n ↔ (P,Q) SYT одной формы λ⊢n; λ_1(P) = LIS(σ), λ'_1(P) = LDS(σ)
Формула крюка: f^λ = n!/∏h(i,j) = dim неприводимого S_n-модуля M^λ; ∑(f^λ)^2 = n!
Числа Костки K_{λμ} = |SSYT(λ,μ)| = кратность веса μ в GL(n)-модуле V_λ
Группа Кокстера W = ⟨s_i | s_i^2=1, (s_i s_j)^{m_{ij}}=1⟩; порядок Брюа на W
Многочлены КЛ P_{u,w}(q) с ненотрицательными коэффициентами кодируют когомологии IC-пучков

Вопросы для размышления

Почему RSK-биекция между перестановками и парами SYT объясняет тождество ∑(f^λ)^2 = n!?
Как алгоритм LIS за O(n log n) связан с первой строкой RSK-таблицы?
Что геометрически означает ненотрицательность коэффициентов многочленов Кажданa-Люстига?

Связанные уроки

alg-28-sym-func — RSK связывает перестановки с функциями Шура
alg-27-lie-repr — S_n-представления через диаграммы Юнга
alg-26-quantum-groups — Многочлены Кажданa-Люстига из квантовых групп