Groups, lattices and bases

About ten years ago I wrote a six-page paper, which I didn’t succeed in getting any journal editor to publish. I will say a bit about its contents below, but you can read it now: I have posted it on the arXiv, where it just appeared today (as number 1408.0968). It contains an open problem which I would like to see solved.

A base for a permutation group is a sequence of points whose pointwise stabiliser is the identity. It is irredundant if no point is fixed by the stabiliser of its predecessors, and minimal if no point is fixed by the stabiliser of all the others (that is, every re-ordering is irredundant).

The paper considers three invariants of finite groups defined by base size, as follows:

  • b1(G) is the maximum, over all permutation representations, of the maximum size of an irredundant base;
  • b2(G) is the maximum, over all permutation representations, of the maximum size of a minimal base;
  • b3(G) is the maximum, over all permutation representations, of the minimum base size.

The three measures are non-decreasing (in the order given), but can be all distinct, as they are for PSL(2,7), where they take the values 5, 4, 3 respectively.

The number b1(G) is familiar: it is just the length of the longest subgroup chain in G. This is a parameter dear to me. In the early 1980s, I found the formula

Length of S_n

for the length of a subgroup chain in the symmetric group Sn, where b(n) is the number of ones in the base 2 representation of n. It was found independently by Ron Solomon and Alex Turull, who invited me to join them in writing a paper on it.

The parameter b2(G) is related to embeddings of the Boolean lattice B(n) into the subgroup lattice of G:

First, one can show that B(n) can be embedded as a meet-semilattice if and only if it can be embedded as a join-semilattice (but this is not equivalent to embeddability as a lattice, as is shown by the quaternion group of order 8).

Now one has the following:

  • The largest n for which B(n) is embeddable as a join-semilattice of the subgroup lattice of G is the parameter μ'(G) considered by Julius Whiston, the largest size of an independent subset of G (a subset for which no element is in the subgroup generated by the other elements).
  • The largest n for which B(n) is embeddable as a meet-semilattice of the subgroup lattice of G, so that the bottom element is a normal subgroup, is b2(G).

So the question arises: can the condition in bold type above be deleted? In other words, is b2(G) always equal to μ'(G)? I know of no group in which this is not so.

I know less about b3, but if G is a non-abelian simple group then b3(G) can be found by looking only at primitive permutation representations.

Proofs, further details, and a historical summary can be found in the paper.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , . Bookmark the permalink.

3 Responses to Groups, lattices and bases

  1. Walter Sinclair says:

    I’m not sure how to start thinking about this question. Aside from their cardinalities, what is the general relationship between an irredundant base and an independent set? And is that general relationship less relaxed for a normal subgroup?

    • Bases depend on a particular permutation action, that is what makes that side of the equation difficult. Also, I find any minimax number a bit slippery to think about. My own view is that the best way in is to decide whether the statement I highlighted is really unnecessary, that is, if the Boolean lattice is embeddable as a meet-semilattice of the subgroup lattice, then there is an embedding with the bottom subgroup normal.

      Actually, I think that the best way to start would be to make a more systematic search for a counterexample than I did. (I simply couldn’t think of one.)

  2. I have no idea if it is of any help or interest but, whilst the work of Saxl and Whiston (rightly) gets much attention in any discussion of independent generating sets, some more recent and much-overlooked work on independent generating sets in classical groups in dimension three was done by Phil Keen in his PhD thesis.

    Phil left academia and never published any part of his thesis, which explains the obscurity of the results.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.