Комбинаторная теория групп

КОМБИНАТОРНАЯ ТЕОРИЯ ГРУПП, раздел групп теории, в котором характерной чертой исследований является использование комбинаторных методов, в отличие от алгебраических, геометрических и прочих. Основные объекты комбинаторной теории групп - группы, заданные с помощью порождающих и определяющих соотношений. Всякая группа есть множество с заданными на нём двумя операциями - произведением и взятием обратного элемента. Если подмножество Х элементов группы G таково, что любой её элемент получается из элементов подмножества Х конечным числом применений этих двух операций, то Х называется множеством порождающих для группы G. Выбор некоторого фиксированного множества порождающих для группы G позволяет представить любой элемент группы G конечной записью (так называемым групповым словом), в которой участвуют лишь порождающие элементы группы. Например, слово ab^-1c обозначает элемент, полученный произведением трёх порождающих а, b^-1 и с, где b^-1  - элемент, обратный b. Любая абстрактная группа G может быть задана конечным или бесконечным множеством порождающих и конечным или бесконечным множеством определяющих соотношений вида R = 1, где R - групповое слово в алфавите порождающих. Для множества порождающих а₁,а₂, ..., а_n и множества определяющих соотношений R₁ = 1, R₂ = 1,..., R_m = 1 задаваемая ими группа G определяется следующим образом. Рассматривается множество групповых слов в алфавите а₁, а₂,..., а_n и определяются два вида операций на словах из этого множества: 1) вставка или вычёркивание двухбуквенных подслов вида a_ia_i¹ или a_i^-1 a_i,i=1,2,..., n, 2) вставка или вычёркивание левых частей R_j, j = 1,2,..., m, определяющих соотношений. Два слова, которые могут быть получены друг из друга с помощью конечного числа операций 1) и 2), считаются эквивалентными. Это отношение эквивалентности разбивает множество всех групповых слов в алфавите а₁, а₂, .., а_n на классы эквивалентности, которые и рассматриваются в качестве элементов группы G. Произведением двух классов эквивалентности, содержащих слова х и у, по определению считается класс, содержащий слово ху. Роль единичного элемента играет класс, содержащий пустое слово, а операция взятия обратного элемента определяется следующим образом. Для данного группового слова х определяется формальное обратное слово х^-1, которое получается чтением слова Х в обратном порядке и заменой каждой буквы a_i на a_i^-1 и, наоборот, a_i^-1 на а_i.  Классы эквивалентности, содержащие слова х и х^-1, являются взаимно обратными элементами группы G. Простейшими примерами групп, заданных с помощью порождающих и определяющих соотношений, являются свободные группы - группы, для которых множество определяющих соотношений пусто.

Особую роль в комбинаторной теории групп играют группы, для которых могут быть выбраны конечные множества порождающих и определяющих соотношений, такие группы называются конечно определёнными группами. Любая конечная группа конечно определена, однако класс конечно определённых групп содержит и широкий подкласс бесконечных групп. То обстоятельство, что бесконечная группа может быть задана с помощью порождающих и определяющих соотношений записью конечной длины, и послужило активному развитию комбинаторной теории групп. При исследовании групп, заданных таким способом, основным инструментом являются различные комбинаторные методы, так как в этом случае имеют дело со словами и отношениями на множестве слов.

Развитие комбинаторной теории групп началось с работы немецкого математика В. фон Дика (1882), в которой было сформулировано само понятие группы, заданной порождающими и определяющими соотношениями. В работе немецкого математика М. Дэна (1911) были выделены три проблемы, связанные с этим понятием. 1. Проблема распознавания равенства: по любым двум групповым словам, представляющим элементы данной группы, определить, равны эти элементы или нет. 2. Проблема распознавания сопряжённости: по любым двум групповым словам, представляющим элементы группы, определить, сопряжены они или нет, при этом два элемента g и h группы называются сопряжёнными, если выполнено равенство g = x^-1hx при некотором х. 3. Проблема распознавания изоморфизма: по любым двум конечным заданиям групп с помощью порождающих и определяющих соотношений определить, изоморфны данные группы или нет. Эти проблемы являются примерами алгоритмических проблем, в которых ставится вопрос о существовании алгоритма, определяющего по данному объекту из некоторого бесконечного множества обладает этот объект данным свойством или нет. Фундаментальный результат П. С. Новикова (1955) и У. Буна (1959) утверждает, что в общем случае проблема распознавания равенства и, как следствие, проблема распознавания сопряжённости неразрешимы, то есть для них такого алгоритма не существует. Согласно теореме С. И. Адяна (1955) и американского математика М. Рабина (1958), почти все естественные свойства групп, заданных порождающими и определяющими соотношениями, алгоритмически нераспознаваемы; в частности, проблема распознавания изоморфизма также неразрешима. Утверждения об алгоритмической неразрешимости свойств элементов групп и свойств самих групп - важнейшие результаты комбинаторной теории групп, оказавшие влияние на теорию групп и другие области математики.

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

Лит.: Магнус В., Каррас А., Солитер Д. Комбинаторная теория групп. М., 1974; Линдон Р., Шупп П. Комбинаторная теория групп. М., 1977; Коксетер Г., Мозер У. Порождающие элементы и определяющие соотношения дискретных групп. М., 1980; Чандлер Б., Магнус В. Развитие комбинаторной теории групп. М., 1985.