Презентација групе

У математици, презентација је један од метода за специфицирање групе. Презентација групе G обухвата скуп S генератора — тако да се сваки елемент групе може записати као производ степена неких од ових генератора — и скуп R релација међу тим генераторима. Тада кажемо да G има презентацију

$⟨S\mid R⟩.$

Неформално, G има горњу презентацију ако је то „најслободнија” група генерисана са S, која подлеже само релацијама R. Формално, за групу G се каже да има горњу презентацију ако је изоморфна количнику слободне групе над S са нормалном подгрупом генерисаном релацијама R.

Као једноставан пример, циклична група реда n има презентацију

$⟨a\mid a^n=1⟩,$

где је 1 идентитет групе. Ово се може еквивалентно написати као

$⟨a\mid a^n⟩,$

захваљујући конвенцији да се чланови који не укључују знак једнакости сматрају једнаким идентитету групе. Такви чланови називају се релатори, што их разликује од релација које укључују знак једнакости.

Свака група има презентацију, и заправо много различитих презентација; презентација је често најкомпактнији начин описивања структуре групе.

Блиско повезан, али различит концепт је апсолутна презентација групе.

Позадина

Слободна група над скупом S је група где се сваки елемент може јединствено описати као коначан производ облика:

$s_1^{a_1}{s}_2^{a_2}\cdots s_n^{a_n}$

где су s_i елементи скупа S, суседни s_i су различити, а a_i су ненулти цели бројеви (али n може бити нула). Мање формално речено, група се састоји од речи у генераторима и њиховим инверзима, подложних само поништавању генератора са суседном појавом његовог инверза.

Ако је G било која група, а S генеришући подскуп од G, онда је сваки елемент G такође горе наведеног облика; али генерално, ови производи неће јединствено описати елемент G.

На пример, диједарска група D₈ реда шеснаест може бити генерисана ротацијом r реда 8 и рефлексијом f реда 2, и сигурно је сваки елемент D₈ производ r-ова и f-ова.

Међутим, имамо, на пример, Шаблон:Math, Шаблон:Math, итд., тако да такви производи нису јединствени у D₈. Свака таква еквиваленција производа може се изразити као једнакост са идентитетом, као што су

Шаблон:Math,

Шаблон:Math, или

Шаблон:Math.

Неформално, можемо сматрати ове производе са леве стране као елементе слободне групе Шаблон:Math, и нека је Шаблон:Math. То јест, нека је R подгрупа генерисана низовима rfrf, r⁸, fШаблон:Px2², од којих је сваки такође еквивалентан са 1 када се посматра као производ у D₈.

Ако тада означимо са N подгрупу од F генерисану свим коњугатима x⁻¹Rx од R, онда по дефиницији следи да је сваки елемент N коначан производ x₁⁻¹r₁x₁ ... x_m⁻¹r_m x_m чланова таквих коњугата. Из тога следи да ће се сваки елемент N, када се посматра као производ у D₈, такође свести на 1; и стога је N нормална подгрупа од F. Дакле, D₈ је изоморфна количничкој групи Шаблон:Math. Тада кажемо да D₈ има презентацију

$⟨r,f\mid r^8=1,f^2=1,(rf{)}^2=1⟩.$

Овде је скуп генератора Шаблон:Math, а скуп релација је Шаблон:Math. Често се R скраћује, дајући презентацију

$⟨r,f\mid r^8=f^2=(rf{)}^2=1⟩.$

Још краћи облик изоставља знак једнакости и идентитета, да би се навео само скуп релатора, који је Шаблон:Math. Тиме се добија презентација

$⟨r,f\mid r^8,f^2,(rf{)}^2⟩.$

Све три презентације су еквивалентне.

Ознаке

Иако је нотација Шаблон:Math која се користи у овом чланку за презентацију сада најчешћа, ранији аутори су користили различите варијације истог формата. Такве нотације укључују следеће:

• Шаблон:Math
• Шаблон:Math
• Шаблон:Math
• Шаблон:Math

Дефиниција

Шаблон:Redirect Нека је S скуп и нека је F_S слободна група над S. Нека је R скуп речи над S, тако да R природно даје подскуп од $F_S$. Да би се формирала група са презентацијом $⟨S\mid R⟩$, узме се количник од $F_S$ по најмањој нормалној подгрупи која садржи сваки елемент из R. (Ова подгрупа се назива нормално затворење N од R у $F_S$.) Група $⟨S\mid R⟩$ се тада дефинише као количничка група

$⟨S\mid R⟩=F_S/N.$

Елементи S се називају генератори групе $⟨S\mid R⟩$, а елементи R се називају релатори. Каже се да група G има презентацију $⟨S\mid R⟩$ ако је G изоморфна $⟨S\mid R⟩$.

Уобичајена је пракса да се релатори пишу у облику $x=y$ где су x и y речи над S. То значи да $y^{-1}x\in R$. Ово има интуитивно значење да се слике x и y требају сматрати једнаким у количничкој групи. Тако је, на пример, rⁿ у листи релатора еквивалентно са $r^n=1$.

За коначну групу G, могуће је изградити презентацију G из табеле множења групе, на следећи начин. Узмимо да је S скуп елемената $g_i$ из G, а R да су све речи облика $g_i{g}_j{g}_k^{-1}$, где је $g_i{g}_j=g_k$ унос у табели множења.

Алтернативна дефиниција

Дефиниција презентације групе може се алтернативно преформулисати у терминима класа еквиваленције речи над алфабетом $S\cup S^{-1}$. У овој перспективи, две речи проглашавамо еквивалентним ако је могуће доћи од једне до друге низом потеза, где се сваки потез састоји од додавања или уклањања узастопног пара $x{x}^{-1}$ или $x^{-1}x$ за неко Шаблон:Mvar у Шаблон:Mvar, или додавањем или уклањањем узастопне копије релатора. Елементи групе су класе еквиваленције, а операција групе је конкатенација.

Овај приступ је посебно уобичајен у области комбинаторичка теорија група.

Коначно презентоване групе

За презентацију се каже да је коначно генерисана ако је S коначан, а коначно повезана ако је R коначан. Ако су оба коначна, каже се да је коначна презентација. Група је коначно генерисана (односно коначно повезана, Шаблон:Visible anchor) ако има презентацију која је коначно генерисана (односно коначно повезана, коначна презентација). Група која има коначну презентацију са једном релацијом назива се група са једним релатором.

Рекурзивно презентоване групе

Ако је S индексиран скупом I који се састоји од свих природних бројева N или коначног подскупа њих, онда је лако поставити једноставно један-на-један кодирање (или Геделово нумерисање) Шаблон:Nowrap из слободне групе над S у природне бројеве, тако да можемо пронаћи алгоритме који, за дато f(w), израчунавају w, и обрнуто. Тада можемо назвати подскуп U од F_S рекурзивним (односно рекурзивно пребројивим) ако је f(U) рекурзиван (односно рекурзивно пребројив). Ако је S индексиран као горе, а R рекурзивно пребројив, онда је презентација рекурзивна презентација, а одговарајућа група је рекурзивно презентована. Ова употреба може изгледати чудно, али могуће је доказати да ако група има презентацију са R рекурзивно пребројивим, онда има и другу са R рекурзивним.

Свака коначно презентована група је рекурзивно презентована, али постоје рекурзивно презентоване групе које се не могу коначно презентовати. Међутим, теорема Грејама Хајгмана каже да коначно генерисана група има рекурзивну презентацију ако и само ако се може уградити у коначно презентовану групу. Из овога можемо закључити да постоји (до изоморфизма) само пребројиво много коначно генерисаних рекурзивно презентованих група. Бернхард Нојман је показао да постоји непребројиво много неизоморфних група са два генератора. Стога, постоје коначно генерисане групе које се не могу рекурзивно презентовати.

Историјат

Једну од најранијих презентација групе помоћу генератора и релација дао је ирски математичар Вилијам Роуан Хамилтон 1856. године, у свом икосијанском рачуну – презентацији икосаедарске групе. Прво систематско проучавање дао је Валтер фон Дик, ученик Феликса Клајна, почетком 1880-их, постављајући темеље за комбинаторичку теорију група.

Примери

Следећа табела наводи неке примере презентација за често проучаване групе. Имајте на уму да у сваком случају постоје многе друге могуће презентације. Наведена презентација није нужно најефикаснија могућа.

Група	Презентација	Коментари
слободна група над S	$⟨S\mid \varnothing ⟩$	Слободна група је „слободна” у смислу да не подлеже никаквим релацијама.
${\pi }_1(S_g)$, површинска група оријентабилног рода $g\ge 0$	$⟨a_1,b_1,\dots ,a_g,b_g|[a_1,b_1][a_2,b_2]\dots [a_g,b_g]⟩$	Угласта заграда означава комутатор: $[a,b]=ab{a}^{-1}{b}^{-1}$
Cn, циклична група реда n	$⟨a\mid a^n⟩$
Dn, диједарска група реда 2n	$⟨r,f\mid r^n,f^2,(rf{)}^2⟩$	Овде r представља ротацију, а f рефлексију.
D∞, бесконачна диједарска група	$⟨r,f\mid f^2,(rf{)}^2⟩$
Dicn, дициклична група	$⟨r,f\mid r^{2n},r^n=f^2,fr{f}^{-1}=r^{-1}⟩$	Кватернионска група Q8 је посебан случај када је n = 2
Z × Z	$⟨x,y\mid xy=yx⟩$
Z/mZ × Z/nZ	$⟨x,y\mid x^m,y^n,xy=yx⟩$
слободна Абелова група над S	$⟨S\mid R⟩$ где је R скуп свих комутатора елемената S
Sn, симетрична група над n симбола	генератори: ${\sigma }_1,\dots ,{\sigma }_{n-1}$ релације: ${\sigma }_i^2=1$, ${\sigma }_i{\sigma }_j={\sigma }_j{\sigma }_i\text{ if }j\ne i\pm 1$, ${\sigma }_i{\sigma }_{i+1}{\sigma }_i={\sigma }_{i+1}{\sigma }_i{\sigma }_{i+1}$ Последњи скуп релација може се трансформисати у $({\sigma }_i{\sigma }_{i+1}{)}^3=1$ коришћењем ${\sigma }_i^2=1$.	Овде σi је пермутација која замењује i-ти елемент са i+1-им. Производ σiσi+1 је 3-циклус на скупу {i, i+1, i+2}.
Bn, групе плетеница	генератори: ${\sigma }_1,\dots ,{\sigma }_{n-1}$ релације: ${\sigma }_i{\sigma }_j={\sigma }_j{\sigma }_i\text{ if }j\ne i\pm 1$, ${\sigma }_i{\sigma }_{i+1}{\sigma }_i={\sigma }_{i+1}{\sigma }_i{\sigma }_{i+1}$	Приметите сличност са симетричном групом; једина разлика је уклањање релације ${\sigma }_i^2=1$.
Шаблон:Nowrap, Клајнова 4-група	$⟨s,t\mid s^2,t^2,(st{)}^2⟩$
Шаблон:Nowrap, тетраедарска група	$⟨s,t\mid s^2,t^3,(st{)}^3⟩$
Шаблон:Nowrap, октаедарска група	$⟨s,t\mid s^2,t^3,(st{)}^4⟩$
Шаблон:Nowrap, икосаедарска група	$⟨s,t\mid s^2,t^3,(st{)}^5⟩$
Q8, кватернионска група	$⟨i,j\mid i^4,jij=i,iji=j⟩$	За алтернативну презентацију погледајте Dicn изнад са n=2.
SL(2, Z)	$⟨a,b\mid aba=bab,(aba{)}^4⟩$	тополошки a и b се могу визуелизовати као Денови обрти на торусу
GL(2, Z)	$⟨a,b,j\mid aba=bab,(aba{)}^4,j^2,(ja{)}^2,(jb{)}^2⟩$	нетривијална Z/2Z – проширење групе од SL(2, Z)
PSL(2, Z), модуларна група	$⟨a,b\mid a^2,b^3⟩$	PSL(2, Z) је слободан производ цикличних група Z/2Z и Z/3Z
Хајзенбергова група	$⟨x,y,z\mid z=xy{x}^{-1}{y}^{-1},xz=zx,yz=zy⟩$
BS(m, n), Баумслаг-Солитар групе	$⟨a,b\mid a^n=b{a}^m{b}^{-1}⟩$
Титсова група	$⟨a,b\mid a^2,b^3,(ab{)}^{13},[a,b{]}^5,[a,bab{]}^4,((ab{)}^{4}a{b}^{-1}{)}^6⟩$	[a, b] је комутатор

Пример коначно генерисане групе која није коначно презентована је венчани производ $𝐙\wr 𝐙$ групе целих бројева са самом собом.

Неке теореме

Теорема. Свака група има презентацију.

Да бисте ово видели, за дату групу G, размотрите слободну групу F_G над G. По универзалном својству слободних група, постоји јединствен хомоморфизам група Шаблон:Math чија је рестрикција на G идентитетска пресликавање. Нека је K језгро овог хомоморфизма. Тада је K нормално у F_G, стога је једнако свом нормалном затворењу, па је Шаблон:Math. Пошто је идентитетска пресликавање сурјективно, φ је такође сурјективно, па по Првој теореми о изоморфизму, Шаблон:Math. Ова презентација може бити веома неефикасна ако су и G и K много већи него што је потребно.

Последица. Свака коначна група има коначну презентацију.

Могуће је узети елементе групе за генераторе и Кејлијеву табелу за релације.

Новиков-Бунова теорема

Негативно решење проблема речи за групе каже да постоји коначна презентација Шаблон:Math за коју не постоји алгоритам који, за дате две речи u, v, одлучује да ли u и v описују исти елемент у групи. Ово је показао Пјотр Новиков 1955. године а другачији доказ је добио Вилијам Бун 1958. године.

Конструкције

Претпоставимо да G има презентацију Шаблон:Math и H има презентацију Шаблон:Math са S и T који су дисјунктни. Тада

• слободан производ Шаблон:Math има презентацију Шаблон:Math;
• директан производ Шаблон:Math има презентацију Шаблон:Math, где [S, T] значи да сваки елемент из S комутира са сваким елементом из T (уп. комутатор); и
• полудиректан производ Шаблон:Math има презентацију Шаблон:Math.

Дефицит

Дефицит коначне презентације Шаблон:Math је једноставно Шаблон:Math а дефицит коначно презентоване групе G, означен као def(G), је максимум дефицита преко свих презентација G. Дефицит коначне групе је не-позитиван. Шуров мултипликатор коначне групе G може бити генерисан са −def(G) генератора, а G је ефикасна ако је тај број потребан.

Геометријска теорија група

Презентација групе одређује геометрију, у смислу геометријске теорије група: имамо Кејлијев граф, који има метрику, названу метрика речи. Такође постоје два резултујућа поретка, слаби поредак и Бруаов поредак, и одговарајући Хасеови дијаграми. Важан пример су Коксетерове групе.

Даље, нека својства овог графа (груба геометрија) су интринзична, што значи да не зависе од избора генератора.

Види још

• Нилсенова трансформација
• Презентација модула
• Презентација моноида
• Нотација за конструкцију скупова
• Тицеова трансформација

Литература

• Шаблон:Cite book ― Ова корисна референца садржи табеле презентација свих малих коначних група, рефлексионих група, итд.
• Шаблон:Cite book ― Шрајерова метода, Нилсенова метода, слободне презентације, подгрупе и HNN екстензије, Голод-Шафаревичева теорема, итд.
• Шаблон:Cite book ― Основни алгоритми из теоријске рачунарске науке, рачунарске теорије бројева, и рачунарске комутативне алгебре, итд.

Спољашње везе

• Шаблон:MathWorld
• Small groups and their presentations on GroupNames