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

ряд, соответствующий И/ . Под длиной 3L &i =<0)...x(ri )a x ',(ri y .x~>(t)i будем понимать число U \ ) ‘ 2 rt +f. Множеству /У поставим в соответствие упорядоченное ш о - жество пар 2(W)~(U,/ > , } , ■ ■ , ( £ . fle)) . где в каждой паре ( t ,(i;) первое число с обозначает длину элемента из мно- нества V~{hVUSj , второе-Д - - указывает, скольно элементов длины l содержится е множестве V . Назовем X (lv) харак­ теристикой множества W . На множестве характеристик X (W L) _ соответствующих, различным нильсеновсдим множествам И'- , можно ввести линей­ ный порядок. (ШРЕДЕЯЕШЕ 8 . Пусть W , ~ два конечшх нильсенов- ских множества свободной группы и пусть X(iV)=((t,fi,\ .,(^/1е)), №.f a )) - их характеристики. Тогпа l ( t y ) <X (W ), ецли 1) 2 ) * = * '/ ? . <№>; 3) £* € , f l e - f i e ' ц • но /?,>.,• “У**-* • , 1 И 4, Пусть Q e F , H < F / p £ H , 3 /t£ p \J i, и IV -нильсеновское множество образующих подгруппы Н , а И'" - нильсеновское множество образующих подгруппы <W ,y> . Тогда * ( И " ) < x i W). ДОКАЗАТЕЛЬСТВО. Пусть д*С*(1).. х ( к ) с [ x (i)x (l) f fj Д 4 X , <jn *H . Будем предполагать, что с поделено левой половины некоторого u ( t) ^ { !>\'U W 'j, u ( t ) =cun ( i ) или неизолированная левая половина и (О (лем­ ма 2 ). Тогда присоединение к подгруппе Н элемента у рав­ носильно присоединению иг*Щ гф , где i tf J tlW U W 'y U un ) обладает свойством /3 относи­ тельно вспомогательного ряда, соответствующего множеству / у . Пусть / (с) <L (ц п (/)) . Упорядочим множество : и, 4 гл *... < va +, (Ю) л применим к (К,) и вспомогательному ряду (II) множества W преобразопания Л1>, = 1 / 2 1 8К , . перево­ дящие {W, си п (л ) } в нильсеновское множество (V7 и ряд (И ) во вспомогательный ряд множества W (лемма I ) . В результате этого процесса будет преобразовано в Щ ) и '-ЧлЦН , а э ш т п S ,= u ~ ,p )a <'*(;) R