<figure><img src="image_1.png" /></figure>

HAL
open science

# Random Schreier graphs of the general linear group over finite fields and expanders

Geoffroy Caillat-Grenier

► To cite this version:

Geoffroy Caillat-Grenier. Random Schreier graphs of the general linear group over finite fields and expanders. 2023. lirmm-04090380

HAL Id: lirmm-04090380

https://hal-lirmm.ccsd.cnrs.fr/lirmm-04090380

Preprint submitted on 17 Oct 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Open licence - etalab
# Random Schreier Graphs as Expanders

Geoffroy Caillat-Grenier(✉)

LIRMM, Univ Montpellier, CNRS, Montpellier, France
geoffroy.caillat-grenier@lirmm.fr

**Abstract.** Expander graphs, due to their mixing properties, are useful in many algorithms and combinatorial constructions. One can produce an expander graph with high probability by taking a random graph (e.g., the union of $d$ random bijections for a bipartite graph of degree $d$). This construction is much simpler than all known explicit constructions of expanders and gives graphs with good mixing properties (small second largest eigenvalue) with high probability. However, from the practical viewpoint, it uses too many random bits, so it is difficult to generate and store these bits for large graphs. The natural idea is to restrict the class of the bijections that we use. For example, if both sides are linear spaces $\mathbb{F}_q^k$ over a finite field $\mathbb{F}_q$, we may consider only *linear* bijections, making the number of random bits polynomial in $k$ (and not $q^k$).

In this paper we provide some experimental data that shows that this approach conserves the mixing properties (the second eigenvalue) for several types of graphs (undirected regular and biregular bipartite graphs). We also prove some upper bounds for the second eigenvalue (though they are quite weak compared with the experimental results). Finally, we discuss the possibility to decrease the number of random bits further by using Toeplitz matrices; our experiments show that this change makes the mixing properties only marginally worse while the number of random bits decreases significantly.

## 1 Introduction

Consider a regular undirected graph with $n$ vertices and degree $d$, and a random walk: at every step, being at some vertex, we choose uniformly a random neighbor and go there. Then, after some fixed number of steps, we get a probability distribution on vertices. If this distribution converges fast to the uniform distribution as the number of steps increases, we say that the graph has good *mixing* properties: we will forget soon where we have started.

Adding one step to our walk means multiplying the probability distribution by the (normalized) adjacency matrix of the graph. The largest eigenvalue of this matrix corresponds to the stationary state (the uniform distribution), so the convergence speed is determined by the *second largest* eigenvalue of this matrix. Graphs having good mixing properties are called *expanders*. They are

Full version: arXiv:2305.02154

Source code: gite.lirmm.fr/gcaillatgrenier/random-schreier-graphs-as-expanders.

© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025
Y. Chen et al. (Eds.): COCOON 2024, LNCS 15161, pp. 397–408, 2025.
https://doi.org/10.1007/978-981-96-1090-7_32
Spectral bound for random Schreier graphs of
$GL_k(\mathbb{F}_2)$

Geoffroy Caillat-Grenier *

October 2023

**Abstract**

In this paper we discuss potentially practical ways to construct expander graphs with good spectral properties and a compact description. We consider variations of a construction that is simple to implement in practice, and develop techniques that seem to be applicable to graphs of feasible size. More specifically, we focus on expander graphs defined as random Schreier graphs of the general linear group over the finite field of size two. We perform numerical experiments and observe that such constructions produce with high probability Ramanujan graphs that can be useful for practical applications.

To find a theoretical explanation of the observed experimental results and prove an upper bound for the expected second largest eigenvalue of the sampled graphs, we use the method of moments. We focus on the settings for which it seems difficult to study the asymptotic behaviour of large graphs but it is possible to provide non-trivial bounds for graphs of relatively small size (interesting for practical applications).

The main contribution of this work is twofold. First, we study families of expander graphs that are, so to speak, pseudo-random (i.e., each graph can be efficiently reconstructed from a short random seed); this approach takes an intermediate position between explicit (deterministic) constructions and the conventional theory of random graphs. Second, we adjust and optimise theoretical bounds not for the limiting behaviour of graphs but for the values of parameters that become meaningful in practical applications (when the whole graph or at least the indices of its vertices can be stored in computer memory).

# 1 Introduction

The regular expander graphs have been extensively studied for several decades and applications can be found in a wide variety of fields, see [20]. It is remarkable that the expansion properties, which are of combinatorial nature, are connected to some spectral properties of the adjacency matrix of the graph, namely the gap between the two largest magnitude eigenvalues (the spectral gap). A large spectral gap means “good” expansion, mixing, and connectivity properties. Observe also that the second largest eigenvalue for some particular

<footnote>* Université de Montpellier, France.</footnote>
used in numerous applications in computer science and in coding theory (see e.g. [9, 13, 23, 24]).

How can we get a graph with good mixing properties, i.e., with small second eigenvalue (an expander)? The natural idea is to try a random graph. For example, for undirected graphs we may consider $d/2$ random permutations of $n$ vertices (where $d$ is some even number) and use them as edges connecting the vertices before and after the permutation. We get a graph of degree $d$ (that might have parallel edges and loops). This construction is called the *permutation model*. The largest eigenvalue equals $d$ (before the normalization that divides all elements by $d$), and all eigenvalues are real (since the matrix is symmetric). What can be said about the distribution of the second largest eigenvalue for a graph randomly sampled in this model?

This question was studied extensively (see [13] for a survey). In 1987 the bound $O(d^{3/4})$ (valid with high probability) was proven in [6]. Then it was improved by Friedman ([12], see also [4] for a shorter proof) who proved that (for every $\varepsilon > 0$) the random construction gives the second eigenvalue at most $2\sqrt{d-1}+\varepsilon$ with high probability for all sufficiently large $n$ (number of vertices) and fixed $d$. This is rather close to the Alon-Boppana lower bound $2\sqrt{d-1}-\varepsilon$ that is valid (for every fixed $\varepsilon > 0$) for all sufficiently large graphs ([20]), so the randomized construction is close to being optimal, at least asymptotically.

There are many different explicit constructions of expanders (see, for example, [2, 10, 16, 18, 19, 21]); some of them also achieve a second eigenvalue close to the optimal. However, they are quite complicated, may have some restrictions on the degree, and the bounds for time complexity and eigenvalues can be of asymptotic nature. The advantage of the random graphs is the simplicity: we generate a graph using a simple randomized algorithm, check its second eigenvalue, and if it is small enough, we can use the graph when good expansion properties are needed. Note that the second eigenvalue needs to be computed only once (and this is still feasible for rather large graphs using modern algorithms and computers), and after that we may safely use the graph in our application.

It is important that the application does not need to recheck the eigenvalues. It still needs, however, to store the graph itself. For the random permutations model, it is a lot of information (each permutation of $n$ vertices requires about $n \log n$ bits). We may overcome this problem if we generate the random graph using much less random bits, store these bits in the application memory, and recompute the neighbors on the fly. But how can we decrease the number of random bits and still get good mixing properties?

In this paper we experiment with one approach of this type. Namely, we replace random permutations by *linear* random permutations. Let $\mathbb{F}_q$ be a finite field with $q$ elements. The $k$-dimensional vector space over this field contains $q^k$ elements ($k$-tuples of elements of $\mathbb{F}_q$). A $k \times k$ invertible matrix determines a permutation of these elements. The zero tuple is a fixed point, so we delete it and get a $q^k - 1$-element set where the group $GL_k(\mathbb{F}_q)$ of invertible $k \times k$ matrices over $\mathbb{F}_q$ acts transitively. The non-zero tuples will be the vertices of the
graph can be computed efficiently, while a direct computation of the Cheeger constant (as well as other combinatorial parameters characterising the properties of expansion and connectivity) would require an exponential search over all subsets of the graph's vertices. At the same time, we should notice that the spectral technique has its limitations, and computing the second largest eigenvalue cannot give better guarantee than an expansion ratio greater than half of the degree ([10]).

In a regular graph of degree $d$ (called $d$-regular graph) with $n$ vertices, the largest magnitude eigenvalue of its adjacency matrix is always $d$. Since the graph is undirected, the matrix is symmetric, hence all eigenvalues are real. We then denote them $d = |\lambda_1| \ge |\lambda_2| \ge \dots \ge |\lambda_n|$. If we consider the normalised adjacency matrix (whose entries are divided by the degree), we note its eigenvalues $1 = |\mu_1| \ge \dots \ge |\mu_n|$. The Alon-Boappana bound refers to the lower bound $|\lambda_2| \ge 2\sqrt{d-1} - \epsilon$ ([15]). A famous result due to Friedman ([9], see also [5] for a shorter proof) states that almost all $d$-regular graphs have second largest eigenvalue smaller than $2\sqrt{d-1} + \epsilon$. This upper bound matches asymptotically the lower bound which makes it optimal in some sense. Thus, most graphs have second largest eigenvalue as small as one can hope for.

The aforementioned results suggest that in practice one can produce a random expander graphs and use it in applications. However, producing such a graph, keeping it in memory and manipulations with it may require much resources. Explicit constructions of expanders (see e.g. [11], [8], [1], [12], [13], [14]) may seem more attractive since we don't need to keep such a graph in memory: neighbours of each vertex can be computed from scratch when needed. However, this approach has its own disadvantages. Some explicit constructions of graph of expanders lack optimality of parameters; they often imply constraints on the degree and the implementation can be difficult in practice. Besides, “polynomial time” algorithms and “asymptotic bounds” involved in these constructions may be good in theory but less successful in practice, for graphs of reasonably small size.

To overcome the mentioned difficulties, in this paper we use an approach that is intermediate between explicit constructions of expanders and purely random graphs. We consider families of graphs that are in some sense pseudo-random. Such a graph can be specified by a “seed” that is rather short compared with the size of the graph; the efficiency of the construction means that given the seed we can compute very efficiently the list of neighbours for every given vertex. More specifically, we take for this purpose some families of Schreier graphs, see below. We start our work with numerical experiments and show that typical graphs in these families enjoy good spectral properties. Then we analyse the properties of these graphs with theoretical tools, which allows us to explain partially the observed results.

Our theoretical analysis also has certain peculiarities. Unlike most works on expander graphs, we pay little attention to asymptotic estimates. Indeed, are ultimate aim to explain eventually the behaviour of (pseudo)random graphs of graspable size, while the remainder terms in typical asymptotic bounds become reasonably small only for astronomically large graphs. Instead, we focus on the techniques that can be used for graphs of comparatively small size (mostly with $2^{10}$ to $2^{200}$ vertices, which seems to be relevant for most practical applications). While asymptotic bounds need to be somewhat elegant (otherwise they would be too hard to analyse), we can afford to use complex and hideous formulas that
graph, and $d/2$ invertible matrices give us $d/2$ permutations of vertices, so we
may construct a regular graph with $q^k - 1$ vertices and degree $d$.

The construction that we described is a special (and easy to implement)
case of a *Schreier graph*: let $H$ be a group acting transitively on a set $X$, so
that $h \in H$ maps $x \in X$ into $h.x$. Let $S$ be a random multiset containing $d$
elements of $H$. Then the Schreier (undirected) graph $G$ is a $2d$-regular graph of
size $|X|$ whose edges are $(x, s.x)$ for $x \in X$ and $s \in S$. In our example $X = (\mathbb{F}_q^k)^*$
and $H = GL_k(\mathbb{F}_q)$.

This approach uses much less bits than the general permutation model: we need $O(\log^2 n)$ bits for each random matrix instead of $O(n \log n)$ bits for a random permutation. The problem is that there are no theoretical guarantees for mixing properties: results proven for the random permutation model do not have yet their counterparts for random *linear* permutations (though some weaker results exist; see Theorem 1.3 in [11]; see also [22] or [8]). Note, however, that we can use this approach in practice safely, assuming we can check the eigenvalues before using the graph.

How to choose the size of graphs for numerical experiments? On the one hand, experiments with “relatively small” graphs are less predictable (therefore, more interesting), since their spectral and combinatorial properties may be far from the asymptotic limits. On the other hand, for “relatively large” graphs, it is easier to justify the advantage of pseudo-randomness (sampling a pseudo-random graph requires significantly less random bits than a truly random one). In this paper, due to the limited space, we focus on expanders of sizes that can be in demand in practice (we only produced very few large graphs). In fact, the size of a “useful” expander depends on the area of application. One of the most popular field of applications of expander graphs is coding theory. In what follows we mostly focus on graphs with $\approx 16000$ vertices, which could be used to construct expander codes (see [23,24]) with parameters comparable with the codes used in real life (like, e.g., the “short” variant of the LDPC from the DVB-S2 standard). However, we emphasise the importance of studying expander graphs of other sizes. Indeed, in some practically used codes, the codewords are significantly longer (many tens of thousands of bits). Moreover, we have theoretical evidences that in some settings codes with codewords of size $10^7$ and even more can be useful (see, e.g., [9]). This means that we eventually may need practical constructions of expander graphs with dozens of millions of vertices. In the full version, we also mention practically useful graphs with even larger (exponentially larger!) number of vertices.

In this paper we provide some experimental evidence showing that this approach may work for several settings. In Sect. 2 we compare the empirical distributions for the second eigenvalue for random permutations and linear random permutations for undirected graphs. We also compare different choices for the field size. In Sect. 3 we provide a similar comparison for bipartite graphs including the case where the sizes of the left and right parts differ significantly. To decrease the number of random bits further, we can use Toeplitz matrices; the experiments with them are reported in Sect. 4. Finally, in Sect. 5 we show how
still allow to do calculations for specific values of the parameters.

## 1.1 Models of random and pseudo-random graphs

Now we proceed with a more formal description of random graph models. There exist several such models, see, e.g. [21]. Our interest will focus on the *permutation model*.

**Definition 1.1 (Permutation model).** *Select randomly and independently d elements $\{\pi_1, \dots, \pi_d\}$ of the symmetric group over the set $\{1, \dots, n\}$. A 2d-regular graph on n vertices in the permutation model is then constructed as follows: connect every vertex i with the vertex $\pi_j(i)$ for every $j \in [1, d]$.*

The obtained graph is undirected, and every vertex $i$ will be connected to $\pi_j(i)$ and $\pi_j^{-1}(i)$ for all $j \le d$. We allow multiple edges and self-loops. Observe that a randomly chosen permutation $\pi_i$ requires $O(\log(n!))$ bits to keep it in the memory of a computer. A description of a random graph sampled in the permutation model occupies $\Theta(dn \log n)$ bits of information (substantially, we have to store for each vertex the list of its neighbours, and in general there is no way to compress such a naive representation).

In this model, it is known that most of graphs have a nearly optimal spectral gap (in [9] it is proven that almost all graphs have second largest magnitude eigenvalue smaller than $2\sqrt{2d-1} + \epsilon$). Thus, the procedure of sampling a random graph will give us with high probability an expander. The argument that we suggest in this paper is inspired by the proof of a similar but weaker statement by Broder and Shamir:

**Proposition 1 ([4]).** Let $G$ be a 2d-regular undirected graph on $n$ vertices in the permutation model. Let $\lambda_2$ be the second largest magnitude eigenvalue of its symmetric adjacency matrix. Then

$$E(|\lambda_2|) = O(d^{\frac{3}{4}})$$

as $n$ goes to infinity.

In what follows we deal with a more algebraic model of random graphs (which seems to be more convenient from the practical view point). Let us proceed with the definition of a *Schreier graph*.

**Definition 1.2 (Random Schreier graphs).** Let $H$ be a group acting transitively on a set $X$. We denote $h.x \in X$ the product of the action of $h \in H$ on $x \in X$. Let $S$ be a random multiset of elements of $H$ of $d$ elements. Then the Schreier (undirected) graph

$$G = \mathrm{Sch}(H \circled{\circ} X, S)$$

is a 2d-regular graph of size $|X|$ whose edges are $(x, s.x)$ for $x \in X$ and $s \in S$.

One can notice that a graph from the permutation model is also a Schreier graph of the symmetric group on $n$ elements.

We are motivated by the result about random Schreier graphs expansion properties in [7], which generalises the theorem on Cayley graphs proven in [2]. A similar result was proven recently in [16]:
the tools from [6] can work for random linear permutation and sketch the proof of some (weak) upper bound for the expected second largest eigenvalue of Schreier graphs (of any group) and for graphs from Toeplitz matrices. With some additional work, these tools provide better bounds (though still quite weak compared with the experimental results) for graphs considered in Sect. 2 and 3 of a given size, and we discuss these bound. Unfortunately, even the exact statements of these bounds are quite complicated and the details (as well as the proofs) are given in the full version.

## 2 Regular Graphs

Consider a finite field $\mathbb{F}_q$ with $q$ (q prime) elements, and the vector space $\mathbb{F}_q^k$ over $\mathbb{F}_q$. Choose randomly $d/2$ invertible matrices $T_1, \dots, T_{d/2}$, and use the corresponding permutations of the set of non-zero tuples to get an undirected graph of degree $d$: a non-zero tuple $x \in \mathbb{F}_q^k$ has neighbors $T_1x, \dots, T_{d/2}x, T_1^{-1}x, \dots, T_{d/2}^{-1}x$. This is a regular graph with $q^k - 1$ vertices and degree $d$ (that may contain loops and parallel edges), and we compute numerically the second eigenvalue of this graph. This procedure is repeated many times, and then the empirical distribution of the second eigenvalues is shown (Fig. 1). For comparison, we show also the distribution for the random permutation model and for a different field sizes (and approximately the same graph size).

<figure><img src="image_1.png" /><figcaption>**Fig. 1.** All the eigenvalues (horizontal axis) are divided by $2\sqrt{d-1}$. The two upper curves (quite close to each other) show the empirical distributions for random permutation model (dashed line) and random *linear* permutation model for graphs of degree $d=30$ (15 permutations) and size $16383 = 2^{14} - 1$. The third curve (wider green one in the bottom part) shows the distribution for random linear permutations on 5-tuples from a 7-element field, so the graph has $7^5 - 1 = 16806$ vertices (and the same degree 30, obtained with 15 permutations). For each distribution 5000 experiments were made; the eigenvalues are grouped in 40 bins.</figcaption></figure>
**Proposition 2** ([16]). Let $H$ be a group, $X$ a set on which $H$ is acting transitively and $S$ a multiset of $d$ randomly chosen elements of $H$ and their inverses. Let $G = \text{Sch}(H \circled X, S)$. The second largest eigenvalue of the associated normalised adjacency matrix is denoted $\mu_2$. For every $\epsilon > 0$, there exist a constant $c_\epsilon$ such that for $d = c_\epsilon \log |X|$ we get

$$ \mathbf{E}(|\mu_2|) < \epsilon $$

where the expectation is taken over all random multisets $S$.

The bound in Proposition 2 may look too weak (ideally, we would like to bound $|\mu_2|$ for a $d$-regular graph by $(2\sqrt{d} - 1 + \epsilon)/d$). However, it applies to a very large class of Schreier graphs. One may hope to prove stronger bound for a more restricted family of graphs.

**The main construction.** We will focus on Schreier graphs of $H = GL_k(\mathbb{F}_2)$ acting on $X = (\mathbb{F}_2^k)^*$ by matrix-vector multiplication. This construction is, in some ways, similar to the permutation model — it is actually the permutation model restricted to the permutations that can be represented by an invertible matrix over $\mathbb{F}_2$. Observe that this construction is very simple and convenient for practical applications. Indeed, vertices of this graph are all strings of $k$ zeros and ones (except for the single string that consist of $k$ zeros). The elements of $S$ are $d$ non-singular (invertible) matrices sampled uniformly and independently from $H$ and their inverses. To find a neighbour of a vertex $v$ induced by $s \in S$, we simply multiply the column-vector $v$ by the matrix $s$.

Let us observe that a representation of a random Schreier graph is much more compact than a representation of a random graph from the general permutation model. Indeed, in order to specify a permutation on $n$ vertices, $O(n \log n)$ bits are needed, whereas only $O(k^2) = O(\log^2 n)$ bits are necessary to specify an invertible matrix in our finite field. By analogy with pseudo-random generators, one may call these graphs *pseudo-random*, since the random seed determining the entire graph is much shorter than the size of incidence matrix or the list of all edges.

It remains to verify that graphs from the presented constructions are typically good spectral expanders. We will see that, due to numerical experiments, this is indeed the case for most graphs from these families (with reasonably chosen parameters). For relatively small graphs (e.g., with $n \sim 10^4$ vertices, when we are able to produce completely the matrix of a graph and compute its eigenvalues with a computer) the experimental results might be quite enough for application. Indeed, we can sample a random set $S$, then verify numerically that the graph corresponding to this $S$ is indeed a good expander, and then plug this instance of a graph in the application.

However, most of this paper is devoted to the attempts to get theoretical bounds for the families of graphs discussed above. Why do we need theoretical bounds for the spectral gap of these (pseudo)random graphs? One reason is purely theoretical: we would like to eventually explain the phenomena that we observe in numerical experiments. Another reason is more practical. In applications we may need “strongly explicit” expanders with pretty large number of vertices (e.g., with $n \sim 2^{200}$), so that we cannot produce the entire matrix of the graph, but we still can keep in the memory of a computer an index of one vertex and we can compute efficiently indices of its neighbours. In this case, we
The invertible matrices were generated by choosing a random<fnref n="1" /> matrix and then testing whether it is invertible. For Boolean matrices, the fraction of invertible ones is above 1/4 (see, e.g., [1]), so we do not need too many trials; for bigger fields, the fraction is even bigger. Computing the determinant (checking the invertibility) is easy. For computing the eigenvalues we used the C++ library Spectra<fnref n="2" /> that implements the Lanczos algorithm [7].

The choice of the unit on the horizontal axis ($2\sqrt{d}-1$ for non-normalized adjacency matrices) is motivated by the asymptotic lower bounds we mentioned. Graphs that have the second eigenvalue smaller than this unit are usually called *Ramanujan graphs*; we see that for our parameters both the random permutations and random linear permutations give Ramanujan graphs most of the time.

We also tested another set of parameters: 5-tuples from a 7-element field (so the resulting graph size is close to the previously considered one, $7^5 - 1 = 16806$ instead of $2^{14} - 1 = 16383$, which makes the results roughly comparable). Note that this choice allows us to decrease the number of random bits used for the graph generation. We see that this is achieved for a price: the distribution is now less concentrated, though still very close to the Ramanujan threshold. (One could expect that more random bits lead to better concentration.) One can also observe (we do not have any explanation for this paradoxical observation) that the probability to get a random graph that is on the left of, say, 0.998, becomes bigger for a bigger field. So, if we try to get one graph with small eigenvalue after many trials, the bigger field may be better. One could try to go to the extreme in this direction and consider $1 \times 1$ invertible matrices, i.e., consider multiplication by non-zero elements in some field $F_q$ (the graph size is then $q-1$). This is, however, a bad idea since in this case the invertible matrices commute and therefore many paths in a random walk arrive at the same place just due to commutativity. Such a graph will have poor mixing properties.

Additionally, we can observe that variations on the degree of the graphs (for a given construction) does not seem to have much impact on the distribution of the second largest eigenvalues (Fig. 2, left). Though the difference is hardly visible, we can see that smaller degree leads to a slightly greater second largest eigenvalue. This is not surprising since low degree random graphs tend to be worse expanders. However, the eigenvalues are slightly more concentrated. As expected (see Fig. 2 on the right) increasing the dimension does not change the expected value but decreases the variance.

## 3 Bipartite Biregular Graphs

The experiments in the previous section were for undirected regular graphs, but one may also need a *bipartite graph* that is *biregular* (degrees of the vertices

<footnote n="1">¹ The random number generator was Mersenne twister ([17]); we tested physical random generators without noticing any difference.</footnote>

<footnote n="2">² Spectra's home page: https://spectralib.org/.</footnote>
cannot compute numerically the spectrum of the graph. So it would be helpful to have a theoretical result saying that a randomly chosen graph from the family G with a very high probability has a small enough second eigenvalue. Although our theoretical results only apply to finite fields of size 2, experimental results show that the construction can be suitable for bigger fields (see Figures 2 and 3).

All of this led us to try to adapt the proof in [4] (though it ended up being quite different) to get a bound on the expected second largest eigenvalue of the adjacency matrix of the graphs obtained. We prove the following statement:

**Theorem 1.** Let $G = \mathrm{Sch}(GL_k(\mathbb{Z}_2) \circledast (\mathbb{Z}_2^k)^*, S)$ be a graph of size $n = 2^k - 1$ and whose degree is $2d = 2|S|$, with $k \le 2$. Let $\mu_2$ be the second largest eigenvalue of its normalised adjacency matrix. Consider the following recursive relation:

$$X_q(c, l, d) = \begin{cases} 1 & \text{if } c = 0 \text{ and } l = 0 \\ 0 & \text{if } q > l \\ \sum_{i=c}^{\lfloor l/q \rfloor} \binom{d}{i} \left(\frac{2^q}{q!}\right)^i \frac{l!}{(l-qi)!} X_{q+1}(0, l-qi, d-i) & \text{otherwise.} \end{cases}$$

We set $x_3(i) = X_3(1, 2m - 2i, d - i)$ and $x_4(i) = X_4(0, 2m - 2i, d - i)$. Then, for all integer $m$,

$$\mathbf{E}(|\mu_2|) \le \left( \left(\frac{1}{2d}\right)^{2m} n \left[ \sum_{i=1}^{m} \binom{d}{i} \frac{(2m)!}{(2m-2i)!} \left[ (2^i - 1)(x_3(i) + x_4(i)) \frac{2}{n} + \left( (x_3(i) + x_4(i)) \frac{1}{n} + \frac{2^i}{(i+1)!} \left(x_3(i) \frac{5}{n} + x_4(i)\right) \right) \right] + X_1(1, 2m, d) \frac{1}{n} + x_3(0) \frac{5}{n} + x_4(0) \right] - 1 \right)^{\frac{1}{2m}}. \quad (1)$$

The bound (1) looks messy, and the asymptotic analysis may be difficult. However, this formula becomes useful when we need to calculate (with help of a computer) a bound for a specific graph of relatively small size (e.g., less than $2^{200}$ vertices). For a specific graph $G$, we choose $m$ in such a way that (1) gives the strongest bound possible for $\mathbf{E}(|\mu_2|)$. Though this big formula is fairly hard to analyse, it is easy to compute it numerically. We have been able to check that this gives a meaningful and non trivial bound for $2m$ close to $k$. This result is less general than Proposition 2, but it gives stronger and more explicit bounds for certain specific values of parameters. Nevertheless, an asymptotic study of its behaviour might be interesting. However, this is not done in this paper.

## 1.2 A construction of pseudo-random bipartite expanders

The construction explained above can easily be adapted to obtain bipartite $d$-regular graphs of $2n$ vertices ($n$ in each partition, $n = 2^k - 1$). In such a graph, each vertex of the first partition is labeled the same way that of the second, by a vector in $(\mathbb{F}_2^k)^*$. We have two ways of constructing the edges.

The first way is the following. We select uniformly at random $d$ matrices of $GL_k(\mathbb{F}_p)$ that form a multiset $D$. Then we connect each vertex $x$ from the first
<figure><img src="image_2.png" /><figcaption>**Fig. 2.** On the left: second largest eigenvalue distributions for $GL_{14}(\mathbb{F}_2)$ Schreier graphs of degrees 10, 30, 60 and 120. On the right: instead of the degree, we vary the dimension of the matrices and keep the same field $\mathbb{F}_2$.</figcaption></figure>

are the same in each part, but may differ in left and right parts) and has good mixing properties (for the back and forth random walk).

Note first that every undirected regular graph can be converted to a bipartite biregular graph (with the same degree in both parts), just by doubling the set of vertices (each vertex now is present both in the left and right part) and interpreting the edges as edges between parts. The random walk in this graph is just the random walk in the original undirected graph (combined with alternating the parts), so the mixing properties of this bipartite graph are the same as for the initial undirected regular graph.

However, in the bipartite case we do not need to use a permutation together with its inverse. Instead, we consider $d$ random bijections between parts and get a biregular graph of degree $d$. We use this construction in our experiments with bipartite graphs (the previous construction would have given the same result as for regular non-bipartite graphs). This allows us to have bipartite graphs of any (possible odd) degree.

Sometimes (e.g., in some constructions in coding theory) we need biregular bipartite graphs where left and right parts are of different size. A natural way to get such a graph is to start with a bipartite graph with the same part sizes, and then merge vertices in one of the parts. Merging $s$ vertices into one, we decrease the size and increase the degree by the factor of $s$. (We assume that number of vertices is a multiple of $s$.)

These constructions can be performed both with random permutations and random linear permutations. The same question arises: what can be said about mixing properties of graphs in these two settings? A traditional way to measure mixing property of a bipartite graph is to consider the (non-normalized) adjacency matrix for it (height and width are equal to the total number of vertices in both parts). The eigenvalues of this matrix are grouped into pairs, starting with $\sqrt{d_L d_R}$, where $d_L$ and $d_R$ are left and right degrees (the eigenvector coordinates are $\sqrt{d_L}$ in the left part and $\sqrt{d_R}$ in the right part) and $-\sqrt{d_L d_R}$ (to change the
partition to two vertices of the second partition: s.x and $s^{-1}.x$, with $s \in D$. This way, we obtain a bipartite 2d-regular graph. Here the degree of the graph needs to be even, as in non bipartite graphs from our construction. The main interest of this approach is that we can obtain the same bound for the second largest eigenvalue as in Theorem 1 with very little additional work.

In order to obtain bipartite regular graphs of odd degree, we can take a slightly different setting. Once we have our multiset $D$, we connect every $x$ in the first partition to $s.x$ in the second one. This gives a $d$ regular bipartite graph denoted

$$G = \mathrm{Sch}_{\mathrm{BP}}(\mathrm{GL}_k(\mathbb{F}_2) \circled{\circ} (\mathbb{F}_2^k)^*, D).$$

For this family of graphs the proof of Theorem 1 does not apply directly, but we can adapt it in order to get similar bounds. We prove the following statement:

**Theorem 2.** Let $G = \mathrm{Sch}_{\mathrm{BP}}(\mathrm{GL}_k(\mathbb{F}_2) \circled{\circ} (\mathbb{F}_2^k)^*, D)$ with $k \le 2$, $|D| = d$, and $|(\mathbb{F}_2^k)^*| = n$. Let $\mu_2$ be the second largest magnitude eigenvalue of its normalised adjacency matrix. Consider the relation

$$Y_q(c, l, d) = \begin{cases} 1 & \text{if } c = 0 \text{ and } l = 0 \\ 0 & \text{if } q > l \\ \sum_{i=c}^{\lfloor \frac{l}{q} \rfloor} \binom{d}{i} (q!)^{-i} \frac{l!}{(l-qi)!} Y_{q+1}(0, l-qi, d-i) & \text{otherwise.} \end{cases}$$

We set $y_3(i) = Y_3(1, 2m - 2i, d - i)$, $y_4(i) = Y_4(0, 2m - 2i, d - i)$. Then,

$$\mathbf{E}(|\mu_2|) \le \left(\left(\frac{1}{d}\right)^{2m} n \left[\left(\frac{1}{d}\right)^{2m} \sum_{i=1}^{m} \left[\binom{d}{i} \left(\frac{1}{2}\right)^i \frac{(2m)!}{(2m-2i)!} \frac{2^i}{(i+1)!} \left(y_3(i)\frac{5}{n} + y_4(i)\right)\right] + Y_1(1, 2m, d)\frac{1}{n} + Y_2(1, 2m, d)\frac{2}{n} + y_3(0)\frac{5}{n} + y_4(0)\right] - 1\right)^{\frac{1}{2m}}. \quad (2)$$

And again, the expression in (2) is difficult to analyse, but it helps to compute concrete bounds for graphs with some specific values of parameters. The expression in (2) is only slightly weaker than that in (1) (see Section 2). Moreover, it seems that the optimal value of $2m$ is the same in both theorems.

So far we discussed regular bipartite graphs, where all vertices have the same degree. In bipartite biregular graphs, the degree is the same for every vertex in the same partition, but it can be different from one partition to the other. These graphs are of interest for many applications in computer science and in coding theory (see, e.g., [17], [22]), and good spectral properties are often needed. We can adapt the construction above to get such graphs. Assume we need a graph with degree $d_1$ in the left partition whose size is $n_1$, and $d_2$ in the right one, of size $n_2$, such that $n_1d_1 = n_2d_2$ and $n_2 \le n_1$. To achieve that, construct a graph as previously and merge every $\gamma = d_2/d_1$ vertex on the right side (taking them in an arbitrary order). We denote such a graph

$$G = \mathrm{Sch}_{\mathrm{BP}}(\mathrm{GL}_k(\mathbb{F}_p) \circled{\circ} (\mathbb{F}_p^k)^*, D, \gamma).$$

In such a graph, the greatest eigenvalue of its adjacency matrix is $\sqrt{d_1d_2}$. For this kind of graphs, the analogous of the Alon-Boppana bound $2\sqrt{d-1}$ is
<figure><img src="image_3.png" /><figcaption>**Fig. 3.** Here, $\mathbf{n}1$ is the size of each partition. The dashed line (blue) shows the distribution of second eigenvalues for a bipartite graph constructed from 30 random permutations of 16383-element set (nonzero bit vectors of size 14). The orange line (close to the first one) shows the same for 30 linear permutations (over $\mathbb{F}_2$). The third line (green, in the bottom part) shows the distribution for 30 permutations of a 16806-element set that are randomly chosen among the $\mathbb{F}_7$-linear permutations of nonzero 5-tuples with elements in $\mathbb{F}_7$. (Color figure online)</figcaption></figure>

sign of the eigenvalue we change signs in all eigenvector coordinates in one of the parts). The next pair, $\lambda > 0$ and $-\lambda < 0$, determines the mixing properties, and we call $\lambda$ the second largest eigenvalue (ignoring the negative ones).

The role of the Ramanujan threshold $2\sqrt{d-1}$ (for regular undirected graphs of degree $d$) is now played by $\sqrt{d_L-1} + \sqrt{d_R-1}$: it has been proven that the second largest eigenvalue cannot be much smaller than this quantity [15] and with high probability is not much larger for random graphs [5]. We use $\sqrt{d_L-1} + \sqrt{d_R-1}$ as the unit on the horizontal axis for all our figures.

Figure 3 shows the experiments with bipartite graphs with the same degree 30 in both parts obtained using 30 permutations of a set of non-zero elements of $\mathbb{F}_2^{14}$. The setting is different from the case of the undirected regular graph (Fig. 1) where we used 15 permutations and their inverses, but the results turn out to be quite similar (and the distribution for the case of $\mathbb{F}_7^5$ is also similar to Fig. 1).

For the case of different left and right degrees the results of our numerical experiments are shown in Fig. 4. Comparing this figure with the previous one, we observe some differences: the random permutations now give slightly (but visibly) better results compared to random linear permutations. On the other hand, changing the size of the field (and matrix dimension) now has much less effect. In fact, results may depend on which triples we are merging, for the linear case, due to the additional structure induced by the construction (compared to general permutations). However, this phenomenon still has to be explained.
$\sqrt{d_1 - 1} + \sqrt{d_2 - 1}$: it has been proven that the second largest magnitude eigenvalue cannot be much smaller than this quantity ([19]) and not much larger in most of the cases ([3]). We prove the following statement, which is a corollary of Theorem 2:

**Corollary 1.** Let $G' = Sch_{BP}(GL_k(\mathbb{F}_2) \circled{\circ} (\mathbb{F}_2^k)^*, D, \gamma)$ with $|D| = d_1$. Let $d_2 = \gamma d_1$ and let $\lambda_2$ be the second largest magnitude eigenvalue of its adjacency matrix.

$$ \mathbf{E}(|\lambda_2|) \leq \sqrt{d_1 d_2 \alpha}. $$

where $\alpha$ is the minimum over $m$ of the bound applied to regular bipartite Schreier graphs of odd (Theorem 2) or even (Theorem 1) degree.

## 1.3 A simple asymptotic bound

In this work we do not focus on asymptotic behaviour of large graphs. However, we observe that at least in some setting, the used technique easily gives some asymptotic bounds. This bound applies to the construction of a Schreier graph $GL_k(\mathbb{F})$ with any dimension $k$ and with any finite field $\mathbb{F}$, which is not the case of the previous ones (in Theorem 1 and Theorem 2 we use very substantially the fact that the group is not abelian, which is false in dimension one). The bound applies to graphs with a pretty large degree, $d = \Omega(\ln n)$ (see next section for an estimate of the constant hidden in the $\Omega$ notation).

**Theorem 3.** Let $G = Sch(GL_k(\mathbb{F}_p) \circled{\circ} (\mathbb{F}_p^k)^*, S)$ graph of size $n = p^k - 1$ and whose degree is $2d = 2|S|$. Let $\mu_2$ be the second largest eigenvalue of its normalised adjacency matrix. Then,

$$ \mathbf{E}(|\mu_2|) \leq e \sqrt{\frac{\ln n}{d}} $$

where $\ln$ is the natural logarithm and $e$ its base.

# 2 Experimental results

We have conducted numerical experiments which showed that the spectral properties of the Schreier graphs in our constructions for regular and bipartite graphs are pretty close to the optimal values achieved by “truly random” graphs (much closer than what one could expect from Theorem 1 and Theorem 2, see Figures 2 and 3 below). The main motivation of our work was to explain this results theoretically. With the help of a computer, we applied our bounds from Theorems 1, 2 and 3 to some specific parameters of graphs. This calculations are shown in Figure 1. We can observe that the theoretical results that we obtain give non trivial bounds for the second eigenvalue but do not explain completely our numerical experiments.

**Results of the experiments.** We show below (Figures 2 and 3) the experimental results we have got for the eigenvalues of randomly sampled graphs. For each of the following curves, we computed the second largest magnitude eigenvalues of 5000 graphs and display the probability distribution. In order to
<figure><img src="image_4.png" /><figcaption>**Fig. 4.** The dashed line (blue) shows the distribution of the second eigenvalues for 5000 experiments when we take 10 random permutations of a set with $2^{14} - 1 = 16383$ elements, construct a bipartite graph with degree 10 in both sides and then merge triples of vertices on one side thus getting degree 30 and size $16383/3 = 5461$. The solid (orange) line replaces random permutations by random *linear* (over $\mathbb{F}_2$) permutations of non-zero vectors in $\mathbb{F}_2^{14}$. Finally, the line with dots (green) shows the same distribution if we take 10 linear permutations of non-zero vectors in $\mathbb{F}_7^5$. (Color figure online)</figcaption></figure>

# 4 Graphs from Toeplitz Matrices

We now modify our construction in order to reduce further the number of random bits. Instead of taking random invertible matrices, we take invertible Toeplitz matrices. Recall that a matrix $T = (t_{ij})$ is called a *Toeplitz matrix* if $t_{ij}$ depends only on the difference $j-i$.

If we choose the elements of such a matrix randomly from a field of prime size $q$, then we get an invertible matrix with probability $1-1/q$ (see [14]), so it is even easier to generate them. A Toeplitz matrix is defined by $2k-1$ elements of the field (instead of $k^2$ for a general matrix), so this is also an advantage. (One more technical advantage is that we can multiply a vector by a Toeplitz matrix fast since it is essentially the convolution.)

In Fig. 5 (left) we return to the case of undirected regular graphs, and compare random graphs obtained using 15 random matrices (either random invertible matrices or random invertible Toeplitz matrices). Two upper curves (yellow and blue) use $\mathbb{F}_2^{14}$; one can see that Toeplitz matrices give bigger (and less concentrated) eigenvalues. The same can be seen from two bottom curves (red and green); we see also that decreasing the dimension and increasing the field size increase significantly the variance (but not the mean, see below). The difference between Toeplitz and general invertible matrices is visible but small. Hence, Toeplitz matrices are suitable for producing good spectral expanders (at least with the parameters of the experiments). On the right of Fig. 5, we observe that the parity of the dimension of Toeplitz matrices used affects the mean of the distribution (the variance behaves as expected). Odd dimensions tend to pro-
<table><thead><tr><th>(k, d)</th><th>Th.1</th><th>Th.2</th><th>Th.3</th><th>[4]</th><th>[9]</th></tr></thead><tbody><tr><td>(14, 16)</td><td>0.7317</td><td>0.8256</td><td>2.1169</td><td>1.1208</td><td>0.3479</td></tr><tr><td>(16, 16)</td><td>0.7862</td><td>0.8794</td><td>2.2631</td><td>1.0458</td><td>0.3479</td></tr><tr><td>(20, 20)</td><td>0.7758</td><td>0.8629</td><td>2.2631</td><td>0.9532</td><td>0.3122</td></tr><tr><td>(25, 100)</td><td>0.3277</td><td>0.3718</td><td>1.1315</td><td>0.6783</td><td>0.1410</td></tr><tr><td>(30, 1000)</td><td>0.0988</td><td>0.1128</td><td>0.3919</td><td>0.4088</td><td>0.0447</td></tr><tr><td>(40, 1000)</td><td>0.1110</td><td>0.1251</td><td>0.4526</td><td>0.3594</td><td>0.0447</td></tr><tr><td>(60, 60)</td><td>0.7377</td><td>0.7944</td><td>2.2631</td><td>0.5805</td><td>0.1818</td></tr><tr><td>(200, 200)</td><td>0.7016</td><td>0.7350</td><td>2.2631</td><td>0.3694</td><td>0.0998</td></tr></tbody></table>

Figure 1: This table shows the computed bounds from our three theorems for different parameters (the dimension $k$ and the degree $d$). These values are compared with the best asymptotic bound known ([9]) and to the bound from [4]).

calculate these eigenvalues, we used the C++ library Spectra<fnref n="1" /> that implements the Lanczos algorithm ([6]).

One can observe that the second largest eigenvalues are likely to be much closer to the optimal asymptotic value ($2\sqrt{2d-1}$ and $\sqrt{d_1-1}+\sqrt{d_2-1}$ respectively) than what we have shown theoretically. In addition, the variances of the distributions decrease when the dimensions of the matrices grow. The degrees of the graphs do not seem to have an effect on the probability distribution of the normalised value of the second largest eigenvalue.

**A partial theoretical explanation.** These experimental observations show that the second eigenvalue of a random Schreier graph from our construction is very close to the theoretical optimum (among all regular graphs). This phenomenon remains unexplained. What is even more frustrating, and we cannot guarantee that (pseudo)random graphs from similar families but with a large number of vertices (e.g., with $n \sim 2^{200}$) posses good spectral properties. However, Theorem 1, Theorem 2 and Theorem 3 imply some nontrivial bound for the second eigenvalues of those graphs. The values in Figure 1 allow to illustrate the behaviour of our bounds.

Let us start with the bound from Theorem 3. We apply this theorem with $d = ck = O(\log n)$ (where $c$ is a constant). The theorem gives a non-trivial bound (a constant that is below 1) when $c$ is around 6 or above.

Theorem 1 implies a stronger bound: this resulting bound becomes meaningful with $d \ge \frac{2}{3}k$, which means that it becomes useful with a smaller degree (for large enough $k$). With $d = k$, this theorem gives a bound that seems to converge to a value around 0.7 (we have tested this observation up to $k = 400$). This bound is always smaller than that of Theorem 3.

The bound from Theorem 2 is very similar to that of Theorem 1. Their respective values can be easily compared in the table (1).

The natural conjecture that raises from this observation would then be that for $d = O(\log n)$, the bounds from Theorems 1 and 2 converge to a value between 0 and 1 (exclusive). This would imply that those theorems improve the

<footnote n="1">¹Spectra's home page: spectralib.org.</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 5. On the left: distributions of second largest eigenvalues of 5000 graphs obtained from Toeplitz matrices (TP) for $\mathbb{F}_2^{14}$ and $\mathbb{F}_7^5$ compared with the corresponding empirical distributions for random linear permutations in the same vector spaces (GL). On the right, all graphs are from Toeplitz matrices over $\mathbb{F}_2$. (Color figure online)</figcaption></figure>

duce better spectral expanders (this can be also observed on the left part of the Figure, red curve). We could not find any explanation of this phenomenon.

## 5 Computer-Assisted Theoretical Bounds

The numerical experiments show that the constructions discussed in the previous sections allow to sample good spectral expanders of reasonable size (say, with $n \sim 10^4$ vertices) where we can compute the second eigenvalue. However, in some applications we may need “strongly explicit” expanders with much larger number of vertices (see e.g. [9]). In this case we cannot produce the entire matrix of the graph (nor compute the eigenvalues), although we still can keep in the memory an index of one vertex and compute efficiently the indices of its neighbors.

It is thus useful to have theoretical guarantees about the eigenvalues when we cannot compute them. To do so, one can use the trace method [6] for the case of Cayley (or arbitrary Schreier) graphs, following [3]. This gives the following bound (see also [8, 22]):

**Proposition 1.** Let $G$ be a Schreier graph constructed using $d$ elements of a group acting on an $n$-element set (so it has $n$ vertices and degree $2d$). Let $\mu_2$ be the second largest eigenvalue of its normalized adjacency matrix. Then

$$ \mathbf{E}(|\mu_2|) \le e \sqrt{\frac{\ln n}{d}} $$

where $\ln n$ is the natural logarithm and $e$ its base. The same bound holds for graphs constructed with $d$ randomly chosen invertible Toeplitz matrices. The statement is also valid for bipartite graphs of $2n$ elements of degree $d$ (produced with $d$ random elements).
<figure><img src="image_3.png" /><figcaption>Figure 2: This is the observed distribution of the second largest eigenvalues of 2d-regular graphs (not normalised) adjacency matrix from our construction with different parameters. Here, $d = 15$, and $n$ is the size of the graph. We represent the probability distribution with $k = 5, 6$ and $14$, (where $k$ is the matrix dimension) and adapt the size of the field so that all graphs have roughly the same size. We show the measured value of the second largest eigenvalue in the normalised form, i.e., $s$ divided by $2\sqrt{2d-1}$. We compare the random Schreier graphs with “truly” random regular graphs: in the figure, “Perm” refers to the graphs obtained from the permutation model (see above) and “SW” refers to graphs obtained from the Steger-Wormald algorithm ([18]) which provides random regular graphs without loops and multiple edges.</figcaption></figure>
*Proof Sketch.* The proof of this bound goes as follows. To get an upper bound for the eigenvalues of some symmetric real matrix $M$, we can use upper bounds for the trace of $M^m$ for some even $m$ (that will be chosen later). Indeed, the trace is the sum of the $m$th powers of the eigenvalues. In our case $M$ is the (normalized) adjacency matrix, and we know the first eigenvalue 1. Hence, given an upper bound for the trace of $M^m$ we get some bound for the second eigenvalue. (In fact, we will get a bound for expected value of $\mu_2^m$, but this will imply a bound for the expected value of $\mu_2$ due to convexity.)

Trace of $M^m$ for a normalized adjacency matrix $M$ has a natural interpretation in terms of random walks: the $i$th diagonal element of the matrix is the probability to return to $i$ after $m$ steps of a random walk (starting from $i$). We need a bound for the expected value of this trace (for a random choice of $d$ elements of the group). So we have two independent choices: (a) choice of $d$ group elements $h_1, \dots, h_d$; (b) choice which of $h_1, \dots, h_d, h_1^{-1}, \dots, h_d^{-1}$ will be used along the walk ($m$ choices from $2d$-element set). We can exchange the order of averaging and first take a random word of length $m$ over the alphabet with $2m$ symbols $h_1, \dots, h_d, h_1^{-1}, \dots, h_d^{-1}$, and only after that choose the random values (group elements) for $h_1, \dots, h_d$.

For example, with some probability we get after the first stage a word of length $m$ where the letters cancel each other completely. Then on the second stage we remain in the same vertex with probability 1. But if $m$ is significantly smaller than $d$, then with high probability we get a non-canceling word, and, moreover, a word where some letter $h_i$ appears only once (as $h_i$ or $h_i^{-1}$). In this case the second stage probability to return back is $1/n$ (since this unique application of $h_i$ will make the distribution uniform, due to transitivity of the action). If we combine these remarks carefully (and take $m \approx \ln n$), we get the required bound. See the full version for details.

A more subtle classification of the words of length $m$ over the alphabet composed of the symbols $\{h_1, \dots, h_d, h_1^{-1}, \dots, h_d^{-1}\}$ allows us to improve this bound (the statement is in the full version) for Schreier graphs of $GL_k(\mathbb{F}_2)$. Unfortunately, the improved bound is quite complicated (and even its asymptotic behavior is not clear). Both the bound and its proof are included in the full version. However, using computer assistance, we can compute this improved bound for specific values of parameters ($k$ and $d$). $\square$

Looking at this table (Table 1), we see that the improved bound makes sense in several cases where Proposition 1 does not give anything (the bound is greater than the trivial bound 1). However, even the improved bound is far from being tight (recall that our experiments, when feasible, exhibit a rather small difference between the second eigenvalue and Ramanujan's threshold). Moreover, we can observe some convergence behavior when $d=k$. This would imply that the asymptotic behavior of the improved bound is similar to that of Proposition 1. Similar bounds can be obtained for the bipartite case (see the full version), and these observations remain valid.
<figure><img src="image_4.png" /><figcaption>Figure 3: We display here the observed distribution of the second eigenvalue for bipartite biregular graphs. The measured value of the second largest eigenvalues is normalised by division by $\sqrt{d_1 - 1} + \sqrt{d_2 - 1}$, which is the analogous of $2\sqrt{d - 1}$ for bipartite biregular graphs ([3]).</figcaption></figure>
**Table 1.** Upper bounds for the expected value of $\mu_2$ provided by Proposition 1 and its improved version (see the full version) for a few choices of parameters. We display also the Ramanujan's threshold for comparison. The first three lines correspond to graphs that we tested in our experiments.

<table><thead><tr><th>(k, d)</th><th>Improved</th><th>Proposition 1</th><th>Ramanujan</th></tr></thead><tbody><tr><td>(14, 15)</td><td>0.7607</td><td>2.1863</td><td>0.3590</td></tr><tr><td>(14, 30)</td><td>0.5033</td><td>1.5459</td><td>0.2560</td></tr><tr><td>(14, 60)</td><td>0.3389</td><td>1.0931</td><td>0.1818</td></tr><tr><td>(20, 20)</td><td>0.7758</td><td>2.2631</td><td>0.3122</td></tr><tr><td>(25, 50)</td><td>0.4969</td><td>1.6002</td><td>0.1989</td></tr><tr><td>(30, 500)</td><td>0.1435</td><td>0.5543</td><td>0.0632</td></tr><tr><td>(40, 500)</td><td>0.1618</td><td>0.6401</td><td>0.0632</td></tr><tr><td>(50, 1000)</td><td>0.1217</td><td>0.5060</td><td>0.0447</td></tr><tr><td>(60, 60)</td><td>0.7377</td><td>2.2631</td><td>0.1818</td></tr><tr><td>(200, 200)</td><td>0.7016</td><td>2.2631</td><td>0.0998</td></tr></tbody></table>

# 6 Final Comments

In this paper we study a pseudo-random construction of spectral expanders using Schreier graphs. The experimental results suggest that these graphs provide almost optimal value for the second largest eigenvalue (close to $2\sqrt{d-1}$ for regular graphs of degree $d$ and to $\sqrt{d_1-1} + \sqrt{d_2-1}$ for bi-uniform bipartite graphs with degrees $d_1$ and $d_2$), and are potentially useful for the applications.

Still there is no theoretical explanation for this phenomenon: the existing bounds are quite weak, even in the improved version (and these improvements do not give a closed answer, just a recurrent formula that allows us to compute the bound).

The possible reduction of the number of random bits used and the computational complexity via Toeplitz matrices looks promising (as the experiments show) but a comprehensive theoretical analysis is missing. The only proven bound that applies in the setting with Toeplitz matrices is Proposition 1, which gives nontrivial bounds only if the degree of the graph is bigger than logarithm of the number of vertices.

# References

1. The on-line Encyclopedia of Integer Sequences, sequence a048651. https://oeis.org/A048651

2. Alon, N.: Explicit expanders of every degree and size. Combinatorica 41, 447-463 (2020)

3. Alon, N., Roichman, Y.: Random Cayley graphs and expanders. Random Struct. Algorithms 5, 271-285 (1994)
bound from Theorem 3 by a constant factor. Therefore, those bounds would be asymptotically $O(\sqrt{\log n})$.

**Practical implementation.** We now briefly explain how our construction of “pseudo-random” (and, therefore, “almost explicit”) graphs can be implemented. The main task that needs to be done is obviously sampling the $d$ matrices from $GL_k(F_p)$. One way of doing so is simply picking uniformly and independently all $k^2$ coefficients of the matrix and reject the matrix if its determinant is zero (modulo $p$). Computing the determinant is polynomial in $k = O(\log n)$. In order to estimate the expected value of the numbers of tries we need to get an invertible matrix, we can estimate the following quantity:

$$ \frac{|GL_k(F_p)|}{|M_{k,k}(F_p)|} = \frac{\prod_{i=0}^{k-1} p^k - p^i}{p^{k^2}} = \prod_{i=0}^{k-1} (1 - p^{i-k}) = \prod_{i=1}^{k} (1 - p^{-i}) $$

where $M_{k,k}(F_p)$ is the set of all $k \times k$ matrices whose coefficients are in $F_p$. One can show<fnref n="2" /> that this product is convergent and always bigger than $\frac{1}{4}$. From this, we can conclude that we need generally less than four tries so we get a non-singular matrix. Once we have our $d$ matrices, it is enough to apply them to all vectors. This can be done in $O(k^2)$ steps. This way, the whole graph can be produced in time $O(nd \log^2 n)$.

# 3 Proofs of the main results

## 3.1 Proofs of Theorems 1 and 3

Let $p$ be a prime, $k$ a natural integer and $G = \text{Sch}(GL_k(\mathbb{Z}_p) \circled{\circled{(Z_p^k)}^*}, S)$ be a Schreier graph with $S$ a random subset of $d$ elements of $GL_k(\mathbb{Z}_p)$ and their inverses. Hence, we obtain a $2d$ regular graph whose size is $n = p^k - 1$. By mapping every element of $(Z_p^k)^*$ to an element of $[1, p^k - 1]$ (e.g. with $f: (x_1, \dots, x_k) \mapsto \sum_{i=0}^{k-1} x_i p^i$), we can associate every pair of vertices with a coordinate of a matrix. This way, we can define $M$, the normalised adjacency matrix of $G$. Let

$$ 1 = |\mu_1| \ge |\mu_2| \ge \dots \ge |\mu_n| $$

be its eigenvalues (which are real since the matrix is symmetric).

Consider a random walk of $2m$ steps starting at vertex $i$. Then the $(i, i)$ coordinate of $M^{2m}$ corresponds to the number of closed walks starting at vertex $i$ of size $2m$ divided by $(2d)^{2m}$, since $(2d)^{2m}$ is the number of paths of size $2m$ starting at $i$. Therefore, this is the probability (denoted $P_{ii}$) of returning to the vertex $i$ after $2m$ steps of the random walk. Since $\text{Trace}(M^{2m})$ is equal to the sum of all of these quantities and since the expected $(i, i)$ coordinate of $M^{2m}$ is the same for every $i$ we get

$$ \mathbf{E}(\text{Trace}(M^{2m})) = n\mathbf{E}(P_{11}). $$

On the other hand, we have

$$ \sum_{i=1}^{n} \mu_{i}^{2m} = \text{Trace}(M^{2m}). $$

<footnote n="2">²See e.g. math.stackexchange.com/questions/491948.</footnote>
4. Bordenave, C.: A new proof of Friedman's second eigenvalue theorem and its extension to random lifts. Annales scientifiques de l'École normale supérieure **53**(4), 1393-1439 (2015)

5. Brito, G., Dumitriu, I., Harris, K.D.: Spectral gap in random bipartite biregular graphs and applications. Comb. Probab. Comput. **31**(2), 229-267 (2022). https://doi.org/10.1017/S0963548321000249

6. Broder, A., Shamir, E.: On the second eigenvalue of random regular graphs. In: Proceedings of the 28th ACM Symposium on Theory of Computing, pp. 286-294 (1987)

7. Calvetti, D., Reichel, L., Sorensen, D.C.: An implicitly restarted Lanczos method for large symmetric eigenvalue problems. Electron. Trans. Numer. Anal. **2**, 1-21 (1994)

8. Christofides, D., Markström, K.: Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales. Random Struct. Algor. **32**, 88-100 (2008)

9. Chung, S.-Y., Forney, G.D., Richardson, T.J., Urbanke, R.: On the design of low-density parity-check codes within 0.0045 db of the Shannon limit. IEEE Commun. Lett. **5**(2), 58-60 (2001). https://doi.org/10.1109/4234.905935

10. Dinitz, M., Schapira, M., Valadarsky, A.: Explicit expanding expanders. Algorithmica **78**, 1225-1245 (2015)

11. Eberhard, S., Jezernik, U.: Babai's conjecture for high-rank classical groups with random generators. Invent. Math. **227**, 149-210 (2020)

12. Friedman, J.: A proof of Alon's second eigenvalue conjecture. In: Proceedings of the 35th ACM Symposium on Theory of Computing, pp. 720-724 (2003)

13. Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. **43**, 439-561 (2006)

14. Kaltofen, E.L., Lobo, A.A.: On rank properties of Toeplitz matrices over finite fields. In: International Symposium on Symbolic and Algebraic Computation (1996)

15. Li, W.-C.W., Solé, P.: Spectra of regular graphs and hypergraphs and orthogonal polynomials. Eur. J. Comb. **17**(5), 461-477 (1996)

16. Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica **8**, 261-277 (2017)

17. Matsumoto, M., Nishimura, T.: Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator **8**(1) (1998)

18. Mohanty, S., O'Donnell, R., Paredes, P.: Explicit near-Ramanujan graphs of every degree. In: Proceedings of the 52nd ACM Symposium on Theory of Computing, pp. 510-523 (2019)

19. Morgenstern, M.: Existence and explicit constructions of $q+1$ regular Ramanujan graphs for every prime power $q$. J. Comb. Theory Ser. B. **62**(1), 44-62 (1994)

20. Nilli, A.: On the second eigenvalue of a graph. Discret. Math. **91**(2), 207-210 (1991)

21. Reingold, O., Vadhan, S., Wigderson, A.: Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In: Proceedings of the 41th ACM Symposium on Theory of Computing, pp. 3-13 (2000)

22. Sabatini, L.: Random Schreier graphs and expanders. J. Algebraic Combin. **56**, 889-901 (2021)

23. Sipser, M., Spielman, D.A.: Expander codes. IEEE Trans. Inf. Theory **42**(6), 1710-1722 (1996)

24. Zemor, G.: On expander codes. IEEE Trans. Inf. Theory **47**(2), 835-837 (2001)
Thus, since $\mu_i^{2m} \ge 0$ and $\mu_1 = 1$, we get $|\mu_2| \le (\text{Trace}(M^{2m}) - 1)^{1/2m}$, which implies by Jensen's inequality

$$ \mathbf{E}(|\mu_2|) \le (n\mathbf{E}(P_{11}) - 1)^{1/2m} \quad (3) $$

Given the starting vertex (say $v_1 = f^{-1}(1)$), the random walk can be seen as the product of 2m elements of S chosen uniformly and independently at random. We denote this product $\omega = w_{2m}.w_{2m-1}\dots w_2.w_1$ and each of its matrices represents the choice of a particular neighbour for all vertices. Hence, if the first vertex on the path is $v_1$, the second will be $v_2 = s_{i_1}.v_1$ (where $s_{i_1}$ is the value of $w_1$), the third $v_3 = s_{i_2}.v_2$ (where $s_{i_2}$ is the value of $w_2$) and so on; the last vertex of the path is then $\omega.v_1$.

We reuse here the main conceptual idea of the proof in [4]. The value of $\omega.v_1$ depends on two types of random choices: on the random choice of the word $\omega = w_{2m}.w_{2m-1}\dots w_2.w_1$ where each letter is chosen at random in $\{s_1, s_1^{-1}, \dots, s_d, s_d^{-1}\}$, and the random choice of a matrix in $GL_k(\mathbb{F}_p)$ for each $s_i$. These two choices are independent. We may sample at first the words $\omega$ and only then choose the matrices $s_j$. We prefer not to sample the entire value of each $s_j$ in “one shot” but reveal the values of these matrices (better to say, the values of the linear operators corresponding to these matrices) little by little, as it is needed. Thus, starting at vertex $v_1$, instead of choosing at random in $GL_k(\mathbb{F}_p)$ the entire matrix $w_1 = s_{i_1}$, we only determine the result of the product $v_2 = s_{i_2}.v_1$. This choice does not determine completely the matrix $s_i$ but imposes a linear constraint on the matrix elements of $s_{i_1}$. The same letter $w_1$ may appear in the word $\omega$ several times. Each time the same letter $w_1$ appears in the word $\omega$ and, therefore, the matrix $s_{i_1}$ is encountered on the path, we must define the action of this matrix on some new vector $x$. We choose the result of $s_{i_1}.x$ by extending the partial definition of $s_{i_1}$, which means an extension of the linear constraints on $s_i$ fixed earlier. In a similar way, we define step by step the other matrices $s_j$ that are involved in $\omega$. We need to understand the distribution of the vector $v_{2m} = \omega.v_1$ that we obtain at the end of this procedure (and the probability of the event $v_{2m} = v_1$). In the next paragraphs we analyse this distribution.

Consider a matrix $s \in S$ that has been already encountered on the path refined by $\omega$, and we have already defined the action of $s$ on $t$ different vertices. Assume that we encounter the same matrix $s$ once again, and we must define the product $s.x$ for some one more vector $x \in (\mathbb{F}_p^k)^*$. In the permutation model, as stated in [4] this would be a uniform distribution over the $n-t$ vertices that have not been earlier assigned to the partially defined permutation $s$. However, in our construction, even if $x$ is totally new to $s$, the result of $s.x$ may not be necessarily undetermined. Indeed, if $x$ is linearly dependent from the vectors that we have already met, we would have

$$ x = \sum_{i=1}^{t} \alpha_i x_i, $$

which is a sum of vectors whose result, when multiplied by $s$, is already known. Thus,

$$ s.x = \sum_{i=1}^{t} \alpha_i s.x_i $$
would be completely determined by our previous random choices, and would not give any new information about s. Intuitively, we would say that the step that leads from x to s.x is not free. In order characterise formally what it means for a step to be free, we need to introduce the following set: let s be a matrix of S, $\omega = w_{2m}...w_1$, $v_1$ the starting vertex and $v_{j+1} = w_j v_j$. Then we define

$$ \Sigma_s(i) = \operatorname{span}(\{v_j : j < i, w_j = s\} \cup \{v_{j+1} : j < i, w_j = s^{-1}\}). $$

This is the set of vector on which the action of s is determined at step i. The image set is thus

$$ s.\Sigma_s(i) = \operatorname{span}(\{v_{j+1} : j < i, w_j = s\} \cup \{v_j : j < i, w_j = s^{-1}\}). $$

This leads to the analogous definition that is presented in [4].

**Definition 3.1** (free and forced step). We consider the i-th step in the path. Let $s = w_i$. We say that step i is forced when $v_i \in \Sigma_s(i)$. In the opposite case, we say that the step i is free.

Alternatively, instead of saying that a step i is free, we will say that the vector obtained after this step is free (namely the i + 1-th vector, $w_i v_i$). The following lemma justifies this terminology, and will be used systematically in the rest of the paper.

**Lemma 3.1.1.** Let $s = w_i$ for a step i and t be the dimension of $\Sigma_s(i)$. Then, if $v_i \notin \Sigma_s$, $v_{i+1} = s.v_i$ can be chosen uniformly at random among the $p^k - p^t$ vectors that do not belong to $s.\Sigma_s(i)$.

*Proof.* The choice of a non degenerate matrix s of size $k \times k$ is the same as the choice of an bijective linear operator from $\mathbb{F}_p^k$ to $\mathbb{F}_p^k$. To specify a linear operator, we only need to define it on vectors of any basis in $\mathbb{F}_p^k$. Let $x_1, \dots, x_t$ be a basis of $\Sigma_s(i)$. By the assumption of the lemma, vector $v_i$ is linearly independent with $x_1, \dots, x_t$. Therefore, we can let $x_{t+1} = v_i$ and then extend $x_1, \dots, x_t, x_{t+1}$ to a basis in the space $\mathbb{F}_p^k$ with some $x_{t+2}, \dots, x_k$.

To define s, we should specify one by one linearly independent vectors $y_1 = s.x_1, y_2 = s.x_2, \dots, y_k = s.x_k$. We have $p^k - 1$ possibilities to choose $y_1$ (any non zero vector), $p^k - p$ possibilities to choose $y_2$ (any vector linearly independent with the fixed $y_1$), $p^k - p^2$ possibilities to choose $y_3$ (any vector linearly independent with $y_1$ and $y_2$), and so on. In particular, if we have fixed the values $y_i = s.x_i$ for $i = 1, \dots, t$, then it remains $p^k - p^t$ available options to choose $y_{t+1}$ (which is the same as $v_{i+1}$ in our notation). □

**Remark.** This implies a sort of transitivity of the group action which is stronger than the simple transitivity, but weaker than the k-transitivity: for all $t \le k$, if $(x_1, \dots, x_t)$ and $(y_1, \dots, y_t)$ are two families of linearly independent elements of $\mathbb{F}_p^k$ then, there exists an element s of $GL_k(\mathbb{F}_p)$ such that for all $i \le t$, $s.x_i = y_i$.

As a direct consequence of this lemma, we can formulate the following corollary:

**Corollary 2.** If a matrix s appears only once in $\omega$ at step i, $s.v_i = v_{i+1}$ is chosen uniformly at random among every vertex of the graph.
Proof. Indeed, when this happens, we can rewrite $\omega$ as $AsB$ with $A$ and $B$ some invertible matrices. Then we can expose the coefficients of $A$ and $B$. The key point is that those matrices are independent from $s$, which means that we still have no information about $s$. This way, since $v_i = B.v_1$, we have $\mathbf{P}(\omega.v_1 = v_1) = \mathbf{P}(s.v_i = A^{-1}v_1) = \frac{1}{n}$. $\square$

The probability we have just found is conditioned by the structure of $\omega$, hence it needs to be multiplied by the probability of the condition. This is only dependent on the properties of $\omega$ which can be seen as an element of a free group generated by the set $\{s_1, \dots, s_d\}$. Let us remind that $\omega$ can be seen as a words whose letters are taken from $\{s_1, s_1^{-1}, \dots, s_d, s_d^{-1}\}$. In order to estimate the total probability of having a closed walk, we subdivide the space of such words in a few events whose probabilities will be determined. Those events are chosen so the conditional probability is more convenient to estimate. This will be done later. Let us define our events:

* $X_1$: “at least one letter appears exactly once”

* $X_2$: $\overline{X_1} \wedge \overline{X_1}$ “at least one letter appears exactly twice with same sign”

* $X_3$: “no letter appears once or twice, at least one letter appears exactly three times”

* $X_4$: “no letter appears once, twice, nor three times”

* $X'_2$: $\overline{X_1} \wedge \overline{X_3} \wedge \overline{X_4}$ “all letters that appear exactly twice have different sign”

These events form a partition of the set of all possible words, whose size is $(2d)^{2m}$. In order to finish the proof of Theorem 3, let us leave aside all the events but $X_1$ and consider its complementary. We bound their probability using an argument similar to that of [2]. We observe that a word that belongs to $\overline{X_1}$ has at most $m$ different letters in it, hence we have at most $\binom{d}{m}$ ways of choosing those letters in the alphabet. When choosing each letter at random, the probability that all of them are in the right set is $(\frac{m}{d})^{2m}$. Hence

$$ \mathbf{P}(\overline{X_1}) \le \binom{d}{m} \left(\frac{m}{d}\right)^{2m} \le \left(e \frac{d}{m}\right)^m \left(\frac{m}{d}\right)^{2m} = \left(e \frac{m}{d}\right)^m. $$

The probability we are looking for is then

$$ \begin{aligned} \mathbf{P}(\omega.v_1 = v_1) &= \mathbf{P}(\omega.v_1 = v_1|X_1)\mathbf{P}(X_1) + \mathbf{P}(\omega.v_1 = v_1|\overline{X_1})\mathbf{P}(\overline{X_1}) \\ &\le \mathbf{P}(\omega.v_1 = v_1|X_1) + \mathbf{P}(\overline{X_1}) \le \frac{1}{n} + \left(e \frac{m}{d}\right)^m. \end{aligned} $$

We set $m = \ln n$ to minimise the bound. Substituting the above quantity back into equation 3 completes the proof of Theorem 3.

In order to find a tighter bound, we use a more careful analysis. We consider again all of our events. We are going to represent the probability $P(\omega.v_1 = v_1)$ as the sum

$$ P(\omega.v_1 = v_1 | \omega \in X_1) \cdot P(X_1) + \dots + P(\omega.v_1 = v_1 | \omega \in X_4) \cdot P(X_4) \\ + P(\omega.v_1 = v_1 | \omega \in X'_2) \cdot P(X'_2). $$
For $i = 1, 2, 3$ and $4$ we estimate separately $P(X_i)$ and $P(\omega.v_1 = v_1 | \omega \in X_i)$, and we estimate the value of the product $P(\omega.v_1 = v_1 | \omega \in X'_2) \cdot P(X'_2)$ as a whole. The sum of these bounds result in the proof of Theorem 1.

The events $X'_2$ and $X_4$ together involve one particular event that implies a closed walk with probability 1. This event is the “collapse” of the whole word to the identity matrix. It happens when iterating the reduction operation $(Ass^{-1}B \mapsto AB$ for all invertible matrices $A, s$ and $B)$ ends up with the identity matrix. The probability of this event denoted $C$ is analysed in [4] (lemma 2):

$$ \mathbf{P}(C) = \binom{2m+1}{m} \frac{(2d)^m}{2m+1} \left(\frac{1}{2d}\right)^{2m} \le \left(\frac{2}{d}\right)^m $$

This is proven by counting the number of well parenthesized words of size $2m$ (Catalan number) with $d$ different type of parenthesis. We wish to bound the probability of having a closed walk when $\omega$'s structure is such that this event cannot happen.

We express the size of these sets using a more general recursive formula. Let $X_q(c, l, d)$ be the size of the set of all words of length $l$, on the alphabet that consists of $d$ letters and its negations, such that at least $c$ letters appear (with the positive or negative sign) in this word $q$ times, and the other letters that appear in it have more occurrences. Then

$$ X_q(c, l, d) = \sum_{i=c}^{\lfloor \frac{l}{q} \rfloor} \binom{d}{i} \prod_{j=0}^{i-1} 2^q \binom{l-qj}{q} X_{q+1}(0, l-qi, d-i) $$

Indeed, $2^q \binom{l}{q}$ is the number of ways to place $q$ times the same letters in a word of size $l$ (each letter can have positive or negative sign). Thus, $\prod_{j=0}^{i-1} 2^q \binom{l-qj}{q}$ is the number of ways of repeating $i$ times this operation while removing at every step $q$ free places. It simplifies as follows

$$ \prod_{j=0}^{i-1} 2^q \binom{l-qj}{q} = \left(\frac{2^q}{q!}\right)^i \prod_{j=0}^{i-1} \frac{(l-qj)!}{(l-qj-q)!} = \left(\frac{2^q}{q!}\right)^i \frac{l!}{(l-qi)!} $$

Note that $X_q(0, 0, d) = 1$ because we only have one way of placing no letters in a word of size 0. Moreover, if $q > l$ then $X_q(c, m, d) = 0$, since the $q$ letters cannot fit in the word. Using these observations, we have a complete recursive definition of $X_q(c, l, d)$,

$$ X_q(c, l, d) = \begin{cases} 1 & \text{if } c = 0 \text{ and } l = 0 \\ 0 & \text{if } q > l \\ \sum_{i=c}^{\lfloor \frac{l}{q} \rfloor} \binom{d}{i} \left(\frac{2^q}{q!}\right)^i \frac{l!}{(l-qi)!} X_{q+1}(0, l-qi, d-i) & \text{otherwise.} \end{cases} $$

Then we get

$$ |X_1| = X_1(1, 2m, d), $$

$$ |X_3| = X_3(1, 2m, d) $$

and

$$ |X_4| = X_4(0, 2m, d). $$
One can notice that $|X_3 \cup X_4| = |X_3| + |X_4| = X_3(0, 2m, d)$.

Since there are $4^i - 2^i$ possibilities for choosing the sign of $i$ pairs so that the letters of at least one of them have same sign, the number of ways of placing these pairs in the word is $\binom{d}{i}(4^i - 2^i) \prod_{j=0}^{i-1} \binom{2m-2j}{2} = \binom{d}{i}(2^i - 1) \frac{(2m)!}{(2m-2i)!}$. Hence

$$|X_2| = \sum_{i=1}^{m} \binom{d}{i} (2^i - 1) \frac{(2m)!}{(2m-2i)!} X_3(0, 2m-2i, d-i).$$

Similarly, there are $2^i$ ways of choosing the sign of $i$ pairs of letter so that all pairs are of different sign. Thus we get

$$|X'_2| = \sum_{i=1}^{m} \binom{d}{i} \frac{(2m)!}{(2m-2i)!} X_3(0, 2m-2i, d-i).$$

This can be summarized with the relation $X_2(1, 2m, d) = |X_2| + |X'_2|$.

We have already explained that $\mathbf{P}(\omega.v_1 = v_1|X_1) = \frac{1}{n}$. It remains to bound this probability conditioned to the other events. In what is next, we will set $p = 2$. Taking a bigger field might weaken the bounds and complicate the analysis. We start with $X_2$.

**Lemma 3.1.2.**

$$\mathbf{P}(\omega.v_1 = v_1|X_2) \le \frac{2}{n}.$$

*Proof.* Let $s$ be the matrix that appears twice with same sign. The word is then of the form $AsBsC.v_1 = v_1$ with $A, B$ and $C$ some invertible matrices of known coefficients. We can rewrite this equation as $sBs.x = y$ with $x$ and $y$ two determined vectors ($x = C.v_1$ and $y = A^{-1}.v_1$). It is useful to name the different vectors of the product:

$$s \overbrace{\underbrace{B}_{y''} \underbrace{s.x}_{y'}}^{x'} = y.$$

Since we are in the field of size two there is no non-trivial pairs of parallel vectors. Hence the step that leads to $y''$ is free only if $x' \neq x$. In a larger field ($p > 2$), for $y''$ to be free, it is necessary that $x \neq \alpha x'$ for all non zero $\alpha \in \mathbb{F}_p$. By taking $p = 2$, a lot of case-by-case analysis is avoided.

Because $y'$ is necessarily free and since $x$ and $x' = B.y'$ are independent, $\mathbf{P}(x' = x) = \frac{1}{n}$. Then, if $x' = x$, we have $y'' = y'$. This is the probability that $y''$ is forced. If this is not the case, namely if $x' \neq x$ (which happens with probability $\frac{n-1}{n}$), then the probability for $y''$ to be equal to $y$ is at most $\frac{1}{n-1}$ ($y''$ cannot be equal to $y'$ since both steps are free). Therefore,

$$\mathbf{P}(\omega.v_1 = v_1|X_2) \le \frac{1}{n} + \frac{n-1}{n} \frac{1}{n-1} = \frac{2}{n}.$$

□

Now we bound the probability $\mathbf{P}(\omega v_1 = v_1|X_3)$. We proceed the same way as above, by distinguishing the cases where the final step is free or not. We prove the following claim:
**Lemma 3.1.3.**

$$ P(\omega.v_1 = v_1|\text{"at least a letter appears exactly three times"}) \le \frac{5}{n}. $$

In particular, we have

$$ P(\omega.v_1 = v_1|X_3) \le \frac{5}{n}. $$

*Proof.* Under the $X_3$ condition, the word can take four forms that will be analysed separately:

* $sBsCs.x = y$

* $s^{-1}BsCs.x = y$

* $sBs^{-1}Cs.x = y$

* $sBsCs^{-1}.x = y$

Any other form can be turned into one of the above by switching $s$ with $s^{-1}$, which does not change the argument. The different possibilities can be summarized by writing $s_1Bs_2Cs_3.x = y$; at most one of $s_1, s_2, s_3$ is $s^{-1}$ and the others are $s$. We will use the notation below to treat all four cases:

$$ \underbrace{s_1 \quad B \quad s_2 \quad C \quad s_3 \quad x}_{y''} = y. $$

We start with the case in which there is no $s^{-1}$ in $\omega$. Here, the step that leads to $y'''$ is free only if $x'' \ne x$, $x'' \ne x'$ and $x'' \ne x' + x''$ (that is, $x''$ is not a linear combination of $x'$ and $x$). Since $x'$ and $x$ are independent, $P(x' = x) = \frac{1}{n}$. Hence, with probability $\frac{n-1}{n}$ we get that $y''$ is free, which means that $x'' = B.y''$ is uniformly distributed among the $n-1$ vectors different from $B.y'$. There are three values for $x''$ that make the final step forced and they are equally likely, thus $P(y'''$ is forced $|x' \ne x) \le \frac{3}{n-1}$. The opposite case happens with probability $\frac{n-4}{n-1}$. Then $P(y''' = y) \le \frac{1}{n-3}$. To illustrate the reasoning, we can represent those probabilities by a tree:
<figure><img src="image_5.png" /></figure>

The rightmost leaf corresponds to $y'''$ being free which gives a probability $\frac{1}{n-3}$ of having a closed walk. Therefore,

$$ \mathbf{P}(sBsCs.x = y) \leq \frac{1}{n} + \frac{n-1}{n} \left( \frac{3}{n-1} + \frac{n-4}{n-1} \frac{1}{n-3} \right) \leq \frac{5}{n}. $$

Now, consider $s_3 = s^{-1}$. Then $y''$ is forced if $x' = y'$, but those two vectors are correlated, so we cannot bound the probability of this event. We will consider both cases and take the probability of the most likely event as a bound. If $y' = x'$, then $y''$ is forced, which implies that $y'' = x$. In this case, if $x'' = y'$ we have $y''' = x$. However, $x'' = B.x$, which is independent from $y'$ (which is from a free step). Hence, the probability for them to be equal is $\frac{1}{n}$. In the opposite case, $y'''$ is free, which gives a total probability of this branch of $\frac{2}{n}$. We now suppose that $y''$ is free. Then, with probability $\frac{3}{n-1}$, $y'''$ is forced. In the other case, $y'''$ is equal to $y$ with probability at most $\frac{1}{n-3}$. Here is the probability tree:

<figure><img src="image_6.png" /></figure>

The branches whose probabilities are close to 1 corresponds to the cases when
$y'''$ is free. Thus we have

$$ \mathbf{P}(sBsCs^{-1}.x = y) \leq \max\left(\frac{2}{n}, \frac{3}{n-1} + \frac{n-4}{n-1}\frac{1}{n-3}\right) \leq \frac{4}{n-1}. $$

When $s_2 = s^{-1}$ the choice of $y''$ is forced if $x' = y'$, which implies $x'' = B.x$. Then $s$ is defined only on $x$. If $B.x = x$ then, since $y'$ is free, $\mathbf{P}(y''' = y) = \mathbf{P}(y' = y) = \frac{1}{n}$. Otherwise, $y'''$ is free, and therefore $\mathbf{P}(y''' = y) = \frac{1}{n-1}$. On the other hand, if $y''$ is free, then $s$ is defined on $x$ and $y''$. Since $y''$ is free, $x''$ and $x$ are independent, thus $\mathbf{P}(x'' = x) = \frac{1}{n-1}$. Moreover, if $x'' = y''$, $\mathbf{P}(y''' = y) = \mathbf{P}(x' = y) = \frac{1}{n}$. If $x'' = y'' + x$, we have $y''' = x' + y' = (C + Id_k)y'$ which is independent from $y$. Hence, $\mathbf{P}(y''' = y) = \frac{1}{n}$. Otherwise, since three vectors are excluded, $y'''$ is free with probability at most $\frac{n-3}{n}$. If so, $\mathbf{P}(y'' = y) = \frac{1}{n-3}$. As before, the case study can be illustrated with a tree:

<figure><img src="image_7.png" /></figure>

Thus, we get

$$ \mathbf{P}(sBs^{-1}Cs.x = y) \leq \max\left(\frac{2}{n-1}, \frac{3}{n-1} + \frac{n-2}{n-1}\left(\frac{n-3}{n-2}\frac{1}{n-3}\right)\right) = \frac{4}{n-1}. $$

Lastly, we consider the case $s_1 = s^{-1}$. Here, $y''$ is forced when $x' = x$. Those are not correlated, so this event happens with the probability $\frac{1}{n}$. In the other case, $s^{-1}$ is defined on $y''$ and $y'$, which are random. If $x'' = y''$, we have $y''' = x'$ which is equal to $y$ with probability less than $\frac{1}{n-1}$. Since $y''$ is free, $y'$ and $y''$ are independent, hence $\mathbf{P}(x'' = y') = \mathbf{P}(x'' = y' + y'') = \frac{1}{n-1}$. If $y'''$ is free, it can take any value with probability $\frac{1}{n-3}$. The last probability tree is then
<figure><img src="image_8.png" /></figure>

Hence we have

$$ \mathbf{P}(s^{-1}BsCs.x = 1) \le \frac{1}{n} + \frac{n-1}{n} \max \left( \frac{1}{n-2}, \frac{1}{n-2} + \frac{n-4}{n-2} \frac{1}{n-3} \right) \le \frac{5}{n}. $$

By taking the maximum of all these bounds, we conclude the proof. □

It remains to bound $\mathbf{P}(\omega.v_1 = v_1|X'_2)\mathbf{P}(X'_2)$. To simplify the notations we set $x_3(i) = X_3(1, 2m - 2i, d - i)$ and $x_4(i) = X_4(0, 2m - 2i, d - i)$. We need to prove the following statement.

**Lemma 3.1.4.**

$$ \mathbf{P}(\omega.v_1 = v_1|X'_2)\mathbf{P}(X'_2) \le \left(\frac{1}{2d}\right)^{2m} \sum_{i=1}^{m} \binom{d}{i} \frac{(2m)!}{(2m-2i)!} \left[ \frac{x_3(i) + x_4(i)}{n} + \frac{2^i}{(i+1)!} \left( \frac{5}{n}x_3(i) + x_4(i) \right) \right]. \quad (4) $$

*Proof.* Before we proceed with the proof of this lemma we stress again that in this statement we do not bound separately $\mathbf{P}(X'_2)$ and $\mathbf{P}(\omega.v_1 = v_1|X'_2)$, we estimate directly the product of these two probabilities, which equals to the probability of the event

$$ \mathbf{P}(\omega.v_1 = v_1 \text{ and } \omega \in X'_2). $$

The probability is taken, as usual, over the random choice of a word $\omega$ of 2m letters and the random choice of invertible matrices assigned to the letters of this alphabet.

We start the proof with two claims.

*Claim 1:* Assume that the word $\omega$ contains letters $t$ and $s$ exactly twice, and each of these letters appears once with the positive and once with the negative sign, and these letters interleave:

$$ \omega = \dots t \dots s \dots t^{-1} \dots s^{-1} \dots \quad (5) $$

Then the probability to get a closed walk corresponding to the path $\omega$ (probability taken over the choice of matrices for each letter in the alphabet) is equal to $1/n$. The claim remains true if we swap the positions of the pair of letters $s$ and $s^{-1}$ and/or of the pair of letters $t$ and $t^{-1}$.
*Proof of the claim.* Words from $X'_2$ are all of the form $AsBs^{-1}C$ with A, B and C some invertible matrices. Hence, we wish to estimate the probability of the event $sBs^{-1}.x = y$, with $x = C.v_1$, and $y = A^{-1}.v_1$. We use the notation

$$ \underbrace{s \quad B \quad s^{-1} \cdot x}_{y'} = y. $$

Here, the matrix $t$ is a factor of $B$ (hence $B = \dots t \dots$). We first suppose that $x = y$. Then, if $x' = y'$ we have $y'' = x = y$. Since $t$ appears in $B$, $x'$ is independent of $y'$, and thus $P(y' = x') = \frac{1}{n}$ (because this is the first time $t$ is used in the path). In the opposite case, we have $y'' \neq y$, and the path cannot be closed.

Now we suppose $x \neq y$. Then if $y' = x'$ we have $y'' = x \neq y$. If $y' \neq x'$ (which happens with probability $\frac{n-1}{n}$, $y''$ is free, and its value is uniformly distributed among the $n-1$ remaining vectors. Therefore, when we have this configuration of random matrices in $\omega$, the probability of having a closed walk is $\frac{1}{n}$. $\square$

It can be noticed that here, the fact that $t$ appears with different sign is not used.

*Claim 2: Let us take the set of $2i$ literals*

$$ \{s_1, s_1^{-1}, \dots, s_i, s_i^{-1}\} $$

and consider the set of all words of length $(2i)$ composed of these literals (each one should be used exactly once). We claim that the fraction of words that represent a well formed structure of $i$ pairs of parentheses, where each pair is associated with some pair of literals $(s_j, s_j^{-1})$ or $(s_j^{-1}, s_j)$, is equal to $\frac{2^i}{(i+1)!}$.

*Proof of claim.* In general, we have $(2i)!$ different ways to distribute $(2i)$ literals among $(2i)$ positions. Let us count the fraction of permutations where the literals form a structure of $i$ pairs of parentheses. The number of well parenthesized words (with one type of parentheses) of size $2i$ is the Catalan number $\binom{2i+1}{i} \frac{1}{2i+1}$. We have $i!$ ways to assign each pair of parentheses with one of $i$ types of literals, and $2^i$ to choose the signs in each pairs $(\dots s_j \dots s_j^{-1} \dots$ or $\dots s_j^{-1} \dots s_j \dots$ for each of $i$ pairs). Hence, the proportion of the well parenthesized words is

$$ \frac{\binom{2i+1}{i} \frac{1}{2i+1} i! 2^i}{(2i)!} = \frac{(2i+1)! i! 2^i}{(2i+1)! i! (i+1)!} = \frac{2^i}{(i+1)!}. $$

$\square$

It is easy to see that the absence of pattern 5 is equivalent to having such well formed structure of parenthesis.

Let us proceed with the proof of the lemma. By definition, in each word $\omega \in X'_2$ all letters that appear exactly twice must have different signs. In what follows we denote $i$ that number of letters that appear in $\omega$ exactly twice. For a fixed $i$, to specify a word $\omega$ where $i$ letters appear twice (with opposite signs) and the other letters appear at least three times, we should
* choose $i$ letters among $d$ (those who appear exactly twice), which gives $\binom{d}{i}$ combinations;

* choose $2i$ positions in the word $\omega$ of length $2m$ where we place the letters that appear twice, which gives $\binom{2m}{2i}$ combination;

* fix a permutations of the $(2i)$ literals on the chosen $(2i)$ positions, which gives $(2i)!$ combinations;

* fill the remaining $(2m - 2i)$ positions of $\omega$ with other letters, using each letter at least three times; we subdivide these combinations into two sub-cases:

- there is at least one letter that is used exactly three times; we have $x_3(i) = X_3(1, 2m - 2i, d - i)$ possibilities to do it;

- there is no letter that is used exactly three times, i.e., each letter (besides the $i$ letters that were used twice) must be used at least four times; we have $x_4(i) = X_4(0, 2m - 2i, d - i)$ possibilities to fill in this way the remaining $(2m - 2i)$ positions.

The $i$ pairs of letters in $\omega$ contain the pattern (5) may contain or not contain the pattern (5). By Claim 2, the latter is the case for the fraction $\frac{2^i}{(i+1)!}$ of all $\omega$ (with $i$ pairs) and, respectively, the former is the case for the fraction $1 - \frac{2^i}{(i+1)!}$ of these words.

If the $i$ pairs of letters in $\omega$ contain the pattern (5), then by Claim 1 the probability that $\omega$ provides a closed path is at most $\frac{1}{n}$ (probability taken over the choice of matrices for each letter in the alphabet). Since we have in total $(2d)^{2m}$ words $\omega$, this case contributes to the resulting probability $P(\omega.v_1 = v_1$ and $\omega \in X'_2)$ at most

$$ \left(\frac{1}{2d}\right)^{2m} \binom{d}{i} \binom{2m}{2i} (2i)! \left(1 - \frac{2^i}{(i+1)!}\right) (x_3(i) + x_4(i)) \cdot \frac{1}{n} $$

(in what follows we bound $1 - \frac{2^i}{(i+1)!}$ by 1).

If the $i$ pairs of letters in $\omega$ do not contain the pattern (5) but one of other letters appear in $\omega$ exactly three times, then the probability to have a closed path is at most $\frac{5}{n}$, as shown in Lemma 3.1.3. This case contributes to the resulting probability at most

$$ \left(\frac{1}{2d}\right)^{2m} \binom{d}{i} \binom{2m}{2i} (2i)! \cdot \frac{2^i}{(i+1)!} \cdot x_3(i) \cdot \frac{5}{n} $$

At last, if $\omega$ does not contain the pattern (5) and all other letters appearing in $\omega$ are used more than three times, then we trivially bound the probability to have a closed path by 1. This contributes to the resulting probability

$$ \left(\frac{1}{2d}\right)^{2m} \binom{d}{i} \binom{2m}{2i} (2i)! \cdot \frac{2^i}{(i+1)!} \cdot x_4(i). $$

Summing these quantities for all possible values of $i$ and observing that $\binom{2m}{2i}(2i)! = \frac{(2m)!}{(2m-2i)!}$, we obtain the statement of the lemma. $\square$

<figure><img src="image_9.png" /></figure>
We proceed with similar bounds for the other sets of words:

$$ \mathbf{P}(\omega v_1 = v_1 | X_1) \mathbf{P}(X_1) \leq \frac{1}{n} \left( \frac{1}{2d} \right)^{2m} |X_1|, $$

$$ \mathbf{P}(\omega v_1 = v_1 | X_2) \mathbf{P}(X_2) \leq \frac{2}{n} \left( \frac{1}{2d} \right)^{2m} |X_2|, $$

$$ \mathbf{P}(\omega v_1 = v_1 | X_3) \mathbf{P}(X_3) \leq \frac{5}{n} \left( \frac{1}{2d} \right)^{2m} |X_2|, $$

and

$$ \mathbf{P}(\omega v_1 = v_1 | X_4) \mathbf{P}(X_4) \leq \left( \frac{1}{2d} \right)^{2m} |X_4|. $$

The sum of these expressions is larger than $P_{11}$ defined at the beginning of this section. By replacing it in equation 3, we complete the proof. It is easy to see that the rough bounding used in the proof of Theorem 3 gives a larger bound than that of Theorem 2.

## 3.2 Proof of Theorem 2

We now can adapt this proof to get a similar bound for $d$-regular bipartite graphs. Let $G = Sch_{BP}(Gl_k(\mathbb{Z}_2) \circledast (\mathbb{Z}_2^k)^*, D)$ and $M$ be its normalised adjacency matrix. In order to associate its coordinate to vertices we can proceed as in the preceding section by mapping surjectively $[1, 2(2^k - 1)]$ to $(\mathbb{Z}_2^k)^*$, taking care of distinguishing the vectors of the first and the second partition. Here, we set $2n = 2(2^k - 1)$, the number of vertices in the graph. Let us start by adapting the trace method to the bipartite graphs. One can remark that the adjacency matrix of $G$ is of the form

$$ M = \left( \begin{array}{c|c} 0 & A \\ \hline tA & 0 \end{array} \right) $$

where $tA$ is the transposition of $A$. In a bipartite graph, it is known that the spectrum $|\mu_1| \ge \dots \ge |\mu_{2n}|$ is symmetric with respect to zero. Hence for $1 \le i \le n$, we have $|\mu_{2i+1}| = |\mu_{2(i+1)}|$. This way we get

$$ \sum_{i=0}^{n-1} 2\mu_{2i+1}^{2m} = \mathrm{Trace}(M^{2m}). $$

In order to study the spectral gap, the relevant quantity to estimate is then $|\mu_3| = |\mu_4|$. Since $|\mu_1| = |\mu_2| = 1$, we thus obtain

$$ 2\mu_3^{2m} \leq \sum_{i=1}^{n-1} 2\mu_{2i+1}^{2m} = \mathrm{Trace}(M^{2m}) - 2. $$

As we have seen in section 3.1, the expected value of $\mathrm{Trace}(M^{2m})$ is the sum of the probability of getting of closed path of size $2m$, starting on each vertex.
We note this probability $P_{ii}$ for the vertex $i$. It is the same for every vertex, hence we get, by using Jensen's inequality

$$ \mathbf{E}(|\mu_3|) \le \left( \frac{1}{2} (\mathbf{E}(\text{Trace}(M^{2m}))) - 2 \right)^{\frac{1}{2m}} = (nP_{11} - 1)^{\frac{1}{2m}}. \quad (6) $$

One can notice that here, $n$ is the size of the partition, not the size of the graph. Indeed, with an even number of steps, the path must end in the same partition as it started, which eliminates half of the vertices.

We first explain why the construction for even degree regular bipartite graphs gives the same bound as Theorem 1. Here, a random walk can be represented as a sequence of matrices of $D \cup D^{-1}$. This is because every vertex $x$ is connected to $s.x$ and $s^{-1}.x$. Each element of the sequence is chosen independently of the others. It is then easy to see that the structure of the walk is exactly the same as in the non bipartite case: a uniformly random sequence of $2m$ matrices from $D \cup D^{-1}$. The same proof can then be applied to this sequence, the elements of the sequence will then behave the same way as in the preceding section.

However, some work needs to be done for graphs of odd degree. In order to apply here a similar reasoning as in the previous section, we need to understand what a random walk in $G$ looks like in terms of the matrices of $D$.

<figure><img src="image_10.png" /><figcaption>Figure 4: The steps of the random walk work by pairs of matrices of $D$; the first one brings us on a vertex of the right hand side, the other is for the way back.</figcaption></figure>

In a bipartite regular graph obtained by our construction, a random walk of size $2m$ is a sequence $\omega$ of elements of $D$ chosen independently at random. As usual, every edge in the graph corresponds to some invertible matrix. In the case of a bipartite graph we assume that the multiplication by the matrices transforms the vertices in the left part into the vertices of the right part. Thus, in a random walk on such a graph, the matrices that appear in an odd position in $\omega$ are taken with the positive sign, while the matrices that appear in an even step are taken with the negative sign, see Fig. 4.

We wish to proceed as in the preceding section, by partitioning the set of possible sequences (words) so that we can analyse the probability of having a closed walk conditioned to the sets this partition. In order to reuse the results above, we choose a similar partitioning. There is a minor difference: now the signs of matrices appearing in $\omega$ are fixed (positive for odd position and negative for the others). Hence, the number of possible words is $d^{2m}$. We define the sets before determining their size:

* $Y_1$: “at least one letter appears exactly once”
• $Y_2: \bar{Y}_1 \wedge \text{"at least one letter appears exactly twice"}$

• $Y_3: \text{"no letter appear once or twice, at least one letter appears exactly three times"}$

• $Y_4: \text{"no letter appear once, twice, nor three times"}$

Up to this point, it is not hard to understand why the bound of Theorem 3 holds. Indeed, the sign of the matrices do not play any role in the proof, so the probability of $\bar{Y}_1$ can be bounded by the same quantity as in the previous section. In addition, the probability of having a closed walk conditioned to $Y_1$ is also $\frac{1}{n}$ ($n$ is the size of a partition). Therefore, Theorem 3 applies to bipartite regular graphs.

We can define the analogous recursive relation used in the preceding part. Since this formula represents a quantity that does not depend on the sign of the letters (they are determined by the parity of the positions), we can just ignore them:

$$ Y_q(c, l, d) = \begin{cases} 1 & \text{if } c=0 \text{ and } l=0 \\ 0 & \text{if } q > l \\ \sum_{i=c}^{\lfloor \frac{l}{q} \rfloor} \binom{d}{i} (q!)^{-i} \frac{l!}{(l-qi)!} Y_{q+1}(0, l-qi, d-i) & \text{otherwise.} \end{cases} $$

As before, $Y_q(c, l, d)$ is the number of words of size $l$ on alphabet of size $d$ that have at least $c$ different letters that appear $q$ times and whose other present letters have more occurrences. The only difference with $X_q(c, l, d)$ is that we do not deal with signs. For the same reason, we have

$$ |Y_1| = Y_1(1, 2m, d), $$

$$ |Y_2| = Y_2(1, 2m, d), $$

$$ |Y_3| = Y_3(1, 2m, d) $$

and

$$ |Y_4| = Y_4(0, 2m, d). $$

We have already shown that when one letter appears exactly once, the probability of having a closed walk is $\frac{1}{n}$. Similarly, when a letter appears exactly three times, the probability of getting a closed walk is less than $\frac{5}{n}$. Indeed, in the proof of Lemma 3.1.3, all possible configurations of signs for the letter that appears three times are considered (e.g. $\omega = \dots s \dots s^{-1} \dots s \dots$ or $\dots s \dots s \dots s^{-1} \dots$). No assumption is done on their respective probabilities to occur. These probabilities may or may not be different in the bipartite setting. Since this bound ($\frac{5}{n}$) is the maximum over all the probabilities of getting a closed walk with each configuration of signs, the resulting bound for the probability of getting a closed walk in the bipartite case remains the same. Hence we get

$$ \mathbf{P}(\omega.v_1 = v_1|Y_1)\mathbf{P}(Y_1) \le \left(\frac{1}{d}\right)^{2m} Y_1(1, 2m, d)\frac{1}{n} $$

and

$$ \mathbf{P}(\omega.v_1 = v_1|Y_3)\mathbf{P}(Y_3) \le \left(\frac{1}{d}\right)^{2m} Y_3(1, 2m, d)\frac{5}{n}. $$
As before, we do not bound the probability of getting a closed walk under condition $Y_4$. Then

$$ \mathbf{P}(\omega.v_1 = v_1|Y_4)\mathbf{P}(Y_4) \leq \left(\frac{1}{d}\right)^{2m} Y_4(0, 2m, d). $$

We now estimate $\mathbf{P}(\omega.v_1 = v_1|Y_2)\mathbf{P}(Y_2)$. We set $y_3(i) = Y_3(1, 2m-2i, d-i)$ and $y_4(i) = Y_4(0, 2m-2i, d-i)$.

**Lemma 3.2.1.**

$$ \mathbf{P}(\omega.v_1 = v_1|Y_2)\mathbf{P}(Y_2) \leq Y_2(1, 2m, d)\frac{2}{n} + \sum_{i=1}^{m}\binom{d}{i}\left(\frac{1}{2}\right)^i\frac{(2m)!}{(2m-2i)!(i+1)!}\left(y_3(i)\frac{5}{n} + y_4(i)\right) \quad (7) $$

*Proof.* We proceed in a similar way as in the proof of lemma 3.1.4. Consider we have $i$ pairs of matrices that appear exactly twice in $\omega$. In the bipartite setting, the signs are forced by the parity of the position of each letter. We thus choose to ignore them. Then, the probability of having no pair $(s, t)$ such that we have the pattern $\omega = \dots s \dots t \dots s \dots t \dots$ is $\frac{2^i}{(i+1)!}$. The proof is the same as that of claim 2 in Lemma 3.1.4, except that the numerator and the denominator of the fraction are both divided by $2^i$ (because we ignore the signs).

Using the proof of Lemma 3.1.2, we conclude that, if a letter appears twice with the same sign, the probability of having a closed walk is less than $\frac{2}{n}$. If there is a pair $(s, t)$, $\omega = \dots s \dots t \dots s^{-1} \dots t^{-1} \dots$, then, by using the argument from lemma 3.1.4 (claim 1), the probability of getting a closed walk is $\frac{1}{n}$. If those cases do not happen, we still can bound the probability of getting a closed walk using lemma 3.1.3 when at least a letter appears three times. The conditional probability of getting a closed walk is then less than $\frac{5}{n}$.

Let us combine together all these bounds.

* The union of the event in which a letter appears exactly twice with same sign, and the event where the letters that appear twice form a bad parenthesized word (if we forget about the signs) has size smaller than $Y_2(1, 2m, d)$. The probability of getting a closed walk in this case is not greater than $\frac{2}{n}$.

* The size of the event in which this bound does not apply, but we can apply the bound from lemma 3.1.3 (which is $\frac{5}{n}$) can be computed as follows. $(2i)! \binom{2m}{2i}$ is the number of ways of placing $i$ pairs of letters with different sign in $2m$ positions. Since we ignore the sign, this quantity has to be divided by $2^i$ which gives $(\frac{1}{2})^i \frac{(2m)!}{(2m-2i)!}$. A fraction $\frac{2^i}{(i+1)!}$ of them are well formed. $y_3(i)$ is the numbers of ways of filling the remaining gaps so that no letter appear once nor twice, and at least letter appears three times. Choosing the $i$ pairs among the $d$ possible ones and summing over all $i \leq 2m$, we get

$$ \sum_{i=1}^{m} \binom{d}{i} \left(\frac{1}{2}\right)^i \frac{(2m)!}{(2m-2i)!(i+1)!} y_3(i). $$
• Similarly, the number of remaining words that correspond to walks whose probability of being closed is not estimated is

$$ \sum_{i=1}^{m} \binom{d}{i} \left(\frac{1}{2}\right)^i \frac{(2m)!}{(2m-2i)!(i+1)!} y_4(i). $$

Summing all these quantities, multiplying them by their respective probabilities of getting a closed walk and dividing the whole expression by the number of possible words (that is $d^{2m}$), we can conclude.

□

Summing all the above probabilities and substituting this in 6 finishes the proof of Theorem 2.

## 3.3 Proof of Corollary 1

We now turn to bound the second largest eigenvalue for biregular graphs. Let

$$ G = Sch_{BP}(GL_k(\mathbb{Z}_p) \circledast (\mathbb{Z}_p^k)^*, D, \gamma). $$

We note $n_1 = p^k - 1$, the size of the first partition, $n_2 = \frac{n_1}{\gamma}$ the size of the second one, and $\gamma = \frac{d_2}{d_1}$, thus $d_1$ and $d_2$ are the respective degrees of each partition of the graph. Let

$$ P = \left( \begin{array}{c|c} 0 & M \\ \hline M & 0 \end{array} \right) $$

be its adjacency matrix. Hence $M$ has dimension $n_1 \times n_2$. Let

$$ Q = \left( \begin{array}{c|c} 0 & A \\ \hline A & 0 \end{array} \right) $$

the adjacency matrix of

$$ G' = Sch_{BP}(GL_k(\mathbb{Z}_p) \circledast (\mathbb{Z}_p^k)^*, D), $$

which is the bipartite regular graph before merging the vertices of the right partition. We set $J$ such that $M.^tM = A.J.^tA$, thus $J = I_{n_2} \otimes J_\gamma$, where $J_\gamma$ is the $\gamma \times \gamma$ matrix whose entries are only ones and $\otimes$ is the Kronecker product. An example of resulting paths is shown in Fig. 5.

We set $A = (a_{ij})_{i,j \in [1, n_1]}$. All $A$'s columns and rows sum up to $d_1$ —so does $^tA$. We can show that for every $x = (x_1, \dots, x_{n_1})$ orthogonal to $e_1 = \frac{1}{\sqrt{n_1}}(1, \dots, 1)$, $Ax$ is also orthogonal to $e$. Indeed, the coordinates of such an $x$ sum up to zero. We denote $Ax = (y_1, \dots, y_{n_1})$. Then

$$ \sum_{i=1}^{n_1} y_i = \sum_{i=1}^{n_1} \sum_{j=1}^{n_1} a_{ij}x_j = \sum_{j=1}^{n_1} x_j \sum_{i=1}^{n_1} a_{ij} = d_1 \sum_{j=1}^{n_1} x_j = 0. $$

Therefore, $Ax$ is orthogonal to $e$. The same is true for $^tAx$.

On the other hand, it is easy to see that the spectrum of $J$ is

$$ \underbrace{(\gamma, \dots, \gamma)}_{n_2} \underbrace{0, \dots, 0}_{n_1 - n_2}. $$
<figure><img src="image_11.png" /><figcaption>Figure 5: Traveling three steps starting from the left in this directed graph is equivalent to doing two steps in the bipartite graph (starting from the left as well) with merged vertices on the right. The merging operation is represented by $J$ which corresponds to the complete bipartite graphs in the middle. Here $n_1 = 6, n_2 = 2, d_1 = 1, d_2 = 3$.</figcaption></figure>

Let $\lambda_2(X)$ be the second largest eigenvalue of some square matrix $X$ and let $x$ be the normalised eigenvector associated to $\lambda_2(M.^tM)$. For every positive number $q$, we have

$$|\lambda_2(M.^tM)^q| = ||(A.J.^tA)^q.x|| = ||A(J.^tA.A)^{q-1}J.^tA.x|| \leq \gamma d_1 ||A(J.^tA.A)^{q-1}x'||$$

with $x'$ a normalised vector orthogonal to $e$ (because of the preceding fact). Hence

$$||(J.^tA.A)^{q-1}x'|| \leq \gamma^{q-1}|\lambda_2^{q-1}(^tA.A)|.$$

We conclude that

$$|\lambda_2(M.^tM)^q| \leq d_1^2 \gamma^q |\lambda_2(^tA.A)^{q-1}| = d_1 d_2 (\gamma |\lambda_2(^tA.A)|)^{q-1}.$$

Since this is a positive quantity, its $q$-th root is defined:

$$\lambda_2(M.^tM) \leq \left(d_1 d_2 (\gamma |\lambda_2(^tA.A)|)^{q-1}\right)^{\frac{1}{q}} = \left(d_1 d_2 \frac{(\gamma |\lambda_2(^tA.A)|)^q}{|\lambda_2(^tA.A)|}\right)^{\frac{1}{q}}$$

which gives

$$\lambda_2(M.^tM) \leq \left( \frac{d_1 d_2}{|\lambda_2(^tA.A)|} \right)^{\frac{1}{q}} \gamma |\lambda_2(^tA.A)|$$

By taking the limits when $q$ goes to infinity, we obtain

$$\lambda_2(M.^tM) \leq \gamma |\lambda_2(^tA.A)|$$

To finish the proof, we show the following:

**Lemma 3.3.1.** If $\lambda$ is an eigenvalue of $P$ then $\lambda^2$ is an eigenvalue of $M.^tM$.
Proof. $P^2$, whose entries represents the paths of size two in the graph, is the matrix of a disconnected $d_1d_2$-regular graph. Indeed, we can remark that

$$P^2 = \left( \begin{array}{c|c} M \cdot M & 0 \\ \hline 0 & M \cdot M \end{array} \right)$$

and $M \cdot M$ is symmetric. Let

$$v = (v_1, v_2, \dots, v_{n_1+n_2})$$

be an eigenvector of $P$ with eigenvalue $\lambda$. Then

$$v' = (-v_1, -v_2, \dots, -v_{n_1}, v_{n_1+1}, \dots, v_{n_1+n_2})$$

is also an eigenvector with associated eigenvalue $-\lambda$. Thus, $v - v'$ is an eigenvector of $P^2$ of eigenvalue $\lambda^2$ and this vector has $n_2$ zeros on the right. Because $P^2$ represents a disconnected graph, if we reduce the dimension of this vector by $n_2$ (removing the zeros on the right corresponding to one connected component) we get an eigenvector of $M \cdot M$ of eigenvalue $\lambda^2$. Therefore, $M \cdot M$ has the same eigenvalues —denoted $\mu_1 \ge \mu_2 \ge \dots \ge \mu_{n_1}$— as $P$, but squared. $\square$

The proof works the same with $Q$ (taking $n_1 = n_2$). We note $\alpha$ the bound for $|\mu_3(Q)|$ proven in the preceding section. $\alpha$ might refer to the bound from Theorem 1 if the graph is obtained from a bipartite regular graph of even degree or to the bound from Theorem 2 if its degree is odd. In $^tA.A$, the second largest magnitude eigenvalue is thus $|\lambda_2(^tA.A)| = (d_1|\mu_3(Q)|)^2 \le d_1^2\alpha^2$. Hence we have

$$|\lambda_2(P)| = \sqrt{|\lambda_2(M \cdot M)|} \le \sqrt{\gamma|\lambda_2(A \cdot A)|} \le \sqrt{d_1 d_2 \alpha}.$$

# 4 Final comments

In section 3.1, we have seen that the probability for the random walk to collapse to the identity sequence is less than $(\frac{2}{d})^m$. If so, the probability of getting a closed walk (conditioned by the collapsing event) is then 1. When the collapse does not happen, we cannot hope for a smaller probability than $\frac{1}{n}$ to get a closed path in the graph. This is the smallest probability of a closed walk one can get in a random graph. The trace method gives then

$$\mathbf{E}(|\mu_2|) \le \left( n \left( \frac{1}{n} + \left( \frac{2}{d} \right)^m \right) - 1 \right)^{\frac{1}{2m}} = n^{\frac{1}{2m}} \sqrt{\frac{2}{d}}.$$

With $m = \Omega(\ln n)$, we get $\mathbf{E}(|\mu_2|) = O(d^{-\frac{1}{2}})$, which is bigger than the bound from [9] only by a constant factor. This suggests that this technique can be improved by a subtler subdivision of the probability space of $\omega$, as well as a more careful analysis of the probability of having a closed walk (specially with the condition $X'_2 \cap X_4$ for $X'_2$ and $X_4$ defined on page 14).

Let us observe that the term $n^{\frac{1}{2m}}$ is getting close to 1 only when $m = \Omega(\log n)$. This is why in [4] or [2], the length of the random walk ($2m$) is logarithmic in the number of vertices. Our computations show that the optimal size of the walk should be a bit smaller; this might be because it allows us to assume that, with the overwhelming probability, at least one letter appears in
$\omega$ exactly one time (the event $X_1$ in the proof of Theorems 1 and 3). Clearly, we cannot keep $m$ small and at the same time make the factor $n^{\frac{1}{2m}}$ close to 1. This is an important limitation of our technique.

Our experimental results show that the second largest eigenvalue distribution measured for these graphs is much closer to that we can observe in the permutation model, at least in high dimension, and with a small field. A reasonable conjecture might be the following:

**Conjecture 1.** Let $G_k = \text{Sch}(GL_k(\mathbb{Z}_p) \circled{\scriptstyle(\mathbb{Z}_p^k)^*}, S)$ with $S$ a random subset of $GL_k(\mathbb{Z}_p)$ and $p$ a prime number. Let $G'_k$ be a $2|S|$-regular graph from the permutation model of size $p^k-1$. Then, as $k$ grows, the second largest eigenvalue distribution of $G$ converges to that of $G'$.

We believe that similar statements are true for bipartite regular and biregular graphs from our construction.

**Conclusion.** In this paper we study a pseudo-random construction of spectral expanders represented as Schreier graphs. The experimental results suggest that these graphs have nearly optimal value for the second largest eigenvalues (not only when the size of the graph goes to infinity but also for graspable sizes relevant for practical applications). Theoretical results proven above are the first step to explain these experimental results. Instead of more traditional asymptotic bounds, we focused on theoretical bound that can be calculated (possibly with help of computer) for graphs of rather small size involved in our numerical experiments. We observe the limitations of the method of moments used in our proof which often leads to dealing with too many cases. A more precise theoretical explanation of the behaviour of random Schreier graphs $\text{Sch}(GL_k(\mathbb{Z}_p) \circled{\scriptstyle(\mathbb{Z}_p^k)^*}, S)$ will require a subtler analysis. Another possible direction of the future research is a reduction of the number of random bits used to produce each graph. It would be interesting to reduce the number of these bits from $O(d \log^2 n)$ to $O(d \log n)$, which would bridge the gap between (pseudo)random and deterministic constructions. We would also like to draw attention to the theoretical bounds and estimates obtained with the help of “hideous” formulas combined with computer calculations. We believe that such an approach can be justified when studying properties of relatively small graphs.

**Acknowledgments.** The author thanks his PhD adviser, Andrei Romashchenko for providing several ideas and useful remarks on this work.

## References

[1] Noga Alon. Explicit expanders of every degree and size, 2020. arXiv:2003.11673.

[2] Noga Alon and Yuval Roichman. Random cayley graphs and expanders. Random Structures and Algorithms, 5(2):271–284, 1994.

[3] Gerandy Brito, Ioana Dumitriu, and Kameron Decker Harris. Spectral gap in random bipartite biregular graphs and applications, 2018. arXiv: 1804.07808.
[4] Andrei Broder and Eli Shamir. On the second eigenvalue of random regular graphs. pages 286-294, 1987. doi: 10.1109/SFCS.1987.45.

[5] C. Bordenave, A new proof of Friedman's second eigenvalue theorem and its extension to random lifts, arXiv 1502.04482v4, 2019. To appear in Annales scientifiques de l'Ecole normale sup'erieure

[6] Daniela Calvetti, L Reichel, and And Sorensen. An implicitly restarted lanczos method for large symmetric eigenvalue problems. Electronic Trans. Numer. Anal., 2:1-21, 04 1994.

[7] Christofides, D. and Markström, K. (2008), Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales. Random Struct. Alg., 32: 88-100. https://doi.org/10.1002/rsa.20177

[8] Michael Dinitz, Michael Schapira, and Asaf Valadarsky. Explicit expanding expanders, 2015. doi:10.48550/arXiv.1507.01196.

[9] Joel Friedman. A proof of Alon's second eigenvalue conjecture. Pro- ceedings of the thirty-fifth ACM symposium on Theory of computing - STOC '03, 2003. doi: 10.1145/780542.780646.

[10] Nabil Kahale. Eigenvalues and expansion of regular graphs. J. ACM, 42(5):1091-1106, 1995. doi: 10.1145/210118.210136.

[11] Alexander Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8:261-277, 09 1988. doi: 10.1007/BF02126799.

[12] M. Morgenstern, Existence and explicit constructions of $q + 1$ regular Ramanujan graphs for every prime power $q$, Journal of Combinatorial Theory. Series B, 62(1), 44-62, 1994.

[13] O. Reingold, S. Vadhan and A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders, Annals of Mathematics, 155(1), 157-187, 2002

[14] S. Mohanty, R. O'Donnell and P. Paredes, Explicit near-Ramanujan graphs of every degree, arXiv 1909.06988v2

[15] A. Nilli. On the second eigenvalue of a graph. Discrete Mathematics, 91(2):207-210, 1991.

[16] Luca Sabatini. Random schreier graphs and expanders. arXiv preprint arXiv: 2105.06378, 2021.

[17] M. Sipser and D.A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710-1722, 1996. doi:10.1109/18.556667.

[18] A. Steger and N. C. Wormald. Generating random regular graphs quickly. Combinatorics, Probability and Computing, 8(4):377-396, 1999. doi: 10.1017/S0963548399003867.

[19] Wen-Ch'ing Winnie Li and Patrick Solé. Spectra of regular graphs and hypergraphs and orthogonal polynomials. European Journal of Combinatorics, 17(5):461-477, 1996.
[20] A. Wigderson S. Hoory, N. Linial. Expander graphs and their applications. Bulletin of the American Mathematical Society 43, pages 439–561, August 2006.

[21] N. C. Wormald. Models of Random Regular Graphs, page 239–298. London Mathematical Society Lecture Note Series. Cambridge University Press, 1999. doi: 10.1017/CBO9780511721335.010.

[22] G. Zemor. On expander codes. IEEE Transactions on Information Theory, 47(2):835–837, 2001. doi: 10.1109/18.910593