# Combinatorics via Closed Orbits:
Vertex Expansion and Graph Quantum Ergodicity

Amitay Kamber 111Einstein Institute of Mathematics, The Hebrew University of
Jerusalem, Israel, email<EMAIL_ADDRESS>Tali Kaufman 222Department of
Computer Science, Bar-Ilan University, Ramat-Gan, 5290002, Israel, email:
<EMAIL_ADDRESS>research supported by ERC.

###### Abstract

This work presents a general paradigm to construct finite combinatorial
objects, with extermal substructures. This is done by observing that there
exist _infinite_ combinatorial structures with desired extermal substructures,
coming from an action of a subgroup of the automorphism group. The crux of our
idea, that we call _the closed orbits method_ is a systematic way to construct
a finite quotient of the infinite structure, containing a _simple_ shadow of
the infinite substructure, which maintains its extermal combinatorial
property. In particular, the shadow of a thin infinite substructure in the
cover remains small in the quotient.

We give a couple of applications of our paradigm. The first application is to
the well known question of _vertex expansion_ of number theoretic Ramanujan
graphs. It has been a common belief that such graphs are _lossless expanders_.
We show that some number theoretic Ramanujan graphs are not even _unique
neighbor expanders_ , which is a weaker notion. This holds, in particular, for
the Morgenstern Ramanujan graphs.

The second application is in the field of graph quantum ergodicity, where we
produce number theoretic Ramanujan graphs with an eigenfunction of small
support that corresponds to the zero eigenvalue. This again contradicts common
expectations.

The closed orbits method is based on an established idea from dynamics and
number theory, of studying closed orbits of subgroups. The novelty of this
work is in exploiting this idea to combinatorial questions.

##  1 Introduction

##### Combinatorics via inheriting the spectrum of the covering object.

Various combinatorial questions are studied using sparse graphs. Their
solution is often based on spectral analysis of the underlying graph, and in
particular on the fact that the given graph is a good expander. Namely, the
second eigenvalue of its adjacency matrix is very far from its first
eigenvalue ([7]).

The strongest spectral expansion condition is the Ramanujan property, which
says that the second largest non-trivial eigenvalue in absolute value of the
adjacency operator of a $d$-regular graph is bounded by $2\sqrt{d-1}$. An
alternative point of view is that the finite $d$-regular Ramanujan graph
inherits the spectrum of its covering object, which is the infinite
$d$-regular tree $T_{d}$. Namely, the graph’s non-trivial spectrum is
contained in the spectrum of $T_{d}$.

An explicit family of Ramanujan graphs were constructed in the celebrated work
of Lubotzky Phillips and Sarnak ([14]), based on number theory and in
particular the theory of automorphic forms, and deep results of Deligne and
others. The arithmetic construction of Ramanujan graphs is based on the
following idea: Consider the action of the group
$G=\operatorname{PGL}_{2}(\mathbb{Q}_{q})$ on its Bruhat-Tits tree
$B_{G}=T_{q+1}$. Using the number theory related to quaternion algebras, it is
possible to construct an arithmetic lattice $\Gamma$ in $G$ such that by
taking a quotient of $T_{q+1}$ by $\Gamma$ we get a $(q+1)$-regular graph
which inherits the spectrum of the infinite tree, namely, a graph with the
Ramanujan property. There are various possible variations on the construction,
for example, the work of Morgenstern ([19]) who gave a similar construction of
Ramanujan graphs based on the group
$G=\operatorname{PGL}_{2}(\mathbb{F}_{q}((t)))$. We call the resulting graphs
"number theoretic graphs", to distinguish them from other constructions of
Ramanujan graphs (e.g., the graphs constructed by [16]).

This construction was later extended to Ramanujan Complexes ([15, 12]), which
are arithmetic construction coming from the action of a $p$-adic group $G$ of
high rank on its building $B_{G}$. The Ramanujan property is based on the fact
that the finite complex inherits the spectral behavior of its covering
building ([5, 9]).

##### This work: Combinatorics via inheriting new properties of the covering
object.

The focus of our work is to study finite graphs by understanding new
properties that they inherit from their infinite cover. Namely, we study the
the number theoretic $(q+1)$-regular finite graph $X$ by turning to its
infinite covering object $B_{G}=T_{q+1}$, together of the action of $G$ on it.

Specifically, we focus on the action of a subgroup $H\leq G$ on $B_{G}$. An
orbit of $H$ gives a substructure $Z\subset B_{G}$ with various desired
properties. This substructure of $B_{G}$ is used to solve some combinatorial
questions for the infinite cover.

We look at the action of projecting $Z$ into the quotient finite graph $X$. We
want to understand the image $Y\subset X$ of the map, as it inherits the
properties of $Z$. Usually, this map is very complicated, and in particular,
its image $Y$ is the entire graph $X$. However, using the _closed orbits
method_ that we introduce in this work, we show that there are special
situations when this map is simple, and in particular, its image $Y$ may be
small relative to $X$.

As we explain in Subsection 1.5, the special situations happen if the orbit
$\Gamma\backslash H$ in the compact space $\Gamma\backslash G$ is closed,
hence the name of the method. The notion of _closed orbit_ is basic in ergodic
theory, and it has many uses in homogeneous dynamics, number theory and
representation theory. The novelty of our work can be seen as exploiting this
well known notion into new understanding of finite combinatorial questions.

We use the closed orbit methodology to study several combinatorial problems.
Most notable is the question of a graph with optimal vertex expansion (i.e.,
lossless expansion of graphs). It was a common belief among experts that
number theoretic graphs are _lossless expanders_. In Theorem 1.1 we disprove
this speculation and show that there are number theoretic graphs which are not
even _unique neighbor expanders_ , a weaker property that is implied by
lossless expansion.

In the following parts of the introduction we explain what is the vertex
expansion problem and discuss some of its rich history. Then we explain how
our general method applies to this question, using the closed orbits machinery
that we develop. Then we discuss a number of other combinatorial phenomena
addressed by our method - vertex expansion in Ramanujan complexes, and edge
expansion in Ramanujan graphs. Another surprising application is in the field
of quantum ergodicity of graphs, where we show in Theorem 1.10 the existence
of a concentrated eigenfunction of the adjacency operator, again contradicting
a natural belief that such eigenfunctions do not exist for number theoretic
graphs.

In Subsection 1.5 we explain the closed orbits machinery in more detail. We
finish by discussing the inverse situations in which closed orbits do not
exist. We pose a conjecture that non existence of closed orbits implies
lossless expansion of number theoretic graphs.

###  1.1 Vertex Expansion and the Spectral Method

There are some notoriously hard combinatorial questions about graphs, where
the spectral theory falls short of proving a desired answer. A notable example
is the question of finding a family of explicit $d$-regular graphs which are
_lossless-expanders_. For $X$ a $d$-regular graph, the _expansion ratio_ of a
set $Y\subset X$ is the ratio $\frac{\left|N(Y)\right|}{\left|Y\right|}$,
where $N(Y)$ is the set of neighbors of the set $Y$, including vertices from
$Y$ itself. This ratio is bounded by $d$. For $d$ large, a graph is a
lossless-expander if there is a constant $\alpha$ such that for every set
$Y\subset X$ of size $|Y|\leq\alpha|X|$, its expansion ratio is $d-o(d)$.
There are some constructions of graphs satisfying weaker notions ([4]), but
even going beyond expansion ratio $d/2$ is a major open question ([7]).

The best results using the spectral method are due to Kahale ([8]). He shows
that for Ramanujan graph the expansion ratio of linear sized sets of size
bounded by $\alpha|X|$, is at least $d/2-\beta$, where the $\beta\to 0$ as
$\alpha\to 0$ (see Theorem 5.6). Kahale also constructs graphs with a subset
of two vertices and expansion ratio $d/2$, which are almost-Ramanujan, in the
sense that their second eigenvalue in absolute value is bounded by
$2\sqrt{d-1}+o(1)$. In particular, he showed that the best expansion ratio
that it is possible to get solely by using spectral arguments can not exceed
$d/2$ for linear sized sets.

Kahale’s example has a short cycle of length 4. For graphs with large girth
(the length of the shortest cycle), Kahale proved that small sets have
expansion ratio $d-o(d)$ (see also [17]). For LPS graphs, that have the best
known girth, it implies that sets of size that is bounded by
$|X|^{1/3-\epsilon}$ have expansion ratio close to $d$.

###  1.2 Vertex Expansion via the Closed Orbit Method

The fact that Ramanujan graphs have vertex expansion ratio of $d/2$, and the
fact that Kahale’s construction have poor girth, led various researchers to
speculate that Ramanujan number theoretic graphs, which have very large girth,
should yield lossless expansion, or at least graphs in which their vertex
expansion is strictly greater than $d/2$. Such graphs are also _unique
neighbor expanders_ , since if a set $Y$ has expansion ratio which is greater
than $d/2$ then there exists a vertex that have a unique neighbor in $Y$. A
weaker desired property is _odd neighbor expansion_ , which says that there is
a vertex that is connected to an odd number of elements in $Y$.

We show that the common belief that number theoretic graphs have lossless
vertex expansion, is not true. As a matter of fact, some of those graph are
not even _odd neighbor expanders_ , and therefore not _unique neighbor
expanders_.

######  Theorem 1.1 (Number theoretic Ramanujan graphs that are not odd
neighbor expanders).

For every prime power $q$, there exists an infinite family of
$\left(q+1\right)$-regular number theoretic Ramanujan graphs $X$, and a subset
$Y\subset X$, $\left|Y\right|=O\left(\sqrt{\left|X\right|}\right)$, such that
every $x\in N\left(Y\right)$ has precisely $2$ neighbors in $Y$. Therefore $Y$
has no unique neighbors and
$\left|N\left(Y\right)\right|=\frac{q+1}{2}\left|Y\right|$.

Explicitly, for $q$ an odd prime power, we may choose the graph to be some of
the bipartite Ramanujan graphs constructed by Morgenstern, with girth greater
than $4/3\log_{q}\left(\left|X\right|\right)$.

We prove Theorem 1.1 in two stages: First we focus on bad vertex expansion in
the covering object, namely, we look at an infinite substructure of the
$(q+1)$-regular tree that is not expanding enough. Then we use the closed
orbit method that we develop to “import” the infinite non-expanding
substructure into a finite small subset of a number theoretic graph. This
subset will have bad expansion ratio, and we thus disprove a common belief
that number theoretic graphs are lossless expanders.

##### Using subgroups to finding an infinite subgraph with bad vertex
expansion.

on the $(q+1)$-regular tree $B_{G}$ of
$G=\operatorname{PGL}_{2}\left(\mathbb{F}_{q}\left(\left(t\right)\right)\right)$.
This gives rise to an embedding of the vertices of the $(q+1)$-regular tree
$B_{H}$ of $H$ in $B_{G}$ (See Figure 1.1 and the discussion in Subsection
4.2). The embedding can also be described as an embedding of the
$\left(q+1,2\right)$-biregular subdivision graph of $B_{H}$ in the
$\left(q+1\right)$-regular tree $B_{G}$.

Notice that the image of embedding is very thin, in the sense that a large
ball in $B_{G}$ with $n$ vertices will contain $\Theta(\sqrt{n})$ vertices of
$B_{H}$. The following lemma says that the embedded set has bad expansion
properties.

######  Lemma 1.2 (Lemma 4.2).

Let $Z\subset B_{G}$ be the embedding of the vertices of $B_{H}$ in $B_{G}$.
Then each vertex $v\in N(Z)$ is a neighbor of precisely two vertices of $Z$.

$\boldsymbol{\left(\begin{array}[]{cc}1&0\\\
&t^{2}\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}1&0\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t^{2}&0\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t^{2}&1\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}1&0\\\
&t^{2}\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}1&0\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t^{2}&0\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t^{2}&1\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}1&0\\\
&t\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t&1\\\
&t\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t&0\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t&1\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t^{2}&t\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t^{2}&t+1\\\
&1\end{array}\right)}$ Figure 1.1: Part of the tree of
$\operatorname{PGL}_{2}\left(\mathbb{F}_{2}\left(\left(t^{2}\right)\right)\right)$
(left) embedded in part of the tree of
$\operatorname{PGL}_{2}\left(\mathbb{F}_{2}\left(\left(t\right)\right)\right)$
(right). See Subsection 4.2 for the meaning of the vertex labels.

##### Using the closed orbit method to get a finite set with bad vertex
expansion

Once we demonstrated the non-expanding set $Z\subset B_{G}$ in the infinite
world, we may take a quotient of $B_{G}$ by a lattice, and look at the image
$Y$ of $Z$ in the resulting finite graph.

Since every neighbor of $Z$ is connected to $Z$ by at least two edges, the
same is true for its image $Y\subset X$. Therefore, $Y$ has no unique
neighbors, but $Y$ may be very dense in the graph $X$. The closed orbit method
allows us to find an arithmetic quotient where $Y$ maintains its volume in the
tree. Namely, we have the following:

######  Lemma 1.3 (Special case of Theorem 1.11).

It is possible to choose a family of arithmetic lattices $\Gamma\leq G$, such
that the projection $Y$ of the set $Z$ into the finite graph
$X=\Gamma\backslash G$ is of size $|Y|=O\left(\sqrt{|X|}\right)$.

Most of the non-explicit part of Theorem 1.1 follows from Lemma 1.3 and the
discussion above. The discussion implies that every vertex $x\in N(Y)$ is
connected by _at least_ two edges to $Y$. The fact that $x$ has precisely two
neighbors in $Y$ follows from a trick we explain later. This implies that
there are number theoretic graphs that are not even odd neighbor expanders.

In the following we apply the closed orbits method to the Morgenstern
Ramanujan graphs ([19]). This will give _explicit_ number theoretic graphs
with bad vertex expansion, and the explicit part of of Theorem 1.1.

#####  Morgenstern graphs: Explicit number theoretic graphs that are not
lossless expanders.

Let us describe how the above can be applied to the construction of Ramanujan
graphs by Morgenstern ([19]). Morgenstern constructs a lattice
$\Gamma\leq\operatorname{PGL}_{2}\left(\mathbb{F}_{q}\left(\left(t\right)\right)\right)$
that acts simply transitively on the Bruhat-Tits tree $B_{G}$, with generators
$\gamma_{1},...,\gamma_{q+1}$. If $\Gamma_{n}$ is a normal subgroup of
$\Gamma$, the graph $\Gamma_{n}\backslash B_{G}$ is then naturally isomorphic
to the Cayley graph
$X=\operatorname{Cayley}\left(\Gamma/\Gamma_{n},\left\\{\gamma_{1},...,\gamma_{q+1}\right\\}\right)$.

When $\Gamma_{n}$ is chosen by some explicit congruence conditions we get the
Morgenstern graphs, which have plenty of nice properties, described in [19,
Theorem 4.13], and are very similar to the celebrated LPS graphs ([14, 11]).
In particular, they are Ramanujan graphs and their girth is at least
$4/3\log_{q}\left(\left|X\right|\right)$.

The general method applies as follows: It turns out that after a "change of
variables", for
$H=\operatorname{PGL}_{2}\left(\mathbb{F}_{q}\left(\left(t^{2}\right)\right)\right)$,
the subgroup $\Gamma\cap H$ is generated by
$\delta_{1}=\gamma_{1}^{2},\dots,\delta_{q+1}=\gamma_{q+1}^{2}$ and is
actually also a Morgenstern lattice of $H$, which acts simply transitively on
the Bruhat-Tits tree $B_{H}$. When we look at the congruence subgroups
$\Gamma_{n}$, we get the following explicit theorem:

######  Theorem 1.4 (Explicit Number theoretic Ramanujan graphs that are not
odd neighbor expanders).

For every odd prime power $q$ and $m$ large enough, there exists a
$\left(q+1\right)$-regular bipartite Morgenstern Ramanujan graph
$X=\operatorname{Cayley}\left(\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{2m}}\right),\left\\{\gamma_{1},...,\gamma_{q+1}\right\\}\right)$
with generators $\gamma_{1},...,\gamma_{q+1}$, such that the subgroup
$\left\langle\gamma_{1}^{2},...,\gamma_{q+1}^{2}\right\rangle$ is isomorphic
to $\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{m}}\right)$. Moreover, the
graph
$Y=\operatorname{Cayley}\left(\left\langle\gamma_{1}^{2},...,\gamma_{q+1}^{2}\right\rangle,\left\\{\gamma_{1}^{2},...,\gamma_{q+1}^{2}\right\\}\right)$
is also a $\left(q+1\right)$-regular bipartite Morgenstern Ramanujan graph.

The subset $Y\subset X$ is of size $|Y|=O\left(\sqrt{|X|}\right)$, and every
$x\in N\left(Y\right)$ has precisely $2$ neighbors in $Y$.

Theorem 1.4 gives the explicit part of Theorem 1.1. As a matter of fact, the
proof of Theorem 1.4 is elementary, assuming the result of [19].

##### Ramanujan complexes are not sufficient for lossless expansion.

A promising option for a graph with good vertex expansion are the Ramanujan
complexes constructed in [15, 10] (See Subsection 4 for some discussion about
Ramanujan complexes).

Unlike $d$-regular graphs, they have a rigid local structure, which implies
interesting combinatorial properties. For example, many recent works used the
Garland method to show that they are "high dimensional expanders" ([13]).
Therefore, one may speculate that the rigid local structure will imply
lossless expansion.

However, we show that the underlying graph on the vertices of the complex can
have bad vertex expansion:

######  Theorem 1.5 (Skeleton graphs of Ramanujan complexes that are not odd
neighbor expanders).

Let $n$ be prime, $q$ a prime power,
$G=\operatorname{PGL}_{n}\left(\mathbb{F}_{q}\left(\left(t\right)\right)\right)$
and $B_{G}$ be the Bruhat-Tits building of $G$. Then there is an infinite
family of Ramanujan quotients $\Gamma\backslash B_{G}$ such that it underlying
graph $X$ has a subset $Y$ of size
$\left|Y\right|=O\left(\left|X\right|^{1/2}\right)$, with no unique neighbors.

The proof of Theorem 1.5 is based on applying the orbit method to
$H=\operatorname{PGL}_{n}\left(\mathbb{F}_{q}\left(\left(t^{2}\right)\right)\right)\leq
G=\operatorname{PGL}_{n}\left(\mathbb{F}_{q}\left(\left(t\right)\right)\right)$.
The basic observation is the following lemma:

######  Lemma 1.6.

The embedding $Z$ of the vertices of the building of $B_{H}$ in the vertices
of the building of $B_{G}$ have no unique neighbors.

The lemma implies that the projection $Y\subset X$ of $Z\subset B_{G}$ will
also have no unique neighbors. However, it does not have to be small. The
closed orbit method allows us to find lattices such that the image $Y$
satisfies $|Y|=O\left(\sqrt{|X|}\right)$.

###  1.3 Bad Edge Expansion for Number Theoretic Graphs

The results about vertex expansion have an analog for edge expansion. The
_edge expansion ratio_ of a set $S\subset X$ is the ratio
$\frac{M(S,X-S)}{|S|}$, where $M(S,X-S)$ is the number of edges between $S$
and its complement in $X$. Another way of studying this ratio is by looking at
the number $M(S,S)$ of internal edges in $S$, as $M(S,X-S)+M(S,S)=d|S|$.
Finally, $\frac{M(S,S)}{|S|}$ is simply the average degree of the induced
graph on $S$.

A graph is a good edge expander if the average induced degree for every set
$S$ is small. The best result about the connection between spectral gap and
edge expansion is given in the following result of Kahale:

######  Theorem 1.7 (Kahale ([8]), see also Theorem 1.8).

Let $X$ be a $\left(q^{2}+1\right)$-regular Ramanujan graph, with
$\left|X\right|\to\infty$. Then for every subset $Y\subset X$ with
$\left|Y\right|=o\left(\left|X\right|\right)$, the average degree of the
induced graph on $Y$ is bounded by $\sqrt{q}+1+o\left(1\right)$.

As with vertex expansion, we can prove that there exists number theoretic
graphs with as bad edge expansion as allowed by Kahale’s result:

######  Theorem 1.8 (Kahale’s spectral bound for edge expansion is tight).

For every prime power $q$, there exists an infinite family of
$\left(q^{2}+1\right)$-regular number theoretic Ramanujan graphs $X$, and a
$\left(q+1\right)$-regular induced subgraphs $Y\subset X$,
$\left|Y\right|=\Theta\left(\sqrt{\left|X\right|}\right)$.

The proof of this theorem is based on applying the general construction to
$G=\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{2}}\left(\left(t\right)\right)\right)$
and
$H=\operatorname{PGL}_{2}\left(\mathbb{F}_{q}\left(\left(t\right)\right)\right)$.
This gives as embedding $Z$ of $B_{H}$ in $B_{G}$. The basic property of this
embedding is:

######  Lemma 1.9.

Every vertex of $Z$ is connected to $q+1$ other vertices of $Z$.

See also Figure 1.2.

$\boldsymbol{\left(\begin{array}[]{cc}1&0\\\
&t^{2}\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}1&0\\\
&t\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}1&0\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t&1\\\
&t\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t&0\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t&1\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}1&0\\\
&t^{2}\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}1&0\\\
&t\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}1&0\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t&1\\\
&t\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t&0\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t&1\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t&\alpha\\\
&t\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t&\alpha+1\\\
&t\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t&\alpha\\\
&1\end{array}\right)}$$\boldsymbol{\left(\begin{array}[]{cc}t&\alpha+1\\\
&1\end{array}\right)}$ Figure 1.2: Part of the tree of
$\operatorname{PGL}_{2}\left(\mathbb{F}_{2}\left(\left(t\right)\right)\right)$
(left) embedded in part of the tree of
$\operatorname{PGL}_{2}\left(\mathbb{F}_{4}\left(\left(t\right)\right)\right)$
(right). We denote $\mathbb{F}_{4}=\left\\{0,1,\alpha,\alpha+1\right\\}$.

When projected to a finite quotient, the image $Y$ of $Z$ still has induced
degree at least $q+1$. The closed orbit method allows us to find an arithmetic
lattice such that this projection is small.

###  1.4 Concentrated eigenfunctions of number theoretic graphs

The closed orbits machinery could be useful beyond the specific question of
expansion. Indeed, we use this ideology to construct an eigenfunction with
eigenvalue 0, which has a small support in a number theoretic graph.

There is a lot of recent work, initiated by Brooks and Lindenstrauss ([3]),
whose aim is to understand eigenfunctions of the adjacency operator on
$\left(q+1\right)$-regular graphs. Similarly to the setting of vertex
expansion, eigenfunctions on a $\left(q+1\right)$-regular graph with girth at
least $\beta\log_{q}n$, have support of size at least
$\Theta\left(n^{\frac{\beta}{4}}\right)$ (See [6, Subsection 1.1]). Therefore,
the support of eigenfunctions on the graphs $X$ of Theorem 1.4 is at least
$n^{1/3-o\left(1\right)}$. More generally, Brooks and Lindenstrauss ([3])
proved that for a $\left(q+1\right)$-regular graph $X$ with girth
$\beta\log_{q}n$, for every $\epsilon>0$ there is $\delta>0$ such that if a
set $Y$ supports $\epsilon$ of the mass of an eigenfunction $f$ (were the
eigenfunction is normalized to $\left\lVert f\right\rVert_{2}=1$ and the mass
is determined by $\left|f\right|^{2}$), then
$\left|Y\right|\geq\Omega_{\epsilon}\left(n^{\delta}\right)$. This was
improved by Ganguly and Srivastava ([6]) to
$\left|Y\right|=\Omega\left(\epsilon n^{\epsilon\beta/4}\right)$.

Recently, Alon, Ganguly and Srivastava ([1]), extending the results of Ganguly
and Srivastava ([6]), constructed $\left(q+1\right)$-regular graphs of high
girth, with many eigenfunctions of small support, of eigenvalues that are
dense in $\left(-2\sqrt{q},2\sqrt{q}\right)$. Their graphs are with second
eigenvalue bounded by $\frac{3}{\sqrt{2}}\sqrt{q}\approx 2.121\sqrt{q}$, which
is close to being Ramanujan.

As for our contribution, let $X,Y$ be the graphs from Theorem 1.4. Let
$f:X\to\mathbb{C}$ be

$\displaystyle f\left(x\right)$
$\displaystyle=\begin{cases}+1&x\in\operatorname{PSL}_{2}\left(\mathbb{F}_{q^{m}}\right)\\\
-1&x\in\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{m}}\right)-\operatorname{PSL}_{2}\left(\mathbb{F}_{q^{m}}\right)\\\
0&x\notin\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{m}}\right)\end{cases}.$

######  Theorem 1.10 (Number theoretic Ramanujan graphs with concentrated
eigenfunctions).

The function $f\in L^{2}\left(X\right)$ is an eigenfunction of the adjacency
operator $A$ of $X$ with eigenvalue $0$.

Therefore, for every odd prime power $q$ there exists a $(q+1)$-regular number
theoretic Ramanujan graph $X$ of girth greater than $4/3\log_{q}(|X|)$, with
an eigenfunction of the adjacency operator of eigevnalue 0, which is supported
on $O\left(\sqrt{|X|}\right)$ vertices.

###### Proof.

Let $x\in X$. Notice that if $\gamma_{k}x\in Y$, then also
$\gamma_{k}^{-1}x=\gamma_{k}^{-2}\gamma_{k}x=\delta_{k}^{-1}\gamma_{k}x\in Y$.
Moreover, $\gamma_{k}x$ and $\gamma_{k}^{-1}x$ are on different parts of $Y$.
Therefore the total number of $(+1)$ contributing to
$\left(Af\right)\left(x\right)$ is equal to the the total number of $(-1)$
contributing to $\left(Af\right)\left(x\right)$. Therefore
$\left(Af\right)\left(x\right)=0$. ∎

Notice that after normalisation our eigenfunction to $\left\lVert
f\right\rVert_{2}=1$, we have $\left\lVert
f\right\rVert_{\infty}=\Omega\left(n^{-1/4}\right)$. By moving the
eigenfunction with the automorphisms of the Cayley graph, we actually get
$\Theta\left(\sqrt{n}\right)$ such functions. We are not familiar with any
similar construction of an explicit non-trivial eigenfunction on number-
theoretic graphs. However, our method is limited to the eigenvalue $0$.

We remark that our method is similar to the work of Milićević about large
values of eigenfunctions of arithmetic hyperbolic $3$-manifolds ([18]), and
also to the earlier work of Rudnick and Sarnak ([23]). Their methods show that
automorphic eigenfunction can have large supremum-norm at closed orbits of
smaller subgroups. The work [18], in particular, uses subgroups coming from
field extension. The main difference is that in our combinatorial setting we
can explicitly construct the eigenfunction, and this eigenfunction is not
automorphic in the sense that it is not an eigenunction of the other Hecke
operators that act on the space. However, the eigenvalue $0$ can be perhaps
explained by the existence of an automorphic lift from the smaller group. It
will be interesting to clarify this.

Finally, it will be interesting to apply the methods of [23, 18] to graphs, as
they may prove the existence of more general eigenfunctions with large
supremum norm.

###  1.5 The Closed Orbits Method

In the following we explain the closed orbits method and state our abstract
theorem about it.

Let $G$ be a locally compact group, $H\leq G$ a closed subgroup and
$\Gamma\leq G$ a cocompact lattice. We may loot at the orbit $\Gamma
xH\subset\Gamma\backslash G$ of a point $\Gamma x$. This action defines a map

$\tilde{F}_{\Gamma}:\Gamma_{x,H}\backslash H\to\Gamma\backslash G,$

where $\Gamma_{x,H}=x^{-1}\Gamma x\cap H$.

The above map and its image can be quite complicated in general. However, when
$\Gamma_{x,H}$ is a lattice in $H$ the map becomes much simpler, and in
particular, it becomes a topological embedding, and its image is closed. We
will focus of the case when $x=e\in G$ is the identity, and denote
$\Gamma_{H}=\Gamma_{e,H}=\Gamma\cap H$.

For our combinatorial purposes, we move from the group $G$ itself to a
discrete space. We assume that $G$ and $H\leq G$ are semisimple $p$-adic
groups, and let $K\leq G$ be a compact open subgroup. The space $G/K$ is a
discrete space with a $G$-action, which is closely related to the Bruhat-Tits
building $B_{G}$ of $G$. For simplicity we will work with the space $G/K$
instead of the Bruhat-Tits building $B_{G}$. The left $H$-action on $G/K$
defines an embedding

$H/K_{H}\to G/K,$

where $K_{H}=H\cap K$.

The reader may restrict herself to the case when
$G=\operatorname{PGL}_{n}\left(\mathbb{F}_{q}((t))\right)$,
$H=\operatorname{PGL}_{n}\left(\mathbb{F}_{q}((t^{2}))\right)$,
$K=\operatorname{PGL}_{n}\left(\mathbb{F}_{q}[[t]]\right)$ and
$K_{H}=\operatorname{PGL}_{n}\left(\mathbb{F}_{q}[[t^{2}]]\right)$, when $G/K$
and $H/K_{H}$ may be identified with the vertices of the Bruhat-Tits buildings
$B_{G}$ and $B_{H}$.

When we insert $\Gamma$ again into the picture, we get a map of discrete
spaces

$F_{\Gamma}:\Gamma_{H}\backslash H/K_{H}\to\Gamma\backslash G/K.$

When $\Gamma_{H}$ is a lattice in $H$, this is a map between two finite
combinatorial objects.

For the applications, we want two properties: First, $\Gamma_{H}$ should
indeed be a lattice in $H$. Second, we want $\Gamma_{H}\backslash H/K_{H}$ to
be as small as possible relative to $\Gamma\backslash G/K$.

To achieve the two properties we turn to number theory. our general method
will be:

  1. 1.

Construct an arithmetic lattice $\Gamma\leq G$ such that $\Gamma_{H}$ is a
lattice in $H$.

  2. 2.

Take congruence covers $\Gamma_{n}$ of $\Gamma$, such that the index
$\left[\Gamma_{H}:\Gamma_{n}\cap\Gamma_{H}\right]$ will grow far slower than
the index $\left[\Gamma:\Gamma_{n}\right]$.

We implement the above when $H$ and $G$ are related by field extension. The
actual details are based on the theory of semisimple groups over adelic rings,
and is done in Section 3. Here is a non-precise version of our general
abstract theorem. A precise version is given in Theorem 3.7.

######  Theorem 1.11 (The Closed Orbits Method).

Assume that $k_{0}$ is a non-Archimedean local field, $l_{0}$ is a finite
field extension of $k_{0}$ and $\boldsymbol{G}$ is a semisimple algebraic
group defined over $k_{0}$. Let $H=\boldsymbol{G}\left(k_{0}\right)\leq
G=\boldsymbol{G}\left(l_{0}\right)$. Then in many cases described in Section
3, we may choose a cocompact arithmetic lattice $\Gamma\leq G$, such that
$\Gamma_{H}=\Gamma\cap H\leq H$ is also a cocompact arithmetic lattice.
Moreover, we may choose a sequence $\left\\{\Gamma_{n}\right\\}$ of “principal
congruence subgroups” of $\Gamma$ of growing index, such that

$\left[\Gamma_{H}:\Gamma_{n}\cap\Gamma_{H}\right]=O\left(\left|\Gamma:\Gamma_{n}\right|^{1/\left[l_{0}:k_{0}\right]}\right).$

Therefore, it holds that $\left|(\Gamma_{n}\cap\Gamma_{H})\backslash
H/K_{H}\right|=O\left(\left|\Gamma_{n}\backslash
G/K\right|^{1/\left[l_{0}:k_{0}\right]}\right)$. We conclude that we can
construct a map between a small combinatorial object and a large combinatorial
object, which locally looks like the embedding of $H/K_{H}$ in $G/K$.

###  1.6 Vertex Expansion without Closed Orbits

Our explicit construction is based on the graphs of Morgenstern ([19]) and not
on the more famous LPS graphs of Lubotzky, Phillips and Sarnak ([14]). Our
method actually completely fails for LPS graph, since they are based on
lattices in $\operatorname{PGL}_{2}\left(\mathbb{Q}_{p}\right)$, $p$ prime,
and $\mathbb{Q}_{p}$ has no closed subfields. In particular,
$\operatorname{PGL}_{2}\left(\mathbb{Q}_{p}\right)$ has no closed subgroup
which behave similarly to the closed subgroup
$\operatorname{PGL}_{2}\left(\mathbb{F}_{q}\left(\left(t^{2}\right)\right)\right)$
of
$\operatorname{PGL}_{2}\left(\mathbb{F}_{q}\left(\left(t\right)\right)\right)$.

More generally, the LPS graphs are constructed from quaternion algebras over
$\mathbb{Q}$, and $\mathbb{Q}$ has no subfields which allows us to apply the
method we explain in Section 3.

While our results may suggest that the LPS graphs also have bad vertex
expansion, we believe that they actually point to the other direction. One can
perhaps uses the lack of similar subgroups to show that the LPS graphs have
good vertex expansion, although implementing this idea seems hard.

We therefore end the introduction with the following conjecture, stating that
the LPS graphs are lossless expanders:

######  Conjecture 1.12 (LPS graphs are lossless expanders).

Let $q$ be fixed and large, and $X_{n}$ be the family of $(q+1)$-regular
Ramanujan graphs constructed in [14]. Then for every $\epsilon>0$, there is
$n$ large enough such that for every set $Y\subset X_{n}$ with
$|Y|\leq|X_{n}|^{1-\epsilon}$, we have

$|N(Y)|\geq(q+1-o(q))|Y|.$

### Structure of this Article

In Section 2 we prove Theorem 1.4, showing explicit number theoretic Ramanujan
graphs with bad vertex expansion. This also proves the explicit part of
Theorem 1.1. We assume the results of [19], the proof uses elementary number
theory in function fields, and is independent from the rest of the paper.

In Section 3 we state and prove the precise version of Theorem 1.11, that is
our general theorem presenting the closed orbits method. The proof is based on
the theory of semisimple groups over the adeles, and in particular the strong
approximation theorem.

In Section 4 we present the implications of the closed orbits method to vertex
expansion, edge expansion and graph quantum ergodicity. We apply Theorem 1.11
to division algebras, discuss the Bruhat-Tits building, and prove Theorem 1.8
and Theorem 1.5. We also prove the non-explicit part of Theorem 1.1

Finally, in Section 5, we present simple proofs of Kahale’s theorems, using
the results of [2]. This section is independent of the other sections.

##  2 Explicit Number Theoretic Graphs with Bad Vertex Expansion

The main goal of this section is to prove Theorem 1.4. The theorem is more
than a special case of Theorem 1.11, since the lattices do not come from
simply connected groups, as we assume in Theorem 1.11. This allows to
construct very explicit Cayley graphs, but add another layer of complication,
which we resolve using Morgenstern’s results.

Let us first give a short explanation how the explicit construction fits into
the general framework. Let $\Gamma=\langle\gamma_{1},...,\gamma_{q+1}\rangle$
be a free group with $\gamma_{1},...,\gamma_{q+1}$ as generators and their
inverses. Let $\Gamma^{\prime}$ be the subgroup of $\Gamma$ generated by
$\delta_{1},...,\delta_{q+1}$, where $\delta_{i}=\gamma_{i}^{2}$.

The Cayley graph
$T_{\Gamma}=\operatorname{Cayley}(\Gamma,\\{\gamma_{1},...,\gamma_{q+1}\\})$
is a $(q+1)$-regular tree. Similarly,
$T_{\Gamma^{\prime}}=\operatorname{Cayley}(\Gamma^{\prime},\\{\delta_{1},...,\delta_{q+1}\\})$
is a $(q+1)$-regular tree. The embedding of $\Gamma^{\prime}$ in $\Gamma$
gives an embedding of the vertices of $T_{\Gamma^{\prime}}$ in $T_{\Gamma}$.
Moreover, each edge in $T_{\Gamma^{\prime}}$ corresponds to two edges in
$T_{\Gamma}$, or alternatively, the embedding extends to a graph embedding of
the $(q+1,2)$-biregular subdivision graph of $T_{\Gamma^{\prime}}$ in
$T_{\Gamma}$. We therefore deduce if $Z\subset T_{\Gamma}$ is the embedding of
the vertices of $T_{\Gamma^{\prime}}$ in $T_{\Gamma^{\prime}}$, then every
vertex $v\in N(Z)$ is connected to two vertices of $Z$. This is a version of
Lemma 1.2 in our case.

Now, let $\Gamma_{n}$ be a finite index subgroup of $\Gamma$. Then we may look
at the Cayley graph
$X=\operatorname{Cayley}(\Gamma/\Gamma_{n},\\{\gamma_{1},...,\gamma_{q+1}\\}))$
(with the elements being identified with their image in $\Gamma/\Gamma_{n})$.
Alternatively, $X$ can be identified with the quotient of $T_{\Gamma}$ by
$\Gamma_{n}$. There is a natural embedding
$\Gamma^{\prime}/(\Gamma^{\prime}\cap\Gamma_{n})\to\Gamma/\Gamma(n)$. The
image $Y$ of this embedding can be identified with the projection of $Z\subset
T_{\Gamma}$ to $X$. We deduce that every neighbor of $Y$ is also connected to
$Y$ by at least two edges.

The problem is then to find a subgroup $\Gamma_{n}$ such that $|Y|$ will be
much smaller than $|X|$, or alternatively
$[\Gamma^{\prime}:\Gamma^{\prime}\cap\Gamma_{n}]$ will be much smaller than
$[\Gamma:\Gamma_{n}]$, which will be an explicit version of Lemma 1.3. During
the proof we will show that it holds for the Morgenstern graphs using explicit
calculations.

It may be hard to identify the relation between the proof and the general
theory, which involves $p$-adic groups. After setting some preliminaries we
explain some of it in Remark 2.5 and later we explain another part of the
connection in Subsection 4.1.1.

Throughout the proof we freely use basic number theory in function fields. See
[22] for a good introduction to this subject.

We start by recalling the construction of the Morgenstern Ramanujan graphs
([19]). Let $q$ be a odd prime power, with $\mathbb{F}_{q}$ the corresponding
finite field. Consider the quaternion algebra
$A\left(\mathbb{F}_{q}\left(u\right)\right)$, which has a base $1,i,j,ij$ over
$\mathbb{F}_{q}\left(u\right)$, with relations

$i^{2}=\epsilon,j^{2}=u-1,ij=-ji,$

where $\epsilon\in\mathbb{F}_{q}$ is a non-square. This algebra has a norm

$N\left(a+bi+cj+dij\right)=a^{2}-\epsilon b^{2}+\left(\epsilon
d^{2}-c^{2}\right)\left(u-1\right).$

We let $A^{\times}\left(\mathbb{F}_{q}\left(u\right)\right)/Z^{\times}$ be the
quotient of the invertible elements of
$A\left(\mathbb{F}_{q}\left(u\right)\right)$ by the equivalence condition
$\alpha\sim\alpha^{\prime}$ if and only if there is
$a\in\mathbb{F}_{q}\left(u\right)$ with $a\alpha=\alpha^{\prime}$.

There are $q+1$ element
$\left\\{\gamma_{1}^{\prime},...,\gamma_{q+1}^{\prime}\right\\}\subset
A\left(\mathbb{F}_{q}\left[u\right]\right)$, satisfying

$\gamma_{k}^{\prime}=1+c_{k}j+d_{k}ij,$

with $c_{k},d_{k}\in\mathbb{F}_{q}$ and $N\left(\gamma_{k}^{\prime}\right)=u$.
Those elements correspond to the $q+1$ solutions of $\epsilon d^{2}-c^{2}=1$.

We let $S=\left\\{\gamma_{1},...,\gamma_{q+1}\right\\}$ be the image of those
elements in $A^{\times}\left(\mathbb{F}_{q}\left(u\right)\right)/Z^{\times}$.
Finally, let $\Gamma$ be the group generated by $\gamma_{1},...,\gamma_{q+1}$.

######  Theorem 2.1 ([19, Corollary 4.7]).

$\Gamma$ is a free group on $\frac{q+1}{2}$ generators, with
$\gamma_{1},...,\gamma_{q+1}$ as generators and their inverses. Moreover, we
may identify

$\displaystyle\Gamma\cong\Bigl{\\{}$ $\displaystyle\alpha=a+bi+cj+dij\in
A\left(\mathbb{F}_{q}\left[u\right]\right):\exists l\geq
0,N\left(\alpha\right)=u^{l},$ $\displaystyle
u-1|\gcd\left(a-1,b\right),u\nmid\gcd\left(a,b,c,d\right)\Bigr{\\}},$

where we denote by $A\left(\mathbb{F}_{q}\left[u\right]\right)$ the elements
of $A$ with $a,b,c,d\in\mathbb{F}_{q}\left[u\right]$.

Now let $g\in\mathbb{F}_{q}\left[u\right]$ be an irreducible polynomial of
degree $2m$. Then the congruence subgroup $\Gamma\left(g\right)$ of $\Gamma$
is the set of elements of $\Gamma$ who have in their equivalence class an
element $a+bi+cj+dij\in A\left(\mathbb{F}_{q}\left[u\right]\right)$,
satisfying $g\nmid a,g|b,g|c,g|d$.

Recall that the Legendre symbol for $f,g\in\mathbb{F}_{q}\left(u\right)$,
$g\neq 0$ irreducible is defined as

$\displaystyle\left(\frac{f}{g}\right)$ $\displaystyle=\begin{cases}0&g|f\\\
1&f\text{ is a square$\neq 0$ }\operatorname{mod}g\\\
-1&\text{else}\end{cases}$ $\displaystyle\equiv f^{\left(q^{\deg
g}-1\right)/2}\ (\mathrm{mod}\ g).$

######  Theorem 2.2 ([19, Theorem 4.13]).

The Cayley graph
$X_{g}=\operatorname{Cayley}\left(\Gamma/\Gamma\left(g\right),\left\\{\gamma_{1},...,\gamma_{q+1}\right\\}\right)$
is a $\left(q+1\right)$-regular Ramanujan graph.

There are two possibilities, depending on the Legendre symbol
$\left(\frac{u}{g}\right)$:

  1. 1.

If $\left(\frac{u}{g}\right)=-1$ then the group $\Gamma/\Gamma\left(g\right)$
is isomorphic to $\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{2m}}\right)$, the
graph $X_{g}$ is bipartite and its girth is at least
$\frac{4}{3}\log_{q}\left(\left|X_{g}\right|\right)$.

  2. 2.

If $\left(\frac{u}{g}\right)=1$ then the group $\Gamma/\Gamma\left(g\right)$
is isomorphic to $\operatorname{PSL}_{2}\left(\mathbb{F}_{q^{2m}}\right)$, the
graph $X_{g}$ is not bipartite, and its girth is at least
$\frac{2}{3}\log_{q}\left(\left|X_{g}\right|\right)$.

We now consider the $q+1$ elements
$S^{\prime}=\left\\{\delta_{1},...,\delta_{q+1}\right\\}\subset
A^{\times}\left(\mathbb{F}_{q}\left(u\right)\right)/Z^{\times}$ satisfying
$\delta_{k}=\gamma_{k}^{2}$, so explicitly

$\delta_{k}=2-u+2c_{k}j+2d_{k}ij.$

Let
$\Gamma^{\prime}=\left\langle\delta_{1},...,\delta_{q+1}\right\rangle\leq\Gamma$.

To prove Theorem 1.4 we need to understand the group
$\Gamma^{\prime}/\left(\Gamma^{\prime}\cap\Gamma\left(g\right)\right)$ and its
Cayley structure relative to the generators $\delta_{1},...,\delta_{q+1}$.

It is simpler to work with valuations instead of divisions. Recall that the
valuations of the field $\mathbb{F}_{q}\left(u\right)$ are $v_{1/u}$ defined
by $v_{1/u}\left(\frac{f}{g}\right)=\deg_{u}g-\deg_{u}f$,
$f,g\in\mathbb{F}_{q}\left[u\right]$, and for every irreducible monic
polynomial $p\in\mathbb{F}_{q}\left(u\right)$ the valuation
$\nu_{p}\left(p^{a}\frac{f}{g}\right)=a$, where
$f,g\in\mathbb{F}_{q}\left(u\right)$ are not divisible by $p$.

Using the language of valuations, $\Gamma\left(g\right)$ contain all the
elements of $A^{\times}\left(\mathbb{F}_{q}\left(u\right)\right)/Z^{\times}$,
which are in the free group generated by $\gamma_{1},...,\gamma_{q+1}$, and
further have an element $\alpha=a+bi+cj+dij$ in their equivalence class
satisfying:

$v_{g}\left(a\right)=0,v_{g}\left(b\right)>0,v_{g}\left(c\right)>0,v_{g}\left(d\right)>0.$

Next we make the change of variables $t=\frac{u}{2-u}$. It holds that
$u=\frac{2t}{t+1}$, $u-1=\frac{t-1}{t+1}$ and $2-u=\frac{2}{t+1}$.

Over $\mathbb{F}_{q}$$\left(t\right)$ the quaternion algebra $A$ changes to
the quaternion algebra
$A_{1}=\operatorname{span}\left\\{1,i_{1},j_{1},i_{1}j_{1}\right\\}$ over
$\mathbb{F}_{q}\left(t\right)$ with $i_{1}^{2}=\epsilon$,
$j_{1}^{2}=\frac{t-1}{t+1}$, $i_{1}j_{1}=-j_{1}i_{1}$. In the new algebra, we
have

$\displaystyle\gamma_{k}$ $\displaystyle=1+c_{k}j_{1}+d_{k}i_{1}j_{1}$
$\displaystyle\delta_{k}$
$\displaystyle=\frac{2}{t+1}+2c_{k}j_{1}+2d_{k}i_{1}j_{1}.$

Let $T:\mathbb{F}_{q}\left(u\right)\to\mathbb{F}_{q}\left(t\right)$,
$T\left(f\left(u\right)\right)=f\left(\frac{2t}{t+1}\right)$ be the
isomorphism of fields defined by the change of coordinates. There is a
bijection between valuations $v$ of $\mathbb{F}_{q}\left(u\right)$ and
valuations $\sigma$ of $\mathbb{F}_{q}\left(t\right)$, defined by
$v\left(f\right)=\sigma\left(T\left(f\right)\right)$ for every
$f\in\mathbb{F}_{q}\left(u\right)$. Let us describe this bijection.

The change of variables is a composition of two simpler change of variables: A
linear transformation $t=au+b$, $a\neq 0,b\in\mathbb{F}_{q}$ and an inversion
$t=1/u$.

For $t=au+b$, the bijection is as follows: $v_{1/u}$ corresponds to
$\sigma_{1/t}$, and for $g\left(u\right)$ monic irreducible, $\deg
g=m^{\prime}$, let $h\left(t\right)=a^{-m^{\prime}}g\left(at+b\right)$. Then
$v_{g}$ corresponds to $\sigma_{h}$.

For $t=1/u$, the bijection is as follows: $v_{1/u}$ corresponds to
$\sigma_{t}$, $v_{u}$ corresponds to $\sigma_{1/t}$, and for $g\left(u\right)$
monic irreducible, $g\left(u\right)\neq u$, $\deg g=m^{\prime}$,
$g(u)=u^{m^{\prime}}+a_{m^{\prime}-1}u+....+a_{0}$, let
$h\left(t\right)=a_{0}^{-1}t^{m^{\prime}}g\left(1/t\right)=t^{m^{\prime}}+a_{1}a_{0}^{-1}t^{m^{\prime}-1}+...+a_{m^{\prime}-1}a_{0}^{-1}t+a_{0}^{-1}$.
Then $v_{g}$ corresponds to $\sigma_{h}$.

Applying the above to $t=\frac{u}{2-u}$, $u=\frac{2t}{t+1}$, the bijection is

$\displaystyle v_{1/u}$ $\displaystyle\leftrightarrow\sigma_{t+1}$
$\displaystyle v_{u-2}$ $\displaystyle\leftrightarrow\sigma_{1/t},$

and for $g\left(u\right)\neq u-2$ of degree $m^{\prime}$, let
$h\left(t\right)$ the monic polynomial corresponding to
$\left(t+1\right)^{m^{\prime}}g\left(\frac{2t}{t+1}\right)$. Then
$v_{g}\leftrightarrow\sigma_{h}$.

The other direction of this correspondence is given as follows: For
$h\left(t\right)\neq t+1$ of degree $m^{\prime}$, let $g\left(t\right)$ be the
monic polynomial corresponding to
$\left(u-2\right)^{m^{\prime}}h\left(\frac{u}{2-u}\right)$. Then
$\sigma_{h}\leftrightarrow v_{g}$.

######  Lemma 2.3.

Using the correspondence above, for $g\left(u\right)\neq u-2$, it holds that
$\left(\frac{u}{g\left(u\right)}\right)=\left(\frac{2t\left(t+1\right)}{h\left(t\right)}\right)$.

###### Proof.

The Legendre symbol $\left(\frac{f\left(u\right)}{g\left(u\right)}\right)$ for
$v_{g}\left(f\right)\geq 0$ is determined by whether the image of $f$ in the
finite field
$\left\\{f^{\prime}\in\mathbb{F}_{q}\left(u\right):v_{g}\left(f^{\prime}\right)\geq
0\right\\}/\left\\{f^{\prime}\in\mathbb{F}_{q}\left(u\right):v_{g}\left(f^{\prime}\right)>0\right\\}$
is a zero, a non-zero square, or neither. Since $u=\frac{2t}{t+1}$ and
$2t\left(t+1\right)=\frac{2t}{t+1}\left(t+1\right)^{2}$, the result follows. ∎

Returning to $\Gamma\left(g\right)$, let $h\left(t\right)$ correspond to
$g\left(u\right)$ as above. Then after the change of coordinates we have:

######  Lemma 2.4.

The group $\Gamma\left(g\right)$ is isomorphic subgroup of
$A_{1}^{\times}\left(\mathbb{F}_{q}\left(t\right)\right)/Z^{\times}$ generated
by $\gamma_{1},..,\gamma_{q+1}$, $\gamma_{k}=1+c_{k}j_{1}+d_{k}i_{1}j_{1}$,
such that there is an element in the equivalent class satisfying

$v_{h}\left(a\right)=0,v_{h}\left(b\right)>0,v_{h}\left(c\right)>0,v_{h}\left(d\right)>0.$
(2.1)

The group $\Gamma/\Gamma\left(g\right)$ is isomorphic to
$\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{2m}}\right)$ if and only if
$\left(\frac{2t\left(t+1\right)}{h\left(t\right)}\right)=-1$.

Next, we change the algebra to an equivalent algebra. Let
$A_{2}=\operatorname{span}\left\\{1,i_{2},j_{2},i_{2}j_{2}\right\\}$ be the
quaternion algebra over $\mathbb{F}_{q}\left(t\right)$ with
$i_{2}^{2}=\epsilon$, $j_{2}^{2}=\left(t+1\right)\left(t-1\right)=t^{2}-1$,
$i_{2}j_{2}=-j_{2}i_{2}$. Then
$A_{1}\left(\mathbb{F}_{q}\left(t\right)\right)\cong
A_{2}\left(\mathbb{F}_{q}\left(t\right)\right)$, with the explicit isomorphism

$a+bi_{1}+cj_{1}+di_{1}j_{1}\in
A_{1}\left(\mathbb{F}_{q}\left(t\right)\right)\leftrightarrow
a+bi_{2}+\frac{c}{t+1}j_{2}+\frac{d}{t+1}i_{2}j_{2}\in
A_{2}\left(\mathbb{F}_{q}\left(t\right)\right).$

In the new algebra,

$\displaystyle\gamma_{k}$
$\displaystyle=1+\frac{c_{k}}{t+1}j_{2}+\frac{d_{k}}{t+1}i_{2}j_{2}$
$\displaystyle\delta_{k}$
$\displaystyle=\frac{2}{t+1}+\frac{2}{t+1}c_{k}j_{2}+\frac{2}{t+1}d_{k}i_{2}j_{2}$
$\displaystyle=1+c_{k}j_{2}+d_{k}i_{2}j_{2}.$

The last equality follows from the fact that we work in
$A_{2}^{\times}\left(\mathbb{F}_{q}\left(t\right)\right)/Z^{\times}$.

Moving to
$A_{2}^{\times}\left(\mathbb{F}_{q}\left(t\right)\right)/Z^{\times}$, $\Gamma$
is generated by $\gamma_{1},...,\gamma_{q+1}\in
A_{2}^{\times}\left(\mathbb{F}_{q}\left(t\right)\right)/Z^{\times}$, while
$\Gamma\left(g\right)$ consists of the elements with an element in their
equivalence class satisfying Equation (2.1).

Therefore $\Gamma^{\prime}$ is generated by $\delta_{1},...,\delta_{q+1}\in
A_{2}^{\times}\left(\mathbb{F}_{q}\left(t\right)\right)$, and
$\Gamma^{\prime}\cap\Gamma\left(g\right)$ are the elements in
$\Gamma^{\prime}$ satisfying Equation (2.1).

Denote $s=t^{2}$. Notice that $A_{2}$ is defined over
$\mathbb{F}_{q}\left(s\right)$, and moreover
$A_{2}\left(\mathbb{F}_{q}\left(s\right)\right)$ is the quaternion algebra
defined by the relations $i_{2}^{2}=\epsilon$, $j_{2}^{2}=s-1$,
$i_{2}j_{2}=-j_{2}i_{2}$. Therefore,
$A_{2}\left(\mathbb{F}_{q}\left(s\right)\right)$ is the same algebra as
$A\left(\mathbb{F}_{q}\left(u\right)\right)$, up to changing $u$ to $s$.
Moreover, the elements $\delta_{1},...,\delta_{q+1}$ are actually defined over
$\mathbb{F}_{q}\left(s\right)$, and correspond to the elements
$\gamma_{1},...,\gamma_{q+1}$ of $A\left(\mathbb{F}_{q}\left(u\right)\right)$!
This is the “miracle” underlying this construction.

######  Remark 2.5.

Let us stop the proof for a moment and explain the connection between Theorem
1.4 and Theorem 1.11.

After the change of variables, look at the group
$G=A_{2}^{\times}\left(\mathbb{F}_{q}((t))\right)/Z^{\times}\cong\operatorname{PGL}_{2}\left(\mathbb{F}_{q}((t))\right)$.
Morgenstern shows that $\Gamma$ acts simply transitively on the Bruhat-Tits
building $B_{G}$ of $G$, and actually the Cayley graph of $\Gamma$ with
respect to $\gamma_{1},...,\gamma_{q+1}$ can be identified with $B_{G}$.

Denote
$H=A_{2}^{\times}\left(\mathbb{F}_{q}\left(\left(t^{2}\right)\right)\right)/Z^{\times}\cong\operatorname{PGL}_{2}\left(\mathbb{F}_{q}\left(\left(t^{2}\right)\right)\right)$
which is a closed subgroup of $G$. It is not hard to see that
$\Gamma^{\prime}=\Gamma\cap H$. The calculation above implies that
$\Gamma^{\prime}$ acts simply transitively on the Bruhat-Tits building $B_{H}$
of $H$, and its Cayley graph with respect to $\delta_{1},...,\delta_{q+1}$ is
isomorphic to $B_{H}$. Therefore $\Gamma^{\prime}=\Gamma\cap H$ is a lattice
in $H$, which is far from obvious. As we explain in Section 4, this fact also
follows from the fact that $A_{2}$ is actually defined over
$\mathbb{F}_{q}(s)=\mathbb{F}_{q}\left(t^{2}\right)$.

The embedding of the Cayley $\Gamma^{\prime}$ in $\Gamma$ is exactly the
embedding of $B_{H}$ in $B_{G}$. This implies that the embedding of
$\Gamma^{\prime}/\left(\Gamma^{\prime}\cap\Gamma(g)\right)$ in
$\Gamma/\Gamma(g)$ is the same as the embedding of
$\left(\Gamma^{\prime}\cap\Gamma(g)\right)\backslash B_{H}$ in
$\Gamma(g)\backslash B_{G}$.

In the next part of the proof we study the growth of
$\left[\Gamma^{\prime}:\left(\Gamma^{\prime}\cap\Gamma(g)\right)\right]$
relative to $[\Gamma:\Gamma(g)]$ as in Lemma 1.3 or Theorem 1.11. We will
actually understand a bit more than that.

Continuing the proof, we may assume that $\Gamma^{\prime}\subset
A_{2}^{\times}\left(\mathbb{F}_{q}\left(s\right)\right)/Z^{\times}$. However,
we still need to handle the conditions of Equation (2.1) to understand
$\Gamma^{\prime}\cap\Gamma\left(g\right)$.

There are two cases: the “good case”
$h\in\mathbb{F}_{q}\left(t^{2}\right)=\mathbb{F}_{q}\left(s\right)$ (i.e., $h$
only has $t$ to an even power) and the “bad case”
$h\notin\mathbb{F}_{q}\left(t^{2}\right)=\mathbb{F}_{q}\left(s\right)$.

In the good case, let $\tilde{h}\left(s\right)\in\mathbb{F}_{q}\left(s\right)$
the be polynomial satisfying $\tilde{h}\left(t^{2}\right)=h\left(t\right)$.
Notice that
$\deg\left(\tilde{h}\right)=\deg\left(h\right)/2=\deg\left(g\right)/2=m$.

In the bad case, let $\tilde{h}\left(s\right)\in\mathbb{F}_{q}\left(s\right)$
be the polynomial satisfying
$\tilde{h}\left(t^{2}\right)=h\left(t\right)h\left(-t\right)$.

In both cases,
$\tilde{h}\left(s\right)\in\mathbb{F}_{q}\left(s\right)=\mathbb{F}_{q}\left(t^{2}\right)$
is an irreducible polynomial (or prime), which lies below the irreducible
polynomial $h\left(t\right)\in\mathbb{F}_{q}\left(t\right)$ in the extension
of $\mathbb{F}_{q}\left(s\right)$ to $\mathbb{F}_{q}\left(t\right)$. In other
words, it holds that
$h\left(t\right)\mathbb{F}_{q}\left[t\right]\cap\mathbb{F}_{q}\left[s\right]=\tilde{h}\left(s\right)\mathbb{F}_{q}\left[s\right]$
and for $f\in\mathbb{F}_{q}\left(s\right)$,
$v_{h}\left(f\left(t^{2}\right)\right)=v_{\tilde{h}}\left(f\left(s\right)\right)$.

This implies that we may identify $\Gamma^{\prime}$ as the subgroup of
$A_{2}^{\times}\left(\mathbb{F}_{q}\left(s\right)\right)/Z^{\times}$,
generated by $\delta_{k}=1+c_{k}j_{2}+d_{k}i_{2}j_{2}$, and
$\Gamma^{\prime}\cap\Gamma\left(g\right)$ as its subgroup of elements with an
element in the equivalence class satisfying
$v_{\tilde{h}}\left(a\right)=0,v_{\tilde{h}}\left(b\right)>0,v_{\tilde{h}}\left(c\right)>0,v_{\tilde{h}}\left(d\right)>0.$

The final description is exactly the description of the Morgenstern graph,
with $u$ replaced by $s$ and $g\left(u\right)$ replaced by
$\tilde{h}\left(s\right)$. Therefore:

######  Theorem 2.6.

$Y_{g}=\operatorname{Cayley}\left(\Gamma^{\prime}/\left(\Gamma^{\prime}\cap\Gamma\left(g\right)\right),\left\\{\delta_{1},...,\delta_{q+1}\right\\}\right)$
is isomorphic to the Morgenstern graph $X_{\tilde{h}}$.

In particular, the subgroup
$\Gamma^{\prime}/\left(\Gamma^{\prime}\cap\Gamma\left(g\right)\right)\leq\Gamma/\Gamma(g)$
is isomorphic to either $\operatorname{PSL}_{2}\left(q^{\deg\tilde{h}}\right)$
or $\operatorname{PGL}_{2}\left(q^{\deg\tilde{h}}\right)$.

Our next goal is to understand which of the two cases,
$\operatorname{PSL}_{2}$ or $\operatorname{PGL}_{2}$ happens. In the “good
case”,
$\tilde{h}\left(s\right)\in\mathbb{F}_{q}\left(s\right)=\mathbb{F}_{q}\left(t^{2}\right)$
remains irreducible in the extension to $\mathbb{F}_{q}\left(t\right)$. In
other words, it is inert in the extension. Since this is a quadratic
extension, it is well known that it happens if and only if
$\left(\frac{s}{\tilde{h}\left(s\right)}\right)=-1$. In this case, by Theorem
2.2, $Y_{g}$ is a bipartite Cayley graph on
$\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{\deg\tilde{h}}}\right)=\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{m}}\right)$.

In the “bad case”,
$h\left(s\right)\in\mathbb{F}_{q}\left(s\right)=\mathbb{F}_{q}\left(t^{2}\right)$
splits in the extension to $\mathbb{F}_{q}\left(t\right)$. This happens if and
only if $\left(\frac{s}{\tilde{h}\left(s\right)}\right)=1$. In this case, by
Theorem 2.2, $Y_{g}$ is a non-bipartite Cayley graph on
$\operatorname{PSL}_{2}\left(\mathbb{F}_{q^{\deg\tilde{h}}}\right)=\operatorname{PSL}_{2}\left(\mathbb{F}_{q^{2m}}\right)$.

For Theorem 1.4, we need to prove that the good case may happen, and to
understand $X_{g}$ in this case. For this we notice that we may first choose
$\tilde{h}\in\mathbb{F}_{q}\left(s\right)$ of degree $m$, which is inert in
the field extension to $\mathbb{F}_{q}\left(t\right)$, then get
$h\left(t\right)=\tilde{h}\left(t^{2}\right)$ and finally get
$g\left(u\right)$ from it as the irreducible monic corresponding to
$\left(u-2\right)^{2m}h\left(\frac{u}{2-u}\right)$.

We recall quadratic reciprocity in $\mathbb{F}_{q}\left(s\right)$ ([22,
Theorem 3.3]), which states that for $f,g\in\mathbb{F}_{q}\left[s\right]$
irreducible

$\left(\frac{f}{g}\right)=\left(-1\right)^{\frac{q-1}{2}\deg f\deg
g}\left(\frac{g}{f}\right).$

Then

$\left(\frac{s}{\tilde{h}\left(s\right)}\right)=\left(-1\right)^{\frac{q-1}{2}\deg\tilde{h}}\left(\frac{\tilde{h}\left(s\right)}{s}\right)=\left(-1\right)^{\frac{q-1}{2}\deg\tilde{h}}\left(\frac{\tilde{h}\left(0\right)}{s}\right)=\left(-1\right)^{\frac{q-1}{2}\deg\tilde{h}}\left(\frac{\tilde{h}\left(0\right)}{q}\right).$

The last element is the usual Legendre symbol in $\mathbb{Z}$.

Next,

$\left(\frac{2t\left(t+1\right)}{h\left(t\right)}\right)=\left(\frac{2}{h\left(t\right)}\right)\left(\frac{t}{h\left(t\right)}\right)\left(\frac{t+1}{h\left(t\right)}\right).$

Since $h\left(t\right)$ is of even degree,
$\mathbb{F}_{q}\left(t\right)/h\left(t\right)\mathbb{F}_{q}\left(t\right)$
contains $\mathbb{F}_{q^{2}}$. Therefore every $a\in\mathbb{F}_{q}$ has a
square root in it and $\left(\frac{2}{h\left(t\right)}\right)=1.$ It holds
that by quadratic reciprocity, since the degree of $h\left(t\right)$ is even,

$\displaystyle\left(\frac{t}{h\left(t\right)}\right)$
$\displaystyle=\left(\frac{h\left(t\right)}{t}\right)=\left(\frac{h\left(0\right)}{t}\right)=\left(\frac{h\left(0\right)}{q}\right)=\left(\frac{\tilde{h}\left(0\right)}{q}\right)$
$\displaystyle\left(\frac{t+1}{h\left(t\right)}\right)$
$\displaystyle=\left(\frac{h\left(t\right)}{t+1}\right)=\left(\frac{h\left(-1\right)}{t+1}\right)=\left(\frac{h\left(-1\right)}{q}\right)=\left(\frac{\tilde{h}\left(1\right)}{q}\right).$

The last two elements in each row are the Legendre symbol in $\mathbb{Z}$.
Therefore
$\left(\frac{2t\left(t+1\right)}{h\left(t\right)}\right)=\left(\frac{\tilde{h}\left(0\right)}{q}\right)\left(\frac{\tilde{h}\left(1\right)}{q}\right)$
determines whether $X_{g}$ is $\operatorname{PGL}$ or $\operatorname{PSL}$.

We conclude that by determining
$\tilde{h}\left(0\right),\tilde{h}\left(1\right)$ we can make $Y_{g}$ be
isomorphic to $\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{m}}\right)$ and
$X_{g}$ to be isomorphic to either of
$\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{2m}}\right)$ or
$\operatorname{PSL}_{2}\left(\mathbb{F}_{q^{2m}}\right)$. Finally, for $m$
large enough, we may freely choose
$\tilde{h}\left(0\right),\tilde{h}\left(1\right)$ while keeping $\tilde{h}$
irreducible by Chabotarev’s density theorem ([22, Theorem 4.7 and Theorem
4.8]).

We collect our findings in the following lemma:

######  Lemma 2.7.

For every $m$ large enough, we may find a monic irreducible polynomial $g$ of
degree $2m$ such that:

  1. 1.

The Morgenstern Ramanujan Cayley graph
$X_{g}=\operatorname{Cayley}\left(\Gamma/\Gamma\left(g\right),\left\\{\gamma_{1},...,\gamma_{q+1}\right\\}\right)$
is bipartite,
$\Gamma/\Gamma\left(g\right)\cong\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{2m}}\right)$
and its girth is greater than $4/3\log_{q}\left(|X_{g}|\right)$.

  2. 2.

The subgroup
$\Gamma^{\prime}/\left(\Gamma^{\prime}\cap\Gamma\left(g\right)\right)\leq\Gamma/\Gamma(g)$
that is generated by $\left\\{\gamma_{1}^{2},...,\gamma_{q+1}^{2}\right\\}$ is
isomorphic to $\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{m}}\right)$.
Moreover,
$Y_{g}=\operatorname{Cayley}\left(\Gamma^{\prime}/\left(\Gamma^{\prime}\cap\Gamma\left(g\right)\right),\left\\{\gamma_{1}^{2},...,\gamma_{q+1}^{2}\right\\}\right)$
is also a Morgenstern Ramanujan graph.

Notice that the lemma implies that
$|Y_{g}|=\left|\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{m}}\right)\right|=O\left(\sqrt{\left|\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{2m}}\right)\right|}\right)=O(\sqrt{|X_{g}|})$.
By the discussion at the beginning of this section, we conclude that Lemma 2.7
is an explicit version of Lemma 1.3.

We need however another result to complete the proof of Theorem 1.4.

######  Lemma 2.8.

Every vertex $x\in N(Y_{g})$ is connected to exactly two vertices in $Y_{g}$.

###### Proof.

If $x\in N(Y_{g})$, then $x=\gamma_{i}y$, for $y\in Y_{g}$, and $\gamma_{i}$ a
generator. Therefore $x$ is connected in $X_{g}$ to both
$y=\gamma_{i}^{-1}x,\gamma_{i}^{2}y=\gamma_{i}x\in Y_{g}$. Therefore every
neighbor of $Y_{g}$ is connected to at least two vertices of it (we discussed
this part of the proof at the beginning of the section).

Assume by contradiction that $x\in N(Y_{g})$ is connected to more than two
vertices of $Y_{g}$, then by applying the automorphism of the Cayley graph
$X_{g}$ defined by subgroup
$\Gamma^{\prime}/\left(\Gamma^{\prime}\cap\Gamma\left(g\right)\right)$, we
would get $O\left(|Y_{g}|\right)$ other neighbors of $Y_{g}$ which are
connected to more than 2 vertices of $Y_{g}$. Then there is some $\delta>0$
such that on average a neighbor of $Y_{g}$ is connected to $2+\delta$ vertices
in $Y_{g}$. This contradicts Kahale’s vertex expansion Theorem 5.6.

∎

######  Remark 2.9.

Assume that we choose $\tilde{h}\left(s\right)$,
$\deg\tilde{h}\left(s\right)=m$, such that it splits in the extension to
$\tilde{h}\left(t^{2}\right)=h\left(t\right)h\left(-t\right)$. Then a similar
construction still works – we look at
$g\left(u\right)=g_{1}\left(u\right)g_{2}\left(u\right)$, where
$g_{1}\left(u\right)$ corresponds to $h\left(t\right)$ and
$g_{2}\left(u\right)$ corresponds to $h\left(-t\right)$. Then
$\Gamma\left(g\right)=\Gamma\left(g_{1}\right)\cap\Gamma\left(g_{2}\right)$
defines a Cayley graph
$X_{g}=\operatorname{Cayley}\left(\Gamma/\Gamma\left(g\right),\left\\{\gamma_{1},...,\gamma_{q+1}\right\\}\right)$.
There is an embedding $F:Y_{g}\cong X_{\tilde{h}}\to X_{g}$, which extends to
a graph map on the subdivision graph $Y_{g}^{\prime}$ of $Y_{g}$.

In this case $Y_{g}$ will be a Cayley graph on
$\operatorname{PSL}_{2}\left(\mathbb{F}_{q^{m}}\right)$, while $X_{g}$ will be
a Cayley graph on some subgroup between
$\operatorname{PSL}_{2}\left(\mathbb{F}_{q^{m}}\right)\times\operatorname{PSL}_{2}\left(\mathbb{F}_{q^{m}}\right)$
and
$\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{m}}\right)\times\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{m}}\right)$.
So again we get a similar map from a small $\left(q+1,2\right)$-biregular
graph and a big $\left(q+1\right)$-regular Ramanujan graph.

###  2.1 Explicit Generators

We shortly describe how to construct our graphs explicitly. Assume we are
given monic irreducible
$\tilde{h}\left(s\right)\in\mathbb{F}_{q}\left(s\right)$, $\deg\tilde{h}=m$,
which is inert (remains irreducible) in the extension to
$\mathbb{F}_{q}\left(t\right)$.

Let $h\left(t\right)=\tilde{h}\left(t^{2}\right)$ be the irreducible
polynomial of degree $2m$ in $\mathbb{F}_{q}\left(t\right)$ above
$\tilde{h}\left(s\right)$. Let $\epsilon\in\mathbb{F}_{q}$ be a non-square and
let
$\boldsymbol{i}\in\mathbb{F}_{q}\left(t\right)/h\left(t\right)\mathbb{F}_{q}\left(t\right)$
be a square root of $\epsilon$ (which exists since $h$ is of even degree).
Consider the following elements in
$\operatorname{PGL}_{2}\left(\mathbb{F}_{q}\left(t\right)/h\left(t\right)\mathbb{F}_{q}\left(t\right)\right)\cong\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{2m}}\right)$:

$\displaystyle\gamma_{k}$
$\displaystyle=\left(\begin{array}[]{cc}t+1&\left(c_{k}-d_{k}\boldsymbol{i}\right)\\\
\left(c_{k}+d_{k}\boldsymbol{i}\right)\left(t^{2}-1\right)&t+1\end{array}\right)$
$\displaystyle\delta_{k}$
$\displaystyle=\gamma_{k}^{2}=\left(\begin{array}[]{cc}1&\left(c_{k}-d_{k}\boldsymbol{i}\right)\\\
\left(c_{k}+d_{k}\boldsymbol{i}\right)\left(t^{2}-1\right)&1\end{array}\right)$

(we work modulu center so it makes sense). Recall that
$\left(c_{k},d_{k}\right)$ are the $\left(q+1\right)$ solutions to $\epsilon
d^{2}-c^{2}=1$.

Then $\gamma_{1},...,\gamma_{q+1}$ generate a Ramanujan Cayley graph
isomorphic to the Morgenstern Cayley graph of the monic polynomial
corresponding to $\left(u-2\right)^{2m}h\left(\frac{u}{2-u}\right)$. The
elements $\left\\{\gamma_{1},...,\gamma_{q+1}\right\\}$ generate
$\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{2m}}\right)$ if and only if
$\left(\frac{2t\left(t+1\right)}{h\left(t\right)}\right)=\left(\frac{\tilde{h}\left(0\right)}{q}\right)\left(\frac{\tilde{h}\left(1\right)}{q}\right)=-1$.
The $\delta_{k}$ generate a Ramanujan Cayley graph isomorphic to
$\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{m}}\right)$. This is simplest to
see when $m$ itself is even, since then
$\epsilon\in\mathbb{F}_{q}\left(t^{2}\right)/\tilde{h}\left(t^{2}\right)\mathbb{F}_{q}\left(t^{2}\right)\subset\mathbb{F}_{q}\left(t\right)/h\left(t\right)\mathbb{F}_{q}\left(t\right)$,
and the $\delta_{k}$ are the generators given in [19, Equation (14)].

##  3 The Closed Orbit Method

The goal of this section is to formalize and prove Theorem 1.11, which we do
in Theorem 3.7. The proof follows the standard construction of arithmetic
cocompact lattices, and keeps track of its behavior when taking field
extensions. The essential results are the second part of Theorem 3.4 and Lemma
3.6, which relates lattices in a group with a lattice in a subgroup.

We use a number of standard results about semisimple groups over global
fields, which may be found in Prasad’s work [21]. To keep our arguments short,
we assume familiarity with the theory.

Here is our general setting: Let $k$ be global field (a number field or a
finite extension of $\mathbb{F}_{q}\left(t\right)$) and let $l$ be a finite
separable field extension of $k$. We denote the places of $k$ using the letter
$v$ with $k_{v}$ being the field completion. Similarly, we denote the places
of $l$ by the letter $w$, with $l_{w}$ being the field completion. For the
non-Archimedean places, we let $\mathcal{O}_{v}$ (resp. $\mathcal{O}_{w}$) be
the ring of integers of $k_{v}$ (resp. $l_{w}$), and let $\pi_{v}$ (resp.
$\pi_{w}$) be the uniformizer of $k_{v}$ (resp. $l_{w}$).

Let $\mathbb{A}_{k}$ and $\mathbb{A}_{l}$ be the adele rings of $k$ and $l$,
i.e.,

$\mathbb{A}_{k}=\left\\{\left(x_{v}\right)\in\prod_{v}k_{v}:x_{v}\in\mathcal{O}_{v}\text{
for almost every $v$}\right\\},$

and similarly for $\mathbb{A}_{l}$.

Let $\boldsymbol{G}$ be a semisimple algebraic group defined over $k$, defined
by set of equations as a subgroup of $\operatorname{SL}_{N}$. We will use the
same notation $\boldsymbol{G}$ for its extension of scalars to $l$. We assume
that $\boldsymbol{G}$ is connected, simply connected, and almost-simple over
$k$ and over $l$. Let $\boldsymbol{\tilde{G}}$ be the split form of
$\boldsymbol{G}$, so over the algebraic closure $\overline{k}$ of $k$ (and
$l$),
$\boldsymbol{G}\left(\overline{k}\right)\cong\boldsymbol{\tilde{G}}\left(\overline{k}\right)$.

Notice that $\boldsymbol{G}\left(k_{v}\right)$ and
$\boldsymbol{G}\left(l_{w}\right)$ are well defined, and have a natural
topology coming from the embedding
$\boldsymbol{G}\left(k_{v}\right)\subset\operatorname{SL}_{N}\left(k_{v}\right)\subset
M_{N}\left(k_{v}\right)$. In addition,
$\boldsymbol{G}\left(\mathcal{O}_{v}\right)$ and
$\boldsymbol{G}\left(\mathcal{O}_{w}\right)$ are also well defined for almost
every $v$ and almost every $w$. For almost every place $v$ of $k$, the
isomorphism
$\boldsymbol{G}\left(\overline{k}\right)\cong\boldsymbol{\tilde{G}}\left(\overline{k}\right)$
is actually defined over $k_{v}$, so there is an isomorphism
$\boldsymbol{G}\left(k_{v}\right)\cong\boldsymbol{\tilde{\boldsymbol{G}}}\left(k_{v}\right)$.
Moreover, after dropping a finite number of places $v$ of $k$,
$\boldsymbol{G}\left(\mathcal{O}_{v}\right)\cong\boldsymbol{\tilde{G}}\left(\mathcal{O}_{v}\right)$
is well defined, and is a maximal compact open subgroup of
$\boldsymbol{G}\left(k_{v}\right)$. For such $v$, let $w_{1},...,w_{m}$ be the
places of $l$ over $v$. Then
$\boldsymbol{G}\left(l_{w_{i}}\right)\cong\boldsymbol{\tilde{G}}\left(l_{w_{i}}\right)$,
$\boldsymbol{G}\left(\mathcal{O}_{w_{i}}\right)\cong\boldsymbol{\tilde{G}}\left(\mathcal{O}_{w_{i}}\right)$
and there is a diagonal embedding
$\boldsymbol{G}\left(k_{v}\right)\to\prod_{i=1}^{m}\boldsymbol{G}\left(k_{w_{i}}\right)$,
such that
$\boldsymbol{G}\left(k_{v}\right)\cap\prod\boldsymbol{G}\left(\mathcal{O}_{w_{i}}\right)=\boldsymbol{G}\left(\mathcal{O}_{v}\right)$.

For the finite number of non-Archimedean places where where the above does
hold, the embedding
$\boldsymbol{G}\left(k_{v}\right)\to\prod_{i=1}^{m}\boldsymbol{G}\left(k_{w_{i}}\right)$
is still well defined, and for every compact open subgroup of
$\prod_{i=1}^{m}K_{w_{i}}\leq\prod_{i=1}^{m}\boldsymbol{G}\left(l_{w_{i}}\right)$,
the subgroup
$K_{v}=\prod_{i=1}^{m}K_{w_{i}}\cap\boldsymbol{G}\left(k_{v}\right)\leq\boldsymbol{G}\left(k_{v}\right)$
is a compact open subgroup.

By the above, the adele group

$\boldsymbol{G}\left(\mathbb{A}_{k}\right)=\left\\{\left(g_{v}\right)\in\prod_{v}\boldsymbol{G}\left(k_{v}\right):g_{v}\in\boldsymbol{G}\left(\mathcal{O}_{v}\right)\text{
for almost every $v$}\right\\}$

is well defined, and has a natural topology coming from the topology of
$\mathbb{A}_{k}$ and the embedding
$\boldsymbol{G}\left(\mathbb{A}_{k}\right)\subset\operatorname{SL}_{N}\left(\mathbb{A}_{k}\right)\subset
M_{N}\left(\mathbb{A}_{k}\right)$. We have a diagonal embedding
$\boldsymbol{G}\left(k\right)\to\boldsymbol{G}\left(\mathbb{A}_{k}\right)$.
The same is true for $l$.

The local embeddings
$\boldsymbol{G}\left(k_{v}\right)\to\prod_{i=1}^{m}\boldsymbol{G}\left(k_{w_{i}}\right)$
extend to a global embedding
$\boldsymbol{G}\left(\mathbb{A}_{k}\right)\to\boldsymbol{G}\left(\mathbb{A}_{l}\right).$
Under this embedding, it holds that
$\boldsymbol{G}\left(\mathbb{A}_{k}\right)\cap\boldsymbol{G}\left(l\right)=\boldsymbol{G}\left(k\right)$.
We consider all of our groups as subgroups of
$\boldsymbol{G}\left(\mathbb{A}_{l}\right)$. For finite sets of places $V$,
$W$, there are natural projection maps

$\displaystyle P_{V}$
$\displaystyle:\boldsymbol{G}\left(\mathbb{A}_{k}\right)\to\prod_{v\in
V}\boldsymbol{G}\left(k_{v}\right)$ $\displaystyle P_{W}$
$\displaystyle:\boldsymbol{G}\left(\mathbb{A}_{l}\right)\to\prod_{w\in
W}\boldsymbol{G}\left(l_{w}\right).$

Recall that $\boldsymbol{G}$ is called isotropic over a field $F$ if
$G\left(F\right)$ contains a non-trivial split torus, and is called
anisotropic over $F$ otherwise. If $F$ is a local field, being anisotropic is
equivalent to $G\left(F\right)$ being compact in the appropriate topology. We
assume that $\boldsymbol{G}$ is anisotropic over $l$, which implies that it is
also anisotropic over $k$.

We have the following two basic theorems:

######  Theorem 3.1 (Borel, Behr, Harder).

$\boldsymbol{G}\left(k\right)\leq\boldsymbol{G}\left(\mathbb{A}_{k}\right)$
and
$\boldsymbol{G}\left(l\right)\leq\boldsymbol{G}\left(\mathbb{A}_{l}\right)$
are cocompact lattices.

######  Theorem 3.2 (The strong approximation property – Platonov, Prasad).

$G$ satisfies the strong approximation property over $k$ and over $l$, i.e.,
for every place $v$ where $k$ is isotropic,
$\boldsymbol{G}\left(k\right)\boldsymbol{G}\left(k_{v}\right)$ is dense in
$\boldsymbol{G}\left(\mathbb{A}_{k}\right)$. The same is true for $l$.

Let $V_{0}$ be a finite set of non-Archimedean places of $k$. We let $W_{0}$
be the places of $l$ over the places of $V_{0}$. We assume that
$\boldsymbol{G}$ is isotropic over some place in $V_{0}$, which implies that
it is isotropic over some place in $W_{0}$. If we work over number fields, we
further assume that $\boldsymbol{G}$ is anisotropic over all the Archimedean
places of $l$ which are not in $W_{0}$ (and therefore also over all the
Archimedean places of $k$ which are not in $V_{0}$).

We collect our various assumptions into the following definition.

######  Definition 3.3.

Assume that there exist:

  1. 1.

A global field $k$ and $l$ a finite separable field extension of $k$.

  2. 2.

A semisimple algebraic group $\boldsymbol{G}$ defined over $k$ which is
connected, simply connected, and almost-simple over $k$ and over $l$.
Moreover, $\boldsymbol{G}$ is anisotropic over $l$.

  3. 3.

A finite set $V_{0}$ of places of $k$, with $W_{0}$ the places of $l$ over the
places of $V_{0}$. The group $\boldsymbol{G}$ is isotropic over some place in
$V_{0}$, and is anisotropic over all the Archimedean places of $l$ which are
not in $W_{0}$.

Then we say that that the pair $\left(G,H\right)$ of a group $G$ and subgroup
$H\leq G$ is good, where

$\displaystyle G$ $\displaystyle=\prod_{w\in
W_{0}}\boldsymbol{G}\left(l_{w}\right)$ $\displaystyle H$
$\displaystyle=\prod_{v\in V_{0}}\boldsymbol{G}\left(k_{v}\right).$

Given a good pair $\left(G,H\right)$, our next goal is to choose a cocompact
lattice $\Gamma\leq G$, such that $\Gamma\cap H\leq H$ is also a cocompact
lattice.

Notice that $G$ embeds into $\boldsymbol{G}\left(\mathbb{A}_{l}\right)$ by

$G\cong\prod_{w\in W_{0}}\boldsymbol{G}\left(l_{w}\right)\times\prod_{w\notin
W_{0}}\left\\{\operatorname{id}\right\\}\leq\boldsymbol{G}\left(\mathbb{A}_{l}\right)$

and similarly $H$ embeds into $\boldsymbol{G}\left(\mathbb{A}_{k}\right)$.

We let

$\displaystyle\boldsymbol{G}\left(\mathbb{A}_{l}^{W_{0}}\right)$
$\displaystyle=\left\\{\left(g_{w}\right)_{w}\in\boldsymbol{G}\left(\mathbb{A}_{l}\right):\forall
w\in W_{0},g_{w}=\operatorname{id}\right\\}$
$\displaystyle\boldsymbol{G}\left(\mathbb{A}_{k}^{V_{0}}\right)$
$\displaystyle=\left\\{\left(g_{v}\right)_{v}\in\boldsymbol{G}\left(\mathbb{A}_{k}\right):\forall
v\in V_{0},g_{v}=\operatorname{id}\right\\},$

with the natural induced topology.

For $w\not\in W_{0}$ non-Archimedean, fix a compact open subgroup
$K_{w}\leq\boldsymbol{G}\left(l_{w}\right)$, equals almost everywhere to
$\boldsymbol{G}\left(\mathcal{O}_{w}\right)$. For the $w\notin W_{0}$
Archimedean, let $K_{w}=\boldsymbol{G}\left(l_{w}\right)$, which is compact by
our assumptions. For $v\notin V_{0}$, we let
$K_{v}=\prod_{i=1}^{m}K_{w_{i}}\cap\boldsymbol{G}\left(k_{v}\right)$, where
$w_{1},...,w_{m}$ are the places of $l$ over $v$. By the above, $K_{v}$ is a
compact open subgroup of $\boldsymbol{G}\left(k_{v}\right)$, which is equal
almost everywhere to $\boldsymbol{G}\left(\mathcal{O}_{v}\right)$.

The choices of $K_{w}$ define the compact open subgroup
$\boldsymbol{K_{l}}=\prod_{w\in
W_{0}}\left\\{\operatorname{id}\right\\}\times\prod_{w\not\in W_{0}}K_{w}$ of
$\boldsymbol{G}\left(\mathbb{A}_{l}^{W_{0}}\right)$. Then
$\boldsymbol{K_{k}}=\boldsymbol{K_{l}}\cap\boldsymbol{G}\left(\mathbb{A}_{k}\right)$
is a compact open subgroup of
$\boldsymbol{G}\left(\mathbb{A}_{k}^{V_{0}}\right)$ of the form
$\boldsymbol{K_{k}}=\prod_{v\in
V_{0}}\left\\{\operatorname{id}\right\\}\times\prod_{v\not\in V_{0}}K_{v}$.
Notice that $\boldsymbol{K_{l}}$ and $G$ commute with each other, and
$G\boldsymbol{K_{l}}$ is an open subgroup of
$\boldsymbol{G}\left(\mathbb{A}_{l}\right)$.

We choose

$\displaystyle\Gamma$
$\displaystyle=P_{W_{0}}\left(\boldsymbol{G}\left(l\right)\cap
G\boldsymbol{K_{l}}\right)$ (3.1) $\displaystyle\Gamma^{\prime}$
$\displaystyle=P_{V_{0}}\left(\boldsymbol{G}\left(k\right)\cap
H\boldsymbol{K_{k}}\right),$

so that $\Gamma,\Gamma^{\prime}$ are subgroups of $G=\prod_{w\in
W_{0}}\boldsymbol{G}\left(k_{w}\right)$ and $H=\prod_{v\in
V_{0}}\boldsymbol{G}\left(k_{v}\right)$.

######  Theorem 3.4.

  1. 1.

$\Gamma$ (resp. $\Gamma^{\prime}$) is a cocompact lattice in $G$ (resp. $H$).

  2. 2.

It holds that $\Gamma^{\prime}=H\cap\Gamma$.

###### Proof.

Most of this theorem is standard, and we avoid giving the full details. See
e.g., [19, Lemma 3.1] for a similar statement.

The discreteness of $\Gamma$ in $G$ essentially follows from the discreteness
of $l\cap\left(\prod_{w\notin W_{0}}\mathcal{O}_{w}\right)$ in $\prod_{w\in
W_{0}}l_{w}$.

By Theorem 3.1, $G\left(l\right)$ is a cocompact lattice in
$\boldsymbol{G}\left(\mathbb{A}_{l}\right)$. By the strong approximation
property and our assumptions, $\boldsymbol{G}\left(l\right)G$ is dense in
$\boldsymbol{G}\left(\mathbb{A}_{l}\right)$. Moreover, $G\boldsymbol{K}_{l}$
is open in $\boldsymbol{G}\left(\mathbb{A}_{l}\right)$. This implies that

$\boldsymbol{G}\left(l\right)G\boldsymbol{K}_{l}=\boldsymbol{G}\left(\mathbb{A}_{l}\right).$

Therefore, the map

$G\to
G\left(l\right)\backslash\boldsymbol{G}\left(\mathbb{A}_{l}\right)/\boldsymbol{K_{l}}$

is onto, and $g,g^{\prime}\in G$ are sent to the same element if there are
$k\in\boldsymbol{K_{l}}$ and $\gamma\in G\left(l\right)$ such that

$\gamma g=g^{\prime}k.$

However, $g$ and $k$ commute so we have $\gamma=g^{\prime}g^{-1}k.$ This
implies that $\gamma\in\boldsymbol{G}\left(l\right)\cap G\boldsymbol{K_{l}}$
and $g^{\prime}g^{-1}=P_{W_{0}}\left(\gamma\right)$.

On the other hand, if $\gamma\in\boldsymbol{G}\left(l\right)\cap
G\boldsymbol{K_{l}}$ and $g^{\prime}g^{-1}=P_{W_{0}}\left(\gamma\right)$, then
we may choose $k\in\boldsymbol{K_{l}}$ such that $\gamma g=g^{\prime}k$. We
conclude that there is an isomorphism

$\displaystyle\boldsymbol{G}\left(l\right)\backslash\boldsymbol{G}\left(\mathbb{A}_{l}\right)/\boldsymbol{K_{l}}$
$\displaystyle\cong
P_{W_{0}}\left(\boldsymbol{G}\left(l\right)\cap\boldsymbol{K_{l}}\right)\backslash
G$ $\displaystyle=\Gamma\backslash G.$

By considering the $G$ right action on the two spaces and the compatibility of
measures, we deduce that $\Gamma$ is a lattice in $G$.

For the same reasons,
$\Gamma^{\prime}=\pi_{V}\left(\boldsymbol{G}\left(k\right)\cap\boldsymbol{\boldsymbol{K}_{k}}\right)\leq
H$ is cocompact a lattice in $H$.

Finally, and this is where our proof is slightly less standard, since
$P_{W_{0}}\left(\boldsymbol{G}\left(l\right)\right)\cap
H=P_{w_{0}}\left(\boldsymbol{G}\left(k\right)\right)\cap H$,
$\boldsymbol{G}\left(k\right)\cap
G\boldsymbol{K_{l}}=\boldsymbol{G}\left(k\right)\cap H\boldsymbol{K_{k}}$, and
$P_{W_{0}}\left(\boldsymbol{G}\left(\mathbb{A}_{k}\right)\right)=P_{V_{0}}\left(\boldsymbol{G}\left(\mathbb{A}_{k}\right)\right)$,

$\Gamma\cap H$ $\displaystyle=P_{W_{0}}\left(\boldsymbol{G}\left(l\right)\cap
G\boldsymbol{K_{l}}\right)\cap H$
$\displaystyle=P_{W_{0}}\left(\boldsymbol{G}\left(k\right)\cap
G\boldsymbol{K_{l}}\right)\cap H$
$\displaystyle=P_{W_{0}}\left(\boldsymbol{G}\left(k\right)\cap
H\boldsymbol{\boldsymbol{K}_{k}}\right)$
$\displaystyle=P_{V_{0}}\left(\boldsymbol{G}\left(k\right)\cap
H\boldsymbol{\boldsymbol{K}_{k}}\right)=\Gamma^{\prime},$

as needed. ∎

Next, we construct congruence subgroups of $\Gamma$. Let $v_{1}$ be a place of
$k$ where it holds that
$K_{v_{1}}=\boldsymbol{G}\left(\mathcal{O}_{v}\right)\cong\boldsymbol{\tilde{G}}\left(\mathcal{O}_{v}\right)$.
Moreover, we want $v_{1}$ to be inert in the extension to $l$, and let $w_{1}$
be the place of $l$ over it. By Chebotarev’s density theorem there are
infinitely many such $v_{1}$.

Notice that we have a $(\operatorname{mod}w_{1})$-homomorphism
$\boldsymbol{G}\left(\mathcal{O}_{w_{1}}\right)\to\boldsymbol{G}\left(\mathcal{O}_{w_{1}}/\pi_{w_{1}}\mathcal{O}_{w_{1}}\right)$.
This map is onto since the group
$\boldsymbol{G}\left(\mathcal{O}_{w_{1}}/\pi_{w_{1}}\mathcal{O}_{w_{1}}\right)\cong\boldsymbol{\tilde{G}}\left(\mathcal{O}_{w_{1}}/\pi_{w_{1}}\mathcal{O}_{w_{1}}\right)$
is generated by its unipotent elements, which may be lifted to
$\boldsymbol{G}\left(\mathcal{O}_{w_{1}}\right)$.

As $P_{w_{1}}\left(\boldsymbol{G}\left(l\right)\cap
G\boldsymbol{K_{l}}\right)\subset\boldsymbol{G}\left(\mathcal{O}_{w_{1}}\right)$,
we have a homomorphism
$p_{w_{1}}:\Gamma\to\boldsymbol{G}\left(\mathcal{O}_{w_{1}}/\pi_{w_{1}}\mathcal{O}_{w_{1}}\right)$.
Similarly, we have a homomorphism
$p_{v_{1}}^{\prime}:\Gamma^{\prime}\to\boldsymbol{G}\left(\mathcal{O}_{v_{1}}/\pi_{v_{1}}\mathcal{O}_{v_{1}}\right)$.

Now, choose the “congruence subgroups”

$\displaystyle\Gamma\left(w_{1}\right)$ $\displaystyle=\ker
p_{w_{1}}\vartriangleleft\Gamma$ (3.2)
$\displaystyle\Gamma^{\prime}\left(v_{1}\right)$ $\displaystyle=\ker
p_{v_{1}}^{\prime}\vartriangleleft\Gamma^{\prime}.$

The split group $\boldsymbol{\tilde{G}}$ is a Chavalley group, which implies
that its size over a finite field $\mathbb{F}$ (over which it is defined)
satisfies:

$\boldsymbol{\tilde{G}}\left(\mathbb{F}\right)=\Theta\left(\left|\mathbb{F}\right|^{\dim
G}\right).$

Since $v_{1}$ is inert in the extension,
$\left|\mathcal{O}_{w_{1}}/\pi_{w_{1}}\mathcal{O}_{w_{1}}\right|=\left|\mathcal{O}_{v_{1}}/\pi_{v_{1}}\mathcal{O}_{v_{1}}\right|^{\left[l:k\right]}$.
Therefore, since $\boldsymbol{G}\cong\tilde{\boldsymbol{G}}$ in our case,

$\left|\boldsymbol{G}\left(\mathcal{O}_{v_{1}}/\pi_{v_{1}}\mathcal{O}_{v_{1}}\right)\right|=O\left(\left|\boldsymbol{G}\left(\mathcal{O}_{w_{1}}/\pi_{w_{1}}\mathcal{O}_{w_{1}}\right)\right|^{1/\left[l:k\right]}\right).$
(3.3)

######  Lemma 3.5.

The maps $p$ and $p^{\prime}$ are onto, so

$\displaystyle\Gamma/\Gamma\left(w_{1}\right)$
$\displaystyle\cong\boldsymbol{G}\left(\mathcal{O}_{w_{1}}/\pi_{w_{1}}\mathcal{O}_{w_{1}}\right)$
$\displaystyle\Gamma^{\prime}/\Gamma^{\prime}\left(v_{1}\right)$
$\displaystyle\cong\boldsymbol{G}\left(\mathcal{O}_{v_{1}}/\pi_{v_{1}}\mathcal{O}_{v_{1}}\right)$

###### Proof.

Let
$K_{w_{1}}^{\prime}=\ker\left(\boldsymbol{G}\left(\mathcal{O}_{w_{1}}\right)\to\boldsymbol{G}\left(\mathcal{O}_{w_{1}}/\pi_{w_{1}}\mathcal{O}_{w_{1}}\right)\right)$,
which is a finite index group of
$K_{w_{1}}=\boldsymbol{G}\left(\mathcal{O}_{w_{1}}\right)$, and therefore
compact open. Let $\boldsymbol{K_{l}^{\prime}}=\prod_{w\in
W_{0}}\left\\{\operatorname{id}\right\\}\times\prod_{w_{1}\neq w\in
W_{0}}K_{w}$. Notice that
$\Gamma\left(w_{1}\right)=P_{W_{0}}\left(\boldsymbol{G}\left(l\right)\cap
G\boldsymbol{K_{l}^{\prime}}\right).$

By the strong approximation theorem
$\boldsymbol{G}\left(l\right)G\boldsymbol{K_{l}^{\prime}}=\boldsymbol{G}\left(\mathbb{A}_{l}\right)$.
Therefore for every $k\in K_{w_{1}}$ there is
$\gamma\in\boldsymbol{G}\left(l\right)$ and $g\in G$ such that $k\in\gamma
g\boldsymbol{K_{l}^{\prime}}$. This implies that
$\gamma\in\boldsymbol{G}\left(l\right)\cap G\boldsymbol{K_{l}}$, so
$P_{W_{0}}\left(\gamma\right)\in\Gamma$. Finally,
$p_{w_{1}}\left(P_{W_{0}}\left(\gamma\right)\right)=P_{w_{1}}\left(\gamma\right)=kK_{w_{1}}^{\prime}$,
so $p$ is onto as needed.

The claim for $p_{v_{1}}^{\prime}$ is similar, by choosing

$\displaystyle K_{v_{1}}^{\prime}$
$\displaystyle=\ker\left(\boldsymbol{G}\left(\mathcal{O}_{v_{1}}\right)\to\boldsymbol{G}\left(\mathcal{O}_{v_{1}}/\pi_{v_{1}}\mathcal{O}_{v_{1}}\right)\right)$
$\displaystyle=K_{v_{1}}\cap K_{w_{1}}^{\prime}$

and $\boldsymbol{K_{k}^{\prime}}=\prod_{v\in
V_{0}}\left\\{\operatorname{id}\right\\}\times
K_{v_{1}}^{\prime}\times\prod_{v_{1}\neq v\in V_{0}}K_{v}$. ∎

######  Lemma 3.6.

$\Gamma\left(w_{1}\right)\cap H=\Gamma^{\prime}\left(v_{1}\right)$.

###### Proof.

Continuing the notations of the last proof
$\Gamma\left(w_{1}\right)=P_{W_{0}}\left(\boldsymbol{G}\left(l\right)\cap
G\boldsymbol{K_{l}^{\prime}}\right)$, and

$\displaystyle\Gamma\left(w_{1}\right)\cap H$
$\displaystyle=P_{W_{0}}\left(\boldsymbol{G}\left(l\right)\cap
G\boldsymbol{K_{l}^{\prime}}\right)\cap H$
$\displaystyle=P_{W_{0}}\left(\boldsymbol{G}\left(k\right)\cap
G\boldsymbol{K_{l}^{\prime}}\right)\cap H$
$\displaystyle=P_{W_{0}}\left(\boldsymbol{G}\left(k\right)\cap
H\boldsymbol{K_{k}^{\prime}}\right)\cap H$
$\displaystyle=P_{V_{0}}\left(\boldsymbol{G}\left(k\right)\cap
H\boldsymbol{K_{k}^{\prime}}\right)$
$\displaystyle=\Gamma^{\prime}\left(v_{1}\right).$

∎

We can finally state the precise form of Theorem 1.11.

######  Theorem 3.7.

Let $\left(G,H\right)$ be a good pair as above, $\Gamma$ as in Equation (3.1),
and $\Gamma\left(w_{1}\right)\vartriangleleft\Gamma$ as in Equation (3.2).
Then $\Gamma\cap H=\Gamma^{\prime}$ is a cocompact lattice in $H$, and for
$\Gamma^{\prime}\left(v_{1}\right)=\Gamma\left(w_{1}\right)\cap H$ it holds
that $\Gamma^{\prime}\left(v_{1}\right)=\Gamma^{\prime}\cap H$, and

$\left[\Gamma^{\prime}\left(v_{1}\right):\Gamma^{\prime}\right]=O\left(\left|\Gamma:\Gamma\left(w_{1}\right)\right|^{1/\left[l_{0}:k_{0}\right]}\right).$

Therefore, if $W_{0}$ contains only non-Archimedean places and $K$ is a
maximal compact open subgroup of $G$ and $K_{H}=H\cap K$ is the corresponding
compact open subgroup of $H$,

$\left|\Gamma^{\prime}\left(v_{1}\right)\backslash
H/K_{H}\right|=O\left(\left|\Gamma\left(w_{1}\right)\backslash
G/K\right|^{1/\left[l_{0}:k_{0}\right]}\right).$

###### Proof.

Almost all of the theorem was proven above, except for the last part. It holds
that

$\left|\Gamma\backslash
G/K\right|\left[\Gamma:\Gamma\left(w_{1}\right)\right]\left|\Gamma\cap
K\right|^{-1}\leq\left|\Gamma\left(w_{1}\right)\backslash
G/K\right|\leq\left|\Gamma\backslash
G/K\right|\left[\Gamma:\Gamma\left(w_{1}\right)\right].$

Since $\Gamma\backslash G/K$ and $\Gamma\cap K$ are finite (this is where we
use the fact that $W_{0}$ has no Archimedean places),

$\left|\Gamma\left(w_{1}\right)\backslash
G/K\right|=\Theta\left(\left[\Gamma:\Gamma\left(w_{1}\right)\right]\right)$

The arguments for $\Gamma^{\prime}$ are the same. ∎

##  4 Applications of the Closed Orbit Method

In this section we explain how the arguments of the last section apply to
groups defined by quaternion algebras and division algebras, which will then
give us interesting lattices in $\operatorname{SL}_{n}$.

###  4.1 Closed Orbits in Division Algebras

Let $A$ be a division algebra over a global field $k$. For simplicity we
assume that $k$ is a function field and the degree $n$ of $A$ is a prime.

Since we assume that $n$ is prime, over any completion $k_{v}$,
$A\left(k_{v}\right)$ is either a division algebra, in which case we say that
$A$ ramifies at $v$, or isomorphic to $M_{n}\left(k_{v}\right)$, in which case
we say that $A$ splits or is unramified at $v$. The
Albert–Brauer–Hasse–Noether Theorem implies that given any subset of places
$v_{1},...,v_{m}$, we may choose $A$ that will ramify only at a subset of
$v_{1},...,v_{m}$, and may choose
$A\left(k_{v_{1}}\right),...,A\left(k_{v_{m-1}}\right)$ as we want up to
isomorphism ($A\left(k_{v_{m}}\right)$ will be determined by the others).

Now let $l$ be a separable field extension of $k$. Given a place $v$ of $k$
and a place $w$ of $l$ over it, it holds that $A\left(l_{w}\right)$ will be
split if and only if it is possible to embed $l_{w}$ in $A\left(k_{v}\right)$.
We will restrict ourselves to quadratic extensions, and recall that $n$ is
prime. In this case:

  1. 1.

If $n\neq 2$ then $A\left(l_{w}\right)$ splits if and only if
$A\left(k_{v}\right)$ splits.

  2. 2.

If $n=2$:

    1. (a)

If $A$ splits at $v$ then it splits at $w$, i.e., if $A\left(k_{v}\right)\cong
M_{2}\left(k_{v}\right)$, then $A\left(l_{w}\right)\cong
M_{2}\left(l_{w}\right)$.

    2. (b)

If $A$ ramifies at $v$ then it remains ramified in $w$ if and only if $v$
splits in the extension from $l$ to $k$.

Now consider the semisimple algebraic group $\boldsymbol{G}$ defined over $k$
by

$\boldsymbol{G}\left(k\right)=\left\\{\alpha\in
A\left(k\right):N\left(\alpha\right)=1\right\\}.$

The group $\boldsymbol{G}$ is connected, simply connected and absolutely
almost simple. The split form of $\boldsymbol{G}$ is $\operatorname{SL}_{n}$.
The group $\boldsymbol{G}$ is anisotropic over a $k_{v}$ (resp. $l_{w}$) if
and only if the algebra $A$ ramifies at $k_{v}$ (resp. $l_{w}$). The group
$\boldsymbol{G}$ is anisotropic over $k$ (resp. $l$) if and only if $A$ has a
ramified place $k_{v}$ (resp. $l_{w}$).

We conclude that Definition 3.3 will holds if $\boldsymbol{G}$ has a ramified
place over $l$, and if $V_{0}$ contains a place where $A$ splits. Let us focus
on the case when $V_{0}=\left\\{v_{0}\right\\}$ is a split place with a single
place $w_{0}$ above $v_{0}$ (so $W_{0}=\left\\{w_{0}\right\\}$). Then
$G=\boldsymbol{G}\left(l_{w_{0}}\right)\cong\operatorname{SL}_{n}\left(l_{w_{0}}\right)$
and
$H=\boldsymbol{G}\left(k_{v_{0}}\right)\cong\operatorname{SL}_{n}\left(k_{v_{0}}\right)$.
We with to show that Theorem 3.7 applies to those cases.

######  Proposition 4.1.

The pairs

$\displaystyle\left(G,H\right)=\left(\operatorname{SL}_{n}\left(\mathbb{F}_{q}\left(\left(t\right)\right)\right),\operatorname{SL}_{n}\left(\mathbb{F}_{q}\left(\left(t^{2}\right)\right)\right)\right)$
or
$\displaystyle\left(G,H\right)=\left(\operatorname{SL}_{n}\left(\mathbb{F}_{q^{2}}\left(\left(t\right)\right)\right),\operatorname{SL}_{n}\left(\mathbb{F}_{q}\left(\left(t\right)\right)\right)\right)$

are good, i.e., satisfy Definition 3.3.

###### Proof.

We start with the second case as it is simpler. We first let
$k=\mathbb{F}_{q}\left(t\right)$ and choose the place $v_{0}=s$, so
$k_{0}=k_{v_{0}}=\mathbb{F}_{q}\left(\left(t\right)\right)$. We let
$l=\mathbb{F}_{q^{2}}\left(t\right)$ be the quadratic constant field extension
of $k$. Then $v_{0}$ is inert in the extension, i.e. have a unique place
$w_{0}=t$ over it, with
$l_{w_{0}}=l_{0}=\mathbb{F}_{q^{2}}\left(\left(t\right)\right)$. We then let
$A$ be a division algebra of degree $n$ which splits at $k_{0}$ but is
ramifies over $k$ and remains ramified over $l$. It is easy to see that it can
happen – for $n>2$ we may choose any division algebra over $k$ (it will remain
a division algebra over $l$), and for $n=2$ we need to make sure that $A$ will
also ramify at some place $v$ corresponding to a polynomial of even degree,
since it will then split in the extension and there will remain ramified
places. All the conditions of Definition 3.3 therefore hold for
$G=\boldsymbol{G}\left(l_{0}\right)\cong\operatorname{SL}_{n}\left(\mathbb{F}_{q^{2}}\left(\left(t\right)\right)\right)$,
$H=\boldsymbol{G}\left(k_{0}\right)\cong\operatorname{SL}_{n}\left(\mathbb{F}_{q}\left(\left(t\right)\right)\right)$.

For the first case, we let $k=\mathbb{F}_{q}\left(s\right)$, and let $l$ be a
separable quadratic extension of $k$ which ramifies at the place $v_{0}=s$.
For $\operatorname{char}q\neq 2$ we may take $l=\mathbb{F}_{q}\left(t\right)$
for $t^{2}=s$. For $\operatorname{char}q=2$ this extension no longer works
since it is not separable. Instead we may look at the extension
$\mathbb{F}_{q}\left(u\right)$ which we get by adding a root to
$u^{2}+su+1=0$. Once again, we choose a division algebra $A$ such that it
splits at $k_{0}$ and ramifies over $k$ and over $l$. It is simple to see that
such $A$ exists. In any case, if $w_{0}$ is the place of $l$ over $v_{0}$,
then locally we have $l_{0}=\mathbb{F}_{q}\left(\left(t\right)\right)$ for
some $t$ such that $t^{2}=s$. Therefore,
$G=\boldsymbol{G}\left(l_{0}\right)\cong\operatorname{SL}_{n}\left(\mathbb{F}_{q}\left(\left(t\right)\right)\right)$
and
$H=\boldsymbol{G}\left(k_{0}\right)\cong\operatorname{SL}_{n}\left(\mathbb{F}_{q}\left(\left(t^{2}\right)\right)\right)$,
as needed. ∎

####  4.1.1 The Explicit Construction

Let us explain how the abstract arguments are related to the explicit
construction. For $\operatorname{char}q\neq 2$, let
$k=\mathbb{F}_{q}\left(s\right)$ and let $l=\mathbb{F}_{q}\left(t\right)$ for
$t^{2}=s$. Let $v_{0}=s$, $w_{0}=t$, so
$k_{0}=\mathbb{F}_{q}\left(\left(s\right)\right)$ and
$l_{0}=\mathbb{F}_{q}\left(\left(t\right)\right)$. We choose the algebra
$A_{2}$ with the basis $1,i,j,ij$, and the relations
$i^{2}=\epsilon,j^{2}=s-1,ij=-ji$, for $\epsilon\in\mathbb{F}_{q}$ non-square.
The algebra $A_{2}$ ramifies at $1/s$ and $s-1$ and satisfies the conditions.
Over $t$ the algebra $A_{2}$ ramifies at $t-1$ and $t+1$, and is isomorphic to
the algebra $A_{1}$ defined by the relations
$i^{2}=\epsilon,j^{2}=\frac{t-1}{t+1},ij=-ji$. After a change of variables
$u=\frac{2t}{2+1}$, the algebra $A_{1}$ is isomorphic to the algebra $A$ over
$\mathbb{F}_{q}\left(u\right)$, defined by $i^{2}=\epsilon$, $j^{2}=u-1$,
$ij=-ji$. Moreover, the place $t$ correspond to the place $u$ under this
isomorphism. Let $\boldsymbol{G}=\operatorname{PGL}_{1}\left(A_{2}\right)$.

Notice that $\boldsymbol{G}$ is not simply connected, but most of the general
argument of Section 3 applies to it, with some modifications we discuss below.

Since $A_{2}$ over $\mathbb{F}_{q}\left(t\right)$ and $A$ over
$\mathbb{F}_{q}\left(u\right)$ are isomorphic, the construction of Morgenstern
in [19] allows us to find a compact open subgroup
$\boldsymbol{K_{l}}\subset\boldsymbol{G}\left(\mathbb{A}_{l}^{\\{t\\}}\right)$
, such that
$\Gamma=P_{\left\\{t\right\\}}\left(\boldsymbol{G}\left(l\right)\cap
G\boldsymbol{K_{l}}\right)\leq G=\boldsymbol{G}\left(l_{0}\right)$ is a
lattice in $G$ which acts simply transitively on the Bruhat-Tits building of
$G$, and all of its congruence subgroups define Ramanujan graphs.

The arguments of Section 3 (when extended to the non-simply connected case)
say that $\Gamma^{\prime}=\Gamma\cap H\leq H=\boldsymbol{G}\left(k_{0}\right)$
is a lattice in $H$. As a matter of fact, direct calculation shows that
$\Gamma^{\prime}$ is generated by $\gamma_{1}^{2},...,\gamma_{q+1}^{2}$, where
$\gamma_{1},...,\gamma_{q+1}$ are the generators of $\Gamma$, and more
importantly, $\Gamma^{\prime}$ acts simply transitively on the Bruhat-Tits
building of $H$. This implies that the map
$F_{\Gamma}:\Gamma^{\prime}\backslash B_{H}\to\Gamma\backslash B_{G}$ is
injective, since both sets are of size $1$. Finally, we take congruence covers
$\Gamma\left(w_{1}\right)$ and $\Gamma^{\prime}\left(v_{1}\right)$ as above,
to get a map from a small graph to a large graph.

The fact that $\boldsymbol{G}$ is not simply connected mainly implies that the
exact behavior of $\Gamma/\Gamma\left(w_{1}\right)$ and
$\Gamma^{\prime}/\Gamma\left(v_{1}\right)$ is not known from the general
arguments. To understand it we need some more work that is done by Morgenstern
in [19] and the calculations of Section 2.

###  4.2 The Bruhat-Tits Building

In this subsection, let $l_{0}=\mathbb{F}_{q}\left(\left(t\right)\right)$ and
we quickly recall the Bruhat-Tits building of
$\operatorname{SL}_{n}\left(l_{0}\right)$ and its Ramanujan quotients. When
$n=2$, the Bruhat-Tits building is a tree, and a good reference is [11]. For
$n>2$, see [12] and the references therein.

It is simpler to work with $G=\operatorname{PGL}_{n}\left(l_{0}\right)$, as
the buildings are the same, and $\operatorname{SL}_{n}\left(l_{0}\right)$ acts
on the building by its image
$\operatorname{PSL}_{n}\left(l_{0}\right)\subset\operatorname{PGL}_{n}\left(l_{0}\right)$.
Let $\mathcal{O}=\mathbb{F}_{q}\left[\left[t\right]\right]$ be the ring of
integers of $l_{0}$. Let $K=\operatorname{PGL}_{n}\left(\mathcal{O}\right)$,
which is a maximal compact open subgroup of $G$.

The Bruhat-Tits building $B_{G}$ of $G$ is a clique complex whose vertices can
be identified with $G/K$ (in general, we identify a building with its
vertices). The set $G/K$ can also be described as all the $\mathcal{O}$
submodules of $l_{0}^{n}$, up to homothety (multiplication by a scalar from
$l_{0}$). There is an edge between two modules
$\left[M\right]\neq\left[M^{\prime}\right]$ if they have representatives
$M,M^{\prime}$ such that $tM\subseteq M^{\prime}\subsetneq M$. There is a
bijection between equivalence classes of modules $\left[M\right]$ and matrices
$A_{M}\in M_{n}\left(\mathbb{F}_{q}\left[t\right]\right)$, of the form

$A_{M}=\left(\begin{array}[]{cccc}t^{m_{1}}&f_{1,2}\left(t\right)&&f_{1,n}\left(t\right)\\\
0&t^{m_{2}}&&f_{2,n}\left(t\right)\\\ \\\ 0&&0&t^{m_{n}}\end{array}\right),$

such that:

  1. 1.

$m_{1}\geq 0,...,m_{n}\geq 0$, for $1\leq i<j\leq n$.

  2. 2.

$f_{i,j}\in\mathbb{F}_{q}\left[t\right]$ satisfies $\deg f_{i,j}<m_{i}$ for
$i<j$.

  3. 3.

$\gcd\left(t^{m_{1}},...,t^{m_{n}},f_{1,2}\left(t\right),...f_{n-1,n}\left(t\right)\right)=1$.

The bijection is given by sending a matrix $A$ to the module generated by its
columns. We identify a module with the corresponding matrix by this bijection.

Each module $M$ has a color
$c\left(M\right)\in\left[n\right]=\left\\{0,...,n-1\right\\}$. It is uniquely
determined by $\det\left(A_{M}\right)=t^{c\left(M\right)+nz}$, for some
$z\in\mathbb{N}$. The subgroup $\operatorname{PSL}_{n}\left(l_{0}\right)\leq
G$ acts transitively on vertices of color $0$.

Let $M_{0}$ be the “standard module” corresponding to the identity matrix $I$,
or the identity coset in $G/K$. Its neighbors are the modules which
corresponding to the set $N=\left\\{A_{M_{1}},...,A_{M_{t}}\right\\}$ of
matrices $A_{M_{i}}$ as above, which further satisfy:

  1. 1.

$0\leq m_{1},...,m_{n}\leq 1$.

  2. 2.

If $m_{j}=1$ then $f_{i,j}=0$ for $i<j$.

  3. 3.

$A\neq I$.

Finally, for every module $M$, its neighbors correspond to matrices of the
form $\left\\{A_{M}A:A\in N\right\\}$, up to dividing by a power of $t$ which
is the gcd of all the elements.

Given a lattice $\Gamma\leq\operatorname{PGL}_{n}\left(l_{0}\right)$ , we may
look at the quotient space $\Gamma\backslash B_{G}$. Assuming that $\Gamma$
does not intersect a big enough neighborhood of the identity (and in
particular, is torsion-free), $\Gamma\backslash B_{G}$ is a simplicial
complex. In the case $n=2$ this is a $\left(q+1\right)$-regular graph. We
again refer to [12] for a discussion of such complexes. If we have a lattice
$\Gamma^{\prime}\leq\operatorname{SL}_{n}\left(l_{0}\right)$ we may project it
to $\Gamma^{\prime}\leq\operatorname{PGL}_{n}\left(l_{0}\right)$, and then,
assuming that $\Gamma^{\prime}$ is torsion free,
$\left|\Gamma^{\prime}\backslash\operatorname{SL}_{n}\left(l_{0}\right)/\operatorname{SL}_{n}\left(\mathcal{O}\right)\right|=n\left|\Gamma\backslash
B_{G}\right|$, since $\operatorname{SL}_{n}\left(l_{0}\right)$ preserves the
color of the vertices of $B\left(G\right)$.

For the lattices $\Gamma$ constructed from division algebras in this work, for
every compact subset $S\subset G$, it holds that as $w_{1}$ changes,
eventually $\Gamma\left(w_{1}\right)\cap M\in\left\\{e\right\\}$. This implies
that $\Gamma\left(w_{1}\right)\backslash B_{G}$ will indeed eventually be a
simplicial complex. A far deeper fact is that over function fields,
$\Gamma\left(w_{1}\right)\backslash B_{G}$ is a “Ramanujan complex” – see [15,
5, 9] for a general discussion of this concept, and specifically [5, Section
7] for a proof.

###  4.3 Vertex Expansion

Consider $l_{0}=\mathbb{F}_{q}\left(\left(t\right)\right)$ and its subfield
$\mathbb{F}_{0}=F_{q}\left(\left(t^{2}\right)\right)$. Let
$\mathcal{O}_{k_{0}}=\mathbb{F}_{q}\left[\left[t^{2}\right]\right]$,
$\mathcal{O}_{l_{0}}=\mathbb{F}_{q}\left[\left[t\right]\right]$ be the
corresponding rings of integers.

We let $G=\operatorname{PGL}_{n}\left(l_{0}\right)$,
$H=\operatorname{PGL}_{n}\left(k_{0}\right)$, and
$K=\operatorname{PGL}_{n}\left(\mathcal{O}_{l_{0}}\right)$, $K_{H}=H\cap
K=\operatorname{PGL}_{n}\left(\mathcal{O}_{k_{0}}\right)$ the maximal compact
open subgroups. We have an action of $H$ on Bruhat-Tits building $B_{G}$ of
$G$, and since the stabilizer of the standard module is $K_{H}$, we have a map
(on vertices) $F:B_{H}\to B_{G}$. See Figure 1.1 for a special case of this
embedding.

We consider the set $N$ defining the neighbors in $B_{G}$ and the set $N_{H}$
defining the neighbors in $B_{H}$, as in Subsection 4.2. There is a bijection
$T:N\to N_{H}$, with $A\in N$ corresponding to $T\left(A\right)\in N_{H}$
where $t$ is replaced by $s=t^{2}$. Let $A\in N$ with diagonal
$\left(t^{m_{1}},...,t^{m_{n}}\right)$, then we get $T\left(A\right)$ by
simply replacing the diagonal with $\left(t^{2m_{1}},...,t^{2m_{n}}\right)$.
Moreover, if $m_{j}=1$ then the $j$-th column is 0 outside the diagonal, and
this implies that $T\left(A\right)=AD\left(A\right)$, where
$D\left(A\right)=\operatorname{diag}\left(t^{m_{1}},...,t^{m_{n}}\right)$ is
the diagonal matrix with the same diagonal as $A$. Notice that
$D\left(A\right)\in N$. Therefore, if $A_{M}\in B_{H}$, then
$F\left(A_{M}T\left(A\right)\right)=F\left(A_{M}\right)AD\left(A\right)$. This
discussion may be concluded as follows:

######  Lemma 4.2.

Let $M\in F\left(B_{H}\right)\subset B_{G}$, and let $M^{\prime}=MA$, $A\in N$
be a neighbor of $M$ in $B_{G}$. Then there is
$M^{\prime\prime}=M^{\prime}D\left(A\right)=MT\left(A\right)\in
F\left(B_{H}\right)$, another neighbor of $M^{\prime}$ from
$F\left(B_{H}\right)$.

Therefore, F$\left(B_{H}\right)\subset B_{G}$ has no unique neighbors (i.e.,
neighbors that are connected to it by a single edge).

We may now prove Theorem 1.5:

###### Proof of Theorem 1.5.

By Proposition 4.1, Theorem 3.7, and the discussion in Subsection 4.2, there
is a lattice $\Gamma\leq\operatorname{PGL}_{n}\left(l_{0}\right)$ of
arbitrarily large covolume, such that if we denote $Y^{\prime}=\Gamma\cap
H\backslash B_{H}$, $X=\Gamma\backslash B_{G}$, then
$\left|Y^{\prime}\right|=O\left(\left|X\right|^{1/2}\right)$ and $X$ and
$Y^{\prime}$ are Ramanujan complexes.

There is also a natural map $F_{\Gamma}:Y^{\prime}\to X$. It holds that
$Y=F_{\Gamma}\left(Y^{\prime}\right)$ is the image of $F\left(B_{H}\right)$
under the projection $B_{G}\to\Gamma\backslash B_{G}=X$. By Lemma 4.2
$F\left(B_{H}\right)$ has no unique neighbors in $B_{G}$. Therefore, the set
$Y$ – the projection of $F\left(B_{H}\right)$ to $X$ – has no unique
neighbors. ∎

We may also complete the proof of Theorem 1.1.

###### Proof of Theorem 1.1.

For $n=2$ the complex $X$ of Theorem 1.5 is a graph, and there is a subset
$Y\subset X$, $|Y|=O(\sqrt{|X|})$, such that each $y\in N\left(Y\right)$ is
connected to at least two vertices of $Y$. Then we can show that every $y\in
N\left(Y\right)$ is connected to precisely $2$ vertices of $N\left(Y\right)$,
as in the proof of Lemma 2.8 (see also the proof of Theorem 1.8 in Subsection
4.4). ∎

###  4.4 Edge Expansion

Let us now take $n=2$, $l_{0}=\mathbb{F}_{q^{2}}\left(\left(t\right)\right)$
and $G=\operatorname{PGL}_{2}\left(l_{0}\right)$. Let
$k_{0}=\mathbb{F}_{q}\left(\left(t\right)\right)$, and
$H=\operatorname{PGL}_{2}\left(k_{0}\right)$, which is a subgroup of $G$.

The Bruhat-Tits building $B_{G}$ of $G$, which is described in the previous
section, is a $\left(q^{2}+1\right)$-regular tree. Explicitly, the set $N$
determining the neighbors contains $\left(\begin{array}[]{cc}1&0\\\
0&t\end{array}\right)$ and $\left(\begin{array}[]{cc}t&a\\\
0&1\end{array}\right)$ for $a\in\mathbb{F}_{q^{2}}$.

The subgroup $H$ acts on $B_{G}$, and the stabilizer of the standard module
$M_{0}$ is
$H\cap\operatorname{PGL}_{2}\left(\mathbb{F}_{q^{2}}\left[\left[t\right]\right]\right)=\operatorname{PGL}_{2}\left(\mathbb{F}_{q}\left[\left[t\right]\right]\right)$,
which is a maximal compact open subgroup of $H$. We therefore have a map
$F:B_{H}\to B_{G}$. Let $N_{H}$ be the set determining the neighbors in
$B_{H}$, which contains $\left(\begin{array}[]{cc}1&0\\\
0&t\end{array}\right)$ and $\left(\begin{array}[]{cc}t&a\\\
0&1\end{array}\right)$ for $a\in\mathbb{F}_{q}$. Notice that $N_{H}\subset H$.
Moreover, for $A\in N_{H}$ and $M\in B_{H}$ described by its matrix,
$f\left(MA\right)=f\left(M\right)A$. In other words, adjacent vertices in
$B_{H}$ are sent to adjacent vertices in $B_{G}$ (see Figure 1.8 for a special
case).

The discussion above implies:

######  Lemma 4.3.

Every vertex in $F\left(B_{H}\right)\subset B_{G}$ is connected to $q+1$ other
vertices of $F\left(B_{H}\right)$.

We may now prove Theorem 1.8 from the introduction:

###### Proof of Theorem 1.8.

By Proposition 4.1, Theorem 3.7, and the discussion in Subsection 4.2, there
is a lattice $\Gamma\leq\operatorname{PGL}_{2}\left(l_{0}\right)$ of
arbitrarily large covolume, such that if we denote $Y^{\prime}=\Gamma\cap
H\backslash B_{H}$, $X=\Gamma\backslash B_{G}$, then
$\left|Y^{\prime}\right|=O\left(\left|X\right|^{1/2}\right)$ and $X$ and
$Y^{\prime}$ are Ramanujan graphs.

There is also a natural map $F_{\Gamma}:Y^{\prime}\to X$. By Lemma 4.3, every
vertex of $Y=F_{\Gamma}\left(Y^{\prime}\right)$ is connected to at least $q+1$
other vertices of $Y$, as $Y=F_{\Gamma}\left(Y\right)$ is the image of
$F\left(Y\right)$ by the projection map $B_{G}\to\Gamma\backslash B_{G}$.

We claim that $Y$ is $\left(q+1\right)$-regular. This also implies that $Y$ is
a quotient of $Y^{\prime}$, and is therefore a Ramanujan graph.

If $Y$ is not $\left(q+1\right)$-regular, there is a vertex $y\in Y$ that is
connected to more than $\left(q+1\right)$ other elements of $Y$. We next use
symmetry as in the proof of Lemma 2.8. Notice that the group
$\Gamma\left(w_{1}\right)\backslash\Gamma$ acts on $X$, and its subgroup
$\Gamma^{\prime}\left(v_{1}\right)\backslash\Gamma^{\prime}$ (using the
natural embedding
$\Gamma^{\prime}\left(v_{1}\right)\backslash\Gamma^{\prime}\to\Gamma\left(w_{1}\right)\backslash\Gamma$)
preserves $Y$. Therefore, there are
$\Theta\left(\left|\Gamma^{\prime}\left(v_{1}\right)\backslash\Gamma^{\prime}\right|\right)=\Theta\left(\left|Y\right|\right)$
vertices in $Y$ that are connected to more than $q+1$ vertices. Since the
minimal degree of $Y$ is $q+1$, the average degree is greater than
$q+1+\delta$ for some explicit $\delta>0$. This is impossible by Kahale’s
Theorem 1.7. ∎

##  5 Expansion Using Moore’s Bound

In this section we reprove Kahale’s lower bounds about vertex and edge
expansion in Ramanujan graphs. While the bounds we get are a bit weaker than
Kahale’s, we believe that they are easier to understand.

First, let us set notations. An undirected graph is a finite set $X$ of
vertices, a finite set $E$ of directed edges, two maps $s,t:E\to X$, and an
involution $\overline{\cdot}:E\to E$, satisfying the conditions
$s\left(\overline{e}\right)=t\left(e\right)$, $\overline{e}\neq e$. We allow
multiple edges and self loops, but no ”half edges”. For $x\in X$ we let
$d_{x}=\\#\left\\{e\in E:s\left(e\right)=x\right\\}$ be the degree of $x$. We
assume that $X$ is connected.

A non-backtracking path of length $l$ in $X$ is a sequence
$\left(e_{1},...,e_{l}\right)$ of edges, with
$t\left(e_{i}\right)=s\left(e_{i+1}\right)$ and $e_{i+1}\neq\overline{e_{i}}$.
We denote by $M_{l}\left(X\right)$ the number of non-backtracking paths of
length $l$ in $X$.

Given a subset $S\subseteq X$, we have an induced graph on $S$, containing all
the edges $e\in E$ with $s\left(e\right),t\left(e\right)\in S$. Therefore
$M_{l}\left(S\right)$ is well defined. We also denote by
$M_{l}\left(S,X\right)$ the non-backtracking paths
$\left(e_{1},...,e_{l}\right)$ in $X$ such that
$s\left(e_{1}\right),t\left(e_{l}\right)\in S$.

Our proofs uses the results of [2], whose main technical result is:

######  Theorem 5.1 ([2]).

Let $X$ be an undirected graph with $m$ directed edges, and assume that $X$
has no vertices of degree $1$. Let

$\tilde{d}-1=\left(\prod_{e\in
E}\left(d_{s\left(e\right)}-1\right)\right)^{1/m}=\left(\prod_{x\in
X}\left(d_{x}-1\right)^{d_{x}}\right)^{1/m},$

i.e., the geometric average over the edges of the degree of their source
vertex minus $1$. Then

$M_{l}\left(X\right)\geq m\left(\tilde{d}-1\right)^{l-1}.$

While the number $\tilde{d}$ is somewhat complicated, it holds:

######  Lemma 5.2.

Assume that $X$ is a graph without vertices of degree $1$. Then:

  1. 1.

([2]) $\tilde{d}\geq\overline{d}$, where $\overline{d}$ is the average degree
of $X$.
Moreover, for every $C>0$, for every $\epsilon>0$ there is $\delta>0$ such
that if $\tilde{d}\leq\overline{d}+\delta$ and $\overline{d}\leq C$, then
there is $d\geq 2$ satisfying $\left|\tilde{d}-d\right|\leq\epsilon$, and all
but $\epsilon n$ of the vertices of $X$ are of degree $d$.

  2. 2.

If $X$ is bipartite,
$\tilde{d}-1\geq\sqrt{\left(\overline{d}_{L}-1\right)\left(\overline{d}_{R}-1\right)}$,
where $\overline{d}_{L}$ (resp. $\overline{d}_{R}$) is the average degree of
the left side (resp. the right side) of $X$.

######  Remark 5.3.

A similar “moreover” argument is true for the bipartite case, but we will not
need it.

###### Proof.

For the first claim, it holds that $m=\overline{d}n$. Therefore
$\tilde{d}-1=\left(\prod_{x\in
X}\left(d_{x}-1\right)^{d_{x}}\right)^{1/\overline{d}n}$. So

$\log\left(\tilde{d}-1\right)=\frac{1}{\overline{d}}\frac{1}{n}\sum_{x\in
X}d_{x}\log\left(d_{x}-1\right)\geq\frac{1}{\overline{d}}\overline{d}\log\left(\overline{d}-1\right)=\log\left(\overline{d}-1\right),$

where the inequality follows from the convexity of $d\log\left(d-1\right)$ for
$d\geq 2$. The moreover part follows from the strict convexity of
$d\log\left(d-1\right)$ for $d\geq 2$.

For the second claim, let $n_{L},n_{R}$ be the number of vertices in
$X_{L},X_{R}$ – the right and left sides of $X$. Then

$n_{L}\overline{d}_{L}=n_{R}\overline{d}_{R}=m/2.$

Therefore

$\displaystyle\tilde{d}-1$ $\displaystyle=\left(\prod_{x\in
X}\left(d_{x}-1\right)^{d_{x}}\right)^{1/\overline{d}n}$
$\displaystyle=\left(\prod_{x\in
X_{L}}\left(\left(d_{x}-1\right)^{d_{x}}\right)^{1/\overline{d}_{L}n_{L}}\right)^{1/2}\left(\prod_{x\in
X_{R}}\left(\left(d_{x}-1\right)^{d_{x}}\right)^{1/\overline{d}_{R}n_{R}}\right)^{1/2}$
$\displaystyle\leq\sqrt{\left(\overline{d}_{L}-1\right)\left(\overline{d}_{R}-1\right)},$

where the inequality is as in the proof of the first claim. ∎

We combine the lower bound on $M_{l}\left(S\right)$ coming from Moore’s bound,
with a standard upper bound from spectral graph theory.

We let $L^{2}\left(X\right)$ be the set of functions $f:X\to\mathbb{C}$, with
the usual inner product. The adjacency operator $A:L^{2}\left(X\right)\to
L^{2}\left(X\right)$ is defined as

$\left(Af\right)\left(x\right)=\sum_{e\in
E,t\left(e\right)=x}f\left(s\left(e\right)\right).$

The operator $A$ is self-adjoint and therefore diagonalizable, with real
eigenvalues and an orthogonal basis of eigenvectors. If $X$ is $d$-regular,
the constant function is an eigenvector of $A$, with eigenvalue $d$. If $X$ is
bipartite, $A$ has the eigenvalue $-d$, corresponding to the eigenvector that
is equal to a constant $C$ on one side, and is equal to $-C$ on the other
side. If $X$ is connected, as we assume, those are the only eigenvectors with
eigenvalues of absolute value $d$. We say that $X$ is Ramanujan if every
eigenvalue $\lambda$ of $A$ satisfies either $\left|\lambda\right|=d$ or
$\left|\lambda\right|\leq 2\sqrt{d-1}$. This bound is optimal for large graphs
by the Alon-Boppana bound ([20]).

######  Lemma 5.4.

Let $X$ be a $d$-regular Ramanujan graph with $n$ vertices and let $S\subset
X$ be a subset.

For $l$ such that $\left|S\right|\left(d-1\right)^{l/2}\leq n$, the number
$M_{l}\left(S,X\right)$ of non-backtracking paths in $X$ that start and end in
$S$ satisfies that
$M_{l}\left(S,X\right)\leq\left|S\right|\left(l+3\right)\left(d-1\right)^{l/2}$.

###### Proof.

We define a length $l$ non-backtracking version of the adjacency operator,
$A_{l}:L^{2}\left(X\right)\to L^{2}\left(X\right)$,

$\left(A_{l}f\right)\left(x\right)=\sum_{\left(e_{1},...,e_{l}\right),t\left(e_{l}\right)=x}f\left(s\left(e_{1}\right)\right),$

where the sum is over the non-backtracking paths in $X$. Notice that it holds
that $M_{l}\left(S,X\right)=\left\langle
A_{l}\mathds{1}_{S},\mathds{1}_{S}\right\rangle$, where $\mathds{1}_{S}$ is
the characteristic function of $S$.

Since the graph is $d$-regular, there is a simple relation between the
$A_{l}$-s, given by

$\displaystyle A$ $\displaystyle=A_{1}$ $\displaystyle A^{2}$
$\displaystyle=dI+A_{2}$ $\displaystyle AA_{l}$
$\displaystyle=\left(d-1\right)A+A_{l+1}\,\,\,\,\,\,\,\,l>1.$

The relations imply that $A_{l}$ is a polynomial in $A$, given explicitly for
$l\geq 2$ by

$A_{l}=\left(d-1\right)^{l/2}\left(\left(1-\left(d-1\right)^{-1}\right)U_{l}\left(\frac{A}{2\sqrt{d-1}}\right)+2\left(d-1\right)^{-1}T_{l}\left(\frac{A}{2\sqrt{d-1}}\right)\right),$

where $T_{l}$ and $U_{l}$ are the Chebyshev polynomials of the first and
second kind, given by
$U_{l}\left(\cos\theta\right)=\frac{\sin\left(\left(n+1\right)\theta\right)}{\sin\theta}$,
$T_{l}\left(\cos\theta\right)=\cos\left(n\theta\right)$. In particular, if
$f\in L^{2}\left(X\right)$ is an eigenvector of $A$, $f$ is also an
eigenvector of $A_{l}$. If the eigenvalue of $A$ is bounded in absolute value
by $2\sqrt{d-1}$, the corresponding eigenvalue of $A_{l}$ is bounded in
absolute value by $\left(l+1\right)\left(d-1\right)^{l/2}$.

Returning to the relation $M_{l}\left(S,X\right)=\left\langle
A_{l}\mathds{1}_{S},\mathds{1}_{S}\right\rangle$, first assume that $X$ is
non-bipartite. We write
$\mathds{1}_{S}=\frac{\left|S\right|}{n}\mathds{1}_{X}+r$, with
$r\perp\mathds{1}_{X}$ and $\left\lVert
r\right\rVert_{2}^{2}\leq\left\lVert\mathds{1}_{S}\right\rVert_{2}^{2}=\left|S\right|$.
Notice that $A_{l}\mathds{1}_{X}=d\left(d-1\right)^{l}\mathds{1}_{X}$. By the
Ramanujan assumption and the fact that $A_{l}$ is self-adjoint,

$\left|\left\langle
A_{l}r,r\right\rangle\right|\leq\left(l+1\right)\left(d-1\right)^{l/2}\left\lVert
r\right\rVert_{2}^{2}.$

Then

$\displaystyle M_{l}\left(S,X\right)$ $\displaystyle=\left\langle
A_{l}\mathds{1}_{S},\mathds{1}_{S}\right\rangle$
$\displaystyle=\frac{\left|S\right|^{2}}{n^{2}}\left\langle
A_{l}\mathds{1}_{X},\mathds{1}_{X}\right\rangle+\left\langle
A_{l}r,r\right\rangle$
$\displaystyle\leq\frac{\left|S\right|^{2}}{n^{2}}nd\left(d-1\right)^{l}+\left(l+1\right)\left(d-1\right)^{l/2}\left\lVert
r\right\rVert_{2}^{2}$
$\displaystyle\leq\left|S\right|\left(\frac{\left|S\right|d\left(d-1\right)^{l-1}}{n}+\left(l+1\right)\left(d-1\right)^{l/2}\right)$
$\displaystyle\leq\left|S\right|\left(\left(\frac{d}{d-1}+l+1\right)\left(d-1\right)^{l/2}\right).$

We conclude by noting that $\frac{d}{d-1}\leq 2$. The case of bipartite graphs
is similar. ∎

We can compare $M_{l}\left(S,X\right)$ with $M_{l}\left(S\right)$, as it
obvious that

$M_{l}\left(S,X\right)\geq M_{l}\left(S\right).$

The case of edge expansion essentially follows directly:

######  Theorem 5.5.

Let $X$ be a $d$-regular Ramanujan graph let $S\subset X$ be a subset with
$\left|S\right|\left(d-1\right)^{l/2}\leq\left|X\right|$. Then the average
degree of the graph $S$ induced from $X$ is bounded by
$\left(1+O\left(\frac{\ln\left(l+2\right)}{l}\right)\right)\sqrt{d-1}+1$.

Moreover, assuming $\left|S\right|=o\left(\left|X\right|\right)$, for
$\delta>0$ small enough, there is $\epsilon>0$, such that if the average
degree of $\left|S\right|$ is larger than $\sqrt{d-1}+1+\epsilon$, then
$\sqrt{d-1}+1$ is an integer and at most $\delta\left|S\right|$ of the
vertices of $\left|S\right|$ have degree different from $\sqrt{d-1}+1$.

###### Proof.

We may assume that the average degree of $S$ is at least $2$. We then may
remove from $S$ vertices of degree $1$ without lowering the average degree,
until all the degrees are at least $2$. Notice that if we remove more than
$o\left(\left|S\right|\right)$ of the vertices then the average degree grows
by a constant.

By Theorem 5.1,

$M_{l}\left(S\right)\geq\left|S\right|\tilde{d}\left(\tilde{d}-1\right)^{l-1}\geq\left|S\right|\left(\tilde{d}-1\right)^{l},$

where $\tilde{d}$ is as in the theorem.

On the one hand, by Lemma 5.4,

$M_{l}\left(S,X\right)\leq\left|S\right|\left(l+3\right)\left(d-1\right)^{l/2}.$

Therefore,

$\tilde{d}-1\leq\left(l+3\right)^{1/l}\left(d-1\right)^{1/2}=\left(1+O\left(\ln\left(l+2\right)/l\right)\right)\left(d-1\right)^{1/2}.$

So by Lemma 5.2,
$\overline{d}\leq\tilde{d}\leq\left(1+O\left(\ln\left(l+2\right)/l\right)\right)\sqrt{d-1}+1$.

The moreover part follows from the moreover part of Lemma 5.2. ∎

The vertex expansion result is similar, but one should be a bit more careful
when handling vertices of degree $1$.

######  Theorem 5.6.

Let $X$ be a $d$-regular Ramanujan graph and let $S\subset X$ be a subset with
$\left|S\right|\left(d-1\right)^{l}\leq\left|X\right|$. Let $N\left(S\right)$
be the neighbors of $\left|S\right|$. Then

$\left|N\left(S\right)\right|\geq\frac{d}{2}\left|S\right|\left(1-O\left(\frac{\ln\left(l+2\right)}{l}\right)\right).$

Moreover, assuming that $\left|S\right|=o\left(\left|X\right|\right)$, for
every $\epsilon>0$ there is $\delta>0$, such that for $\left|X\right|$ large
enough, if
$\left|N\left(S\right)\right|\leq\frac{d}{2}\left|S\right|\left(1+\delta\right)$
then all but at most $\epsilon\left|N\left(S\right)\right|$ of the vertices of
$\left|N\left(S\right)\right|$ are connected to exactly $2$ vertices of $S$.

###### Proof.

We assume that $X$ is bipartite and $S\subset X$ is contained in one of the
sides. See the proof of Theorem 2 in [8] for this simple reduction.

Decompose $N\left(S\right)=M\cup M^{\prime}$, where $M$ are vertices that are
connected to two or more vertices in $S$ and $M^{\prime}$ are vertices that
are connected to exactly one vertex in $S$. We may assume that every vertex in
$S$ is connected to at least $2$ vertices in $M$. Otherwise, assuming the
ratio $\left|N\left(S\right)\right|/\left|S\right|$ is smaller than $d-1$,
when we remove vertices that are connected to one or zero vertices in $M$, we
increase the ratio $\left|N\left(S\right)\right|/\left|S\right|$.

Consider the bipartite graph $Y$ on $\left(S,M\right)$, where $S$ is on the
left side and $M$ is on the right side. Let $m=\left|M\right|$,
$m^{\prime}=\left|M^{\prime}\right|$, $s=\left|S\right|$. Let $e$ be the
number of directed edges from $S$ to $M$ (notice that it is half of the edges
in $Y$, which contain edges from $M$ to $S$ as well).

It holds that

$\displaystyle m^{\prime}$ $\displaystyle=ds-e$
$\displaystyle\left|N\left(S\right)\right|$ $\displaystyle=m+m^{\prime}$
$\displaystyle=m+ds-e.$

The average left degree of $Y$ is $\overline{d}_{L}=\frac{e}{s}$ and the
average right degree is $\overline{d}_{R}=\frac{e}{m}$. Write
$d^{\prime}=\sqrt{\left(\overline{d}_{L}-1\right)\left(\overline{d}_{R}-1\right)}+1$.

By Theorem 5.1 and Lemma 5.2,

$M_{l}\left(S\right)\geq sd^{\prime}\left(d^{\prime}-1\right)^{l-1}.$

However, by Lemma 5.4,

$M_{l}\left(S,X\right)\leq
s\left(\left(l+3\right)\left(d-1\right)^{l/2}\right).$

Denote $\epsilon=\ln\left(l+2\right)/l$. Then we get, as before,

$d^{\prime}-1\leq\sqrt{d-1}\left(1+O\left(\epsilon\right)\right)$

Therefore

$\sqrt{\frac{e}{s}-1}\sqrt{\frac{e}{m}-1}\leq\sqrt{d-1}\left(1+O\left(\epsilon\right)\right)$

Simplifying,

$\displaystyle\frac{e}{m}$ $\displaystyle\leq
1+\frac{\left(1+O\left(\epsilon\right)\right)\left(d-1\right)s}{e-s}=\frac{e+\left(d-2\right)s}{e-s}\left(1+O\left(\epsilon\right)\right)$
$\displaystyle m$
$\displaystyle\geq\frac{e\left(e-s\right)}{e+\left(d-2\right)s}\left(1-O\left(\epsilon\right)\right)$
$\displaystyle m-e$
$\displaystyle\geq-\frac{e\left(d-1\right)s}{e+\left(d-2\right)s}\left(1+O\left(\epsilon\right)\right).$

Since $e\leq ds$, we get

$m-e\geq-\frac{d}{2}s\left(1+O\left(\epsilon\right)\right).$

and since $\left|N\left(S\right)\right|=m-e+ds$, we deduce

$\left|N\left(S\right)\right|\geq\frac{d}{2}s\left(1-O\left(\epsilon\right)\right).$

The proof also says that if $e\leq\alpha ds$ for some $\alpha<1$, then

$N\left(S\right)\geq\beta\frac{d}{2}s\left(1+O\left(\epsilon\right)\right)$

for some $\beta>1$ depending on $\alpha$. Therefore, if we assume that
$\left|S\right|=o\left(\left|N\right|\right)$ and
$\left|N\left(S\right)\right|\leq\frac{d}{2}s\left(1+o\left(1\right)\right)$,
then $e=ds\left(1-o\left(1\right)\right)$. Therefore all but $o\left(s\right)$
of the vertices of $N\left(S\right)$ are connected to at least $2$ vertices of
$S$, and by the bound on the size of $N\left(S\right)$, all but
$o\left(s\right)$ of the vertices of $N\left(S\right)$ are connected to
exactly $2$ vertices of $S$. ∎

######  Remark 5.7.

The proofs of Kahale give slightly better bounds for both edge and vertex
expansions, where $O\left(\ln\left(l+2\right)/l\right)$ is replaced by
$O\left(1/l\right)$.

## References

  * [1] Alon, N., Ganguly, S., and Srivastava, N. High-girth near-ramanujan graphs with localized eigenvectors.  arXiv preprint arXiv:1908.03694 (2019).
  * [2] Alon, N., Hoory, S., and Linial, N. The moore bound for irregular graphs.  Graphs and Combinatorics 18, 1 (2002), 53–57.
  * [3] Brooks, S., and Lindenstrauss, E. Non-localization of eigenfunctions on large regular graphs.  Israel Journal of Mathematics 193, 1 (2013), 1–14.
  * [4] Capalbo, M., Reingold, O., Vadhan, S., and Wigderson, A. Randomness conductors and constant-degree lossless expanders.  In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (2002), pp. 659–668.
  * [5] First, U. A. The Ramanujan property for simplicial complexes.  arXiv preprint arXiv:1605.02664 (2016).
  * [6] Ganguly, S., and Srivastava, N. On non-localization of eigenvectors of high girth graphs.  International Mathematics Research Notices (2018).
  * [7] Hoory, S., Linial, N., and Wigderson, A. Expander graphs and their applications.  Bulletin of the American Mathematical Society 43, 4 (2006), 439–561.
  * [8] Kahale, N. Eigenvalues and expansion of regular graphs.  Journal of the ACM (JACM) 42, 5 (1995), 1091–1106.
  * [9] Kamber, A. ${L}^{p}$-expander complexes.  arXiv preprint arXiv:1701.00154 (2016).
  * [10] Li, W.-C. W. Ramanujan hypergraphs.  Geometric and Functional Analysis 14, 2 (2004), 380–399.
  * [11] Lubotzky, A. Discrete groups, expanding graphs and invariant measures, vol. 125.  Springer Science & Business Media, 1994.
  * [12] Lubotzky, A. Ramanujan complexes and high dimensional expanders.  Japanese Journal of Mathematics 9, 2 (2014), 137–169.
  * [13] Lubotzky, A. High dimensional expanders.  arXiv preprint arXiv:1712.02526 (2017).
  * [14] Lubotzky, A., Phillips, R., and Sarnak, P. Ramanujan graphs.  Combinatorica 8, 3 (1988), 261–277.
  * [15] Lubotzky, A., Samuels, B., and Vishne, U. Ramanujan complexes of type ${A}_{d}$.  Israel Journal of Mathematics 149, 1 (2005), 267–299.
  * [16] Marcus, A., Spielman, D. A., and Srivastava, N. Interlacing families I: bipartite Ramanujan graphs of all degrees.  In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on (2013), IEEE, pp. 529–537.
  * [17] McKenzie, T., and Mohanty, S. High-girth near-ramanujan graphs with lossy vertex expansion.  arXiv preprint arXiv:2007.13630 (2020).
  * [18] Milićević, D. Large values of eigenfunctions on arithmetic hyperbolic 3-manifolds.  Geometric and Functional Analysis 21, 6 (2011), 1375–1418.
  * [19] Morgenstern, M. Existence and explicit constructions of $q+1$ regular ramanujan graphs for every prime power $q$.  Journal of Combinatorial Theory, Series B 62, 1 (1994), 44–62.
  * [20] Nilli, A. On the second eigenvalue of a graph.  Discrete Mathematics 91, 2 (1991), 207–210.
  * [21] Prasad, G. Strong approximation for semi-simple groups over function fields.  Annals of Mathematics 105, 3 (1977), 553–572.
  * [22] Rosen, M. Number theory in function fields, vol. 210.  Springer Science & Business Media, 2013.
  * [23] Rudnick, Z., and Sarnak, P. The behaviour of eigenstates of arithmetic hyperbolic manifolds.  Communications in Mathematical Physics 161, 1 (1994), 195–213.