ホワイトヘッドのアルゴリズム

ホワイトヘッドのアルゴリズムは、有限階数自由群F _nにおける保型同値問題を解く群論における数学アルゴリズムである。このアルゴリズムは、 JHCホワイトヘッドの1936年の古典的な論文^{[ 1 ]}に基づいている。ホワイトヘッドのアルゴリズムが多項式時間計算量を持つかどうかは、（ n  = 2の場合を除いて）未だ不明である。

問題の説明

を自由基底 を持つ階数の自由群とします。自己同型問題、あるいはの自己同型同値問題 は、2つの自由に簡約された語が与えられたとき、となるような自己同型が存在するかどうかを問うものです。 ${\displaystyle F_{n}=F(x_{1},\dots,x_{n})}$ ${\displaystyle n\geq 2}$ ${\displaystyle X=\{x_{1},\dots ,x_{n}\}}$ ${\displaystyle F_{n}}$ ${\displaystyle w,w'\in F_{n}}$ ${\displaystyle \varphi \in \operatorname {Aut} (F_{n})}$ ${\displaystyle \varphi (w)=w'}$

したがって、自己同型問題は、 に対して であるかどうかを問う。 に対して が成り立つのは、の共役類がそれに応じてとなる場合のみである。したがって、 に対する自己同型問題は、の元の共役類の -同値性という観点から定式化されることが多い。 ${\displaystyle w,w'\in F_{n}}$ ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$ ${\displaystyle w,w'\in F_{n}}$ ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$ ${\displaystyle \operatorname {Out} (F_{n})[w]=\operatorname {Out} (F_{n})[w']}$ ${\displaystyle [w],[w']}$ ${\displaystyle F_{n}}$ ${\displaystyle w,w'}$ ${\displaystyle F_{n}}$ ${\displaystyle \operatorname {出力} (F_{n})}$ ${\displaystyle F_{n}}$

元 について、は に関する の自由に縮約された長さを表し、は に関する の巡回的に縮約された長さを表します。自己同型問題では、入力 の長さはを の元と見なすか、における対応する共役類を定義する と見なすかによって、または として測定されます。 ${\displaystyle w\in F_{n}}$ ${\displaystyle |w|_{X}}$ ${\displaystyle w}$ ${\displaystyle X}$ ${\displaystyle \|w\|_{X}}$ ${\displaystyle w}$ ${\displaystyle X}$ ${\displaystyle w}$ ${\displaystyle |w|_{X}}$ ${\displaystyle \|w\|_{X}}$ ${\displaystyle w}$ ${\displaystyle F_{n}}$ ${\displaystyle [w]}$ ${\displaystyle F_{n}}$

歴史

の自己同型問題は、JHCホワイトヘッドによって1936年の古典論文^{[ 1 ]}でアルゴリズム的に解かれ、彼の解はホワイトヘッドのアルゴリズムとして知られるようになりました。ホワイトヘッドはこの論文で位相幾何学的アプローチを用いています。すなわち、3次元多様体、すなわちのコピーの連結和を考えます。すると、、さらに、に同型な有限正規部分群による商を除けば、の写像類群はに等しくなります。 ^{[ 2} ]を参照してください。 [3 ^]の異なる自由基底は、における「球面系」の同位体類で表すことができ、元 の巡回縮約形、および のホワイトヘッドグラフは、一般位置を表すループ^{が系内の球面と}どのように交差するかから「読み取る」ことができます 。ホワイトヘッドの動きは^、球面系を変更する特定の種類の位相的な「スワッピング」動きによって表すことができます。^{[ 4 ] [ 5 ]}${\displaystyle F_{n}}$ ${\displaystyle M_{n}=\#_{i=1}^{n}\mathbb {S} ^{2}\times \mathbb {S} ^{1}}$ ${\displaystyle n}$ ${\displaystyle \mathbb {S} ^{2}\times \mathbb {S} ^{1}}$ ${\displaystyle \pi _{1}(M_{n})\cong F_{n}}$ ${\displaystyle \mathbb {Z} _{2}^{n}}$ ${\displaystyle M_{n}}$ ${\displaystyle \operatorname {出力} (F_{n})}$ ${\displaystyle F_{n}}$ ${\displaystyle M_{n}}$ ${\displaystyle w\in F_{n}}$ ${\displaystyle [w]}$ ${\displaystyle [w]}$

その後、ラパポート^{[ 6 ]} 、そして後にはヒギンズとリンドン[ ^{7 ]}が、彼女の研究に基づいて、ホワイトヘッドの研究とホワイトヘッドのアルゴリズムを純粋に組合せ論的かつ代数的に再解釈した。リンドンとシュップ^{[ 8 ]}の著書におけるホワイトヘッドのアルゴリズムの説明は、この組合せ論的アプローチに基づいている。カラーとフォクトマン^{[ 9 ]}は、1986年の論文「アウタースペース^」において、ホワイトヘッドのアルゴリズムに対して、組合せ論的な用語を用いながらもホワイトヘッドの当初の考えに忠実に従ったハイブリッドなアプローチを示した。

ホワイトヘッドのアルゴリズム

ホワイトヘッドのアルゴリズムに関する私たちの説明は、主にリンドンとシュップの著書の第I章4に従っています。^{[ 8 ] [ 10 ]}

概要

自己同型群は、ホワイトヘッド自己同型、すなわちホワイトヘッド移動の特に有用な有限生成集合を持つ。ホワイトヘッドのアルゴリズムの最初の部分は、ホワイトヘッド移動 を に反復的に適用し、各 を「自己同型的に最小」な形へと導くことで構成される。この「自己同型的に最小」な形とは、巡回的に縮約された長さが各ステップで厳密に減少する形である。のこれらの最小形を自己同型的に見つけたら、 かどうかを調べる。 の場合、は において自己同型的に同値ではない。 ${\displaystyle \operatorname {Aut} (F_{n})}$ ${\displaystyle {\mathcal {W}}}$ ${\displaystyle w,w'\in F_{n}}$ ${\displaystyle w,w'}$ ${\displaystyle u,u'}$ ${\displaystyle w,w'}$ ${\displaystyle \|u\|_{X}=\|u'\|_{X}}$ ${\displaystyle \|u\|_{X}\neq \|u'\|_{X}}$ ${\displaystyle w,w'}$ ${\displaystyle F_{n}}$

ならば、 をとするホワイトヘッド移動の有限連鎖が存在し、この連鎖全体を通して巡回縮約長が一定であるかどうかを検証する。そのような連鎖が存在する 場合のみ、の元は保型的に同値ではない。${\displaystyle \|u\|_{X}=\|u'\|_{X}}$ ${\displaystyle u}$ ${\displaystyle u'}$ ${\displaystyle w,w'}$ ${\displaystyle F_{n}}$

ホワイトヘッドのアルゴリズムは、の探索自己同型問題も解きます。つまり、 が与えられた場合、ホワイトヘッドのアルゴリズムが であると結論付ければ、アルゴリズムはとなる自己同型も出力します。このような元は、上記の手順から生じるからまでのホワイトヘッド移動の連鎖の合成として生成されます。 ${\displaystyle F_{n}}$ ${\displaystyle w,w'\in F_{n}}$ ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$ ${\displaystyle \varphi \in \operatorname {Aut} (F_{n})}$ ${\displaystyle \varphi (w)=w'}$ ${\displaystyle \varphi \in \operatorname {Aut} (F_{n})}$ ${\displaystyle w}$ ${\displaystyle w'}$

ホワイトヘッド自己同型

のホワイトヘッド自己同型、またはホワイトヘッド移動は、次の 2 つのタイプのいずれかの の自己同型です。${\displaystyle F_{n}}$ ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$ ${\displaystyle F_{n}}$

1. となるようなの順列が存在し、これは第一種ホワイトヘッド自己同型と呼ばれます。${\displaystyle \sigma \in S_{n}}$ ${\displaystyle \{1,2,\dots ,n\}}$ ${\displaystyle i=1,\dots ,n}$ $${\displaystyle \tau (x_{i})=x_{\sigma (i)}^{\pm 1}}$$ ${\displaystyle \tau}$
2. 乗数と呼ばれる元 が存在し、任意の に対して となる。このようなは第二種ホワイトヘッド自己同型と呼ばれる。は の自己同型なので、この場合となる。${\displaystyle a\in X^{\pm 1}}$ ${\displaystyle x\in X^{\pm 1}}$ $${\displaystyle \tau (x)\in \{x,xa,a^{-1}x,a^{-1}xa\}。}$$ ${\displaystyle \tau}$ ${\displaystyle \tau}$ ${\displaystyle F_{n}}$ ${\displaystyle \tau (a)=a}$

多くの場合、ホワイトヘッド自己同型 の場合、対応する の外部自己同型は、ホワイトヘッド自己同型またはホワイトヘッド移動とも呼ばれます。 ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$ ${\displaystyle \operatorname {出力} (F_{n})}$

例

させて。 ${\displaystyle F_{4}=F(x_{1},x_{2},x_{3},x_{4})}$

が となる準同型写像であるとすると、 は 実際には の自己同型写像​​であり、さらに は乗数 を持つ第二種のホワイトヘッド自己同型写像​​である。 ${\displaystyle \tau :F_{4}\to F_{4}}$ $${\displaystyle \tau (x_{1})=x_{2}x_{1},\quad \tau (x_{2})=x_{2},\quad \tau (x_{3})=x_{2}x_{3}x_{2}^{-1},\quad \tau (x_{4})=x_{4}}$$ ${\displaystyle \tau }$ ${\displaystyle F_{4}}$ ${\displaystyle \tau }$ ${\displaystyle a=x_{2}^{-1}}$

が となる準同型写像であるとします。 すると は、 による共役により与えられるの内部自己同型写像​​であり、さらに は、乗数 を持つ第二種のホワイトヘッド自己同型写像​​です。 ${\displaystyle \tau ':F_{4}\to F_{4}}$ $${\displaystyle \tau '(x_{1})=x_{1},\quad \tau '(x_{2})=x_{1}^{-1}x_{2}x_{1},\quad \tau '(x_{3})=x_{1}^{-1}x_{3}x_{1},\quad \tau '(x_{4})=x_{1}^{-1}x_{4}x_{1}}$$ ${\displaystyle \tau '}$ ${\displaystyle F_{4}}$ ${\displaystyle x_{1}}$ ${\displaystyle \tau '}$ ${\displaystyle a=x_{1}}$

保型的極小元とホワイトヘッド極小元

に対して、共役類は、任意の に対して が成り立つとき、保型的に極小であるとされる。また、共役類は、任意のホワイトヘッド移動に対して が成り立つとき、ホワイトヘッド極小であるとされる。 ${\displaystyle w\in F_{n}}$ ${\displaystyle [w]}$ ${\displaystyle \varphi \in \operatorname {Aut} (F_{n})}$ ${\displaystyle \|w\|_{X}\leq \|\varphi (w)\|_{X}}$ ${\displaystyle [w]}$ ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$ ${\displaystyle \|w\|_{X}\leq \|\tau (w)\|_{X}}$

したがって、定義により、が保型的に極小であれば、ホワイトヘッド極小でもある。逆もまた真であることがわかる。 ${\displaystyle [w]}$

ホワイトヘッドの「ピーク削減補題」

以下の命題はホワイトヘッドの「ピーク削減補題」と呼ばれ、^{[ 8 ]の命題4.20と[ 10 ]}の命題1.2を参照。

とします。すると、次が成り立ちます。 ${\displaystyle w\in F_{n}}$

1. が自己同型的に最小でない場合、となる ホワイトヘッド自己同型が存在する。${\displaystyle [w]}$ ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$ ${\displaystyle \|\tau (w)\|_{X}<\|w\|_{X}}$

1. が保型的に極小であり、別の共役類も保型的に極小であるとする。すると、 と のときのみ、ホワイトヘッド移動の有限列が存在し、と となる。${\displaystyle [w]}$ ${\displaystyle [w']}$ ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$ ${\displaystyle \|w\|_{X}=\|w'\|_{X}}$ ${\displaystyle \tau _{1},\dots ,\tau _{k}\in \operatorname {Aut} (F_{n})}$ $${\displaystyle \tau _{k}\cdots \tau _{1}(w)=w'}$$ $${\displaystyle \|\tau _{i}\cdots \tau _{1}(w)\|_{X}=\|w\|_{X}{\text{ for }}i=1,\dots ,k.}$$

ピーク削減補題の(1)は、共役類がホワイトヘッド極小となるのは、それが自型的に極小となる場合のみであることを意味している。 ${\displaystyle [w]}$

自己同型グラフ

の自己同型グラフ は、頂点集合が元の共役類全体の集合であるグラフである。2つの異なる頂点がにおいて隣接している場合、かつ となるホワイトヘッド自己同型が存在する。の頂点に対して、におけるの連結成分はと表記される。 ${\displaystyle {\mathcal {A}}}$ ${\displaystyle F_{n}}$ ${\displaystyle [u]}$ ${\displaystyle u\in F_{n}}$ ${\displaystyle [u],[v]}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle \|u\|_{X}=\|v\|_{X}}$ ${\displaystyle \tau }$ ${\displaystyle [\tau (u)]=[v]}$ ${\displaystyle [u]}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle [u]}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}}[u]}$

ホワイトヘッドグラフ

巡回簡約形式 の場合、ホワイトヘッドグラフは頂点集合 を持つラベル付きグラフです。ただし、 の場合、と を結ぶ辺 があり、そのラベルまたは「重み」は で巡回的に読み取られるサブワードの異なる出現回数に等しくなります。(ホワイトヘッドグラフの一部のバージョンでは、 を持つ辺のみが含まれます。) ${\displaystyle 1\neq w\in F_{n}}$ ${\displaystyle u}$ ${\displaystyle \Gamma _{[w]}}$ ${\displaystyle X^{\pm 1}}$ ${\displaystyle x,y\in X^{\pm 1},x\neq y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle n(\{x,y\};[w])}$ ${\displaystyle x^{-1}y,y^{-1}x}$ ${\displaystyle u}$ ${\displaystyle n(\{x,y\};[w])>0}$

がホワイトヘッド自己同型ならば、長さの変化はホワイトヘッドグラフの重みの線形結合として表すことができ、その係数は によって決定される。 ^{[ 8 ]}の第1章の命題4.16を参照。この事実はホワイトヘッドのピーク削減結果の証明において重要な役割を果たす。 ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$ ${\displaystyle \|\tau (w)\|_{X}-\|w\|_{X}}$ ${\displaystyle \tau }$ ${\displaystyle n(\{x,y\};[w])}$ ${\displaystyle \Gamma _{[w]}}$

ホワイトヘッドの最小化アルゴリズム

ホワイトヘッドの最小化アルゴリズムは、自由に簡約された単語が与えられたとき、次のような自己同型最小のものを見つける。${\displaystyle w\in F_{n}}$ ${\displaystyle [v]}$ ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})v.}$

このアルゴリズムは次のように進行します。 が与えられた場合、 を とします。が既に構築されている場合、となるホワイトヘッド自己同型が存在するかどうかを確認します。( のホワイトヘッド自己同型集合は有限であるため、この条件は確認できます。) そのようなものが存在する場合、と入力して次のステップに進みます。そのようなものが存在しない場合は、が に対して自己同型的に最小であると宣言し、アルゴリズムを終了します。 ${\displaystyle w\in F_{n}}$ ${\displaystyle w_{1}=w}$ ${\displaystyle w_{i}}$ ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$ ${\displaystyle \|\tau (w_{i})\|_{X}<\|w_{i}\|_{X}}$ ${\displaystyle F_{n}}$ ${\displaystyle \tau }$ ${\displaystyle w_{i+1}=\tau (w_{i})}$ ${\displaystyle \tau }$ ${\displaystyle [w_{i}]}$ ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w_{i}}$

ピーク低減補題の(1)は、ホワイトヘッドの最小化アルゴリズムが （ ）で終了することを意味しており、その場合 は確かに自己同型最小となり を満たします。 ${\displaystyle w_{m}}$ ${\displaystyle m\leq \|w\|_{X}}$ ${\displaystyle [w_{m}]}$ ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w_{m}}$

保型同値問題に対するホワイトヘッドのアルゴリズム

自己同型同値問題に対するホワイトヘッドのアルゴリズムでは、が かどうかを判定します。 ${\displaystyle w,w'\in F_{n}}$ ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$

アルゴリズムは次のように進行します。 が与えられた場合、まずホワイトヘッド最小化アルゴリズムを のそれぞれに適用し、かつ となる保型的に最小のものを見つけます。 の場合、 であると宣言し、アルゴリズムを終了します。次に、 であると仮定します。次に、かつ となるホワイトヘッド移動の有限列が存在するかどうかを確認します。${\displaystyle w,w'\in F_{n}}$ ${\displaystyle w,w'}$ ${\displaystyle [v],[v']}$ ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})v}$ ${\displaystyle \operatorname {Aut} (F_{n})w'=\operatorname {Aut} (F_{n})v'}$ ${\displaystyle \|v\|_{X}\neq \|v'\|_{X}}$ ${\displaystyle \operatorname {Aut} (F_{n})w\neq \operatorname {Aut} (F_{n})w'}$ ${\displaystyle \|v\|_{X}=\|v'\|_{X}=t\geq 0}$ ${\displaystyle \tau _{1},\dots ,\tau _{k}\in \operatorname {Aut} (F_{n})}$ $${\displaystyle \tau _{k}\dots \tau _{1}(v)=v'}$$ $${\displaystyle \|\tau _{i}\dots \tau _{1}(v)\|_{X}=\|v\|_{X}=t{\text{ for }}i=1,\dots ,k.}$$

この条件は、長さの巡回縮約語の数が有限であることから確認できます。より具体的には、幅優先アプローチを用いて自己同型グラフの連結成分を構築し、 であることを確認します。 ${\displaystyle t}$ ${\displaystyle F_{n}}$ ${\displaystyle {\mathcal {A}}[v],{\mathcal {A}}[v']}$ ${\displaystyle {\mathcal {A}}[v]\cap {\mathcal {A}}[v']=\varnothing }$

そのようなシーケンスが存在する場合、 を宣言し、アルゴリズムを終了します。そのようなシーケンスが存在しない場合は、 を宣言し、アルゴリズムを終了します。 ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$ ${\displaystyle \operatorname {Aut} (F_{n})w\neq \operatorname {Aut} (F_{n})w'}$

ピーク削減補題は、ホワイトヘッドのアルゴリズムが における自己同型同値問題を正しく解くことを意味します。さらに、 の場合、アルゴリズムは実際に（ホワイトヘッドの合成が移動するにつれて）となる自己同型を生成します。 ${\displaystyle F_{n}}$ ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$ ${\displaystyle \varphi \in \operatorname {Aut} (F_{n})}$ ${\displaystyle \varphi (w)=w'}$

ホワイトヘッドアルゴリズムの計算複雑さ

• の階数が固定されている場合、ホワイトヘッド最小化アルゴリズムは常に2次時間で終了し、となるような自己同型最小の巡回縮約語を生成します。^{[ 10 ]}さらに、 が固定されていないと見なされる場合でも、入力に対するホワイトヘッド最小化アルゴリズム（の適応）はで終了します。^{[ 11 ]}${\displaystyle n\geq 2}$ ${\displaystyle F_{n}}$ ${\displaystyle w\in F_{n}}$ ${\displaystyle O(|w|_{X}^{2})}$ ${\displaystyle u\in F_{n}}$ ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})u}$ ${\displaystyle n}$ ${\displaystyle w\in F_{n}}$ ${\displaystyle O(|w|_{X}^{2}n^{3})}$
• の階数が固定されている場合、自型極小グラフの構築には時間がかかり、 では事前に指数時間が必要になります。そのため、 が与えられた場合に であるかどうかを判定するホワイトヘッドのアルゴリズムは、では最大で指数時間で実行されます。${\displaystyle n\geq 3}$ ${\displaystyle F_{n}}$ ${\displaystyle u\in F_{n}}$ ${\displaystyle {\mathcal {A}}[u]}$ ${\displaystyle O\left(\|u\|_{X}\cdot \#V{\mathcal {A}}[u]\right)}$ ${\displaystyle |u|_{X})}$ ${\displaystyle w,w'\in F_{n}}$ ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$ ${\displaystyle \max\{|w|_{X},|w'|_{X}\}}$
• について、カーンは、自型極小の に対して、グラフには最大で個の頂点があり、したがってグラフの構築はの二次時間で実行できることを証明しました。^{[ 12 ]}その結果、 の自型同値問題に対するホワイトヘッドのアルゴリズムは、 が与えられた場合、では二次時間で実行されます。${\displaystyle n=2}$ ${\displaystyle u\in F_{2}}$ ${\displaystyle {\mathcal {A}}[u]}$ ${\displaystyle O\left(\|u\|_{X}\right)}$ ${\displaystyle {\mathcal {A}}[u]}$ ${\displaystyle |u|_{X}}$ ${\displaystyle F_{2}}$ ${\displaystyle w,w'\in F_{2}}$ ${\displaystyle \max\{|w|_{X},|w'|_{X}\}}$

応用、一般化および関連する結果

• ホワイトヘッドのアルゴリズムは、任意の固定されたに対して、のm組の選出とm組の共役類の自己同型同値問題を解くために適応できる。 ^{[ 8 ]}のCh.I.4と^{[ 13 ]を参照。}${\displaystyle m\geq 1}$ ${\displaystyle F_{n}}$ ${\displaystyle F_{n}}$
• マクールはホワイトヘッドのアルゴリズムとピーク削減法を用いて、任意の に対して安定化因子が有限に提示可能であることを証明し、における共役類のm組の安定化因子についても同様の結果が得られた。^{[ 14 ]}マクールはまた、ピーク削減法を用いて、ホワイトヘッド自己同型集合を生成集合とする群の有限表現を構築した。^{[ 15 ]}次に、この表現を用いて、もともとニールセンによって提案された、ニールセン自己同型を生成集合とするに対する有限表現を復元した。^{[ 16 ]}${\displaystyle w\in F_{n}}$ ${\displaystyle \operatorname {Stab} _{\operatorname {Out} (F_{n})}([w])}$ ${\displaystyle \operatorname {Out} (F_{n})}$ ${\displaystyle F_{n}}$ ${\displaystyle \operatorname {Aut} (F_{n})}$ ${\displaystyle \operatorname {Aut} (F_{n})}$
• ゲルステンは、ホワイトヘッドのアルゴリズムのバリエーションを得て、2つの有限部分集合が与えられたときに、その部分群が自己同型的同値であるかどうか、つまり、となるようなものが存在するかどうかを判定するアルゴリズムを導いた。^{[ 17 ]}${\displaystyle S,S'\subseteq F_{n}}$ ${\displaystyle H=\langle S\rangle ,H'=\langle S'\rangle \leq F_{n}}$ ${\displaystyle \varphi \in \operatorname {Aut} (F_{n})}$ ${\displaystyle \varphi (H)=H'}$
• ホワイトヘッドのアルゴリズムとピーク削減は、カラーとフォークトマンによるカラー・フォークトマン外部空間が収縮可能であることの証明において重要な役割を果たしている。^{[ 9 ]}
• コリンズとツィーシャンはホワイトヘッドのピーク削減と群の自由積における自同型同値性に対するホワイトヘッドのアルゴリズムの類似物を得た。^{[ 18 ] [ 19 ]}
• ギルバートはピーク簡約補題の一種を用いて自由積の自己同型群 の表現を構築した。^{[ 20 ]}${\displaystyle \operatorname {Aut} (G)}$ ${\displaystyle G=\ast _{i=1}^{m}G_{i}}$
• レヴィットとヴォクトマンは、閉じた双曲面である群における自己同型同値問題（選民、m組の元、m組の共役類について）を解決するホワイトヘッド型アルゴリズムを考案した。 ^{[ 21 ]}${\displaystyle G=\pi _{1}(S)}$ ${\displaystyle S}$
• の半径の球面から 一様ランダムに選ばれた元が である場合、 の指数関数的に速く1に近づく確率で、共役類は既に保型的に最小であり、さらに となる。したがって、がそのような「一般的な」2つの元である場合、ホワイトヘッドのアルゴリズムはにおいて線形時間で が保型的に同値であるかどうかを判定する。^{[ 10 ]}${\displaystyle w\in F_{n}=F(X)}$ ${\displaystyle m\geq 1}$ ${\displaystyle F(X)}$ ${\displaystyle m\to \infty }$ ${\displaystyle [w]}$ ${\displaystyle \#V{\mathcal {A}}[w]=O\left(\|w\|_{X}\right)=O(m)}$ ${\displaystyle w,w'\in F_{n}}$ ${\displaystyle w,w'}$ ${\displaystyle \max\{|w|_{X},|w'|_{X}\}}$
• 上記の結果と同様に、の「ランダムに選ばれた」有限生成部分群に対する自己同型極小性の一般性も成り立つ。^{[ 22 ]}${\displaystyle F_{n}}$
• リーは、が巡回簡約語で が自己同型的に最小であり、 または の両方が出現するときは常に における の出現回数の合計が の出現回数より小さい場合、はにおける次数の多項式によって上方に有界であることを証明した。^{[ 23 ]}したがって、が上記の性質を持つものと自己同型的に同値である場合、ホワイトヘッドのアルゴリズムはの時間で が自己同型的に同値かどうかを判定する。${\displaystyle u\in F_{n}=F(X)}$ ${\displaystyle [u]}$ ${\displaystyle x_{i},x_{j},i<j}$ ${\displaystyle u}$ ${\displaystyle u^{-1}}$ ${\displaystyle x_{i}^{\pm 1}}$ ${\displaystyle u}$ ${\displaystyle x_{i}^{\pm 1}}$ ${\displaystyle \#V{\mathcal {A}}[u]}$ ${\displaystyle 2n-3}$ ${\displaystyle |u|_{X}}$ ${\displaystyle w,w'\in F_{n},n\geq 3}$ ${\displaystyle w}$ ${\displaystyle u}$ ${\displaystyle w,w'}$ ${\displaystyle O\left(\max\{|w|_{X}^{2n-3},|w'|_{X}^{2}\}\right)}$
• 組紐群の共役問題を解くガーサイドアルゴリズムはホワイトヘッドのアルゴリズムと似た一般的な構造を持ち、「サイクリング動作」がホワイトヘッド動作の役割を果たしている。^{[ 24 ]}
• クリフォードとゴールドスタインはホワイトヘッドアルゴリズムに基づく手法を用いて、有限部分集合が与えられたときにその部分集合に${\displaystyle Z\subseteq F_{n}}$ ${\displaystyle H=\langle Z\rangle \leq F_{n}}$ の原始元は^{[ 25 ]}の自由生成集合の元である${\displaystyle F_{n},}$ ${\displaystyle F_{n}.}$
• デイはホワイトヘッドのアルゴリズムとホワイトヘッドのピーク還元の類似物を、直角アルティン群の元の自型同値性について得た。^{[ 26 ]}

参考文献

1. J. HC Whitehead ,自由群の同値な要素集合について, Ann. of Math. (2) 37:4 (1936), 782–800. MR  1503309
2. Suhas Pandit,球面複体の自己同型に関するノート. Proc. Indian Acad. Sci. Math. Sci. 124:2 (2014), 255–265; MR 3218895 
3. アレン・ハッチャー「自由群の自己同型群のホモロジー安定性」 Commentarii Mathematici Helvetici 70:1 (1995) 39–62; MR 1314940 
4. カレン・ヴォクトマン「自由群の自己同型と宇宙空間」 幾何学および組合せ群論に関する会議議事録、第1部（ハイファ、2000年） Geometriae Dedicata 94（2002年）、1-31; MR 1950871 
5. アンドリュー・クリフォード、リチャード・Z・ゴールドスタイン、「自由群の原始元の集合」、代数ジャーナル357（2012）、271-278; MR 2905255 
6. エルビラ・ラパポート「自由群とその自己同型について」 アクタ・マセマティカ99 (1958), 139–163; MR 0131452 
7. PJヒギンズ、RCリンドン「自由群の自己同型写像​​の下での要素の同値性」ロンドン数学会誌(2) 8 (1974)、254-258; MR 0340420 
8. Roger LyndonとPaul Schupp、組み合わせ群理論。 1977年版の復刻版。数学の古典。Springer-Verlag、ベルリン、2001。ISBN 3-540-41158-5MR  1812024
9. Marc Culler ; Karen Vogtmann (1986). 「グラフのモジュライと自由群の自己同型性」(PDF) . Inventiones Mathematicae . 84 ( 1): 91– 119. doi : 10.1007/BF01388734 . MR 0830040. S2CID 122869546 .  
10. イリヤ・カポビッチ、ポール・シュップ、ウラジミール・シュピレイン、「ホワイトヘッドのアルゴリズムの一般的性質とランダム1関係群の同型性剛性」、パシフィック・ジャーナル・オブ・マスマティクス223:1 (2006)、113–140
11. Abdó Roig, Enric Ventura, Pascal Weil,ホワイトヘッド最小化問題の複雑さについて. International Journal of Algebra and Computation 17:8 (2007), 1611–1634; MR 2378055 
12. ビラル・カーン「 階数2の自由群における保型共役性の構造」計算群論および実験群論、115–196ページ、現代数学、349ページ、アメリカ数学会、プロビデンス、ロードアイランド州、2004年
13. Sava Krstić, Martin Lustig, Karen Vogtmann ,「デーンツイスト自己同型根の同変ホワイトヘッドアルゴリズムと共役性」エディンバラ数学会誌 (2) 44:1 (2001), 117–141
14. ジェームズ・マックール「自由群の自己同型群の有限提示部分群のいくつか」代数ジャーナル35:1-3 (1975), 205–213; MR 0396764 
15. ジェームズ・マックール「有限ランクの自由群の自己同型群の表現」ロンドン数学会誌 (2) 8 (1974), 259–266; MR 0340421 
16. ジェームズ・マックール「ニールセンによる自由群の自己同型群の表現について」ロンドン数学会誌 (2) 10 (1975), 265–270
17. スティーブン・ガーステン「ホワイトヘッドのアルゴリズムについて」アメリカ数学会報10:2 (1984), 281–284; MR 0733696 
18. Donald J. Collins、 Heiner Zieschang、 無料製品のためのホワイトヘッド メソッドの救出。 I. ピークの低減。数学時代185:4 (1984)、487–504 MR 0733769 
19. Donald J. Collins、 Heiner Zieschang、 無料製品のためのホワイトヘッド メソッドの救出。 II.アルゴリズム。数学時代186:3 (1984)、335–361; MR 0744825 
20. Nick D. Gilbert,自由積の自己同型群の提示.ロンドン数学会紀要(3) 54 (1987),第1号,115-140頁.
21. ギルバート・レビットとカレン・ヴォクトマン、「曲面群のためのホワイトヘッドアルゴリズム」、トポロジー39:6 (2000)、1239–1251
22. フレデリック・バッシーノ、シリル・ニカウ、パスカル・ヴェイユ「ホワイトヘッド極小性の一般性について」 群論ジャーナル19:1 (2016), 137–159 MR 3441131 
23. ドンギ・リー「保型軌道における最小長の語数のより厳しい境界」代数ジャーナル305 :2 (2006), 1093–1101; MR 2266870 
24. Joan Birman、Ki Hyoung Ko、Sang Jin Lee、「編組群における語と共役性の問題への新しいアプローチ」、 Advances in Mathematics 139:2 (1998)、322–353; Zbl 0937.20016 MR 1654165  
25. アンドリュー・クリフォード、リチャード・Z・ゴールドスタイン、「自由群の部分群と原始元」、群論ジャーナル13:4 (2010)、601–611; MR 2661660 
26. マシュー・デイ「直角アルティン群におけるフルフィーチャピーク削減」代数および幾何学的位相学14:3 (2014), 1677–1743 MR 3212581 

さらに読む

• ハイナー・ツィーシャン「組合せ群論と位相幾何学におけるニールセン法とホワイトヘッド法について」Groups—Korea '94 (Pusan)、317–337、1994年8月18日～25日に釜山国立大学で開催された第3回群論国際会議議事録。AC KimとD.L. Johnson編。de Gruyter、ベルリン、1995年、ISBN 3-11-014793-9MR  1476976
• ホワイトヘッドの3次元多様体モデルを用いたホワイトヘッドのアルゴリズムに関するカレン・ヴォクトマンの講義ノート