## Introduction

This Friday we went international with a captivating lecture on the Grigorchuk Group and its good buddies given by guest lecturer Professor Rachel Skipper all the way from École Normale Supérieure in Paris!

## The Automorphisms of the Infinite Binary Rooted Tree

We’ll get to the Grigorchuk group in a bit, but let’s first start off with a group somewhat adjacent to it in its construction and motivation. We’d like to characterize some of the automorphisms of an infinite binary rooted tree (shown below).

I’ve labelled the vertices to help us when we consider automorphisms of this tree (symmetries that preserve gluing). With some experimentation, we can see that one valid symmetry could be swapping two branches that share a node above it. However, since this symmetry has to preserve gluing, every part below must also get swapped. It’s like a domino effect! I think this hints at the recursive nature of elements in this group. Let’s characterize these more rigorously now.

We have the group generated by three elements:

Where is a transposition, note that is it 2-torsion! This notation is a little bit confusing at first, but I hope to make it clear through a diagram. If we apply to our tree, we change the labels as follows. The smaller arrows represent the swapping at that level.

When we multiply these generators, we are able to move the permutations across the ordered pairs ‘at the cost’ of applying the permutation to the ordered pair. For instance, we have

So the multiplication in the ordered pairs is carried out component wise and we multiply the permutations as usual.

## Mealy Automata

As it turns out, a finite state automaton is able to capture this information in a really nice way for us. We define a *Mealy automaton* as a 4-tuple. Its four components are

- , a finite set of states
- , a finite alphabet
- , a function called the output function
- , a function called the transition function

This is a little different from the automata we’ve seen before, as our vertices hold more meaning and our edges are labelled a little differently. Again, we make this clear with an example.

Let’s write out the components of this Mealy Automaton:

- , a function is defined by following the arrow and seeing what element of corresponds to it on the edge. For example,
- , a function is defined similarly as above, except instead of the edge label, our value is the state the arrow leads to. For example,

This automaton is called the Alëshin automaton, and describes the generators above! Here’s how: recall we have . When we look at our machine, we see two arrows out of . The edge labels indicate the permutation and the destinations indicate what goes in the ordered pair. One arrow to has the label . The indicates that is in the first entry of the ordered pair, and the indicates that goes to .

So, these machine gives us an exact way of transforming strings of s and s with our states. This is powerful! Remember these strings correspond to vertices in our tree, so this allows us to see exactly where a vertex goes under some symmetry. We just have to follow each step, with our output and transition functions! Let’s try it with under .

– we reach the end of our string so no more state in our output

this is where 0110 ends up under the transformation

Note the multiplication and the ‘cost of moving an ordered pair across’ shows up here too! Fun fact: the group generated by is actually free! This was proven once by Aleshin, but that proof was lacking. As noted by Professor Skipper, it was proven properly by Vorobets and Vorobets in 2007. This paper is pretty readable!

## The Grigorchuk Group

We’ve now developed enough machinery to talk about the Grigorchuk group! Like the group above, it is most nicely described a Mealy automaton (shown below).

Like the group above, it can also be visualized as acting on a rooted binary tree. See below!

It is generated by the four elements (depicted above and written out below). Here, represents the group identity

The Grigorchuk group has some interesting properties! **One being that is it a finitely generated, infinite torsion group.** What’s more is that every element has order of a power of 2! Pretty crazy stuff. I’m not going to include a full proof here, but instead walk through an part of an example to maybe convince you of that last fact.

We can do computations to obtain

This means that we are able to write every element as an alternating product of s and other generators. More computation gives us

Can you see where this is going? Let’s do an explicit example.

We’d like to verify that

This is getting a little tiring to write, but at the end we are able to get down to a bunch of elements which are just the identity. I’m cutting this part just a little short because I’m really excited about the next section, but if you’re interested you should check out Chapter 6 in our book. The group there is the Gupta-Sidki group, which is similar (it looks at symmetries of an infinite rooted ternary tree). Professor Skipper noted that most of our present day finitely generated infinite torsion groups (more accessible ones anyways) come from groups adjacent to the Grigorchuk group!

## The Hanoi Towers Group

Speaking of infinite rooted ternary trees, we can use them to play (and beat) Hanoi! Ternary makes sense in the case of three pegs, as we can make at most 3 swaps at any moment. Let’s construct our automaton to help us.

- three pegs, labelled 1,2, and 3
- three nontrivial states representing possible moves between the pegs
- a string representing the current location of the discs

Note that this automaton codes in valid moves! I think that’s super cool! This automaton can actually tell us a lot more than just then 3 disc case, but let’s just consider the 3 disc case for now.

A graphical method of presenting this case is a *Schreier graph*. Informally, it is a way of capturing information about a self-similar group at a certain level. To give an example, look at this automaton called the Adding Machine.

We can see it acting on an infinite binary rooted tree below. The represents a swap, and the plain vertex indicates nothing (the identity).

As we can see on the tree, there are distinct ‘levels’! To construct a level -Schreier graph, we take the vertices of that level to be the states, and all the nontrivial states to be our directed edges.

As you might guess (and hinted at from the name) the group associated with the adding machine is actually \mathbb{Z}, the infinite cyclic group.

Now back to our Tower of Hanoi! Let’s look at our Level 3 Schreier graph.

The graph clearly shows the quickest way to win (just 7 moves) is from the state 111 to 333! One thing that really stands out to me is that this graph will show you how to get to *any *state. Another thing MurphyKate mentioned was that as we keep increasing the level, our Schreier graph will resemble the Sierpinski triangle!

Thank you for reading! A lot of the last section was from the book *A Sampling of Remarkable Groups* written by Bonanome, Dean and Dean.

I really enjoyed reading your post. There is so much extra information here. The Hanoi Towers Group is absolutely fascinating. It is so counter-intuitive about the infinite cyclic subgroup of the Hanoi Towers Group.

Really great job Akash! I really like the simplicity and the value behind the Grigorchuk group. It still baffles me that we can have finitely generated infinite torsion groups and I am excited to look inot more examples of this phenomenon.

This was a fantastic lecture and you really did it justice. The fact that we don’t have a general strategy for playing towers of Hanoi with n discs and m pegs is so interesting. I wonder if there’s computational data for small cases. It’s also just generally cool how that game with three pegs can be represented by a graph at all.

This is a great post and I was able to understand quite a bit of it, even though I missed the lecture. It sounds like you talked about some really interesting groups!