# Algorithm to generate random commuting permutations

I am seeking to understand the properties of a typical pair of permutations $(\sigma,\tau) \in \mathrm{Sym}(n)^2$ chosen uniformly at random from all pairs such that $\sigma$ and $\tau$ commute. In particular, I would like to prove that the following holds.

$(\ast)$ With high probability, the graph on $\{1,\ldots,n\}$ induced by $\sigma$ and $\tau$ has few 'unnecessary' short cycles (i.e. short cycles which do not correspond to commutators).

It seems that the best way to do this would be to have a straightforward algorithm to generate such a random pair. I have been unable to find such an algorithm in the literature and I would appreciate if someone could tell me what is known about this subject.

I would be equally happy to have a way of establishing $(\ast)$ for a random pair of approximately commuting permutations. To make the last statement precise, for each $\epsilon > 0$ I would like to know that if $n$ is large enough then $(\ast)$ holds for a pair chosen uniformly at random from of the set of all pairs $(\sigma,\tau) \in \mathrm{Sym}(n)^2$ such that $\sigma \tau \sigma^{-1} \tau^{-1}$ has at least $(1-\epsilon)n$ fixed points.

• If $n$ is not too large, you could just use one of the fast algorithms to generate random permutations described here, and then keep only pairs of permutations that commute; these become rare as $\exp(\sqrt{n}-n\ln n)$ when $n$ is large, so then a direct approach to find them would be needed; it seems like something a Monte Carlo algorithm might be able to achieve... – Carlo Beenakker Feb 5 '17 at 8:10
• If I didn't make a mistake, the total number of ordered pairs of commuting permutations on $n$ letters is $p(n)n!$, where $p(n)$ is the number of partitions of $n$. If you could turn this identity into a combinatorial bijection somehow, then you just need to sample an ordered pair of a permutation and a partition and then apply the hypothetical bijection. – zeb Feb 5 '17 at 10:05

Here's a method for sampling two commuting elements of a group $G$, given that you can sample a random element of $G$ and that you can also sample a random conjugacy class of $G$ (and assuming as well that for any two elements $a,x \in G$ which are in the same conjugacy class, you can efficiently compute some $z \in G$ with $zxz^{-1} = a$). It's based on Theorem IV of the paper "On some problems of a statistical group-theory. IV" by Erdős and Turán.

Step 1: Let $C$ be a uniformly random conjugacy class of $G$, and let $x$ be an arbitrary element of $C$.

Step 2: Let $y$ be a uniformly random element of $G$.

Step 3: Let $a = yxy^{-1}$.

Step 4: Compute an element $z \in G$ such that $zxz^{-1} = a$, such that $z$ depends only on $a$ and $x$.

Step 5: Let $b = yz^{-1}$.

Then $ab = ba$ and $(a,b)$ is uniformly distributed among ordered pairs of commuting elements of $G$.