The diameter of permutation groups
The diameter of the Rubik’s cube graph (it is a Cayley graph) is 20.
Define the diameter of a finite group as the maximal diameter of all its Cayley graphs.
conjecture (Babai 1992). There exists a such that for every finite simple nonabelian group ,
- Helfgott: ,
- Dinai, Varju:
- Pyber-Szabo, Breuillard-Green-Tao: groups of Lie type of bounded rank.
There remains permutation groups.
Theorem 1 (Helfgott-Seress)
The same estimate follows for all transitive subgroups of .
1. Product theorems
These are usually more important than diameter bounds that follow from them.
Theorem 2 There exists a polynomial such that for all finite simple groups of Lie type and rank , and generating systems ,
This fails for (Pyber-Spiga).
Alternative techniques, like algebraic geometry of varieties (Larsen-Pink), or escape from subvarieties (Mozes-Oh) do not apply directly either.
2. A weak product theorem for
This provides a simpler proof of Helfgott-Seress’ diameter bound. This is work in progress.
Theorem 3 There exists such that, for all symmetric generating systems ,
where gives a slightly worst diameter bound than Helfgott-Seress.
2.1. Dimensional estimate
Find a special subset (analogue of 1-dimensional variety) such that for every blob, at least one among boundedly many conjugates has long intersections with the blob.
Special turns out to be: which has no long orbits.
2.2. Prefixes and suffixes
Better than set growing under multiplication, one should think in terms of sets growing under a group action, restricted to subsets.
Also we play with subset analogues of statements in group theory:
- orbit versus stabilizer,
- lifting and reduction from quotients,
- large subgroups of .
Some aspect of probabilistic method is used: outcomes of short random walks.
The key feature of is that it acts on a very small set. This makes it possible to apply work of Babai and of Pyber on 2-transitive actions.
The action by conjugation is a important than the translation action. For , action on -tuples helps.
Which generating sets maximize diameter? For , random choices give much smaller diameters ( instead of a power of ). This might be sharp, I do not know.