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

ЛЬМ1А 15. Пусть Н - конечно порожденная подгруппа свобод­ ной группы F я w - произвольный элемент F . Тогда можно эл ек ти вн о установить, существует ли натуральное п я слово г е р такие , что * ' м п 1 ' , €Н. ДОКАЗАТЕЛЬСТВО. Д оказател ьстю этой лемиы проводим анало­ гично доказательству леммы 1 4 . Выберем в качестве I наимень­ ший среди элементов двойного класса смежности H b < w > Как и в предыдущей л еш е , ж удовлетворяет соотношению ( 86 ) . Составля­ ем список с л о в { l i l u i j , где каждое 2 , так о в о , что 1 г , 1 <л/а , Для каждого 2 , выписываем образующие <д(ги е = * 1 На основании леммы I I существует алгоритм, позволяющий выписать образ,уюшие пересечения < 2 *н / 2 [ 1>ЛН . Лемма доказана. ЛКМиА 16 . Элементы w, , Wt группы б , , содержащиеся в Ч (W 4 ) ) , сопряжены в <?f тогда и только т о г д а , когда они со­ пряжены в U, ДОКАЗАТЕЛЬСТЮ. Пусть в б , существует ?<?<?, так о е, что 2 УУ, 2 ‘, = И/Д. Допустим, что|| 2 /|= ) , то е ст ь 2 = hg. t y g l f f Ф и , Ц , ТоДда из соотношения W i с л е д у е т, что g w ^ - i ^ w / , w/e Ut . На основании теоремы 3 g U ^ 'H U , е ст ь циклическая подгруппа, а из следствий I и 2 получаем, что каждое из слов й> , либо сопряжены с (V c i(a 1>...,Q n) ) t (ггс определяется словом I, однозначно) , t e f t , либо с f,l (a,s...t a n) , ^ сл и f,= w ^ , , либо со степенью образующего Сд ' , <! , подгруппы б , в подгруппе U<. Допустим, что утверждение леммы справедливо для случая, когда I/* Д•< Arв , Докажем е го для случая, когда й* 11=k 0 B i* k c j1...gkc t$ k c ' Допустим, что в <?, имеет место равенство Я - ' Я . w< 9 Z 9 * ! - r . % 7) Для того чтобы равенство ( 8 ? ) имело место В <?, ’ / необходимо, чтобы Из доказанного выше сл е д у е т, что элементы W/ и W, сопряжены в Ц . Заменим в (8 7 ) элементы < ^а е Wr элементами V^n//,) , , получим равенство иэ которого в силу индуктивного предположения следует, что и V’f’Wx) сопряжены в Лемма доказана. ЛЕММА 17. В группе (?f разрешима проблема сопряженности с л о в . 30