Слово Холла

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

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

обозначения Предварительные

Местом действия этой статьи является свободная магма в $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,y]\in H$ если и только если $x\in H$ $x\in H$ и $y\in H$ $y\in H$ и $x>y$ $x>y$ и:
- Или $x\in A$ (и поэтому $y\in A$ ),
- Или $x=[u,v]$ с $u\in H$ и $v\in H$ и $v\leq y$ .
Коммутаторы можно располагать произвольно, при условии, что $y<[x,y]$ всегда держит.

Конструкция и обозначения, используемые ниже, почти идентичны тем, которые используются в процессе сбора данных коммутатора , и поэтому их можно напрямую сравнивать; веса - это длины строк. Отличие в том, что упоминания о группах не требуется. Все эти определения совпадают с определениями X. Вьенно. ^[4]Обратите внимание, что некоторые авторы меняют порядок неравенства. Отметим также, что одно из условий – $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.

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

Переписка [ править ]

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

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

с

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

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

Стандартная факторизация [ править ]

Общий порядок на деревьях Холла переходит к словам Холла. Таким образом, учитывая слово Холла $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}$ Это может быть достигнуто путем определения и рекурсивного применения простой системы переписывания терминов . Единственность факторизации следует из свойств конфлюэнтности системы. ^[5]Перезапись осуществляется путем замены определенных пар последовательных слов Холла в последовательности; оно дается после этих определений.

Падение в последовательности $(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. ^[6]

История [ править ]

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

См. также [ править ]

Ссылки [ править ]

^ Холл, Филип (1934), «Вклад в теорию групп простого порядка», Труды Лондонского математического общества , 36 : 29–95, doi : 10.1112/plms/s2-36.1.29
^ В. Магнус, (1937) «Об отношениях между высшими коммутаторами», Ж. Грелль 177 , 105–115.
^ Перейти обратно: ^а ^б Холл, Маршалл (1950), «Основы свободных колец Ли и высших коммутаторов в свободных группах» , Proceedings of the American Mathematical Society , 1 (5): 575–581, doi : 10.1090/S0002-9939-1950-0038336- 7 , ISSN 0002-9939 , МР 0038336
^ X. Вьеннот, (1978) «Свободные алгебры Ли и свободные моноиды», Конспект лекций по математике , 691 , Springer – Verlag
^ Перейти обратно: ^а ^б ^с Ги Мелансон, (1992) « Комбинаторика деревьев Холла и слов Холла », Журнал комбинаторной теории , 59A (2), стр. 285–308.
^ Гай Мелансон и К. Ройтенауэр (1989), «Слова Линдона, свободные алгебры и перетасовки», Канадский журнал математики . 41 , № 4, стр. 577-591.

[1] Холл, Филип (1934), «Вклад в теорию групп простого порядка», Труды Лондонского математического общества , 36 : 29–95, doi : 10.1112/plms/s2-36.1.29

[2] В. Магнус, (1937) «Об отношениях между высшими коммутаторами», Ж. Грелль 177 , 105–115.

[mhall-3] Перейти обратно: ^а ^б Холл, Маршалл (1950), «Основы свободных колец Ли и высших коммутаторов в свободных группах» , Proceedings of the American Mathematical Society , 1 (5): 575–581, doi : 10.1090/S0002-9939-1950-0038336- 7 , ISSN 0002-9939 , МР 0038336

[4] X. Вьеннот, (1978) «Свободные алгебры Ли и свободные моноиды», Конспект лекций по математике , 691 , Springer – Verlag

[melancon-5] Перейти обратно: ^а ^б ^с Ги Мелансон, (1992) « Комбинаторика деревьев Холла и слов Холла », Журнал комбинаторной теории , 59A (2), стр. 285–308.

[6] Гай Мелансон и К. Ройтенауэр (1989), «Слова Линдона, свободные алгебры и перетасовки», Канадский журнал математики . 41 , № 4, стр. 577-591.

[1]

[2]

[3]

[4]

[5]

[6]

обозначения Предварительные ​ ​