On a theorem of Ore

Theorem A (Ore, 1951). The commutator width of the alternating group on five or more points is one.

In other words, every element of the alternating group on at least $5$ elements is a commutator (of elements in that group).

For our work on distortion with Antonin Callard I decided to actually implement the so-called “commutator trick” (which maybe I’ll discuss in another post), and it felt natural to use Ore’s theorem since it the formulas that appear in the commutator trick are shorter by a multiplicative constant if we use it. For this, I of course needed a “constructive” proof of Ore’s theorem, i.e. I needed an algorithm that takes an even permutation $a$ on a finite set $S$ , and produces two even permutations $b, c$ on the same set, such that $a = [b, c] = bcb^{-1}c^{-1}$ .

Here’s Ore’s argument:

“A more thorough investigation whose details we shall omit here makes it possible to establish the stronger form of Theorem 1 [= Theorem B below].”

Although this is quite convincing, and far from the worst proof I have seen in terms of proof value, this is not very helpful when you need to actually explain the formulas to your computer. There has been quite a bit of further research into the topic of commutator width of simple groups (spoiler alert, it’s at most one), but the papers I found cite Ore’s paper for the alternating group, so they are not very helpful either.

In this post, I give a simple algorithmic proof of Theorem A. This is not exactly the actual algorithm I implemented, as there were some simplifications I came up with while writing this post (my program actually did one special case by brute force). Maybe I will test this later if I get around to revisiting my implementation, to see if it holds up in practice.

First, let us recall what Ore explicitly proves.

Theorem B (Ore, 1951). The commutator width of the symmetric group on five or more points is one.

In other words, any even permutation can be written as a commutator of two permutations (which may not be even themselves). In what follows, I act right-to-left with my permutations, and commutators are $a b a^{-1} \cdot b^{-1}$ , following Ore’s conventions.

Proof. It is well known that two permutations are conjugate (in the symmetric group) if and only if they have the same cycle structure. We first observe that a permutation is a commutator if and only if it can be written as a product of two conjugate permutations. Namely, a commutator $a b a^{-1} \cdot b^{-1}$ is such a product, since $a^{-1}$ has the same cycle structure as $a$ , and conjugating by $b$ preserves the conjugacy class. Conversely, if $a, c$ are conjugate permutations, then so are $a^{-1}$ and $c$ so $c = ba^{-1}b^{-1}$ and thus $ac = aba^{-1}b^{-1}$ is a commutator.

Back to the problem at hand, it now suffices to show that odd cycles and pairs of even cycles are commutators (on the same domain), as we can then represent the individual odd cycles and even-cycle-pairs of the cycle decomposition of an even permutation $g$ as commutators $[a_n, b_n]$ , and then we get $g = [A, B] = [\prod a_n, \prod b_n]$ because $a_m$ and $b_n$ commute for $m \neq n$ since they are on disjoint domains. Note that an even permutation is precisely one where there is an even number of even cycles in the cycle decomposition, so indeed we can go through the even cycles in pairs.

Representations as products of conjugate permutations are obtained as follows:
$(1, 2, \ldots, 2i + 1) = (1, 2, \ldots, i + 1)(i + 1, i + 2, \ldots, 2i + 1)$ (a product of two $(i+1)$ -cycles), and
$(1, \ldots, 2i) (2i+1,\ldots, 2i+2j) = (1, \ldots, i+j+1)(2i, i+j+1, \ldots, 2i+2j)$ (a product of two $(i+j+1)$ -cycles) when $j \geq i$ . Square.

Let $A = \prod a_n$ , $B = \prod b_n$ be obtained from the above (as described, taking $a_n, b_n$ the “commutatorands” obtained from the argument, for odd cycles and pairs of even cycles).

Our plan is to simply massage these permutations to get even permutations $A', B'$ such that $[A', B'] = [A, B] = g$ , by using the special form of the permutations obtained from Ore’s argument. One could presumably instead directly give formulas for the permutations $A', B'$ , but we couldn’t find simple formulas that do not involve a complicated case distinction. Let’s now restate Ore’s theorem and prove it.

Theorem A’. The commutator width of the alternating group on five or more points is one. Furthermore, there is a polynomial time algorithm that, given an even permutation $g$ (in cycle notation or two-line notation) constructs two even permutations $A, B$ such that $g = [A, B]$ .

Proof. Let’s first work out the concrete commutator representations for the products of conjugate permutations that were used in the previous proof. Concretely, recall that the idea is to write $aba^{-1}b^{-1}$ as $a \cdot ba^{-1}b^{-1}$ and note that in $ba^{-1}b^{-1}$ we act by $b$ on the entries in the cycle representation of $a^{-1}$ . So when writing a product $ac$ of two cycles this way, it is easy to write down $b$ in two-line notation (i.e. as a function): $b$ should map the entries of the cycle $a^{-1}$ to the entries of $c$ , in order, and it does not matter where other points are mapped.

So for an odd cycle $(1, 2, \ldots, 2i + 1) = (i+1, i+2, \ldots, 2i+1)(1, 2, \ldots, i + 1)$ with $i \geq 1$ (we will discuss fixed points separately, let’s not count them as odd cycles), we take $a = (i+1, i+2, \ldots, 2i+1)$ . Then $a^{-1} = (2i+1, 2i, \ldots, i+1)$ so to map this to $(1, 2, \ldots, i + 1)$ we should take
$b = \begin{pmatrix}1 & 2 & \cdots & i & i+1 & \ldots & 2i-1 & 2i & 2i+1 \\ * & * & \cdots & * & i+1 & \ldots & 3 & 2 & 1\end{pmatrix}$
where $*$ s indicate that it does not matter where these points are mapped (other than the fact we must get a permutation). For example, we can (and later will) pick $b$ to be just the reversal map.

For a pair of two-cycles $(1, \ldots, 2i) (2i+1, \ldots, 2i+2j) = (1, \ldots, i+j+1) (2i, i+j+1, \ldots, 2i+2j)$ , with $j \geq i$ , we take $a = (1, \ldots, i+j+1)$ and $b = \begin{pmatrix}1 & 2 & \ldots & i+j & i+j+1 & i+j+2 & i+j+3 & \ldots & 2i+2j \\ 2i+2j & 2i+2j-1 & \ldots & i+j+1 & 2i & * & * & \ldots & * \end{pmatrix}$ where $*$ s again indicate that we don’t care where the points are mapped.

We could now pick the images of $b$ that we do not care about suitably to get the correct parity, and use the symmetry of the situation for $a$ to do the same for $a$ , but the number of special cases this leads to seems to be long, so we use a slightly different approach which is also easy implement (and has no special cases).

We observe that for odd cycles of length $2i+1$ , in the choice above $a$ has $i$ fixed points since it is an $(i+1)$ -cycle, and if we pick $b$ to be the reversal, then it has one fixed point and $i$ two-cycles.

For a pair of even cycles of lengths $2i, 2j$ , $a$ has $i+j-1$ fixed points since it is an $(i+j+1)$ -cycle, and we can ensure $b$ has at least $i+j-2$ two-cycles: In the above formula for $b$ , we have determined the images of $1, \ldots, i+j+1$ only; all but two of them have images in $i+j+2, \ldots, 2i+2j$ so we can map them back to their starting points, except for $2i$ which already has a preimage.

Concretely, we can make the choice $b = \begin{pmatrix} 1& \ldots & i+j & i+j+1 & i+j+2 \;\; \ldots & 2j & 2j+1 & 2j+2 \;\; \ldots & 2i+2j \\ 2i+2j & \ldots & i+j+1 & 2i & i+j-1 \;\; \ldots & 2i+1 & i+j & 2i-1 \;\; \ldots & 1 \end{pmatrix}$
where we understand that if $i = j$ then the images of $i+j+1, i+j+2 \ldots, 2j$ are omitted and $b$ is just the reversal. Thus, in the case $i = j$ , $B$ in fact gains $i+j$ two-cycles.

Now we consider the final commutator $[A, B]$ where again $A$ is the product of the $a$ s and $B$ that of the $b$ s. To summarize the above discussion, in the odd case $2i+1$ , $A$ always gains $i$ fixed points and $B$ gains $i$ two-cycles. In the even case $2i \leq 2j$ : $A$ gains $i+j-1$ fixed points and $B$ gains $i+j-2$ two-cycles, except if $i = j$ then $B$ gains $i+j$ two-cycles. In particular, in each construction step (where we consider an odd cycle or a pair of even cycles) we gain at least one fixed point in $A$ , and at least one two-cycle in $B$ . Of course, each fixed point of the original permutation will be a fixed point of both $A$ and $B$ .

We will try to fix the parities of $A, B$ in two steps. First, we fix the parity of $A$ without changing the commutator. So suppose $A$ is odd (otherwise skip this step). Write $[A, B] = A B A^{-1} \cdot B^{-1}$ , and suppose $B$ has at least one two-cycle $c$ . Then we can pick $A' = Ac$ and $[A', B] = A c B c A^{-1} \cdot B^{-1} = [A, B]$ because the cycles in the cycle representation of $B$ commute and $c^3 = c$ .

Note that in this modification, $A$ (we rename $A'$ back to $A$ ) may lose one or two fixed points (the ones that touch the cycle $c$ ), but if it loses two fixed points then it gains the new two-cycle $c$ .

We can do the same if $B$ has at least two fixed points, namely in the above we can pick $A' = Ac$ where $c$ exchanges the two fixed points.

Next, suppose that $B$ is odd. We will do the exact same thing. Write $[A, B] = A \cdot B A^{-1} B^{-1}$ . If $A^{-1}$ has at least two fixed points (equivalently, $A$ does), pick $c$ to be the two-cycle that swaps them. Alternatively, if $A^{-1}$ (equivalently $A$ ) has at least one two-cycle $d$ , pick $c = d$ . Then take $B' = Bc$ . This permutation is even, and $A \cdot B' A^{-1} B'^{-1} = A \cdot B c A^{-1} c B'^{-1} = A \cdot B A^{-1} B'^{-1} = [A, B]$ again because $c$ commutes with $A^{-1}$ .

All in all, these steps manage to fix the parity (at least) if $A$ has at least two fixed points, and $B$ has at least one two-cycle, or has at least two fixed points. Note that if our initial permutation has at least two fixed points, then in particular $A, B$ both have two fixed points, so the fixing steps go through. Note also that if we perform at least two construction steps (again, this refers to a step where we consider an odd cycle or a pair of even cycles and construct a commutator presentation) in the proof, then since each construction step gives at least one fixed point for $A$ and at least one two-cycle for $B$ , again the fixing steps go through.

We show that this covers all cases: Suppose that there is at most one fixed point (as discussed, otherwise we are done). As discussed, we are done if there are at least two construction steps, so suppose there is only one. If the unique construction step is with an odd cycle, then this odd cycle is of length at least $2i+1 \geq 5$ (since there is at most one fixed point and there are at least five points in total). Then in the construction $A$ gains at least $i \geq 2$ fixed points, and $B$ gains at least $i \geq 2$ two-cycles, so we are done, since at the end $A$ will indeed have at least two fixed points, and $B$ at least one two-cycle, as required.

Suppose then that the only construction step is with a pair of even cycles of lengths $2i, 2j$ . If $i+j \geq 3$ , then $A$ gains at least $i+j-1 \geq 2$ fixed points, and $B$ gains at least $i+j-2 \geq 1$ two-cycle, so we are done. If $i+j = 2$ , we get one fixed point for $A$ from the construction step, and since $i = j$ we gain $i+j \geq 2$ two-cycles for $B$ . In this case, there must indeed be a fixed point for the original permutation (i.e. the cycle structure is precisely $(1, 2, 2)$ ), again since there are at least five points in total. Thus, in this case, $A$ also has the global fixed point, thus at least two in total, so again we are done. Square.