# Girth, words and diameter

Martin W. Liebeck  M.W. Liebeck, Department of Mathematics, Imperial College,
London SW7 2BZ, UK<EMAIL_ADDRESS>and  Aner Shalev  A. Shalev,
Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel
<EMAIL_ADDRESS>
###### Abstract.

We study the girth of Cayley graphs of finite classical groups $G$ on random
sets of generators. Our main tool is an essentially best possible bound we
obtain on the probability that a given word $w$ takes the value 1 when
evaluated in $G$ in terms of the length of $w$, which has additional
applications. We also study the girth of random directed Cayley graphs of
symmetric groups, and the relation between the girth and the diameter of
random Cayley graphs of finite simple groups.

###### 2010 Mathematics Subject Classification:

Primary 20D06; Secondary 20P05, 05C80, 05C12

We are grateful to Sean Eberhard for some enlightening comments. The second
author acknowledges the support of ISF grant 686/17, BSF grant 2016072 and the
Vinik chair of mathematics which he holds.

##  1\. Introduction

The girth of a graph (resp. directed graph) is the minimal length of a cycle
(resp. directed cycle) in the graph. The girth of finite $k$-regular graphs
has been studied extensively, with a particular focus on graphs of large girth
– see for example [8], [18]. Note the trivial upper bound of
$2\log_{k-1}{v}+1$ for the girth, where $v$ is the number of vertices and
$k>2$.

In [9] the girth of random Cayley graphs of various families of groups was
studied, and large girth results were established. For a finite group $G$ and
a sequence $S$ of elements $g_{1},\ldots,g_{k}$ of $G$, let $\Gamma(G,S)$
(resp. $\Gamma^{*}(G,S)$) denote the associated undirected (resp. directed)
Cayley graph. Corollary 2 of [9] asserts that for finite simple groups $G$,
the girth of $\Gamma(G,S)$ for $k$ random generators tends to $\infty$ almost
surely as $|G|\rightarrow\infty$. Also [9, Thm. 4] shows that for groups $G$
of Lie type of bounded rank, the girth is $\Omega(\log|G|)$, while [9, Thm. 3]
asserts that for $G=S_{n}$, the girth is at least $\Omega((\log|G|)^{1/2})$
almost surely. An error in the proof of the latter result was recently pointed
out in [7], and a slightly weaker bound of the form $\Omega(n^{1/3})$ was
obtained.

The random girth of classical groups $G$ of unbounded rank has apparently
remained unexplored. Denote by $Cl_{n}(q)$ a simple classical group over
$\mathbb{F}_{q}$ with natural module of dimension $n$. Our first result shows
in particular that if the underlying field $\mathbb{F}_{q}$ has bounded size,
then the random girth of such groups is at least $\Omega((\log|G|)^{1/2})$.

######  Theorem 1.

There exists an absolute constant $N$, and for each integer $k\geq 2$ and
prime power $q$ a positive real number $b=b(q,k)$ with the following property.
Let $G=Cl_{n}(q)$ with $n\geq N$, and let $S$ be a sequence of $k$
independently chosen random elements of $G$. Then as $|G|\rightarrow\infty$,
the girth of the Cayley graph $\Gamma(G,S)$ exceeds $b\sqrt{\log|G|}$ almost
surely.

In particular, for bounded $q$ and $k$ the girth is almost surely
$\Omega(\sqrt{\log|G|})$. Also the proof shows that the girth exceeds $Bn$ for
some positive constant $B=B(k)$; in fact we can take
$B=\frac{1}{7(1+2\log_{2}{(2k-1)})}$.

Our next result concerns the girth of directed Cayley graphs of symmetric
groups (namely, the minimal length of a directed cycle in the graph).

######  Theorem 2.

Fix an integer $k\geq 2$, and let $S$ be a sequence of $k$ independently
chosen random elements of $G=S_{n}$. Then the girth of $\Gamma^{*}(G,S)$
almost surely exceeds $c\sqrt{\log_{k}|G|}$, where $c$ is a positive absolute
constant.

Thus the girth of a random directed Cayley graph of $S_{n}$ is at least
$\Omega(\sqrt{n\log n})$.

The diameter of Cayley graphs of finite simple groups (with explicit or with
random generators) has also attracted considerable attention – see for
instance [2], [4], [19], [10], [11], [5], [3] and the references therein.
Clearly if $d$ and $g$ are the diameter and girth respectively, then a trivial
lower bound for $d$ is $\lfloor\frac{g}{2}\rfloor$, and there is interest in
finding families of graphs for which $d$ is bounded in terms of $g$. According
to [1], a family of graphs is $dg$-bounded if the ratio $\frac{d}{g}$ is
bounded. The focus is on graphs of large girth, meaning that the girth is
$\Omega(\log|G|)$, where $G$ ranges over the ambient family of groups. The
main result of [1] is a construction of certain Cayley graphs of $SL_{n}(p)$
with respect to two explicit generators, where $n$ is fixed, which are of
large girth and $dg$-bounded.

It follows from part (i) of the next result that such families of Cayley
graphs exist for all groups of Lie type of bounded rank. Parts (ii) and (iii)
bound the diameter in terms of (nonlinear) functions of the girth almost
surely for other families of finite simple groups.

######  Proposition 3.

Fix $k\in\mathbb{N}$. Let $G$ be a finite simple group and let $S$ be a
sequence of $k$ independently chosen random elements of $G$. Let $d,g$ be the
diameter and girth of $\Gamma(G,S)$ respectively. Suppose
$|G|\rightarrow\infty$.

  * (i)

If $G$ is of Lie type of bounded rank, then $\Gamma(G,S)$ has large girth and
is $dg$-bounded (i.e. $d=O(g)$) almost surely.

  * (ii)

If $G=Alt_{n}$, then almost surely $d\leq g^{6}(\log g)^{c}$ for some absolute
constant $c$.

  * (iii)

If $G=Cl_{n}(q)$ is a classical group of dimension $n$ with $q$ bounded, then
$d\leq C^{g(\log g)^{3}}$ almost surely, for some constant $C=C(k)>1$.

The proof of part (i) is rather short, modulo the deep results in [4, 19]
(which are also used in [1]). Parts (ii) and (iii) require results from [11]
and [3] respectively.

The bound in part (iii) above seems far from best possible, and it would be
nice to obtain a polynomial bound in this case too. Such a bound would follow
from Theorem 1, together with Babai’s conjecture (so far unproved) that the
diameter of any connected Cayley graph of a (nonabelian) finite simple group
$G$ is at most $(\log{|G|})^{c}$, for some absolute constant $c$ (see [2,
1.7]). In fact, a polynomial bound in part (iii) of Proposition 3 would
already follow if the latter bound on the diameter holds almost surely for
random Cayley graphs of classical groups.

The proofs of Theorems 1 and 2 rely on the study of the probability $P_{G}(w)$
that a word $w=w(x_{1},\ldots,x_{k})$ in the free group $F_{k}$ takes the
value 1 when we substitute a sequence $S$ of $k$ independently chosen random
elements of $G$ for $x_{1},\ldots,x_{k}$. It is an elementary observation that

${\textbf{P}}(\hbox{girth}(\Gamma(G,S))\leq L)\leq\sum_{|w|\leq L}P_{G}(w)$

where $|w|$ denotes the length of $w$ (see [9, Sec. 2]). The study of
$P_{G}(w)$ is an important part of the theory of word maps, with a particular
focus on finite simple groups $G$. In [6, Thm. 3] it is shown that if $w\neq
1$ then $P_{G}(w)\rightarrow 0$ as $|G|\rightarrow\infty$; and [12, Thm. 1.1]
shows that for every $w\neq 1$ there exist $\delta=\delta(w)>0$ and $N=N(w)$
such that $P_{G}(w)\leq|G|^{-\delta}$ provided $|G|>N$. The next result gives
an explicit and close to best possible value for the constant $\delta(w)$ in
terms of the length of $w$.

######  Theorem 4.

For any $\epsilon>0$, there exists $c=c(\epsilon)>0$ with the following
property. Let $\ell\in\mathbb{N}$ and let $G=Cl_{n}(q)$ be a classical group
of dimension $n\geq c\ell$. Then, for any reduced word $w\in F_{k}$ of length
$\ell$, we have

$P_{G}(w)\leq|G|^{-\frac{1}{(2+\epsilon)\ell}}.$

In fact the proof gives $c(\epsilon)=4\,(1+\frac{2}{\epsilon})$ for
$G=SL_{n}(q)$, and $c(\epsilon)=7\,(1+\frac{2}{\epsilon})$ for the other
classical groups. For more detailed bounds on $P_{G}(w)$ see Section 2.
Theorem 4 improves a bound of the form
$P_{G}(w)\leq|G|^{-\frac{1}{1800\ell^{2}}+o(1)}$ obtained in the proof of [12,
Thm. 1.1].

As claimed above, Theorem 4 is close to being best possible; indeed, [16, Thm.
1.4] shows that, for a fixed power word $w=x_{1}^{\ell}$ and $G=Cl_{n}(q)$
with $n\rightarrow\infty$ we have $P_{w}(G)=|G|^{-\frac{1}{\ell}+o(1)}$. It
seems an interesting and challenging problem to improve the upper bound in
Theorem 4 to $P_{G}(w)\leq|G|^{-\frac{1}{(1+\epsilon)\ell}}$.

The key to the proof of Theorem 2 is the following result, which is of some
independent interest. Recall that a word $w\in F_{k}$ is said to be positive
(or a semigroup word) if it does not involve inverses of the generators of
$F_{k}$.

######  Proposition 5.

Let $w\in F_{k}$ be a positive word of length $\ell$. Then for all
$n\in\mathbb{N}$, we have

$P_{S_{n}}(w)\leq\left(\frac{2\ell}{n}\right)^{\lfloor\frac{n}{2\ell}\rfloor}\leq(n!)^{-\frac{1}{2\ell}+o_{n}(1)}.$

In fact the inaccurate proof of the above bound for $P_{S_{n}}(w)$ on p.106 of
[9] becomes accurate when $w$ is assumed to be a positive word. Proposition 5
is essentially best possible; indeed for $w=x_{1}^{\ell}$ we have
$P_{S_{n}}(w)=(n!)^{-\frac{1}{\ell}+o_{n}(1)}$ (see for instance [16, 2.17]).

We conclude the introduction with applications of the two results above to
representation varieties and subgroup growth (cf. [12, 1.3, 1.4]).

######  Corollary 6.

Let $\Gamma$ be a non-free group with $k$ generators, and let $\ell$ be the
minimal length of a non-trivial relation (in these generators) which holds in
$\Gamma$. Then for every $\epsilon>0$ there exists $N=N(\ell,\epsilon)$ such
that the following hold for all $n\geq N$ and for any algebraically closed
field $F$:

  * (i)

$\dim{\rm Hom}(\Gamma,GL_{n}(F))\leq(k-\frac{1}{(2+\epsilon)\ell})n^{2}$;

  * (ii)

$\dim{\rm Hom}(\Gamma,G)\leq(k-\frac{1}{(2+\epsilon)\ell})\dim G$, where $G$
is a simple algebraic group over $F$ of dimension $n$.

Recall that $a_{n}(\Gamma)$ denotes the number of index $n$ subgroups of
$\Gamma$.

######  Corollary 7.

Let $\Gamma$ be a group with $k$ generators which satisfy some non-trivial
positive relation. Let $\ell$ be the minimal length of such a relation. Then
$a_{n}(\Gamma)\leq(n!)^{k-1-\frac{1}{2\ell}+o_{n}(1)}$.

##  2\. Proof of Theorem 4

First we give the proof in the case $G=GL_{n}(q)$. Our method is inspired by
Eberhard’s proof in [7]. Denote by $V=\mathbb{F}_{q}^{n}$ the underlying
vector space. Assume $2\ell<n$.

Let $a_{1},\ldots,a_{k}$ be free generators for $F_{k}$, and let
$w=w_{\ell}\cdots w_{1}$, where each $w_{i}\in\\{a_{1}^{\pm
1},\ldots,a_{k}^{\pm 1}\\}$. Let $g_{1}\ldots,g_{k}$ be a random sequence of
elements of $G$.

Fix $v_{1}\in V\setminus 0$, and define $v_{1}^{0},\ldots v_{1}^{\ell}$ by

$\begin{array}[]{l}v_{1}^{0}=v_{1},\\\
v_{1}^{j}=w_{j}(g_{1},\ldots,g_{k})(v_{1}^{j-1})\;\;(1\leq
j\leq\ell).\end{array}$

Call the sequence $v_{1}^{0},\ldots v_{1}^{\ell}$ the trajectory of $v_{1}$.
Assume $v_{1}^{0},\ldots,v_{1}^{j-1}$ are linearly independent. Then

$v_{1}^{j}\not\in{\rm Sp}\left(\\{v_{1}^{i}\,(i\leq j-1)\,|\,w_{i}=w_{j}\hbox{
or }w_{i+1}=w_{j}^{-1}\\}\right),$ (1)

which excludes at most $q^{j-1}$ possibilities for $v_{1}^{j}$; all other
vectors are equally likely as possibilities for $v_{1}^{j}$, since
$w_{j}(g_{1},\ldots,g_{k})$ is a random element. Hence the conditional
probability

${\textbf{P}}\left(v_{1}^{j}\in{\rm
Sp}(v_{1}^{0},\ldots,v_{1}^{j-1})\,|\,v_{1}^{0},\ldots,v_{1}^{j-1}\right)\leq\frac{q^{j}}{q^{n}-q^{j-1}}.$

It follows that

${\textbf{P}}\left(v_{1}^{0},\ldots,v_{1}^{\ell}\hbox{ lin.
dep.}\right)\leq\sum_{j=1}^{\ell}\frac{q^{j}}{q^{n}-q^{j-1}}\leq\frac{q+q^{2}+\ldots+q^{\ell}}{q^{n}-q^{\ell-1}}<\frac{q}{q-1}\cdot\frac{q^{\ell}}{q^{n}-q^{\ell-1}}.$

Now suppose $v_{1}^{0},\ldots,v_{1}^{\ell}$ are given, and set $V_{1}={\rm
Sp}(v_{1}^{0},\ldots v_{1}^{\ell})$. Pick $v_{2}\not\in V_{1}$, and define the
trajectory of $v_{2}$ to be $v_{2}^{0},\ldots v_{2}^{\ell}$ as above. Assuming
$v_{2}^{0},\ldots v_{2}^{j-1}$ to be linearly independent and also have span
intersecting $V_{1}$ trivially, we have

${\textbf{P}}\left(v_{2}^{j}\in{\rm Sp}(v_{2}^{0},\ldots v_{2}^{j-1}\cup
V_{1})\right)\leq\frac{q^{\ell+j}}{q^{n}-q^{\ell+j-1}},$

and hence, arguing as above, we obtain

${\textbf{P}}\left(v_{2}^{0},\ldots,v_{2}^{\ell}\hbox{ lin.
dep.}\,|\,v_{1}^{0},\ldots,v_{1}^{\ell}\right)\leq\sum_{j=1}^{\ell}\frac{q^{\ell+j}}{q^{n}-q^{\ell+j-1}}<\frac{q}{q-1}\cdot\frac{q^{2\ell}}{q^{n}-q^{2\ell-1}}.$

Repeating this argument $m$ times, where $m\leq\frac{n}{\ell}$ (choosing each
$v_{i}$ ($1\leq i\leq m$) not in the span of the previous trajectories), we
obtain

${\textbf{P}}\left(v_{m}^{0},\ldots,v_{m}^{\ell}\hbox{ lin.
dep.}\,|\,v_{i}^{0},\ldots,v_{i}^{\ell}\hbox{ for
}i<m\right)<\frac{q}{q-1}\cdot\frac{q^{m\ell}}{q^{n}-q^{m\ell-1}}.$

If $w(g_{1},\ldots,g_{k})=1$, then $v_{i}^{\ell}=v_{i}$ for all $i$, and hence

$\begin{array}[]{ll}P_{G}(w)&\leq\prod_{i=1}^{m}{\textbf{P}}\left(v_{i}^{\ell}=v_{i}\,|\,v_{j}^{\ell}=v_{j}\hbox{
for }1\leq j\leq i-1\right)\\\
&<\prod_{i=1}^{m}\frac{q}{q-1}\frac{q^{i\ell}}{q^{n}-q^{i\ell-1}}=(\tfrac{q}{q-1})^{m}\prod_{i=1}^{m}\frac{1}{q^{n-i\ell}-q^{-1}}.\end{array}$

Set $m=\lfloor\frac{n}{\ell}\rfloor$. Define

$a(q)=\prod_{i=1}^{m}\frac{q^{n-i\ell}}{q^{n-i\ell}-q^{-1}}=\prod_{i=1}^{m}\frac{1}{1-q^{-(n-i\ell)-1}}.$

We may and shall assume $\ell\geq 2$, since for $w$ of length $1$ we have
$P_{G}(w)=|G|^{-1}$ for all finite groups $G$. Clearly $a(q)\leq a(2)\leq a$,
where

$a:=\prod_{i=0}^{\infty}\frac{1}{1-2^{-(2i+1)}}=\prod_{i=0}^{\infty}(1+\frac{1}{2^{2i+1}-1})<2.3749,$

where the last inequality is easily verified by computing the sum for $i\leq
6$ and bounding its tail. It follows that

$P_{G}(w)\leq
a\cdot(\tfrac{q}{q-1})^{m}\cdot\prod_{i=1}^{m}q^{-n+i\ell}=a\cdot(\tfrac{q}{q-1})^{m}\cdot
q^{-mn+\frac{1}{2}\ell m(m+1)}.$

Now $\frac{n}{\ell}-1<m\leq\frac{n}{\ell}$. We conclude that

$P_{G}(w)\leq a\cdot(\tfrac{q}{q-1})^{\frac{n}{\ell}}\cdot
q^{-n(\frac{n}{\ell}-1)+\frac{1}{2}n(\frac{n}{\ell}+1)}=a\cdot(\tfrac{q}{q-1})^{\frac{n}{\ell}}\cdot
q^{-\frac{n^{2}}{2\ell}+\frac{3n}{2}}.$

For $\ell\geq 3$, this is less than $q^{-\frac{n^{2}}{(2+\epsilon)\ell}}$,
hence less than $|G|^{-\frac{1}{(2+\epsilon)\ell}}$, provided $n\geq
c(\epsilon)\ell$, where $c(\epsilon)=4\,(1+\frac{2}{\epsilon})$. And for
$\ell=2$, the same assertion holds using the upper bound for $i_{2}(G)$, the
number of involutions in $G$, given by [13, 1.3] (noting that for the word
$w=x^{2}$, $P_{G}(w)=\frac{i_{2}(G)+1}{|G|}$).

This completes the proof of Theorem 4 for $G=GL_{n}(q)$, and the same argument
replacing $G$ by $SL_{n}(q)$ gives the result for $SL_{n}(q)$.

Now let $G=Cl_{n}(q)$ be a classical group with natural module
$V=(\mathbb{F}_{Q})^{n}$, where $Q=q^{2}$ if $G$ is unitary and $Q=q$
otherwise. Let $(\,,\,)$ be the associated bilinear or sesquilinear form on
$V$ preserved by $G$, and when $G$ is orthogonal, let $R$ be the associated
quadratic form. Assume $n>4\ell$.

The proof is rather similar to the previous proof for $GL_{n}$. Let
$a_{1},\ldots,a_{k}$ be free generators for $F_{k}$, and let $w=w_{\ell}\cdots
w_{1}$, where each $w_{i}\in\\{a_{1}^{\pm 1},\ldots,a_{k}^{\pm 1}\\}$. Let
$g_{1}\ldots,g_{k}$ be a random sequence of elements of $G$. Let $v_{1}\in V$
be a nonzero singular vector, and define its trajectory $v_{1}^{0},\ldots
v_{1}^{\ell}$ as before. Assume that $v_{1}^{0},\ldots,v_{1}^{j-1}$ are
linearly independent. Again, (1) holds, excluding at most $q^{j-1}$
possibilities for $v_{1}^{j}$. Moreover the values of $(v_{1}^{j},v_{1}^{i})$
are specified for the vectors $v_{1}^{i}$ for which $w_{i}=w_{j}$ or
$w_{i+1}=w_{j}^{-1}$. Hence there are at least $Q^{n-j}-Q^{j-1}$ possibilities
for $v_{1}^{j}$, and so

${\textbf{P}}\left(v_{1}^{j}\in{\rm
Sp}(v_{1}^{0},\ldots,v_{1}^{j-1})\,|\,v_{1}^{0},\ldots,v_{1}^{j-1}\right)\leq\frac{Q^{j}}{Q^{n-j}-Q^{j-1}}.$

It follows that

${\textbf{P}}\left(v_{1}^{0},\ldots,v_{1}^{\ell}\hbox{ lin.
dep.}\right)\leq\sum_{j=1}^{\ell}\frac{Q^{j}}{Q^{n-j}-Q^{j-1}}\leq\frac{Q}{Q-1}\cdot\frac{Q^{\ell}}{Q^{n-\ell}-Q^{\ell-1}}.$

Now as before define further trajectories $v_{i}^{0},\ldots,v_{i}^{\ell}$ for
$1\leq i\leq m$, where $m<\frac{n}{2\ell}$. Arguing as above we obtain

${\textbf{P}}\left(v_{i}^{0},\ldots,v_{i}^{\ell}\hbox{ lin.
dep.}\,|\,v_{j}^{0},\ldots,v_{j}^{\ell}\hbox{ for
}j<i\right)\leq\frac{Q}{Q-1}\cdot\frac{Q^{i\ell}}{Q^{n-i\ell}-Q^{i\ell-1}}.$

If $w(g_{1},\ldots,g_{k})=1$, then $v_{i}^{\ell}=v_{i}$ for all $i$, and hence

$\begin{array}[]{ll}P_{G}(w)&\leq\prod_{i=1}^{m}{\textbf{P}}\left(v_{i}^{\ell}=v_{i}\,|\,v_{j}^{\ell}=v_{j}\hbox{
for }1\leq j\leq i-1\right)\\\
&\leq(\tfrac{Q}{Q-1})^{m}\prod_{1}^{m}\frac{Q^{i\ell}}{Q^{n-i\ell}-Q^{i\ell-1}}=(\tfrac{Q}{Q-1})^{m}\prod_{1}^{m}\frac{1}{Q^{n-2i\ell}-Q^{-1}}.\end{array}$

Set $m=\lfloor\frac{n}{2\ell}\rfloor$. Arguing as above, this leads to

$P_{G}(w)\leq
a\cdot(\tfrac{Q}{Q-1})^{\frac{n}{2\ell}}Q^{-\frac{n^{2}}{4\ell}+\frac{3n}{2}}.$

As before, this gives $P_{G}(w)\leq|G|^{-\frac{1}{(2+\epsilon)\ell}}$ provided
$n\geq 7\,(1+\frac{2}{\epsilon})\ell$.

This completes the proof of Theorem 4.

##  3\. Deduction of Theorem 1

Let $G$ be a finite group and $S$ a sequence of $k$ random elements of $G$
chosen independently. For $\ell\geq 1$, define $P_{G}(\ell)$ to be the maximum
of $P_{G}(w)$ over all words $w\in F_{k}$ of length $|w|=\ell$. Then as in [9,
Sec. 2] by the well-known union bound, for any positive integer $L$ we have

${\textbf{P}}(\hbox{girth}(\Gamma(G,S))\leq L)\leq\sum_{|w|\leq
L}P_{G}(w)=\sum_{\ell=1}^{L}2k(2k-1)^{\ell-1}P_{G}(\ell).$ (2)

Now let $G=Cl_{n}(q)$ and choose $\epsilon$ with $0<\epsilon\leq\log_{2k-1}q$.
Then Theorem 4 gives $P_{G}(l)\leq|G|^{-\frac{1}{(2+\epsilon)\ell}}$ for
$\ell\leq\frac{n}{c}$, where $c=c(\epsilon)=7\,(1+\frac{2}{\epsilon})$. Hence,
taking $L\leq\frac{n}{c}$, the right hand side in (2) is bounded above by

$E:=\frac{k}{k-1}(2k-1)^{n/c}|G|^{-\frac{c}{(2+\epsilon)n}}.$

Since $\frac{c}{2+\epsilon}=\frac{7}{\epsilon}$, we have

$\log_{2k-1}E\leq 1+\frac{n}{c}-\frac{3.5(n-1)}{\epsilon}\log_{2k-1}q,$

and by the choice of $\epsilon$ this tends to 0 as $|G|\rightarrow\infty$.
Hence the girth is at least $\frac{n}{c}$. Fixing $k$ and $\epsilon$, this is
of the order of $b(q)\sqrt{\log|G|}$, where $b(q)=(\log q)^{-\frac{1}{2}}$.
Theorem 1 follows.

##  4\. Proof of Proposition 3

We first prove part (i). Fix $k\geq 2$. Let $G=G(q)$ be a simple group of Lie
type of fixed rank and let $S$ be a sequence of $k$ independently chosen
random elements of $G$. By [14], $S$ generates $G$ almost surely. By [9, Thm.
4], the girth $g$ of $\Gamma(G,S)$ satisfies

$g\geq c_{1}\log|G|$ (3)

almost surely for some positive absolute constant $c_{1}$. Let $T$ be the
symmetric set consisting of the elements of $S$ and their inverses. Write
$h=\lfloor\frac{g-1}{2}\rfloor$. Since $g$ is the girth, we have
$|T^{h}|\geq(2k-1)^{h}$ almost surely. Let $A=T^{h}$. Then it follows from (3)
that $|A|\geq|G|^{\delta}$ for some positive absolute constant $\delta$ almost
surely.

By the Product Theorem [4, 19], there is a positive absolute constant
$\epsilon$ such that for any symmetric generating subset $B$ of $G$, either
$B^{3}=G$ or $|B^{3}|\geq|B|^{1+\epsilon}$. It follows inductively that if $m$
is chosen minimally such that $\delta(1+\epsilon)^{m}\geq 1$, then we have

$A^{3^{m}}=G.$

Note that $m$ is an absolute constant. It follows that

$d=\hbox{diam}(\Gamma(G,S))\leq 3^{m}\cdot h\leq c_{2}\cdot g$

almost surely, where $c_{2}=3^{m}/2$, as required.

Now we prove part (ii) of Proposition 3. Let $G=Alt_{n}$ and let $S$ be a
sequence of $k$ independently chosen random elements of $G$. It follows from
[7, Thm. 1.1] that $g=\hbox{girth}(\Gamma(G,S))>c_{1}n^{1/3}$ almost surely,
where $c_{1}$ is a positive absolute constant. Also by [11, Thm. 1.1],
$d=\hbox{diam}(\Gamma(G,S))<c_{2}n^{2}(\log n)^{c_{3}}$. The conclusion
follows.

The proof of part (iii) relies on [3, Thm. 1.4], showing that, for
$G=Cl_{n}(q)$, the diameter $d$ of any connected Cayley graph of $G$ satisfies

$d\leq q^{O(n(\log n+\log q)^{3})}.$

Combining this with the fact that the girth $g$ of $\Gamma(G,S)$ satisfies
$g\geq B(k)n$ almost surely (see the remark following Theorem 1) we easily
derive part (iii).

##  5\. Proof of Results 2, 5, 6 and 7

The proof of [9, Thm. 3] given on p.106 was shown to contain an error by
Eberhard [7]. However, the error pointed out in [7, Sec. 3] only pertains if
there is a value of $i$ such that both $a_{i}$ and $a_{i}^{-1}$ occur in the
word $w$. Hence, if we restrict to positive words, the inequality displayed as
(6) on p.106 of [9] holds. Proposition 5 is just this bound. Now Theorem 2
follows, just as in [9, p.106].

To prove Corollaries 6 and 7 we may assume that $\Gamma=\langle
a_{1},\ldots,a_{k}:w(a_{1},\cdots,a_{k})=1\rangle$ where $w$ is the relation
(resp. the positive relation) of minimal length $\ell$ (since our group is a
quotient of the group above).

Note that, for an algebraic group $G$, the variety ${\rm Hom}(\Gamma,G)$ can
be identified with the subvariety of $G^{k}$ defined by the equation
$w(g_{1},\ldots,g_{k})=1$. The proof of Corollary 6 now follows using Theorem
4 and Lang-Weil estimates, as in [16, Sec. 7] and [12, Sec. 4].

Finally, to prove Corollary 7 we combine Proposition 5 with the well-known
inequality

$a_{n}(\Gamma)\leq|{\rm Hom}(\Gamma,S_{n})|/(n-1)!=P_{S_{n}}(w)n!^{k-1}\cdot
n,$

which follows from [17, 1.1].

## References

  * [1] G. Arzhantseva and A. Biswas, Large girth graphs with bounded diameter-by-girth ratio, arXiv:1803.09229.
  * [2] L. Babai and A. Seress, On the diameter of permutation groups, European J. Combin. 13 (1992), 231–243.
  * [3] A. Biswas and Y. Yang, A diameter bound for finite simple groups of large rank, J. London Math. Soc. 95 (2017), 455–474.
  * [4] E. Breuillard, B. Green and T. Tao, Approximate subgroups of linear groups, Geom. Funct. Anal. 21 (2011), 774–819.
  * [5] E. Breuillard and M. Tointon, Nil progressions and groups with moderate growth, Adv. Math. 289 (2016), 1008–1055.
  * [6] J.D. Dixon, L. Pyber, A. Seress and A. Shalev, Residual properties of free groups and probabilistic methods, J. Reine Angew. Math. 556 (2003), 159–172.
  * [7] S. Eberhard, The trivial lower bound for the girth of $S_{n}$, arXiv:1706.09972.
  * [8] P. Erdös and H. Sachs, Regulare Graphen gegebener Taillenweite mit minimaler Knotenzahl,Wiss Z Univ Halle-Wittenberg Math-Nat R 12 (1963), 251–258.
  * [9] A. Gamburd, S. Hoory, M. Shahshahani, A. Shalev and B. Virág, On the girth of random Cayley graphs, Random Structures Algorithms 35 (2009), 100–117.
  * [10] H. Helfgott, A. Seress, On the diameter of permutation groups, Ann. of Math. 179 (2014), 611–658.
  * [11] H. Helfgott, A. Seress, and A. Zuk, Random generators of the symmetric group: diameter, mixing time and spectral gap, J. Algebra 421 (2015), 349–368.
  * [12] M. Larsen and A. Shalev, Fibers of word maps and some applications, J. Algebra 354 (2012), 36–48.
  * [13] R. Lawther, M.W. Liebeck and G.M. Seitz, Fixed point ratios in actions of finite exceptional groups of Lie type, Pacific J. Math. 205 (2002), 393–464.
  * [14] M.W. Liebeck and A. Shalev, The probability of generating a finite simple group, Geom. Ded. 56 (1995), 103–113.
  * [15] M. W. Liebeck and A. Shalev, Fuchsian groups, coverings of Riemann surfaces, subgroup growth, random quotients and random walks, J. Algebra 276 (2004), 552–601.
  * [16] M. W. Liebeck and A. Shalev, Fuchsian groups, finite simple groups, and representation varieties, Invent. Math. 159 (2005), 317–367.
  * [17] A. Lubotzky and D. Segal, ‘Subgroup Growth’, Progress in Math. 212, Birkhäuser Verlag, Basel, 2003.
  * [18] G. A. Margulis, Explicit construction of graphs without short cycles and low density codes, Combinatorica 2 (1982), 71–78.
  * [19] L. Pyber and E. Szabó, Growth in finite simple groups of Lie type, J. Amer. Math. Soc. 29 (2016), 95–146.