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.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

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 )

Google+ photo

You are commenting using your Google+ 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