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

[Derek Holt]

Dear GAP Forum

Jonathan Cohen has helpfully provided a helpful and informative description
of small and large base groups.

But, since today is a holiday for the New Year, let me append a couple of
quibbles!

On Sat, Jan 01, 2005 at 03:34:58PM +0800, Jonathan Cohen wrote:
> 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

You have just said that "large base" applies to families of permutation groups
rather than to individual groups, so presumably you mean that the family of
symmetric groups { S_n | n in N } *is* small base.

> -- The cyclic groups are small base, since every cyclic groups admits
> a base of length 1

You have not specified a family of permutation groups here.
The cyclic group generated by (1,2)(3,4,5) has no base of length 1 .

> -- The non-alternating finite simple groups are small base (this
> follows from a result of cameron)

The non-alternating finite simple groups form a family of (isomorphism
classes of) abstract groups rather than a family of permutation groups.
Presumably you are saying here that the family of all equivalence classes of
permutation representations of all non-alternating finite simple groups
is a small base family?

> 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.

Again, it is not immediately clear how to formulate the above statement
in terms of families of groups.

> 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.

It seems to me, on balance, that this particular abuse is a bad idea and
leads to confusion.

Happy New Year,
Derek Holt.

> 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
> 
> 
> 
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum