Слово Холла

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

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

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

Местом действия этой статьи является свободная магма в $n$ генераторы. Это просто набор, содержащий $n$ элементы вместе с бинарным оператором $\bullet$ это позволяет сопоставлять любые два элемента рядом друг с другом. Сопоставление считается неассоциативным и некоммутативным , поэтому при сопоставлении трех и более элементов обязательно нужно использовать скобки. Так, например, $(a\bullet b)\bullet c$ это не то же самое, что $a\bullet (b\bullet c)$.

Таким образом, оператор магмы $\bullet$ обеспечивает удобную замену любому другому желаемому бинарному оператору, который может иметь дополнительные свойства, такие как групповые или алгебраические коммутаторы. Так, например, сопоставление магмы можно отобразить в коммутатор некоммутативной алгебры:

$a\bullet b\mapsto [a,b]=ab-ba$

или к групповому коммутатору:

$a\bullet b\mapsto aba^{-1}b^{-1}$

Два вышеупомянутых отображения являются просто гомоморфизмами магмы в общепринятом смысле гомоморфизма ; объекты справа просто имеют большую структуру, чем магма. Чтобы избежать неловкой типографской путаницы, которая $\bullet$, принято просто писать $ab$ для $(a\bullet b)$. Однако использование круглых скобок является обязательным, поскольку $(ab)c\neq a(bc)$ как уже отмечалось. Если $a$ является составным объектом, иногда можно написать $(a)$ при необходимости, чтобы устранить неоднозначность использования. Конечно, можно также написать $[a,b]$ вместо $ab$, но это может привести к увеличению количества квадратных скобок и запятых. Имея это в виду, в противном случае можно быть гибким в обозначениях.

Набор для зала

— Множество Холла это полностью упорядоченное подмножество свободной неассоциативной алгебры, то есть свободной магмы . Позволять $A={a_{1},\ldots ,a_{n}}$ — набор образующих, и пусть $M(A)$ будь свободной магмой $A$. Свободная магма — это просто набор неассоциативных строк в буквах $A$, с сохранением скобок для обозначения группировки. Круглые скобки можно записать в квадратных скобках, чтобы элементы свободной магмы можно было рассматривать как формальные коммутаторы. Эквивалентно, свободная магма — это совокупность всех бинарных деревьев с листьями, отмеченными элементами $A$.

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

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

Конструкция и обозначения, используемые ниже, почти идентичны тем, которые используются в процессе сбора данных коммутатора , и поэтому их можно напрямую сравнивать; веса - это длины строк. Отличие в том, что упоминания о группах не требуется. Все эти определения совпадают с определениями Х. Вьенно. Обратите внимание, что некоторые авторы меняют порядок неравенства. Отметим также, что одно из условий – $v\leq y$, может чувствовать себя «назад»; именно эта «отсталость» обеспечивает порядок убывания, необходимый для факторизации. Изменение неравенства не устраняет эту «отсталость».

Пример

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

${\begin{aligned}&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{aligned}}$

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

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

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

$M_{n}(k)\ =\ {1 \over k}\sum _{d\,|\,k}\mu \!\left({k \over d}\right)n^{d}={1 \over k}\sum _{d\,|\,k}\mu \!\left({d}\right)n^{k/d}$

где $\mu$ — классическая функция Мёбиуса . Сумма представляет собой свертку Дирихле .

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

Некоторые основные определения полезны. Учитывая дерево $t=[x,y]$, элемент $x$ называется непосредственным левым поддеревом и аналогично $y$ является непосредственным правым поддеревом . — Правое поддерево это либо $y$ само себя или правое поддерево любого из $x$ или $y$. Крайнее правое поддерево — это либо $y$ само по себе или крайнее правое поддерево $y$.

Основная лемма состоит в том, что если $v$ является правым поддеревом дерева Холла $t=[x,y]$, затем $v\leq y.$

Слова Холла

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

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

Точнее, каждое слово $w\in A^{*}$ можно записать как конкатенацию слов Холла

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

с каждым словом Холла $h_{j}$ будучи полностью заказанным Залом, приказав:

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

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

Листва

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

Холла

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

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

и

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

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

Переписка

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

$f(t)=f(t_{1})\cdots f(t_{n})$

с

$f(t_{1})\leq \cdots \leq f(t_{n})$

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

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

Общий порядок на деревьях Холла переходит к словам Холла. Таким образом, учитывая слово Холла $w=f([x,y])$, его можно факторизовать как $w=f(x)f(y)$ с $f(x)>f(y)$. Это называется стандартной факторизацией .

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

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

Переписывание термина

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

Падение в последовательности $(h_{1},h_{2},\ldots ,h_{n})$ слов Холла — это пара $(h_{i},h_{i+1})$ такой, что $h_{i}>h_{i+1}.$ Если последовательность является стандартной последовательностью, то удаление называется допустимым, если у него также есть такая последовательность. $h_{i+1}\leq h_{i+2},\ldots ,h_{n}.$

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

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

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

$(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})$

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

Общий заказ

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

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

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

$m<n\quad$ и $\quad u_{1}=v_{1},\,u_{2}=v_{2},\,\cdots ,u_{m}=v_{m}$

или если

$u_{1}=v_{1},\,u_{2}=v_{2},\,\ldots ,u_{k}=v_{k}\quad$ и $\quad u_{k+1}<v_{k+1}.$

Свойства

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

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

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

Последствия

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

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

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

История

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

См. также

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