Permutations contained in transitive subgroups

Permutations contained in transitive subgroups, Discrete Analysis 2016:12, 36 pp.

This paper is part of a series. The previous paper in the series [2] concerned the following question. A property of elements \(x_1,\dots,x_t\) of a group \(G\) is said to hold invariably if it holds even if \(x_1,\dots,x_t\) are replaced by arbitrary conjugates. How many random permutations in \(S_n\) are needed for the probability that they invariably generate \(S_n\) to be bounded away from zero? It was known that four elements suffice [3], and the main result of [2] was that three elements did not suffice. This was achieved with the help of an estimate for the probability that a random permutation contains a fixed set (that is, a set that maps to itself) of given size \(k\), obtained in the first paper of the series [1]. Of course, a fixed set of size \(k\) exists if and only if the cycle decomposition of the permutation contains cycles of lengths that add up to \(k\).

The relevance of the sizes of fixed sets is that if permutations \(\pi_1,\dots,\pi_t\) all have fixed sets of size \(k\), then we can find conjugates that have the same fixed set of size \(k\), and these conjugates clearly do not generate \(S_n\). The estimate obtained for the probability that a random permutation has a fixed set of size \(k\) is \(k^{-\delta}(1+\log k)^{-3/2}\), up to a constant, where \(\delta=1-(1+\log\log 2)/\log 2\). This estimate holds for all \(k\) (with the same constant) up to \(n/2\).

Another consequence of the estimate in [1] is that when \(n\) is even, the probability that a random permutation in \(S_n\) is contained in a transitive subgroup of \(S_n\) other than \(S_n\) or \(A_n\) is at least \(cn^{-\delta}(\log n)^{-3/2}\). That is because with at least that probability there is a fixed set of size \(n/2\), so we can take the group of permutations that preserve the partition of \(\{1,2,\dots,n\}\) into that set and its complement. The conjectures are made in that paper that there should be a matching upper bound, and a stronger upper bound when \(n\) is odd. The current paper proves both these conjectures. The behaviour turns out to depend critically on the smallest prime factor \(p\) of \(n\), with a change in behaviour as soon as \(p\geq 5\).

In order to prove these results, the authors obtain estimates for the probability that a random permutation \(\pi\in S_n\) has disjoint fixed sets of sizes \(k_1,\dots,k_m\) for given \(k_1,\dots,k_m\) that add up to \(n\).

Results of this kind have many applications, and this paper makes a significant contribution to our understanding of the subgroup structure of the symmetric group.

[1] S. Eberhard, K. Ford and B. J. Green, Permutations fixing a \(k\)-set, arxiv:1507.04465

[2] S. Eberhard, K. Ford and B. J. Green, Invariable generation of the symmetric group, arxiv:1508.01870

[3] R. Pemantle, Y. Peres and I. Rivin, Four random permutations conjugated by an adversary generate \(S_n\) with high probability, arxiv:1412.3781