The little theorem yesterday has inspired me to bring to light something I wrote a few years ago. Every mathematician has papers that never got published; it seemed interesting to you but you were unable to persuade anyone else. This is one of those. I will summarise it here, with a few comments; the original paper is still available here, and has all the proofs, if you are interested …
Introduction and history
The game is to measure the “size” or “complexity” of a finite group by a single number. There are zillions of ways of doing this, but the purpose of the paper was to discuss several that should be better known, and relationships among them. They are interesting because they arise in different places, because the connections are a bit unexpected, and there are some nice theorems (including Julius Whiston’s) about them. And there is a small but nagging open problem buried in here.
I start with a remark. Suppose that we have some function f defined on finite groups, taking natural number values – think of it as a measure of the group in some sense. Then we can define a new, and often better, function f*, by the rule that f*(G) is the maximum value of f(H) over all subgroups H of G. Then f* has the good property that it is monotone, that is, if G_{1}≤G_{2}, then f*(G_{1})≤f*(G_{2}). In particular, if f is itself monotone, then f=f*.
For example, let d(G) is the minimum number of generators of G, then d(S_{n})=2, which does not really reflect the complication of symmetric groups. Laszlo Babai proposed the study of d*(S_{n}) in connection with the complexity of graph isomorphism, and gave an upper bound of 2n–2 for it. The correct value is [n/2] for n≥4, where the square brackets denote rounding down, as was shown by Annabel McIver and Peter Neumann.
An open problem about this result is whether there is an efficient algorithm for finding a generating set of at most this size, given an arbitrary set of generators of a subgroup. A weaker bound n–1 was proved by Mark Jerrum who gave a “polynomial delay” algorithm for it; that is, if the permutations are given one at a time, then a polynomial amount of computation at each step finds a set of size at most n–1 generating the same subgroup as all the permutations so far.
Another interesting measure is l(G), the length of the longest chain of subgroups of G. This function is monotone, and in fact is additive over group extensions, which means that the length of G is the sum of the lengths of its composition factors. So to determine it for all groups, it is enough to calculate it for simple groups.
I, and independently Ron Solomon and Alex Turull, calculated the length of the symmetric groups; we joined forces to publish this. (Historically this is interesting because Babai had observed that d*(G)≤l(G), and had actually bounded l(S_{n}) by 2n–2.) The exact value is given by the surprising formula
l(S_{n}) = [(3n-1)/2]–b(n),
where b(n) is the number of 1s in the base-2 expansion of n.
Finally for this section, the parameter μ(G) is defined as the size of the largest independent generating set for G, where a set is independent if none of its members lies in the subgroup generated by all the others. Then μ*(G) is simply the size of the largest independent set in G. These parameters are of great significance in the behaviour of random walks on G in the work of Diaconis and Saloff-Coste. Julius Whiston showed that
μ(S_{n}) = μ*(S_{n}) = n–1.
He notes that there are groups G with μ(G) not equal to μ*(G).
Measures defined by bases
Let G be a permutation group on a set X. A base for G is a sequence of points of X whose pointwise stabiliser is the identity. (Treating a base as a sequence rather than a set fits with the use of bases in computational group theory, where the elements of a base are chosen in order.) A base is called irredundant if no point is fixed by the pointwise stabiliser of its predecessors; it is minimal if no point is fixed by the pointwise stabiliser of the other points in the sequence.
It is computationally a simple matter to choose an irredundant base; simply choose each base point to be a point moved by the stabiliser of the points previously chosen. It is less straightforward to choose a minimal base. Note that a base is minimal if and only if every re-ordering of it is irredundant.
Now, given a finite group G, we define three numbers b_{1}(G), b_{2}(G), b_{3}(G), as follows. In each case, the maximum is taken over all permutation representations of G (not necessarily faithful or transitive).
- b_{1}(G) is the maximum, over all representations, of the maximum size of an irredundant base;
- b_{2}(G), is the maximum, over all representations, of the maximum size of a minimal base;
- b_{3}(G) is the maximum, over all representations, of the minimum base size.
Clearly we have:
b_{1}(G) ≥ b_{2}(G) ≥ b_{3}(G).
These inequalities can be strict; for the group G=PSL(2,7) (the simple group of order 168), we have b_{1}(G)=5, b_{2}(G)=4, b_{3}(G)=3.
How do these relate to what we have already seen? First, we have b_{1}(G)=l(G).
I think that perhaps b_{2}(G)=μ*(G). Here is what I can prove. Given two subgroups of a group, their meet is their intersection, and their join is the subgroup they generate. With these operations, the set of subgroups forms a lattice. Now a meet-semilattice of a lattice is a subset containing the top element and closed under meet; a join-semilattice is a subset containing the bottom element and closed under join. The Boolean lattice B(n) is the lattice of all subsets of an n-element set.
Now we have:
- There is a meet-semilattice of the subgroup lattice of G isomorphic to B(n) if and only if there is a join-semilattice of the subgroup lattice of G isomorphic to B(n) [but these conditions do not imply that there is a lattice isomorphic to B(n)]
- The largest n for which B(n) is embeddable as a join-semilattice of the subgroup lattice of G is μ*(G).
- The largest n for which B(n) is embeddable as a meet-semilattice of the subgroup lattice of G so that the minimal element is a normal subgroup is b_{2}(G).
Clearly, if it were not for the clause in bold in the last statement, these three facts would establish that b_{2}(G)=μ*(G). As it stands, they show that b_{2}(G)≤μ*(G).
It would be pleasant if there were some relationship between b_{3}(G) and d*(G); but this is not the case.
Now for the symmetric group S_{n}, we have
n–1≤b_{3}(S_{n})≤b_{2}(S_{n})≤μ*(S_{n})=n–1,
where the first inequality holds because any base in the “natural” representation has size n–1, and the last equality is Whiston’s Theorem. So equality holds throughout.
You might be interested in this discussion over at the Secret Bloggins Seminar http://sbseminar.wordpress.com/2008/03/19/sfpa-how-complicated-are-groups/
Pingback: The symmetric group, 6 « Peter Cameron's Blog
Pingback: The symmetric group, 8 « Peter Cameron's Blog
Pingback: hasse diagrams; balancing acts; thurlow levels; embedding; turing bombe | Peter's ruminations