The symmetric group, 11

I am going to talk about a celebrated theorem of John Dixon and some of its variants; this is on my mind at the moment, for reasons I will explain at the end.

Dixon’s theorem is easily stated.

Two random elements of the symmetric group S_n generate S_n or A_n with probability tending to 1 as n→∞.

This was conjectured by Netto in 1882; the proof did not come until 1969. Note that, if both the random permutations are even (this holds with probability 1/4), the group they generate will be contained in the alternating group (and so equal to it with high probability).

Before sketching the proof I will make some comments.

First off, lots is known about a single random permutation: its cycle structure, order, and so on, are worked out in a series of papers on “statistical group theory” by Erdős and Turán in the 1950s. What sort of questions should we ask about a random pair of permutations? To most group theorists, the group they generate would seem the obvious first thing to look at.

In general, suppose that G is a group and H a subgroup of G; assume that H is equal to its normaliser. Then a simple argument shows that the average number of conjugates of H in which a random element g of G lies is 1. Although this does not immediately tell us the probability that g lies in some conjugate, it suggests that it should be fairly high. If H has index n in G, then the average number of conjugates of H containing a random pair of elements of G is only 1/n, so the probability that both elements are contained in a random conjugate is likely to be considerably smaller (and in any case not more than 1/n, by Markov’s inequality). Now since two elements generate G if and only if no maximal proper subgroup contains both, the overall strategy of the proof is now clear. We also see that maximal subgroups of small index will need more care than those of large index.

The proof breaks into two parts. First we calculate the probability that the two random permutations generate a transitive subgroup of S_n. This can be done precisely, as Dixon did. For they generate a transitive subgroup if and only if there is no proper subset of {1,…,n} fixed by both; this can be computed by inclusion-exclusion, and the probability turns out to be approximately 1−1/n.

There is a curious puzzle here. Call a permutation g of {1,…,n} connected if there is no number k, with 0<k<n, such that g maps the set {1,….,k} into itself. The number of of connected permutations provides an interesting and well-known sequence (number A003319 in Sloane’s list). For example, the power series Sum n!xⁿ is divergent for all non-zero x; but, of course, it has an inverse (as a formal power series). The coefficient of xⁿ in the inverse is the number of connected permutations (with the sign changed).

The number of pairs of elements which generate a transitive subgroup of S_n turns out to be the product of (n−1)! and the number of connected permutations of {1,…,n+1}. This fact is quite surprising, since the definition of connected permutation depends on an ordering of the domain, while the other terms in the equation do not. Is there a bijective proof?

The second, and more difficult, part is to estimate the probability that two random permutations generate a transitive subgroup which is not the symmetric or alternating group. According to our outline above, we need to know that there are not too many conjugacy classes of maximal transitive subgroups, and that these sugroups have large index.

This is a terrain in which the landscape has been enormously changed by the Classification of Finite Simple Groups (I plan to discuss this in the next post in this sequence). Using information available at the time, Dixon was able to show that the required probability is at most 2/(log log n)². Newer results enabled Babai in 1989 to reduce this to O(1/n²), showing that the probability that two random elements fail to generate the symmetric or alternating group is (1+o(1))/n. It is possible to be considerably more accurate if desired: a paper by John Dixon in the Electronic Journal of Combinatorics in 2005 gives the first six terms in the asymptotic expansion.

There are several variants of Dixon’s theorem.

The symmetric group is almost simple; the analysis has been extended to other almost simple groups, and especially to simple groups. Strengthenings have also been found. For example, we can specify that the generators have orders 2 and 3; or we can fix the first generator to be any non-identity element, and then find that almost all choices of a second generator give the symmetric or alternating groups. These results have also been extended to other simple groups. There is a lot to be said here, but it is a bit off-topic, so I will pass on.

I conjectured that, with probability tending to 1, a random element of the symmetric group S_n is contained in no transitive subgroup except S_n and possibly A_n. This conjecture was proved by Łuczak and Pyber; the proof is not straightforward, and the best possible error estimates have not been determined.

This is harder than Dixon’s Theorem because we only have one random permutation rather than two; what makes it work is that we only have to deal with transitive subgroups, whereas it is the intransitive subgroups which are the largest.

The result was proved for an application to the multiplication group of a Latin square, the group generated by the rows and columns regarded as permutations (which is the symmetric group with high probability). The motivation is that a quasigroup (a structure whose Cayley table is a Latin square) has non-trivial character theory if and only if its multiplication group is not 2-transitive – this is a special and rare event. Yet it happens for all groups of order greater than 2. Groups are indeed special!

What about extensions to the infinite? Let us not be too ambitious, and begin with the countably infinite. Now the symmetric group on a countably infinite set is uncountable, and so cannot be generated by two elements; the finitary symmetric group is locally finite, and so for a different reason cannot be generated by two elements. Also, there is no natural measure on the symmetric group. So an analogue of Dixon’s theorem seems unlikely. Yet it exists, and it was Dixon himself who discovered it in 1990.

Although there is no natural measure on the symmetric group, there is a natural topology. Suppose that the points on which the group acts are the natural numbers. Define the distance between two distinct permutations g and h to be 1/2^k, where k is the smallest natural number i such that either the images of i under g and h differ, or the images of i under g^-1 and h^-1 differ. This definition of distance makes the symmetric group into a complete metric space. (If we omitted the clause involving the inverses, we would define a metric, but it would not be complete.)

In an earlier posting, I described how the notion of Baire category in a complete metric space could be used, in a similar way to the notion of measure in a measure space, to make precise the notion of “almost all”. A set is residual if it contains a countable intersection of open dense sets. Residual sets resemble sets of full measure in various ways; they are necessarily non-empty (the Baire category theorem) and they are closed under countable intersections; moreover, they have non-empty intersection with any non-empty open set.

A permutation group on an infinite set is said to be highly transitive if it is n-tranitive (that is, can map any n-tuple of distinct points to any other) for all natural numbers n. It is not hard to see that a permutation group is highly transitive if and only if its closure is the symmetric group. Now Dixon showed in 1990:

For a residual set of pairs (g,h) of elements of the symmetric group on a countable set, the group generated by g and h is free and highly transitive.

So all we have to do is change measure to Baire category, change “subgroup generated” to “closed subgroup generated”, and the theorem holds!

This resolves in a very strong way the question of the existence of 2-generator free highly transitive groups, first proved by Tom McDonough in 1977.

For a last analogy I turn from groups to monoids, or (what is almost the same thing) automata. Let T_n denote the full transformation monoid on the set {1,…,n} (the set of all functions from this set to itself, with the operation of composition). A submonoid of Tn is called synchronizing if it contains a function of rank 1 (one whose image has cardinality 1).

After a talk I gave on synchronization, Brendan McKay asked me about the probability that r random elements of T_n generate a synchronizing monoid. As I reported here, I was able to show, using Joyal’s proof of Cayley’s Theorem on trees, that for k = 1, the probability is 1/n (the same as the probability that a single random permutation generates a transitive group, as it happens: is this significant?)

The analogue of Dixon’s theorem would be this statement: The probability that two random transformations generate a synchronizing monoid tends to 1 as n→∞. I have not succeeded in proving this; but I think that an approach resembling Dixon’s might be feasible.

For example, it is not hard to see that T₃ contains exactly 7 maximal non-synchronizing monoids, each of order 6 (one of them is the symmetric group S₃); the sizes of their intersections can be computed, and so using inclusion-exclusion, an exact formula for the probability that k random elements generate a synchronizing monoid can be calculated. Its leading term is 1-7(2/9)^k.

Previous | Next