Решение алгоритмических проблем для свободного произведения с коммутирующими подгруппами тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Введение

Глава 1. О централизаторах элементов для свободного произве- 10 дения с коммутирующими подгруппами.

1.1. Описание централизатора элементов со слоговой длиной 10 единица.

1.2. Доказательство общего случая.

Глава 2. Описание пересечения централизаторов элементов.

2.1. Построение пересечения конечного числа циклических подгрупп и свободных абелевых ранга 2.

2.2. Построение пересечения циклических подгрупп и централизаторов элементов со слоговой длиной единица.

2.3. Построение пересечения свободных абелевых подгрупп ранга 2 и централизаторов элементов со слоговой длиной единица.

2.4. Построение пересечения конечного множества централизаторов элементов со слоговой длиной единица.

Глава 3. Решение обобщенной проблемы сопряженности.

3.1. О пересечении смежных классов централизаторов элементов

3.2. Разрешимость проблемы обобщенной сопряженности.

Основными алгоритмическими проблемами в теории групп, поставленными М. Деном [4] в одной из его работ в 1911 году, являются проблемы равенства и сопряженности в конечно определенных группах и проблема изоморфизма групп.

Исследование этих проблем стимулировало развитие комбинаторных методов в теории групп, что явилось причиной возникновения одного из самых активно развивающихся направлений современной математики - комбинаторной теории групп. В настоящее время имеется целый ряд книг, посвященных данной теме; среди них достаточно назвать монографии Карраса, Магнуса и Солитера [22], а также Линдона и Шуппа [20].

Среди работ, связанных с исследованием проблем М. Дена, наиболее выдающимися являются работы П. С. Новикова [31], доказавшего неразрешимость проблемы равенства слов в конечно определенных группах; им же доказана неразрешимость проблемы изоморфизма групп. Примеры конечно определенных групп с неразрешимой проблемой равенства были даны Бу-ном [2].

С.И. Адяном [9] определено понятие наследственного нетривиального свойства группы и доказано, что не существует алгоритма, позволяющего для произвольной группы с конечным числом образующих и определяющих соотношений распознать выполнимость свойства /3, представляющего собой объединение нетривиального наследственного инвариантного свойства, если только существуют группы, обладающие этим свойством /3.

Из этого следует, что практически все проблемы, относящиеся к конечно определенным группам, в общем случае неразрешимы.

Отрицательное решение проблемы равенства слов явилось причиной изучения проблем Дена в определенных классах групп.

Для групп с разрешимой проблемой равенства слов возникает более общая проблема - проблема вхождения, впервые рассмотренная Нильсеном в свободных группах и Магнусом в группах с одним определяющим соотношением для так называемых магнусовых подгрупп.

Известно, что проблема вхождения в классе всех конечно определенных групп неразрешима, что непосредственно следует из связи между проблемой вхождения и проблемой равенства слов. Поэтому естественен интерес к изучению рассматриваемой проблемы для каких - то фиксированных классов групп. Как было отмечено выше, положительное решение проблемы вхождения в свободных группах следует из результата Нильсена.

К. А. Михайловой [28] этот результат был обобщен на свободное произведение групп, доказано, что если в группах А и В разрешима проблема вхождения, то она разрешима в их свободном произведении.

В отличие от свободного произведения, прямое произведение групп, как доказала К. А. Михайлова [29], не наследует свойства сомножителей иметь разрешимой проблему вхождения.

Обобщением проблемы сопряженности слов является проблема обобщенной сопряженности слов, проблема степенной сопряженности и проблема сопряженности подгрупп.

Определение 1. Под обобщенной проблемой сопряженности слов в группе G понимается решение в G системы уравнений &"=l(z 'w.z = v/y), где Wj, vjr i = I, n— фиксированные элементы группы G.

Существование такого алгоритма для некоторого класса конечно определенных групп позволяет для любого автоморфизма ^ Е AutG определить, является ли он внутренним.

Проблема изоморфизма конечно порожденной коммутативной полугруппы сводится к проблеме обобщенной сопряженности слов в классе GLn(Z) групп. Отсюда следует, что решение данной проблемы является важной задачей в комбинаторной теории групп.

С описанием множества решений данной системы связана проблема построения централизатора конечно порожденной подгруппы.

Г.С. Маканиным [23] решена известная проблема Артина об описании всех кос в ,J/)n+\ , коммутирующих с данной косой. Доказано, что централизатор любого элемента в конечно порожден и указан алгоритм построения его образующих. Используя результат Г. Г. Гурзо [19], обобщившей теорему Г. С. Маканина [23], Т. А. Маканина [24] получила полное решение обобщенной проблемы сопряженности слов в JSn+i.

Результаты Г.С. Маканина, Г. Г. Гурзо и Т. А. Маканиной справедливы для групп Артина конечного типа, определенных Брискорном Э. и Сайто К. в статье [18], а именно, в [32] показано, что централизатор конечно порожденной подгруппы конечно порожден и существует алгоритм, выписывающий образующие централизатора; разрешима проблема обобщенной сопряженности слов; дано полное описание решений системы уравнений

--l(z~Jwjz = vi).

И. Г. Лысенок [21], доказал разрешимость обобщенной проблемы сопряженности для гиперболических групп, им же установлено, что централизатор элемента в гиперболической группе является конечно порожденным.

В. Н. Безверхний доказал разрешимость проблемы обобщенной сопряженности в группах C(p)&T(q), где (p,q) Е {(6,3), (4,4), (3,6)} и в группах Артина большого типа [10, 14, 15]. Также, для данных классов групп была доказана конечная порожденность централизатора конечной порожденной подгруппы.

Герстеном и Шортом [4] доказана конечная порожденность централизатора элементов для биавтоматных групп.

Помимо указанных выше проблем, мы будем рассматривать проблему А.И. Мальцева [26] о нахождении образующих пересечения конечно порожденных подалгебр данной алгебры, решившего данную проблему для конечно порожденных нильпотентных групп [25]. С данной проблемой тесно связано свойство <~У( (Хаусона) подалгебр данной алгебры, а именно, алгебра обладает свойством гУ( ? если пересечение конечно порожденных подалгебр есть конечно порожденная подалгебра. Известно [5], что свободные группы обладают свойством rY{. Б. Баумслаг [1] обобщил результат Хаусона на свободное произведение групп.

Для свободных групп проблема А. И. Мальцева о пересечении подгрупп решена В. Н. Безверхним [11]. Конструктивное доказательство теоремы Б.Баумслага, данное в статье [16], позволило ее авторам решить указанную проблему А. И. Мальцева для свободного произведения групп. Там же доказано, что теорема Баумслага на свободное произведение с объединением не переносится. Показано, что свободное произведение групп, обладающих свойством Хаусона, объединенных по конечным группам, обладает свойством Хаусона. Также в данной работе показано, что если сомножители обладают свойством Хаусона и них разрешима проблема Мальцева и разрешима проблема пересечения смежных классов конечно порожденных подгрупп, то и свободное произведение этих групп, объединенных по конечным подгруппам, наследует указанное выше свойство.

Д. И. Молдаванским в [29] доказывается, что группы с одним определяющим соотношением с нетривиальным центром свойством Хаусона не обладают.

И. Капович показал [6], что в группе G=<a, t; at 'ata't a 't2 > свойством Хаусона также не выполнено.

Представленная работа посвящены решению некоторых алгоритмических проблем в классе групп, являющемся свободным произведением двух свободных групп с коммутирующими подгруппами:

С = ^А*В;{Н,К = 7^, где Н и К — конечно порожденные подгруппы в

А и В соответственно, а именно, описанию централизатора элементов, построению пересечения централизаторов и решению обобщенной проблемы сопряженности. Для групп этого класса Д. Гурвицем [8] доказана разрешимость проблем равенства и сопряженности слов. В работе Р.Е. Шуппа и С.Ф. Миллера [7] исследуется геометрия этих групп и показано, что условия при которых проблема слов разрешима идентичны для свободного произведения с объединением. Если А и В имеют разрешимую проблему равенства и в подгруппах Н и К разрешима обобщенная проблема равенства, то в группе G разрешима проблема равенства.

В первом параграфе вводятся основные определения симметризованного множества, циклически R — приведенного слова, R - диаграммы, приводятся результаты, полученные ранее для рассматриваемого класса групп. Основным результатом первой главы является следующая теорема Теорема 1. Централизатор любого элемента группы G конечно порожден и есть либо циклическая, либо свободная абелева ранга 2, либо подгруппа вида

Cjg)= (V, П*а>Ка')' 4 84 е н> S >8 * н;

Ca(g)= (5, К *П*аМ/ )> а-84 е Д g=sk ,g е Н . f

-1 \ i.-i

Ca(8h s, UhUb] , b. gbi e K, g g^K, i=l

CJg)= H * Т1*ЬДЪ]1 j,bj'gbi e K, g=sk ,g g К

Причем Cliybjj выбирается как минимальный представитель двойного смежного класса < g > а'/ Н ( < g > b'K^j.

Все результаты первой главы получены с помощью плоских односвяз-ных диаграмм Ван-Кампена.

Во второй главе решается вопрос описания пересечения конечного числа централизаторов элементов группы G. В рассматриваемом классе групп пересечение конечно порожденных подгрупп в общем случае не является конечно порожденной подгруппой. Это следует из результата Д. И. Молдаванского (1968 г.): группа, содержащая прямое произведение бесконечной циклической подгруппы и свободной ранга 2, не обладает свойством Хаусона [29]. Однако, как доказано автором, для централизаторов подгрупп это свойство справедливо.

Теорема 2. Пересечение конечного числа централизаторов элементов группы G есть конечно порожденная подгруппа одного из типов, описанных в теореме 1.

Теорема 3. Существует алгоритм, выписывающий образующие пересечения конечного числа централизаторов элементов группы G.

Из доказанных теорем получается ряд следствий.

Следствие 1. Централизатор конечно порожденной подгруппы конечно порожден.

Следствие 2. Существует алгоритм, выписывающий обра п'ющие централизаторов подгрупп группы G.

Следствие 3. Пересечение централизаторов конечно порожденных подгрупп есть конечно порожденная подгруппа и существует алгоритм, выписывающий образующие этого пересечения.

В третьей главе доказывается разрешимость проблемы обобщенной сопряженности при условии, что подгруппы Н и К антинормальны.

Определение 2. Подгруппа Р группы G называется антинормальной, если из того, что g ^ Р следует, что g ' Pg П Р = j/j .

Теорема 4. Существует алгоритм, позволяющий установить, пусто где CG(Wj) централизатор элемента wj в G.

Теорема 5. В группе G разрешима проблема обобщенной сопряженно

II или нет пересечение следующих смежных классов подгрупп: j JgjCc;(vt'(), emu слов.

Теорема конечно определенная группа и > {v/i- у ~~ слова из G. Если F — какое-то решение сис9 темы &'' ,(z 'WjZ = vi), то множество CG(H) • F, где CGf H) — централизатор подгруппы H, порожденный множеством jvtA jy , , является множеством всех решений системы.

Все результаты, полученные в диссертации, опубликованы в работах [36-41] и докладывались на алгебраическом семинаре A. J1. Шмелькина, А.Ю. Ольшанского (МГУ 2001г.), на алгебраическом семинаре под руководством В. Н. Безверхнего (1996-2001г.), на IV Международной конференции «Современные проблемы теории чисел и ее приложения» (Тула, 2001 г.); на Всероссийской научной конференции «Современные проблемы математики, механики и информатики» (Тула, 2000 г.).

10

1. Baumslag В. 1.tersection of finitely generated subgroups in free product. J. London Math, soc., 1966, 41. P. 673-679.

2. Boone W. W. Gertain simple, unsolvable problems of group theory.// V, VI. Proc. Kon. ned. akad. wetensch., 1957, 19, №1, 22-27; №2, p. 227232 (РЖМат, 1959, 78).

3. Dehn M. Uber unendliche discontinuierliche Gruppen. Maht. Annal. 71, 116-144,1.4, II.3, 1911.

4. Gersten S. M., Short H. B. Rational subgroups of biautomatic groups Annals of Math. 1991, 134, P. 125-158.

5. Howson A.G. On the intersection of finitely generated free groups. J. London Math, soc., 1954, 29. P. 428-434.

6. Kapovich I. Howson property and one- relator groups// Commynication in algebra. 1999. V. 27.№ 3. P. 1057-1072.

7. Miller,C.F.Ill, Schupp,P.E. The geometry of Higman-Neumann-Neumann extensions// Comm. Pure. Appl. Math. 26, 787-802(1973).

8. R. Daniel Hurwitz. On the Conjugacy Problem in a Free product with Commuting Subgroup// Math. Ann. 221, 1-8, 1976.

9. Адян С.И. Неразрешимость алгоритмических проблем в теории групп// Труды Мое. Мат. об-ва. 1957. Т.6. С. 231-298.

10. Безверхний В. Н. О нормализаторах C(p)&T(q)-rpynnax// Алгоритмические проблемы теории групп и полугрупп. Межвуз. сб. научн. тр. Тула, 1994.

11. Безверхний В. Н. О пересечении конечно порожденных подгрупп свободной группы // Сб. науч. тр. каф. высш. матем.- Тула: Изд-во ТулПИ, 1974. С. 51-56.

12. Безверхний В. Н. Решение проблемы вхождения в группах с одним определяющим соотношением с нетривиальным центром// Сиб. матем. журнал. 1985. № 2. Т. 26

13. Безверхний В. Н. Решение проблемы вхождения для одного класса групп// Вопросы теории групп и полугрупп Тула: Изд-во ТГПИ им. Л.Н. Толстого, 1972. С. 3-86.

14. Безверхний В. Н. Решение проблемы обобщенной сопряженности слов C(p)&T(q)-rpynnax// Известия Тульского гос. ун-та. Сер. "Математика". Тула: Изд-во ТулГу, 1998.

15. Безверхний В. Н. Решение проблемы обобщенной сопряженности слов в группах Артина большого типа// Фундаментальная и прикладная математика. Т.5. №1. 1999.

16. Безверхний В. Н., Роллов Э. В. О подгруппах свободного произведения групп// Современная алгебра, вып.1.-Л., 1974. С.

17. Безверхний В.Н. О неразрешимости проблемы вхождения для некоторого класса групп// Сб. науч. тр. каф. высш. матем.- Тула: Изд-во ТулПИ, 1974. С. 51-54.

18. Брискорн Э., Сайто . Группы Артина и Кокстера // Математ. заметки: сб. переводов, 1974. 18, № 6. С. 56-79.

19. Гурзо Г.Г. О централизаторах конечных множеств элементов группы кос// Математ. заметки. 1985.Т. 37.№1. С.3-6.

20. Линдон Р., Шупп П. Комбинаторная теория групп.-М.: Мир, 1980.

21. Лысенок И. Г. О некоторых алгоритмических свойствах гиперболических групп// Изв. АН СССР. Сер. мат. 1959. Т.53.№4.

22. Магнус В., Каррас А., Солитер Д. Комбинаторная теория групп.-М.: Наука, 1974.

23. Маканин Г.С. О нормализаторах группы кос// Мат. сб. 1971. 86. № 2. С. 171-179.

24. Маканина Т. А. Об одной системе решений в группе кос// Изв. учеб. заведений: Математика. 1986.№9. С.58-62.

25. Мальцев А. И. Два замечания о нильпотентных группах// Мат.сб. 1955. 37.№3.С. 567-572.

26. Мальцев А. И. О гомоморфизмах на конечные группы // Уч. зап. Ивановского пед. ин-та .1958.С.49-60.

27. Михайлова К. А. Проблема вхождения для прямых произведений групп// Мат. сб. 1966. 70.№2. С. 241 -251.

28. Михайлова К. А. Проблема вхождения для свободного произведения групп//Мат. сб. 1968. 75.№2. С. 199-210.

29. Молдованский Д. И. О пересечении конечно порожденных подгрупп// Сиб. матем. журнал. 1968. № 9. С. 1422-1426.

30. Новиков П.С. Об алгоритмической неразрешимости проблемы тождества в теории групп// Труды МИАН СССР, 1955.Т.44.С. 23 1-298

31. Трубицын Ю. Э. О нормализаторах конечных множеств в группах Артина конечного типа// Алгоритмические проблемы теории групп и полугрупп. Межвуз. сб. научн. тр. Тула. 1986.

32. Щепин Е. Е. К проблеме вхождения в конечно определенных группах// Сиб. мат. журн. 1968. T.IX, №2. С.443-448.

33. Новикова О. А. Решение проблемы вхождения в одном классе групп// Тезисы докл. на Международн. алгебр. конференции памяти А. Е. Куроша. Москва, 1998. С. 196-197.

34. Новикова О. А. Решение проблемы вхождения и финитной отделимости в одном классе групп// Известия Тульского гос. ун-та. Сер. "Математика". Тула: Изд-во ТулЕу, 1998. Т. 4. Вып. 3. С. 93-98.

35. Безверхний В.Н., Новикова О.А. Описание централизатора элементов группы Еурвица// Алгоритмические проблемы теории групп и полугрупп. Межвуз. сб. научн. тр. Тула: изд-во Тул. гос. пед. ун-та им. Л. Н. Толстого, 2001, с.79-97.

36. Новикова О. А. Описание централизатора элементов группы Гур-вица// Тезисы докладов IV Международной конференции, посвященной 60-лет. Мерзлякова Ю. И. Новосибирск. 2000 г.

37. Безверхний В.Н., Новикова О.А. Решение проблемы пересечения централизаторов элементов для свободного произведения с коммутирующими подгруппами// Известия Тульского гос. ун-та. Сер. "Математика".-Тула: Изд-во ТулГу, 2001. Т. 7. Вып. 1, с.21-33.