화이트헤드의 알고리즘

화이트헤드의 알고리즘은 유한계급 자유군_n F에서 자동동형성 문제를 해결하기 위한 집단 이론의 수학 알고리즘이다.이 알고리즘은 J. H. C의 1936년 고전적인 논문을 기초로 한다. 흰머리.^[1]화이트헤드의 알고리즘이 다항식 시간 복잡성을 가지고 있는지는 아직 알 수 없다(사례 n = 2 제외).

문제성명

Let ${\displaystyle F_{n}=F(x_{1},\dots ,x_{n})}$ be a free group of rank ${\displaystyle n\geq 2}$ with a free basis ${\displaystyle X=\{x_{1},\dots ,x_{n}\}}$.The automorphism problem, or the automorphic equivalence problem for ${\displaystyle F_{n}}$ asks, given two freely reduced words ${\displaystyle w,w'\in F_{n}}$ whether there exists an automorphism ${\displaystyle \varphi \in \operatorname {Aut} (F_{n})}$ such that ${\displaystyle \phi (w)=}$${\displaystyle w^{}}$ ${\displaystyle {\prime }^{}}$ ${\$.

Thus the automorphism problem asks, for ${\displaystyle w,w'\in F_{n}}$ whether ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$. For ${\displaystyle w,w'\in F_{n}}$ one has ${\displaystyle \mathrm{Aut}(F_n)w=\mathrm{Aut}(F_n)}$${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$ if and only if ${\displaystyle \operatorname {Out} (F_{n})[w]=\operatorname {Out} (F_{n})[w']}$, where ${\displaystyle [w],[w']}$ are conjugacy classes in ${\displaysty$이에$$ $따라{\displaystyle }$ w${\displaystyle ,}$ ${\displaystyle {}^{}}$, w ${\displaystyle {\prime }^{}}$ ${\$의 $le F_{n}.$따라서 F ${\displaystyle n_{}}$ ${\$에 대한 자동형성 문제는 $종종{\displaystyle {}_{}}$ ${\displaystyle \mathrm{Out}}$ ${\displaystyle }$ (${\displaystyle {Fn}_{}}$ ${\displaystyle {}_{}}${\$displaystyle \operatorname {Out}(F_{n})$ ${\displaystyle {-fn}_{}}${\$displaystyform F_{$n}} 요소의 결합성 클래스의 동등성$$ 측면에서 공식화된다$.$

For an element ${\displaystyle w\in F_{n}}$, ${\displaystyle w _{X}}$ denotes the freely reduced length of ${\displaystyle w}$ with respect to ${\displaystyle X}$, and ${\displaystyle \ w\ _{X}}$ denotes the cyclically reduced length of ${\displaystyle w}$ with respect to ${\displaystyle X}$. For the automorphism problem, the length of an input ${\displaystyle w}$ is measured as ${\displaystyle w _{X}}$ or as ${\displaystyle \ w\ _{X}}$, depending on whether one views ${\displaystyle w}$ as an element of ${\displaystyle F_{n}}$ or as F ${\displaystyle n_{}}$ ${\$에서 해당 결합 등급${\displaystyle }$[${\displaystyle w]}$ ${\displaystyle [w]}$ 정의$.$

역사

$F{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$에 대한 자동형성 문제는 J. H. C에 의해 알고리즘적으로 해결되었다. 1936년 고전적인 논문에서 화이트헤드(^[1]Whitehead)와 그의 해결책은 화이트헤드의 알고리즘으로 알려지게 되었다.화이트헤드는 논문에서 위상학적 접근법을 사용했다.Namely, consider the 3-manifold ${\displaystyle M_{n}=\#_{i=1}^{n}\mathbb {S} ^{2}\times \mathbb {S} ^{1}}$, the connected sum of ${\displaystyle n}$ copies of ${\displaystyle \mathbb {S} ^{2}\times \mathbb {S} ^{1}}$.Then ${\displaystyle \pi _{1}(M_{n})\cong F_{n}}$, and, moreover, up to a quotient by a finite normal subgroup isomorphic to ${\displaystyle \mathbb {Z} _{2}^{n}}$, the mapping class group of ${\displaystyle M_{n}}$ is equal to ${\displaystyle \operatornam$$e {Out}(F_{n})$ 참조$.$^[2]Different free bases of ${\displaystyle F_{n}}$ can be represented by isotopy classes of "sphere systems" in ${\displaystyle M_{n}}$, and the cyclically reduced form of an element ${\displaystyle w\in F_{n}}$, as well as the Whitehead graph of ${\displaystyle [w]}$, can be "read-off" from hoh [${\displaystyle w}$ ${\displaystyle ]}$ ${\displaystyle [w]}$을(를) 나타내는 일반 위치의 루프가 시스템의 구들을 교차한다$$.화이트헤드 움직임은 구체 시스템을 수정하는 특정한 종류의 위상학적 "스왑" 움직임으로 표현될 수 있다.^[3][4][5]

이어서 라파포트,^[6] 그리고 후에 그녀의 작품을 바탕으로 히긴스와 린든이 화이트헤드의 작품과 화이트헤드의 알고리즘에 대해 순전히 조합적, 대수적 재해석을 했다.^[7]린든과 슐프^[8] 책에서 화이트헤드의 알고리즘을 설명하는 것은 이러한 결합적 접근법에 바탕을 두고 있다.Culler와 Vogtmann은 ^[9]Outer Space를 소개한 1986년 논문에서 Whitehead의 알고리즘에 하이브리드 접근법을 제시했는데, 이 알고리즘은 조합 용어로 제시되었지만 Whitehead의 독창적인 아이디어를 근접하게 따른다.

화이트헤드의 알고리즘

화이트헤드의 알고리즘에 관한 우리의 설명서는 대부분 Ch를 따른다.린든과 슈프 책에도 I.4가 실려 있다.^[8][10]

개요

자동형성 그룹 Aut ${\displaystyle \mathrm{aut}}$(${\displaystyle {Fn}_{}}$) ${\displaystyle \operatorname {Aut}(F_{n})$은 특히 유용한 유한 생성 세트 $W{\displaystyle \mathcal{}}$ ${\$을(를) 화이트헤드 자동형 또는 화이트헤드 이동으로 구성한다.$w{\displaystyle }$, ${\displaystyle {}^{}}$ , w ${\displaystyle \prime }$ ${\displaystyle n_{}}$ F$$n {\$displaystyle w,w$'\$in F_{$n}}} 화이트헤드의 알고리즘의$$ 첫${\displaystyle }번째{\displaystyle }$ ${\displaystyle {}^{}}$은 w${\displaystyle {}^{}}$, w$display$ {\$displaystyle$ w$,$w}에 반복적으로 적용하여$$ 각각을 "자동적으로 최소" 형태로 만들고, 이 단계에서 반복적으로 감소시키는 것으로 구성된다.Once we find automorphically these minimal forms ${\displaystyle u,u'}$ of ${\displaystyle w,w'}$, we check if ${\displaystyle \ u\ _{X}=\ u'\ _{X}}$. If ${\displaystyle \ u\ _{X}\neq \ u'\ _{X}}$ then ${\displaystyle w,w'}$ are$F{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$에 자동적으로 동등하지 않음$.$

$\Vert$ ${\displaystyle u_{}}$ ${\displaystyle {}_{}}$X =${\displaystyle {}^{}}$ u${\displaystyle {}_{}}$u $u${ { { { { { { { { { { {$${$$\ \ u $u$${\displaystyle {}^{}}u$ $\$ \ \ u$$$u$ u$$$u$ \ \ \ \ \$$u u u u u u u \ u u u u x x x x x \ x x x x x ${\displaystyle x_{}}$ x \ \ x u x \ x x x x \$w{\displaystyle }$, ${\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ 요소는 그러한$$ ${\displaystyle {체인}_{}}$이 존재하는$$ 경우에만 $F{\displaystyle {}_{}}$ n ${\$에서 자동적으로 동등하지 않다.

Whitehead's algorithm also solves the search automorphism problem for ${\displaystyle F_{n}}$. Namely, given ${\displaystyle w,w'\in F_{n}}$, if Whitehead's algorithm concludes that ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$, the algorithm also outputs an automorphism ${\displaystyle \varphi \in \operatorname {Aut} (F_{n})}$ such that ${\displaystyle \varphi (w)=w'}$. Such an element ${\displaystyle \varphi \in \operatorname {Aut} (F_{n})}$ is produced as the composition of a chain of Whiteh위의 절차에서 발생한 ead 이동으로 $w{\displaystyle }$ ${\$$displaystyle w}$에서${\displaystyle {}^{}}$w {\$displaystyle$ w$'}$까지 이동하십시오$.$

백두자동화

$F{\displaystyle }$ ${\displaystyle n_{}}$ ${\$의 Whitehead automformism, 즉 Whitehead move는$$ 다음 두 가지 유형 중 $하나$로 ${\displaystyle F_{}}$ n$${\$displaystyle F_{n}$의 Aut ${\displaystyle }$(${\displaystyle F_{}}$ $){\displaysty \tau \in \operatorname {Aut}(F_{n})})$이다.

(i) 순열 $\sigma {\displaystyle }$ ${\displaystyle S_{}}$ ${\displaystyle {}_{}}$ ${\$$1$ ,${\displaystyle 2}$, , n$}$ {\$displaystyle \{1,2,\$dots ,n$\}$의 순열${\displaystyle }$σ${\displaystyle }$=${\displaystyle 1}$ , ${\displaystyle n,}$\$displaystystyle i=1,\dots ,n}$이 있다.

${\displaystyle \tau(x_{i})=x_{\pma (i)}^{\pm 1.$

이러한 $\tau {\displaystyle }$ ${\displaystyle \tau}$을(를) 제1종류의 화이트헤드 오토모프(Whitehead automorphism)라고 한다$$.

(ii)${\displaystyle {}^{}}$± ${\displaystyle 1^{}}$ ${\$ X$^{\pm$ 1$}$의 $모든{\displaystyle {}^{}}$ multipl X ±${\displaystyle 1^{}}$ ${\$ $1$$}$에 대해 승수라고 하는 $원소$가 있다$.$

$\\displaystyle \tau (x)\in \{x,xa,a^{-1}x,a^{-1}xa\}.}$

이러한 $\tau {\displaystyle }$ ${\displaystyle \tau}$을(를) 제2종류의 Whitehead automorphism이라고 한다.${\displaystyle \tau }$은(는) ${\displaystyle F_{}}$ n ${\$의 자동형이기 때문에$,$ 이 경우$$ $\tau {\displaystyle (}$는${\displaystyle )}$ = ${\displaystyle \tau(a)=a}$를 따른다.

Often, for a Whitehead automorphism ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$, the corresponding outer automorphism in ${\displaystyle \operatorname {Out} (F_{n})}$ is also called a Whitehead automorphism or a Whitehead move.

예

Let $F{\displaystyle {}_{}}$ ${\displaystyle {4\mathrm{}}_{}}$= ${\displaystyle F}$( ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle {}_{}}$x ${\displaystyle {3\mathrm{}}_{}}$, ${\displaystyle {x\mathrm{}}_{}{}_{}{}_{}}$) ${\displaystyle F_{4}=F(x_{1},x_{2},x_{3},x_{4$

$\tau {\displaystyle }$: ${\displaystyle {F\mathrm{}}_{}}$ ${\displaystyle {}_{}}$→ F ${\displaystyle {4\mathrm{}}_{}}$ ${\$을(를) 동형성으로 하자.

${\displaystyle \tau(x_{1})=x_{1},\displaystyle \tau(x_{2})=x_{2}x_{3}x_{2}^{1},\display \tau(x_{4}}}}x_{4}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}})$

그렇다면 ${\displaystyle \tau }}$은(는$$) $사실{\displaystyle {}_{}}$ F ${\displaystyle {4\mathrm{}}_{}}${\$displaystyle F_{4}$의 자동형이며$,$ 더욱이 $moreover{\displaystyle }$ ${\displaystyle \tau}$은 승수 $a{\displaystyle }$= ${\displaystyle {}_{}^{}}$- ${\displaystyle 1_{}^{}}$ ${\$의 두 번째 종류의 자동형이다$.$

$\tau {\displaystyle {}^{}}$: ${\displaystyle {}_{}}$ ${\displaystyle {4\mathrm{}}_{}}$→ ${\displaystyle {F\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\$$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}}$

Then ${\displaystyle \tau '}$ is actually an inner automorphism of ${\displaystyle F_{4}}$ given by conjugation by ${\displaystyle x_{1}}$, and, moreover, ${\displaystyle \tau '}$is a Whitehead automorphism of the second kind, with the multiplier ${\displaystyle a=x_{1}}$.

자동 최소 및 화이트헤드 최소 요소

For ${\displaystyle w\in F_{n}}$, the conjugacy class ${\displaystyle [w]}$ is called automorphically minimal if for every ${\displaystyle \varphi \in \operatorname {Aut} (F_{n})}$ we have ${\displaystyle \ w\ _{X}\leq \ \varphi (w)\ _{X}}$. Also, a conjugacy class ${\displaystyle [w]}$ is called Whitehead minimal if for every Whitehead move ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$ we have ${\displaystyle \ w\ _{X}\leq \ \tau (w)\ _{X}}$.

따라서 정의상${\displaystyle }$[${\displaystyle w}$ ${\displaystyle ]}$ ${\displaystyle [w]}$이(가) 자동으로 최소인 경우 화이트헤드 최소인 경우도 있다.그 반론도 사실인 것으로 밝혀졌다.

화이트헤드의 "피크 감소 보조정리"

다음 문구를 Whitehead의 "피크 감소 보조정리"라고 하며, 제안 4.20 in 및 제안 1.2 in을 참조하십시오.^[10]

$W{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$을$($를) 그대로 두고 다음을 유지하십시오.

(1) If ${\displaystyle [w]}$ is not automorphically minimal, then there exists a Whitehead automorphism ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$ such that ${\displaystyle \ \tau (w)\ _{X}<\ w\ _{X}}$.

(2)${\displaystyle }$[ ${\displaystyle w}$ ${\displaystyle ]}$ ${\displaystyle [w]}$이(가) 자동적으로 최소이며$,{\displaystyle }$ 다른 결합 클래스 [${\displaystyle {}^{}}$ ${\displaystyle ]}$ ${\displaystyle [w]}$도 자동적으로$$ 최소라고 가정한다.Then ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$ if and only if ${\displaystyle \ w\ _{X}=\ w'\ _{X}}$ and there exists a finite sequence of Whitehead moves ${\displaystyle \tau _{1$$}},\dots ,\tau _{k}\in \operatorname {Aut}(F_{n})$과 같은 경우

${\displaystyle \tau _{k}\cdots \tau _{1}(w)=w'}$

그리고

${\displaystyle \tau \{i}\cdots \tau \tau _{1}(w)\{X}=\w\{X}{\text{{{}{}{}{}i=1,\dots,k.}}$

피크 감소 보조정리부 (1)은 결합 등급${\displaystyle }$[${\displaystyle w}$ ${\displaystyle ]}$ ${\displaystyle [w]}$이(가) 자동으로 최소인 경우에만 화이트헤드 최소임을$$ 암시한다.

자동형 그래프

The automorphism graph ${\displaystyle {\mathcal {A}}}$ of ${\displaystyle F_{n}}$ is a graph with the vertex set being the set of conjugacy classes ${\displaystyle [u]}$ of elements ${\displaystyle u\in F_{n}}$. Two distinct vertices ${\displaystyle [u],[v]}$ are adjacent${\$에서 ${\displaystyle {}_{}}$ $u$ =${\displaystyle {}_{}\Vert }$ ${\displaystyle v}$ ${\displaystyle {}_{}}$ ${\displaystyle v_{}}$ ‖ X ${\$$displaysty \tau}}$이(가$)$ 있고${\displaystyle }$[${\displaystyle \tau }$ (${\displaystyle u}$)${\displaystyle }$=${\displaystyle }$[${\displaystyle v}$ ${\displaystyle ]}$ ${\displaystystyle$ [\tyle]와$$ 같은 자동 \type$[\$type[\$type$ (u]이$)}$이)}이)가 있다.$=[v$ $A{\displaystyle \mathcal{}}$ ${\$의 꼭지점${\displaystyle }$[${\displaystyle u]}$ ${\$$displaystyle [u]}$에 $대해{\displaystyle \mathcal{}}$$,$$$${\$$displaystyle${\$mathcal$$${$A$$}$의${\displaystyle }$연결된$$ ${\displaystyle \mathrm{구성}}$ 요소는${\displaystyle }$A [$$]{\$displaystystystyle {a}$로 표시된다$.$

화이트헤드 그래프

For ${\displaystyle 1\neq w\in F_{n}}$ with cyclically reduced form ${\displaystyle u}$, the Whitehead graph ${\displaystyle \Gamma _{[w]}}$ is a labelled graph with the vertex set ${\displaystyle X^{\pm 1}}$, where for ${\displaystyle x,y\in X^{\pm 1},x\$$neq y}$ there is an edge joining ${\displaystyle x}$ and ${\displaystyle y}$ with the label or "weight" ${\displaystyle n(\{x,y\};[w])}$ which is equal to the number of distinct occurrences of subwords ${\displaystyle x^{-1}y,y^{-1}x}$ read cyclically in ${\displa$$ystyle u}$. (Whitehead 그래프의 일부 버전에서는 ({ , [ > ${\displaystyle n(\{x,y\};[w])0})$이 있는 에지만 포함되어 있다.)

If ${\displaystyle \tau \in \operatorname {Aut} (F_{n})}$ is a Whitehead automorphism, then the length change ${\displaystyle \ \tau (w)\ _{X}-\ w\ _{X}}$ can be expressed as a linear combination, with integer coefficients determined by ${\displaystyle \tau }$, of the weights${\displaystyle }$$n{\displaystyle {\mathrm{}}_{}}$${\displaystyle }$(${\displaystyle }${ ${\displaystyle x}$, ${\displaystyle y}$ ${\displaystyle \};}$[ ${\displaystyle w];}$ ${\displaystyle$ n$(\{x,y\};;[w])}$ 화이트헤드 그래프$$ [${\displaystyle {}_{}}$[ ${\displaystyle w_{}}$ ${\displaystyle {]}_{}}$ ${\$의 제안서 4.6을 참조하십시오.나는.^[8] 이 사실이 화이트헤드의 최고점 감소 결과의 입증에 중요한 역할을 한다.

화이트헤드의 최소화 알고리즘

Whitehead's minimization algorithm, given a freely reduced word ${\displaystyle w\in F_{n}}$, finds an automorphically minimal ${\displaystyle [v]}$ such that ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})v.$$}$

이 알고리즘은 다음과 같이 진행된다.감안할 때 w∈ Fn{\displaystylew\in F_{n}},}. ∈ Aut(Fn){\displaystyle\tau\in \operatorname{Aut}(F_{n})⁡이 화이트 헤드 자기 동형 τ 존재하는 만약 제가{\displaystyle w_{나는}w}이미};‖ wi. 수표가‖τ(wi)‖ X<>생성된다 w1)w{\displaystyle w_{1}=w을 ${\$$displaystyle \\\{i}\{X}<\w_{i}\{X$ (${\displaystyle F_{}}$ n {\$displaystyle$F_{n}}의 Whitehead 자동화 세트가 유한하므로$$ 이 상태를 확인할 수 있다.)이러한 $\tau {\displaystyle }$ ${\displaystyle \tau }$이(가) 있는$$ 경우 ${\displaystyle w_{}}$ i${\displaystyle {}_{}}$+ 1${\displaystyle {}_{}}$= ${\displaystyle \tau ({}_{}}$ ${\displaystyle i_{}}$) ${\displaystyle w_{i+1}=\tau(w_{i})$를 넣고 다음$$ 단계로 이동하십시오.If no such ${\displaystyle \tau }$ exists, declare that ${\displaystyle [w_{i}]}$ is automorphically minimal, with ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w_{i}}$, and terminate the algorithm.

Part (1) of the Peak Reduction Lemma implies that the Whitehead's minimization algorithm terminates with some ${\displaystyle w_{m}}$, where ${\displaystyle m\leq \ w\ _{X}}$, and that then ${\displaystyle [w_{m}]}$ is indeed automorphically minimal and satisfies ${\displaystyle \mathrm{Aut}(F_n)w=\mathrm{Aut}}$${\displaystyle (F_{}}$ n${\displaystyle {}_{}}$) ${\displaystyle {}_{}}$ ${\displaystyle m_{}}$ ${\$

자동형 등가성 문제에 대한 화이트헤드의 알고리즘

Whitehead's algorithm for the automorphic equivalence problem, given ${\displaystyle w,w'\in F_{n}}$ decides whether or not ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$.

알고리즘은 다음과 같이 진행한다.Given ${\displaystyle w,w'\in F_{n}}$, first apply the Whitehead minimization algorithm to each of ${\displaystyle w,w'}$ to find automorphically minimal ${\displaystyle [v],[v']}$ such that ${\displaystyle \operatorname {Aut} (F_{n})w=$$\operatorname {Aut} (F_{n})v}$ and ${\displaystyle \operatorname {Aut} (F_{n})w'=\operatorname {Aut} (F_{n})v'}$. If ${\displaystyle \ v\ _{X}\neq \ v'\ _{X}}$, declare that ${\displaystyle \operatorname {$$자동}(F_{n})w\neq \operatorname {Aut}(F_{n}w$')을$$ 선택하고 알고리즘을 종료하십시오.이제 $\Vert {\displaystyle }$ ${\displaystyle v}$ ${\displaystyle {}_{}}$ ${\displaystyle X_{}}$= ${\displaystyle \Vert }$ ${\displaystyle {}^{}}$ ${\displaystyle \Vert {}_{}}$ v ${\displaystyle X_{}}$= ${\displaystyle t}$ ${\displaystyle \ge }$ ${\displaystyle 0}$ ${\displaystyle$\$\v\{X}=\ v'\{X}=t\geq$ 0$\}$이라고 가정합시다.그런 다음 Whitehead 이동 순서가 유한한지 확인하십시오. $\tau$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \mathrm{Aut}}$ ${\displaystyle }$(${\displaystyle {Fn}_{}}$) ${\displaystyle \tau _{1},\dots ,\tau \{k}\in \operatorname {Aut}(F_{n}).$

${\displaystyle \tau _{k}\put \tau _{1}(v)=v'}$

그리고

${\displaystyle \tau \{i}\dots \tau _{1}(v)\ _{X}=\v\ _{X}=t{\text{{} for }i=1,\dots,k.}$

이$$ ${\displaystyle {조건}_{}}$은 F$$n {\$displaystyle$F_{$n}$에서 길이$$t {\$displaystyle$t}의 주기적 감소 단어 수가 유한하므로 확인할$$ 수 있다.More specifically, using the breadth-first approach, one constructs the connected components ${\displaystyle {\mathcal {A}}[v],{\mathcal {A}}[v']}$ of the automorphism graph and checks if ${\displaystyle {\mathcal {A}}[v]\cap {\mathcal {A}}[v']=\varnothing }$.

이러한 시퀀스가 존재할 경우, ${\displaystyle \mathrm{Aut}}$ ${\displaystyle }$(${\displaystyle {}_{}}$ ${\displaystyle n_{}}$) w${\displaystyle }$= ${\displaystyle \mathrm{Auto}}$ ${\displaystyle }$ ${\displaystyle (F_{}}$ n${\displaystyle {}_{}}$) ${\displaystyle {}^{}}$ w w ${\displaystyle {\prime }^{}}$ ${\$을$$선언하고 알고리즘을 종료하십시오.이러한 시퀀스가 없는 경우, ${\displaystyle \mathrm{Aut}}$ aut${\displaystyle }$(F${\displaystyle }$n${\displaystyle {}_{}}$) ${\displaystyle w_{}}$ ${\displaystyle w}$ Auto ${\displaystyle }$(${\displaystyle {}_{}}$ n${\displaystyle {}_{}}$) ${\displaystyle w_{}}$ w ${\$을 선언하고$$ 알고리즘을 종료하십시오.

The Peak Reduction Lemma implies that Whitehead's algorithm correctly solves the automorphic equivalence problem in ${\displaystyle F_{n}}$. Moreover, if ${\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}$, the algorithm actually produces (as a composition ofWhitehead movements) 자동형성 $\phi {\displaystyle }$ ${\displaystyle \mathrm{Auto}}$ ${\displaystyle }$($){\displaystyle \varphi \in$ \$varphi$ \in $\operatorname {Aut}(F_$${n$$})$과 같은 $w$ ${\displaystyle )}$= w = ${\displaystyle {}^{}}$ = w =$w$

Whitehead 알고리즘의 계산 복잡성

• If the rank ${\displaystyle n\geq 2}$ of ${\displaystyle F_{n}}$ is fixed, then, given ${\displaystyle w\in F_{n}}$, the Whitehead minimization algorithm always terminates in quadratic time ${\displaystyle O( w _{X}^{2})}$ and produces an automorphically minimal cyclically하셨는지 말 u∈ Fn{\displaystyleu\in F_{n}}w가 Aut ⁡(Fn))Aut ⁡(Fn)너{\displaystyle \operatorname{Aut}(F_{n})w=\operatorname{Aut}(F_{n})u}.[10] 해도 n{n\displaystyle}은 고려해서 고정된,(에 대한 적응)화이트 헤드 최소화 알고리즘에 입력 w∈ F. n$$${\$$displaystyle w\in F_{n}}$ 시간 O(${\displaystyle {\mathrm{}}_{}^{}}$ X $2n{\displaystyle }$3${\displaystyle {}^{}}$) {\$displaystyle O(w _{X}^{2}n^{3})$에 종료됨$.$^[11]
• If the rank ${\displaystyle n\geq 3}$ of ${\displaystyle F_{n}}$ is fixed, then for an automorphically minimal ${\displaystyle u\in F_{n}}$ constructing the graph ${\displaystyle {\mathcal {A}}[u]}$ takes ${\displaystyle O\left(\ u\ _{X}\cdot$$\#V{\mathcal {A}}[u]\right)}$ time and thus requires a priori exponential time in ${\displaystyle u _{X})}$. For that reason Whitehead's algorithm for deciding, given ${\displaystyle w,w'\in F_{n}}$, whether or not ${\displaystyle \operatorname {A$$ut}(F_{n}=\operatorname {Aut}(F_{n}w'})$은$$${\displaystyle 최대}$ 지수 시간인 최대${\displaystyle }${${\displaystyle w}$ ${\displaystyle {}_{}}$, w${\displaystyle {}_{}{}_{}{}^{}}$X${\displaystyle {}_{}}$} ${\displaystyle \max\{X},$ w'$_{X}\}}}$에서 실행된다$.$
• For ${\displaystyle n=2}$, Khan proved that for an automorphically minimal ${\displaystyle u\in F_{2}}$, the graph ${\displaystyle {\mathcal {A}}[u]}$ has at most ${\displaystyle O\left(\ u\ _{X}\right)}$ vertices and hence constructing the graph ${\displa$∈ F2{\displaystyle w,w'\in F_{2}}max에서 2차 시간{wX, 내력Ystyle{{A\mathcal}}[u]}2차 시간에 너 X{\displaystyle u_{X}}.[12]에 결과적으로, F2에서 자기 동형 등가성 문제에 대한 화이트 헤드의 알고리즘{\displaystyle F_{2}}, 주어진 w, w′ 할 수 있다.${\displaystyle w^{}}$ ${\displaystyle {\prime }^{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \max\{w_{X},$w$' _{X$

애플리케이션, 일반화 및 관련 결과

• 화이트헤드의 알고리즘은 풀 수 있도록 적응될 수 있다. $모든{\displaystyle }$ ${\displaystyle {고정}_{}}$ m${\displaystyle }${$$1 {\$displaystyle$ m\$geq$ 1$\}$에 대해,$$F n {\$displaystyle$F_${n$}}의 선택 항목 m-tuple 및$$ $F{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$의 결합 등급에 대한 m-tules의 자동 동등성 문제를 다룬다$.$~의 I.4
• McCool used Whitehead's algorithm and the peak reduction to prove that for any ${\displaystyle w\in F_{n}}$ the stabilizer ${\displaystyle \operatorname {Stab} _{\operatorname {Out} (F_{n})}([w])}$ is finitely presentable, and obtained a similar results for ${\dis$conjugacy 수업의 F와{\displaystyle F_{n}에 m-tuples의Playstyle\operatorname{아웃}(F_{n})}-stabilizers}.[14]맥쿨 또한 Aut}화이트 헤드 automorphisms의 generat은 집합과(Fn){\displaystyle \operatorname{Aut}(F_{n})⁡ 그 그룹의 유한 발표를 건설하기 위해 피크 감소 방법을 사용하였다.ing그리고 나서 그는 이 프레젠테이션을 ^[16]닐슨으로 인해 원래 닐슨으로 인해 발생된 ${\displaystyle \mathrm{Aut}}$ ${\displaystyle }$(${\displaystyle {Fn}_{}}$) ${\displaystyle \operatorname {Aut} (F_{n})}$에 대한 유한한 프레젠테이션을 복구하기 위해 사용했다$.$^[15]
• Gersten obtained a variation of Whitehead's algorithm, for deciding, given two finite subsets ${\displaystyle S,S'\subseteq F_{n}}$, whether the subgroups ${\displaystyle H=\langle S\rangle ,H'=\langle S'\rangle \leq F_{n}}$ are automorphically equivalent, that is, whether there는 $\phi {\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle \mathrm{aut}(}$ (${\displaystyle {Fn}_{}}$ ${\displaystyle {}_{}}${\$displaystyle \varphi \in \operatorname {Aut}(F_{n})$과 같은 φ ${\displaystyle (H}$ ${\displaystyle )}$= ${\displaystyle {}^{}}$′ ${\$이(가) 있다$.$^[17]
• 화이트헤드의 알고리즘과 피크 감소는 컬러와 보그트만이 컬러-보그만 아우터 공간이 수축 가능하다는 증거에 핵심적인 역할을 한다.^[9]
• 콜린스와 지스창은 화이트헤드의 피크 감소와 화이트헤드의 프리 프로덕트 내 자동 등가 알고리즘을 아날로그로 얻었다.^[18][19]
• Gilbert는 피크 감소 보조정리 버전을 사용하여 $무료{\displaystyle }$ 제품 ${\displaystyle G_{}^{}}$=${\displaystyle {}_{=}^{}}$ ${\displaystyle {\mathrm{i}}_{}^{}}$ = 1m ${\displaystyle {Gi}_{}}${\$displaystyle$ G$=\ast {i=1}^{m}G_{i$^[20]의 오토모르프 그룹 ${\displaystyle \mathrm{Aut}}$ $⁡$(${\displaystyle G}$) ${\displaysty$ \$operatorname {Aut}}}$에 대한 프레젠테이션을 구성했다.
• Levitt와 Vogtmann은 S {\displaystyle $S}$이(가$)$ 닫힌 쌍곡면인 그룹 $G{\displaystyle }$= ${\displaystyle {}_{}}$ 1 ${\displaystyle {}_{}S}$ $){\displaystyle G=\pi _{1}(S)$에서 자동 등가성 문제(선택, 결합 등급의 m-tule)를 저장하기 위한 Whitehead형 알고리즘을 생성했다.^[21]
• If an element ${\displaystyle w\in F_{n}=F(X)}$ chosen uniformly at random from the sphere of radius ${\displaystyle m\geq 1}$ in ${\displaystyle F(X)}$, then, with probability tending to 1 exponentially fast as ${\displaystyle m\to \infty }$, the conjugacy class ${\displ$$aystyle [w]}$은(는) 이미 자동적으로 최소로 되어$$ 있고$,{\displaystyle \mathrm{}}$ 더욱이 # ${\displaystyle V}$ ${\displaystyle A}$[ ${\displaystyle w}$ ${\displaystyle ]}$= ${\displaystyle O}$ (${\displaystyle \Vert }$ ${\displaystyle w}$ ${\displaystyle {}_{}}$ ${\displaystyle X_{}}$)${\displaystyle }$= ${\displaystyle O}$( m$){\V{\mathcal{A}}=$$O\left(\ w\ _{X}\right)=O(m)}$. Consequently, if ${\displaystyle w,w'\in F_{n}}$ are two such ``generic" elements, Whitehead's algorithm decides whether ${\displaystyle w,w'}$ are automorphically equivalent in linear time in ${\displaystyle \max\{ w _{X},$$w' _{X}\}}$^[10].
• 위의 결과와 유사하게 F ${\displaystyle n_{}}$ ${\$의 미세하게 생성된 하위 그룹의 자동형 최소성 생성에 대한 결과와 유사하다$.$^[22]
• 이 대통령은 만약 ∈ FnxF({\displaystyleu\in F_{n}(X)}은 주기적으로 줄어든다는 말[u]{\displaystyle[u]}automorphically 최소입니다 등 만약 때마다)나는,)j, i<. j{\displaystyle x_{나는},x_{j},i<. j}둘 다 너{\displaystyle u}또는 너 − 1{\displaystyle u^{에서 발생하는-것을 증명했다.1}}then the total number of occurrences of ${\displaystyle x_{i}^{\pm 1}}$ in ${\displaystyle u}$ is smaller than the number of occurrences of ${\displaystyle x_{i}^{\pm 1}}$, then ${\displaystyle \#V{\mathcal {A}}[u]}$ is bounded above by a polynomial of degree ${\disp$만약 w2n-3}너 X{\displaystyle u_{X}}.[23]에Laystyle 따라서 w′ ∈ F, n≥ 3{\displaystyle w,w'\in F_{n},n\geq 3}이 w{w\displaystyle}automorphically 위의 속성을 가진 너{\displaystyle u}에 해당합니다 그러한, 화이트 헤드의 알고리즘을 결정하는지 여부 및 w, w.′${\displaystyle w,w'}$은(는) $시간{\displaystyle }$ O$(${${\displaystyle {}_{}^{}}$ X ${\displaystyle {\mathrm{2n}}_{}^{}}$- ${\displaystyle 3_{}^{}}$,${\displaystyle {}_{}^{}w{}^{}}$ ${\displaystyle {\prime }^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle \})}$에서 자동적으로 동일하다$(\backslash$$displaystyle O\left(\max\{X}^{2n-3}, w')$
• 브레이드 그룹에서 결합 문제를 해결하기 위한 가르사이드 알고리즘은 화이트헤드의 알고리즘과 유사한 일반 구조를 가지며, 화이트헤드 동작의 역할을 하는 '사이클링 동작'이 있다.^[24]
• 클리포드와 골드 스틴, Z⊆ Fn{\displaystyle Z\subseteq F_{n}}H)⟨ Z⟩ ≤ Fn{\displaystyle H=\langle Z\rangle \leq F_{n}}는 .mw-parser-output .vanchor&gt가 들어 있는지 여부가 서브 그룹 외모를 결정하는 유한 부분 집합을 주어진 알고리즘은 target~.vanchor-text{backgro를 생산하기 위해 Whitehead-algorithm에 기반한 기술을 사용했다.Und-color:Fn의#b1d2ff}원시적 요소,{\displaystyle F_{n},.$}$은(는) F ${\displaystyle n_{}}$. ${\displaystyle F_{n}$의 자유 생성 세트의 요소임.$}$^[25]
• 데이는 직각 아르틴 그룹의 원소들의 자동적 등가성을 위해 화이트헤드의 알고리즘과 화이트헤드의 피크 감소의 유사점을 얻었다.^[26]

참조

추가 읽기

• Heiner Zieschang, On the Nielsen and Whitehead methods in combinatorial group 이론 및 위상.단체—1994년 (부산), 317–337, 1994년 8월 18–25일 부산대학교에서 열린 제3차 단체 이론 국제 회의의 진행.A. C. Kim과 D. L. Johnson이 편집함. 1995년 베를린 드 그루이터; ISBN 3-11-014793-9 MR1476976
• 화이트헤드의 3-manifold 모델을 이용한 화이트헤드의 알고리즘에 대한 카렌 보그만의 강의 노트