Math.uic.edu

MINIMAL PERMUTATION REPRESENTATIONS OF NILPOTENT GROUPS BEN ELIAS, LIOR SILBERMAN, AND RAMIN TAKLOO-BIGHASH ABSTRACT. A minimal permutation representation of a finite group G is a faithful G-set with the smallestpossible size. We study the structure of such representations and show that for certain groups they may beobtained by a greedy construction. In these situations (except when central involutions intervene) all minimalpermutation representations have the same set of orbit sizes. Using the same ideas we also show that if thesize d(G) of a minimal faithful G-set is at least c|G| for some c > 0 then d(G) = |G|/m + O(1) for aninteger m, with the implied constant depending on c.
It is a classical theorem of Cayley’s that a group G is isomorphic to a subgroup of a symmetric group.
Accordingly we let the degree d(G) of the finite group G be the least integer d such that G can be embeddedin Sd, the symmetric group on d letters. More precisely, Cayley’s discussion in [4] implicitly relies on theobservation that the regular action of the group on itself gives an embedding of G into Sn, where n = |G|is the order of G. It is then natural to ask to what extent the resulting bound d(G) ≤ n is sharp.
The problem of finding d(G) was first studied by Johnson [7]. Among other things, he classified those groups for which d(G) = n. Except for a family of 2-groups, these groups are precisely the cyclic p-groups. A structure theorem for groups with d(G) ≥ cn, c any fixed positive constant, was obtained by[1] (see Remark 4.2 below), while related results were obtained by Berkovich in [2].
Although easy to define, the degree is difficult to compute. It is more-or-less obvious that d(G) can be computed by examining all subsets of the subgroup lattice of G. The main conceptual finding of this noteis that in some cases a “greedy” algorithm is also available, that is an algorithm that proceeds by makinglocally optimal choices rather than directly searching for the global minimum. This is hardly of practicalapplication (the subgroup lattice of a group may be exponentially larger than the group itself), but it hassurprising consequences for the structure of a minimal permutation representation. We note that whenevera group G acts on a set X, the sizes of the orbits of the action determine a partition of |X|. Our mainapplication is: Theorem 1.1. Let G be a finite nilpotent group of odd order. For each prime p, let ep be maximal such that the center of G contains a subgroup isomorphic to the elementary abelian group faithful permutation representation of G. Then, (1) The number of orbits for the G-action on X is (2) The multiset of sizes of the orbits is a group isomorphism invariant.
This is a special case of a more general result, Theorem 3.18 below. We remark that a restriction of the odd-order type is necessary, the simplest counterexample being the four-group C2 × C2. Its regular repre-sentation is a minimal permutation representation, but it also has minimal representations with two orbitsof size 2. Though not strictly necessary for the proofs of Theorems 1.1 and 3.18, we include Theorem3.16. This theorem, which gives a method to find all perfect minimal faithful permutation representations(c.f. Definition 3.12), forms the conceptual backbone of our work.
The main motivation of this work was to understand the distribution of ∆(G) = d(G)/ |G| in the interval [0, 1]. For example, it was easy to show that every number of the form 1 , n a positive integer, is a limit point of ∆(G) as |G| tends to infinity. Clearly, zero is also a limit point. We show here (see Theorem4.6 below) that these are the only limit points.
This paper is organized as follows. In Section 2 we recall basic definition. Section 3 contains our main results. Section 4 contains our study of limit points of ∆(G) in the interval [0, 1], plus some numericalresults.
We review our notation for standard constructions for group actions. For further details and basic definition see e.g. sections 1.1-1.4 of [3], or sections 1.3-1.4 of [5]. For basic materials on socle seesection 4.3 of [5].
Let G be a finite group acting on a set X. We call this action a minimal faithful permutation represen- tation if the action is faithful, and the size of the set X is the smallest possible among all sets on which Gacts in a faithful fashion. Under the action of G, the set X decomposes as a disjoint union of orbits. Choos-ing a point stabilizer subgroup in each orbit, it is clear that minimal faithful permutation representationscorrespond to collections1 H of subgroups of G where: [G : H] is minimal among all H satisfying (1).
We call such sets H “minimal faithful collections”; they are the subject of this paper. The first condition corresponds to faithfulness of the action, the second to the minimality of the degree. Clearly if H is aminimal faithful collection, no two of its elements can be conjugate.
We shall make use of the socle, M(G), of a finite group G, the subgroup generated by the set M(G) of all minimal normal subgroups of G. Specifically, the lattice T (G) = {T subgroups of G contained in the socle will play a major role.
Every element T ∈ T can be written as a direct product of minimal normal subgroups ([10] Thm II.4.8 p.131). In the language of order theory, the lattice T is atomic with the minimal normal subgroups beingthe atoms. Since the lattice of normal subgroups of G is modular, both T and its dual are matroids.
1We shall use the term “colllection” for such sets of subgroups.
MINIMAL PERMUTATION REPRESENTATIONS OF NILPOTENT GROUPS In particular, the number of factors in direct product a representation of T ∈ T as above is an invariant of the pair (G, T ). We denote it dimG T and call it the dimension of T .
When G is nilpotent every normal subgroup intersects the center ([11] Thm IV.2.9 p. 18). The dis- cussion above is then elementary. Since every subgroup of the center is normal, M(G) = M(Z(G)).
Furthermore, the socle is a product of elementary abelian p-groups.
For a subgroup H of G we write RCG(H) for the relative core of H, the subgroup CoreG(H) ∩ M(G).
For a collection H of subgroups we similarly set It is clear that CoreG(H) is trivial if and only if RCG(H) is trivial. This simple observation underlies ourlater analysis.
We extend the notion of dimension above to all subgroups of G by setting dimG(H) = dimG(RCG(H)).
In particular we write dim G for dimG(G) = dimG(M(G)). We will also use the codimension codimG(H) =dim G − dimG(H).
We discuss here the (algorithmic) problem of constructing a minimal permutation representation of G.
As input, we give ourselves the subgroup lattice of G and, in addition, the order of each subgroup andwhether it is normal in G or not. This analysis will shed light on the structure of the minimal permutationrepresentations.
Definition 3.1. Let G be an arbitrary finite group, and let T be as above. We call G socle friendly if forall H < G, T ∈ T , we have RCG(H · T ) = RCG(H).T .
Lemma 3.2. If G is a nilpotent group, then G is socle friendly.
Proof. Since the lattice T is relatively complemented, we may write T = (T ∩ RCG(H)) · S for someT ∈ S disjoint to RCG(H). We then have HT = HS and RCG(H)T = RCG(H)S so we may assumeH ∩T = {1}. Clearly RCG(H)T ⊂ RCG(H ·T ). Conversely, let N < HT be a minimal normal subgroupof G. If N < T there is nothing to prove, so we may assume T ∩ N = {1}. Since H and T are disjoint,every n ∈ N can be uniquely written in the form n = hntn for some hn ∈ H and tn ∈ T . Note that themap n → hn is a group homomorphism (it is the restriction to N of the quotient map HT /T since N and T are disjoint it is an isomorphism onto its image N .
Since N and T are central subgroups (here we use the nilpotence of G), it follows that N is a central subgroup as well, and since N was a cyclic group of prime order so is N . It follows that N is a minimalnormal subgroup of G, contained in H. We conclude that N ⊂ N T ⊂ RCG(H)T .
Remark 3.3. Not every finite group is socle friendly. Here is the construction of an infinite family ofexamples ([9]). Let H be any finite group with two non-isomorphic one dimensional representations V1, V2over a finite field F. We let V = V1⊕V2 and G = H V . Then M(G) = V and T = {0, V1, V2, V }. Let Wbe any one dimensional F-subspace not containing either of V1, V2. Then W is core-free and consequentlyRCG(W ).V1 = V1 and RCG(W ).V2 = V2. But W.V1 = W.V2 = V and as a result RCG(W.V1) =RCG(W.V2) = V . This shows that G is not socle friendly.
3.2. Minimal faithful collections and codimension one subgroups. Let G be a finite socle friendlygroup. We are interested in constructing a minimal faithful collection of subgroups of G, and a naturalway to do so is step-by-step, incrementally adding subgroups to our collection until it is faithful. Ratherthan keeping track of CoreG(H), we note that RCG(H) carries sufficient information to decide whetherCoreG(H) is trivial. Moreover, while the cores CoreG(H) decrease through the lattice of all normalsubgroups of G, the relative cores RCG(H) decrease through the lattice T (G) which is much easier towork with.
We now turn to the “minimality” property of a collection, which appears to push in the opposite direction to “faithfulness”. The first favors selecting large subgroups, and having few of them. The second seemsto suggest choosing small subgroups, or else many large ones will be needed. The multiplicative propertyof orders of subgroups actually implies that choosing many large subgroups is the right way The analysisis very similar to that of Johnson [7]. In both cases it is shown that the elements of a minimal faithfulcollection may be (and in some cases, must be) drawn from a particular class of subgroups, using the sametrick. The reader should compare the following Lemma with [7, Lemma 1] Lemma 3.4. (“replacement lemma”) Let H < G be of codimension at least 2. Then there exist subgroupsH1 and H2 of G containing H such that RCG(H1) ∩ RCG(H2) = RCG(H) and 1 + 1 Moreover, this inequality is strict unless G contains at least two central involutions.
Proof. Since T is a matroid and RCG(H) has codimension at least 2, there exists two minimal normalsubgroups N1, N2 ∈ M(G) (“atoms of the lattice T (G)”) such that the lattice join RCG(H)N1N2 hasdimension greater by 2 than that of RCG(H). In other words, that lattice join is a direct produt. Theinclusions RCG(H) < RCG(H)Ni are then proper, and we have RCG(H) = RCG(H)N1 ∩ RCG(H)N2.
We thus set Hi = H · Ni, i = 1, 2 (these are semi-direct products as the Ni are minimal normal subgroups). By Lemma 3.2, RCG(Hi) = RCG(H)Ni, and it follows that RCG(H1) ∩ RCG(H2) =RCG(H). Since H is a proper subgroup of both H1, H2 its index in both subgroups is at least 2, and wehave Equality can only happen if both N1 and N2 are of order 2, in which case the non-trivial elements of Ni Definition 3.5. Let A = A(G) denote the set of subgroups of G of codimension 1.
The reader should compare the next theorem with [7, Cor. 1].
MINIMAL PERMUTATION REPRESENTATIONS OF NILPOTENT GROUPS Theorem 3.6. There exist minimal faithful collections contained in A, and these are the ones of maximalsize. If G has at most one central involution then every minimal faithful collection is contained in A.
Proof. Let H be a faithful collection, and let H ∈ H. If H is of codimension 0 (i.e. RCG(H) = M(G))we have {1} = RCG(H) = RC (H \ {H}) ∩ RCG(H) = RC (H \ {H}) .
In particular, H \ {H} is also faithful. If H has codimension at least 2, let H1, H2 be the subgroupsconstructed in Lemma 3.4, and let H = (H \ {H}) ∪ {H1, H2}. By construction we have RCG(H ) =RCG(H) = {1} so that H is faithful. In addition, Lemma 3.4 yields ∆(H ) ≤ ∆(H), with a strictinequality if G has at most one central involution. In general we note that H has more elements than H. Inparticular, a minimal faithful collection of maximal size must consist of codimension-one subgroups.
Definition 3.7. Call a collection H ⊂ A independent if its relative core is strictly contained in that of anyproper sub-collection, in other words if RCG(H) | H ∈ H is an independent set of atoms in the latticedual to T .
A minimal faithful collection H ⊂ A is certainly independent – otherwise it would have a faithful Proposition 3.8. The set of independent collections of A forms a matroid, i.e. the following statementsare true: (1) A subcollection of an independent collection is independent.
(2) H ⊂ A is independent if and only if codimG HM = |H|.
(3) If H, H are independent collections with |H | > |H| then there exists H ∈ H such that H ∪ {H } Proof. This will follow via the replacement Lemma from general fact that T is a matroid.
(1) Let H ⊂ A be independent, and suppose H us a proper subcollection of H ⊂ H such that contradicting the independence of H.
(2) Let S, T ∈ T (G) with codimG T = 1. Then ST either equals T or M , and we have dimG S ∩ T = dimG S or dimG S − 1, respectively, by the inclusion-exclusion formula for dimension. Byinduction on the size of any collection H = {Hi}k equality if and only if the sequence of intersections ∩m RC is not possible by the choice of H ). By part (2) we see that that H ∪ {H } is independent.
Corollary 3.9. Let H ⊂ A be independent. Then the following are equivalent: (1) |H| = dim G;(2) H is faithful;(3) H is a maximal independent subset of A. Here, maximal means maximal with respect to inclusion.
Proof. The equivalence of (1) and (2) is contained in part (2) of Proposition 3.8. An independent collectionwith HM = {1} is certainly maximal. An independent collection with HM = {1} is not maximal since inthat case there exists some T ∈ T of codimension 1 which does not contain HM , and we can add it to Hto form a larger independent collection.
Corollary 3.10. A subset H ⊂ A is a minimal faithful collection if and only if it is independent andmaximizes Proof. We have already noted that a minimal faithful collection contained in A is independent and maxi-mal (with respect to inclusion), and that a maximal (with respect to inclusion) independent set is a faith-ful collection. It is clear that a subset maximizing this weight function is maximal independent, since2 − 1 > 0 for all subgroups H. Finally, we note that a maximal independent set H satisfies Corollary 3.11. There exist minimal faithful collections of size dim G. If G has more than one centralinvolution, there may also exist minimal faithful collections of smaller size.
Proof. We have seen that there exist minimal faithful collections contained in A, that these are independentsets, and that every independent set has dim G elements.
Inspired by this Corollary we make the following definition: Definition 3.12. A minimal faithful collection of size dim G is called perfect. Correspondingly, a minimalfaithful permutation representation with dim G orbits under the G-action is called perfect.
Example 3.13. Let G be a p-group for a prime p, and let Z = Z(G) be its center. It is well-known(and follows from the class formula) that every normal subgroup of G intersects the center non-trivially.
Since every subgroup of the center is normal, it follows that M(G) = M(Z), and in particular dim G =dim Z(G). This observation recovers [7, Thm. 3]: Theorem 3.14. Let G be a p-group with center Z. Then there exists a minimal faithful collection for G ofsize dim Z. If p is odd this holds for all minimal faithful collections.
MINIMAL PERMUTATION REPRESENTATIONS OF NILPOTENT GROUPS 3.3. Construction. In the remainder of this section we assume that G is a socle friendly finite group.
We have reduced the problem of finding a minimal faithful collection to maximizing an additive weightfunction on a matroid. This is a problem which is solvable by a greedy algorithm, and this allows us togive a way to search for and construct perfect minimal faithful permutation representations. Before wepresent our method we record a useful Lemma: Lemma 3.15. Let H ⊂ A be independent, and suppose H < G has the largest size possible such thatH Then H ∈ A, H ∪ {H } is independent, and H maximizes the function w(H) = 2 − 1 among all H ∈ A such that H ∪ {H} is independent.
Proof. We can find T ∈ T of codimension 1 containing H we have HM = H T = T , which does not contain H = T , so that H is of codimension 1 and H ∪ {H } is independent. Finally H was chosen to maximize w(H) in an even larger family than needed.
We now describe a method to find all perfect minimal faithful permutation representations. We assume (1) The subgroup lattice of G;(2) the sizes of every element of the subgroup lattice;(3) and that normal subgroups are marked as such.
Then for each i ≥ 0 we recursively construct a sequence of triples (Hi, Ti, ∆i) with each Hi a collection of subgroups of G, Ti a subgroup of G, and ∆i a non-negative real number. In order to do this we proceedas follows. Let H0 = ∅, T0 = M(G), ∆0 = 0. Now suppose (Hi, Ti, ∆i) is given, and Ti = {1}. First wefind a subgroup Hi+1 of G of maximal size not containing Ti. Then we set Hi+1 = Hi ∪ {Hi+1}, Ti+1 =Ti ∩ CoreG(Hi+1), ∆i+1 = ∆i + i = {1}, we simply set (Hi+1, Ti+1, ∆i+1) = (Hi, Ti, ∆i).
The sequence (Hi, Ti, ∆i) is certainly not unique and depends on the choices of the subgroups Hi. Thenwe have the following theorem: Theorem 3.16. Let G be a socle friendly finite group, and let dim G = δ. Then (1) For any choice of the subgroups Hi, Tδ−1 = {1} whereas Tδ = {1}. Furthermore, Hδ is a minimal faithful collection of size δ, and ∆δ = ∆(G).
(2) Conversely, up to G-isomorphism any minimal faithful collection of size δ can be obtained this Proof. First we prove the first part. From Lemma 3.15 it is clear for each i the collection Hi is independent,and Ti = (Hi)M . Also it is easy to see that for each i, dim Ti+1 = dim Ti − 1 as long as Ti = {1}. Theseobservations immediately give the first assertion of the theorem. We show by induction that for k ≤ δ, is minimal among independent collections of size k. This is certainly the case for k = 0. Thus let Hk−1 be given, and choose the subgroup Hk. Suppose there is an independent collection H ⊂ A ofsize k such that 1 . We may then write H = H ∪ {H } where H is a member of minimal size. By the inductive hypothesis, must have |Hk| < |H |. By the choice of H , we actually have |H use the matroid property of the independent subcollections of A shown in Proposition 3.8(3): since H isof size k, while Hk−1 is of size k − 1, there exists some H ∈ H such that Hk−1 ∪ {H } is independent.
In particular this implies that (Hk−1 ∪ {H }) contradiction to the existence of H .
Now we prove the second part. Let H = {Hi}δ be a minimal faithful collection, ordered such that |H1| ≥ |H2| ≥ · · · ≥ |Hδ| .
Then we claim that each k, Hk has maximal size among all subgroups H of G such that {Hi}k−1 ∪ {H} . By induction, it suffices to check that if a subgroup H < G is in- dependent of {Hi}k−1 then there exists l ≥ k such that H ∪ {H } \ {H G(Hi). It is then easy to see that we may take l to be the first j such that RCG(H ) ∩ Sj = Sj .
The assertion of the theorem is now immediate.
3.4. The main theorem. In this section we state and prove our main theorem. We start with a definition: Definition 3.17. Let G be a finite group. Given a permutation representation X we denote by m(X) themulti-set consisting of the sizes of the orbits of X under the G-action.
Theorem 3.18. Let G be a socle friendly finite group. Let X be a minimal faithful permutation represen-tation of G. Then, (1) The number of orbits of X under the action of G is at most dim G;(2) G has perfect minimal faithful permutation representations; and if the center of G has at most one involution then every faithful permutation representation is perfect; (3) If X1, X2 are two perfect minimal faithful representations of G, then m(X1) = m(X2).
Proof. The first two parts of the theorem follow from Corollary 3.11. The third part easily follows fromTheorem 3.16 and its proof.
4.1. Accumulation points of ∆(G). Let n, p ∈ N with p > n a prime. Then ∆(Cn × Cp) = 1 + ∆(Cn) = . This means that for each positive integer n, the point 1 is an accumulation point of the set {∆(G);G finite group} in the interval [0, 1]. In fact, in Theorem 4.6 below we show that these points are the only non-zero accumulation points. We begin with somepreliminary lemmas.
Lemma 4.1. Let H < G be a subgroup. Then d(H) ≤ d(G) and ∆(G) ≤ ∆(H).
Proof. The first claim is obvious. For the second, let H be a faithful collection of subgroups of H andnote that ∆(H) is independent of the ambient group. Then KG(Hi) ⊂ KH(Hi) (larger intersection). Inparticular, KG(H) = {1}. Choosing H minimal for H we deduce that ∆(G) ≤ ∆(H) = ∆(H).
MINIMAL PERMUTATION REPRESENTATIONS OF NILPOTENT GROUPS Remark 4.2. A cyclic p-group has relative degree 1. In particular, if P < G is a cyclic p-group then Conversely, Babai-Goodman-Pyber [1] give an explicit function f : [0, 1] → R such that if ∆(G) ≥ ∆then G has a cyclic p-subgroup of index at most f (∆). In other words, as |G| grows with ∆(G) ≥ ∆, thedegree of G is controlled (up to bounded multiplicative error) by the size of the largest cyclic p-subgroupof G. Specifically, they show that when G does not possess a large cyclic group of prime-power order ithas a pair of reasonably large subgroups with trivial intersection.
Note that the above bound on ∆(G) is derived from a faithful collection of size 2. In Lemma 4.3 we show that when ∆(G) ≥ ∆ there exists k depending only on ∆ such that a minimal permutationrepresentation of G has at most k orbits. The case of groups of prime exponent and nilpotence class two,studied in [1, Thm. 3.6] as well as [8] shows that we need k > 2 in general.
Lemma 4.3. Let k = dim G. Then ∆(G) ≤ Proof. Write the socle M = M(G) as the direct product of k minimal normal subgroups {Si}k . For j . It is clear that {Hi} is a faithful collection of size k and each of its elements Lemma 4.4. Let P be a cyclic p-subgroup of G. Then RCG(P ) < M(P ). If |G| is large enough comparedto [G : P ] then equality holds.
Proof. Let N < P be non-trivial and normal in G. Then M(P ) is a characteristic subgroup of N . Itfollows that RCG(P ) is either trivial or equal to M(P ). In any case, we have dimG P ≤ 1.
Finally, the core of P has index at most ([G : P ])! (it is the kernel of a homomorphism into S[G:P ]). If |G| > ([G : P ])! then CoreG(P ) is a non-trivial normal subgroup of G contained in P , hence containingits unique subgroup of order p. In that case M(P ) is normal in G and thus RCG(P ) = M(P ).
In fact, if G has a large cyclic p-subgroup then a permutation representation with two orbits is almost Corollary 4.5. Let P be a cyclic p-subgroup of G, and let l(G) be the order of the smallest point stabilizerin an orbit in a minimal permutation representation of G. Then Proof. Let H be a minimal faithful collection for G, chosen so that it contains an element H1 of smallestpossible order (denoted above by l(G)). Clearly ∆(G) = ∆(H) ≥ as well assume M (P ) ∈ M(G), otherwise KG(P ) = {1} and the claim is clear. Then H, being faithful,must contain an element H2 disjoint from M (P ), hence {P, H2} is a faithful collection.
Theorem 4.6. Let Gn be a sequence of groups with orders increasing to infinity such that limn→∞ ∆(Gn) >0. Then this limit is of the form 1/l for some l ∈ N.
Proof. For n large enough we have ∆(Gn) > ∆ > 0. The main result of [1], already quoted above, is thatGn has a cyclic pn-subgroup Pn of index at most f (∆) for some f : [0, 1] → N. It follows that Here l(Gn) is as in the statement of Corollary 4.5. As |Gn| → ∞, we see that limit. The sequence of integers l(Gn) must then be eventually constant.
Note that we have shown more, that if ∆(G) ≥ ∆ > 0 then any minimal permutation representa- tion consists of one large orbit of size essentially |G| ∆(G), and several other orbits of size and numberbounded in terms of ∆. Indeed, the number of orbits is bounded by Lemma 4.3. We have an obviousbound l(G) ≤ (∆(G) − f (∆)/ |G|)−1. Next, as soon as |G| is large enough so that the subgroups H1, H2 of Lemma 4.4 must have the same size. We conclude that if ∆(G) > ∆ and |G| islarge enough (depending on ∆), G has a cyclic p-subgroup P of index at most f (∆) such that M (P ) isnormal in G and a subgroup H of order l(G) belonging to a minimal faithful collection and disjoint fromM (P ). Then every other member of that minimal faithful collection may be replaced with P keeping thecollection faithful. Hence all other orbits in the representation must have size at most f (∆).
4.2. Some numerical results. The thesis [6] contains an implementation of procedure preceding Theo-rem 3.16 in the algebraic programming language MAGMA [12]. Using the limited computing power of apersonal computer, p-groups of order pn with n ≤ 6 with small p were examined. Any such group can befound in the MAGMA database. Let us summarize the findings.
There is only one group G of order p, and for this group ∆(G) = 1. There are two groups of order p2, namely Zp × Zp and Zp2. Here ∆(Zp × Zp) = 2 and ∆( There are five groups of order p3: one cyclic with ∆ = 1; one elementary abelian with ∆ = 3 ; one abelian with a generator of order p2, having ∆ = 1 + 1 ; and two non-abelian groups both having ∆ = 1 .
∆(G) = 1 + 3 + 4 . For groups of order p4 and p5 we state the following conjecture: For any prime p ≥ 3, there are exactly fifteen groups of order p4, and these can be enumerated and described. So the proof of the first part of the conjecture should be straightforward. We have computation-ally verified the conjecture for groups of order p4 for every prime p in the range 3 < p < 50 and severallarger values of p (≈ 1000). We considered the groups of order p5 for p ≤ 19. Note that the number ofgroups of order p5 is 61 + 2p + 2 gcd(p − 1, 3) + gcd(p − 1, 4). For groups of order p6, we did not haveenough data points to be able to guess a formula.
MINIMAL PERMUTATION REPRESENTATIONS OF NILPOTENT GROUPS We would like to acknowledge conversations with John Conway, William Kantor, Avinoam Mann and James Wilson. Our interest in minimal permutation representations was triggered by a question raisedby Andre Kornell in a Princeton undergraduate Algebra class. During the initial investigation, the thirdauthor was assisted by Evan Hass, another student in that class. Theorem 3.16 was initially obtained forp-groups by the first author under the supervision of the third author ([6]). In an earlier draft of this paperwe had claimed that every finite group is socle friendly (Definition 3.1). We wish to thank Neil Saundersfor pointing out this inaccuracy and constructing a counterexample ([9]. Also c.f. Remark 3.3 where asimplification of Saunders’ example is presented.). We also thank two anonymous referees for their carefulreading of the manuscript and their many suggestions which led to considerable improvement in the styleand presentation of the paper.
The second author’s research was supported in part by a Porter Ogden Jacobus Fellowship at Princeton University, a Clay Mathematics Foundation Liftoff Fellowship, and the National Science Foundation underagreement No. DMS-0111298. The third author’s research was partially funded by the Young InvestigatorGrant No. 215-6406 from the NSA and by the National Science Foundation grant No. DMS-0701753.
Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF and the NSA.
1. László Babai, Albert J. Goodman, and László Pyber, On faithful permutation representations of small degree, Comm.
Algebra 21 (1993), no. 5, 1587–1602.
2. Yakov Berkovich, The degree and index of a finite group, J. Algebra 214 (1999), no. 2, 740–761.
3. Peter J. Cameron, Permutation groups, London Mathematical Society Student Texts, vol. 45, Cambridge University Press, 4. Arthur Cayley, Desiderate and suggestions: No. 1. the theory of groups, Amer. J. Math. 1 (1878), no. 1, 50–52.
5. John D. Dixon and Brian Mortimer, Permutation groups, Graduate Texts in Mathematics, vol. 163, Springer-Verlag, New 6. Benjamin Elias, Minimally faithful group actions and p-groups, 2005, Princeton University Senior Thesis.
7. D. L. Johnson, Minimal permutation representations of finite groups, Amer. J. Math. 93 (1971), 857–866.
8. Peter M. Neumann, Some algorithms for computing with finite permutation groups, Proceedings of groups—St. Andrews 1985 (Cambridge), London Math. Soc. Lecture Note Ser., vol. 121, Cambridge Univ. Press, 1986, pp. 59–92.
9. Neil Saunders, Private communication, 09/01/2007.
10. Michio Suzuki, Group theory. I, Grundlehren der Mathematischen Wissenschaften, vol. 247, Springer-Verlag, Berlin, 1982.
11.
, Group theory. II, Grundlehren der Mathematischen Wissenschaften, vol. 248, Springer-Verlag, New York, 1986.
12. MAGMA Computational Algebra System, http://magma.maths.usyd.edu.au/.
BEN ELIAS, COLUMBIA UNIVERSITY DEPARTMENT OF MATHEMATICS, NEW YORK, NY 10027E-mail address: [email protected] DEPARTMENT OF MATHEMATICS, UNIVERSITY OF BRITISH COLUMBIA, VANCOUVER BC V6T 1Z4, CANADAE-mail address: [email protected] RAMIN TAKLOO-BIGHASH, DEPARTMENT OF MATH, STAT, AND COMP SCI, UNIVERSITY OF ILLINOIS AT CHICAGO,

Source: http://www.math.uic.edu/~rtakloo/papers/group-paper/delta.12.pdf