WikiDer > Холл слово

В математика, в районах теория групп и комбинаторика, Слова зала предоставить уникальный моноидная факторизация из свободный моноид. Они также полностью заказанный, и таким образом обеспечить полный порядок на моноиде. Это аналог более известного случая Слова Линдона; на самом деле слова Линдона - это особый случай, и почти все свойства, которыми обладают слова Линдона, переносятся на слова Холла. Слова Холла находятся во взаимно однозначном соответствии с Холл деревья. Это бинарные деревья; вместе они образуют Набор для прихожей. Этот набор является особенным полностью заказанный подмножество свободной неассоциативной алгебры, т.е. свободная магма. В этой форме деревья Холла служат основой для свободные алгебры Ли, и может использоваться для выполнения коммутаций, требуемых Теорема Пуанкаре – Биркгофа – Витта. используется при строительстве универсальная обертывающая алгебра. Таким образом, это обобщает тот же процесс, когда делается со словами Линдона. Деревья холлов также можно использовать для полного упорядочения элементов группы с помощью процесс сбора коммутатора, который является частным случаем приведенной ниже общей конструкции. Можно показать, что Лазерные наборы совпадают с холловскими множествами.

Историческое развитие идет в порядке, обратном приведенному выше описанию. В процесс сбора коммутатора был впервые описан в 1934 г. Филип Холл и исследован в 1937 г. Вильгельм Магнус.^[1][2] Наборы Холла были представлены Маршалл Холл на основе работы Филипа Холла о группах.^[3] Впоследствии Вильгельм Магнус показали, что они возникают как градуированная алгебра Ли связанный с фильтрацией на свободная группа предоставленный нижний центральный ряд. Эта переписка была мотивирована коммутатор идентичности в теория групп благодаря Филиппу Холлу и Эрнст Витт.

Набор для прихожей

В Набор для прихожей это полностью заказанный подмножество свободной неассоциативной алгебры, т.е. свободная магма. Позволять ${ Displaystyle А = {а_ {1}, ldots, а_ {п}}}$ - набор образующих, и пусть ${ Displaystyle М (А)}$ быть свободной магмой ${ displaystyle A}$. Свободная магма - это просто набор неассоциативных струн в буквах ${ displaystyle A}$, с сохранением скобок, чтобы показать группировку. Точно так же свободная магма - это совокупность всех бинарные деревья чьи листья являются элементами ${ displaystyle A}$.

Набор Холла ${ Displaystyle H подмножество M (A)}$ можно построить рекурсивно следующим образом:

• Элементы ${ displaystyle A}$ дается произвольный общий порядок.
• В комплект Холла входят генераторы: ${ Displaystyle A подмножество H.}$
• Коммутатор ${ displaystyle [x, y] in H}$ если и только если ${ displaystyle x in H}$ и ${ displaystyle y in H}$ и ${ displaystyle x> y}$ и:
  • Либо ${ displaystyle x in A}$ (и поэтому ${ displaystyle y in A}$),
  • Или же ${ Displaystyle х = [и, v]}$ с ${ displaystyle u in H}$ и ${ displaystyle v in H}$ и ${ displaystyle v leq y}$.
• Коммутаторы можно заказывать произвольно при условии, что ${ Displaystyle у <[х, у]}$ всегда держит.

Конструкция и обозначения, используемые ниже, почти идентичны тем, которые используются в процесс сбора коммутатора, и поэтому можно напрямую сравнивать; веса - это длины строк. Разница в том, что упоминания групп не требуется. Все эти определения совпадают с определениями X. Вьенно.^[4] Обратите внимание, что некоторые авторы меняют порядок неравенства. Отметим также, что одно из условий - ${ displaystyle v leq y}$, может ощущаться «назад»; именно эта «отсталость» обеспечивает порядок убывания, необходимый для факторизации. Устранение неравенства делает нет переломить эту «отсталость».

Пример

Рассмотрим генераторную установку с двумя элементами ${ displaystyle {a, b }.}$ Определять ${ displaystyle a> b}$ и писать ${ displaystyle xy}$ за ${ Displaystyle [х, у]}$ для упрощения записи используйте круглые скобки только по мере необходимости. Начальные члены набора Холла затем (по порядку)

${ Displaystyle { begin {align} & b, a, & ab, & (ab) b, ; ; (ab) a, & ((ab) b) b, ; ; ( (ab) b) a, ; ; ((ab) a) a, & (((ab) b) b) b, ; (((ab) b) b) a, ; (( (ab) b) a) a, ; (((ab) a) a) a, ; ((ab) b) (ab), ; ((ab) a) (ab), & cdots end {выровнены}}}$

Обратите внимание, что есть ${ Displaystyle 2,1,2,3,6, ldots}$ элементы каждой отдельной длины. Это начальная последовательность полинома ожерелья из двух элементов (описана ниже).

Комбинаторика

Основной результат состоит в том, что количество элементов длины ${ displaystyle k}$ в зале набор (более ${ displaystyle n}$ генераторы) задается колье полином

${ Displaystyle M_ {n} (к) = {1 над k} сумма _ {d , | , k} mu ! left ({k over d} right) n ^ { d} = {1 over k} sum _ {d , | , k} mu ! left ({d} right) n ^ {k / d}}$

куда ${ displaystyle mu}$ это классика Функция Мёбиуса. Сумма составляет Свертка Дирихле.

Определения и леммы.

Полезны некоторые основные определения. Учитывая дерево ${ Displaystyle т = [х, у]}$, элемент ${ displaystyle x}$ называется непосредственное левое поддерево, и аналогично, ${ displaystyle y}$ это немедленное правое поддерево. А правое поддерево либо ${ displaystyle y}$ само, или правое поддерево любого ${ displaystyle x}$ или же ${ displaystyle y}$. Это в отличие от крайнее правое поддерево, который либо ${ displaystyle y}$ сам или крайнее правое поддерево ${ displaystyle y}$.

Основная лемма состоит в том, что если ${ displaystyle v}$ является правым поддеревом дерева Холла ${ Displaystyle т = [х, у]}$, тогда ${ displaystyle v leq y.}$

Слова зала

Слова зала получаются из множества Холла, «забывая» о скобках коммутатора, но в остальном сохраняя понятие полного порядка. Оказывается, это «забывание» безвредно, так как соответствующее дерево Холла может быть выведено из слова, и оно уникально. То есть слова Холла находятся во взаимно однозначном соответствии с деревьями Холла. Общий порядок на деревьях Холла переходит в общий порядок на словах Холла.

Это соответствие позволяет моноидная факторизация: Учитывая свободный моноид ${ displaystyle A ^ {*}}$, любой элемент ${ displaystyle A ^ {*}}$ можно однозначно разложить на восходящую последовательность холловских слов. Это аналогично и обобщает более известный случай факторизации с Слова Линдона предоставленный Теорема Чена – Фокса – Линдона..

Точнее каждое слово ${ Displaystyle ш в А ^ {*}}$ можно записать как конкатенацию слов Холла

${ displaystyle w = h_ {1} h_ {2} cdots h_ {k}}$

с каждым словом Холла ${ displaystyle h_ {j}}$ полностью заказывается Заказчиком Зала:

${ displaystyle h_ {1} leq h_ {2} leq cdots leq h_ {k}.}$

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

Листва

В листва магмы ${ Displaystyle М (А)}$ каноническое отображение ${ displaystyle f: M (A) to A ^ {*}}$ от магмы до свободный моноид ${ displaystyle A ^ {*}}$, данный ${ displaystyle f: a mapsto a}$ за ${ displaystyle a in A}$ и ${ Displaystyle f: [x, y] mapsto f (x) f (y)}$ иначе. Листва - это просто цепочка, состоящая из листьев дерева, то есть взятие дерева, записанное с помощью коммутаторных скобок, и стирание коммутаторных скобок.

Факторизация холловских слов

Позволять ${ displaystyle t = [x, y] in H}$ быть деревом Холла, и ${ Displaystyle ш = е ([х, у])}$ - соответствующее холловское слово. Учитывая любую факторизацию холловского слова ${ displaystyle w = uv}$ на две непустые строки ${ displaystyle u}$ и ${ displaystyle v}$, то существует факторизация в деревья Холла такая, что${ Displaystyle и = е (x_ {1}) cdots f (x_ {m})}$и ${ Displaystyle v = е (y_ {1}) cdots f (y_ {n})}$с

${ displaystyle x_ {1}, ldots, x_ {m}> y_ {1}}$

и

${ displaystyle y_ {1} leq y_ {2} leq cdots leq y_ {n} leq y.}$

Это и последующее развитие ниже дано Ги Мелансоном.^[5]

Переписка

Обратное к приведенной выше факторизации устанавливает соответствие между словами Холла и деревьями Холла. Это можно сформулировать в следующей интересной форме: если ${ displaystyle t}$ дерево Холла, и соответствующее слово Холла ${ displaystyle f (t)}$ факторизуется как

${ Displaystyle е (т) = е (т_ {1}) cdots е (т_ {п})}$

с

${ Displaystyle е (т_ {1}) leq cdots leq f (т_ {п})}$

тогда ${ Displaystyle п = 1}$. Другими словами, слова Холла не можешь быть разложенным на нисходящую последовательность других слов Холла.^[5] Это означает, что по холловскому слову соответствующее дерево может быть однозначно идентифицировано.

Стандартная факторизация

Полный порядок на деревьях Холла переходит в слова Холла. Таким образом, учитывая слово Холла ${ Displaystyle ш = е ([х, у])}$, его можно разложить на множители как ${ Displaystyle ш = е (х) е (у)}$ с ${ Displaystyle е (х)> е (у)}$. Это называется стандартная факторизация.

Стандартная последовательность

А последовательность слов зала ${ Displaystyle (ш_ {1}, ш_ {2}, ldots, ш_ {п})}$ считается стандартная последовательность если каждый ${ displaystyle w_ {i}}$ это либо буква, либо стандартная факторизация ${ displaystyle w_ {i} = u_ {i} v_ {i}}$ с ${ displaystyle v_ {i} leq w_ {i + 1}, cdots, w_ {n}.}$ Обратите внимание, что возрастающие последовательности слов Холла являются стандартными.

Изменение срока

Уникальная факторизация любого слова ${ Displaystyle ш в А ^ {*}}$ в конкатенацию восходящей последовательности слов Холла ${ displaystyle w = h_ {1} h_ {2} cdots h_ {k}}$с ${ displaystyle h_ {1} leq h_ {2} leq cdots leq h_ {k}}$ может быть достигнуто путем определения и рекурсивного применения простого система переписывания терминов. Единственность факторизации следует из слияние свойства системы.^[5] Переписывание выполняется путем обмена определенными парами последовательных слов Холла в последовательности; он приводится после этих определений.

А уронить в последовательности ${ displaystyle (h_ {1}, h_ {2}, ldots, h_ {n})}$ слов Холла пара ${ Displaystyle (ч_ {я}, ч_ {я + 1})}$ такой, что ${ displaystyle h_ {i}> h_ {i + 1}.}$ Если последовательность является стандартной, то капля называется законное падение если есть это ${ displaystyle h_ {i + 1} leq h_ {i + 2}, ldots, h_ {n}.}$

Учитывая стандартную последовательность с допустимым падением, существуют два различных правила перезаписи, которые создают новые стандартные последовательности. Один соединяет два слова в капле:

${ displaystyle (h_ {1}, h_ {2}, ldots, h_ {n}) to (h_ {1}, h_ {2}, ldots, h_ {i} h_ {i + 1}, ldots, h_ {n})}$

в то время как другой переставляет два элемента в капле:

${ displaystyle (h_ {1}, h_ {2}, ldots, h_ {n}) to (h_ {1}, h_ {2}, ldots, h_ {i-1}, h_ {i + 1) }, h_ {i}, h_ {i + 2}, ldots, h_ {n})}$

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

Общий заказ

Полный порядок может быть предоставлен по словам ${ displaystyle w in A ^ {*}.}$ Это похоже на стандартный лексикографический порядок, но на уровне холловских слов. Учитывая два слова ${ displaystyle u, v}$ с учетом восходящего порядка слов Холла, я. е. который

${ displaystyle u = u_ {1} u_ {2} cdots u_ {m} quad}$ и ${ Displaystyle quad v = v_ {1} v_ {2} cdots v_ {n}}$

с каждым ${ displaystyle u_ {i}, v_ {j}}$ слово Холла, есть порядок, который ${ Displaystyle и$ если либо

${ Displaystyle м <п квад}$ и ${ displaystyle quad u_ {1} = v_ {1}, , u_ {2} = v_ {2}, , cdots, u_ {m} = v_ {m}}$

или если

${ displaystyle u_ {1} = v_ {1}, , u_ {2} = v_ {2}, , ldots, u_ {k} = v_ {k} quad}$ и ${ displaystyle quad u_ {k + 1}$

Характеристики

Слова Холла обладают рядом любопытных свойств, многие из которых почти идентичны таковым для Слова Линдона. Первое и наиболее важное свойство состоит в том, что слова Линдона являются частным случаем холловских слов. То есть определение слова Линдона удовлетворяет определению слова Холла. Это легко проверить прямым сравнением; обратите внимание, что направление неравенства, используемое в определениях выше, в точности противоположно тому, которое используется в обычном определении слов Линдона. Множество деревьев Линдона (которые следуют из стандартной факторизации) является множеством Холла.

Другие свойства включают:

• Слова зала ациклический он же примитивный. То есть их нельзя записать в виде ${ Displaystyle ш = х ^ {п}}$ для некоторого слова ${ displaystyle x in A ^ {*}}$ и ${ displaystyle n> 1}$.
• Каждое примитивное слово ${ Displaystyle ш в А ^ {*}}$ является сопрягать к слову Холла. То есть существует круговой сдвиг из ${ displaystyle w}$ это холловское слово. Эквивалентно существует факторизация ${ displaystyle w = uv}$ такой, что ${ displaystyle vu}$ это холловское слово. Этот конъюгат уникален.
• Слово ${ Displaystyle ш в А ^ {*}}$ является холловским словом тогда и только тогда, когда для любой факторизации ${ displaystyle w = uv}$ на непустые слова подчиняется ${ displaystyle w> vu}$. (Заметим еще раз, это точно так же, как и для слова Линдона; слова Линдона являются наименьшими в своем классе сопряженности, и мы работаем с соглашением о неравенстве, которое является обратным по сравнению с неравенством слов Линдона.)
• Слово ${ Displaystyle ш в А ^ {*}}$ является холловским словом тогда и только тогда, когда оно больше любого из своих правильных множителей.
• Каждое слово ${ Displaystyle ш в А ^ {*}}$ является спряжением мощности уникального холловского слова.

Подразумеваемое

Существует аналогичная система переписывания терминов для Слова Линдона, вот как факторизация моноида выполняется словами Линдона.

Поскольку слова Холла могут быть помещены в деревья Холла, и каждое дерево Холла можно интерпретировать как коммутатор, термин перезапись может использоваться для выполнения процесс сбора коммутатора на группу.

Еще одно очень важное применение правила перезаписи - выполнение коммутаций, которые появляются в Теорема Пуанкаре – Биркгофа – Витта.. Подробное обсуждение коммутации можно найти в статье о универсальные обертывающие алгебры. Обратите внимание, что переписывание термов словами Линдона также может быть использовано для получения необходимой коммутации для теоремы PBW.^[6]

История

Наборы Холла были представлены Маршалл Холл на основе работы Филип Холл по группам.^[3] Впоследствии Вильгельм Магнус показали, что они возникают как градуированная алгебра Ли связанный с фильтрацией на свободная группа предоставленный нижний центральный ряд. Эта переписка была мотивирована коммутатор идентичности в теория групп благодаря Филиппу Холлу и Эрнст Витт.

Смотрите также

• Идентичность Холла – Петреско
• Марковский одометр

Рекомендации