Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a finite group G, I'm interested to know the smallest size of a set X such that G acts faithfully on X. It's easy for abelian groups - decompose into cyclic groups of prime power order and add their sizes. And the non-abelian group of order pq (p, q primes, q = 1 mod p) embeds in the symmetric group of degree q as shown here: www.jstor.org/stable/2306479.

How much is known about this problem in general?

share|improve this question
    
I'd be surprised if you can do better than Cayley's theorem. –  Steve Huntsman Mar 2 '10 at 15:06
    
There's also the strong Cayley theorem: mathreference.com/grp-act,cayley.html –  Qiaochu Yuan Mar 2 '10 at 15:08
1  
A preliminary search uncovered this paper: adsabs.harvard.edu/abs/2007arXiv0705.4122E –  Qiaochu Yuan Mar 2 '10 at 15:09
1  
In general you really cannot do better than Cayley's theorem: Q_8 embeds in S_8 but not in any smaller symmetric group. –  Johannes Hahn Mar 2 '10 at 19:52
1  
@Qiaochu "This paper has been withdrawn by the authors; Proposition 3.10 fails in general. The result still holds for nilpotent groups -- a weaker version will follow." –  I. J. Kennedy Sep 28 '12 at 17:09
show 1 more comment

1 Answer

up vote 20 down vote accepted

It is difficult to find this number for arbitrary finite groups, but many families have been solved. A somewhat early paper that has motivated a lot of work in this area is:

Johnson, D. L. "Minimal permutation representations of finite groups." Amer. J. Math. 93 (1971), 857-866. MR 316540 DOI: 10.2307/2373739.

This paper classifies those groups for which the regular permutation representation is the minimal faithful permutation representation (cyclic of prime power order, K4, or generalized quaternion) and some results on nilpotent groups (improved in later papers).

The minimal permutation degrees of the finite simple groups are known from:

Cooperstein, Bruce N. "Minimal degree for a permutation representation of a classical group." Israel J. Math. 30 (1978), no. 3, 213-235. MR 506701 DOI: 10.1007/BF02761072.

This paper only finds the degrees. A fuller description of the permutation representations are given in:

Grechkoseeva, M. A. "On minimal permutation representations of classical simple groups." Siberian Math. J. 44 (2003), no. 3, 443-462 MR 1984704 DOI: 10.1023/A:1023860730624.

There are a great deal of topics associated with minimal permutation degrees. I'll just briefly sketch them below, let me know if any interest you and I can give citations or longer descriptions:

The minimal degree of a subgroup is never larger than the minimal degree of the parent group, but the minimal degree of a quotient group may be much, much larger than that of the original. This poses problems in computational group theory, since quotient groups may be difficult to represent. Some quotients are easy to represent, and this has had a significant impact on CGT in the last 10 years or so.

Finding minimal permutation representations of covering groups can be difficult, and here I think the results are much less complete. Basically what you want are large subgroups not containing normal subgroups. In a covering group Z(G) is contained in really quite a few of the "good choices". This is because it is contained in Φ(G), the Frattini subgroup, the intersection of the maximal subgroups. One has to give up using maximal subgroups (at least if Z(G) is cyclic of prime power order), and so the minimal degree can increase dramatically.

Minimal degrees of primitive permutation groups is a topic with a different flavor (rather than specific families of groups, it is more of the interactions between group properties), but a great deal is known. Similar techniques are used to describe asymptotic behavior of minimal degrees of arbitrary families of finite groups, and quite powerful results are available there.

share|improve this answer
    
Someone asked for a reference for quotient groups having larger minimal degree than their parents. Extraspecial groups as quotients of direct products of smaller extra special groups work: Neumann (1985) ams.org/mathscinet-getitem?mr=896501 Holt-Walton (2002) ams.org/mathscinet-getitem?mr=1879020 –  Jack Schmidt Apr 12 '13 at 16:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.