В математике , в области теории групп и комбинаторики , зал слова обеспечивают уникальную моноидное факторизации в свободной моноиде . Они также полностью упорядочены и, таким образом, обеспечивают полный порядок на моноиде. Это аналог более известного случая слов Линдона ; на самом деле слова Линдона - это особый случай, и почти все свойства, которыми обладают слова Линдона, переносятся на слова Холла. Слова Холла находятся во взаимно однозначном соответствии с деревьями Холла . Это бинарные деревья ; вместе они образуют комплекс Холла . Этот набор является особеннымполностью упорядоченное подмножество свободной неассоциативной алгебры, то есть свободной магмы . В этой форме деревья Холла обеспечивают основу для свободных алгебр Ли и могут использоваться для выполнения коммутаций, требуемых теоремой Пуанкаре – Биркгофа – Витта, используемой при построении универсальной обертывающей алгебры . Таким образом, это обобщает тот же процесс, когда делается со словами Линдона. Деревья Холла также можно использовать для упорядочивания элементов группы с помощью процесса сбора коммутаторов , который является частным случаем общей конструкции, приведенной ниже. Можно показать, что множества Лазара совпадают с множествами Холла.
Историческое развитие идет в порядке, обратном приведенному выше описанию. Процесс сбора коммутатора был впервые описан в 1934 году Филипом Холлом и исследован в 1937 году Вильгельмом Магнусом . [1] [2] Наборы Холла были введены Маршаллом Холлом на основе работы Филипа Холла о группах. [3] Впоследствии Вильгельм Магнус показал, что они возникают как градуированная алгебра Ли, связанная с фильтрацией на свободной группе, заданной нижним центральным рядом . Это соответствие было мотивировано коммутаторными тождествами в теории групп Филипа Холла и Эрнста Витта .
Набор для прихожей
Множество Hall является вполне упорядоченным подмножеством свободной неассоциативной алгебры, то есть свободная магма . Позволять - набор образующих, и пусть быть свободной магмой . Свободная магма - это просто набор неассоциативных струн в буквах, с сохранением круглых скобок, чтобы показать группировку. Эквивалентно свободная магма - это совокупность всех бинарных деревьев , листья которых являются элементами.
Набор Холла можно построить рекурсивно следующим образом:
- Элементы дается произвольный общий порядок.
- В комплект Холла входят генераторы:
- Коммутатор если и только если а также а также а также:
- Либо (и поэтому ),
- Или же с участием а также а также .
- Коммутаторы можно заказывать произвольно, при условии, что всегда держит.
Конструкция и обозначения, используемые ниже, почти идентичны тем, которые используются в процессе сбора коммутатора , и поэтому их можно напрямую сравнить; веса - это длины строк. Разница в том, что упоминания групп не требуется. Все эти определения совпадают с определениями X. Вьенно. [4] Обратите внимание, что некоторые авторы меняют порядок неравенства. Отметим также, что одно из условий -, может казаться «задом наперед»; именно эта «отсталость» обеспечивает порядок убывания, необходимый для факторизации. Реверсивное неравенство вовсе не обратить вспять эту «отсталость».
Пример
Рассмотрим генераторную установку с двумя элементами Определять и писать для для упрощения записи используйте круглые скобки только по мере необходимости. Затем начальные члены набора Холла (по порядку)
Обратите внимание, что есть элементы каждой отдельной длины. Это начальная последовательность полинома ожерелья из двух элементов (описана ниже).
Комбинаторика
Основной результат состоит в том, что количество элементов длины в зале набор (более генераторы) задается полиномом ожерелья
где - классическая функция Мёбиуса . Сумма представляет собой свертку Дирихле .
Определения и леммы.
Полезны некоторые основные определения. Учитывая дерево, элемент называется непосредственным левым поддеревом , и аналогично,это непосредственное правое поддерево . Правое поддерево либо само по себе, либо правое поддерево одного из или же . Это контрастирует с крайним правым поддеревом , которое либо само, или крайнее правое поддерево .
Основная лемма состоит в том, что если является правым поддеревом дерева Холла , тогда
Слова зала
Слова Холла получаются из набора Холла, «забывая» о скобках коммутатора, но в остальном сохраняя понятие полного порядка. Оказывается, это «забывание» безвредно, поскольку соответствующее дерево Холла может быть выведено из слова, и оно уникально. То есть слова Холла находятся во взаимно однозначном соответствии с деревьями Холла. Полный порядок на деревьях Холла переходит в общий порядок на словах Холла.
Это соответствие допускает факторизацию моноида : учитывая свободный моноид , любой элемент можно однозначно разложить на восходящую последовательность холловских слов. Это аналогично и обобщает более известный случай факторизации слов Линдона, предоставляемый теоремой Чена – Фокса – Линдона .
Точнее каждое слово можно записать как конкатенацию слов Холла
с каждым словом Холла полностью заказывается Заказчиком Зала:
Таким образом, порядок слов Холла расширяется до полного порядка на моноиде. Леммы и теоремы, необходимые для обеспечения соответствия между словом и деревом и уникального упорядочивания, кратко описаны ниже.
Листва
Листву из магмы каноническое отображение от магмы к свободному моноиду , данный для а также иначе. Листва - это просто строка, состоящая из листьев дерева, то есть взятие дерева, записанное с помощью коммутаторных скобок, и стирание коммутаторных скобок.
Факторизация холловских слов
Позволять быть деревом Холла, и - соответствующее холловское слово. Учитывая любую факторизацию холловского слова на две непустые строки а также , то существует факторизация по деревьям Холла такая, что а также с участием
а также
Это и последующее развитие ниже дано Ги Мелансоном. [5]
Переписка
Обратное к приведенной выше факторизации устанавливает соответствие между словами Холла и деревьями Холла. Это можно сформулировать в следующей интересной форме: если дерево Холла, и соответствующее слово Холла факторизуется как
с участием
тогда . Другими словами, слова Холла нельзя разложить на нисходящую последовательность других слов Холла. [5] Это означает, что по холловскому слову соответствующее дерево может быть однозначно идентифицировано.
Стандартная факторизация
Полный порядок на деревьях Холла переходит в слова Холла. Таким образом, учитывая слово Холла, его можно разложить на множители как с участием . Это называется стандартной факторизацией .
Стандартная последовательность
Последовательность холловских словназывается стандартной последовательностью, если каждый это либо буква, либо стандартная факторизация с участием Обратите внимание, что возрастающие последовательности слов Холла являются стандартными.
Изменение срока
Уникальная факторизация любого слова в конкатенацию восходящей последовательности слов Холла с участием может быть достигнуто путем определения и рекурсивного применения простой системы переписывания терминов . Уникальность факторизации следует из впадения свойств системы. [5] Перезапись выполняется путем обмена определенными парами последовательных слов Холла в последовательности; он приводится после этих определений.
Капля в последовательности слов Холла пара такой, что Если последовательность является стандартной последовательностью, то сброс называется законным, если он также имеет
Учитывая стандартную последовательность с допустимым падением, есть два различных правила перезаписи, которые создают новые стандартные последовательности. Один соединяет два слова в капле:
в то время как другой переставляет два элемента в капле:
Нетрудно показать, что обе перезаписи приводят к новой стандартной последовательности. Как правило, удобнее всего применять перезапись к самому правому разрешенному падению; тем не менее, можно показать, что перезапись является конфлюэнтной, и поэтому можно получить одни и те же результаты независимо от порядка.
Общий заказ
Полный порядок может быть предоставлен по словам Это похоже на стандартный лексикографический порядок , но на уровне холловских слов. Учитывая два словаучитываются в восходящей Холла порядок слов, то есть что
- а также
с каждым слово Холла, есть порядок, который если либо
- а также
или если
- а также
Характеристики
Слова Холла обладают рядом любопытных свойств, многие из которых почти идентичны словам Линдона . Первое и наиболее важное свойство состоит в том, что слова Линдона являются частным случаем холловских слов. То есть определение слова Линдона удовлетворяет определению слова Холла. Это легко проверить прямым сравнением; обратите внимание, что направление неравенства, используемое в определениях выше, в точности противоположно тому, которое используется в обычном определении слов Линдона. Множество деревьев Линдона (которые следуют из стандартной факторизации) является множеством Холла.
Другие свойства включают:
- Слова Холла ациклические, иначе говоря, примитивные . То есть их нельзя записать в виде для некоторого слова а также .
- Каждое примитивное слово является сопряженным к слову Холла. То есть, существует циклический сдвиг вэто слово Холла. Эквивалентно существует факторизация такой, что это холловское слово. Этот конъюгат уникален.
- Слово является холловским словом тогда и только тогда, когда для любой факторизации на непустые слова подчиняется . (Заметим еще раз, это точно так же, как и для слова Линдона; слова Линдона являются наименьшими из своего класса сопряженности, и мы работаем с соглашением о неравенстве, которое является обратным по сравнению с неравенством слов Линдона.)
- Слово является холловским словом тогда и только тогда, когда оно больше любого из своих правильных множителей.
- Каждое слово является спряжением мощности уникального холловского слова.
Подразумеваемое
Для слов Линдона существует аналогичная система переписывания терминов , так факторизация моноида осуществляется с помощью слов Линдона.
Поскольку слова Холла могут быть помещены в деревья Холла, и каждое дерево Холла можно интерпретировать как коммутатор, термин перезапись может использоваться для выполнения процесса сбора коммутатора в группе.
Еще одно очень важное применение правила перезаписи - выполнение коммутаций, которые появляются в теореме Пуанкаре – Биркгофа – Витта . Подробное обсуждение коммутации содержится в статье об универсальных обертывающих алгебрах . Обратите внимание, что переписывание термов словами Линдона также может использоваться для получения необходимой коммутации для теоремы PBW. [6]
История
Наборы Холла были представлены Маршаллом Холлом на основе работы Филипа Холла над группами. [3] Впоследствии Вильгельм Магнус показал, что они возникают как градуированная алгебра Ли, связанная с фильтрацией на свободной группе, заданной нижним центральным рядом . Это соответствие было мотивировано коммутаторными тождествами в теории групп Филипа Холла и Эрнста Витта .
Смотрите также
- Идентичность Холла – Петреско
- Марковский одометр
Рекомендации
- ^ Hall, Филипп (1934), "Вклад в теорию групп порядка прайм-силы", Труды Лондонского математического общества , 36 : 29-95, DOI : 10.1112 / ПНИЛИ / s2-36.1.29
- ^ В. Магнус, (1937) "Über Beziehungen zwischen höheren Kommutatoren", J. Grelle 177 , 105-115.
- ^ а б Холл, Маршалл (1950), «Основа для свободных колец Ли и высших коммутаторов в свободных группах» , Труды Американского математического общества , 1 (5): 575-581, DOI : 10,1090 / S0002-9939-1950-0038336- 7 , ISSN 0002-9939 , MR 0038336
- ^ X. Виеннот, (1978) «Свободные лиги и моноиды свободных», конспекты лекций по математике , 691 , Springer – Verlag
- ^ a b c Гай Мелансон, (1992) « Комбинаторика холловских деревьев и холловских слов », Журнал комбинаторной теории , 59A (2) стр. 285–308.
- ^ Г Melancon и С. Reutenauer (1989), «Линдон слово, свободные алгебры и перемешивает», Canadian Journal математики . 41 , No. 4, pp. 577-591.