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

случаях при любом натуральном х g x е К . Пусть g, е G, . Если g, - элемент бесконечного порядка, что эффективно проверяется благодаря теореме Карраса, Магнуса и Солитэра, дающей характеризацию элементов конечного порядка в группах с одним определяющим соотношением (см. [1], с. 273), то при всех х е N g x е К . Если же т - порядок элемента g ,, то g m= I е К . Таким обра­ зом, если все образующие группы G, входят в L, то алгоритм, определяющий, существует ли х е N , что g x е К , возможен. В случае положительного ответа можно эффективно найти наименьшее натуральное к, при котором g x е К . 2. Пусть L - максимальное подмножество образующих группы G, в к ром отсутствует образующий, входящий в R. Если 5 , c l , S2 = L \S V Кл =gp(S {), Кг - gp(S2), К = gp(L), то по теореме Магнуса о свободе (см. [1], с. 271), К - свободна и К =K t *К2. Для произвольного g e K gx еК, о g e K , . Поэтому достаточно решить вопрос о существовании алго­ ритма для множества свободных образующих L. Доказательство проведем ин­ дукцией по длине слова R. Если R затрагивает только один образующий, то теорема справедлива, так как в этом случае G = К* < о;а* = 1> , К = gp(L) - свободная группа, и если g е G - архимедов элемент относительно функции длины /, индуцируемой этим разложением, то для любого х е N g x t К . В про­ тивном случае g = wg,w~', где g, еЛГ или g, е< а ;ат= 1>. Если l(w )* О, g, е К , то так как К - свободна, g x £ К для всех натуральных х. Если же g, е< а; ат = 1 >, то g = waw~‘, и g 1 е К тогда и только тогда, когда гх кратно т. Пусть теперь R затрагивает не менее двух образующих. Предположим сначала, что образующий, скажем /, входящий в Л, имеет в слове R нулевую сумму показателей: а,(Л) = 0. Как известно (см. [1], с. 272), в этом случае G можно рассматривать как ЯЛТ^-расширение G =< H ,t;tX T '= Y > , 196 (1)