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 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 on a finite set , and produces two even permutations on the same set, such that .
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 , 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 is such a product, since has the same cycle structure as , and conjugating by preserves the conjugacy class. Conversely, if are conjugate permutations, then so are and so and thus 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 as commutators , and then we get because and commute for 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:
(a product of two -cycles), and
(a product of two -cycles) when . Square.
Let , be obtained from the above (as described, taking 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 such that , by using the special form of the permutations obtained from Ore’s argument. One could presumably instead directly give formulas for the permutations , 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 (in cycle notation or two-line notation) constructs two even permutations such that .
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 as and note that in we act by on the entries in the cycle representation of . So when writing a product of two cycles this way, it is easy to write down in two-line notation (i.e. as a function): should map the entries of the cycle to the entries of , in order, and it does not matter where other points are mapped.
So for an odd cycle with (we will discuss fixed points separately, let’s not count them as odd cycles), we take . Then so to map this to we should take
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 to be just the reversal map.
For a pair of two-cycles , with , we take and where s again indicate that we don’t care where the points are mapped.
We could now pick the images of that we do not care about suitably to get the correct parity, and use the symmetry of the situation for to do the same for , 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 , in the choice above has fixed points since it is an -cycle, and if we pick to be the reversal, then it has one fixed point and two-cycles.
For a pair of even cycles of lengths , has fixed points since it is an -cycle, and we can ensure has at least two-cycles: In the above formula for , we have determined the images of only; all but two of them have images in so we can map them back to their starting points, except for which already has a preimage.
Concretely, we can make the choice
where we understand that if then the images of are omitted and is just the reversal. Thus, in the case , in fact gains two-cycles.
Now we consider the final commutator where again is the product of the s and that of the s. To summarize the above discussion, in the odd case , always gains fixed points and gains two-cycles. In the even case : gains fixed points and gains two-cycles, except if then gains 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 , and at least one two-cycle in . Of course, each fixed point of the original permutation will be a fixed point of both and .
We will try to fix the parities of in two steps. First, we fix the parity of without changing the commutator. So suppose is odd (otherwise skip this step). Write , and suppose has at least one two-cycle . Then we can pick and because the cycles in the cycle representation of commute and .
Note that in this modification, (we rename back to ) may lose one or two fixed points (the ones that touch the cycle ), but if it loses two fixed points then it gains the new two-cycle .
We can do the same if has at least two fixed points, namely in the above we can pick where exchanges the two fixed points.
Next, suppose that is odd. We will do the exact same thing. Write . If has at least two fixed points (equivalently, does), pick to be the two-cycle that swaps them. Alternatively, if (equivalently ) has at least one two-cycle , pick . Then take . This permutation is even, and again because commutes with .
All in all, these steps manage to fix the parity (at least) if has at least two fixed points, and 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 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 and at least one two-cycle for , 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 (since there is at most one fixed point and there are at least five points in total). Then in the construction gains at least fixed points, and gains at least two-cycles, so we are done, since at the end will indeed have at least two fixed points, and at least one two-cycle, as required.
Suppose then that the only construction step is with a pair of even cycles of lengths . If , then gains at least fixed points, and gains at least two-cycle, so we are done. If , we get one fixed point for from the construction step, and since we gain two-cycles for . In this case, there must indeed be a fixed point for the original permutation (i.e. the cycle structure is precisely ), again since there are at least five points in total. Thus, in this case, also has the global fixed point, thus at least two in total, so again we are done. Square.