АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1991 г.

вычислим и ,9 -, /?6$ = • допуотим, ЧТО 6 ^ V, * / T , w i'B a f a t f ... f a A . f i ' . . ' По лемме 16 /ie v.K<n44 сопряжены в £-f. (aIQj Решаем <ац; для ^ _ £ и ^ ,., , то есть проверяем фор­ мулу: 3 X'n-i * Ц ' **-< е * ■ X n -ifr-i ЯШ+ h’>bZ+t- Пусть она справедлива. Тогда слово tv/^сопрягаем елементом V ? Получим: к * * '* Л/*** - ft ■■ -jfn -i-tfn -i —f n , где h *+ f = tn~l h * . C a^ jJ Проверяем (a ^ J для слов w ^ u>* , w, . Пусть (а^) не Выполняется. ( a ^ ) Выполняем для tv//J пункт (a c ) . Пусть через конечное число шагов, применяя к пр еобр азтани я 1в,^) - C a ^ j J , полу­ чим слово tV/rt,= Л * , где h * у,' , , .^ n h cty n 1.■ $ z , * K J z , /;г со­ пряжены в (7, , Допустим, что Vt^r^MVt . Тогда вычисляем $ , i Л У (У гУ Пусть Ut,i + E , тогда - ци­ клическая подгруппа с образ.угацим <?,#, - < g h k c f n ..- f r , = W K ,*)> элементы h 0 сопряжены в U, . Теперь проверим формулу П ь ^ М - К Kh n (h t 1 ) tB = f ьоли такое tD сущ ествует, то слова Wt , IVjt сопряжены, в противном случае - н ет. Лемма доказан а. Из лешы 17 вытекает СУЩОГВИЕ 3 . В группе ( J = < < 3 , Р,Ч',Л,(о1,...10^р)=Ш г1: ; ап/1^ где d jifltO , разрешима проблема сопряженности слов. ЛМиМА 1 8 . В группе (?f разрешима проблема степенной сопря­ женности. ДОКАЗАТЕЛЬСТВО. Пусть Wt , _ два произвольных элемента HtyH'jf .llW iH i l , то е с т ь W, =А,у, , . Дели wti tvx * Рл или wh \Nx (F m • то на основании леммы 16 проблема степенной со ­ пряженности этих элементов в <?, сводится к проблеме степенной сопряженности в сомножителе . Пусть Wf e F n , . Тогда по лемме 15 можно эффективна установить, будет ли некоторая степень w, сопряжена с некото­ рым элементом из объединения; если - д а , то получаем предыду­ щий случай. 33