I was recently reminded of a very simple chestnut about sampling elements from finite groups. This is the kind of problem you give your intro group theory students to test whether or not they are paying attention, or at least to keep them busy; nothing special. But the way it was worded suggested a harder version of the problem that immediately piqued my interest, and though I haven’t fully solved it yet, it ended up tying itself up in a neat little bow by the end of it.

So here’s the easy problem. What is the probability that $k$ group elements sampled uniformly at random from the finite group $G$ multiply together to form the identity? To be precise, if $g_i \in G$ were sampled uniformly randomly, what is $\mathrm P(g_1 \cdots g_k = 1)$?

I’m not going to beat around the bush and stall for time in order for you to pause and solve it any longer than it takes for you to finish reading this sentence, so look away if you must. The answer is $1/\lvert G \rvert$, regardless of the value of $k$. This is because, once you’ve sampled $g_1$ through $g_{k-1}$, the final element must be exactly $(g_1 \cdots g_{k-1})^{-1}$ in order to get the identity.

You can end the story here, and leave it as a cute problem to toss out if you ever wanna make sure someone remembers how groups work.

Or, you can do what I did, and mishear the problem statement as follows. What is the probability that $k$ group elements, sampled uniformly at random from the finite group $G$, multiply together in some order to form the identity? To be precise, for $g_i$ as before, what is

$$p(G,k) := \mathrm P(\exists \sigma \in S_k: g_{\sigma_1} \cdots g_{\sigma_k} = 1)?$$

Now we’re talking about something interesting! This problem seems hard in general. I haven’t found a solution, nor do I know where to find it in the literature, if it exists there at all.

For the sake of terminology, if $A$ is a multiset of elements of $G$, say that a Wilsonian product¹ of $A$ is some ordered product of all the elements of $A$. Let $w(A)$ be the set of all Wilsonian products of $A$, so that we can restate

$$p(G,k) = \mathrm P(1 \in w(\text{sample of size}\ k)).$$

So, some easy observations to begin with. $p(G,k) \ge 1/\lvert G \rvert$ because the easy version of this problem is a lower bound. In fact, $p(G,1) = p(G,2) = 1/\lvert G \rvert$.

Let’s try to solve $p(G,3)$. $g_3$ must equal either $(g_1g_2)^{-1}$ or $(g_2g_1)^{-1}$ in order to make the identity possible, and those fail to be distinct elements iff $g_1$ commutes with $g_2$. So we find that

$$p(G,3) = \frac{2 - \text{comm.prob.}}{\lvert G \rvert},$$

involving the commuting probability, an atrocious number. Perhaps there is some slicker argument, but I don’t see any. From where I’m standing this just looks like increasingly horrifying case analysis, so I propose we just let this go for now.

For the next round of observations, recall the derived group $G' = [G,G]$ generated by all the commutators $[g,h] = ghg^{-1}h^{-1}$. This is a normal subgroup of $G$, and the quotient $G/G'$ is also known as the abelianization $\def\ab{\textrm{ab}}G^\ab$.

These are relevant because across all $\sigma \in S_k$, $g_{\sigma_1} \cdots g_{\sigma_k}$ always has the same image under the quotient map $G \to G^\ab$. So for instance, if the image $\overline{g_1 \cdots g_k}$ is not equal to $\overline1 \in G^\ab$, then there’s no possible reordering that could give a product of the identity. This amounts to an upper bound $p(G,k) \le 1/\lvert G^\ab \rvert$. If $G$ is abelian then $G = G^\ab$ so $p(G,k) = 1/\lvert G \rvert$.

Seeing no more convenient inroads for specific $k$, we perform the standard mathematical give-up maneuver of turning to the asymptotics, in this case letting $k \to \infty$. Let’s abbreviate

$$p(G,\infty) = \lim_{k\to\infty} p(G,k).$$

It behooves me to justify the existence of this limit in order to say that, but I’ll do you one better, by pinning down its value over the course of the rest of this ‘blog post. In fact, let’s get right into it:

Proposition. $p(G,\infty) = 1/\lvert G^\ab \rvert$.

Proof Sketch. $p(G,k) \le 1/\lvert G^\ab \rvert$ so $p(G,\infty) \le 1/\lvert G^\ab \rvert$ also. We may assume that $\overline{g_1 \cdots g_k} = \overline1$ and our task is to find a reordering equal to $1$ with arbitrarily high probability. For any multiset $A$ of elements of $G$, we may assume that $A$ is a submultiset of our sample with arbitrarily high probability by taking $k$ sufficiently large. Suppose there exists a choice of multiset $A$ such that the Wilsonian products $w(A)$ contain every element of $\overline A{}^{-1} \in G^\ab$. Then, for any ordered product of $(g_i) - A$, there exists an inverse in $w(A)$, so pick an arbitrary order of $(g_i) - A$ and use the corresponding ordering of $A$ to cancel it. ∎

This limit trick reduces the proof of the proposition to the task of finding such an $A$—for convenience I’ll call it a flexible multiset—and it is due to Discord user smorc. The smaller $|A|$ is, the better the concrete bounds, but any flexible $A$ will suffice to prove this in the limit.

My contribution to the problem was to actually construct a flexible $A$, first for $G = S_n$ and then for all finite groups $G$. It will have $w(A) = G'$, which is to say $\overline A = \overline 1 \in G^\ab$, so in what follows I will be talking as if that is a given, even though strictly speaking it is a coincidence and flexibility is more general than that.

Recall that $G'$ is generated by commutators $[g,h] = ghg^{-1}h^{-1}$. Let $S$ be a generating multiset of $G'$ consisting entirely of commutators. A generating multiset is like a generating set, but it has the multiplicities baked into it already, so that every element of $G'$ can be expressed as the ordered subproduct² of $S$.

These obviously exist, because you can take $S$ to be a sufficiently large multiple of a plain old generating set, and decomposing all its products of commutators into their factors. We incur no penalty to the size of $S$ in doing this, and because of the way we turn $S$ into $A$—you’ll see in just a moment—it actually allows for more potential reductions in size.

Finally, let $A$ be the multiset

$$\sum_{[g,h] \in S} (g, g^{-1}, h, h^{-1}).$$

That is to say, for every commutator in $S$, take into $A$ its four factors. By construction, $w(A) = G'$. To see this, for $c \in G'$, write it as an ordered subproduct of $S$, so that it is also an ordered subproduct of $A$; then for every remaining element of $A$, its inverse is also present, so you can tack them onto the end in inverse pairs. This is not the most efficient $A$ you can get out of $S$, but it’s the easiest to specify and justify.

And that’s the whole problem. This $A$ slots right into the proof sketch above and we’re done!

That felt a little short to me, so let’s screw around a little more with examples and “historical” notes, before I end this post.

For $G = S_n$, we have $G' = A_n$ and $G^\ab = \{\text{even}, \text{odd}\}$. We can take $A$ to be the multiset containing every transposition of $S_n$ twice. You can even do a hands-on argument, as I originally did, where you handle arbitrary $\tau \in A_n$ by doing each cycle separately and finishing off the induction by handling the case of double transpositions.

I was pretty proud of this because I hadn’t had a nice problem in a while and I got to put to use my experience with fiddling with $A_n$. You see, in 2016, I had to prove $A_n$ was simple for $n\ge5$ as part of an algebra assignment, so I am regrettably quite practiced with permutation groups.

In between solving this symmetric group case and finding an elementary solution for the general case, Forte Shinko brought to my attention the following theorem:

Theorem (Dénes–Hermann 1982). $w(G)$ is a coset of $G'$.

For such a short theorem statement, it is a remarkably strong fact. $w(G)$ is the entire coset, which means that if you take $A = G$—that is, every element of $G$ taken exactly once—in our sampling problem, it will make a flexible set. A more detailed version of this result actually characterizes which coset this is, and in most cases that coset is just $G'$ itself, with only a small list of specific conditions resulting in the alternative, but for our purposes that is irrelevant.

Dénes–Hermann has a mightily complicated proof for its concise conclusion. The first completed proof relied on the Feit–Thompson theorem—odd order implies solvable—of all things! Feit–Thompson was the crown jewel of group theory at the time, and the Classification of Finite Simple Groups was a year away from being announced (and over two decades away from being correctly sketched (and as of 2021 we’re still waiting for it to be published)) so it was the biggest tool in the toolbox.

Subsequent work in this area, then and still known as the problem of L. Fuchs, focused on excising the dependency on Feit–Thompson, and was to my knowledge completed in 1972, but only published twenty years later (Yff 1991) for some reason? The whole timestream is wacky around this problem: Golomb started his inquiries into Wilsonian products of $G$ in 1951, but did not conjecture [what is now known as the theorem of] Dénes–Hermann until 1970, by which time the problem was already well-known (Fuchs 1964) and solved in the case that $G$ is solvable (Rhemtulla 1969³).

Luckily there is a much more elementary argument in our case. It’s a dinky little problem but you could probably guide a student of group theory through it without trouble.