# How to write down explicit elements of a group from its presentation?

Let $$G=\langle s_1, s_2, s_3 \mid s_1^2=s_2^2=s_3^2=1, (s_1s_2)^4=(s_2s_3)^3=(s_1s_3)^2=1 \rangle.$$

How to write down explicit elements of $G$?

The following elements $$1, \ s_1, \ s_1s_2, \ s_1s_2s_1, \ s_1s_2s_1s_2, \ s_1s_2s_1s_2s_1, \ s_1s_2s_1s_2s_1s_2, \ s_1s_2s_1s_2s_1s_2s_1, \\ s_2, \ s_2s_3, \ s_2s_3s_2, \ s_2s_3s_2s_3, \ s_2s_3s_2s_3s_2, \\ s_3, \ s_3s_1, \ s_3s_1s_3$$ are in $G$, what are the other elements (I think there are $48$ elements)? Thank you very much.

-
Your question is, rather, «how to make a non-redundant list of the elements of the group?» Writing elemtents of the group explicitly is trivial: just write arbitrary words in the generators and their inverses! –  Mariano Suárez-Alvarez Jul 26 '12 at 18:19
In addition to the excellent mechanical answers, you might want to have a look at drawing out the Cayley Graph of the group, with nodes labeled by elements and edges labeled by generators - it should reveal some interesting underlying structure here... –  Steven Stadnicki Jul 26 '12 at 18:27
@StevenStadnicki, constructing the graph from the presentation is the Todd-Coxeter enumeration :-) –  Mariano Suárez-Alvarez Jul 26 '12 at 18:31

An alternative to Todd-Coxeter enumeration is Knuth-Bendix rewriting. Coxeter groups have pretty nice rewriting systems. As @Qiaochu Yuan mentions, every element of a Coxeter group has an expression as a “reduced” word (which for Coxeter groups, means “of shortest length”). Unfortunately, elements have multiple expressions as reduced words, so you have to be a little careful listing them. While there are some pretty easy combinatorial ways to check which element you've got, you might appreciate a simple way of always getting the same reduced word. This is called a (reduced, confluent) rewriting system.

The one for $B_3$ is quite simple:(Editted to correct reduction ordering) $$\begin{array}{rcl} s_i \cdot s_i &\mapsto& 1 & 1 \leq i \leq 3 \\ % s_3 \cdot s_1 &\mapsto& s_1 \cdot s_3 \\% s_3 \cdot s_2 \cdot s_3 & \mapsto &s_2 \cdot s_3 \cdot s_2 \\% s_2 \cdot s_1 \cdot s_2 \cdot s_1 &\mapsto&s_1 \cdot s_2 \cdot s_1 \cdot s_2 \\ s_3 \cdot s_2 \cdot s_1 \cdot s_3 &\mapsto& s_2 \cdot s_3 \cdot s_2 \cdot s_1 \\ s_3 \cdot s_2 \cdot s_1 \cdot s_2 \cdot s_3 \cdot s_2 &\mapsto&s_2 \cdot s_3 \cdot s_2 \cdot s_1 \cdot s_2 \cdot s_3 \end{array}$$

Each line indicates a rule. If you have some products of $s_i$, you keep blindly applying these rules until you can't anymore. Notice each rule has a direction. Only apply them forwards, never in reverse. In a presentation, you might have to use the rules in reverse, but in a rewriting system the rules only go one way. If you cannot apply any of the rules, then you are done, and you have a reduced word. In fact, amongst all reduced words for that element, you have the one that comes first alphabetically.

The rules themselves are pretty simple. Repeated generators go away. Alphabetize 31 to 13, since the presentation told you they were the same. Alphabetize 323 since $(s_2 s_3)^3$ can be rewritten as the “braid relation” $s_3 s_2 s_3 = s_2 s_3 s_2$, and we want the alphabetically first version. Similarly, converting $(s_1 s_2)^4$ into its braid relation and choosing the alphabetically first one, you get the fourth rule. The only slightly surprising rule is the last one, which is just needed to alphabetize a more complicated Braid relation.

-
Should the left side of the last be s3.s1.s2.s3.s1.s2? As listed, it's the only one that doesn't feature the same multiset of generators on both sides... –  Steven Stadnicki Jul 26 '12 at 20:51
@StevenStadnicki: $s_3 \cdot s_1 \cdots$ is not the left hand side of any rule, since its prefix $s_3 \cdot s_1$ is already the left hand side of a rule. The rule is a little funny though, so I had the computer do the calculation and got a slightly different system. I think the old was correct, but for a different (weird) ordering. I had started using $s_n$ as the special generator, and then flipped it back to $s_1$ being special. However, that obviously changes what alphabetical means. –  Jack Schmidt Jul 26 '12 at 22:24

The canonical answer to this question is the Todd-Coxeter enumeration algorithm.

-
Pretty much anything you try to do «by hand» will be an approximation to the T-C's algorithm... so you might just as well go for it. It is pretty simple, in fact. You can find a very nice description in Rotman's book on group theory for example. –  Mariano Suárez-Alvarez Jul 26 '12 at 18:23
Moreover, software like GAP (gap-system.org) will use this to answer your question. –  Mariano Suárez-Alvarez Jul 26 '12 at 18:24
thank you. Which package of GAP should I use? –  LJR Jul 26 '12 at 18:49
GAP itself :-) ${}$ –  Mariano Suárez-Alvarez Jul 26 '12 at 18:51
It seems that in GAP 4, we cannot use weyl_goup package. –  LJR Jul 26 '12 at 18:54

In the special case of Coxeter groups there are almost-non-redundant expressions for all of the elements of the group given by reduced words, and the ambiguity in when two reduced words give the same element of the group is well-understood. For a definition and more background see, for example, Björner and Brenti's Combinatorics of Coxeter Groups (in particular sections 1.4 and 3.4).

-

For certain groups, if you have the right geometric picture and the right geometric tools you can draw out the Cayley graph. For this example, you can sketch out on the surface of a 2-sphere a blue triangle with angles $\pi/2$, $\pi/3$, and $\pi/4$. Draw a red dot in the middle of the triangle. Next, reflect this triangle and its red dot across each of its three blue sides, getting three new blue triangles each with a red dot in its middle, representing the three reflections $s_1,s_2,s_3$. Connect red dots by a red arc when they are in triangles that share a side. Now continue the whole process, reflecting across each blue side, drawing new red dots in each new blue triangle and adding new red arcs appropriately. When you are done, throw away all the blue triangles and keep just the red graph, which will form a truncated cubeoctahedron which gives the Cayley graph. You can then count the 48 vertices, and write out 48 words for each element of the group, at your leisure.

-