Random Permutations

Huseyin Acan, Charles Burnette, Eric Schmutz, James Thomas, and I have just uploaded our paper Permutations With Equal Orders to the arXiv.

The motivating question is one that was discussed previously on this blog: what is the probability that two random permutations ${\pi}$ and ${\pi'}$ have the same order? Equivalently, what is the “collision entropy” of the random variable ${\textup{ord}\, \pi}$ ? If ${\pi}$ and ${\pi'}$ happen to be conjugate, say if they are both ${n}$ -cycles, then of course they have the same order, which leads to the lower bound

$\displaystyle \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \geq \mathbf{P}(\pi \sim \pi') \sim \frac{\Delta}{n^2},$

where ${\Delta \approx 4.26}$ is an explicit constant determined by Flajolet, Fusy, Gourdon, Panario, and Pouyanne. It is natural to guess, based on this as well as numerical evidence, that

$\displaystyle \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \sim \frac{\Delta'}{n^2}$

for some other constant ${\Delta'}$ . This guess turns out to be wrong, but only narrowly so. We prove in our paper that

$\displaystyle \limsup \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \cdot n^2 = \infty,$

but that

$\displaystyle \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \leq n^{-2+o(1)}.$

This is certainly not a complete picture, however, and the project is ongoing. Among the things I expect to be true and hope to prove are the following:

${\liminf \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \cdot n^2}$ is finite.
${\mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \cdot n^2}$ is bounded by a very slowly growing function of ${n}$ , perhaps even ${\log^* n}$ .
The value of ${\mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \cdot n^2}$ depends sensitively on the arithmetic of ${n}$ . In particular, ${\mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \cdot n^2}$ converges along any sequence of the form ${n = m! + \text{constant}}$ .

The proof of the bound

$\displaystyle \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') = n^{-2+o(1)}$

requires a lemma that may be interesting more generally. We prove that all except ${n^{-1+\epsilon}}$ permutations ${\pi}$ have order which is divisible by ${\Omega_\epsilon(\log n)}$ primes ${p > n^{\Omega_\epsilon(1)}}$ . In particular, all except ${n^{-1+\epsilon}}$ permutations have order at least ${e^{\Omega_\epsilon(\log^2 n)}}$ . This is a sort of tail bound related to the famous result of Erdős and Turán that ${\log \textup{ord}\, \pi}$ is approximately normal with mean ${\frac12 \log^2 n}$ and variance ${\frac13 \log^3 n}$ . It might be interesting to try to pin this down more exactly: Estimate the probability that ${\textup{ord}\, \pi \leq e^{x \log^2 n}}$ for any given constant ${x>0}$ . The result should be of the form ${n^{-1 + f(x) + o(1)}}$ for some function ${f(x)}$ which tends to zero with ${x}$ .

Incidentally, in terms of arXiv mechanics, we decided to upload our paper as an update to an earlier paper of the other four authors, so this paper might not have appeared in your usual feed. The overlap of this version with the previous one is virtually empty, however, apart from having the same motivating question.

Finally, I’m happy to report that my Erdős number has now fallen to ${2}$ , presumably its final value.

Happy new year everyone.

Question: What is the largest ${h}$ such that the direct product

$\displaystyle A_n^{\times h} = A_n \times \cdots \times A_n$

of ${h}$ copies of the alternating group ${A_n}$ is ${2}$ -generated?

This is the sort of question which somebody with little experience of nonabelian groups might get very wrong: such a person might guess ${h=2}$ by analogy with linear algebra. Here’s a rough-and-ready construction that shows how wrong that logic is. Assume ${n}$ is odd, for simplicity, and write ${p_1, p_2, \dots}$ for the odd primes less than ${n}$ . Let ${\sigma \in A_n}$ be some ${n}$ -cycle, for each ${i}$ let ${\tau_i}$ be a ${p}$ -cycle, and let

$\displaystyle \begin{array}{rcl} x &=& (\sigma, \sigma, \dots),\\ y &=& (\tau_1, \tau_2, \dots). \end{array}$

Then for each ${i}$ there is some ${k_i > 0}$ such that

$\displaystyle y^{k_i} = (e, \dots, e, \tau_i, e, \dots).$

Clearly then ${\langle x, y^{k_i}\rangle}$ is a subgroup of

$\displaystyle \langle \sigma\rangle \times \cdots \times \langle \sigma\rangle \times A_n \times \langle \sigma \rangle \times \cdots,$

surjecting onto the ${A_n}$ factor. Since ${A_n}$ is perfect (meaning ${[A_n, A_n] = A_n}$ ) we can now use commutators to isolate the ${A_n}$ factor, and generation is proved. This shows that the answer to our initial question is at least ${\pi(n-1)}$ .

In fact this construction is horribly inefficient, and it is possible to give a surprisingly exact answer. Though it is news to me in 2018, it was observed by Philip Hall in 1936.

Theorem 1 Let ${G}$ be a finite group, let ${h_d(G)}$ be the largest ${h}$ such that ${G^h}$ is ${d}$ -generated, and let ${\phi_d(G)}$ be the number of ${d}$ -tuples ${(g_1, \dots, g_d)\in G^d}$ such that ${\langle g_1, \dots, g_d\rangle = G}$ . If ${G}$ is nonabelian simple then

$\displaystyle h_d(G) = \frac{\phi_d(G)}{|\textup{Aut}\, G|}.$

The notation ${\phi_d(G)}$ is Hall’s, motivated by the connection with Euler’s phi function ${\varphi(n)}$ from number theory:

$\displaystyle \varphi(n) = \phi_1(C_n).$

For this reason, ${\phi_d}$ is occasionally referred to as the Euler–Hall function of ${G}$ . Like ${\varphi(n)}$ , ${\phi_d(G)}$ has summatory rule:

$\displaystyle |G|^d = \sum_{H\leq G} \phi_d(H).$

This can be used to calculate ${\phi_d(G)}$ for any group ${G}$ whose subgroup lattice is well understood.

On the other hand, a probablistic group theorist like me is more likely to think

$\displaystyle \phi_d(G) / |G|^d = \mathbf{P}(\langle g_1, \dots, g_d\rangle = G),$

expecting this to be close to ${1}$ whenever ${d>1}$ . This is the case for ${A_n}$ , for example. Since ${\textup{Aut}\, A_n \cong S_n}$ for ${n>6}$ , we have our answer to our initial question:

$\displaystyle h_2(A_n) \sim \frac{|A_n|^2}{|S_n|} = \frac14 n!.$

Compared to our earlier lower bound of ${\pi(n-1)}$ , this is monstrous!

The proof of Theorem 1 is not hard, but it requires a little mental gymnastics. Write ${\Phi_d(G)}$ for the set of generating ${d}$ -tuples, so that ${\phi_d(G) = |\Phi_d(G)|}$ . There is an obvious action of ${\textup{Aut}\, G}$ on ${\Phi_d(G)}$ , and a moment’s thought reveals that this action is fixed-point-free (if an automorphism fixes a set of generators then clearly it fixes everything). On the other hand we can think of ${\Phi_d(G)}$ as the set of surjections ${F_d \to G}$ from the free group ${F_d}$ to ${G}$ . In this view, the action of ${\textup{Aut}\, G}$ is that of post-composition.

Lemma 2 Let ${F}$ and ${G}$ be groups, and let ${f_1, f_2: F \to G}$ be surjections. Then the following are equivalent:

There is an automorphism ${\alpha \in \textup{Aut}\, G}$ such that ${f_1 = \alpha f_2}$ .
${\ker f_1 = \ker f_2}$ .

Proof: Obviously 1 implies 2. If 2 holds then ${f_1, f_2}$ descend to isomorphisms ${F/K \to G}$ , where ${K}$ is the common kernel, and ${\alpha}$ is readily obtained. $\Box$

Thus the orbits of ${\textup{Aut}\, G}$ on ${\Phi_d(G)}$ are in bijection with the subgroups ${K \leq F_d}$ such that ${F_d / K \cong G}$ . Therefore the number of such subgroups is precisely ${\phi_d(G) / |\textup{Aut}\, G|}$ .

Let ${\mathcal{K}}$ be the set of all such subgroups ${K}$ . Clearly we have an injection

$\displaystyle F_d / \bigcap\mathcal{K} \to \prod_{K \in \mathcal{K}} F_d/K \cong G^{|\mathcal{K}|}.$

If ${f:F_d \to G^h}$ is a surjection, then ${\ker f}$ contains ${\bigcap \mathcal{K}}$ , so ${f}$ factors through ${F_d / \bigcap\mathcal{K}}$ , so ${h \leq |\mathcal{K}|}$ . The proof is therefore concluded by the following lemma.

Lemma 3 Assume ${G}$ is nonabelian simple. Then the map

$\displaystyle F / \bigcap \mathcal{K} \to \prod_{K\in \mathcal{K}} F/K$

is surjective.

Proof: Write ${\mathcal{K} = \{K_1, K_2, \dots\}}$ . We will prove by induction on ${m}$ that

$\displaystyle F / (K_1 \cap \cdots \cap K_m) \to F / K_1 \times \cdots \times F/K_m$

is surjective. The case ${m=1}$ is trivial. The case ${m=2}$ follows easily from Goursat’s lemma. For ${m>2}$ , we know by induction that for all

$\displaystyle g_3, g_4, \dots, g'_3, g'_4, \dots \in G$

the image in ${F/K_1 \times \cdots F/K_m}$ contains points of the form

$\displaystyle (1, ?, g_3, g_4, \dots),\quad (?, 1, h_3, h_4, \dots).$

Taking commutators and using ${[G,G]=G}$ , we see that the image contains the subgroup ${1^2 \times G^{m-2}}$ . Similarly, the image contains ${G^{m-2} \times 1^2}$ . Therefore the image is ${G^m}$ . $\Box$

Let’s close with a simple puzzle. In Theorem 1 we assumed that ${G}$ is simple. What about, say, ${S_n}$ ? Prove that ${h_2(S_n) = 2}$ .

Later edit: It seems that Kantor and Lubotzky found an easier way of thinking about this, or at least an equivalent way that involes less mental gymnastics. (See KL, Proposition 6.)

Theorem 4 (Kantor–Lubotzky) Let ${T}$ be a nonabelian simple group, and let ${s_1, \dots, s_d \in T^k}$ be candidate generators of ${G = T^k}$ . Write ${s_i = (t_{i1}, \dots, t_{ik})}$ for each ${i}$ , and consider the matrix ${d \times k}$ matrix

$\displaystyle \left(\begin{array}{ccc} t_{11} & \cdots & t_{1k} \\ \vdots & \ddots & \vdots \\ t_{d1} & \cdots & t_{dk}. \end{array}\right)$

Then ${s_1, \dots, s_d}$ generate ${G}$ if and only if

${\langle t_{1j}, \dots, t_{dj}\rangle = T}$ for each ${j}$ , and
${(t_{1j}, \dots, t_{dj})}$ are in different ${\textup{Aut}\, T}$ -orbits for each ${j}$ .

The conditions are clearly necessary: 1 is necessary lest the projection ${\pi_j}$ of ${\langle s_1, \dots, s_d\rangle}$ onto the ${j}$ th factor not be surjective, and 2 is necessary lest ${\langle s_1, \dots, s_d\rangle}$ be trapped in the subgroup of ${T^k}$ defined by ${\pi_j = \alpha \pi_{j'}}$ for some ${j,j'}$ and some ${\alpha \in \textup{Aut}\, T}$ .

The proof of sufficiency is much like that of Lemma 3 above. Use induction on ${k}$ , using Goursat’s lemma for the case ${k=2}$ .

Armed with Theorem 4, Theorem 1 is quite obvious.

There is also a nice variant for invariable generation. Cheers to Daniele Garzoni for pointing this out to me. Recall that elements ${g_1, \dots, g_d}$ of a group ${G}$ are said to invariably generate if ${g_1', \dots, g'_d}$ generate whenever ${g_i'}$ is conjugate to ${g_i}$ for each ${i}$ . (So invariable generation is really better thought of as a property of conjugacy classes rather than elements.) Then, with the setup as in Theorem 4, ${s_1, \dots, s_d}$ invariably generate ${G}$ if and only if

${t_{1j}, \dots, t_{dj}}$ invariably generate ${T}$ for each ${j}$ , and
${(t_{1j}^G, \dots, t_{dj}^G)}$ are in different ${\textup{Aut}\, T}$ -orbits for each ${j}$ .

Note that ${\textup{Aut}\, T}$ really does act on the set of conjugacy classes, so point 2 makes sense. It follows that the largest ${h}$ such that ${T^h}$ is invariably ${d}$ -generated is equal to the number of ${\textup{Aut}\, T}$ -orbits of ${d}$ -tuples of invariably generating conjugacy classes. But sadly this doesn’t lead to as nice a formula as in Theorem 1, because this action is not fixed-point-free (it is possible for an automorphism to preserve the conjugacy class of each generator without preserving all conjugacy classes).

Random Permutations

Permutations with equal orders

Generating direct powers of a simple group