## Two faithful transitive actions of a 64-group on 8 elements

I've been more than a little obsessed with Galois Theory lately. I'm trying to understand how one goes about computing the Galois group of a general polynomial of low degree, which is a problem that gets complicated fast, and demands intimate familiarity with some commonly-occurring groups. So I have also spent some time trying to deeply understand the structure of some small finite groups.

It only occurred to me recently that knowing the Galois group of a polynomial still leaves something to be known about the symmetries of its roots. In particular, it does not tell you how that group acts upon the polynomial's roots. A group is not the same thing as a group action.

Just as groups are said to be isomorphic if there exists an operation-preserving bijection between them, group actions (of a fixed group $G$) are said to be isomorphic if there is a bijection between their underlying sets that respects the group multiplication. Sometimes group actions are nonisomorphic for obvious reasons, such as the underlying sets having different sizes (so that there cannot be any bijection between them at all) or one action being faithful while the other is not.

In Galois theory, we are mostly interested in faithful transitive group actions, since the action of an irreducible polynomial's Galois group upon its roots must be both faithful and transitive. In theory, it's possible for two polynomials to have the same Galois group and yet have their roots permuted in two different ways that are structurally fundamentally different, because their Galois groups exercise distinct actions upon their roots.

But off the top of my head, I wasn't able to come up with an example of a finite group $G$ with two inequivalent faithful and transitive actions on the same set. So I visited this awesome webpage enumerating transitive group actions on up to $31$ elements and looked for the simplest example of this phenomenon that I could find, which turned out to be a 64-element group that can act on an 8-element set in two nonisomorphic ways.

This page describes the two group actions in terms of their generators as subgroups of the symmetric group $S_8$, but it doesn't offer much intuition. It seems like a pretty fundamental counterexample to be familiar with, so I decided to take some time to try wrapping my head around the structure of these two group actions. After puzzling over this for a few days I was able to represent the group in two different ways using linear algebra over the finite field $\mathbb F_2$, and use the two representations to describe the inequivalent actions of this group.

That's the motivation behind this post! The below write-up is my attempt to describe

• Two groups $G_1,G_2$ of affine transformations over the finite field $\mathbb F_2$
• How $G_1$ and $G_2$ can both be made to act faithfully and transitively on 8 elements
• Why $G_1$ and $G_2$ are actually isomorphic to each other, and to $C_2 \wr C_2^2$
• Why these two group actions are not isomorphic to each other

Let's start by describing $G_1$ as a subgroup of the affine group of the 4-dimensional space $\mathbb F_2^4$. In particular, it is the group of all affine transformations of $\mathbb F_2^4$ taking the form $\mathbf x\mapsto A\mathbf x + \mathbf b$ where $\mathbf b\in\mathbb F_2^4$ is arbitrary and $A\in \text{GL}(4,\mathbb F_2)$ is one of the four permutation matrices corresponding to the action of the Klein 4-group on the coordinates of a vector, that is, one of the following four matrices, which may be called $I, A_1, A_2$ and $A_1 A_2$ respectively: Note that this group has $64$ elements, since there are $4$ choices for the linear part $A$ of the affine transformation and $2^4 = 16$ choices for the affine part $\mathbf b$, making for $4\times 16 = 64$ total affine transformations.

We can describe an action of $G_1$ on a set of $8$ elements by thinking of the linear part of each affine transformation as acting as a permutation, and acting of the translation part of each affine transformation as a sign change. Specifically, if we let $X$ be a set of $4$ formal variables and their additive inverses: Then we can let the affine transformation $\mathbf x\mapsto A\mathbf x + \mathbf b$ act upon this 8-element set by sending where $\sigma$ is the permutation of the Klein 4-group corresponding to $A$. Or, to describe the action in terms of the generators of the affine group:

• $\mathbf x\mapsto A_1\mathbf x$ sends $\pm x_1\leftrightarrow \pm x_2$ and $\pm x_3\leftrightarrow \pm x_4$
• $\mathbf x\mapsto A_2\mathbf x$ sends $\pm x_1\leftrightarrow \pm x_3$ and $\pm x_1\leftrightarrow \pm x_4$
• $\mathbf x\mapsto \mathbf x + \mathbf e_1$ sends $\pm x_1\leftrightarrow \mp x_1$ and fixes $\pm x_2,\pm x_3,\pm x_4$
• $\mathbf x\mapsto \mathbf x + \mathbf e_2$ sends $\pm x_2\leftrightarrow \mp x_2$ and fixes $\pm x_1,\pm x_3,\pm x_4$
• $\mathbf x\mapsto \mathbf x + \mathbf e_3$ sends $\pm x_3\leftrightarrow \mp x_3$ and fixes $\pm x_1,\pm x_2,\pm x_4$
• $\mathbf x\mapsto \mathbf x + \mathbf e_4$ sends $\pm x_1\leftrightarrow \mp x_4$ and fixes $\pm x_1,\pm x_2,\pm x_3$

where $\mathbf e_i$ are the four standard basis vectors of $\mathbb F_2^4$.

Next, let's describe the second group $G_2$ as a subgroup of the affine group on $\mathbb F_2^3$. We will define in to be the subgroup whose linear part takes the form of an invertible upper-triangular matrix. That is, $G_2$ consists of the affine transformations on $\mathbb F_2^3$ of the following form:

Note that this group also has $64 = 2^6$ elements, since there are $6$ parameters in the above mapping, each of which takes values over $\mathbb F_2$.

We'll consider the action of $G_2$ upon the entire space $\mathbb F_2^3$, which has precisely $2^3 = 8$ elements. It's clear that this action is transitive just by considering the pure translations, since any vector $\mathbf x_1\in \mathbb F_2^3$ can be sent to the vector $\mathbf x_2\in\mathbb F_2^3$ by the translation $\mathbf x \mapsto \mathbf x + (\mathbf x_2 - \mathbf x_1)$, which belongs to $G_2$.

It's not trivial to see (at least, it wasn't for me) that these two constructions describe isomorphic groups at all. Let's describe the isomorphism between them.

The group $G_1$ has a normal subgroup isomorphic to $C_2^4$ (which is acted upon by $V$) corresponding to the $16$ different pure translations, so we might start by trying to find this kind of substructure in the second group. To that end, we should be looking for $4$ distinct elements of $G_2$ that commute pairwise, each of which has order $2$. I found the following $4$ elements satisfying those conditions:

In case you're wondering how I found these, it wasn't by brute force - I have a little intuition about linear algebra over $\mathbb F_2$ that comes from thinking of invertible linear transformations as circuits built from CNOT gates. On three wires, it's not hard to convince yourself that a NOT gate on wire 1, a NOT gate on wire 2, a CNOT on wire 1 controlled by wire 3, and a CNOT on wire 2 controlled by wire 3 all commute with each other, and are all involutions (they invert themselves). The affine transformations $f_1,f_2,f_3,f_4$ are essentially descriptions of these gates. This means that the subgroup $\langle f_1,f_2,f_3,f_4\rangle$ generated by these four elements is isomorphic to $C_2^4$, and hence a candidate for the image of the $C_2^4$ subspace of our first group.

The following two elements generate the rest of the affine group (combined with the $f_i$), commute with each other, and also have order $2$, but they do not commute with all of the $f_i$:

This makes them candidates for the generators of the Klein four-group action upon the $f_i$. To find the isomorphism we seek, we would need to make sure that $g_1,g_2$ act upon the subgroup $\langle f_1,f_2,f_3,f_4\rangle$ by conjugation in the same way that $V$ acts upon $C_2^4$ in the semidirect product $C_2 \wr C_2^2$. Here is precisely how they act upon the four generators $f_i$:

Using this table, and the fact that the $f_i$ commute pairwise, one can show that conjugation by $g_1,g_2$ permutes the elements of the following alternative generating set: and they act upon them in precisely the same way as two generators of the Klein 4-group:

Hence we may construct the isomorphism by letting the standard basis vectors $\mathbf b_i$ correspond to the respective $f_i$, and the three nonidentity permutation matrices $A$ correspond to $g_1,g_2$ and $g_1g_2$. To make the isomorphism totally explicit, we may describe it as follows, where each parameter $\alpha_i$ belongs to ${0,1}$:

We can show that the two group actions are not isomorphic by comparing their point stabilizers. For those unfamiliar with the terminology, when $G$ is a group acting upon some set $X$, the point stabilizer of a point $x\in X$, sometimes denoted $G_x$, is defined as the subgroup of $G$ consisting of the elements $g\in G$ that fix $x$. When $g$ is a transitive group, all of the stabilizer subgroups of $G$ will be isomorphic to each other, despite possibly being different subgroups of $G$. In particular, if $g_{xy}\in G$ is some element that sends $x\mapsto y$, then we have that $G_x = g_{xy}^{-1}G_y g_{xy}$. So it makes sense to speak of "the stabilizer group" of a transitive group action.

For the first group, the stabilizer is isomorphic to $C_2^3$. To see why, we can deduce the form of the general element of $G_1$ that fixes a specific element of the set being acted upon, say $x_1$. The general element of $G_1$ can be described by a pair $(A,\mathbf b)$, where $\mathbf b\in C_2^4$ is a bit vector indicating sign changes and $A\in C_2^2$ is a matrix representing an element of the Klein 4-group that specifies how the formal variables are permuted. Any nonidentity value for $A$ will result in $x_1$ being sent to some other formal variable, hence $A$ must be the identity for elements $(A,\mathbf b)$ belonging to the stabilizer of $x_1$. Further, we must have $b_1 = 0$ so that the sign of $x_1$ is not changed. This leaves three free values, namely the last three coordinates $b_2,b_3,b_4$ of $\mathbf b$. If $A$ is equated to the identity element of $C_2^2$ and $\mathbf b$ is constrained to have $b_1 = 0$ while $b_2,b_3,b_4$ are allowed to range over $\mathbb F_2$, we obtain the group $C_2^3$, yielding the claimed stabilizer group.

Next consider the second group, and the stabilizer subgroup of the zero vector $\mathbf 0$. Any matrix sends $\mathbf 0\mapsto \mathbf 0$, so it is necessary and sufficient that the translation component of an affine transformation fix $\mathbf 0$ for the entire transformation to fix $\mathbf 0$. But the only translation fixing $\mathbf 0$ is the trivial translation. This means that the stabilizer of $\mathbf 0$ is precisely the subgroup consisting of linear transformations:

This is also an 8-element group, as can be deduced from the fact that each of the parameters $a_{12}, a_{13}, a_{23}$ ranges over two possible values. To confirm that this group is distinct from $C_2^3$, it's enough to find two non-commuting matrices of this form. With only a little more work, one can show that it is isomorphic to the dihedral group with $8$ elements, i.e. $D_4$. In particular, if $r,s$ are taken to be the two usual generators for $D_4$ with $r^4 = s^2 = e$ and $srs = r^{-1}$, then the following matrices $R,S$ can be taken as their respective equivalents in this stabilizer group:

Considering the point stabilizers is not the only way of distinguishing these two groups actions. Here are some other qualitative differences between them, which I found by writing some Haskell code to manipulate permutations:

• $G_1$ contains $4$ simple transpositions, but $G_2$ does not contain any.
• $G_1$ has $24$ permutations with a single 4-cycle, and $G_2$ has $8$ such permutations.
• In $G_1$, any permutation with a 4-cycle also transposes two pairs of the remaining 4 elements, whereas in $G_2$, any permutation with a 4-cycle transposes only one pair of the remaining 4 elements.
• $G_1$'s action has $12$ permutations that consist of two 4-cycles, and $G_2$ has $28$ such permutations.
• $G_2$'s action has $13$ permutations that consist of four disjoint transpositions, and $G_2$ has $17$ such elements.
• In $G_1$'s action, every ordered pair stabilizer has order $4$ or $8$, but in $G_2$'s action the pair stabilizers have orders $2,4$ and $8$.