КОМБИНАТО́РНАЯ ТЕО́РИЯ ГРУПП
-
Рубрика: Математика
-
Скопировать библиографическую ссылку:
КОМБИНАТО́РНАЯ ТЕО́РИЯ ГРУПП, раздел групп теории, в котором характерной чертой исследований является использование комбинаторных методов, в отличие от алгебраических, геометрических и пр. Осн. объекты К. т. г. – группы, заданные с помощью порождающих и определяющих соотношений. Всякая группа есть множество с заданными на нём двумя операциями – произведением и взятием обратного элемента. Если подмножество $X$ элементов группы $G$ таково, что любой её элемент получается из элементов подмножества $X$ конечным числом применений этих двух операций, то $X$ называется множеством порождающих для группы $G$. Выбор некоторого фиксированного множества порождающих для группы $G$ позволяет представить любой элемент группы $G$ конечной записью (т. н. групповым словом), в которой участвуют лишь порождающие элементы группы. Напр., слово $ab^{–1}c$ обозначает элемент, полученный произведением трёх порождающих $a$, $b^{-1}$ и $c$, где $b^{-1}$ – элемент, обратный $b$. Любая абстрактная группа $G$ может быть задана конечным или бесконечным множеством порождающих и конечным или бесконечным множеством определяющих соотношений вида $R=1$, где $R$ – групповое слово в алфавите порождающих. Для множества порождающих $a_1, a_2,\ldots, a_n$ и множества определяющих соотношений $R_1=1, R_2=1,\ldots, R_m=1$ задаваемая ими группа $G$ определяется следующим образом. Рассматривается множество групповых слов в алфавите $a_1, a_2,\ldots, a_n$ и определяются два вида операций на словах из этого множества: 1) вставка или вычёркивание двухбуквенных подслов вида $a_i a_i^{–1}$ или $a_i^{–1} a_i, i= 1,2,\ldots,n$, 2) вставка или вычёркивание левых частей $R_j, j=1,2,\ldots, m$, определяющих соотношений. Два слова, которые могут быть получены друг из друга с помощью конечного числа операций 1) и 2), считаются эквивалентными. Это отношение эквивалентности разбивает множество всех групповых слов в алфавите $a_1, a_2,\ldots, a_n$ на классы эквивалентности, которые и рассматриваются в качестве элементов группы $G$. Произведением двух классов эквивалентности, содержащих слова $x$ и $y$, по определению считается класс, содержащий слово $xy$. Роль единичного элемента играет класс, содержащий пустое слово, а операция взятия обратного элемента определяется следующим образом. Для данного группового слова $x$ определяется формальное обратное слово $x^{–1}$, которое получается чтением слова $x$ в обратном порядке и заменой каждой буквы $a_i$ на $a_i^{-1}$ и, наоборот, $a_i^{-1}$ на $a_i$. Классы эквивалентности, содержащие слова $x$ и $x^{–1}$, являются взаимно обратными элементами группы $G$. Простейшими примерами групп, заданных с помощью порождающих и определяющих соотношений, являются свободные группы – группы, для которых множество определяющих соотношений пусто.
Особую роль в К. т. г. играют группы, для которых могут быть выбраны конечные множества порождающих и определяющих соотношений, такие группы называются конечно определёнными группами. Любая конечная группа конечно определена, однако класс конечно определённых групп содержит и широкий подкласс бесконечных групп. То обстоятельство, что бесконечная группа может быть задана с помощью порождающих и определяющих соотношений записью конечной длины, и послужило активному развитию К. т. г. При исследовании групп, заданных таким способом, осн. инструментом являются разл. комбинаторные методы, т. к. в этом случае имеют дело со словами и отношениями на множестве слов.
Развитие К. т. г. началось с работы нем. математика В. фон Дика (1882), в которой было сформулировано само понятие группы, заданной порождающими и определяющими соотношениями. В работе нем. математика М. Дэна (1911) были выделены три проблемы, связанные с этим понятием. 1. Проблема распознавания равенства: по любым двум групповым словам, представляющим элементы данной группы, определить, равны эти элементы или нет. 2. Проблема распознавания сопряжённости: по любым двум групповым словам, представляющим элементы группы, определить, сопряжены они или нет, при этом два элемента $g$ и $h$ группы называются сопряжёнными, если выполнено равенство $g=x^{–1}hx$ при некотором $x$. 3. Проблема распознавания изоморфизма: по любым двум конечным заданиям групп с помощью порождающих и определяющих соотношений определить, изоморфны данные группы или нет. Эти проблемы являются примерами алгоритмических проблем, в которых ставится вопрос о существовании алгоритма, определяющего по данному объекту из некоторого бесконечного множества обладает этот объект данным свойством или нет. Фундам. результат П. С. Новикова (1955) и У. Буна (1959) утверждает, что в общем случае проблема распознавания равенства и, как следствие, проблема распознавания сопряжённости неразрешимы, т. е. для них такого алгоритма не существует. Согласно теореме С. И. Адяна (1955) и амер. математика М. Рабина (1958), почти все естеств. свойства групп, заданных порождающими и определяющими соотношениями, алгоритмически нераспознаваемы; в частности, проблема распознавания изоморфизма также неразрешима. Утверждения об алгоритмич. неразрешимости свойств элементов групп и свойств самих групп – важнейшие результаты К. т. г., оказавшие влияние на теорию групп и др. области математики.
Одним из классич. направлений исследований в рамках К. т. г. является нахождение классов групп, для которых те или иные алгоритмич. проблемы разрешимы. Др. направления, в которых также были получены значит. результаты, – изучение разл. известных «классических» групп, изучение т. н. свободных конструкций, построение примеров групп с необычными свойствами.