# Probability of $\alpha\beta\gamma=\gamma\beta\alpha$ for random permutations of a finite set?

Following up on my previous question Probability that two random permutations of an $n$-set commute?, here's a related question for three elements.

Q: If $\alpha,\beta,\gamma$ are chosen uniformly at random from the symmetric group on $n$ elements, what is the probability that $\alpha\beta\gamma=\gamma\beta\alpha$?

For $n \leq 6$ we have the striking property $$\mathrm{Pr}[\alpha\beta=\beta\alpha]=\mathrm{Pr}[\alpha\beta\gamma=\gamma\beta\alpha].$$

as illustrated in the following table:

\begin{array}{r|rr} n & \mathrm{Pr}[\alpha\beta\gamma=\gamma\beta\alpha] & \mathrm{Pr}[\alpha\beta=\beta\alpha] \\ \hline 1 & 1 & 1 \\ 2 & 1 & 1 \\ 3 & 108\ /\ 3!^3 = 0.5 & 18\ /\ 3!^2 = 0.5\\ 4 & 2880\ /\ 4!^3 \simeq 0.208 & 120\ /\ 4!^2 \simeq 0.208 \\ 5 & 100800\ /\ 5!^3 \simeq 0.058 & 840\ /\ 5!^2 \simeq 0.058 \\ 6 & 5702400\ /\ 6!^3 \simeq 0.015 & 7920\ /\ 6!^2 \simeq 0.015 \\ \end{array}

computed using GAP. Does this hold in general?

• The tools used in the previous question (e.g. the centralizer subgroup) do not seem to be usable here. (Although, maybe I'm missing something important.)

• This doesn't seem to generalize: e.g. in $S_3$, we have $\mathrm{Pr}[\alpha\beta\gamma\delta=\delta\gamma\beta\alpha] \simeq 0.103$ which doesn't match.

• None of the permutations $(13),(23),(12) \in S_3$ commute, but $(13)(23)(12)=(23)=(12)(23)(13)$.

Theorem. For any finite group $G$, we have $P(\alpha\beta=\beta\alpha)=P(\alpha\beta\gamma=\gamma\beta\alpha)$.

Proof. We know already that $P(\alpha\beta=\beta\alpha)=k/|G|$ (readers: see previously linked question), and we will derive the same formula for $P(\alpha\beta\gamma=\gamma\beta\alpha)$. First, writing $x=\alpha\beta$ and $y=\beta\alpha$, count

$$\frac{1}{|G|^3}\sum_{(x,y)\in G^2}\color{Blue}{\#\{(\alpha,\beta)\in G^2:\begin{smallmatrix}\alpha\beta=x \\ \beta\alpha=y\end{smallmatrix}\}}\times\color{Red}{\#\{\gamma\in G:x\gamma=\gamma y\}}.$$

Rearrange $\alpha\beta=x$ to $\beta=\alpha^{-1}x$ and plug into $\beta\alpha=y$ for $\alpha^{-1}x\alpha=y$. Thus the blue count is $0$ if the elements $x\not\sim y$, and is $|C_G(x)|$ if $x\sim y$: in any $G$-set, if two elements are in the same orbit, the number of elements which move the first to the second is the size of the first's stabilizer. For the red count, rewrite $x\gamma=\gamma y$ as $x=\gamma y\gamma^{-1}$. By the same principle, this is $|C_G(y)|$ if $x\sim y$ and $0$ if they are not conjugate. We know $|C_G(x)|=|G|/|K|$ where $K$ is $x$'s conjugacy class. Let the classes be listed as $K_1,K_2,\cdots,K_k$. Then we have

$$\frac{1}{|G|^3}\sum_{i=1}^k\sum_{\color{Purple}{x,y\in K_{\Large i}}}\color{Green}{|C_G(x)||C_G(y)|}=\frac{1}{|G|^3}\sum_{i=1}^k \color{Purple}{|K_i|^2}\color{Green}{\left(\frac{|G|}{|K_i|}\right)^2}=\frac{k}{|G|}.$$

• Remarkable! Thanks for that. (And you seem to have taken substantially less time answering the question than I took writing it!) – Rebecca J. Stones Jul 2 '14 at 8:25
• @Rebecca No problem. It was fun. – blue Jul 2 '14 at 8:30

Commutativity can be compared to a torus. The product of all elements around the perimeter is the identity. $ab=ba$ can be re-written $aba^{-1}b^{-1}=1$. Notice $abca^{-1}b^{-1}c^{-1}$ also defines the boundary of a torus. I always get confused about the second one. It's because you can tile the plane with hexagons. Then you can define a sum $\sum_{a,b \in G} \delta(aba^{-1}b^{-1})$ or $\sum_{a,b,c \in G} \delta(abca^{-1}b^{-1}c^{-1})$ to count the combinations of group elements solving your equation.

We will get the same answer in both cases: the number of conjugacy classes of $G$. If you put four hexagons together maybe you can get a commuting pair. I have written down:

$$[cbcb,a]=1 \text{ if } abc=cba$$

Is this a bijection? Can we take a square torus and construct the hexagon torus?

We can because the fundamental parallelogram and the boundary of the 4 hexagons are homotopic. This is in Chapter 2 of Algebraic Topology by Allen Hatcher.

Observe we can right-multiply the equation by $$\beta$$ and then substitute:

$$P(\alpha\beta\gamma=\gamma\beta\alpha) ~~~=~~~ P\big((\alpha\beta)(\gamma\beta)=(\gamma\beta)(\alpha\beta)\big) ~~~=~~~ P(\varepsilon\zeta=\zeta\varepsilon)$$

since $$(\varepsilon,\zeta)=(\alpha\beta,\gamma\beta)\in G^2$$ is uniformly distributed if $$(\alpha,\beta,\gamma)\in G^3$$ is.