Week 6 Friday: The Grigorchuk Group and its Friends

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 $G = \langle a, b, c \rangle$ generated by three elements:

$a = (c,b) \sigma$
$b = (b,c) \sigma$
$c = (a,a)$

Where $\sigma = (01)$ 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 $a$ to our tree, we change the labels as follows. The smaller arrows represent the swapping at that level.

our tree with a applied to it. as we can see, there’s a cascade!

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

$a \cdot b = (c,b) \sigma (b,c) \sigma$
$a \cdot b = (c,b)(c,b) \sigma \sigma$
$a \cdot b = (c^2,b^2)$

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

$Q$ , a finite set of states
$X$ , a finite alphabet
$\lambda$ , a function $Q \times X \rightarrow X$ called the output function
$\tau$ , a function $Q \times X \rightarrow Q$ 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:

$Q = {a,b,c}$
$X = {0,1}$
$\lambda$ , a function $Q \times X \rightarrow X$ is defined by following the arrow and seeing what element of $X$ corresponds to it on the edge. For example, $\lambda (a,0) = 1$
$\tau$ , a function $Q \times X \rightarrow Q$ is defined similarly as above, except instead of the edge label, our value is the state the arrow leads to. For example, $\tau(a,0) = c$

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

So, these machine gives us an exact way of transforming strings of $0$ s and $1$ 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 $0110$ under $a$ .

$a0110$
$(a0)110$
$(1c)110$
$1(c1)10$
$1(1a)10$
$11(a1)0$
$11(0b)0$
$110(b0)$ – we reach the end of our string so no more state in our output
$1101 \leftarrow$ this is where 0110 ends up under the transformation $a$

Note the multiplication and the ‘cost of moving an ordered pair across’ shows up here too! Fun fact: the group generated by $a,b,c$ 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!

the generators acting on the tree courtesy of Wikipedia

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

$a = (e,e) \sigma$
$b = (a,c)$
$c = (a,d)$
$d = (e,b)$

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

$a^2=b^2=c^2=e$
$bc = cb = d$
$cd = dc = b$
$bd = db = c$

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

$aba = (c,a)$
$aca = (d,a)$
$ada = (b,c)$

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

We’d like to verify that $(ab)^{16}=1$

$abababababababababababababababab$
$(aba)a(aba)a(aba)a(aba)a(aba)a(aba)a(aba)a(aba)a$
$(c,a)(a,c)(c,a)(a,c)(c,a)(a,c)(c,a)(a,c)(c,a)(a,c)(c,a)(a,c)(c,a)(a,c)(c,a)(a,c)$
$(caca...,acac...)$

This is getting a little tiring to write, but at the end we are able to get down to a bunch of $b^2$ 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

here’s an example of the string and how it changes. this example uses 0,1,2 labels instead of 1,2,3

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 $n$ -Schreier graph, we take the vertices of that level to be the states, and all the nontrivial states to be our directed edges.

Level 2 Scheirer graph for the Adding Machine

Level 3 Scheirer graph for the Adding Machine

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.

4 Responses to Week 6 Friday: The Grigorchuk Group and its Friends

Shuhang Xue says:

October 25, 2022 at 12:27 am

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.

Osip Surdutovich says:

October 27, 2022 at 8:21 pm

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.

Horace Fusco says:

October 31, 2022 at 6:44 pm

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.

Michaela Polley says:

November 2, 2022 at 4:57 am

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!