For a character \(\chi \), regard the vector \(v_\chi = (\chi (g))_{g \in G}\). The \(g\)-entry of \(Av_\chi \) is \(\sum _{s \in S \cup S^{-1}} \chi (gs) = \chi (g)\sum _{s \in S\cup S^{-1}} \chi (s)\), since \(\chi \) is a homomorphism. Hence \(v_\chi \) is an eigenvector with eigenvalue \(\sum _{s \in S \cup S^{-1}}\chi (s)\). The \(|G|\) characters give an orthogonal basis of \(\mathbb {C}^{G}\), so these are all the eigenvalues. (This is the standard fact recorded e.g. in Lovász’s problem book.)

The Hamming balls of radius \(\lfloor (\delta l/2 - 1)/2 \rfloor \ge \delta l/4 - 1\) centred at the \(2^{m}\) codewords are pairwise disjoint, since the minimum distance exceeds twice that radius. Each ball contains \(\sum _{j \le \text{radius}} \binom {l}{j}\) words of \(\mathbb {Z}_2^{l}\), and the disjoint union has at most \(2^{l}\) words. Hence \(\sum _{j {\lt} \delta l/4}\binom {l}{j}2^{m} {\lt} 2^{l}\).

By Lemma 24 the eigenvalues are the character sums \(\sum _{s \in S\cup S^{-1}}\chi (s)\). For \(G = \mathbb {Z}_2^{m}\), form the \(m \times |S|\) binary matrix \(B = (b_{ij})\) whose columns are the elements of \(S\). Put \(l = |S|\) and let \(U \subseteq \mathbb {Z}_2^{l}\) be the subspace spanned by the rows of \(B\). For \(u \in U\) let \(e(u)\) be the number of \(0\)-entries minus the number of \(1\)-entries of \(u\). Then \(\{ e(u) : u \in U\} \) is exactly the set of eigenvalues. Therefore \(|\mu _{1}| {\lt} (1-\delta )l\) iff the Hamming weight of every nonzero codeword \(u\) lies in \([\delta l/2,\ l - \delta l/2]\); in particular the code generated by the rows of \(B\) has minimum distance at least \(\delta l/2\). By the sphere-packing bound (Lemma 25), \(\sum _{j {\lt} \delta l/4}\binom {l}{j}2^{m} {\lt} 2^{l}\). Taking logarithms and using the entropy estimate \(\sum _{j{\lt}\delta l/4}\binom {l}{j} \le 2^{H(\delta /4)l}\) gives \(m \le (1 - H(\delta /4))l = (1 - \Omega (\delta \log (1/\delta )))l\), i.e. \(l \ge (1 + \Omega (\delta \log (1/\delta )))m\).

Here \(\chi (\sigma + \sigma ^{-1})\) abbreviates \(\chi (\sigma ) + \chi (\sigma ^{-1}) = 2\, \mathrm{Re}\, \chi (\sigma )\). As \(\chi \) is nontrivial, its values are roots of unity whose real parts average to \(0\) over \(\sigma \). The constant \(1.8\) is not optimal; one only needs an absolute constant strictly smaller than \(2\). (If \(\sigma \) has order \(2\) then \(\sigma = \sigma ^{-1}\) and \(\chi (\sigma ) \in \{ -1, 1\} \), so \(\chi (\sigma + \sigma ^{-1}) = 2\chi (\sigma ) \in \{ -2, 2\} \) is handled separately, still leaving each tail probability at most \(1/2\).) A direct check on each cyclic summand (Definition 6) gives the two tail bounds.

Write \(A = \mathbb {Z}_{p_1}\oplus \dots \oplus \mathbb {Z}_{p_k}\) (Definition 6). Fix a nontrivial character \(\chi \). By Lemma 27, for a random \(\sigma \) both \(\operatorname {Pr}(\chi (\sigma +\sigma ^{-1}) \ge 1.8) \le 1/2\) and \(\operatorname {Pr}(\chi (\sigma +\sigma ^{-1}) \le -1.8) \le 1/2\). The eigenvalue attached to \(\chi \) is \(\sum _{s \in S \cup S^{-1}}\chi (s)\) (Lemma 24), a sum of \((1+\varepsilon )\log _2 n\) independent contributions. By a Chernoff-type count, for an absolute constant \(c\),

There are \(n - 1\) nontrivial characters, so by the union bound the probability that some normalized eigenvalue exceeds \(1 - \delta \) in absolute value is at most

which tends to \(0\) provided \(\varepsilon \ge c'\delta \log (1/\delta )\) for an appropriate \(c' = c'(c)\). This completes the proof.

Put \(|S| = d\) and let \(D\) be the diameter of \(X(A,S)\). Since \(A\) is abelian, every element of \(A\) is a product \(s_1^{a_1} s_2^{a_2}\cdots s_d^{a_d}\) with \(S = \{ s_1,\dots ,s_d\} \), each \(a_i\) an integer and \(\sum _{i=1}^{d}|a_i| \le D\). The number of such products is at most \(2^{d}\binom {D+d}{d}\): there are at most \(\binom {D+d}{d}\) ways to choose the absolute values \(|a_i|\) with \(\sum |a_i| \le D\), and at most \(2^{d}\) sign assignments. Hence

If \(X(A,S)\) is a \(\delta \)-expander then its diameter satisfies \(D \le c'\log _2 n\) for some \(c' = c'(\delta )\). Combined with (6) this forces \(d \ge c\log _2 n\) for an appropriate \(c = c(c')\).

If \(G\) is a group, \(S \subseteq G\) and \(H\) is a factor (quotient) of \(G\), then the diameter of the Cayley graph of \(H\) with respect to the image set \(S'\) is at most that of \(X(G,S)\). Thus if \(G\) has an abelian factor of order \(q\), the bound (6) of Proposition 29 applied to that factor gives \(2^{d}\binom {D+d}{d} \ge q\) with \(d = |S|\). Hence if \(X(G,S)\) is a \(\delta \)-expander and \(q \ge |G|^{\epsilon }\) for some fixed \(\epsilon {\gt} 0\), then \(|S| \ge c(\delta ,\epsilon )\log |G|\). For \(G_q = \mathrm{GL}(n,q)\) the quotient \(\mathrm{GL}(n,q)/\mathrm{SL}(n,q) \cong \mathbb {Z}_{q-1}\) is an abelian factor of order \(q - 1 = |G_q|^{\Omega (1)}\) (for fixed \(n\)), so the claim follows.

By Lemma 24 the eigenvalues of \(H\) are the numbers \(e(u) = \# \{ 0\text{-entries}\} - \# \{ 1\text{-entries}\} \) of the codewords \(u\) of the row code, which equals \(l - 2\, \operatorname {wt}(u)\). Hence \(|e(u)| \le \varepsilon l\) iff \(\operatorname {wt}(u) \in [\tfrac {1-\varepsilon }{2}l, \tfrac {1+\varepsilon }{2}l]\). The second largest \(|e(u)|\) over nonzero \(u\) is \(\mu _{1}[H]\), giving the stated equivalence with Definition 31.

Let \(n\) be the number of vertices. Suppose \(l \ge 2m\) and count the closed walks of length \(2m\) in \(X(G,S)\). Their number is at least \(n\) times the number of words of length \(2m\) made of a single appearance of \(x_i\) and a single appearance of \(x_i^{-1}\) for \(m\) distinct members \(x_i\) of \(S\):

where \(\frac{(2m)!}{2^{m}m!}\) counts the ways to split a length-\(2m\) sequence into \(m\) pairs (each pair the occurrence of some \(x_i\) and \(x_i^{-1}\)) and \(l(l-1)\cdots (l-m+1)\) lower-bounds the choices of the elements \(x_i\). The number of closed walks equals \(\operatorname {Tr}(A^{2m}) = \sum _i \lambda _i^{2m} \le \lambda _0^{2m} + (n-1)\mu _{1}^{2m}\) with \(\lambda _0 = 2l\) (the degree, counting \(S \cup S^{-1}\)). Hence

Taking \(2m \sim \log n / \log 2l\) (which is at most \(l\) provided \(l \ge c\log n/\log \log n\)) yields \(|\mu _{1}| \ge \Omega (\sqrt{l}\, \sqrt{\log n / \log l})\).