ホールワード

数学の群論と組合せ論の分野において、ホール語は自由モノイドの一意のモノイド因数分解を提供する。また、ホール語は全順序付けされているため、モノイドに全順序付けを提供する。これは、よりよく知られているリンドン語の場合に類似している。実際、リンドン語は特殊なケースであり、リンドン語が持つほぼすべての特性がホール語にも引き継がれる。ホール語はホール木と 1 対 1 に対応している。これらは二分木であり、まとめてホール集合を​​形成する。この集合は自由非結合代数、すなわち自由マグマの特定の全順序付けされた部分集合である。この形式では、ホール木は自由リー代数の基礎を提供し、普遍包絡代数の構築に使用されるポアンカレ-バーコフ-ウィットの定理で必要な交換を実行するために使用できる。このように、これはリンドン語を用いた場合の同じプロセスを一般化します。ホール木は、交換子収集プロセスを介して群の元に全順序を与えるためにも使用できます。これは、以下に示す一般的な構成の特別な場合です。ラザード集合はホール集合と一致することが示されます。

歴史的発展は上記の記述とは逆の順序で進む。交換子集合過程は1934年にフィリップ・ホールによって初めて記述され、1937年にヴィルヘルム・マグヌスによって研究された。^{[1] [2]}ホール集合は、フィリップ・ホールの群に関する研究に基づき、マーシャル・ホールによって導入された。 ^[3] その後、ヴィルヘルム・マグヌスは、ホール集合が下中心級数によって与えられる自由群上の濾過に関連する次数付きリー代数として生じることを示した。この対応は、フィリップ・ホールとエルンスト・ウィットによる群論における交換子恒等式に触発されたものである。

表記法の準備

この記事の舞台は、ジェネレータにおける自由マグマです。これは、任意の2つの要素を隣り合わせに並べることを可能にする二項演算子と、要素を含む単純な集合です。この並べ方は非結合的かつ非可換的であるとみなされるため、3つ以上の要素を並べる場合は必ず括弧を使用する必要があります。したがって、例えば、はと同じではありません。 ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \bullet }$ ${\displaystyle (a\bullet b)\bullet c}$ ${\displaystyle a\bullet (b\bullet c)}$

このように、マグマ演算子は、群交換子や代数交換子といった追加の特性を持つ可能性のある他の任意の二項演算子の便利な代替手段を提供します。したがって、例えば、マグマの並置は非可換代数の交換子にマッピングできます。 ${\displaystyle \bullet }$

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

またはグループ交換子に:

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

上記の 2 つの写像は、準同型の従来の意味でのマグマ準同型です。右側のオブジェクトはたまたまマグマよりも構造が複雑になっています。 という厄介な印刷上の混乱を避けるために、 については とだけ書くのが慣例です。ただし、既に述べたように、括弧の使用は必須です。が複合オブジェクトである場合は、用法の曖昧さをなくすために、必要に応じて と書くこともあります。もちろん、の代わりに と書くこともできますが、そうすると角括弧やカンマが大量に使用できるようになります。これを念頭に置いておけば、表記法は柔軟にできます。 ${\displaystyle \bullet }$ ${\displaystyle ab}$ ${\displaystyle (a\bullet b)}$ ${\displaystyle (ab)c\neq a(bc)}$ ${\displaystyle a}$ ${\displaystyle (a)}$ ${\displaystyle [a,b]}$ ${\displaystyle ab}$

ホールセット

ホール集合は自由非結合的代数の全順序部分集合、すなわち自由マグマである。を生成元の集合とし、を 上の自由マグマとする。自由マグマは の文字に含まれる非結合的文字列の集合に過ぎず、グループ化を示すために括弧は保持される。括弧は角括弧で囲むこともできる。その場合、自由マグマの要素は形式的な交換子とみなすことができる。同様に、自由マグマはの要素でマークされた葉を持つすべての二分木の集合である。 ${\displaystyle A=\{a_{1},\ldots ,a_{n}\}}$ ${\displaystyle M(A)}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$

ホール集合は、次のように再帰的に（昇順に）構築できます。 ${\displaystyle H\subseteq M(A)}$

• の要素には任意の全順序が与えられます。${\displaystyle A}$
• ホールセットには次のジェネレータが含まれます。${\displaystyle A\subseteq 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 x=[u,v]}$ ${\displaystyle u\in H}$ ${\displaystyle v\in H}$ ${\displaystyle v\leq y}$
• 常に成立する限り、交換子は任意に順序付けることができます。${\displaystyle y<[x,y]}$

以下で用いる構成と表記法は、交換子集合過程で用いられるものとほぼ同一であり、直接比較することができる。重みは文字列の長さである。違いは、群について言及する必要がないことである。これらの定義はすべて、X. Viennot の定義と一致する。^[4] 一部の著者は不等式の順序を逆にしている点に注意されたい。また、条件の1つである は「逆」に感じられるかもしれないことにも注意されたい。この「逆」こそが、因数分解に必要な降順を与えるものである。不等式を逆にしても、この「逆」は逆にならない。 ${\displaystyle v\leq y}$

例

2つの要素を持つ生成集合を考える。記法を簡略化するために、必要に応じて括弧を用いて定義し、記述する。ホール集合の初期要素は（順番に） ${\displaystyle \{a,b\}.}$ ${\displaystyle a>b}$ ${\displaystyle xy}$ ${\displaystyle [x,y]}$

${\displaystyle {\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つの元を持つネックレス多項式の最初の数列です（後述）。 ${\displaystyle 2,1,2,3,6,\ldots }$

組合せ論

基本的な結果は、ホール集合（生成元全体）の長さの要素の数はネックレス多項式で与えられるということである。${\displaystyle k}$ ${\displaystyle n}$

${\displaystyle 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}}$

ここでは典型的なメビウス関数です。和はディリクレ畳み込みです。 ${\displaystyle \mu }$

定義と補題

いくつかの基本的な定義は役に立ちます。木 が与えられたとき、要素 は直近の左部分木と呼ばれ、同様に は直近の右部分木と呼ばれます。右部分木とは、それ自体、またはもしくは の右部分木のいずれかです。極右部分木とは、それ自体、または の極右部分木のいずれかです。 ${\displaystyle t=[x,y]}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle y}$

基本的な補題は、 がホール木 の右部分木である場合、${\displaystyle v}$ ${\displaystyle t=[x,y]}$ ${\displaystyle v\leq y.}$

ホールの言葉

ホール語は、ホール集合から交換子括弧を「忘れる」ことで得られるが、それ以外は全順序の概念は維持される。この「忘れる」ことは無害であることが判明している。なぜなら、対応するホール木は語から演繹でき、かつそれは一意だからである。つまり、ホール語はホール木と一対一に対応する。ホール木の全順序は、ホール語の全順序へと継承される。

この対応によりモノイド因数分解が可能となる。自由モノイド が与えられれば、 の任意の元はホール語の昇順列に一意に因数分解できる。これは、チェン・フォックス・リンドン定理によって提供される、リンドン語による因数分解のよりよく知られたケースに類似しており、それを一般化したものである。 ${\displaystyle A^{*}}$ ${\displaystyle A^{*}}$

より正確には、すべての単語はホールワードの連結として表すことができる。 ${\displaystyle w\in A^{*}}$

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

各ホール単語はホール順序によって完全に順序付けられます。 ${\displaystyle h_{j}}$

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

このように、ホール語順はモノイド上の全順序に拡張されます。語と木との対応、そして一意な順序付けを与えるために必要な補題と定理を以下に概説します。

葉

マグマの葉は、マグマから自由モノイドへの標準的な写像であり、 に対しては 、それ以外の場合には で与えられます。葉は、木の葉からなる文字列、つまり、交換子括弧で書かれた木から交換子括弧を消したものに相当します。 ${\displaystyle M(A)}$ ${\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)}$

ホール語の因数分解

をホール木とし、対応するホール語とする。ホール語を2つの空でない文字列とに分解すると、次の 式を 満たす ホール木への分解が存在する。 ${\displaystyle t=[x,y]\in H}$ ${\displaystyle w=f([x,y])}$ ${\displaystyle w=uv}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u=f(x_{1})\cdots f(x_{m})}$ ${\displaystyle v=f(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 f(t)=f(t_{1})\cdots f(t_{n})}$

と

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

言い換えれば、ホール語は他のホール語の降順の列に因数分解することはできない。 ^[5]これは、ホール語が与えられれば、それに対応する木を一意に識別できることを意味する。 ${\displaystyle n=1}$

標準因数分解

ホール木の全順序はホール語にも引き継がれます。したがって、ホール語 が与えられたとき、 を用いて のように因数分解できます。これは標準因数分解と呼ばれます。 ${\displaystyle w=f([x,y])}$ ${\displaystyle w=f(x)f(y)}$ ${\displaystyle f(x)>f(y)}$

標準シーケンス

ホールワードのシーケンスは、それぞれが文字、または の標準因数分解である場合に標準シーケンスと呼ばれます 。ホールワードの増加シーケンスは標準であることに注意してください 。${\displaystyle (w_{1},w_{2},\ldots ,w_{n})}$ ${\displaystyle w_{i}}$ ${\displaystyle w_{i}=u_{i}v_{i}}$ ${\displaystyle v_{i}\leq w_{i+1},\cdots ,w_{n}.}$

用語の書き換え

任意の単語を、昇順のホール語列の連結に一意 に 分解するには、単純な項書き換えシステムを定義し、再帰的に適用します。この因数分解の一意性は、システムの合流性から導き出されます。 ^[5]書き換えは、連続するホール語の特定のペアをシーケンス内で交換することによって実行されます。これは、これらの定義の後に示されます。 ${\displaystyle w\in A^{*}}$ ${\displaystyle w=h_{1}h_{2}\cdots h_{k}}$ ${\displaystyle h_{1}\leq h_{2}\leq \cdots \leq h_{k}}$

ホールワードのシーケンスにおけるドロップとは、次のペアのことである。シーケンスが標準シーケンスである場合、次の条件も 満たすドロップは合法ドロップと呼ばれる。${\displaystyle (h_{1},h_{2},\ldots ,h_{n})}$ ${\displaystyle (h_{i},h_{i+1})}$ ${\displaystyle h_{i}>h_{i+1}.}$ ${\displaystyle h_{i+1}\leq h_{i+2},\ldots ,h_{n}.}$

正規のドロップを含む標準シーケンスが与えられた場合、新しい標準シーケンスを作成する2つの異なる書き換え規則があります。1つは、ドロップ内の2つの単語を連結するものです。

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

もう 1 つは、ドロップ内の 2 つの要素を並べ替えます。

${\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})}$

どちらの書き換えも新しい標準シーケンスを生成することを示すのは難しくありません。一般的には、書き換えを最も右端の有効なドロップに適用するのが最も便利ですが、書き換えが合流性を持つことが示されており、順序に関わらず同じ結果が得られます。

合計注文

単語には完全な順序を与えることができる。これ は標準的な辞書式順序 に似ているが、ホール語のレベルでの順序である。2つの単語を昇順ホール語順に分解すると、すなわち${\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 u<v}$

${\displaystyle m<n\quad }$ そして${\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}<v_{k+1}.}$

プロパティ

ホール語には多くの興味深い性質があり、その多くはリンドン語のものとほぼ同じです。まず最も重要な性質は、リンドン語がホール語の特殊なケースであるという点です。つまり、リンドン語の定義はホール語の定義を満たします。これは直接比較することで容易に検証できます。上記の定義で使用されている不等式の方向は、リンドン語の通常の定義で使用される不等式の方向と正反対であることに注目してください。リンドン木の集合（標準的な因数分解から得られる）はホール集合です。

その他のプロパティは次のとおりです:

• ホール語は非巡回語であり、原始語とも呼ばれます。つまり、ある語に対して と の形で表記することはできません。${\displaystyle w=x^{n}}$ ${\displaystyle x\in A^{*}}$ ${\displaystyle n>1}$
• 単語がホール語であるためには、を空でない単語に因数分解した際に が成り立つことが必要である。特に、これはホール語が他のホール語の共役ではないことを意味する。繰り返しになるが、これはリンドン語の場合と全く同じである。リンドン語は共役クラスの中で最も小さい語であり、ホール語は最も大きい語である。${\displaystyle w\in A^{*}}$ ${\displaystyle w=uv}$ ${\displaystyle w>vu}$
• 単語がホール語であるのは、その単語がその右辺の因数のいずれよりも大きい場合に限られます。これは前の2つの点から導き出されます。${\displaystyle w\in A^{*}}$
• すべての基本語はホール語と共役である。つまり、の円シフトが存在し、それがホール語となる。同様に、がホール語となるような因数分解も存在する。この共役は唯一である。なぜなら、どのホール語も他のホール語と共役ではないからである。${\displaystyle w\in A^{*}}$ ${\displaystyle w}$ ${\displaystyle w=uv}$ ${\displaystyle vu}$
• すべての単語は、固有のホール語の累乗の共役です。${\displaystyle w\in A^{*}}$

意味合い

Lyndon 語にも同様の項書き換えシステムがあり、これはLyndon 語を使用して モノイドの因数分解を実現する方法です。

ホールワードはホールツリーに配置でき、各ホールツリーは交換子として解釈できるため、書き換えという用語を使用して、グループに対して 交換子収集プロセスを実行できます。

書き換え規則のもう一つの非常に重要な応用は、ポアンカレ・バーコフ・ウィットの定理に現れる交換関係を実行することである。この交換関係の詳細な議論は、普遍包絡代数に関する論文に記載されている。なお、リンドン語を用いた項書き換えは、PBW定理に必要な交換関係を得るためにも使用できる。^[6]

歴史

ホール集合は、フィリップ・ホールの群に関する研究に基づき、マーシャル・ホールによって導入された。^[3]その後、ヴィルヘルム・マグヌスは、ホール集合が、下中心級数によって与えられる自由群上の濾過に付随する次数付きリー代数として現れることを示した。この対応は、フィリップ・ホールとエルンスト・ウィットによる群論における交換子恒等式に触発されたものである。

参照

• ホール・ペトレスコ恒等式
• マルコフオドメーター

参考文献

1. ホール、フィリップ（1934）「素数冪順序群の理論への貢献」ロンドン数学会報、36：29-95、doi：10.1112/plms/s2-36.1.29
2. W. Magnus、(1937) 「Über Beziehungen zwischen höheren Kommutatoren」、J. Grelle 177、105-115。
3. Hall, Marshall (1950)、「自由リー環と自由群の高次交換子の基底」、アメリカ数学会紀要、1 (5): 575– 581、doi : 10.1090/S0002-9939-1950-0038336-7、ISSN  0002-9939、MR  0038336
4. X. Viennot、(1978) "Algèbres de Lie libres et monoïdes libres"、数学講義ノート、691、Springer–Verlag
5. Guy Melançon、(1992)「ホール木とホール語の組合せ論」、組合せ理論ジャーナル、59A (2) pp. 285–308。
6. Guy MelançonとC. Reutenauer (1989)、「Lyndon words, free algebras and shuffles」、Canadian Journal of Mathematics、41巻4号、577-591頁。