Диссертация (Случайные разбиения и асимптотическая теория представлений), страница 3

. , K,j = 1, . . . , L.Теорема 1 является простым следствием теоремы 2.Замечание 3. В определении величин λPi (n) на пространстве (An , µn ) имеетсянеоднозначность, связанная с произвольностью выбора линейного упорядочения алфавита A. Как будет показано в разделе 1.2.2, величины λPi (n) − Nxi (n) имеют одинаковое распределение при любых упорядочениях.15Замечание 4. Пусть µ̃ν (w) — мера на словах произвольной длины из букв алфавита A, определяемая по формулеµ̃ν (w) :=ν |w|µ|w| (w),|w|!где |w| — число букв в слове w. Будем обозначать символом Ñxi (ν) (соотв.

Ñyj (ν)) число букв xi (соотв. yj ) в случайном слове w, взятом по мере µ̃ν . В тех жепредположениях утверждение теоремы 2 выполнено для разностей λ̃Pi (ν) − Ñxi (ν),0λ̃jP (ν) − Ñyj (ν). Доказательство аналогично доказательству теоремы 2.Замечание 5. Теорема 2 может быть переформулирована в терминах, не исполь0зующих RSK-алгоритм. Для этого величины λPi (n), λjP (n) следует определять на вероятностном пространстве, состоящем из Ap -таблиц (см. определение в 2.1).1.2Основные леммы1.2.1В этом разделе мы перескажем часть материала из [56].Пусть на алфавите A задано линейное упорядочение p. Будем писать x % y,если x < y или x = y ∈ Le , и x & y, если x > y или x = y ∈ Lo ∪ G.

Назовемслово w = x1 x2 . . . xn возрастающим, если x1 % x2 % · · · % xn , и убывающим,если x1 & x2 & · · · & xn . Определим Ap -таблицу формы λ как диаграмму Юнгаλ, заполненную буквами из A, при этом вдоль строк стоят возрастающие слова, авдоль столбцов, читаемых снизу вверх, стоят убывающие слова (см. пример ниже).Обобщенный RSK-алгоритм сопоставляет слову w ∈ An пару (R(w), S(w)), где R(w)— Ap -таблица, а S(w) — стандартная1 таблица Юнга, при этом R(w) и S(w) имеютодну и ту же форму λ. Отображениеφp : An → Yn1Стандартной таблицей Юнга называется диаграмма λ, заполненная числами от 1 до |λ|, каж-дое из которых встречается ровно по одному разу, и вдоль всех строк и столбцов которой стоятвозрастающие последовательности.16определяется как сопоставление слову w этой формы λ.

Опишем действие обобщенного RSK-алгоритма.Определим сначала алгоритм строчной вставки; по Ap -таблице T и букве x ∈ Aон строит новую Ap -таблицу, которая обозначается как x → T . Эта таблица содержитна одну клетку больше, чем T , а множество её элементов содержит те же элементы,что и в T , а также элемент x. Предположим, что x ∈ Le . Тогда расстановка этихэлементов определяется следующим образом: если x больше или равен каждого элемента из первой строки, то просто ставим его в новую клетку в конце первой строки.В противном случае находим самый маленький элемент первой строки, строго превосходящий x. Выбиваем этот элемент из клетки и ставим x на его место. Если жеx ∈ Lo , то правило аналогично, только x может выбивать не только строго большие элементы, но и равные себе.

С выбитым элементом повторяем те же действияотносительно второй строчки. Продолжаем этот процесс, пока очередной выбитыйэлемент не оказывается в конце очередной строчки или не выбивается из последнейстроки — в этом случае образуем новую строку из одного элемента.Для w = x1 x2 . . . xn определим R(w) формулойR(w) := [(xn → (xn−1 → (xn−2 · · · → (x2 → (x1 → ∅)) . . . )]На каждом шаге алгоритма к R(w) присоединяется одна новая клетка. Таблица ЮнгаS(w) определяется нумерацией клеток в порядке их присоединения к R(w).Пример. Пусть x1 < x2 < y1 < y2 и Le = {x1 , x2 }, Lo = {y1 , y2 }.

Тогда слово w =x1 y1 y1 y2 x2 x1 y1 под действием обобщенного RSK-алгоритма перейдёт в пару таблиц:x1x1x2y2y11237y15y164Обозначим максимальное натуральное число, которое можно получить как сум-17му длин k непересекающихся возрастающих (соотв. убывающих) подпоследовательностей слова w, символом rk (w) (соотв. ck (w)).Предложение 1.2.1. a) Обобщенный RSK-алгоритм дает биекцию между An ипарами (R, S), где R — Ap -таблица, S — таблица Юнга и R, S имеют общуюформу, состоящую из n клеток.b) Выполнены равенства:rk (w) =kXλi (φp (w)) ;ck (w) =i=1kXλ0j (φp (w)).j=1Доказательство.

Это утверждение является обобщением теоремы Шенстеда (см.[51]). Как указано в [56, Prop.1], доказательство аналогично доказательству теоремыШенстеда (см., например, [23]).Пусть Λ — алгебра симметрических функций от бесконечного числа переменных(см. [39, Ch. 1.2]). Обозначим символом hn полные однородные симметрические функции, а символом sλ — функции Шура. Определим производящую функцию элементовhn формулойH(z) = 1 +∞Xhn z nn=1и пустьπP : Λ → C— гомоморфизм, задаваемый на базисе {hn } формулойπ P (H(z)) = eγzY 1 + βi z1 − αi zi≥1Предложение 1.2.2.

a) Пусть PP (λ) — вероятность того, что заполнение диаграммы λ независимыми случайными буквами с распределением µ1 окажется Ap таблицей. ТогдаPP (λ) = π P (sλ )б) Пусть λ ∈ Yn . Тогда:µn (w : φp (w) = λ) = dim λπ P (sλ ) = MnP (λ)18Доказательство. Cм. [56, Prop.3 и Th.1].Существуют другие обобщения RSK-алгоритма (см. [5], [49]), сохраняющие свойства утверждений 1а) и 2б), но не удовлетворяющие утверждению 1б).1.2.2Будем называть множество I ⊂ A интервалом, если из неравенств:a1 < a < a 2 ,a1 , a2 ∈ I, a ∈ Aследует, что a ∈ I. Для удобства в дальнейшем будем считать упорядочения алфавита A такими, что G образует интервал.Обозначим символами ni (R), n0j (R) число букв xi и yj в Ap -таблице R.

Назовемтипом Ap -таблицы R совокупность чиселtype(R) := ({ni (R)}, {n0j (R)}, m),где m — число букв из G, стоящих в клетках R.Напомним, что различным порядкам на A соответствуют различные отображенияφp : An → Yn .Лемма 1.2.1. Пусть зафиксированы набор чисел ({ni }; {n0j }; m) и диаграмма λ ∈Yn . Тогда величинаµn (w ∈ An : φp (w) = λ; type(R(w)) = ({ni }; {n0j }; m))не зависит от упорядочения p.Доказательство. Заметим, что вероятность совпадения двух букв из G в слове wравна 0, поэтому можно считать, что все буквы из G, входящие в слово w, различны.Пусть g1 < g2 < · · · < gm — произвольные буквы из G.

Рассмотрим набор из |λ| буквΩ = ({xi }, {yj }, g1 , . . . , gm ), в который буквы xi входят ni раз, а буквы yj — n0j раз. Будем заполнять клетки диаграммы λ буквами из Ω так, чтобы получалась Ap -таблица.19По [49, Th.3] число таких заполнений не зависит от упорядочения p. Обозначим эточисло символом d({ni }; {n0j }; m). Каждому заполнению в силу утверждения 1а) соответствует ровно dim λ слов w, составленных из набора букв Ω. Поэтому вероятностьфиксированного заполнения диаграммы λ равнаdim λYαinii≥1где множитель1m!Yn0βj jj≥11,m!возникает из условия g1 < g2 < · · · < gm . Следовательно, искомаявеличина выражается формулой, не зависящей от упорядочения p:µn (w ∈ An : φp (w) = λ; type(R(w)) = ({ni }; {n0j }; m)) =d({ni }; {n0j }; m) Y ni Y n0jβj .dim λαim!j≥1i≥10Следствие 1. Распределение величин λPi (n) − Nxi (n), λjP (n) − Nyj (n) не зависит отпорядка p.Зафиксируем на A порядок p и пусть I — интервал алфавита A. Скажем, чтоалфавит A∗ является укрупнением алфавита A, если интервал I заменяется однойновой буквой z ∈ A∗ (остальные буквы не меняются).

Будем считать, что z ∈ Le(вне зависимости от того, каким из множеств Le , Lo , G принадлежали буквы из I), исопоставим букве z вероятность, равную µ1 (I). В этом случае отображение φ∗p можноестественным образом определить какφ∗p : An → Yn ,то есть на том же вероятностном пространстве, что и отображение φp . В силу этогоможно сравнивать длины строк случайных диаграмм Юнга, порождаемых A и A∗ .Лемма 1.2.2. Для любого k > 0 выполнено неравенствоkXi=1λPi (n)≤kXi=1∗λPi (n)20Доказательство.

Вследствие утверждения 1b), имеем:kXλPi (n) = rk (w);i=1kX∗λPi (n) = rk (w∗ ).i=1Заметим, что любая возрастающая (в смысле нашего определения) подпоследовательность слова w из A переходит в возрастающую подпоследовательность соответствующего слова w∗ ∈ A∗ , так как новая буква z принадлежит множеству Le .Поэтому для любого w выполнено неравенствоrk (w∗ ) ≥ rk (w).Определим транспонирующее отображение, меняющее ролями строки и столбцы,φpt : An → Yn ,следующим образом.