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

Число слов Sm с дЧт )* ъ(А) конечно. Поэтому для некоторого R , Ш ) s d fa 3-) , имеется бесконечное число равенств Cj Y J - A*9J RCj ( j e / Y ), Существуют числа f l и ^ такие, что р -д (У )= у ,д (лк) , Пусть /г - наименьшее положительное / 2 , для которого такое ^ существует. Возведя при необходимости равенство OjYJCj4= a 4 j R в степень д Сл*-) , всегда можно считать, что Ъе-М' При таком R - ц е л о е число. Тогда (С;А*?Y ^C j) . Взяв различные j Y j , и уу ^ , имеем (C jA -Ч У ^ С / ') ^ 'Г ^ Х= ^ Так как в группе кос нет кручения [3 ] , следовательно, C j A ^ Y ^ C j U < т .е . (О Таким образом,в случае В имеет место (4 ). Но, если Y удов­ летворяет (4), то легко выяснить, разрешимо ли уравнение Это будет в том и только в том случае, когда найдутся числа О { < / ? , S такие, что ( А - ^ ^ С а Ч У а ^ У * ~в. Выполнимость этого свойства,, очевидно, алгоритмически распозна­ ваема. 2. Если У не удовлетворяет равенству (4 ), следовательно, тлеет место случай А. Рассматривая последовательно У, Y l ,Y>... найдем ту степень^ У ^ , для которой существует нужное слово У t Как легко видеть, С также алгоритмически, находится. Ограничим ' ы . Допустим, что (А ^ ( У ) Ы- В . Представляя с< в виде <*= Г г + 6} , где О « Г, * 1Г , получим А Гл * = в / Г ^ . Тогда-№ L C A ^ C - 'f ^ m - ^ C - '. ( 5) По условию1 С 4 ес ''= й ^ С У ^ С ' Ч S', S - неприво­ димо и 9C S ) > д ( a V ; гЕрли S r = A * * S , , то по лемме 2 £ < г. Тогда t c s , ) = d ( s r) - d ( A i£ )> r (b { s ) - дГА*)). r6j С другой стороны, правых частей в равенстве (5 ) конечное число. Если мы запишем их в виде А 2*СК{ Ki - слова, i = /, Г, то по неравенству (&) имеем r~(dCs)-d(&,-))< m a x . f d ( A i ) } Г с m a x . {#(*1)}. Г f* i* Г т .е . - 1 2 1 -