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$)?"

  • 2
    $\begingroup$ How about $A_5$? $\endgroup$ – user6976 Sep 8 '19 at 8:33
  • 2
    $\begingroup$ Wouldn't a very large simple group also do the trick, since then $C$ would be small with respect to the order of $G$? $\endgroup$ – 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.

| cite | improve this answer | |
  • 1
    $\begingroup$ 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|)$. $\endgroup$ – YCor Sep 8 '19 at 17:48
  • $\begingroup$ Thanks so much for your helps and specially for the above very useful examples $\endgroup$ – khers Sep 8 '19 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.