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