Алгоритм Уайтхеда

Алгоритм Уайтхеда — математический алгоритм в теории групп для решения проблемы автоморфной эквивалентности в свободной группе конечного ранга F n . Алгоритм основан на классической статье 1936 года Дж. Х. Уайтхеда . [1] До сих пор неизвестно (за исключением случая n  = 2), имеет ли алгоритм Уайтхеда полиномиальную временную сложность .

Постановка проблемы

Пусть — свободная группа ранга со свободным базисом . Проблема автоморфизма , или проблема автоморфной эквивалентности для , спрашивает, существует ли автоморфизм такой, что . Ф н = Ф ( х 1 , … , х н ) {\displaystyle F_{n}=F(x_{1},\dots ,x_{n})} н ≥ 2 {\displaystyle n\geq 2} Х = { х 1 , … , х н } {\displaystyle X=\{x_{1},\точки ,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 {Выход} (F_{n})[w]=\operatorname {Выход} (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 [ш]} Ф н {\displaystyle F_{n}}

История

Проблема автоморфизма для была алгоритмически решена Дж. Х. К. Уайтхедом в классической статье 1936 года [1] , и его решение стало известно как алгоритм Уайтхеда. Уайтхед использовал топологический подход в своей статье. А именно, рассмотрим 3-многообразие , связную сумму копий . Тогда , и, более того, с точностью до частного по конечной нормальной подгруппе, изоморфной , группа классов отображения равна ; см. [2] Различные свободные базисы из могут быть представлены изотопическими классами «систем сфер» в , а циклически приведенная форма элемента , а также граф Уайтхеда из , могут быть «считаны» из того, как петля в общем положении, представляющая пересекает сферы в системе. Движения Уайтхеда могут быть представлены определенными видами топологических «перестановочных» движений, изменяющих систему сфер. [3] [4] [5] Ф н {\displaystyle F_{n}} М н = # я = 1 н С 2 × С 1 {\displaystyle M_{n}=\#_{i=1}^{n}\mathbb {S} ^{2}\times \mathbb {S} ^{1}} н {\displaystyle n} С 2 × С 1 {\displaystyle \mathbb {S} ^{2}\times \mathbb {S} ^{1}} π 1 ( М н ) ≅ Ф н {\displaystyle \пи _{1}(М_{н})\конг Ф_{н}} З 2 н {\displaystyle \mathbb {Z} _{2}^{n}} М н {\displaystyle M_{n}} Вне ⁡ ( Ф н ) {\displaystyle \operatorname {Выход} (F_{n})} Ф н {\displaystyle F_{n}} М н {\displaystyle M_{n}} ж ∈ Ф н {\displaystyle w\in F_{n}} [ ж ] {\displaystyle [ш]} [ ж ] {\displaystyle [ш]}

Впоследствии Рапапорт [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'}

Автоморфизмы Уайтхеда

Автоморфизм Уайтхеда , или движение Уайтхеда , — это автоморфизм одного из следующих двух типов: Ф н {\displaystyle F_{n}} τ ∈ Авт ⁡ ( Ф н ) {\displaystyle \tau \in \operatorname {Aut} (F_{n})} Ф н {\displaystyle F_{n}}

  1. Существует перестановка такая , что для Такая называется автоморфизмом Уайтхеда первого рода . σ ∈ С н {\displaystyle \sigma \in S_{n}} { 1 , 2 , … , н } {\displaystyle \{1,2,\точки ,n\}} я = 1 , … , н {\displaystyle i=1,\точки,n} τ ( х я ) = х σ ( я ) ± 1 {\displaystyle \tau (x_{i})=x_{\sigma (i)}^{\pm 1}} τ {\displaystyle \тау}
  2. Существует элемент , называемый множителем , такой, что для каждого Такой называется автоморфизмом Уайтхеда второго рода . Поскольку является автоморфизмом , то в этом случае следует, что . а ∈ Х ± 1 {\displaystyle a\in X^{\pm 1}} х ∈ Х ± 1 {\displaystyle x\in X^{\pm 1}} τ ( х ) ∈ { х , х а , а − 1 х , а − 1 х а } . {\displaystyle \tau (x)\in \{x,xa,a^{-1}x,a^{-1}xa\}.} τ {\displaystyle \тау} τ {\displaystyle \тау} Ф н {\displaystyle F_{n}} τ ( а ) = а {\displaystyle \тау (а)=а}

Часто для автоморфизма Уайтхеда соответствующий внешний автоморфизм в также называют автоморфизмом Уайтхеда или движением Уайтхеда. τ ∈ Авт ⁡ ( Ф н ) {\displaystyle \tau \in \operatorname {Aut} (F_{n})} Вне ⁡ ( Ф н ) {\displaystyle \operatorname {Выход} (F_{n})}

Примеры

Позволять . Ф 4 = Ф ( х 1 , х 2 , х 3 , х 4 ) {\displaystyle F_{4}=F(x_{1},x_{2},x_{3},x_{4})}

Пусть — гомоморфизм такой, что Тогда на самом деле является автоморфизмом , и, более того, является автоморфизмом Уайтхеда второго рода с множителем . τ : Ф 4 → Ф 4 {\displaystyle \tau :F_{4}\to F_{4}} τ ( x 1 ) = x 2 x 1 , τ ( x 2 ) = x 2 , τ ( x 3 ) = x 2 x 3 x 2 − 1 , τ ( x 4 ) = x 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 } F 4 {\displaystyle F_{4}} τ {\displaystyle \tau } a = x 2 − 1 {\displaystyle a=x_{2}^{-1}}

Пусть — гомоморфизм такой, что Тогда — фактически внутренний автоморфизм , заданный сопряжением с помощью , и, более того, — автоморфизм Уайтхеда второго рода с множителем . τ ′ : F 4 → F 4 {\displaystyle \tau ':F_{4}\to F_{4}} τ ′ ( x 1 ) = x 1 , τ ′ ( x 2 ) = x 1 − 1 x 2 x 1 , τ ′ ( x 3 ) = x 1 − 1 x 3 x 1 , τ ′ ( x 4 ) = x 1 − 1 x 4 x 1 {\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 '} F 4 {\displaystyle F_{4}} x 1 {\displaystyle x_{1}} τ ′ {\displaystyle \tau '} a = x 1 {\displaystyle a=x_{1}}

Автоморфно минимальные и минимальные элементы Уайтхеда

Для класс сопряженности называется автоморфно минимальным, если для каждого имеем . Также класс сопряженности называется минимальным по Уайтхеду , если для каждого хода Уайтхеда имеем . w ∈ F n {\displaystyle w\in F_{n}} [ w ] {\displaystyle [w]} φ ∈ Aut ⁡ ( F n ) {\displaystyle \varphi \in \operatorname {Aut} (F_{n})} ‖ w ‖ X ≤ ‖ φ ( w ) ‖ X {\displaystyle \|w\|_{X}\leq \|\varphi (w)\|_{X}} [ w ] {\displaystyle [w]} τ ∈ Aut ⁡ ( F n ) {\displaystyle \tau \in \operatorname {Aut} (F_{n})} ‖ w ‖ X ≤ ‖ τ ( w ) ‖ X {\displaystyle \|w\|_{X}\leq \|\tau (w)\|_{X}}

Таким образом, по определению, если является автоморфно минимальным, то он также является минимальным по Уайтхеду. Оказывается, обратное также верно. [ w ] {\displaystyle [w]}

«Лемма о пиковой редукции» Уайтхеда

Следующее утверждение называется «леммой о пиковой редукции» Уайтхеда, см. предложение 4.20 в [8] и предложение 1.2 в: [10]

Пусть . Тогда справедливо следующее: w ∈ F n {\displaystyle w\in F_{n}}

  1. Если не является автоморфно минимальным, то существует автоморфизм Уайтхеда такой, что . [ w ] {\displaystyle [w]} τ ∈ Aut ⁡ ( F n ) {\displaystyle \tau \in \operatorname {Aut} (F_{n})} ‖ τ ( w ) ‖ X < ‖ w ‖ X {\displaystyle \|\tau (w)\|_{X}<\|w\|_{X}}
  1. Предположим, что является автоморфно минимальным, и что другой класс сопряженности также является автоморфно минимальным. Тогда тогда и только тогда, когда и существует конечная последовательность движений Уайтхеда такая, что и [ w ] {\displaystyle [w]} [ w ′ ] {\displaystyle [w']} Aut ⁡ ( F n ) w = Aut ⁡ ( F n ) w ′ {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'} ‖ w ‖ X = ‖ w ′ ‖ X {\displaystyle \|w\|_{X}=\|w'\|_{X}} τ 1 , … , τ k ∈ Aut ⁡ ( F n ) {\displaystyle \tau _{1},\dots ,\tau _{k}\in \operatorname {Aut} (F_{n})} τ k ⋯ τ 1 ( w ) = w ′ {\displaystyle \tau _{k}\cdots \tau _{1}(w)=w'} ‖ τ i ⋯ τ 1 ( w ) ‖ X = ‖ w ‖ X  for  i = 1 , … , k . {\displaystyle \|\tau _{i}\cdots \tau _{1}(w)\|_{X}=\|w\|_{X}{\text{ for }}i=1,\dots ,k.}

Часть (1) леммы о пиковой редукции подразумевает, что класс сопряженности является минимальным по Уайтхеду тогда и только тогда, когда он автоморфно минимален. [ w ] {\displaystyle [w]}

Граф автоморфизма

Граф автоморфизмов графа — это граф с множеством вершин, являющимся множеством классов сопряженности элементов . Две различные вершины смежны в , если и существует автоморфизм Уайтхеда такой, что . Для вершины из связная компонента в обозначается . A {\displaystyle {\mathcal {A}}} F n {\displaystyle F_{n}} [ u ] {\displaystyle [u]} u ∈ F n {\displaystyle u\in F_{n}} [ u ] , [ v ] {\displaystyle [u],[v]} A {\displaystyle {\mathcal {A}}} ‖ u ‖ X = ‖ v ‖ X {\displaystyle \|u\|_{X}=\|v\|_{X}} τ {\displaystyle \tau } [ τ ( u ) ] = [ v ] {\displaystyle [\tau (u)]=[v]} [ u ] {\displaystyle [u]} A {\displaystyle {\mathcal {A}}} [ u ] {\displaystyle [u]} A {\displaystyle {\mathcal {A}}} A [ u ] {\displaystyle {\mathcal {A}}[u]}

График Уайтхеда

Для с циклически редуцированной формой граф Уайтхеда является помеченным графом с множеством вершин , где для существует соединение ребер и с меткой или «весом» , который равен числу различных вхождений подслов, считываемых циклически в . (В некоторых версиях графа Уайтхеда включаются только ребра с .) 1 ≠ w ∈ F n {\displaystyle 1\neq w\in F_{n}} u {\displaystyle u} Γ [ w ] {\displaystyle \Gamma _{[w]}} X ± 1 {\displaystyle X^{\pm 1}} x , y ∈ X ± 1 , x ≠ y {\displaystyle x,y\in X^{\pm 1},x\neq y} x {\displaystyle x} y {\displaystyle y} n ( { x , y } ; [ w ] ) {\displaystyle n(\{x,y\};[w])} x − 1 y , y − 1 x {\displaystyle x^{-1}y,y^{-1}x} u {\displaystyle u} n ( { x , y } ; [ w ] ) > 0 {\displaystyle n(\{x,y\};[w])>0}

Если — автоморфизм Уайтхеда, то изменение длины можно выразить как линейную комбинацию с целочисленными коэффициентами, определяемыми , весов в графе Уайтхеда . См. предложение 4.16 в гл. I [8] . Этот факт играет ключевую роль в доказательстве результата Уайтхеда о пиковой редукции. τ ∈ Aut ⁡ ( F n ) {\displaystyle \tau \in \operatorname {Aut} (F_{n})} ‖ τ ( w ) ‖ X − ‖ w ‖ X {\displaystyle \|\tau (w)\|_{X}-\|w\|_{X}} τ {\displaystyle \tau } n ( { x , y } ; [ w ] ) {\displaystyle n(\{x,y\};[w])} Γ [ w ] {\displaystyle \Gamma _{[w]}}

Алгоритм минимизации Уайтхеда

Алгоритм минимизации Уайтхеда , учитывая свободно сокращенное слово , находит автоморфно минимальное такое, что w ∈ F n {\displaystyle w\in F_{n}} [ v ] {\displaystyle [v]} Aut ⁡ ( F n ) w = Aut ⁡ ( F n ) v . {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})v.}

Этот алгоритм работает следующим образом. Дано , положить . Если уже построено, проверить, существует ли автоморфизм Уайтхеда такой, что . (Это условие можно проверить, поскольку множество автоморфизмов Уайтхеда конечно.) Если такой существует, положить и перейти к следующему шагу. Если такого не существует, объявить, что является автоморфно минимальным, с , и завершить алгоритм. w ∈ F n {\displaystyle w\in F_{n}} w 1 = w {\displaystyle w_{1}=w} w i {\displaystyle w_{i}} τ ∈ Aut ⁡ ( F n ) {\displaystyle \tau \in \operatorname {Aut} (F_{n})} ‖ τ ( w i ) ‖ X < ‖ w i ‖ X {\displaystyle \|\tau (w_{i})\|_{X}<\|w_{i}\|_{X}} F n {\displaystyle F_{n}} τ {\displaystyle \tau } w i + 1 = τ ( w i ) {\displaystyle w_{i+1}=\tau (w_{i})} τ {\displaystyle \tau } [ w i ] {\displaystyle [w_{i}]} Aut ⁡ ( F n ) w = Aut ⁡ ( F n ) w i {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w_{i}}

Часть (1) леммы о пиковой редукции подразумевает, что алгоритм минимизации Уайтхеда завершается при некотором , где , и что тогда он действительно автоморфно минимален и удовлетворяет . w m {\displaystyle w_{m}} m ≤ ‖ w ‖ X {\displaystyle m\leq \|w\|_{X}} [ w m ] {\displaystyle [w_{m}]} Aut ⁡ ( F n ) w = Aut ⁡ ( F n ) w m {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w_{m}}

Алгоритм Уайтхеда для проблемы автоморфной эквивалентности

Алгоритм Уайтхеда для задачи автоморфной эквивалентности решает, задано ли . w , w ′ ∈ F n {\displaystyle w,w'\in F_{n}} Aut ⁡ ( F n ) w = Aut ⁡ ( F n ) w ′ {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'}

Алгоритм выполняется следующим образом. Дано , сначала применим алгоритм минимизации Уайтхеда к каждому из , чтобы найти автоморфно минимальный такой, что и . Если , объявить, что и завершить алгоритм. Предположим теперь, что . Затем проверить, существует ли конечная последовательность ходов Уайтхеда такая, что и w , w ′ ∈ F n {\displaystyle w,w'\in F_{n}} w , w ′ {\displaystyle w,w'} [ v ] , [ v ′ ] {\displaystyle [v],[v']} Aut ⁡ ( F n ) w = Aut ⁡ ( F n ) v {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})v} Aut ⁡ ( F n ) w ′ = Aut ⁡ ( F n ) v ′ {\displaystyle \operatorname {Aut} (F_{n})w'=\operatorname {Aut} (F_{n})v'} ‖ v ‖ X ≠ ‖ v ′ ‖ X {\displaystyle \|v\|_{X}\neq \|v'\|_{X}} Aut ⁡ ( F n ) w ≠ Aut ⁡ ( F n ) w ′ {\displaystyle \operatorname {Aut} (F_{n})w\neq \operatorname {Aut} (F_{n})w'} ‖ v ‖ X = ‖ v ′ ‖ X = t ≥ 0 {\displaystyle \|v\|_{X}=\|v'\|_{X}=t\geq 0} τ 1 , … , τ k ∈ Aut ⁡ ( F n ) {\displaystyle \tau _{1},\dots ,\tau _{k}\in \operatorname {Aut} (F_{n})} τ k … τ 1 ( v ) = v ′ {\displaystyle \tau _{k}\dots \tau _{1}(v)=v'} ‖ τ i … τ 1 ( v ) ‖ X = ‖ v ‖ X = t  for  i = 1 , … , k . {\displaystyle \|\tau _{i}\dots \tau _{1}(v)\|_{X}=\|v\|_{X}=t{\text{ for }}i=1,\dots ,k.}

Это условие можно проверить, поскольку число циклически сокращенных слов длины в конечно. Более конкретно, используя подход в ширину , строятся связные компоненты графа автоморфизмов и проверяется, выполняется ли . t {\displaystyle t} F n {\displaystyle F_{n}} A [ v ] , A [ v ′ ] {\displaystyle {\mathcal {A}}[v],{\mathcal {A}}[v']} A [ v ] ∩ A [ v ′ ] = ∅ {\displaystyle {\mathcal {A}}[v]\cap {\mathcal {A}}[v']=\varnothing }

Если такая последовательность существует, объявить , что и завершить алгоритм. Если такой последовательности не существует, объявить, что и завершить алгоритм. Aut ⁡ ( F n ) w = Aut ⁡ ( F n ) w ′ {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'} Aut ⁡ ( F n ) w ≠ Aut ⁡ ( F n ) w ′ {\displaystyle \operatorname {Aut} (F_{n})w\neq \operatorname {Aut} (F_{n})w'}

Лемма о пиковой редукции подразумевает, что алгоритм Уайтхеда правильно решает проблему автоморфной эквивалентности в . Более того, если , алгоритм фактически производит (как композицию движений Уайтхеда) автоморфизм такой, что . F n {\displaystyle F_{n}} Aut ⁡ ( F n ) w = Aut ⁡ ( F n ) w ′ {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'} φ ∈ Aut ⁡ ( F n ) {\displaystyle \varphi \in \operatorname {Aut} (F_{n})} φ ( w ) = w ′ {\displaystyle \varphi (w)=w'}

Вычислительная сложность алгоритма Уайтхеда

  • Если ранг фиксирован , то при заданном алгоритм минимизации Уайтхеда всегда завершается за квадратичное время и производит автоморфно минимальное циклически сокращенное слово такое, что . [10] Более того, даже если не считается фиксированным, (адаптация) алгоритма минимизации Уайтхеда на входе завершается за время . [11] n ≥ 2 {\displaystyle n\geq 2} F n {\displaystyle F_{n}} w ∈ F n {\displaystyle w\in F_{n}} O ( | w | X 2 ) {\displaystyle O(|w|_{X}^{2})} u ∈ F n {\displaystyle u\in F_{n}} Aut ⁡ ( F n ) w = Aut ⁡ ( F n ) u {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})u} n {\displaystyle n} w ∈ F n {\displaystyle w\in F_{n}} O ( | w | X 2 n 3 ) {\displaystyle O(|w|_{X}^{2}n^{3})}
  • Если ранг фиксирован , то для автоморфно минимального построения графа требуется время и, таким образом, априори требуется экспоненциальное время в . По этой причине алгоритм Уайтхеда для принятия решения, заданного , выполняется ли или нет , самое большее за экспоненциальное время в . n ≥ 3 {\displaystyle n\geq 3} F n {\displaystyle F_{n}} u ∈ F n {\displaystyle u\in F_{n}} A [ u ] {\displaystyle {\mathcal {A}}[u]} O ( ‖ u ‖ X ⋅ # V A [ u ] ) {\displaystyle O\left(\|u\|_{X}\cdot \#V{\mathcal {A}}[u]\right)} | u | X ) {\displaystyle |u|_{X})} w , w ′ ∈ F n {\displaystyle w,w'\in F_{n}} Aut ⁡ ( F n ) w = Aut ⁡ ( F n ) w ′ {\displaystyle \operatorname {Aut} (F_{n})w=\operatorname {Aut} (F_{n})w'} max { | w | X , | w ′ | X } {\displaystyle \max\{|w|_{X},|w'|_{X}\}}
  • Для Хан доказал, что для автоморфно минимального граф имеет не более вершин и, следовательно, построение графа может быть выполнено за квадратичное время за . [12] Следовательно, алгоритм Уайтхеда для задачи автоморфной эквивалентности в , заданный , выполняется за квадратичное время за . n = 2 {\displaystyle n=2} u ∈ F 2 {\displaystyle u\in F_{2}} A [ u ] {\displaystyle {\mathcal {A}}[u]} O ( ‖ u ‖ X ) {\displaystyle O\left(\|u\|_{X}\right)} A [ u ] {\displaystyle {\mathcal {A}}[u]} | u | X {\displaystyle |u|_{X}} F 2 {\displaystyle F_{2}} w , w ′ ∈ F 2 {\displaystyle w,w'\in F_{2}} max { | w | X , | w ′ | X } {\displaystyle \max\{|w|_{X},|w'|_{X}\}}
  • Алгоритм Уайтхеда можно адаптировать для решения, для любого фиксированного , проблемы автоморфной эквивалентности для m -кортежей избранных из и для m -кортежей классов сопряженности из ; см. гл. I.4 из [8] и [13] m ≥ 1 {\displaystyle m\geq 1} F n {\displaystyle F_{n}} F n {\displaystyle F_{n}}
  • МакКул использовал алгоритм Уайтхеда и пиковую редукцию для доказательства того, что для любого стабилизатор конечно представим , и получил аналогичные результаты для -стабилизаторов m -кортежей классов сопряженности в . [14] МакКул также использовал метод пиковой редукции для построения конечного представления группы с набором автоморфизмов Уайтхеда в качестве порождающего множества. [15] Затем он использовал это представление для восстановления конечного представления для , первоначально принадлежащего Нильсену , с автоморфизмами Нильсена в качестве порождающих. [16] w ∈ F n {\displaystyle w\in F_{n}} Stab Out ⁡ ( F n ) ⁡ ( [ w ] ) {\displaystyle \operatorname {Stab} _{\operatorname {Out} (F_{n})}([w])} Out ⁡ ( F n ) {\displaystyle \operatorname {Out} (F_{n})} F n {\displaystyle F_{n}} Aut ⁡ ( F n ) {\displaystyle \operatorname {Aut} (F_{n})} Aut ⁡ ( F n ) {\displaystyle \operatorname {Aut} (F_{n})}
  • Герстен получил вариант алгоритма Уайтхеда для решения, если заданы два конечных подмножества , являются ли подгруппы автоморфно эквивалентными, то есть существует ли такое, что . [17] S , S ′ ⊆ F n {\displaystyle S,S'\subseteq F_{n}} H = ⟨ S ⟩ , H ′ = ⟨ S ′ ⟩ ≤ F n {\displaystyle H=\langle S\rangle ,H'=\langle S'\rangle \leq F_{n}} φ ∈ Aut ⁡ ( F n ) {\displaystyle \varphi \in \operatorname {Aut} (F_{n})} φ ( H ) = H ′ {\displaystyle \varphi (H)=H'}
  • Алгоритм Уайтхеда и пиковая редукция играют ключевую роль в доказательстве Каллера и Фогтмана того, что внешнее пространство Каллера–Фогтмана является стягиваемым . [9]
  • Коллинз и Цишанг получили аналоги пиковой редукции Уайтхеда и алгоритма Уайтхеда для автоморфной эквивалентности в свободных произведениях групп. [18] [19]
  • Гилберт использовал версию леммы о пиковой редукции для построения представления для группы автоморфизмов свободного произведения . [20] Aut ⁡ ( G ) {\displaystyle \operatorname {Aut} (G)} G = ∗ i = 1 m G i {\displaystyle G=\ast _{i=1}^{m}G_{i}}
  • Левитт и Фогтман разработали алгоритм типа Уайтхеда для сохранения проблемы автоморфной эквивалентности (для избранных, m -кортежей элементов и m -кортежей классов сопряженности) в группе , где — замкнутая гиперболическая поверхность. [21] G = π 1 ( S ) {\displaystyle G=\pi _{1}(S)} S {\displaystyle S}
  • Если элемент выбран равномерно случайным образом из сферы радиуса в , то с вероятностью, стремящейся к 1 экспоненциально быстро как , класс сопряженности уже автоморфно минимален и, более того, . Следовательно, если есть два таких ``общих'' элемента, алгоритм Уайтхеда решает, являются ли они автоморфно эквивалентными за линейное время в . [10] w ∈ F n = F ( X ) {\displaystyle w\in F_{n}=F(X)} m ≥ 1 {\displaystyle m\geq 1} F ( X ) {\displaystyle F(X)} m → ∞ {\displaystyle m\to \infty } [ w ] {\displaystyle [w]} # V A [ w ] = O ( ‖ w ‖ X ) = O ( m ) {\displaystyle \#V{\mathcal {A}}[w]=O\left(\|w\|_{X}\right)=O(m)} w , w ′ ∈ F n {\displaystyle w,w'\in F_{n}} w , w ′ {\displaystyle w,w'} max { | w | X , | w ′ | X } {\displaystyle \max\{|w|_{X},|w'|_{X}\}}
  • Аналогичные вышеприведенным результаты справедливы для генеричности автоморфной минимальности для «случайно выбранных» конечно порожденных подгрупп . [22] F n {\displaystyle F_{n}}
  • Ли доказал, что если — циклически сокращенное слово, такое что является автоморфно минимальным, и если всякий раз, когда оба встречаются в или , то общее число вхождений в меньше числа вхождений , то ограничено сверху полиномом степени по . [23] Следовательно, если являются такими, что являются автоморфно эквивалентными некоторым с указанным выше свойством, то алгоритм Уайтхеда решает, являются ли они автоморфно эквивалентными за время . u ∈ F n = F ( X ) {\displaystyle u\in F_{n}=F(X)} [ u ] {\displaystyle [u]} x i , x j , i < j {\displaystyle x_{i},x_{j},i<j} u {\displaystyle u} u − 1 {\displaystyle u^{-1}} x i ± 1 {\displaystyle x_{i}^{\pm 1}} u {\displaystyle u} x i ± 1 {\displaystyle x_{i}^{\pm 1}} # V A [ u ] {\displaystyle \#V{\mathcal {A}}[u]} 2 n − 3 {\displaystyle 2n-3} | u | X {\displaystyle |u|_{X}} w , w ′ ∈ F n , n ≥ 3 {\displaystyle w,w'\in F_{n},n\geq 3} w {\displaystyle w} u {\displaystyle u} w , w ′ {\displaystyle w,w'} O ( max { | w | X 2 n − 3 , | w ′ | X 2 } ) {\displaystyle O\left(\max\{|w|_{X}^{2n-3},|w'|_{X}^{2}\}\right)}
  • Алгоритм Гарсайда для решения проблемы сопряженности в группах кос имеет схожую общую структуру с алгоритмом Уайтхеда, при этом «циклические движения» играют роль движений Уайтхеда. [24]
  • Клиффорд и Голдштейн использовали методы, основанные на алгоритме Уайтхеда, для создания алгоритма, который, учитывая конечное подмножество, решает, содержит ли подгруппа Z ⊆ F n {\displaystyle Z\subseteq F_{n}} H = ⟨ Z ⟩ ≤ F n {\displaystyle H=\langle Z\rangle \leq F_{n}} примитивный элемент , которыйявляется элементом свободного порождающего множества[25] F n , {\displaystyle F_{n},} F n . {\displaystyle F_{n}.}
  • Дэй получил аналоги алгоритма Уайтхеда и пиковой редукции Уайтхеда для автоморфной эквивалентности элементов прямоугольных групп Артина . [26]

Ссылки

  1. ^ ab JHC Whitehead , Об эквивалентных наборах элементов в свободной группе , Ann. of Math. (2) 37:4 (1936), 782–800. MR 1503309
  2. ^ Сухас Пандит, Заметка об автоморфизмах сферического комплекса. 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. ^ Карен Фогтманн , Автоморфизмы свободных групп и внешнего пространства. Труды конференции по геометрической и комбинаторной теории групп, часть I (Хайфа, 2000). Geometriae Dedicata 94 (2002), 1–31; MR 1950871
  5. ^ Эндрю Клиффорд и Ричард З. Голдштейн, Наборы примитивных элементов в свободной группе. Журнал алгебры 357 (2012), 271–278; MR 2905255
  6. ^ Эльвира Рапапорт, О свободных группах и их автоморфизмах . Acta Mathematica 99 (1958), 139–163; MR 0131452
  7. ^ PJ Higgins и RC Lyndon, Эквивалентность элементов при автоморфизмах свободной группы. Журнал Лондонского математического общества (2) 8 (1974), 254–258; MR 0340420
  8. ^ abcde Роджер Линдон и Пол Шупп , Комбинаторная теория групп. Перепечатка издания 1977 года. Классика по математике. Springer-Verlag , Берлин, 2001. ISBN 3-540-41158-5 MR 1812024. 
  9. ^ ab Марк Каллер ; Карен Фогтманн (1986). "Модули графов и автоморфизмы свободных групп" (PDF) . Inventiones Mathematicae . 84 (1): 91– 119. doi :10.1007/BF01388734. MR  0830040. S2CID  122869546.
  10. ^ abcd Илья Капович, Пол Шупп и Владимир Шпильрайн, Общие свойства алгоритма Уайтхеда и жесткость изоморфизма случайных групп с одним соотношением. Pacific Journal of Mathematics 223:1 (2006), 113–140
  11. ^ Абдо Ройг, Энрик Вентура и Паскаль Вайль, О сложности задачи минимизации Уайтхеда. Международный журнал алгебры и вычислений 17:8 (2007), 1611–1634; MR 2378055
  12. ^ Билал Хан, Структура автоморфной сопряженности в свободной группе ранга два . Вычислительная и экспериментальная теория групп, 115–196, Contemp. Math., 349, Американское математическое общество , Провиденс, Род-Айленд, 2004
  13. ^ Сава Крстич, Мартин Люстиг и Карен Фогтманн , Эквивариантный алгоритм Уайтхеда и сопряженность для корней автоморфизмов скручивания Дена . Труды Эдинбургского математического общества (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. ^ Дональд Дж. Коллинз и Хайнер Цишанг , Спасение метода Уайтхеда для бесплатных продуктов. I. Пиковое снижение. Mathematische Zeitschrift 185:4 (1984), 487–504 MR0733769
  19. ^ Дональд Дж. Коллинз и Хайнер Цишанг , Спасение метода Уайтхеда для бесплатных продуктов. II. Алгоритм. Mathematische Zeitschrift 186:3 (1984), 335–361; МР 0744825
  20. ^ Ник Д. Гилберт, Представления группы автоморфизмов свободного произведения . Труды Лондонского математического общества (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 MR2266870
  24. ^ Джоан Бирман , Ки Хёнг Ко и Сан Джин Ли, Новый подход к проблемам слов и сопряженности в группах кос , Advances in Mathematics 139:2 (1998), 322–353; Zbl  0937.20016 MR 1654165
  25. ^ Эндрю Клиффорд и Ричард З. Голдштейн, Подгруппы свободных групп и примитивные элементы. Журнал теории групп 13:4 (2010), 601–611; MR 2661660
  26. ^ Мэтью Дэй, Полнофункциональное снижение пика в прямоугольных группах Артина . Алгебраическая и геометрическая топология 14:3 (2014), 1677–1743 MR 3212581

Дальнейшее чтение

  • Хайнер Цишанг, О методах Нильсена и Уайтхеда в комбинаторной теории групп и топологии . Группы — Корея '94 (Пусан), 317–337, Труды 3-й Международной конференции по теории групп, состоявшейся в Пусанском национальном университете, Пусан, 18–25 августа 1994 г. Под редакцией AC Kim и DL Johnson. de Gruyter, Берлин, 1995; ISBN 3-11-014793-9 MR 1476976 
  • Конспект лекций Карен Фогтманн по алгоритму Уайтхеда с использованием трехмерной модели Уайтхеда
Retrieved from "https://en.wikipedia.org/w/index.php?title=Whitehead%27s_algorithm&oldid=1261540556"