# Diameter of Cayley graphs of finite simple groups

Babai, Kantor and Lubotzky proved in 1989 the following theorem (Sciencedirect link to article).

THEOREM 1.1. There is a constant $$C$$ such that every nonabelian finite simple group $$G$$ has a set $$S$$ of at most 7 generators for which the diameter of $$\mathrm{Cay}(G,S)$$ is at most $$C\log|G|$$.

Then they remark that

"A crude estimate for $$C$$ is $$10^{10}$$, but we will not include the bookkeeping required to estimate $$C$$."

This is my question.

"Is there a finite simple group $$G$$ for which there exists a generating set $$S$$ which satisfies the conditions in the above theorem for some reasonably small $$C$$ (comparing to the order of $$G$$)?"

• How about $A_5$? – user6976 Sep 8 '19 at 8:33
• Wouldn't a very large simple group also do the trick, since then $C$ would be small with respect to the order of $G$? – verret Sep 8 '19 at 13:15

There are two examples, $$\mathrm{Alt}_n$$ and $$\mathrm{PSL}_2(q)$$, in this paper (p.861).
For $$\mathrm{Alt}_n$$, the authors used 3 generators and achieved diameter at most $$(1+o(1))4n\log n$$.
For $$\mathrm{PSL}_2(q)$$, an upper bound is $$12\log_4(q)$$ (Every integer in $$\{0 .. q\}$$ can be represented by $$(...(a_m·4+a_{m-1})4+...)4+a_0$$, where $$m < \log_4(q)+1$$, and $$a_k\in\{-1,0,1,2\}$$ for $$k\in\{0..m\}$$. Representing each $$a_k$$ costs at most $$2$$ generators, and multiplying by $$4$$ costs $$2$$ generators. There are $$3$$ numbers need to be represented, as $$\mathrm{PSL}_2(q)$$ has $$3$$ degrees of freedom).
The bound can be improved to $$12\log_5(q)$$ if $$q$$ is a prime of which $$5$$ is a quadratic residue: just replace "multiplying by $$4$$" by "multiplying by $$5$$".
I believe there are much better bounds if we exploit the full power of $$7$$ generators.
• Just to have the same "scale", in $G_n=\mathrm{Alt}_n$ one has $4n\log(n)\sim 4\log(|G_n|)$, and in $H_n=\mathrm{PSL}_2(q)$, $12\log_4(q)\sim (4/\log(4))\log(|H_n|)$. – YCor Sep 8 '19 at 17:48