12
$\begingroup$

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?

Comments:

  • 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)$.

$\endgroup$
20
+100
$\begingroup$

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|}.$$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.