# Finding the order of another element of a group

If in a group $G$, $a^5 = e$ , $e$ is the identity element of $G$. If $a,b \in G$ and $aba^{-1}=b^2$ then find the order of b

I have got no clue how to go forward with it, except that perhaps we can construct a cyclic group of order 5 with a and thus the order of $G$ will be $5k$ , but how to go forward from there, I have got no inkling.

Soham

-
Can you simplify $aaba^{-1} a^{-1}$? How many $a$s can you handle? – Jack Schmidt Jul 31 '12 at 21:23
Sorry I didnt get what you said, can you explain a bit more – Soham Jul 31 '12 at 21:26
You can discover the order of $b$ by trying to write $aaba^{-1}a^{-1}$ in a “better” form. $$aaba^{-1}a^{-1} = a(aba^{-1})a^{-1} = ab^2 a^{-1}$$ is already better, but in fact you can simplify even more to get $aaba^{-1}a^{-1}=b^4$. After that is done, try a few more $a$s. Eventually (hopefully soon) you discover the order of $b$ can only be two different numbers (and probably the examiner only wanted the bigger number). – Jack Schmidt Jul 31 '12 at 21:32
@Soham: almost. $b = b^{32}$ is correct, but that means $b^{31} = 1$, so $b$ has order 31 (or the dull case is that $b=1$ is already the identity). – Jack Schmidt Jul 31 '12 at 21:37
Notice that it's important here that 31 is prime. Also, as stated, technically there's another possibility besides 31. – MartianInvader Jul 31 '12 at 22:19

Here are some hints:

1. Since $a^5=e$, what integer $n$ will satisfy $(a^{-1})^n=e$
2. Now combine what you know about $a$ and $a^{-1}$ along with the equation $aba^{-1}=b^2$ to find an equation where the $a$s disappear.
-
Is 32 the answer? – Soham Jul 31 '12 at 21:35
Why do you think that is the answer? Notice I am not answering your question. I'm not sure what the answer is myself as I have not worked it out completely. Please explain how you got that answer. From there we can help you check your reasoning. – Code-Guru Jul 31 '12 at 21:37
No, I got it. $b=e.b.e$ = $a^5.b.a^{-5}$ and then applying the logic that $aba^{-1}=b^2$ which implies $b=b^{32}$ I went wrong here, which Jack corrected me. its $b^31=1_{G}$ order = 31 – Soham Jul 31 '12 at 21:41
FYI, you need to put { } around your exponents when they contain more than one character. – Code-Guru Jul 31 '12 at 21:43
THanks! Edited! – Soham Jul 31 '12 at 21:44

Feel free to ignore this. I hope it helps understand this group, but it definitely is not needed to understand the homework exercise.

## Two cool ways to work with groups like this

This example is an easy place to introduce two cool ways of working with groups. They both answer the question, "how do we know we are done simplifying? how do we know $b$ really could have order $31$?"

My favorite way of dealing with groups at first was with these rules. $a^5=e$ and $aba^{-1}=b^2$. They tell us how to multiply the elements, and it is much faster than with permutations. The only problem is that sometimes we have to be sneaky like @MarkBennet and @CodeGuru said: we have to replace nothing with $aa^{-1}$. That's kind of fun at first. “Ooo, look how clever I am.” Then one day I found some rules, and I just wasn't sure how clever to be.

It was really hard for me to decide if I was done simplifying. Maybe if I was clever, I could show $b^1 = e$ too...

## Rewriting systems

Luckily, these particular rules are actually very easy to turn into a simplification algorithm. The idea is that $aba^{-1} = b^2$ is the same as $ab =b^2a$. This rule, $ab \to b^2a$ lets us (reverse) alphabetize any word! Every time we have an $a$ before a $b$, we replace it with $b^2 a$, and now that $a$ has been taken care of. Once we take care of all the $a$s we are done!

The proof that we are done is reasonably easy computer science (found for instance in C.C. Sims Computations With Finitely Present Groups or Holt et al.'s Handbook of Computational Group Theory) and has two main ingredients: (1) a definition of “simpler” so we know which ways our rules go, and (2) a joining or "confluence" requirement that assures us that if two people apply the rules in a different order for a little while (so their rivers have split), then they can start applying the rules in order to get to the same point (and their rivers will join back up to flow together).

For instance (1) is "whoever has the least $a$s is simpler, but if they have the same number of $a$s, then look at all the stuff between $a$s and compare from right to left which one has the fewest $b$s" and (2) is "the only way to diverge is to have two rules apply to the same word, and the only real way to diverge is if those two rules overlap; we check the (very few) overlaps, and each one can be fixed by hand, thus all can be fixed".

In our case we get the following is a complete set of rules: $$\left\langle a,b : a^5 \mapsto e, ~b^{31} \mapsto e, ~ab \mapsto b^2a \right\rangle$$

You apply those rules (only forwards, never cleverly converting an $e$ to an $a^5$) and if you cannot apply them, then you have the “simplest” form of the word. Two words are equivalent if and only if their simplest forms look identical.

Summary Rewriting systems give a simple answer to “am I done simplifying?”

## Affine general linear group in dimension 1

Permutation groups are really nice because there is not really issue of “simplifying”, you just multiply the permutations together. If we could find permutations that obeyed the rules, then we'd be certain of at least one example that was completely done. The bad news is that permutations are a pain: multiplying $b$ times $a$ to get $ba$ is a heck of a lot easier than $(1,2,3)(4,5)$ times $(1,4)(2,3)(5,6)$ to get whatever.

It turns out there are better permutations in many cases: affine maps like $y=mx+b$ and just matrices in general.

We figured out $b^{31}=e$ and we want an example of $a$ and $b$ so that $b$ really does have order $31$. It turns out to be almost silly easy: we let $b$ be the permutation that takes $i \mod 31$ to $(i+1) \mod 31$. In this case, $b^2$ takes $i \mod 31$ to $((i+1)+1) \mod 31$, better known as $(i+2) \mod 31$. Clearly $b^n$ takes $i \mod 31$ to $(i+n) \mod 31$ so that $b^{31} = e$ and in fact $b^n =e$ if and only if $n$ is a multiple of $31$.

What should we make $a$ so that it does that “$2$” thing to $b$? This is genius: $a=2$. Or more exactly, $a$ takes $i \mod 31$ to $(2i) \mod 31$. So $b$ is “add one” and $a$ is “multiply by 2”. Ok check this out: what if we do $b$ and then $a$, well we get $(2(i+1)) \mod 31$, but that is just $((2i) + 2) \mod 31$, better known as $a$ and then $b^2$. Writing this as functions $$a(b(i)) = a(i+1) = 2(i+1) = 2i+2 = b^2(2i) = b^2(a(i))$$ so that $ab=b^2a$.

So here we have a concrete group where the rules are valid and where $b$ has order 31.

As a matrix group you can write it as $$a=\begin{bmatrix} 2 & . \\ . & 1 \end{bmatrix}, \qquad b = \begin{bmatrix} 1 & 1 \\ . & 1 \end{bmatrix}$$ where everything is taken mod 31. This is a (large) subgroup of the affine general linear group $$\operatorname{AGL}(1,K) = \{ f : K \to K : x \mapsto \alpha x + \beta ~\mid~ \alpha,\beta \in K, \alpha \neq 0 \} = \left\{ \begin{bmatrix} \alpha & \beta \\ . & 1 \end{bmatrix} : \alpha,\beta \in K, \alpha \neq 0 \right\}$$ where $K=\mathbb{Z}/31\mathbb{Z}$. Our elements $a$ and $b$ are given by $(\alpha=2,\beta=0)$ and $(\alpha=1,\beta=1)$.

Summary Matrix groups (even viewed as permutations) are very concrete, and can be very nice ways to verify your rules are not inconsistent.

-
Man! that was cool stuff... Jack, be my guru for group theory :) I have not done permutation group till now, hopefully by today/tomorrow I would be able to get started, but I have an inkling once I understand that stuff, your second part will make even more sense! I really like this new way of seeing things. Thanks – Soham Aug 1 '12 at 11:36

Hint  Repeatedly square $\rm\:a\,b\,a^{-1}\! = b^2\,$ using $\rm\, (a^n b\, a^{-n})^2\! =\, a^{n+1} b\, a^{-n-1}\,$ till $\rm\:a^5\! =\! 1\:$ kills all $\rm\:a$'s.

-

You can prove that $a^nba^{-n} = b^{2^n}$. So $b^{32} = a^5ba^{-5} = b$, which means $b^{31} = e$

-