[GAP Forum] Metrics for large and small permutation groups.

[Jonathan Cohen]

Hi Javaid and Forum,

> So what is the interpretation of "large groups"?

This requires a bit of terminology. Let G be a permutation group
acting on a set X. A *base* for G is a finite sequence of points from
X whose stabiliser in G is trivial. An *infinite family* of
permutation groups is called *small base* if the minimal length of a
base is polylogarithmic in the degree. What this means is that there
are  positive constants a and b such that each group G in the
family of degree n admits a base of length a*log^b(n). If not, then
the family is called *large base*.

Examples:
-- The symmetric groups are large base, since the minimal base length is
n-1
-- The cyclic groups are small base, since every cyclic groups admits
a bse of length 1
-- The non-alternating finite simple groups are small base (this
follows from a result of cameron)

The *primitive* large base groups are the subgroups of wreath products
S_n wr S_m which contain (A_n)^m, where the wreath product is in its
product action and the action of S_n is on k-element subsets of
{1,2,...,n} - this follows from cameron's result.

Liebeck later sharpened the result to show that every other primitive
group admits a base of length at 9log(n). Praeger and Shalev have
lifted this result to *qusiprimitive groups*, that is, groups all of whose
minimal normal subgroups are transitive. Bamberg has lifted it to
*innately transitive* groups, that is, groups which have at least one
transitive minimal normal subgroup.

As far as I am aware, the question for transitive groups (or broader
classes) remains open. *Large* means *large base* and *small* means
*small base*. One often abuses the definition and refers to individual
groups as small/large when it is clear what infinite family they
belong to.

References:

Peter J. cameron Finite permutation groups and finite simple groups.
Bull. London Math. Soc. 13(1)1--22, 1981

Martin W. Liebeck. On minimal degrees and base sizes of primitive
permutation groups. Arch. Math (basel), 43(1):11-15, 1984

Cheryl E. Praeger and Aner Shalev. Bounds on finite quasiprimitive
permutation groups. J. Aust. Math. Soc., 71(2):243-258, 2001

John Bamberg. Bounds and quotient actions of innately transitive
groups, to appear in the J. Aust. Math. Soc. Available from:
http://www.maths.uwa.edu.au/~john.bam/research/inntrans.html

Jon

--
http://www.maths.uwa.edu.au/~cohenj02