## Notes of Harald Helfgott’s Cambridge lecture 11-05-2017

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 ${c>0}$ such that for every finite simple nonabelian group ${G}$,

$\displaystyle \begin{array}{rcl} diameter(G)=O(\log^c|G|). \end{array}$

Known for

• Helfgott: ${PSl(2,p)}$, ${PSl(3,p)}$
• Dinai, Varju: ${PSl(2,q)}$
• Pyber-Szabo, Breuillard-Green-Tao: groups of Lie type of bounded rank.

There remains permutation groups.

Theorem 1 (Helfgott-Seress)

$\displaystyle \begin{array}{rcl} diameter(\mathfrak{A}_n)=O(\log^4 n \log\log n). \end{array}$

The same estimate follows for all transitive subgroups of ${\mathfrak{S}_n}$.

1. Product theorems

These are usually more important than diameter bounds that follow from them.

Theorem 2 There exists a polynomial ${c(x)}$ such that for all finite simple groups ${G}$ of Lie type and rank ${r}$, and generating systems ${A}$,

$\displaystyle \begin{array}{rcl} |A^3|\geq |A|^{1+c(r)}. \end{array}$

This fails for ${\mathfrak{A}_n}$ (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 ${\mathfrak{A}_n}$

This provides a simpler proof of Helfgott-Seress’ diameter bound. This is work in progress.

Theorem 3 There exists ${c}$ such that, for all symmetric generating systems ${A}$,

$\displaystyle \begin{array}{rcl} |A^{n^c}|\geq |A|^{1+f(n)}, \end{array}$

where ${f}$ gives a slightly worst diameter bound than Helfgott-Seress.

2.1. Dimensional estimate

Find a special subset (analogue of 1-dimensional variety) ${R\subset G}$ 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 ${\mathfrak{A}_n}$.

Some aspect of probabilistic method is used: outcomes of short random walks.

The key feature of ${\mathfrak{A}_n}$ 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.

3. Moral

The action by conjugation is a important than the translation action. For ${\mathfrak{A}_n}$, action on ${k}$-tuples helps.

4. Questions

Which generating sets maximize diameter? For ${\mathfrak{A}_n}$, random choices give much smaller diameters (${\log}$ instead of a power of ${\log}$). This might be sharp, I do not know.