34
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ I'd be surprised if you can do better than Cayley's theorem. $\endgroup$
    – Steve Huntsman
    Mar 2, 2010 at 15:06
  • 2
    $\begingroup$ A preliminary search uncovered this paper: adsabs.harvard.edu/abs/2007arXiv0705.4122E $\endgroup$
    – Qiaochu Yuan
    Mar 2, 2010 at 15:09
  • 4
    $\begingroup$ In general you really cannot do better than Cayley's theorem: Q_8 embeds in S_8 but not in any smaller symmetric group. $\endgroup$
    – Johannes Hahn
    Mar 2, 2010 at 19:52
  • 5
    $\begingroup$ @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." $\endgroup$
    – I. J. Kennedy
    Sep 28, 2012 at 17:09
  • 2
    $\begingroup$ @Steve Huntsman: the regular representation used in the standard proof of Cayley's theorem embeds $S_3$ into $S_6$ (for instance) and you can obviously do better than that. $\endgroup$
    – Fizz
    Apr 6, 2015 at 14:26

2 Answers 2

Reset to default
36
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 4
    $\begingroup$ 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 $\endgroup$
    – Jack Schmidt
    Apr 12, 2013 at 16:11
  • 2
    $\begingroup$ The literature on this isn't unfortunately summarized in any book I know of. The state of the art as of 1999 is summarized in a master thesis by Stephane R. Lemieux "Minimal degree of faithful permutation representations of finite groups". $\endgroup$
    – Fizz
    Apr 6, 2015 at 8:15
  • 3
    $\begingroup$ Neil Saunders has published several [more recent] papers on this topic, although most pertain to the minimal faithful degree of specific classes of groups. His Ph.D. thesis was also on this topic (‘Minimal faithful permutation representations of finite groups’, 2011), and should be a more recent summary of the state of knowledge, but I'm having trouble locating an on-line copy. $\endgroup$
    – Fizz
    Apr 6, 2015 at 8:20
  • 1
    $\begingroup$ Also, the regular representation used in [the proof of] Cayley's theorem applies to semigroups as well (by substituting transformation semigroups for permutation groups) by it is just as uneconomical as a representation. So it is natural to ask the same question for semigroups: i.e. what is the smallest order of a transformation semigroup that embeds a given semigroup. The literature on the latter is even more sparse. Lemieux cites: D. Easdown, "Minimal faithful permutation and transformation representations of groups and semigroups", Contemporary Math. (1992), Vol. 131 (Part 3), 75-84. $\endgroup$
    – Fizz
    Apr 6, 2015 at 9:29
  • 2
    $\begingroup$ The exact same question can be asked for inverse semigroups (represented as injective partial functions i.e. in the symmetric inverse semigroup). BM Schein has a paper on this. THE MINIMAL DEGREE OF A FINITE INVERSE SEMIGROUP $\endgroup$
    – Fizz
    Apr 6, 2015 at 9:31
5
$\begingroup$

Although tighter results may be available for specific classes of groups (as in the comments and other answer), Babai, Goodman, and Pyber [1] showed that in some sense - made precise in the result below - the only obstacle to having a small faithful permutation representation is having a prime-power cyclic group of small index.

Quoting the main result from the abstract:

Let $\mu(G)$ be the smallest degree of a faithful permutation representation of $G$, and let $i(G)$ be the index of its largest cyclic subgroup of prime-power order. Then $i(G) \geq |G| / \mu(G) \geq \exp(c \sqrt{\log i(G)})$ for some constant $c > 0$.

Rephrasing in terms of bounds on $\mu(G)$, this gives

$$ |G|/\exp(c \sqrt{\log i(G)}) \geq \mu(G) \geq |G| / i(G)$$

[1] László Babai, Albert J. Goodman & László Pyber. On faithful permutation representations of small degree. Comm. Alg., 21(5):1587-1602, 1993. doi:10.1080/00927879308824639

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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