LPS-Type Ramanujan Graphs from Definite Quaternion Algebras over $\mathbb{Q}$ of Class Number One

Jonah Mendel Department of Mathematics, Brown University [email protected] and Jiahui Yu Department of Mathematics, MIT [email protected]

Abstract.

In this paper we construct explicit LPS-type Ramanujan graphs from each definite quaternion algebra over $\mathbb{Q}$ of class number 1, extending the constructions of [10] and [1], and answering in the affirmative a question raised in [6]. We do this by showing that for each definite quaternion algebra $\mathcal{H}$ over $\mathbb{Q}$ of class number 1 with maximal order $\mathcal{O}$ , if $G=\mathcal{H}^{\times}/Z(\mathcal{H}^{\times})$ and $p$ is prime such that $G(\mathbb{Q}_{p})\cong\operatorname{PGL}_{2}(\mathbb{Q}_{p})$ then there exists a congruence $p$ -arithmetic subgroup of $G$ which acts simply transitively on the Bruhat-Tits tree of $G(\mathbb{Q}_{p})$ .

1. Introduction

A $k$ -regular graph is called a Ramanujan graph if the second largest eigenvalue in absolute value is less than or equal to $2\sqrt{k-1}$ . Ramanujan graphs are optimal expander graphs from a spectral perspective. In their paper [10], Lubotzky, Philips, and Sarnak explicitly construct a family of degree $p+1$ Ramanujan graphs, for each odd prime $p\equiv 1\pmod{4}$ (for the case $p\equiv 3\pmod{4}$ see [2]). The LPS Ramanujan graphs are Cayley graphs of the group $\operatorname{PSL}(\mathbb{F}_{q})$ for primes $q\equiv 1\pmod{4}$ , with respect to a well-chosen generating set coming from the Hamiltonian quaternion algebra over $\mathbb{Q}$ . In [1], Chiu addresses the case when $p=2$ and gives an explicit construction of a family of 3-regular Ramanujan graphs, by using the definite quaternion algebra over $\mathbb{Q}$ with discriminant 13.

In [6], Jo and Yamasaki generalize the construction of LPS and Chiu’s Ramanujan graphs. More precisely, they consider any definite quaternion algebra over $\mathbb{Q}$ of class number one, make use of Ibukiyama’s [5] explicit construction of maximal orders for all definite quaternion algebras, and construct Cayley graphs of $\operatorname{PSL}_{2}(\mathbb{F}_{q})$ with generating sets coming from these quaternion algebras, which they call LPS-type graphs.

The question of whether these LPS-type graphs are indeed Ramanujan was raised in [6], who were able to answer it only in the special case of the definite quaternion algebra over $\mathbb{Q}$ with discriminant 13. In this paper we answer this question affirmatively, showing that for any definite quaternion algebra over $\mathbb{Q}$ of class number one we can construct from it LPS-type Ramanujan graphs.

Theorem 1.1.

For any $P\in\left\{2,3,5,7,13\right\}$ , let $\mathcal{H}$ be a quaternion algebra over $\mathbb{Q}$ with discriminant $P$ and let $\mathcal{O}$ be the maximal order of $\mathcal{H}$ . For almost any prime $p$ , there is a specific subset $S\subseteq\left\{\alpha\in\mathcal{O}:N(\alpha)=p\right\}$ of size $p+1$ , such that the LPS-type graphs of $\operatorname{PSL}_{2}(\mathbb{F}_{q})$ , for infinitely many primes $q$ , with respect to the generating set $S\pmod{q}$ , are Ramanujan graphs.

For the precise construction of these Ramanujan graphs, see Section 5. The key ingredient in proving Theorem 1.1 is to find congruence $p$ -arithmetic subgroups of $G=\mathcal{H}^{\times}/Z(\mathcal{H}^{\times})$ , where $p\nmid\operatorname{disc}(\mathcal{H})$ , which acts simply transitively on the vertices of the Bruhat-Tits tree of $G(\mathbb{Q}_{p})\cong\operatorname{PGL}_{2}(\mathbb{Q}_{p})$ . The fact that it is a congruence subgroup is crucial for the proof that these graphs are Ramanujan, see for example [9, Theorem 7.3.1].

Therefore, our second main result, which might be of independent interest, is the construction of such congruence subgroups which acts simply transitively on Bruhat-Tits trees.

Theorem 1.2.

Let $\mathcal{H}$ be a quaternion algebra over $\mathbb{Q}$ of class number one and let $\mathcal{O}$ be the maximal order of $\mathcal{H}$ . For any commutative ring with unity $A$ , define the group $\mathcal{G}(A)=(A\otimes_{\mathbb{Z}}\mathcal{O})^{\times}/A^{\times}$ . Then there exists $m\in\mathbb{N}$ and $H\leq\mathcal{G}(\mathbb{Z}/m\mathbb{Z})$ such that for any prime $p\nmid m\cdot\operatorname{disc}(\mathcal{H})$ , the congruence subgroup

\Lambda^{p}=\left\{g\in\mathcal{G}(\mathbb{Z}[1/p]):g\pmod{m}\in H\right\}\leq\mathcal{G}(\mathbb{Q}_{p})

acts simply transitively on the vertices of the Bruhat-Tits tree of $\mathcal{G}(\mathbb{Q}_{p})\cong\operatorname{PGL}_{2}(\mathbb{Q}_{p})$ .

Organization of the paper: In section 2, we collect definitions and results on quaternion algebras, their orders and Bruhat-Tits trees. In section 3, we explain the construction of Ramanujan graphs as Cayley graphs of $\operatorname{PSL}_{2}(\mathbb{F}_{q})$ . In section 4, we describe the construction of LPS-type graphs and show how Theorem 1.1 is obtained from Theorem 1.2. In section 5, we prove Theorem 1.2, and show that the definite quaternion algebra over $\mathbb{Q}$ of discriminant 3 does not contain a simply transitively congruence subgroup of level $m$ , for any prime $m$ .

2. Preliminaries

Notation.

Let $p$ be a prime number and $R$ a ring. We will use the following conventions:

•

$\mathbb{F}_{p}$ denotes the field of $p$ elements.
•

$\mathbb{Z}_{p}$ denotes the set of $p$ -adic integers and $\mathbb{Q}_{p}$ the set of $p$ -adic rationals.
•

$R^{\times}$ denotes the multiplicative group of units in $R$ .
•

$\mathcal{M}_{n}(R)$ denotes the ring of $n\times n$ matrices over $R$ .
•

$\operatorname{GL}_{n}(R)=\mathcal{M}_{n}(R)^{\times}$ and $\operatorname{SL}_{n}(R)=\operatorname{Ker}(\det:\operatorname{GL}_{n}(R)\to R^{\times})$ .
•

$\operatorname{PGL}_{2}(R)=\operatorname{GL}_{2}(R)/R^{\times}$ and $\operatorname{PSL}_{2}(R)=\operatorname{SL}_{2}(R)/\left\{\pm 1\right\}$ .
•

$S_{n},A_{n}$ are the symmetric and alternating group on $n$ elements respectively.
•

$C_{n}$ is the cyclic group of $n$ elements.
•

$D_{n}$ is the dihedral group of $2n$ elements.
•

$\left\{1\right\}$ is the trivial group.
•

For a finite group $G$ , $C_{G}$ denotes the conjugacy classes of subgroups of $G$ .
•

Let a group $G$ act on a set $X$ . For $x\in X$ , $\operatorname{Stab}_{G}(x)=\left\{g\in G:gx=x\right\}$ .

2.1. Quaternion Algebras

Let $k$ be a field of characteristic $\neq 2$ and $a,b\in k^{\times}$ . The quaternion algebra $\mathcal{H}_{a,b}(k)$ is an algebra over $k$ generated by the elements $1,i,j,ij$ satisfying

ij+ji=0,\quad i^{2}=a,\quad j^{2}=b.

Let $\alpha=x+yi+zj+wij\in\mathcal{H}_{a,b}(k)$ . We define the conjugate and norm of $\alpha$ to be

\overline{\alpha}=x-yi-zj-wij,\quad\text{and}\quad N(\alpha)=\alpha\overline{\alpha}=x^{2}-ay^{2}-bz^{2}-abw^{2}

respectively. We write $\mathcal{H}_{a,b}$ to denote quaternion algebras over $\mathbb{Q}$ .

We say that a quaternion algebra $\mathcal{H}_{a,b}(k)$ splits if $\mathcal{H}_{a,b}(k)\cong\mathcal{M}_{2}(k)$ . Otherwise we say that $\mathcal{H}_{a,b}(k)$ ramifies. Similarly, we say that a quaternion algebra $\mathcal{H}_{a,b}$ over $\mathbb{Q}$ splits at a prime $p$ if $\mathcal{H}_{a,b}\otimes\mathbb{Q}_{p}\cong\mathcal{M}_{2}(\mathbb{Q}_{p})$ . Otherwise, we say that $\mathcal{H}_{a,b}$ ramifies at $p$ . We say that a quaternion algebra $\mathcal{H}_{a,b}$ is definite if $\mathcal{H}_{a,b}\otimes\mathbb{R}$ is a division algebra. The following lemma gives us helpful facts about splitting.

Proposition 2.1.

[13, Corollary 7.1.2, Theorem 14.1.3]

(1)

A quaternion algebra $\mathcal{H}_{a,b}(k)$ that is not a division ring splits.
(2)

For any finite field $\mathbb{F}_{q}$ , all quaternion algebras over $\mathbb{F}_{q}$ split.
(3)

Two definite quaternion algebras $\mathcal{H}_{a,b}$ and $\mathcal{H}_{a^{\prime},b^{\prime}}$ over $\mathbb{Q}$ are isomorphic if and only if they ramify at exactly the same primes.
(4)

A quaternion algebra $\mathcal{H}$ over $\mathbb{Q}$ ramifies at only finitely many primes.

The product of the finitely many primes at which $\mathcal{H}_{a,b}=\mathcal{H}_{a,b}(\mathbb{Q})$ ramifies at is called the discriminant of $\mathcal{H}_{a,b}$ and is denoted $\operatorname{disc}(\mathcal{H}_{a,b})$ .

2.2. Orders of Quaternion Algebras

An order of a quaternion algebra $\mathcal{H}_{a,b}$ is a rank 4 module over $\mathbb{Z}$ that is also a subring of $\mathcal{H}_{a,b}$ . An order $\mathcal{O}$ is called a maximal order if it is not properly contained in an order of $\mathcal{H}_{a,b}$ . A right ideal of an order $\mathcal{O}$ is a module $M$ satisfying $M\mathcal{O}=M$ . The class number of an order $\mathcal{O}$ is the number of inequivalent right ideals of $\mathcal{O}$ , where two ideals $M,N$ are equivalent if $M=\alpha N$ for some $\alpha\in\mathcal{H}_{a,b}^{\times}$ . It turns out that all maximal orders of a quaternion algebra have the same class number [13, Chapter 17] and we define the class number of the quaternion algebra to be the class number of its maximal orders. The following theorem provides a way to calculate the class number of a quaternion algebra.

Theorem 2.2.

[4, Theorem 6] The class number $h$ of a definite quaternion algebra $\mathcal{H}$ is given by

h=\frac{1}{12}\prod_{p|\operatorname{disc}(\mathcal{H})}(p-1)+\frac{1}{4}\prod_{p|\operatorname{disc}(\mathcal{H})}\left(1-\left(\frac{-4}{p}\right)\right)+\frac{1}{3}\prod_{p|\operatorname{disc}(\mathcal{H})}\left(1-\left(\frac{-3}{p}\right)\right)

where $\left(\frac{n}{p}\right)$ is the Legendre symbol defined as

\left(\frac{a}{p}\right)=\begin{cases}1&\text{if $a$ is a quadratic redsidue modulo $p$}\\ -1&\text{if $a$ is not a quadratic residue modulo $p$}\\ 0&p\mid a.\end{cases}

Corollary 2.3.

The class number $h$ of $\mathcal{H}$ is $1$ if and only if $\operatorname{disc}(\mathcal{H})\in\left\{2,3,5,7,13\right\}$ .

A class number one quaternion algebra over $\mathbb{Q}$ has only one maximal order up to conjugation. When the quaternion algebra is definite and has class number 1, the following theorem gives us a way to count the number of elements whose norm is a prime power, unique up to units, in the maximal ideal.

Proposition 2.4.

[1, Theorem 3.2] Let $\mathcal{H}$ be a definite quaternion algebra of class number 1 over $\mathbb{Q}$ which splits at $p$ . Let $\mathcal{O}$ be a maximal order of $\mathcal{H}$ . Then,

\#\left\{\alpha\in\mathcal{O}:N(\alpha)=p^{k}\right\}/\mathcal{O}^{\times}=1+p+\cdots+p^{k}.

2.3. The Bruhat-Tits Tree

A $\mathbb{Z}_{p}$ lattice in $\mathbb{Q}_{p}\oplus\mathbb{Q}_{p}$ is a rank 2 $\mathbb{Z}_{p}$ -submodule of $\mathbb{Q}_{p}\oplus\mathbb{Q}_{p}$ . Given two $\mathbb{Z}_{p}$ -lattices $L_{1},L_{2}$ in $\mathbb{Q}_{p}\oplus\mathbb{Q}_{p}$ , if $L_{1}=cL_{2}$ for some $c\in\mathbb{Q}_{p}^{\times}$ , then we say that $L_{1}$ and $L_{2}$ are homothetic, and we write $L_{1}\sim L_{2}$ . Let $\widetilde{V}$ be the set of $\mathbb{Z}_{p}$ -lattices in $\mathbb{Q}_{p}\oplus\mathbb{Q}_{p}$ . It is clear that the homoethetic relation $\sim$ defines an equivalence relation on $\widetilde{V}$ . We define the set of homothetic classes of lattices to be $V=\widetilde{V}/\sim$ . Let $\mathcal{T}_{p+1}$ be the graph whose vertices are elements of $V$ . Given two vertices $[L]$ and $[M]$ , there is an edge between $[L]$ and $[M]$ if and only if there exists $L_{1}\in[L]$ and $L_{2}\in[M]$ such that

pL_{2}\subsetneq L_{1}\subsetneq L_{2}.

Theorem 2.5.

[12, Chapter II Theorem 1] The graph $\mathcal{T}_{p+1}$ defined above is a tree of degree $p+1$ .

We call $\mathcal{T}_{p+1}$ the Bruhat-Tits tree of degree $p+1$ . The following proposition relates the Bruhat-Tits tree to the groups $\operatorname{PGL}_{2}(\mathbb{Q}_{p})$ and $\operatorname{PGL}_{2}(\mathbb{Z}_{p})$ .

Proposition 2.6.

[12, Chapter II, Sections 3,4] The group $\operatorname{PGL}_{2}(\mathbb{Q}_{p})$ acts transitively on the Bruhat-Tits tree $\mathcal{T}_{p+1}$ and the stabilizer of the root $[\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}]$ is $\operatorname{PGL}_{2}(\mathbb{Z}_{p})$ .

3. Ramanujan Graphs and Algebraic Groups

3.1. The Algebraic Group $\mathcal{G}$

Fix a prime $p$ . Let $\mathcal{H}=\mathcal{H}_{a,b}(\mathbb{Q})$ be a definite class number 1 quaternion algebra over $\mathbb{Q}$ which splits at $p$ . Let $\mathcal{O}=\mathbb{Z}\oplus\mathbb{Z}\omega_{1}\oplus\mathbb{Z}\omega_{2}\oplus\mathbb{Z}\omega_{3}$ be the unique (up to conjugacy) maximal order of $\mathcal{H}$ . Let $N:\mathcal{H}\to\mathbb{Q}$ be the norm. Note that $N(\mathcal{O})\subseteq\mathbb{Z}$ and

\mathcal{O}^{\times}=\left\{\alpha\in\mathcal{O}:\mathbb{N}(\alpha)=\pm 1\right\}.

For any abelian ring with unity $A$ , define

\mathcal{G}(A)=\mathcal{G}_{\mathcal{O}}(A):=\left(\mathcal{O}\otimes A\right)^{\times}/A^{\times}.

When the context is clear, we drop the subscript $\mathcal{O}$ . Note that $\mathcal{G}(\mathbb{Z})=\mathcal{O}^{\times}/\left\{\pm 1\right\}$ . Furthermore, $\mathbb{Z}[1/p]^{\times}=\left\{p^{k}:k\in\mathbb{Z}\right\}$ . Therefore,

(1)

\mathcal{G}(\mathbb{Z}[1/p])\cong\left\{\gamma\in\mathcal{O}:N(\gamma)=p^{k},\ k\in\mathbb{Z}\right\}/\left\{\pm p^{k}:k\in\mathbb{Z}\right\}

The following proposition relates $\mathcal{G}(\mathbb{Z}[1/p])$ to the Bruhat-Tits tree $\mathcal{T}_{p+1}$ .

Proposition 3.1.

The group $\mathcal{G}(\mathbb{Z}[1/p])$ acts transitively on the vertices of $\mathcal{T}_{p+1}$ and $\mathcal{G}(\mathbb{Z})$ is the stabilizer of $\left[\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}\right]$ .

Proof.

Because $\mathcal{H}$ splits at $p$ , there is an isomorphism $\psi:\mathcal{H}\otimes\mathbb{Q}_{p}\rightarrow\mathcal{M}_{2}(\mathbb{Q}_{p})$ such that $N(\alpha)=\det\psi(\alpha)$ for $\alpha\in\mathcal{H}$ . The map $\psi$ induces an embedding, $\mathcal{G}(\mathbb{Z}[1/p])\hookrightarrow\operatorname{PGL}_{2}(\mathbb{Q}_{p})$ . Matrices of determinant $p$ map any vertex of $\mathcal{T}_{p+1}$ to a neighbor. Thus, elements in $\mathcal{G}(\mathbb{Z}[1/p])$ of norm $p$ map any vertex to a neighbor. By Proposition 2.4, there exist $p+1$ elements in $\mathcal{\mathcal{missing}}G(\mathbb{Z}[1/p])$ that have norm $p$ . They map each vertex of $\mathcal{T}_{p+1}$ to the $p+1$ neighbors of it. Thus, we can reach any vertex of $\mathcal{T}_{p+1}$ by a product of elements of norm $p$ acting on the origin. Therefore, $\mathcal{G}(\mathbb{Z}[1/p])$ acts transitively on $\mathcal{T}_{p+1}$ .

We have that $\mathbb{Z}_{p}^{\times}\cap\{\pm p^{k}:k\in\mathbb{Z}\}=\left\{\pm 1\right\}$ . Elements in $\operatorname{GL}_{2}(\mathbb{Z}_{p})$ have determinants in $\mathbb{Z}_{p}^{\times}$ . Thus, $\mathcal{G}(\mathbb{Z}[1/p])\cap\operatorname{PGL}_{2}(\mathbb{Z}_{p})=\mathcal{G}(\mathbb{Z})$ . Therefore, when $\mathcal{G}(\mathbb{Z}[1/p])$ acts on $\mathcal{T}_{p+1}$ , the stabilizer of the root $\left[\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}\right]$ is $\mathcal{G}(\mathbb{Z})$ . ∎

We want to find a subgroup $\Lambda$ of $\mathcal{G}(\mathbb{Z}[1/p])$ which acts simply transitively on $\mathcal{T}_{p+1}$ . Let $m$ be a positive integer. We define the reduction modulo $m$ map to be

\bar{\varphi}_{m}:\mathcal{O}\to\mathcal{O}\otimes\mathbb{Z}/m\mathbb{Z},\quad w+x\omega_{1}+y\omega_{2}+z\omega_{3}\mapsto\bar{w}+\bar{x}\omega_{1}+\bar{y}\omega_{2}+\bar{z}\omega_{3}

where $\bar{a}$ is the reduction modulo $m$ of the integer $a$ . We know from (1) that elements of $\mathcal{G}(\mathbb{Z}[1/p])$ are represented by elements of $\mathcal{O}$ , so $\bar{\varphi}_{m}$ induces a map,

\varphi_{m}:\mathcal{G}(\mathbb{Z}[1/p])\to\mathcal{G}(\mathbb{Z}/m\mathbb{Z}).

Definition 3.2.

Let $G$ be a group and let $H,K$ be subgroups of $G$ . We call $K$ a right complement of $H$ if

H\cap K=\left\{1\right\},\quad H\cdot K=G.

Definition 3.3.

Let $(m,H)$ be a pair where $m$ is a positive integer and $H$ is a subgroup of $\mathcal{G}(\mathbb{Z}/m\mathbb{Z})$ such that

(1)

$\mathcal{G}(\mathbb{Z})$ embeds into $\mathcal{G}(\mathbb{Z}/m\mathbb{Z})$ via $\varphi_{m}$ ,
(2)

$H$ is a right complement of $\varphi_{m}(\mathcal{G}(\mathbb{Z}))$ in $\mathcal{G}(\mathbb{Z}/m\mathbb{Z})$ .

Then we call $(m,H)$ a congruence pair of $\mathcal{O}$ . If $p\nmid m$ , we define the following congruence subgroup of $\mathcal{G}(\mathbb{Z}[1/p])$ ,

\Lambda^{p}=\Lambda^{p}_{\mathcal{O}}(m,H):=\left\{\gamma\in\mathcal{G}(\mathbb{Z}[1/p]):\varphi_{m}(\gamma)\in H\right\}=\varphi_{m}^{-1}(H)

with a subset

\mathcal{S}^{p}=\mathcal{S}^{p}_{\mathcal{O}}(m,H)=\left\{\alpha\in\Lambda^{p}:N(\alpha)=p\right\}.

When the context is clear, we write $\Lambda^{p}$ and $\mathcal{S}^{p}$ .

Proposition 3.4.

Let $(m,H)$ be a congruence pair of $\mathcal{O}$ . Then $\mathcal{G}(\mathbb{Z})$ and $\Lambda^{p}$ are complementary subgroups of $\mathcal{G}(\mathbb{Z}[1/p])$ ,

Proof.

We have that $\Lambda^{p}=\varphi_{m}^{-1}(H)$ , so $\Lambda^{p}$ is a subgroup of $\mathcal{G}(\mathbb{Z}[1/p])$ . We can deduce that $\varphi_{m}^{-1}(H)\cap\mathcal{G}(\mathbb{Z})=\left\{1\right\}$ from the assumptions $H\cap\mathcal{G}(\mathbb{Z})=\left\{1\right\}$ and $\varphi_{m}|_{\mathcal{G}(\mathbb{Z})}$ is injective. Let $\gamma\in\mathcal{G}(\mathbb{Z}[1/p])$ . We have that $\mathcal{G}(\mathbb{Z})\cdot H=\mathcal{G}(\mathbb{Z}/m\mathbb{Z})$ , so we can choose $\alpha\in\mathcal{G}(\mathbb{Z})\leq\mathcal{G}(\mathbb{Z}[1/p])$ and $\beta\in H$ be such that $\alpha\beta=\varphi_{m}(\gamma)$ . We have that

\varphi_{m}(\alpha^{-1}\gamma)=\varphi_{m}(\alpha^{-1})\varphi_{m}(\gamma)=\alpha^{-1}(\alpha\beta)=\beta\in H.

Therefore, $\alpha^{-1}\gamma\in\Lambda^{p}$ . Thus, $\alpha(\alpha^{-1}\gamma)=\gamma$ , so $\gamma\in\mathcal{G}(\mathbb{Z})\cdot\Lambda^{p}$ . Therefore, $\mathcal{G}(\mathbb{Z})\cdot\Lambda^{p}=\mathcal{G}(\mathbb{Z}[1/p])$ . ∎

Proposition 3.5.

Let $(m,H)$ be a congruence pair of $\mathcal{O}$ . Then the group $\Lambda^{p}$ acts simply transitively on the Bruhat-Tits tree $\mathcal{T}_{p+1}$ .

Proof.

We first show that $\Lambda^{p}$ acts transtively on $\mathcal{T}_{p+1}$ . Let $u,v$ be vertices of $\mathcal{T}_{p+1}$ . Let $L$ be a $\mathbb{Z}_{p}$ -lattice. There exists $\gamma\in\mathcal{G}(\mathbb{Z}[1/p])$ such that $\gamma\cdot[\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}]=[L]$ . By Proposition 3.4, we can write $\gamma=\lambda\alpha$ for $\alpha\in\mathcal{G}(\mathbb{Z})$ and $\lambda\in\Lambda^{p}$ . We have that

[L]=\gamma\cdot[\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}]=(\lambda\alpha)\cdot[\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}]=\lambda\cdot(\alpha\cdot[\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}])=\lambda\cdot[\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}]

because $\mathcal{G}(\mathbb{Z})$ is the stabilizer of $[Z_{p}\oplus\mathbb{Z}_{p}]$ . Therefore, $\Lambda^{p}$ acts transitively on $\mathcal{T}_{p+1}$ . Lastly, $\Lambda^{p}$ acts imply on $\mathcal{T}_{p+1}$ because

\operatorname{Stab}_{\Lambda^{p}}([\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}])=\Lambda^{p}\cap\operatorname{Stab}_{\mathcal{G}(\mathbb{Z}[1/p])}([Z_{p}\oplus\mathbb{Z}_{p}])=\Lambda^{p}\cap\mathcal{G}(\mathbb{Z})=\left\{1\right\}.

∎

Proposition 3.6.

For any congruence pair $(m,H)$ , $\#\mathcal{S}^{p}=p+1$ and $\mathcal{S}^{p}$ generates $\Lambda^{p}$ .

Proof.

The group $\Lambda^{p}$ acts transitively on the vertices of $\mathcal{T}_{p+1}$ . Therefore, there exist at least $p+1$ elements of $\Lambda^{p}$ which take $\left[\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}\right]$ to each of its $p+1$ neighbors respectively. Each of these elements have norm $p$ . Let $\alpha$ and $\beta$ be distinct elements of norm $p$ such that $\alpha\cdot\left[\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}\right]=\beta\cdot\left[\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}\right]$ . Then $\alpha\beta^{-1}$ is a nontrivial element of $\Lambda^{p}$ which acts trivially on $[\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}]$ . This is a contradiction because $\Lambda^{p}$ acts simply on the vertices of $\mathcal{T}_{p+1}$ . Therefore, there are exactly $p+1$ elements in $\Lambda^{p}$ of norm $p$ . We now want to show that $\mathcal{S}^{p}$ generates $\Lambda^{p}$ . Fix a vertex $[L]$ of $\mathcal{T}_{p+1}$ of distance $d$ from $[\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}]$ . For every neighbor $[M]$ of $[L]$ , there exists a unique element of $\mathcal{S}^{p}$ which takes $[L]$ to $[M]$ . Therefore, there exists a unique word of symbols in $\mathcal{S}^{p}$ of length $d$ which takes $[Z_{p}\oplus\mathbb{Z}_{p}]$ . Therefore, there is an isomorphism of graphs $\mathcal{T}_{p+1}\cong\operatorname{Cay}(\Lambda^{p},\mathcal{S}^{p})$ with $[\mathbb{Z}_{p}\oplus\mathbb{Z}_{p}]$ taken as the identity. Because $\mathcal{T}_{p+1}$ is connected, we have that $\mathcal{S}^{p}$ generates $\Lambda^{p}$ . ∎

The following proposition characterizes the structure of $\mathcal{G}(\mathbb{Z}/m\mathbb{Z})$ . This proposition also helps us find congruence pairs $(m,H)$ .

Proposition 3.7.

When $m=p^{k}$ for $k\geq 1$ , then

\mathcal{G}(\mathbb{Z}/m\mathbb{Z})\cong\operatorname{PGL}_{2}(\mathbb{Z}/m\mathbb{Z})

Proof.

$\mathcal{H}$ splits at $p$ . Thus, $\mathcal{O}\otimes\mathbb{Z}_{p}\cong\mathcal{M}_{2}(\mathbb{Z}_{p})$ because $\mathcal{O}$ is a maximal order of $\mathcal{H}$ . Therefore, we have the following isomorphisms of rings,

\mathcal{O}\otimes\mathbb{Z}/m\mathbb{Z}\cong\mathcal{O}/m\mathcal{O}\cong(\mathcal{O}\otimes\mathbb{Z}_{p})/m(\mathcal{O}\otimes\mathbb{Z}_{p})\cong\mathcal{M}_{2}(\mathbb{Z}_{p})/m\mathcal{M}_{2}(\mathbb{Z}_{p})\cong\mathcal{M}_{2}(\mathbb{Z})/mM_{2}(\mathbb{Z})\cong\mathcal{M}_{2}(\mathbb{Z}/m\mathbb{Z}).

We have that $\mathcal{G}(\mathbb{Z}/m\mathbb{Z})\cong(\mathcal{O}\otimes\mathbb{Z}/m\mathbb{Z})^{\times}/(\mathbb{Z}/m\mathbb{Z})^{\times}$ . Therefore, by showing that $\mathcal{O}\otimes\mathbb{Z}/m\mathbb{Z}\cong\mathcal{M}_{2}(\mathbb{Z}/m\mathbb{Z})$ , we have that $\mathcal{G}(\mathbb{Z}/m\mathbb{Z})\cong\operatorname{PGL}_{2}(\mathbb{Z}/m\mathbb{Z})$ . ∎

Proposition 3.8.

Let $q\neq p$ be a prime such that $\mathcal{H}$ splits at $q$ . Let

\Lambda^{p}(q)=\operatorname{Ker}(\varphi_{q})\cap\Lambda^{p},

i.e., the kernel of $\varphi_{q}$ restricted to $\Lambda^{p}$ . Then we have the following isomorphism of groups,

\Lambda^{p}(q)\backslash\Lambda^{p}\cong\begin{cases}\operatorname{PGL}_{2}(\mathbb{Z}/q\mathbb{Z})&\left(\frac{p}{q}\right)=-1\\ \operatorname{PSL}_{2}(\mathbb{Z}/q\mathbb{Z})&\left(\frac{p}{q}\right)=1.\end{cases}

Proof.

By Proposition 3.7, $\varphi_{q}(\Lambda^{p})\leq\operatorname{PGL}_{2}(\mathbb{Z}/q\mathbb{Z})$ . We want to show that $\operatorname{PSL}_{2}(\mathbb{Z}/q\mathbb{Z})\leq\varphi_{q}(\Lambda^{p})$ , for which we use Strong Approximation. By [11, Lemma 1.2], the reduction modulo $q$ map induces a surjection

\left\{\alpha\in\mathcal{G}(\mathbb{Z}[1/p]):N(\alpha)=1\right\}\to\left\{\alpha\in\mathcal{G}(\mathbb{Z}/q\mathbb{Z}):N(\alpha)=1\right\}.

Let $N(\beta)\equiv 1\pmod{q}$ for $\beta\in\mathcal{G}(\mathbb{Z}/q\mathbb{Z})\cong\operatorname{PGL}_{2}(\mathbb{Z}/q\mathbb{Z})$ . By [11, Lemma 1.1], we can find $(a_{0},a_{1},a_{2},a_{3})\in\mathbb{Z}^{4}$ such that $\alpha=a_{0}+a_{1}\omega_{1}+a_{2}\omega_{2}+a_{3}\omega_{3}$ is of norm $p^{k}$ where $p^{k}\equiv 1\pmod{q}$ and $\varphi_{q}(\alpha)=\beta$ . Therefore,

\operatorname{PSL}_{2}(\mathbb{Z}/q\mathbb{Z})\leq\Lambda^{p}(q)\backslash\Lambda^{p}\cong\varphi_{q}(\Lambda^{p}).

Let $\alpha\in\Lambda^{p}$ . Then, $N(\alpha)=p^{k}$ for some $k\in\mathbb{Z}$ . Suppose that $\left(\frac{p}{q}\right)=1$ . Then there exists $x\in\mathbb{Z}$ such that $q\nmid x$ and $p\equiv x^{2}\pmod{q}$ . Let $l\in\mathbb{Z}$ such that $p^{l}x\equiv 1\pmod{q}$ . Note that $\alpha\sim p^{kl}\alpha$ in $\Lambda^{p}$ . Moreover,

N(p^{l}\alpha)=p^{2kl}N(\alpha)=p^{2kl}x^{2k}\equiv 1\pmod{q}.

Therefore, $\varphi_{q}(\alpha)\in\operatorname{PSL}_{2}(\mathbb{Z}/q\mathbb{Z})$ . Now suppose that $\left(\frac{p}{q}\right)=-1$ . Suppose that $N(\alpha)=p$ and $\varphi_{q}(\alpha)\in\operatorname{PSL}_{2}(\mathbb{Z}/q\mathbb{Z})$ . Then there exists $y\in\mathbb{Z}$ , $q\nmid y$ , such that $N(y\alpha)=y^{2}p=1$ but this implies $p$ is a square modulo $q$ , which is a contradiction. Therefore, $\varphi_{q}(\alpha)\not\in\operatorname{PSL}_{2}(\mathbb{Z}/q\mathbb{Z})$ and $\varphi_{q}(\Lambda^{p})\supsetneq\operatorname{PSL}_{2}(\mathbb{Z}/q\mathbb{Z})$ . But $\operatorname{PSL}_{2}(\mathbb{Z}/q\mathbb{Z})$ is an index 2 subgroup of $\operatorname{PGL}_{2}(\mathbb{Z}/q\mathbb{Z})$ , so $\Lambda^{p}(q)\backslash\Lambda^{p}\cong\operatorname{PGL}_{2}(\mathbb{Z}/q\mathbb{Z})$ . ∎

Let $q$ be an odd prime such that $\left(\frac{p}{q}\right)=1$ . Let $\mathcal{S}^{p,q}=\varphi_{q}(\mathcal{S}^{p})$ . Note that when $\varphi_{q}$ is not injective on $\mathcal{S}^{p}$ , we consider $\mathcal{S}^{p,q}$ to be a multi-set where each element has multiplicity of the size of its pre-image in $\mathcal{S}^{p}$ . As shown above, we can consider this set to be a generating set of $\operatorname{PSL}_{2}(\mathbb{F}_{q})$ . Therefore, we have the Cayley graph

\mathcal{X}^{p,q}=\mathcal{X}^{p,q}_{\mathcal{O}}(m,H)=\operatorname{Cay}(\operatorname{PSL}_{2}(\mathbb{F}_{q}),\mathcal{S}^{p,q}).

Proposition 3.9.

When $q$ is an odd prime such that $\left(\frac{p}{q}\right)=1$ , we have an isometry of graphs

\mathcal{X}^{p,q}\cong\Lambda^{p}(q)\backslash\mathcal{T}_{p+1}.

Proof.

As a subgroup of $\Lambda^{p}$ , the group $\Lambda^{p}(q)$ acts simply on $\mathcal{T}_{p+1}$ . By Proposition 3.8, the orbits of the action are in 1-1 correspondence with $\operatorname{PSL}_{2}(\mathbb{F}_{q})$ . We can thus view the vertices of the quotient graph as elements of $\operatorname{PSL}_{2}(\mathbb{F}_{q})$ . We see this in the sequence of bijections of sets,

\operatorname{PSL}_{2}(\mathbb{F}_{q})\cong\Lambda^{p}(q)\backslash\Lambda^{p}\cong\Lambda^{p}(q)\backslash\operatorname{PGL}_{2}(\mathbb{Q}_{p})/\operatorname{PGL}_{2}(\mathbb{Z}_{p})\cong\Lambda^{p}(q)\backslash V(\mathcal{T}_{p+1})

where $V(\mathcal{T}_{p+1})$ are the vertices of $\mathcal{T}_{p+1}$ . By Proposition 3.6, $\mathcal{S}^{p}$ generates $\Lambda^{p}$ so $\mathcal{S}^{p,q}$ generates the quotient graph. ∎

Theorem 3.10.

[9, Theorem 7.3.1] Let $\mathcal{O}$ be a maximal order of class number 1 which splits at a prime $p$ . Let $q\neq p$ be a prime such that $\left(\frac{p}{q}\right)=1$ . Let $(m,H)$ be a congruence pair of $\mathcal{O}$ . Then the Cayley graph $\mathcal{X}^{p,q}_{\mathcal{\mathcal{O}}}(m,H)$ is a Ramanujan graph.

Note that $\#\operatorname{PSL}_{2}(\mathbb{F}_{q})=q(q-1)(q+1)/2$ so the graph $\mathcal{X}^{p,q}_{\mathcal{O}}$ has $q(q-1)(q+1)/2$ vertices.

4. Construction of Explicit Maximal Orders and LPS-Type Ramanujan Graphs

In this section, we explain Jo and Yamasaki’s construction of LPS-type graphs as in [6]. In the construction, we need a quaternion algebra of class number 1 and a maximal order. In [5], Ibukiyama explicitly constructs a maximal order for any definite quaternion algebra over $\mathbb{Q}$ . We discuss a special case for when the quaternion algebra only ramifies at one prime.

Proposition 4.1 ([5]).

Let $P$ be a prime number. Take a prime $Q$ such that

(2)

Q\equiv 3\mod 8,\quad\left(\frac{-Q}{P}\right)=-1\text{ unless }P=2.

Let $T$ be an integer such that $T^{2}\equiv-P\mod Q$ . Then, $\mathcal{H}_{-P,-Q}$ (i.e. $i^{2}=-P$ , $j^{2}=-Q$ , $ij=-ji=k$ ) is a definite quaternion algebra which only ramifies at $P$ and the quaternion algebra $\mathcal{H}_{-P,-Q}$ has a maximal order $\mathcal{O}_{-P,-Q}=\mathbb{Z}\oplus\mathbb{Z}\omega_{1}\oplus\mathbb{Z}\omega_{2}\oplus\mathbb{Z}\omega_{3}$ where

\omega_{1}=\frac{1+j}{2},\quad\omega_{2}=\frac{i+ij}{2},\quad\omega_{3}=\frac{Tj+k}{Q}.

Definition 4.2.

Let $(P,Q)$ be a pair of positive integers such that $P$ is prime and $Q$ satisfies (2). We call $(P,Q)$ an Ibukiyama Pair.

Note that by quadratic reciprocity, we can find an appropriate integer $T$ that satisfies the required conditions. By Corollary 2.3, the class number of $\mathcal{H}_{-P,-Q}$ is 1 if and only if $P\in\{2,3,5,7,13\}$ . Also, if $\alpha=x+y\omega_{1}+z\omega_{2}+w\omega_{3}\in\mathcal{O}_{-P,-Q}$ then

(3)

N(\alpha)=x^{2}+\frac{Q+1}{4}y^{2}+\frac{P(Q+1)}{4}z^{2}+\frac{T^{2}+P}{Q}w^{2}+xy+Tyw+Pzw.

Note that our choice of $Q$ and $T$ is irrelevant. We now make the following adjustments to our notation:

\mathcal{G}_{-P,-Q}(A)=\mathcal{G}_{\mathcal{O}_{-P,-Q}}(A),\qquad\Lambda^{p}_{-P,-Q}(A)=\Lambda^{p}_{\mathcal{O}_{-P,-Q}}(A)

Proposition 4.3.

[6, Remark V.2] Let $q$ be a prime, $q\neq 2$ , $\left(\frac{-P}{q}\right)=\left(\frac{Q}{q}\right)=1$ and $\left(\frac{p}{q}\right)=1$ . The map $\beta_{q}:\mathcal{O}_{-P,-Q}\rightarrow\mathcal{M}_{2}(\mathbb{F}_{q})$ induced by the reduction modulo $q$ map on $\mathcal{O}_{-P,-Q}$ is defined by

x+y\omega_{1}+z\omega_{2}+w\omega_{3}\mapsto\frac{1}{2Q}\begin{pmatrix}A_{11}&A_{12}\\ A_{21}&A_{22}\end{pmatrix}

where

	$\displaystyle A_{11}$	$\displaystyle=(2Qx+Qy)+Qz\sqrt{-P}$
	$\displaystyle A_{12}$	$\displaystyle=\sqrt{Q}(Qy+2Tw+(Qz+2w)\sqrt{-P})$
	$\displaystyle A_{21}$	$\displaystyle=-\sqrt{Q}(Qy+2Tw-(Qz+2w)\sqrt{-P})$
	$\displaystyle A_{22}$	$\displaystyle=(2Qx+Qy)-Qz\sqrt{-P}$

gives an isomorphism satisfying $\det(\beta_{q}(\alpha))=N(\alpha)$ .

Lemma 4.4.

Let $(P,Q)$ be an Ibukiyama pair. Then

\mathcal{G}_{-P,-Q}(\mathbb{Z}/P\mathbb{Z})\cong N\rtimes H

where

N=\left\{1+xi+yij:x,y\in\mathbb{Z}/P\mathbb{Z}\right\},\quad H=\left\{x+yj:x,y\in\mathbb{Z}/P\mathbb{Z},\ (x,y)\neq(0,0)\right\}/(\mathbb{Z}/P\mathbb{Z})^{\times}.

Proof.

Using (3), we see that the number of elements $\alpha=a_{0}+a_{1}\omega_{1}+a_{2}\omega_{2}+a_{3}\omega_{3}$ with $0\leq a_{i}<P$ and $N(\alpha)\not\equiv 0\pmod{P}$ is $P^{2}(P^{2}-1)$ . Therefore, $\#\mathcal{G}(\mathbb{Z}/P\mathbb{Z})=P^{2}(P^{2}-1)/(P-1)=P^{2}(P+1)$ .

Because $P\neq 2,Q$ , we can break up the $\omega_{i}$ to put the elements of $\mathcal{G}_{-P,-Q}(\mathbb{Z}/m\mathbb{Z})$ in terms of $i,j,ij$ . It is clear that the elements of $N$ and $H$ have nonzero norm. Furthermore, $N$ and $H$ are both closed under multiplication. Thus, $N$ and $H$ can be identified as subgroups of $\mathcal{G}(\mathbb{Z}/P\mathbb{Z})$ . Observe that $N\cap H=\left\{1\right\}$ , $\#N=P^{2}$ , $\#H=(P^{2}-1)/(P-1)=P+1$ . We have computed that $\#\mathcal{G}(\mathbb{Z}/P\mathbb{Z})=P^{2}(P+1)$ , which shows that $\mathcal{G}(\mathbb{Z}/P\mathbb{Z})=N\cdot H$ . Lastly, $N$ is normal in $\mathcal{G}(\mathbb{Z}/P\mathbb{Z})$ because for $n\in N$ and $h\in H$ , we have that $h^{-1}=z-yj$ and

hnh^{-1}=(x+yj)(1+Xi+Yij)(x-yj)\\ =(x+(xX-yY)i+(xY-yX)ij+yj)(x-yj)=A+Bi+Cij\in N.

Therefore, $\mathcal{G}(\mathbb{Z}/P\mathbb{Z})\cong N\rtimes H$ . ∎

Definition 4.5.

An LPS-type graph is any graph constructed in the following way:

(1)

Fix a prime $p$ .
(2)

Let $(P,Q)$ be an Ibukiyama pair such that $P\in\left\{2,3,5,7,13\right\}$ , $P\neq p$ . We have a definite class number 1 rational maximal order $\mathcal{O}_{-P,-Q}$ which splits at $p$ .
(3)

Find all elements in $\mathcal{O}^{\times}_{-P,-Q}$ by solving the norm equation $N(\alpha)=1$ .
(4)

Find $p+1$ elements of $\mathcal{O}_{-P,-Q}$ of norm $p$ , unique up to units, which form a set $\mathcal{S}^{p}$ .
(5)

Take a prime $q$ satisfying

(4) $q\neq p,\quad\left(\frac{-P}{q}\right)=\left(\frac{Q}{q}\right)=1,\quad\left(\frac{p}{q}\right)=1.$
(6)

Via the reduction map $\varphi_{q}$ then the isomorphism $\varphi_{q}$ in Proposition 4.3, realize $\mathcal{S}^{p}$ as a multi-set of elements of $\operatorname{PSL}_{2}(\mathbb{F}_{q})$ and write it as $\mathcal{S}^{p,q}$ . Note that each element of $\mathcal{S}^{p,q}$ has multiplicity of the size of its pre-image in $\mathcal{S}^{p}$ .

(7)

Construct the Cayley graph

\mathcal{X}^{p,q}=\mathcal{X}_{-P,-Q}^{p,q}\left(\mathcal{S}^{p,q}\right)=\operatorname{PSL}_{2}\left(\mathbb{F}_{q},\mathcal{S}^{p,q}\right).

The graph $\mathcal{X}^{p,q}$ is a LPS-type graph.

Theorem 4.6.

Let $(P,Q)$ be an Ibukiyama pair. Let $\mathcal{S}^{p}$ be $p+1$ elements of norm $p$ in $\mathcal{O}_{-P,-Q}$ . Let $q\neq p$ be a prime such that $q$ satisifies $(\ddagger)$ . Let $\mathcal{X}^{p,q}_{-P,-Q}\left(\mathcal{S}^{p,q}\right)$ be the corresponding LPS-type graph. If we can find a congruence pair $(m,H)$ of $\mathcal{O}_{-P,-Q}$ such that $\mathcal{S}^{p}\subseteq\Lambda^{p}_{-P,-Q}(m,H)$ , then $\mathcal{X}^{p,q}_{-P,-Q}$ is Ramanujan.

Proof.

We have that $\mathcal{O}_{-P,-Q}$ is a rational maximal class number one maximal order which splits at $p$ . Because $\mathcal{S}^{p}\subseteq\Lambda^{p}_{-P,-Q}(m,H)$ for some congruence pair $(m,H)$ , we have that $\mathcal{X}_{-P,-Q}^{p,q}\left(\mathcal{S}^{p,q}_{-P,-Q}\right)\cong\mathcal{X}_{\mathcal{O}_{-P,-Q}}^{p,q}(m,H)$ . Theorem 3.10 implies that $\mathcal{X}_{-P,-Q}^{p,q}(m,H)$ is Ramanujan. ∎

Corollary 4.7.

Theorem 1.2 implies Theorem 1.1.

5. The Ramanujan Property for Certain LPS-Type Graphs

Our goal is to show that we can construct Ramanujan LPS-type graphs from definite class number 1 rational quaternion algebras. That is, we want to prove Theorem 1.2, which we restate more explicitly below in terms of congruence pairs. Note that by Proposition 3.5, we have that Theorem 5.1 is equivalent to Theorem 1.2.

Theorem 5.1.

Let $\mathcal{H}$ be a definite class number 1 quaternion algebra over $\mathbb{Q}$ . Let $\mathcal{O}$ be the unique maximal order of $\mathcal{H}$ . There exists a positive integer $m$ and a subgroup $H$ of $\mathcal{G}_{\mathcal{O}}(\mathbb{Z}/m\mathbb{Z})$ such that $(m,H)$ is a congruence pair.

To prove Theorem 5.1, we need the following calculation.

Proposition 5.2.

The unit groups of $\mathcal{O}_{-P,-Q}$ for $P\in\left\{2,3,4,7,13\right\}$ are

\mathcal{G}_{-P,-Q}(\mathbb{Z})=\begin{cases}A_{4}&P=2,\\ S_{3}&P=3,\\ A_{3}&P=5,\\ S_{2}&P=7,\\ A_{2}&P=13.\end{cases}

Proof.

For $P=2$ , see Lemma 5.3. For $P=3$ , see Lemma 5.5. For $P=5$ , see Lemma 5.7. For $P=7$ , see Lemma 5.10. The case $P=13$ is proven in [1, Section 4]. Note that $A_{2}$ is the trivial group. ∎

Proof of Theorem 5.1.

For $P=2$ , see Proposition 5.4. For $P=3$ , see Proposition 5.6. For $P=5$ , see Proposition 5.9. For $P=7$ , see Proposition 5.11. For $P=13$ , $A_{2}$ is the trivial group so $\mathcal{G}_{-P,-Q}(\mathbb{Z}[1/p])$ acts trivially on $\mathcal{T}_{p+1}$ . ∎

Note that $\mathcal{O}_{-P,-Q}$ is completely determined by the ramified primes, so the choice of $Q$ does not matter.

5.1. The Quaternion Algebra Ramifies at 2

Set $P=2$ and $Q=11$ . Observe that $Q\equiv 3\mod{8}$ (we don’t need the reciprocity condition because $P=2$ ). Set $T=3$ . Observe that $T^{2}\equiv-2\mod{11}$ . $\mathcal{H}_{-2,-11}$ is a quaternion algebra over $\mathbb{Q}$ which is of class number 1 and ramifies only at 2. By Theorem 4.1, $\mathcal{H}_{-2,-11}$ has a maximal order $\mathcal{O}_{-2,-11}=\mathbb{Z}+\mathbb{Z}\omega_{1}+\mathbb{Z}\omega_{2}+\mathbb{Z}\omega_{3}$ , where

\omega_{1}=\frac{1+j}{2},\quad\omega_{2}=\frac{i+ij}{2},\quad\omega_{3}=\frac{3j+ij}{11}.

Lemma 5.3.

$\mathcal{G}_{-2,-11}(\mathbb{Z})\cong A_{4}$

Proof.

For $\alpha=x+y\omega_{1}+z\omega_{2}+w\omega_{3}\in\mathcal{O}_{-2,-11}$ , it follows from (3) that

N(\alpha)=x^{2}+3y^{2}+6z^{2}+w^{2}+xy+3yw+2zw.

Solving $N(\alpha)=1$ , we get $24$ solutions in $\mathbb{Z}^{4}$ , which form a group under multiplication. When we quotient by $\left\{\pm 1\right\}$ , we get a group which is isomorphic to $A_{4}$ . Representations of the elements of $\mathcal{G}_{-2,-11}(\mathbb{Z})$ are enumerated in Figure 1. ∎

1	$\omega_{1}$	$\omega_{2}$	$\omega_{3}$	1	$i$	$j$	$ij$
1	0	0	1	0	0	3/11	1/11
0	1	0	-2	1/2	0	-1/22	-2/11
0	1	0	-1	1/2	0	5/22	-1/11
1	-3	-1	5	-1/2	-1/2	-3/22	-1/22
1	-3	-1	6	-1/2	-1/2	3/22	1/22
1	-2	-1	4	0	-1/2	1/11	-3/22
1	-1	0	1	1/2	0	-5/22	1/11
1	-1	0	2	1/2	0	1/22	2/11
1	0	0	0	1	0	0	0
2	-4	-1	7	0	-1/2	-1/22	3/22
2	-3	-1	5	1/2	-1/2	-3/22	-1/22
2	-3	-1	6	1/2	-1/2	3/22	1/22

Figure 1. The elements of

\mathcal{G}_{-2,-11}(\mathbb{Z})

. Each row is a distinct element with a representation in terms of

\omega_{i}

and in terms of

i

and

j

Proposition 5.4.

There exists a subgroup $H\leq\mathcal{G}_{-2,-11}(\mathbb{Z}/3\mathbb{Z})$ such that $H\cong C_{2}$ and $(3,H)$ is a congruence pair of $\mathcal{O}_{-2,-11}$ .

Proof.

We see from Figure 1 that $\mathcal{G}_{-2,-11}(\mathbb{Z})$ embeds in $\mathcal{G}_{-2,-11}(\mathbb{Z}/3\mathbb{Z})$ . We identify $\mathcal{G}_{-2,-11}(\mathbb{Z})$ as a subgroup of $\mathcal{G}_{-2,-11}(\mathbb{Z}/3\mathbb{Z})$ . Lemma 5.3 tells us that $\mathcal{G}_{-3,-19}(\mathbb{Z})\cong A_{4}$ . Proposition 3.7 implies that $\mathcal{G}_{-2,-11}(\mathbb{Z}/3\mathbb{Z})\cong\operatorname{PGL}_{2}(\mathbb{Z}/3\mathbb{Z})\cong S_{4}$ . There is only one copy of $A_{4}$ in $S_{4}$ and

S_{4}=A_{4}\rtimes H

for $H\cong C_{2}$ . Therefore, $(3,H)$ is a congruence pair of $\mathcal{O}_{-2,-11}$ . ∎

5.2. The Quaternion Algebra Ramifies at 3

Set $P=3$ and $Q=19$ . Observe that $Q\equiv 3\mod{8}$ and $\left(\frac{-Q}{3}\right)=-1$ . Set $T=4$ . Observe that $T^{2}\equiv-3\mod{19}$ . Thus, $\mathcal{H}_{-3,-19}$ is a quaternion algebra over $\mathbb{Q}$ which is of class number 1 and ramifies only at 3. By Theorem 4.1, $\mathcal{H}_{-3,-19}$ has a maximal order $\mathcal{O}_{-3,-19}=\mathbb{Z}+\mathbb{Z}\omega_{1}+\mathbb{Z}\omega_{2}+\mathbb{Z}\omega_{3}$ , where

\omega_{1}=\frac{1+j}{2},\quad\omega_{2}=\frac{i+ij}{2},\quad\omega_{3}=\frac{4j+ij}{19}.

Lemma 5.5.

$\mathcal{G}_{-3,-19}(\mathbb{Z})\cong S_{3}$

Proof.

For $\alpha=x+y\omega_{1}+z\omega_{2}+w\omega_{3}\in\mathcal{O}_{-3,-19}$ , it follows from (3) that

N(\alpha)=x^{2}+5y^{2}+15z^{2}+w^{2}+xy+4yw+3zw.

Solving $N(\alpha)=1$ , we get 12 solutions in $\mathbb{Z}^{4}$ , which form a group under multiplication. When we quotient by $\left\{\pm 1\right\}$ , we get a noncommutative group with six elements. There is only one noncommutative group of order 6, $S_{3}$ , so $\mathcal{G}_{-3,-19}(\mathbb{Z})\cong S_{3}$ . Representations of the elements of $\mathcal{G}_{-3,-19}(\mathbb{Z})$ are enumerated in Figure 2. ∎

1	$\omega_{1}$	$\omega_{2}$	$\omega_{3}$	1	$i$	$j$	$ij$
1	0	0	0	1	0	0	0
2	-4	-1	10	0	-1/2	2/19	1/38
2	-4	-1	9	0	-1/2	-2/19	-1/38
1	-1	0	2	1/2	0	-3/38	2/19
0	1	0	-2	1/2	0	3/38	-2/19
0	0	0	1	0	0	4/19	1/19

Figure 2. Elements of

\mathcal{G}_{-3,-19}(\mathbb{Z})

Proposition 5.6.

There exist subgroups $H,H^{\prime},H^{\prime\prime}\leq\mathcal{G}_{-3,-19}(\mathbb{Z}/4\mathbb{Z})$ such that

H\cong C_{2}^{3},\quad H^{\prime}\cong C_{4}\times C_{2}^{2},\quad H^{\prime\prime}\cong D_{4}

and $(4,H)$ , $(4,H^{\prime})$ , and $(4,H^{\prime\prime})$ are congruence pairs of $\mathcal{O}_{-3,-19}$ .

Proof.

We see from Figure 2 that $\mathcal{G}_{-3,-19}(\mathbb{Z})$ embeds in $\mathcal{G}_{-3,-19}(\mathbb{Z}/4\mathbb{Z})$ . We identify $\mathcal{G}_{-3,-19}(\mathbb{Z})$ as a subgroup of $\mathcal{G}_{-3,-19}(\mathbb{Z}/4\mathbb{Z})$ . Proposition 3.7 implies that $\mathcal{G}_{-3,-19}(\mathbb{Z}/4\mathbb{Z})\cong\operatorname{PGL}_{2}(\mathbb{Z}/4\mathbb{Z})$ . Lemma 5.5 tells us that $\mathcal{G}_{-3,-19}(\mathbb{Z})\cong S_{3}$ . Calculation shows that there are two classes $[K],[K^{\prime}]\in C_{\operatorname{PGL}_{2}(\mathbb{Z}/4\mathbb{Z})}$ such that $K,K^{\prime}\cong S_{3}$ . Both $K$ and $K^{\prime}$ have complementary subgroups isomorphic to $C_{8}$ , $C_{4}\times C_{2}^{2}$ , and $D_{4}$ . ∎

5.3. The Quaternion Algebra Ramifies at 5

Set $P=5$ and $Q=3$ . Observe that $Q\equiv 3\mod{8}$ and $\left(\frac{-Q}{5}\right)=-1$ . Set $T=1$ . Observe that $T^{2}\equiv-5\mod{3}$ . $\mathcal{H}_{-5,-3}$ is a quaternion algebra over $\mathbb{Q}$ which is of class number 1 and ramifies only at 5. By Theorem 4.1, $\mathcal{H}_{-5,-3}$ has a maximal order $\mathcal{O}_{-2,-11}=\mathbb{Z}+\mathbb{Z}\omega_{1}+\mathbb{Z}\omega_{2}+\mathbb{Z}\omega_{3}$ , where

\omega_{1}=\frac{1+j}{2},\quad\omega_{2}=\frac{i+ij}{2},\quad\omega_{3}=\frac{j+ij}{3}.

Lemma 5.7.

$\mathcal{G}_{-3,-19}(\mathbb{Z})\cong\langle 1,\omega_{1},1-\omega_{1}\rangle\cong A_{3}$

Proof.

For $\alpha=x+y\omega_{1}+z\omega_{2}+w\omega_{3}\in\mathcal{O}_{-5,-3}$ , it follows from (3) that

N(\alpha)=x^{2}+y^{2}+5z^{2}+2w^{2}+xy+yw+5zw.

Solving $N(\alpha)=1$ , we get $6$ solutions in $\mathbb{Z}^{4}$ , which form a group under multiplication. When we quotient by $\left\{\pm 1\right\}$ , we get a group which is isomorphic to $A_{3}$ . ∎

Lemma 5.8.

Let

	$\displaystyle A=\left\{1+xi+yij:x,y\in\mathbb{Z}/5\mathbb{Z}\right\},\quad B=\left\{j+xi+yij:x,y\in\mathbb{Z}/5\mathbb{Z}\right\},$
	$\displaystyle H=A\cup B.$

The set $H$ is a group isomorphic with $C_{5}\rtimes D_{5}$ .

Proof.

We first check that $H$ contains inverses. Suppose that $\alpha=1+xi+yij\in A$ . Then

\alpha(1-xi-yij)=1+x^{2}i^{2}+y^{2}ijij=1.

Therefore, $\alpha^{-1}\in A$ . Next suppose that $\alpha=j+xi+yij\in B$ , then

	$\displaystyle\alpha^{2}$	$\displaystyle=j^{2}+xji+yjij+xij+x^{2}i^{2}+xyi^{2}j+yij^{2}+xyiji+y^{2}ijij$
		$\displaystyle=-3-xij+3yi+xij-3yi$
		$\displaystyle=-3.$

In particular, every element of $B$ has order 2. Therefore, $\alpha^{-1}=\alpha$ for $\alpha\in B$ . We now show that $H$ is a group. We check the following cases.

(1)

Let $\alpha,\beta\in A$ . Let $\alpha=1+xi+yij$ and $\beta=1+x^{\prime}i+y^{\prime}ij$ . Then

	$\displaystyle\alpha\beta$	$\displaystyle=(1+xi_{y}ij)(1+x^{\prime}i+y^{\prime}ij)$
		$\displaystyle=1+x^{\prime}i+y^{\prime}ij+xi+xx^{\prime}i^{2}+xy^{\prime}i^{2}j+yij+yx^{\prime}iji+yy^{\prime}ijij$
		$\displaystyle=1+x^{\prime}i+y^{\prime}ij+xi-5xx^{\prime}-5xy^{\prime}j+yij+5yx^{\prime}j-15yy^{\prime}$
		$\displaystyle=1+(x+x^{\prime})i+(y+y^{\prime})ij.$

Therefore, $\alpha\beta\in A$ .

(2)

Let $\alpha,\beta\in B$ . Let $\alpha=j+xi+yij$ and $\beta=j+x^{\prime}k+y^{\prime}ij$ . Then

	$\displaystyle\alpha\beta$	$\displaystyle=(j+xi+yij)(j+x^{\prime}i+y^{\prime}ij)$
		$\displaystyle=j^{2}+x^{\prime}ji+y^{\prime}jij+xij+xx^{\prime}i^{2}+xy^{\prime}i^{2}j+yx^{\prime}iji+yy^{\prime}iji$
		$\displaystyle=-3+x^{\prime}ji+y^{\prime}3i+xij-3yi$
		$\displaystyle=-3+3(y^{\prime}-y)i+(x-x^{\prime})ij.$

Therefore, $\alpha\beta\in A$ .

(3)

Let $\alpha\in A$ and $\beta\in B$ . Let $\alpha=1+xi+yij$ and $\beta=j+x^{\prime}i+y^{\prime}ij$ . Then

	$\displaystyle\alpha\beta$	$\displaystyle=(1+xi+yij)(j+x^{\prime}i+y^{\prime}ij)$
		$\displaystyle=j+x^{\prime}i+y^{\prime}ij+xij+xx^{\prime}i^{2}+xy^{\prime}i^{2}j+yij^{2}+yx^{\prime}iji+yy^{\prime}ijij$
		$\displaystyle=j+x^{\prime}i+y^{\prime}ij+xij-3yi$
		$\displaystyle=j+(x^{\prime}-3y)i+(x+y^{\prime})ij.$

Therefore, $\alpha\beta\in B$ .

(4)

Let $\alpha\in B$ and $\beta\in A$ . Let $\alpha=j+xi+yij$ and $\beta=1+x^{\prime}i+y^{\prime}ij$ . Then

	$\displaystyle\alpha\beta$	$\displaystyle=(j+xi+yij)(1+x^{\prime}i+y^{\prime}ij)$
		$\displaystyle=j+x^{\prime}ji+y^{\prime}jij+xi+xx^{\prime}i^{2}+xy^{\prime}i^{2}j+yij+yx^{\prime}iji+yy^{\prime}ijij$
		$\displaystyle=j-x^{\prime}ij+3y^{\prime}i+xi+yij$
		$\displaystyle=j+(3y^{\prime}+x)+(y-x^{\prime})ij.$

Therefore, $\alpha\beta\in B$ .

Therefore, $H$ is in fact a group. $H$ is noncommutative of order 50, and $H$ contains $25$ elements of order 2. Therefore, $H\cong C_{5}\rtimes D_{5}$ . ∎

Proposition 5.9.

There exists a subgroup $H\leq\mathcal{G}_{-5,-3}(\mathbb{Z})$ such that

H\cong C_{5}\rtimes D_{5}.

and $(5,H)$ is a congruence pair of $\mathcal{O}_{-5,-3}$ .

Proof.

We see from Lemma 5.9 that $\mathcal{G}_{-5,-3}(\mathbb{Z})\cong A_{3}$ embeds in $\mathcal{G}_{-5,-3}(\mathbb{Z}/5\mathbb{Z})$ . We have that

\varphi_{5}(\mathcal{G}_{-5,-3}(\mathbb{Z}))\cong\langle 1,1+j,1-j\rangle.

By Lemma 4.4, $\#\mathcal{G}_{-5,-3}(\mathbb{Z}/5\mathbb{Z})=150$ . Let $H\subseteq\mathcal{G}_{-5,-3}(\mathbb{Z}/5\mathbb{Z})$ be as in Lemma 5.8, so $H$ is a subgroup of $\mathcal{G}_{-5,-3}(\mathbb{Z}/5\mathbb{Z})$ isomorphic to $C_{5}\rtimes D_{5}$ . By construction, $H\cap\mathcal{G}_{-5,-3}(\mathbb{Z})=\left\{1\right\}$ and

\#\left(\mathcal{G}_{-5,-3}(\mathbb{Z})\cdot H\right)=3\cdot 50=150=\#\mathcal{G}_{-5,-3}(\mathbb{Z}/5\mathbb{Z})

so $\mathcal{G}_{-5,-3}(\mathbb{Z}/5\mathbb{Z})=\mathcal{G}_{-5,-3}(\mathbb{Z})\cdot H$ . Therefore, $(5,H)$ is a congruence pair of $\mathcal{O}_{-5,-3}$ . ∎

5.4. The Quaternion Algebra Ramifies at 7

Set $P=7$ and $Q=11$ . Observe that $Q\equiv 3\mod{8}$ and $\left(\frac{-Q}{3}\right)=-1$ . Set $T=2$ . Observe that $T^{2}\equiv-3\mod{19}$ . $\mathcal{H}_{-7,-11}$ is a quaternion algebra over $\mathbb{Q}$ which is of class number 1 and ramifies only at 7. By Theorem 4.1, $\mathcal{H}_{-3,-19}$ has a maximal order $\mathcal{O}_{-3,-19}=\mathbb{Z}+\mathbb{Z}\omega_{1}+\mathbb{Z}\omega_{2}+\mathbb{Z}\omega_{3}$ , where

\omega_{1}=\frac{1+j}{2},\quad\omega_{2}=\frac{i+ij}{2},\quad\omega_{3}=\frac{2j+ij}{11}.

Lemma 5.10.

$\mathcal{G}_{-7,-11}(\mathbb{Z})\cong\langle 1,\omega_{3}\rangle\cong A_{2}$

Proof.

For $\alpha=x+y\omega_{1}+z\omega_{2}+w\omega_{3}\in\mathcal{O}_{-7,-11}$ , it follows from (3) that

N(\alpha)=x^{2}+3y^{2}+21z^{2}+w^{2}+xy+2yw+7zw.

Solving $N(\alpha)=1$ , we get $4$ solutions in $\mathbb{Z}^{4}$ which form a group under multiplication. The solutions to $N(\alpha)=1$ are $\pm 1,\pm\omega_{3}$ . When we quotient by $\left\{\pm 1\right\}$ , we get the group $A_{2}$ . ∎

Proposition 5.11.

There exists a subgroup $H\leq\mathcal{G}_{-7,-11}(\mathbb{Z}/2\mathbb{Z})$ such that $H\cong C_{3}$ and $(H,2)$ is a congruence pair of $\mathcal{O}_{-7,-11}$ .

Proof.

Lemma 5.10 tells us that $\mathcal{G}_{-7,-11}(\mathbb{Z})\cong A_{2}$ embeds in $\mathcal{G}_{-7,-11}(\mathbb{Z}/2\mathbb{Z})$ and Proposition 3.7 implies that $\mathcal{G}_{-7,-11}(\mathbb{Z}/2\mathbb{Z})\cong\operatorname{PGL}_{2}(\mathbb{Z}/2\mathbb{Z})\cong S_{3}$ . There is only one class $[K]\in C_{S_{3}}$ such that $K\cong A_{2}$ . Furthermore, there exists $H\leq S_{3}$ such that $H\cong C_{3}$ and $H$ is a complementary subgroup of $C_{2}$ . Therefore, $(2,H)$ is a congruence pair of $\mathcal{O}_{-7,-11}$ . ∎

6. Further Directions for Finding Congruence Pairs

Theorem 4.6 tells us that a LPS-Type graph $\mathcal{X}$ is Ramanujan if we can find a congruence pair whose corresponding congruence subgroup contains the generating set of $\mathcal{X}$ . Therefore, it is of some interest to know what the congruence pairs of a given class number 1 maximal order are.

Question 6.1.

What are all the possible congruence pairs for class number one quaternion algebras?

We take some steps in answering this question. In the cases $P=3$ and $P=7$ , we show that there is no odd prime $m$ for which there exists a congruence pair $(m,H)$ of the respective maximal order. For the case $P=3$ , we use Propostion 6.2 to bound the possible $m$ for congruence pairs $(m,H)$ of $\mathcal{O}_{-P,-Q}$ . For a full treatment of Proposition 6.2, see [3, Chapter 12] or [7, Corollary 2.3]. While we only show the case $P=3$ and $P=7$ , Proposition 6.2 can be used for $P=2$ and $P=5$ to bound $m$ .

Proposition 6.2.

For $q>3$ an odd prime, the maximal subgroups of $\operatorname{PGL}_{2}(\mathbb{Z}/q\mathbb{Z})$ are as follows:

(1)

dihedral groups of order $2(q-1)$ for $q>5$ ,
(2)

dihedral groups of order $2(q+1)$ ,
(3)

a group of order $q(q-1)$ ,
(4)

$\operatorname{PSL}_{2}(\mathbb{Z}/q\mathbb{Z})$ ,
(5)

$S_{4}$ when $q\equiv\pm 3\pmod{8}$ .

Proposition 6.3.

There is no congruence pair $(m,H)$ associated with $\mathcal{O}_{-3,-19}$ for odd primes $m$ .

Proof.

We consider the following cases:

(1)

Let $m=3$ . Let $N$ and $H$ be as in Proposition 4.4, i.e.,

N=\{1+xi+yij:x,y\in\mathbb{Z}/3\mathbb{Z}\},\quad H=\{x+yj:x,y\in\mathbb{Z}/3\mathbb{Z}:(x,y)\not=(0,0)\}/\mathbb{Z}/3\mathbb{Z}^{\times}.

Then, $\#N=9$ , $\#H=4$ , and by Lemma 3.7, $\mathcal{G}_{-3,-19}(\mathbb{Z}/3\mathbb{Z})=H\rtimes N$ . Therefore, $\#\mathcal{G}_{-3,-19}(\mathbb{Z}/3\mathbb{Z})=36$ . Suppose that we can find $K\leq\mathcal{G}_{-3,-19}(\mathbb{Z}/3\mathbb{Z})$ that is a complement of $\mathcal{G}_{-3,-19}(\mathbb{Z})$ in $\mathcal{G}_{-3,-19}(\mathbb{Z}/3\mathbb{Z})$ . We have that $\#\mathcal{G}(\mathbb{Z})$ has order 6. Thus, $\#K=6$ , so $K$ has an element of order 4. We have that $2\omega_{1}=1+j\in\mathcal{G}_{-3,-19}(\mathbb{Z}/3\mathbb{Z})$ has order 4. Therefore, $1+j\not\in\mathcal{G}_{-3,-19}(\mathbb{Z})$ and $1+j\not\in K$ . We have that

\varphi_{3}(\mathcal{G}_{-3,-19}(\mathbb{Z}))=\left\{1,i+2j+2ij,i+j+ij,1+2ij,1+ij,j+ij\right\}.

One can check that for all $\alpha\in\mathcal{G}_{-3,-19}(\mathbb{Z})$ , $\alpha^{-1}(1+j)$ has order 4. Therefore, $1+j\neq\alpha\beta$ for $\alpha\in\mathcal{G}_{-3,-19}(\mathbb{Z})$ and $\beta\in K$ . This is a contradiction.

(2)

Let $m=5$ . One can check that every subgroup isomorphic to $S_{3}$ of $\operatorname{PGL}_{2}(\mathbb{Z}/5\mathbb{Z})\cong S_{5}$ does not have a complementary subgroup.
(3)

Let $m>5$ . Using Proposition 6.2, we see that for any prime $m>5$ , there is no index 6 subgroup of $\operatorname{PGL}_{2}(\mathbb{Z}/m\mathbb{Z})$ .

∎

Proposition 6.4.

There is no congruence pair $(m,H)$ associated with $\mathcal{O}_{-7,-11}$ for odd primes $m$ .

Proof.

Case 1 ( $m=7$ ): Let $N$ and $H$ be as in Proposition 3.7, i.e.,

N=\left\{1+xi+yij:x,y\in\mathbb{Z}/7\mathbb{Z}\right\},\quad H=\left\{x+yj:x,y\in\mathbb{Z}/7\mathbb{Z}:(x,y)\neq(0,0)\right\}/\mathbb{Z}/7\mathbb{Z}^{\times}.

Then $\#N=49$ , $\#H=8$ , and by Proposition 3.7, $\mathcal{G}_{-7,-11}(\mathbb{Z}/7\mathbb{Z})=H\rtimes N$ . Therefore, $\#\mathcal{G}_{-7,-11}(\mathbb{Z}/7\mathbb{Z})=392$ . Suppose that we can find $K$ that is the complement of $\mathcal{G}_{-7,-11}(\mathbb{Z})$ in $\mathcal{G}_{-7,-11}(\mathbb{Z}/7\mathbb{Z})$ . Then $\#K=196$ . Therefore, $K$ does not have any element of order $8$ . Therefore, $1+j\not\in K$ but $1+j\in\mathcal{G}(\mathbb{Z})\cdot K$ . We have that

\omega_{3}=\frac{2j+ij}{11}\equiv 4j+2ij\pmod{7}

and we quotient by scalers, so $\varphi_{7}(\omega_{3})=2j+ij$ . Therefore,

(2j+ij)^{-1}(1+j)=(2j+ij)(1+j)=-22-11i+2j+ij\equiv-1+3i-2j+ij\pmod{7}.

One can check that $-1+3i-2j+ij\in K$ has order 8, which is a contradiction. Therefore, it is impossible to find $K$ that satisfies our desired conditions.

Case 3 ( $m\not=7$ ): Observe that $1\not\equiv\omega_{3}\pmod{m}$ , so $\mathcal{G}_{-7,-11}(\mathbb{Z})$ embeds into $\mathcal{G}_{-7,-11}(\mathbb{Z}/m\mathbb{Z})$ . By Proposition 3.7, $\mathcal{G}_{-7,-11}(\mathbb{Z}/m\mathbb{Z})\cong\operatorname{PGL}_{2}(\mathbb{Z}/m\mathbb{Z})$ . Note that $\mathcal{G}_{-7,-11}(\mathbb{Z})$ maps to to a cyclic group of order 2 in $\operatorname{PSL}_{2}(\mathbb{Z}/m\mathbb{Z})$ . Suppose that we can find $K$ that is the complement of $\mathcal{G}_{-7,-11}(\mathbb{Z})$ in $\mathcal{G}_{-7,-11}(\mathbb{Z}/m\mathbb{Z})$ . Let $\overline{K}=K\cap\operatorname{PSL}_{2}(\mathbb{Z}/m\mathbb{Z})$ . Then, $\mathcal{G}_{-7,-11}(\mathbb{Z})\cdot\overline{K}=\operatorname{PSL}_{2}(\mathbb{Z}/m\mathbb{Z})$ and $\mathcal{G}_{-7,-11}(\mathbb{Z})\cap\overline{K}=\left\{1\right\}$ . However, this implies that $\overline{K}$ has index $2$ as a subgroup of $\operatorname{PSL}_{2}(\mathbb{Z}/m\mathbb{Z})$ which implies that $\overline{K}$ is normal in $\operatorname{PSL}_{2}(\mathbb{Z}/m\mathbb{Z})$ . This is a contradiction because $\operatorname{PSL}_{2}(\mathbb{Z}/m\mathbb{Z})$ is simple for odd primes $m\geq 3$ . ∎

Question 6.5.

Let $X$ and $Y$ be two Ramanujan graphs constructed from a Quaternion algebra. Suppose that $X$ and $Y$ have the same degree and same number of vertices. Are $X$ and $Y$ isomorphic? In particular, let $\mathcal{S}^{p},\mathcal{R}^{p}\subseteq\mathcal{O}_{-P,-Q}$ be sets with $p+1$ elements of norm $p$ which satisfy the conditions of Theorem 4.6. Then does there exist an isomorphism

\mathcal{X}_{-P,-Q}^{p,q}\left(\mathcal{S}^{p,q}\right)\cong\mathcal{X}_{-P,-Q}^{p,q}\left(\mathcal{R}^{p,q}\right)?

Question 6.6.

In Table 8.2 of [8], Kirschmer and Voight classify all definite class number one Eichler orders, which gives all the class number one maximal orders of quaternion algebras over a number field. For which of these orders can one find a congruence pair?

Acknowledgements

We would like to thank Professor Shai Evra and the Einstein Institute of Mathematics REU for their support during our research project. Professor Evra provided invaluable guidance and feedback, and the REU program’s funding and resources were essential to our success. We are grateful for the experience and knowledge gained from this opportunity.

References

[1] Patrick Chiu “Cubic Ramanujan graphs” In Combinatorica 12, 1992, pp. 275–285
[2] Giuliana Davidoff, Peter Sarnak and Alain Valette “Elementary Number Theory, Group Theory and Ramanujan Graphs”, London Mathematical Society Student Texts Cambridge: Cambridge University Press, 2003
[3] Leonard Eugene Dickson “Linear Groups, with an Exposition of the Galois Field Theory”, 1958
[4] Martin Eichler “The Basis Problem for Modular Forms and the Traces of the Hecke Operators” In Proc. of the Conf. on Modular Functions of One Variable V Berlin, Heidelberg: Springer Berlin Heidelberg, 1973, pp. 75–152
[5] Tomoyoshi Ibukiyama “On maximal orders of division quaternion algebras over the rational number field with certain optimal embeddings” In Nagoya Math. J. 88, 1982, pp. 181–195
[6] Hyungrok Jo and Yoshinori Yamasaki “LPS-type Ramanujan graphs” In 2018 International Symposium on Information Theory and Its Applications (ISITA) IEEE, 2018, pp. 399–403
[7] Oliver H. King “The subgroup structure of finite classical groups in terms of geometric configurations” In Surveys in Combinatorics 2005 327 Cambridge: Cambridge University Press, 2005, pp. 29–56
[8] Markus Kirschmer and John Voight “Algorithmic Enumeration of Ideal Classes for Quaternion Orders” In SIAM Journal on Computing 39.5, 2010, pp. 1714–1747
[9] Alexander Lubotzky “Discrete Groups, Expanding Graphs and Invariant Measures” Birkhäuser Basel, 1994
[10] Alexander Lubotzky, Ralph Phillips and Peter Sarnak “Ramanujan graphs” In Combinatorica 8, 1988, pp. 261–277
[11] Andrei Rapinchuk “On strong approximation for algebraic groups” In MSRI Publications 61, 2012, pp. 211–252
[12] Jean-Pierre Serre “Trees” Springer Berlin Heidelberg, 1980
[13] John Voight “Quaternion Algebras” 288, Graduate Texts in Mathematics Springer, 2021

LPS-Type Ramanujan Graphs from Definite Quaternion Algebras over ℚ\mathbb{Q} of Class Number One

Abstract.

1. Introduction

Theorem 1.1.

Theorem 1.2.

2. Preliminaries

Notation.

2.1. Quaternion Algebras

Proposition 2.1.

2.2. Orders of Quaternion Algebras

Theorem 2.2.

Corollary 2.3.

Proposition 2.4.

2.3. The Bruhat-Tits Tree

Theorem 2.5.

Proposition 2.6.

3. Ramanujan Graphs and Algebraic Groups

3.1. The Algebraic Group 𝒢\mathcal{G}

Proposition 3.1.

Proof.

Definition 3.2.

Definition 3.3.

Proposition 3.4.

Proof.

Proposition 3.5.

Proof.

Proposition 3.6.

Proof.

Proposition 3.7.

Proof.

Proposition 3.8.

Proof.

Proposition 3.9.

Proof.

Theorem 3.10.

4. Construction of Explicit Maximal Orders and LPS-Type Ramanujan Graphs

Proposition 4.1 ([5]).

Definition 4.2.

Proposition 4.3.

Lemma 4.4.

Proof.

Definition 4.5.

Theorem 4.6.

Proof.

Corollary 4.7.

5. The Ramanujan Property for Certain LPS-Type Graphs

Theorem 5.1.

Proposition 5.2.

Proof.

Proof of Theorem 5.1.

5.1. The Quaternion Algebra Ramifies at 2

Lemma 5.3.

Proof.

Proposition 5.4.

Proof.

5.2. The Quaternion Algebra Ramifies at 3

Lemma 5.5.

Proof.

Proposition 5.6.

Proof.

5.3. The Quaternion Algebra Ramifies at 5

Lemma 5.7.

Proof.

Lemma 5.8.

Proof.

Proposition 5.9.

Proof.

5.4. The Quaternion Algebra Ramifies at 7

Lemma 5.10.

Proof.

Proposition 5.11.

Proof.

6. Further Directions for Finding Congruence Pairs

Question 6.1.

Proposition 6.2.

Proposition 6.3.

Proof.

Proposition 6.4.

Proof.

Question 6.5.

LPS-Type Ramanujan Graphs from Definite Quaternion Algebras over $\mathbb{Q}$ of Class Number One

3.1. The Algebraic Group $\mathcal{G}$