1
$\begingroup$

Can you help me with this? By trial, I came up with the generators and relation. However, how do I prove that the generators and relations uniquely determine $S_3$?


Problem Find a set of generators and relations for $S_3$

Solution Let $a=(1,2)$, $b=(2,3)$.

We have $ab = (1,2)(2,3) = (1,2,3)$, $ba = (2,3)(1,2) = (1,3,2)$. $aba = (1,2)(1,3,2) = (1,3)$.

Also, we have $a^2=b^2 = 1$. And we have all the $6$ elements.

Hence, $S_3 = \langle a,b \vert a^2=b^2=(ab)^3=1\rangle$.


Thanks

$\endgroup$

migrated from math.meta.stackexchange.com Dec 27 '13 at 0:50

This question came from our discussion, support, and feature requests site for people studying math at any level and professionals in related fields.

  • $\begingroup$ Thanks Isaac and Byron. So one is the front end and the other is the back end? But where does it say I should not post math questions on this page in the link you have. Also, how do I go to the "other" website from here? $\endgroup$ – John Smith Dec 27 '13 at 0:49
  • 4
    $\begingroup$ @LeslieFaulkner: At the left of the black bar near the top of the page, there is a "StackExchange" menu. Click on it, and near the top there are links for "Mathematics" and "Mathematics Meta". For more on meta, see this help page. $\endgroup$ – robjohn Dec 27 '13 at 0:58
  • 4
    $\begingroup$ "site where users discuss the workings and policies of Mathematics Stack Exchange rather than discussing math itself." This is what it says on the help page, though I can understand how you could have missed it. $\endgroup$ – user2055 Dec 27 '13 at 1:11
  • 3
    $\begingroup$ @LeslieFaulkner I'm sorry if the reception you've received hasn't been terribly friendly, so please let me welcome you. Keep in mind that math questions should be directed to the main site, while questions about math.se should be directed to meta - the two sites are separate for a reason. Also please note that the question limits (6 per day, 50 per month, I think) exist for a reason; although this is an excellent resource, you shouldn't post all of your assigned or practice questions here. Posting your questions on meta in order to get around this limit isn't a good idea. $\endgroup$ – user61527 Dec 27 '13 at 4:18
  • 4
    $\begingroup$ @LeslieFaulkner: When you posted your math questions on the meta site twice, there was a large box to the right of the title space that said in large letters, "Is your question about the Mathematics Stack Exchange community or website?" Your questions weren't. As a new user, you might want to make sure that you read at least the things in large bold type and pay attention to them before telling the longer-time users that they're being rude. $\endgroup$ – Isaac Dec 27 '13 at 5:50
4
$\begingroup$

Ok. I figured this out myself. Any element generated is of the form $n_1$ $a$'s followed by $n_2$ $b$'s followed by $n_3$ $a$'s followed by $n_4$ $b$'s and so on. Using the relation $a^2=1=b^2$, we can simplify all the elements to a sequence of alternating $a$'s and $b$'s, i.e., the elements are of the form $$abab\cdots ab \text{ or }baba\cdots ba$$ But we have $(ab)^3 = 1$. Hence, all the elements apart from the identity are $$\{a,ab,aba,abab,ababa,b,ba,bab,baba,babab,bababa\}$$

But we have

  • $bababa = a^2bababa = a(ab)^3a = a^2 = 1$.
  • $babab = bababa^2 = (ba)^3a = a$
  • $ababa = b(ab)^3 = b$
  • $(ab)^2 = b^2(ab)^2a^2 = b(ba)^3a = ba$
  • $(ba)^2 = a^2(ba)^2b^2 = a(ab)^3b = ab$
  • $aba = bab$

Hence, the only distinct elements are are $1, a,b,ab,ba,aba$. So $6$ elements and we can now do a one to one matching with elements of $S_3$.


As an aside, the users on this website are too rude. I am a new user and here to clarify questions on algebra. Shouting at a new user is is not the right way to welcome her!

$\endgroup$
4
$\begingroup$

(Short Writeup) Presentation of Symmetric Groups


1. Proving a set of elements are generators
If you can show that a set of elements generate all 2 cycles then they must generate $S_n$. This is because any $n$-cycles have a decomposition into 2-cycles. i.e. $$(a_1,a_2,a_3,\dots,a_n)=(a_1,a_2)(a_2,a_3,\dots,a_n)$$ and we repeat the process on $(a_2,a_3,\dots,a_n)$. Then having all 2-cycles we can generate any longer cycles.

For your case, since $S_3$ has only three 2-cycles $\{(1,2),(1,3),(2,3)\}$ and you have picked $a=(1,2),b=(2,3)$, it suffices to show that you can get the last one. $$ab=(1,2)(2,3)=(1,2,3)$$ $$aba=(1,2,3)(1,2)=(1,3)$$ which implies that $\langle a,b\rangle$ does generates $S_3$.

Note that since you have chosen $a,b$ such that $a^2=b^2=1$, the only sequence you can generate is $abab\dots$. You can show that $baba\dots$ must generate the same sequence.
So if $\{a,b\}$ are really generators then you must be able to get $(1,3)$ by $abab\dots$.


2. Generating 2-cycles and Coxeter group
A simple way to generate all 2-cycles is by using generators of the form: $$t_k=(k,k+1), 1\leq k<n$$ Proof: Suppose we can generate $(i,k)$ for some $i< k<n$. Then we have $(k,k+1)$ and: $$(k,k+1)(i,k)(k,k+1)=(k,k+1)(i,k,k+1)=(i,k+1)$$ gives us $(i,k+1)$. Since we have $(i,i+1)$, we can generate any $(i,j), i<j\leq n$. Then since we have $(i,i+1)$ for $1\leq i<n$, we can generate all $(i,j)$ for $1\leq i<j\leq n$, which are all 2-cycles. $\square$

As a result, we expect a presentation using these $n-1$ generators. We can check some defining relations, which will turn out to be sufficient: \begin{align*} R_1: &t_k^2 =1, 1\leq k<n\\ R_2: &(t_k t_{k+1})^3=1, 1\leq k<n-1\\ R_3: &(t_jt_k)^2=1, 1\leq j<k-1<n-1 \end{align*} In particular, $R_3$ represents the case where the two 2-cycles have no intersection. This type of group presentation is also known as a Coxeter group, i.e. a group with generators $\{s_i\}$ and relations are defined by: $$s_i^2=1 \text{ and }(s_is_j)^{m_{ij}}=1, m_{ij}\geq 2, i\neq j$$ It is also the most common representation for symmetric groups.

For our presentation, we denote the generators as $g_i$. We can show that $$S_n\cong \langle g_1,g_2,\dots,g_{n-1}|R_1,R_2,R_3\rangle=G_n$$ Where $R_1,R_2$ and $R_3$ are as before, but with $g_i$ in place of $t_i$.


3. Proof of Coxeter representation of for symmetric groups
This section describes a commonly used proof. Define a map $$\phi:G_n\to S_n$$ $$g_i\mapsto t_i$$ This is well defined since $R_1,R_2$ and $R_3$ are satisfied in $S_n$. The map is also surjective since the 2-cycles generate $S_n$. Therefore we have $$|G_n|\geq n!=|S_n|$$

Hence it suffices to show that $$|G_n|\leq n!=|S_n|$$ so that $|G_n|=|S_n|$ and the map is 1-to-1 and we have an isomorphism.

This is true for $n=2$: $$G_2=\langle g_1|g_1^2=1\rangle\cong S_2$$ such that $|G_2|\leq |S_2|$. Hence we assume $|G_{n-1}|\leq |S_{n-1}|=(n-1)!$ and prove the case for $n$. Define $$H=\langle g_2,\dots,g_{n-1}\rangle\subset G_n,$$ which is a subgroup of $G_n$. The defining relations of $G_n$ on $H$ is equivalent to the case in $G_{n-1}$. Hence by induction we know that $|H|\leq (n-1)!$. Our goal is to show that $$[G_n:H]\leq n$$ then using Lagrange's theorem for groups we have $$|G_n|=[G_n:H]|H|\leq n(n-1)!=n!$$ The condition $[G_n:H]\leq n$ can be interpreted as at most $n$ cosets. Hence we try a natural approach to construct $n$ cosets as below: $$S=\{H_0=H, H_1=g_1H, H_2=g_2g_1H,\dots, H_{n-1}=g_{n-1}\dots g_2g_1H\}$$ The goal now is to show that they are distinct.

The first observations are: $$g_iH_i=g_ig_ig_{i-1}\dots g_2g_1H=g_{i-1}\dots g_2g_1H=H_{i-1}$$ $$g_iH_{i-1}=g_ig_{i-1}\dots g_2g_1H=H_i$$ i.e. $g_i$ permutes $\{H_{i-1},H_i\}$. We can show that $g_i$ stabilizes all other $H_j$. In these cases, $|i-j|> 1$, so $i>j+1$ or $i<j-1$.

We will need to manipulate the relations. Recall that the relation $$(g_ig_j)^2=1, i< j-1$$ is equivalent to $$g_ig_j=g_jg_i,$$ i.e. we can swap the elements. The other relation $(g_ig_{i+1})^3=1$ says that: $$(g_ig_{i+1})(g_ig_{i+1})(g_ig_{i+1})=1$$ $$(g_ig_{i+1})(g_ig_{i+1})(g_ig_{i+1})(g_{i+1}g_ig_{i+1})=g_{i+1}g_ig_{i+1}$$ $$g_ig_{i+1}g_i=g_{i+1}g_ig_{i+1}$$ which allows us to do another kind of swapping. These two operations suffices to show $g_iH_j=H_j$.

First assume that $i> j+1$: \begin{align*} g_iH_j &=g_i(g_j\dots g_2g_1)H\\ &=(g_j\dots g_2g_1)g_iH\\ &= (g_j\dots g_2g_1)H\\ &=H_j \end{align*} where we simply sequentially swap $g_i$ towards $H$, since none of the cycles intersect $g_i$.

Now assume that $i<j-1$: \begin{align*} g_iH_j&=\underline {g_i}g_j\dots g_{i+1}g_ig_{i-1}\dots g_2g_1H\\ &= g_j\dots \underline{g_i}g_{i+1}g_ig_{i-1}\dots g_2g_1H\\ &= g_j\dots g_{i+1}g_i \underline {g_{i+1}}g_{i-1}\dots g_2g_1H\\ &= g_j\dots g_{i+1}g_ig_{i-1}\dots g_2g_1 \underline {g_{i+1}}H\\ &= g_j\dots g_{i+1}g_ig_{i-1}\dots g_2g_1H\\ &=H_j \end{align*} We did a shift followed by a triple-elements swap then by a shift. The step $g_{i+1}H=H$ is due to $g_{i+1}\in H$.

This shows that $G_n$ acts transitively on $S$, i.e. it preserves $S$. It is a theorem in group theory that in fact $S=G_n$ and there are exactly $n$ cosets, hence $[G_n:H]=n$ and we are done.


4. A Shorter Representation Using 2 Generators
Recall that the Coxeter group presentation for symmetric group is given by $$G_n=\langle g_1,g_2,\dots,g_{n-1}\;|\;R_1,R_2,R_3\rangle$$ \begin{align*} R_1: &(g_i)^2=1, \;\;\;\;\;\;\;1\leq i\leq n-1\\ R_2: &(g_ig_{i+1})^3=1, \;\; 1\leq i\leq n-1\\ R_3: &(g_ig_j)^2=1,\;\;\;\; 1\leq i<j-1<n-1 \end{align*}

We can obtain a shorter presentation by introducing a new generator $b=(1,2,\dots,n)$. By considering $a=g_1=(1,2)$ and $b$, we can show that they generate $g_2,\dots,g_{n-1}$. Therefore we can reduce the presentation to only 2 elements. We may then simplify the relations to involve only $a$ and $b$, the final result being $$G=\langle a,b\;|\;a^2=1,b^n=1,(ab)^{n-1}=1, (abab^{-1})^3=1, (ab^iab^{-i})^2=1,\;\;\;\; 2\leq i\leq n-2\rangle$$


5. Steps for Shorter Representation
We can add or delete generators and relations while preserving $G$, so that the new presentation of $G$ is structurally unchanged. i.e. $G\cong S_n$.

This procedure can be done through Tietze transformations, as mentioned by @Myself. It states that we can:
(1) add a relation if it can be derived from the current ones
(2) remove a relation if it does not affect the group
(3) add a generator if it can be generated by the group
(4) remove a generator if it is expressible by other generators

5.1 Introducing new generator $b$
We can introduce a new generator $b$ by setting: $$b=g_1g_2\dots g_{n-1}$$ then we adjust the presentation to \begin{align*} G &= \langle g_1,g_2,\dots, g_{n-1},b\;|\;R_1,R_2,R_3,R_4\rangle\\ R_4 &: b=g_1g_2\dots g_{n-1} \end{align*} Let $g_1=a$, which we use interchangeably. The addition of $b$ allows us to derive new relations between $a,b$ and $g_i$: \begin{align*} bab^{-1}&=(g_1g_2\dots g_{n-1})g_1(g_{n-1}\dots g_2g_1) = (g_1g_2)g_1(g_2g_1)\\ &=(g_2g_1g_2)(g_2g_1)\\ &=g_2\\ \text{Assume} &: b^{i-1}ab^{-(i-1)} = g_i\\ \text{Induction step:}&\\ b^iab^{-i}& =b(b^{i-1}ab^{-(i-1)})b^{-1}=bg_ib^{-1}=(g_1g_2\dots g_ig_{i+1}\dots g_{n-1})g_i(g_{n-1}\dots g_{i+1}g_i\dots g_2g_1)\\ &= (g_1g_2\dots g_ig_{i+1})g_i(g_{i+1}g_i\dots g_2g_1) = (g_1g_2\dots g_{i-1})(g_{i+1}g_ig_{i+1})(g_{i+1}g_i\dots g_2g_1)\\ &= (g_1g_2\dots g_{i-1})g_{i+1}(g_{i-1}\dots g_2g_1)=(g_1g_2\dots g_{i-1})(g_{i-1}\dots g_2g_1)g_{i+1}\\ &= g_{i+1} \end{align*} Hence the induction shows that $$b^{i-1}ab^{-(i-1)}=g_i\text{ for }1\leq i\leq n-1.$$ i.e. we can represent $g_i$ purely in terms of $a$ and $b$. Therefore we can remove all the generators and relations involving $g_2,g_3,\dots, g_{n-1}$ by this substitution.

5.2 Replacing relations $R_1$
The first consequence is $R_1$ is now redundant. Consider $ (g_{i+1})^2=1\in R_1$: $$(g_{i+1})^2=1\Longleftrightarrow (b^iab^{-i})^2=1\Longleftrightarrow 1=1$$ which is trivial provided $(g_1)^2=a^2=1$ (also in $R_1$). Therefore we can keep $a^2=1$ and discard the rest, which turns $R_1$ into just $a^2=1$.

5.3 Replacing relations $R_2$
Now let us take any relation in $(g_ig_{i+1})^3=1\in R_2$: \begin{align*} (g_ig_{i+1})^3=1\longrightarrow ((b^{i-1}ab^{-(i-1)})(b^iab^{-i}))^3=1\\ (b^{i-1}abab^{-i})^3=1\\ (b^{i-1}iabab^{-i}) (b^{-1}iabab^{-i}) (b^{-1}iabab^{-i})=1\\ b^{i-1}abab^{-1}abab^{-1}abab^{-i}=1\\ b^{-(i-1)}(b^{i-1}abab^{-1}abab^{-1}abab^{-i})(b^{i-1})=(b^{-(i-1)})(b^{i-1})\\ abab^{-1}abab^{-1}abab^{-1}=1\\ (abab^{-1})^3=1 \end{align*} And therefore $R_2$ is reduced to a single relation: $(abab^{-1})^3=1$.

5.4 Replacing relations $R_3$
Our next step is to investigate $R_3$, with relations of the form $$R_3: (g_ig_j)^2=1, \;\;\;\;1\leq i\leq j-2\leq n-2$$ \begin{align*} (g_ig_j)^2=1\longrightarrow ((b^{i-1}ab^{-(i-1)})(b^{j-1}ab^{-(j-1)}))^2=1\\ (b^{i-1}ab^{-i+j}ab^{-(j-1)})^2=1\\ (b^{i-1}ab^{-i+j}ab^{-(j-1)})(b^{i-1}ab^{-i+j}ab^{-(j-1)})=1\\ b^{i-1}ab^{-i+j}ab^{-j+i}ab^{-i+j}ab^{-(j-1)}=1\\ b^{-(i-1)}(b^{i-1}ab^{-i+j}ab^{-j+i}ab^{-i+j}ab^{-(j-1)})b^{i-1}=(b^{-(i-1)})(b^{i-1})\\ ab^{-i+j}ab^{-j+i}ab^{-i+j}ab^{-j+i}=1\\ (ab^{-i+j}ab^{-j+i})^2=1\\ \end{align*} From the initial conditions, we observe that $$j-i\geq 2$$ and when $i=1$ and $j-2=n-2$, we have $$j-i=(n-3)+1=n-2$$ Therefore $2\leq j-i\leq n-2$. Replacing $j-i$ by $i$, we find the new $R_3$ as: $$R_3: (ab^iab^{-i})^2=1,\;\;\;\; 2\leq i\leq n-2$$

5.5 Replacing relations $R_4$
We are left with the last, new relation $R_4: b = g_1g_2\dots g_{n-1}$.

A simple substitution shows: $$b = g_1g_2\dots g_{n-1}=a(bab^{-1})(b^2ab^{-2})\dots(b^{n-2}ab^{-(n-2)}) = ababab\dots bab^{-(n-2)}$$ $$b=(ab)^{n-1}b^{-n+1}$$ $$b^n =(ab)^{n-1}$$ It remains to show that $b^n=1=(ab)^{n-1}$. This is a bit tricky on $G$, so we use the isomorphism $G\cong S_n$ to deduce that $b=g_1g_2\dots g_{n-1}=(1,2,\dots n)$. Therefore $(ab)^{n-1}=b^n=(1,2,\dots,n)^n=1$ and we find: $$R_4: b^n=1, (ab)^{n-1}=1$$

5.6 Putting everything together
Combining all the new relations: $$G=\langle a,b\;|\;a^2=1,b^n=1,(ab)^{n-1}=1, (abab^{-1})^3=1, (ab^iab^{-i})^2=1,\;\;\;\; 2\leq i\leq n-2\rangle$$ where \begin{align*} R_1 &: a^2=1\\ R_2 &: (abab^{-1})^3=1\\ R_3 &: (ab^iab^{-i})^2=1,\;\;\;\; 2\leq i\leq n-2\\ R_4 &: b^n=(ab)^{n-1}=1 \end{align*} Note that we know that $G\cong S_n$ during all these substitutions, since the operations involved does not change $G$. This completes the presentation shown in section 4.

$\endgroup$
  • $\begingroup$ A fine answer, but of course for $\mathbf S_n$, you skipped the hard part where you have to show that the map $\langle a,b \mid a^2,b^n,(ab)^{n-1}\rangle \to \mathbf S_n$ is injective. (Usually shown by counting the order of both sets.) $\endgroup$ – Myself Dec 27 '13 at 11:22
  • $\begingroup$ Thanks. This is a useful representation. However, you need to show that $S_n$ is actually described by your description. $\endgroup$ – John Smith Dec 27 '13 at 16:39
  • $\begingroup$ @Myself I actually missed out 2 relations $(ab^{-1}ab)^3=1, (ab^{-i}ab^i)^2=1$ for $2\leq i\leq \lfloor n/2\rfloor$. I will be editing this, but it will take a while. $\endgroup$ – Yong Hao Ng Dec 27 '13 at 19:17
  • $\begingroup$ @LeslieFaulkner Please note my comment directly above. I am editing my answer, please give me a while. $\endgroup$ – Yong Hao Ng Dec 27 '13 at 19:18
  • 1
    $\begingroup$ @LeslieFaulkner I have finished writing my answer, but it may be too lengthy for your taste. You might be interested in only sections 2 and 3, which describes the most common representation for symmetric groups using Coxeter groups and the proof respectively. Sections 4 and 5 describes how one might transform the Coxeter presentation into a two generator form. $\endgroup$ – Yong Hao Ng Dec 28 '13 at 15:23
1
$\begingroup$

Well, since the problem asked only for some set of generators and relations, not a reasonably efficient set, there's a really cheap answer: Take all $6$ elements of $S_3$ as your generators. Let the relations be $abc^{-1}=1$ for all $a,b,c$ such that $ab=c$; in other words, take the whole multiplication table as your set of relations.

The point is that any group has a silly set of generators and relations like this. The problem really should have asked for a reasonably small set of generators and relations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.