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

остается не менее п р -С { . Выше было показано, что число дисков не превыше- _ ^2 ет С]. Поэтому N > Итак, I Я2,+11> (2/ + 1)- Ч щ>- ч С, 1 2 С? - т Далее нам понадобится следующая теорема. Теорема о площади [4]. Пусть М - односвязная приведенная диаграмма с условием С(4)&Т(4). Тогда число областей диаграммы М удовлетворяет нера- , ( . Л 2 венству | м | < - £ [4 -/'(D )] DeM Оценим сверху правую часть этого неравенства. . f 1 (4 - i(D)] < 2(2(2 Е -1 r „I-(2 1 + 1)) + 2 np„f = 4(£-1 г„\ (4/ + 2) + ир„)2. V j D s A/ > При л > 4i + 2 верно неравенство 4(£-1 гй1-(4/ + 2) + пр„)2 < 4(£-1 r0 1и + ир0)2. Таким образом, | Я2|Ч/| < -4(Е- \г0\-п + про)2 £ п (Е -1 Го I+ Pof 4 Другими словами, f ( i ) = (2/+1)- пр - С ,2 С\ 2 < |Я2,+/| < я 2 (£-1r01+ р в)2 =/j((). Очевидно, что существует такое число i = i0> 0, что /,(0 > / / i ) Значит, положив I ,=. io и выбрав п > 4/ + 2 получим диаграмму Я 2 ,0+| для которой не­ верна теорема о площади, что невозможно. То есть мы получаем, что предпо­ ложение о наличии в диаграмме длинных дисков привело нас к противоречию. Таким образом, если в диаграмме есть область с двумя внутренними реб­ рами, то числа л, т можно ограничить константой, которая будет зависеть только от длин слов w, v, от числа элементов в множестве определяющих соот­ ношений группы и от их длин. §3. Решение проблемы сопряженности в группах с условием С(5)&Т(4) Очевидно, что как и для групп с условием С(4)&Т(4), для рассматривае­ мого класса групп можно показать, что существует алгоритм, строящий по лю­ бому циклически несократимому слову w, представляющему в группе с услови­ ем С(5)&Т(4) элемент бесконечного порядка, сопряженное с w\ к < 2 в группе G слово и>0) любая степень которого R, R - несократима. Пусть М - приведённая кольцевая диаграмма сопряженности циклически Л,Л- несократимых слов w” , v~m. dM=< 7 Kj г, <p(d)= w” , <z>(r) = v~m. Слова w, v- элементы бесконечного порядка. Без потери общности можем считать, что в М нет областей с двумя внутренними ребрами, в противном случае, выполнив соответствующие сокращения, мы можем рассматривать диаграмму с меньшим числом кусков. Доказательство теоремы будет непосредственно следовать из леммы. 137