Partitions and permutations

Peter J. Cameron School of Mathematical Sciences Queen Mary and Westfield College London E1 4NS U.K.

                p.j.cameron@qmw.ac.uk

Abstract

With any permutation g of a set Ω is associated a partition of Ω into the cycles of g. What information do we get about a group G of permutations if we know either the set or the multiset of partitions of Ω, or of partitions of n = |Ω|, which arise as the cycle partitions of its elements? Some partial answers to these questions are given.

1 Introduction

Let Ω be a finite set of cardinality n. To any permutation g of Ω, we associate the partition CP(g) of Ω into cycles of g, and the partition cp(g) of the integer n given by the cycle lengths.

Now let G be a group of permutations of Ω (a subgroup of the symmetric group on Ω). We are interested in the question: What information about G is contained in the set or multiset of cycle partitions corresponding to its elements? We can distinguish eight questions:

(a) We can ask for a characterisation of the sets or multisets of partitions arising from groups, or we can ask to what extent knowledge of the set or multiset determines the group.

(b) We can consider set partitions CP(G) = {CP(g) : g ∈ G}, or number partitions cp(G) = {cp(g) : g ∈ G}.

(c) We can consider CP(G) or cp(G) as sets, or as multisets. (In the latter case, for each partition π of Ω or n, we know the number of permutations g ∈ G for which CP(g) or cp(g) is equal to π.)

The recognition problem is complicated by the fact that, while permutation groups can be represented efficiently (a subgroup of S_{n} can be generated by O(n) elements, and hence is specified by O(n^{2} log n) bits), no such short representation of sets of partitions is available. P. Kolaitis [13] has suggested the polynomial delay model as a way round this problem:

Problem 1.1 (a) Is there an algorithm which takes as input a subset X of P_{n}, performs a polynomial-time computation after reading each partition in X, and decides whether X = CP(G) for some subgroup G of S_{n}?

(b) Is there a polynomial-length ‘certificate’ S for X (for example, a generating set for G) with the property that, given X, on performing a polynomial-time computation after reading each partition in X, we can confirm that X = CP(G)?

Certainly an affirmative solution to (a) would settle (b) also; these questions are analogous to the definitions of the classes P and NP respectively. Note that a small generating set for the group generated by an arbitrary set of permutations can be computed wth polynomial delay: see Jerrum [12].

For the remainder of the paper, I will concentrate on the question of the extent to which cycle partitions determine the group. These will be considered for set partitions and for number partitions in the next two sections. Then there is a brief survey of the Parker vector of a permutation group, whose kth component is the number of orbits of the group on the set of its k-cycles. The last two sections discuss infinite versions of the results and some possible further directions.

2 Set partitions

In this section, we consider the question: What information about G do we obtain from CP(G)? In particular, if CP(G_{1}) = CP(G_{2}), must G_{1} and G_{2} be isomorphic, or even equal? The answers to the strongest conjectures are negative, as the following examples show. The first example is due to Alberto Leporati [14], who suggested this question to me; the third is due to Eamonn O’Brien [15].

Example 2.1 Let n = 5, and let G_{1} be the cyclic group of order 5, acting regularly. Then CP(G_{1}) consists of the trivial partitions of Ω (into a single part, and into parts of size 1). If CP(G_{1}) = CP(G_{2}), then clearly G_{2} is also a cyclic group of order 5, but it could be any of the six such subgroups of S_{5}. Note, however, that these subgroups are all conjugate in S_{5}, so G_{1} and G_{2} are isomorphic as permutation groups.

Example 2.2 Let G be the group C_{7} × C_{7} of order 49. We embed G in the symmetric group of degree 28 by choosing four subgroups of order 7, say P_{1}, …, P_{4}, and taking the union of the regular actions of G/P_{i} for i = 1, …, 4. It is easy to see that the automorphism group GL(2, 7) of G does not act transitively on the collection of 4-sets of proper subgroups of G; choosing the set of four subgroups from different orbits gives rise to permutation groups which are not isomorphic. However, CP(G) consists of the partition with 28 parts of size 1, the four partitions with seven parts of size 1 (in one orbit) and three of size 7 (each with multiplicity 6), and the partition into the four orbits (with multiplicity 24), in either case. So CP(G) (even as multiset) does not determine G up to permutation isomorphism.

Example 2.3 Eamonn O’Brien [15] found two pairs of examples of groups G_{1}, G_{2} with CP(G_{1}) = CP(G_{2}) for which G_{1} and G_{2} are not isomorphic as abstract groups. The pairs are numbers 19 and 111, and numbers 94 and 249, in the lists of groups of order 64 contained in the computer systems GAP and MAGMA (see [6] and [2]), acting in faithful permutation representations of least possible degree 16.

For example, the first two groups are generated by the permutations

(1, 11, 3, 10, 2, 12, 4, 9)(5, 16, 8, 14, 6, 15, 7, 13),
(1, 8, 4, 6, 2, 7, 3, 5)(9, 13, 11, 15, 10, 14, 12, 16),
(1, 3, 2, 4)(5, 7, 6, 8)(9, 11, 10, 12)(13, 15, 14, 16),
(1, 3, 2, 4)(5, 8, 6, 7)(9, 11, 10, 12)(13, 16, 14, 15),
(1, 4, 2, 3)(5, 8, 6, 7)(9, 11, 10, 12)(13, 15, 14, 16),
(1, 2)(3, 4)(5, 6)(7, 8)(9, 10)(11, 12)(13, 14)(15, 16)

and

(1, 12, 4, 10, 2, 11, 3, 9)(5, 16, 8, 14, 6, 15, 7, 13),
(1, 7, 3, 6, 2, 8, 4, 5)(9, 14, 12, 15, 10, 13, 11, 16),
(5, 6)(7, 8)(13, 14)(15, 16),
(1, 3, 2, 4)(5, 7, 6, 8)(9, 12, 10, 11)(13, 16, 14, 15),
(1, 4, 2, 3)(5, 8, 6, 7)(9, 12, 10, 11)(13, 16, 14, 15),
(1, 2)(3, 4)(5, 6)(7, 8)(9, 10)(11, 12)(13, 14)(15, 16)

respectively; and CP(G_{1}) and CP(G_{2}) consist of the same set of twelve partitions of {1, …, 16} (with the same multiplicities).

So CP(G) does not determine G up to isomorphism, even if G is transitive.

However, the set CP(G) does determine a lot of information about G, as the next results show. We define OP(G) to be the set of all partitions of Ω which are orbit partitions corresponding to subgroups of G. Thus, CP(G) is a subset of OP(G).

Theorem 2.1 Let G_{1} and G_{2} be permutation groups on Ω satisfying CP(G_{1}) = CP(G_{2}). Then

(a) |G_{1}| = |G_{2}|;

(b) OP(G_{1}) = OP(G_{2});

(c) CP(G) and CP(G_{2}) are identical as multisets; that is,

|{g ∈ G_{1} : CP(g) = π}| = |{g ∈ G_{2} : CP(g) = π}|

for all partitions π of Ω.

Proof (a) The proof is by induction on the degree n = |Ω|. Note that CP(G) determines the orbit αG for α ∈ Ω, since

αG = {β ∈ Ω : (∃π ∈ CP(G))(α and β are in the same part of π)}.

Also, if G_{α} is the stabiliser of α in G, then CP(G) determines

CP(G_{α}) = {π ∈ CP(G) : {α} is a part of π}.

By induction, CP(G_{α}) determines |G_{α}|. Since

|αG| · |G_{α}| = |G|

by Lagrange’s Theorem, the result is proved.

We have incidentally shown that, if CP(G_{1}) = CP(G_{2}), then G_{1} and G_{2} have the same orbits on Ω.

(b) It is clear that the orbit partition of a subgroup H is the supremum (in the lattice of partitions of Ω) of the set of cycle partitions of the elements of H (or, indeed, of a generating set for H).

(c) Let π be any partition of Ω, and let G_{1}(π) be the subgroup of G_{1} consisting of all permutations fixing all the parts of π (the intersection of G with the corresponding Young subgroup of the symmetric group: see Fulton [5]). Now CP(G_{1}(π)) consists of those partitions in CP(G_{1}) lying below π in the partition lattice. Hence, if G_{2}(π) is analogously defined in G_{2}, we have CP(G_{1}(π)) = CP(G_{2}(π)), and hence |G_{1}(π)| = |G_{2}(π)|, by part (a) of the theorem.

Now the conclusion follows by Möbius inversion, since an element g ∈ G_{1} satisfies CP(g) = π if and only if g ∈ G_{1}(π) but g ∉ G_{1}(σ) for any σ strictly below π in the partition lattice.

The last part of the theorem shows that, in this case, the set and the multiset of cycle partitions carry exactly the same information. From the first part, we deduce:

Corollary 2.2 If H is a subgroup of G satisfying either CP(G) = CP(H) or OP(H) = OP(G), then G = H.

Proof The conclusion is immediate from the theorem if CP(G) = CP(H). A very similar argument shows that, if OP(G_{1}) = OP(G_{2}), then |G_{1}| = |G_{2}|, and again it follows that if H ≤ G satisfies OP(H) = OP(G), then H = G.

See [1] for an application of these results to the power of database query languages.

Two problems which are left open between the conclusions of the theorem and the preceding examples are the following:

Problem 2.1 If CP(G_{1}) = CP(G_{2}) and G_{1} is primitive, or if G_{1} is regular, are G_{1} and G_{2} isomorphic as permutation groups?

Note that, if G_{1} is regular and CP(G_{1}) = CP(G_{2}), then G_{2} is regular, and the subgroup lattices of G_{1} and G_{2} are isomorphic.

In some special cases, more can be said. Let us say that a group G_{1} is cycle-determined if CP(G_{1}) = CP(G_{2}) implies G_{1} = G_{2}.

Proposition 2.3 (a) A group of order 2 is cycle-determined.

(b) A regular non-cyclic elementary abelian group is cycle-determined.

Proof (a) An involution is determined by its cycle partition.

(b) The parts of the partitions in CP(G), for such a group G, are the lines of an affine space over GF(p), and G is the translation group of this space.

In fact, if CP(G_{1}) = CP(G_{2}), then every involution in G_{1} is also in G_{2}, and vice versa; in particular, a group generated by involutions is cycle-determined.

More generally, we say that H is 1-closed in G if any permutation in G preserving the H-orbits lies in H. Now, if H ≤ G_{1} and H is 1-closed in G_{1}, then the number of permutations preserving the orbit partition of H is the same in G_{2} as in G_{1}, and so H ≤ G_{2}. Hence we have:

Proposition 2.4 If G is generated by subgroups which are cycle-determined and 1-closed in G, then G is cycle-determined.

3 Number partitions; cycle index

The information contained in the multiset cp(G) is precisely the (Pólya) cycle index of G, the polynomial in indeterminates s_{1}, …, s_{n} given by

Z(G) = \frac{1}{|G|} ∑_{g∈G} ∏_{i=1}^{n} s_{i}^{c_{i}(g)},

where c_{i}(g) is the number of i-cycles of g. So we immediately deduce from Theorem 2.1(c):

Theorem 3.1 If CP(G_{1}) = CP(G_{2}), then Z(G_{1}) = Z(G_{2}).

The role of the cycle index in combinatorial enumeration is well-known (see for example, [11]). Note in particular:

Proposition 3.2 Z(G) determines the number of orbits of G on Ω^{k} and on the set of k-element subsets of Ω. In particular, it determines |G|.

The last statement follows from the first, but is most easily seen by substituting s_{1} = 1, s_{i} = 0 for i > 1, in Z(G).

The permutation character of G is the function π : G → {0, 1, …, n} given by

π(g) = number of fixed points of g

for g ∈ G. A well-known Möbius inversion shows that the permutation character of G determines Z(G): for

π(g^{k}) = ∑_{i|k} ic_{i}(g),

and so

c_{k}(g) = \frac{1}{k} ∑_{i|k} μ(k/i)π(g^{i}).

Hence different actions of the same group which have the same permutation character will have the same cycle index. The simplest example is given by the two actions of the Klein group V_{4} on six points:

G_{1} = {1, (1, 2)(3, 4), (1, 2)(5, 6), (3, 4)(5, 6)},
G_{2} = {1, (1, 2)(3, 4), (1, 3)(2, 4), (1, 4)(2, 3)}.

A more elaborate example, given by Guralnick and Saxl [9], has G_{1} primitive and G_{2} imprimitive.

Groups with the same cycle index which are not even be abstractly isomorphic are not difficult to find. For example, if two groups G_{1} and G_{2} have the same numbers of elements of each order then their regular representations have the same cycle index. Examples include

\begin{matrix}Q_{8} × C_{2} & and & C_{4} × C_{4} & (n = 16), \\ C_{3} × C_{3} × C_{3} & and & P_{27} & (n = 27), \end{matrix}

where P_{27} is the nonabelian group of order 27 and exponent 3. Of course, the groups of Example 2.3 also have the same cycle index.

Turning to the set cp(G) without multiplicities, clearly little can be said. This information determines the orders of elements of G (and hence the exponent of G) but not |G| or the number of orbits of G.

4 The Parker vector

In the preceding sections, we treat the cycles of a permutation as the parts of a partition, ignoring the cyclic structure on each. A complementary approach is to consider the cycles in isolation. This approach was taken by Parker [16].

Let Γ_{i}(G) be the set of all i-cycles which appear in the cycle decomposition of some element of G, and let Γ(G) = ⋃_{i=1}^{n} Γ_{i}(G). Now G act on Γ_{i}(G) by conjugation: let p_{i}(G) be the number of orbits in this action. Note that Γ_{1}(G) is isomorphic to Ω, since each point of Ω occurs as a singleton cycle in the identity. Parker gave the formula

p_{i}(G) = \frac{1}{|G|} ∑_{g∈G} iγ_{i}(G),

and deduced that

∑_{i=1}^{n} p_{i}(G) = n

for any permutation group G of degree n.

For a summary of the information about G which is contained in its Parker vector

p(G) = (p_{1}(G), …, p_{n}(G))

see Gewurz [7]. Note that p(G) does not determine |G|; for example, we have p(G_{1} ≀ G_{2}) = p(G_{2} ≀ G_{1}) for any two permutation groups G_{1}, G_{2}, where ≀ denotes the wreath product. On the other hand, Gewurz showed that some groups are determined by their Parker vectors, for example, the symmetric group S_{n} for n ≠ 6 (whose Parker vector consists entirely of 1s).

Parker showed that, if G is the Galois group of a given polynomial of degree n over the rational numbers, then there is a randomised algorithm which computes efficiently the Parker vector of G.

Gewurz [8] pointed out that the Parker vector is determined by the cycle index (and so a fortiori by CP(G)):

Proposition 4.1 p_{i}(G) = i\frac{∂}{∂s_{i}} Z(G)|_{s_{j}=1}.

We can regard Γ(G) as a set of permutations in the symmetric group S_{n}, where each point outside the cycle is regarded as being fixed. In general, of course, Γ(G) is not a subset of G. In fact, the following holds (see [3]):

Proposition 4.2 We have Γ(G) ⊆ G if and only if G is a direct product of symmetric groups and cyclic groups of prime order.

In fact, if we set C_{0}(G) = G and C_{n+1}(G) = ⟨Γ(C_{n}(G)⟩ for all n ≥ 0, then C_{3}(G) = C_{4}(G) for every finite permutation group G. There exist groups with C_{2}(G) ≠ C_{3}(G); such groups are p-groups for some odd prime p, but the problem of determining them is unsolved.

Problem 4.1 Determine the finite permutation groups G with C_{2}(G) ≠ C_{3}(G).

5 The infinite

Some of the above discussion extends to infinite groups. For the most part, counting results fail; some other results remain true, though more ingenuity is required for the proof.

Recall that a permutation group G on an infinite set Ω is

• highly transitive if it is n-transitive for all natural numbers n;

• oligomorphic if it has only finitely many orbits on Ω^{n} for all natural numbers n;

• finitary if all its elements move only finitely many points;

• cofinitary if all its non-identity elements fix only finitely many points.

(For further details, see [4].)

Theorem 5.1 If CP(G_{1}) = CP(G_{2}) and G_{1} is k-transitive (resp. highly transitive, oligomorphic, finitary, cofinitary), then so is G_{2}.

Proof For ‘finitary’ and ‘cofinitary’, this is obvious.

As in the proof of Theorem 2.1, CP(G) determines the orbits of G and also determines CP(G_{α}) for all α ∈ Ω. By induction it determines the orbits of all n-point stabilisers. Now G is oligomorphic (resp. highly transitive) if the stabiliser of any n-tuple has only finitely many (resp. just one) orbit on the remaining points. The argument for k-transitivity is similar.

If G is oligomorphic, then a modified cycle index Z̃(G) can be defined for G as follows: take the sum of the cycle indices of the groups G_{Δ}^{Δ} (the permutation group induced on Δ by its setwise stabiliser), where Δ runs over a set of representatives of the orbits of G on finite sets. This plays a similar role in enumeration to the cycle index of a finite permutation group. Indeed, oligomorphic permutation groups are precisely those for which such an enumeration theory can be developed. To make a connection with the work of Roland Fraïssé [10], note that if the oligomorphic group G is the automorphism group of a homogeneous structure M, then its modified cycle index is obtained by summing the cycle indices of the (unlabelled) structures in the age of M.

Does CP(G) determine the modified cycle index of the oligomorphic group G? For each finite set Δ, it determines CP(G_{Δ}^{Δ}), and hence Z(G_{Δ}^{Δ}), by Theorem 3.1. However, CP(G) does not determine the orbits of G on Ω^{n}, or on the set of finite subsets of Ω, as Example 2.1 shows. Nevertheless, we have:

Theorem 5.2 If CP(G_{1}) = CP(G_{2}) and G_{1} is oligomorphic, then Z̃(G_{1}) = Z̃(G_{2}).

Proof Although we cannot determine the orbits, we can determine a set of orbit representatives for G on Ω^{n}, as follows: first determine orbit representatives for G on Ω; then, for each such α_{1}, determine orbit representatives for G_{α_{1}} on the points different from α_{1}; then for each such pair (α_{1}, α_{2}), determine orbit representatives for G_{α_{1}α_{2}} on the points different from α_{1} and α_{2}; and so on.

Now let (α_{1}, …, α_{n}) be an orbit representative, and let Δ = {α_{1}, …, α_{n}}. We can determine Z(G_{Δ}^{Δ}). However, the orderings of a given set Δ lie in n!/|G_{Δ}^{Δ}| different orbits on n-tuples. So we multiply Z(G_{Δ}^{Δ}) by this factor, and we sum these terms over all orbit representatives on n-tuples. Finally, we sum the result for all n.

The original question of Leporati which motivated this study is open in the infinite case:

Problem 5.1 If H ≤ G and CP(H) = CP(G), does it follow that H = G?

Recall that a base for a permutation group G on Ω is a sequence B of elements of Ω whose pointwise stabiliser is the identity. The answer to Problem 5.1 is affirmative if G has a finite base. This follows easily by induction from the fact that, if H ≤ G and, for some point α ∈ Ω we have α^{G} = α^{H} and G_{α} = H_{α}, then H = G. For the statement that α^{G} = α^{H} means that H contains a set of coset representatives for G_{α} in G.

More generally, if H ≤ G and CP(G) = CP(H), then the closures of G and H in the symmetric group (in the topology of pointwise convergence) are equal. For the closure of G consists of all permutations which preserve every G-orbit on n-tuples for all n. By hypothesis, a set of H-orbit representatives on n-tuples is also a set of G-orbit representatives; so G and H have the same orbits on n-tuples, and hence the same closure. (This is a generalisation of the preceding remark, since it is known that a group having a finite base is closed.)

Since every finite permutation group is closed (and has a finite base), this produces an alternative proof of Corollary 2.2.

6 Remarks and problems

I have said nothing about the problem of deciding whether a given set S of partitions is equal to CP(G) for some group G. Clearly this could be done by computing (as in Theorem 2.1(c)) the number of permutations g ∈ G with CP(g) = π for each partition π ∈ S, choosing in all ways the correct number of permutations, and checking whether we have a group. This algorithm will be very inefficient!

A subset of CP(G) may suffice to specify G. The stabiliser chain of G relative to a base B of size k is the sequence (G_{0} = G, G_{1}, …, G_{k−1}, G_{k} = 1) of subgroups, where G_{i} is the stabiliser of the first i points of B. A set S ⊆ G is a strong generating set (relative to B) if it contains a subset S_{i} which generates G_{i} for i = 0, 1, …, k. I owe the following result to Leonard Soicher [17].

Proposition 6.1 If S is a strong generating set for G, then CP(S) determines |G|.

Proof Suppose that the subset X = CP(S) of P_{n} is given. If we know B, we argue by induction exactly as in the proof of Theorem 2.1(a). We have to modify the condition for two points α and β to be in the same orbit: this holds if and only if there is a sequence

α = ω_{0}, ω_{1}, …, ω_{d} = β

such that, for i = 1, …, d, there is a partition in X for which ω_{i−1} and ω_{i} lie in the same part.

If we do not know B, we test all tuples B = (α_{1}, …, α_{k}) for which the partition of B into singletons is not contained in any non-trivial partition of X, applying the preceding algorithm to B. If B is a base such that X comes from a strong generating set relative to B, we obtain |G|. If not, then we obtain a smaller number. So the largest number obtained is |G|. It suffices to test all tuples which are minimal with respect to the specified property.

I do not know how to recognise the set CP(S) arising from a strong generating set S for a permutation group.

We could play the same game with subsets instead of partitions. That is, we could assume that we know the cycles, or the supports of the cycles, or just the cycle lengths, either with or without multiplicities, and ask what information we can deduce about the group. Note that, with or without multiplicities, the following implications hold between what we can learn about a group from this information:

set partitions → number partitions
↓  ↓
cycles → cycle supports →  cycle lengths

I leave to the diligent reader the task of carrying out such an investigation, starting with the following facts:

(a) the multiset of cycle lengths determines |G| and the Parker vector of G;

(b) the set of cycles determines the groups C_{n}(G) for n ≥ 1 (see Section 4);

(c) the set of cycle supports determines the orbits of G.

References

[1] P. Bonizzoni, G. Della Vedova, A. Leporati, D. Lucarella and G. Mauri, A unifying framework to charcterize the power of query languages, preprint.

[2] W. Bosma and J. Cannon, The MAGMA Handbook, available from the Computational Algebra Group, University of Sydney, 1999.

[3] P. J. Cameron, Cycle-closed permutation groups, J. Algebraic Combinatorics 5 (1996), 315–322.

[4] P. J. Cameron, Permutation Groups, Cambridge University Press, Cambridge, 1999.

[5] W. Fulton, Young Tableaux, London Math. Soc. Student Texts 35, Cambridge University Press, Cambridge, 1997.

[6] The GAP Group, GAP — Groups, Algorithms, and Programming, Version 4.2; Aachen, St Andrews, 1999.

   (http://www-gap.dcs.st-and.ac.uk/~gap)

[7] D. A. Gewurz, Reconstruction of permutation groups from their Parker vectors, J. Group Theory, to appear.

[8] D. A. Gewurz, Parker vectors and cycle indices of permutation groups, in preparation.

[9] R. M. Guralnick and J. Saxl, Primitive permutation characters, pp. 364– 367 in Groups, Combinatorics and Geometry (ed. M. W. Liebeck and J. Saxl), London Math. Soc. Lecture Notes 165, Cambridge University Press, Cambridge, 1992.

[10] R. Fraïssé Theory of Relations, North-Holland, Amsterdam, 1986.

[11] F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, New York, 1973.

[12] M. R. Jerrum, A compact representation for permutation groups, J. Algorithms 7 (1986), 60–78.

[13] P. Kolaitis, personal communication.

[14] A. Leporati, personal communication.

[15] E. O’Brien, personal communication.

[16] R. A. Parker, personal communication.

[17] L. H. Soicher, personal communication.