Find a set of generators and relations for $S_3$

Question

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

Answer 1

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!

Answer 2

(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.

Answer 3

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.