ホールワード

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

注意してください${\displaystyle 2,1,2,3,6,\ldots }$それぞれ異なる長さの要素。これは、2つの要素からなるネックレス多項式の初期シーケンスです（後述）。

基本的な結果として、長さの要素の数は${\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 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)}$それ以外の場合。葉とは、木の葉で構成される文字列のことです。つまり、交換子括弧で記述された木を取り、交換子括弧を消去したものです。

させて${\displaystyle t=[x,y]\in H}$ホールツリーであり、${\displaystyle w=f([x,y])}$対応するホール語とする。ホール語の任意の因数分解が与えられた場合${\displaystyle w=uv}$2つの空でない文字列に分割する${\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.}$

これと、以下に続く展開は、Guy Melançonによって説明されている。^{[ 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})}$

それから${\displaystyle n=1}$言い換えれば、ホールワードは他のホールワードの降順のシーケンスに因数分解できない。 ^{[ 5 ]}これは、ホールワードが与えられた場合、対応するツリーを一意に識別できることを意味する。

ホール木における全順序はホール語に引き継がれます。したがって、ホール語が与えられた場合${\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}.}$ ホール語の並び順が増加することが標準であることに注意してください。

任意の単語の一意な因数分解${\displaystyle w\in A^{*}}$ホールの単語の昇順シーケンスの連結に${\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 (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})}$

一方、もう一方の操作では、ドロップ内の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})}$

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

言葉に基づいて合計注文を提供できます${\displaystyle w\in A^{*}.}$これは標準的な辞書式順序 に似ていますが、ホール語のレベルでの話です。2つの単語が与えられた場合${\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}.}$