Generational equivalence

If you are interested in generating sets for finite groups, you may want to read this. I started this work with Colva Roney-Dougal some time ago, and I talked about it in Budapest last summer. Andrea Lucchini was in the audience, got interested, and added many new results, so we recruited him to the team; but it has still taken us rather a long time to finish the paper. It has just gone on the arXiv.

Let us say that two elements of a finite group G are m-equivalent if one can be substituted for the other in any generating set for G without destroying the generating property. The “m” here stands for maximal subgroups, since two elements are m-equivalent if and only if they lie in the same maximal subgroups of G. In particular, the m-equivalence class of the identity is the Frattini subgroup, the set of non-generators. (This way of viewing m-equivalence leads to the best algorithm we know for computing it.)

The number of m-equivalence classes is an interesting invariant of the group G. We computed it for the first few symmetric groups, and this is now sequence A270534 in the On-Line Encyclopedia of Integer Sequences. The asymptotic behaviour of this sequence is an unknown problem, on which we make some comments in the paper.

But m-equivalence can be refined. Let us say that two elements are m-equivalent at level i if one can be substituted for the other in any i-element generating set. These equivalence relations, indexed by i, get finer as i increases. What can we say about their behaviour?

The number of level-i equivalence classes is 1 if i < d(G), the smallest number of generators for G, and is strictly greater than 1 if i = d(G). It is easy to see that, for i = d(G), the identity and all the elements of the generating set are pairwise inequivalent, so the number of equivalence classes jumps from 1 to at least d(G)+1. It might be interesting to find a good lower bound.

Another significant point is the value of i where the equivalence relation reaches its final value; we call this number ψ(G). Now one of the most interesting and surprising questions we have come up with, and not been able to answer, is:

Is it true that ψ(G) ≤ d(G)+1?

We have no counterexamples to this, and it follows from a result of Burness, Liebeck and Shalev that ψ(G) ≤ d(G)+5. If the answer to the above question is “yes”, then the number of equivalance classes takes at most three distinct values for any given group. This would also yield a remarkable dichotomy for finite groups, into those with ψ(G) = d(G), and those with ψ(G) = d(G)+1. Is there a more obvious property distinguishing the two types?

There are also connections with the generating graph. If d(G) ≤ 2, we can form a graph with vertex set G, where two vertices are joined if these two elements generate the group. Our research began from the observation that the automorphism group of the generating graph is huge (for the alternating group A5, it has order 23482733690880). The reason is that any permutation which preserves the level-2 m-equivalence classes is an automorphism of the graph: two vertices in the same class have the same neighbours in the graph. In the paper we define a reduction process to a weighted graph whose automorphism group (at least in the case of almost simple groups) appears to be close to the automorphism group of G; the automorphism group of the full generating graph is the semi-direct product of a direct product of symmetric groups (on the level-2 m-equivalence classes) by the automorphism group of the weighted reduced graph, and the latter is equal to the automorphism group of G in many cases (though by no means all).

The vertex weight here is simply the cardinality of the equivalence class which is shrunk to give that vertex. An interesting question is to find examples where the reduced graph has automorphisms not preserving the weighting: we have a couple of examples, but the phenomenon is rare.

So there are several good problems to tackle here. Would you like to join in?