Диаграммы Юнга и их предельная форма

А. И. Буфетов, М. В. Житлухин,
Н. Е. Козин

Диаграммы Юнга
и их предельная форма

МЦНМО

Летняя школа «Современная математика»
Дубна, июль 

А. И. Буфетов, М. В. Житлухин, Н. Е. Козин

Диаграммы Юнга и их
предельная форма

Электронное издание

Москва
Издательство МЦНМО


УДК .
ББК .
Б

Буфетов А. И., Житлухин М. В., Козин Н. Е.
Диаграммы Юнга и их предельная форма
Электронное издание
М.: МЦНМО, 
 с.
ISBN ----

Брошюра посвящена асимптотическим свойствам диаграмм Юнга —
картинок на клетчатой бумаге, изображающих разбиение натурального
числа в сумму нескольких слагаемых. В ней доказывается, что типичная
(в смысле меры Планшереля) диаграмма Юнга большого размера имеет
форму, близкую к некоторой фиксированной.
Брошюра написана по материалам цикла лекций на Летней школе
«Современная математика» в Дубне в  г. Она доступна студентам
младших курсов и школьникам старших классов.

Подготовлено на основе книги: А. И. Буфетов, М. В. Житлухин,
Н. Е. Козин. Диаграммы Юнга и их предельная форма. — -е изд.,
стереотип. — М.: МЦНМО, . — ISBN ----.

Издательство Московского центра
непрерывного математического образования
, Москва, Большой Власьевский пер., ,
тел. () ––.
http://www.mccme.ru

ISBN ----

© Буфетов А. И., Житлухин М. В.,
Козин Н. Е., .
© МЦНМО, .

Предисловие

Пусть p(N) — число способов разбить натуральное число N в сумму
невозрастающих слагаемых. Эйлер, рассматривавший задачу о вычислении p(N) для различных значений N, доказал замечательную формулу
+∞
N=0
p(N)tN =
∞
n=1

1

1−tn .

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

(1+ t + t2 +…)(1+ t2 + t4 +…)(1+ t3 + t6 +…)…=

=1+ t +2t2 +…+ p(N)tN +…;

нетрудно заметить, что коэффициент p(N) при tN должен быть в точности равен числу всех возможных способов разбиения числа N в суммы
положительных целых. Позднее Харди и Рамануджану удалось получить знаменитую асимптотическую формулу []

p(N)∼
1

4N
3 e

2π
6
N.

Кроме того, сами разбиения получили удобную и наглядную интерпретацию в виде диаграмм из клеток, которые и были названы диаграммами Юнга в честь Альфреда Юнга.

В  году Вершик и Керов в СССР [] и Логан и Шепп в США
[] одновременно и независимо обнаружили, что типичная (в смысле
меры Планшереля) диаграмма Юнга большого размера имеет форму,
близкую к некоторой фиксированной.
Вершик и Керов также доказали, что длина первой строки диаграммы Юнга имеет асимптотику 2
N (по отношению к мере Планшереля). Это позволило им получить решение знаменитой проблемы Улама
о длине максимальной возрастающей подпоследовательности случайной перестановки.
Задача описания больших диаграмм Юнга тесно связана с задачей
описания собственных значений случайных матриц большого размера. Замечательным образом распределение этих собственных значе
Альфред Юнг (—) — английский математик, выпускник и впоследствии преподаватель Кембриджского университета. В  году предложил идею представления
разбиений чисел в виде диаграмм. С  года был священником в деревне Бердбрук
графства Эссекс.
Вершиком были также получены предельные формы и для ряда других мер []).



ний имеет предельную форму — её описывает знаменитый полукруговой закон Вигнера. Согласно этому закону, с ростом N б´ольшая часть
собственных значений матрицы размера N будет попадать в интервал
[−(2+ ǫ)
N, (2+ ǫ)
N], а формы соответствующих гистограмм будут
приближаться к форме полукруга.
Перемасштабированное отклонение от 2
N длины первой строки
диаграммы Юнга размера N имеет распределение, которое, как оказывается, совпадает с аналогичным распределением для собственных
значений случайных матриц (см. работы Трейси и Видома [], Байка,
Дейфта и Йоханссона [], Бородина, Окунькова и Ольшанского [] и
Йоханссона []).
Объяснение неожиданного сходства таких, казалось бы, совершенно различных задач лежит вне рамок данной брошюры (см. по этому
поводу работу Окунькова []).

−2
N
2
N

Диаграмма Юнга и ее предельная форма

−2
N
2
N

Гистограмма собственных значений и распределение Вигнера



Брошюра представляет собой записки курса об асимптотических
свойствах диаграмм Юнга на летней школе «Современная математика» в  г.
В §  вводятся основные определения, касающиеся комбинаторики
диаграмм Юнга, которые будут использоваться в дальнейшем. В частности, определяется вероятностная мера Планшереля и приводится
формула крюков.
В §  показано, что формула крюков может быть приближена некоторым интегралом, называемым интегралом крюков.
В §  обсуждается экстремаль, определяющая предельную форму
диаграмм.
В §  изучается интеграл крюков как функция отклонения от экстремали. Оказывается, что такое отклонение фактически является соболевской нормой порядка 1/2 на прямой.
В §  сформулирована и доказана основная теорема Вершика—Керова—Логана—Шеппа о предельной форме диаграмм Юнга.
В §  доказывается оценка на длину первой строки типичной диаграммы Юнга.
В §  последняя оценка применяется для решения проблемы Улама
о среднем значении длин максимальных возрастающих подпоследовательностей перестановок из N элементов.
В приложении А, написанном В. А. Клепцыным и Г. А. Мерзоном,
приводится набросок доказательства формулы крюков, основанного
на методе отражений. Приложение Б, написанное Я. М. Сергиенко,
содержит доказательство биективности RSK-соответствия между перестановками и парами таблиц Юнга одинаковой формы.
Мы глубоко благодарны Н. Ю. Медведю и Н. С. Устинову, указавшим
на ряд недочетов и давшим ценные советы по улучшению текста, а
также В. А. Клепцыну, вклад которого в подготовку данной брошюры
невозможно переоценить.



§ . Диаграммы Юнга

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

11=5+3+1+1+1

или
11=6+4+1.

Если считать единицу за базовый «строительный элемент» натуральных чисел,
1=
,

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

10=6+3+1=

Идея такого представления очевидна из рисунка: число строк, состоящих ровно из одной клетки, есть число единиц в данном разбиении; число строк ровно из двух клеток есть число двоек в разбиении
и т. д. Добавив требование, чтобы длина строк в каждой диаграмме не
возрастала сверху вниз, получим однозначное представление каждого
разбиения натурального числа N диаграммой Юнга. Далее, диаграмму λ, состоящую из N клеток, будем называть диаграммой размера N.
Понятно, что каждая диаграмма размера N может быть получена
путем добавления к одной из диаграмм размера N −1 дополнительной
клетки справа в одну из строк. Как показывает следующий пример,
таких «диаграмм-предшественниц» может оказаться несколько:

=

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



Рис. . Фрагмент графа Юнга до размера N =4

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

N = N

и одного столбца, соответствующие разбиению

N =1+1+…+1
N раз
.

Очевидно, что из корневой вершины графа в такие диаграммы всегда
будет вести только один путь. Нас же будет интересовать вопрос, какую
(примерно) форму имеют все диаграммы, в которые ведёт большинство путей (и существует ли вообще такая форма).
Чтобы сформулировать вопрос более точно, введем меру µ(λ) на
множестве диаграмм данного размера N. Используя символ dim λ (размерность диаграммы) для обозначения числа путей, ведущих в диа
Использование обозначения dim, как и термина «размерность», здесь обусловлено
связью с теорией представлений. Число путей, ведущих в диаграмму λ, равно размерности соответствующего ей представления симметрической группы (группы перестановок
N символов).



грамму λ, определим так называемую меру Планшереля:

µ(λ)= dim2 λ

N!
.
(.)

В §  (см. лемму  и обсуждение после неё) мы установим, что мера Планшереля является вероятностной мерой на множестве всех диаграмм заданного размера: сумма мер всех диаграмм размера N будет
всегда равняться единице.
Обратимся к построению диаграмм путем добавления клеток. Спускаясь по графу к выбранной диаграмме λ, будем последовательно нумеровать добавляемые клетки. Таким образом каждому пути, ведущему в данную диаграмму, мы сопоставим новый объект: диаграмму с
пронумерованными клетками (рис. ). Легко заметить, что в каждой
строке и каждом столбце полученной диаграммы (при движении слева
направо и сверху вниз соответственно) числа возрастают. Диаграмма
с такой нумерацией клеток называется таблицей Юнга.

1
1 2
1 2
3

1 2
3

4
1 2
3

4

5

1 2
3

4

5

6

1
1
2

1
2
3

1
2
3

4
1
2
3

4
5

1
2
3

4
5

6

Рис. . Два различных пути построения диаграммы размера N =6

Обратно, легко видеть, что любая нумерация, удовлетворяющая такому ограничению, соответствует некоторому пути в графе Юнга. Таким образом, число путей dim λ, ведущих в диаграмму λ размера N,
будет равно числу таблиц Юнга данной формы — то есть числу способов размещения чисел от 1 до N в клетках диаграммы λ так, чтобы
выполнялось указанное правило возрастания номеров.
Последнее понятие, которое нам понадобится на начальном этапе — это понятие крюка. Крюком клетки □ в диаграмме λ являтся сама
клетка □ вместе со всеми клетками, расположенными от нее справа в
той же строке и снизу в том же столбце. Длиной крюка клетки □ называется число составляющих этот крюк клеток. В дальнейшем длину
крюка клетки □ будем обозначать как h(□) (от англ. hook — крюк).
На рис.  показан пример крюка одной из клеток диаграммы размера
N =33.



h(
)=10

Рис. . Пример крюка длины h=10

Оказывается, что размерность dim λ любой диаграммы λ размера N
выражается через длины крюков следующей формулой:

dim λ=
N!
□∈λ
h(□);
(.)

здесь в знаменателе стоит произведение длин крюков всех клеток диаграммы. Доказательство этой формулы, носящей имя Фрейма—Робинсона—Трелла, приводится в приложении А.
Сопоставляя (.) с (.), можно записать

µ(λ)=
N!
□∈λ
h2(□).
(.)

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

