КОМБИНАТО́РНАЯ ТЕО́РИЯ ГРУПП

КОМБИНАТО́РНАЯ ТЕО́РИЯ ГРУПП, раз­дел групп тео­рии

, в ко­то­ром ха­рак­тер­ной чер­той ис­сле­до­ва­ний яв­ля­ет­ся ис­поль­зо­ва­ние ком­би­на­тор­ных ме­то­дов, в от­ли­чие от ал­геб­раи­че­ских, гео­мет­ри­че­ских и пр. Осн. объ­ек­ты К. т. г. – груп­пы, за­дан­ные с по­мо­щью по­ро­ж­даю­щих и оп­ре­де­ляю­щих со­от­но­ше­ний. Вся­кая груп­па есть мно­же­ст­во с за­дан­ны­ми на нём дву­мя опе­ра­ция­ми – про­из­ве­де­ни­ем и взя­ти­ем об­рат­но­го эле­мен­та. Ес­ли под­мно­же­ст­во $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), поч­ти все ес­теств. свой­ст­ва групп, за­дан­ных по­ро­ж­даю­щи­ми и оп­ре­де­ляю­щи­ми со­от­но­ше­ния­ми, ал­го­рит­ми­че­ски не­рас­по­зна­вае­мы; в ча­ст­но­сти, про­бле­ма рас­по­зна­ва­ния изо­мор­физ­ма так­же не­раз­ре­ши­ма. Ут­вер­жде­ния об ал­го­рит­мич. не­раз­ре­ши­мо­сти свойств эле­мен­тов групп и свойств са­мих групп – важ­ней­шие ре­зуль­та­ты К. т. г., ока­зав­шие влия­ние на тео­рию групп и др. об­лас­ти ма­те­ма­ти­ки.

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