# Computation of Hecke eigenvalues (mod $p$) via quaternions

Yiannis Fam

###### Abstract.

In a 1987 letter [SL96], Serre proves that the systems of Hecke eigenvalues
arising from mod $p$ modular forms (of fixed level $\Gamma(N)$ coprime to $p$,
and any weight $k$) are the same as those arising from functions
$\Omega(N)\to\overline{\mathbb{F}}_{p}$, where $\Omega(N)$ is some double
quotient of $D^{\times}(\mathbb{A}_{f})$ and $D$ is the unique quaternion
algebra over $\mathbb{Q}$ ramified at $\\{p,\infty\\}$. We present an
algorithm which then computes these Hecke eigenvalues on the quaternion side
in a combinatorial manner.

##  1\. Introduction

The study of Hecke eigenvalues originated from Ramanujan’s $\Delta$-function

$\Delta(q)=q\prod\limits_{n=1}^{\infty}(1-q^{n})^{24},$

a weight 12 and level 1 Hecke eigenform about which Ramanujan made a number of
conjectures that have motivated much of the theory of modular forms over the
past century. More recently, it is known [Del69] that a normalised Hecke
eigenform $f=\sum a_{n}q^{n}$ in $S_{k}(\Gamma_{0}(N);\epsilon)$ gives rise to
a mod $p$ Galois representation
$\rho:\mathrm{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})\to\mathrm{GL}_{2}(\overline{\mathbb{F}}_{p})$.
This representation is unramified away from $pN$ and is characterised by the
following trace and determinant of Frobenius data (mapped appropriately into
$\overline{\mathbb{F}}_{p}$):

$\mathrm{tr}(\rho(\mathrm{Frob}_{\ell}))=a_{\ell},\hskip
28.45274pt\mathrm{det}(\rho(\mathrm{Frob}_{\ell}))=\ell^{k-1}\epsilon(\ell).$

These representations play a central role in modern number theory, most
notably in the conjectures of Serre. As such, the mod $p$ Hecke eigenvalues
are objects of great interest, and so one may wish to enumerate these systems
of Hecke eigenvalues as a source of examples.

At present, there already exist algorithms for computing these Hecke
eigenvalues, for example using modular symbols in connection with the Eichler-
Shimura theorem [Wie06]. Our approach will instead make use of the following
theorem of Serre (where we have restricted his result to a fixed level
$\Gamma(N)$) [SL96], that tells us that one could instead compute these Hecke
eigenvalues by working with a particular quaternion algebra. The computation
of the Hecke eigenvalues then becomes a combinatorial one, which is perhaps a
more elementary approach.

######  Theorem 1.1.

Let $D$ be the unique quaternion algebra over $\mathbb{Q}$ ramified at
$\\{p,\infty\\}$. The systems of Hecke eigenvalues ($a_{\ell}$) (with
$a_{\ell}\in\overline{\mathbb{F}}_{p}$, $\ell\nmid pN$ and fixed $N\geq 3$
coprime to $p$) coming from the modular forms (mod $p$) of level $\Gamma(N)$,
are the same as those coming from the functions

$\left(\Omega(N):=U(N)\backslash
D^{\times}(\mathbb{A}_{f})/D^{\times}(\mathbb{Q})\right)\to\overline{\mathbb{F}}_{p}.$

We remark that in this theorem, we do not necessarily realise all the weight
$k$ systems of eigenvalues from the modular form side as weight $(k\mod
p^{2}-1)$ systems of eigenvalues on the quaternion side, only those arising
from weight $k$ eigenforms not divisible by the Hasse invariant. They will
still appear on the quaternion side when ranging over all weights.

######  Notation 1.2.

We need to explain some of this notation:

  * •

Let $\mathcal{O}$ be any maximal order of $D$.

  * •

Let $D_{\ell}=D\otimes\mathbb{Q}_{\ell}$ and
$\mathcal{O}_{\ell}=\mathcal{O}\otimes\mathbb{Z}_{\ell}$ a maximal order, for
any prime $\ell$. So
$\mathcal{O}_{\ell}\cong\mathrm{M}_{2}(\mathbb{Z}_{\ell})$ for $\ell\neq p$.

  * •

Let $D^{\times}(\mathbb{A}_{f})$ denote the finite part of the adelic points
of $D^{\times}$, in other words the restricted product
${\prod\limits_{\ell}}^{\prime}D^{\times}_{\ell}$ with respect to the
subgroups $\mathcal{O}_{\ell}^{\times}$.

  * •

Let $\pi\in\mathcal{O}$ be a uniformiser of $\mathcal{O}_{p}$.

  * •

Let $\mathcal{O}_{p}^{\times}(1)$ be the kernel of reduction mod $\pi$,
$\mathcal{O}_{p}^{\times}\to\mathbb{F}_{p^{2}}^{\times}$.

  * •

For $\ell\neq p$, let $\mathcal{O}_{\ell}^{\times}(N)$ be the subgroup of
$\mathcal{O}_{\ell}^{\times}\cong\mathrm{GL}_{2}(\mathbb{Z}_{\ell})$
consisting of elements congruent to 1 mod $\ell^{v_{\ell}(N)}$, where
$\ell^{v_{\ell}(n)}$ is the highest power of $\ell$ dividing $N$.

  * •

Let $U(N)=\mathcal{O}_{p}^{\times}(1)\times\prod\limits_{\ell\neq
p}\mathcal{O}_{\ell}^{\times}(N)$, an open subgroup of
$D^{\times}(\mathbb{A}_{f})$.

  * •

By a weight $k$ function $f:\Omega(N)\to\overline{\mathbb{F}}_{p}$ we mean a
function which satisfies $f(\mu\cdot[x_{\ell}])=\mu^{-k}f([x_{\ell}])$, where
$\mu\in\mathcal{O}_{p}^{\times}/\mathcal{O}_{p}^{\times}(1)\cong\mathbb{F}_{p^{2}}^{\times}$
acts on $[x_{\ell}]$ by multiplication in the $p$-place.

Note that elements of $\Omega(N)$ correspond to isomorphism classes of
invertible left $\mathcal{O}$-ideals $I$ with $\pi N$-structure, meaning a
basis for $I/\pi NI$ as an $\mathcal{O}/\pi N\mathcal{O}$-module. Explicitly,
an adelic point $(x_{\ell})$ corresponds to an ideal $I$ with
$I_{\ell}=\mathcal{O}_{\ell}x_{\ell}$ for all $\ell$. The $\pi N$-structure is
then given by the reduction modulo $\pi NI$ of any element $x\in I$ satisfying
the congruences

$x\equiv x_{\ell}\mod\pi NI_{\ell}$

for all $\ell$ (this congruence is vacuous for any $\ell\nmid pN$, so such $x$
exists by the Chinese remainder theorem). We then quotient $\Omega(N)$ by
$U(N)$ and $D^{\times}(\mathbb{Q})$ exactly to get the desired bijection.

For a prime $\ell_{0}\nmid pN$, the Hecke operator $T_{\ell_{0}}$ on this
space of functions $\Omega(N)\to\overline{\mathbb{F}}_{p}$ is given by

$T_{\ell_{0}}f([x_{\ell}])=\ell_{0}^{-1}\sum\limits_{i}f(g_{i}\cdot[x_{\ell_{0}}])$

for $\mathrm{GL}_{2}(\mathbb{Z}_{\ell_{0}})\begin{pmatrix}1&0\\\
0&\ell_{0}\end{pmatrix}\mathrm{GL}_{2}(\mathbb{Z}_{\ell_{0}})=\bigsqcup\mathrm{GL}_{2}(\mathbb{Z}_{\ell_{0}})g_{i}$.
Here $g_{i}\cdot[x_{\ell_{0}}]$ means we pick a representative $(x_{\ell})\in
D^{\times}(\mathbb{A}_{f})$ of $[x_{\ell}]$, multiply this in the
$\ell_{0}$-place by the matrix $g_{i}$ (under an identification of
$\mathcal{O}_{\ell_{0}}\cong\mathrm{M}_{2}(\mathbb{Z}_{\ell_{0}})$ and hence
of $D_{\ell_{0}}\cong\mathrm{M}_{2}(\mathbb{Q}_{\ell_{0}})$), and then take
the image in $\Omega(N)$. Each individual $g_{i}\cdot[x_{\ell}]$ is not well
defined in $[x_{\ell}]$, but $T_{l_{0}}$ is well defined, provided we pick the
same representative $(x_{\ell})\in D^{\times}(\mathbb{A}_{f})$ for each
multiplication. This Hecke module structure has been studied before, as in the
likes of [Koh01].

The algorithm we present computes a matrix for the Hecke operator
$T_{\ell_{0}}$ on the space of (weight $k$) functions
$\Omega(N)\to\overline{\mathbb{F}}_{p}$, where $\ell_{0},p$ and $N$ are
pairwise coprime. Note that we allow the cases $N=1,2$ as the definitions on
the quaternion side still make sense here. We begin by computing an
illustrative example for the case $p=11$, and then generalise this to weight
$k=0$ and level $N=1$ for any $p$. Note that in this case the matrices we
compute are exactly Brandt matrices. This is then extended to higher weight
and level, essentially by keeping track of the $\pi N$-structure.

We remark that a similar computation has been performed by Pizer in [Piz80].
This has since been applied in, for example, [SW05] and [CS01]. Pizer was
interested in computing the subspace of cusp forms on $\Gamma_{0}(N)$
generated by theta series, and the Hecke operators on this subspace. The
algorithm involves computing certain Brandt matrix series. The main difference
between our approach and Pizer’s is that we incorporate level $N$ structure
through coset representatives of
$\mathcal{O}_{\ell}^{\times}(N)\backslash\mathcal{O}_{\ell}^{\times}\cong\mathrm{GL}_{2}(\mathbb{Z}/\ell^{v_{\ell}(N)}\mathbb{Z})$.
See also [Dem05] and [Dem07] for a similar approach in the context of Hilbert
modular forms (the corresponding description of Hilbert modular forms on the
quaternion side is more involved than for modular forms). Pizer instead works
with orders of level $N$, which allows them to work purely with the quaternion
algebras, without having to write down explicit isomorphisms of the form
$\mathcal{O}_{\ell}\cong\mathrm{M}_{2}(\mathbb{Z}_{\ell})$, something that we
must do (see Section 3). On the other hand, the use of matrices perhaps makes
the contribution from the level structure more visible. The tradeoff is then
between computing these isomorphisms with the Hensel-like argument involved,
and computing orders of level $N$. A related point of difference is that in
Pizer’s argument one must compute the left ideal classes of an order of level
$N$, whereas we only need to compute these for our maximal order
$\mathcal{O}$, because our level structure is already captured in
$\mathcal{O}_{\ell}^{\times}(N)\backslash\mathcal{O}_{\ell}^{\times}\cong\mathrm{GL}_{2}(\mathbb{Z}/\ell^{v_{\ell}(N)}\mathbb{Z})$,
which is very concrete. Because a maximal order has minimal discriminant, the
corresponding Minkowski bound is lower, and so the computation of these ideal
classes in our case may be (somewhat) faster.

The author would like to thank his M.Phil. supervisors, Alex Ghitza and
Chenyan Wu, for their many helpful comments, and especially Alex for his
careful reading of the script and valuable corrections and suggestions.
Writing of this paper was partially supported by the University of Melbourne
Robert George Williams Scholarship, as well as the Australian Government
Research Training Program Scholarship.

##  2\. An Example

######  Example 2.1.

Take $p$ to be 11. The quaternion algebra $D$ is then
$D=\left(\frac{-1,-11}{\mathbb{Q}}\right)$. In this example we will work with
level $N=1$ as doing so greatly reduces the size of $\Omega(N)$. We will then
compute the Hecke eigenvalues on the space of functions on
$\Omega:=U\backslash D^{\times}(\mathbb{A}_{f})/D^{\times}(\mathbb{Q})$, where
$U:=\mathcal{O}_{p}^{\times}\times\prod\limits_{l\neq
p}\mathcal{O}_{\ell}^{\times}$ is not quite $U(1)$ as we replace
$\mathcal{O}_{p}^{\times}(1)$ with $\mathcal{O}_{p}^{\times}$. Note that this
is the same as computing the Hecke eigenvalues on $\Omega(1)$ of weight
$k\equiv 0\mod p^{2}-1$. Indeed, the modularity condition tells us that these
are functions on $\Omega(1)$ that are invariant under the action of
$\mathcal{O}_{p}^{\times}$, and so can be identified with functions on
$\Omega$. The computation in this section is based on notes of Buzzard [Buz].

Firstly, let’s understand the set $\Omega$. By the same argument that
$\Omega(N)$ corresponds to (isomorphism classes of) invertible left
$\mathcal{O}$-ideals $I$ with $\pi N$-structure, we see that $\Omega$
corresponds just to the invertible left $\mathcal{O}$-ideals $I$. Running the
following in MAGMA [BCP97], we compute a maximal order $\mathcal{O}$ of $D$,
and then find that its left ideal class set has order 2, whose elements we
call $I_{1}$ and $I_{2}$. So $\Omega$ has two elements. We can also compute
integer bases for $\mathcal{O}$, $I_{1}$ and $I_{2}$.

    >>ΨD := QuaternionAlgebra< RationalField() | -1, -11>;
    >>ΨO := MaximalOrder(D);
    >>ΨBasis(O);
    >>ΨClasses := LeftIdealClasses(O);
    >>Ψ#Classes;
    >>ΨI1 := Classes[1];
    >>ΨBasis(I1);
    >>ΨI2 := Classes[2];
    >>ΨBasis(I2);

which outputs:

    [ 1, i, 1/2*i + 1/2*k, 1/2 + 1/2*j ]
    2
    [ 1, -i, -1/2*i - 1/2*k, 1/2 - 1/2*j ]
    [ 2, -2*i, 1 - 3/2*i - 1/2*k, 1/2 - i - 1/2*j ]

We now want to rewrite $I_{1}$ and $I_{2}$ as adelic points in $\Omega$. For
any invertible left $\mathcal{O}$-ideal $I$, $I\otimes\mathbb{Z}_{\ell}$ is a
principal $\mathcal{O}_{\ell}$-ideal, generated by any nonzero element
$\alpha_{\ell}$ whose reduced norm has minimal valuation in
$\mathbb{Z}_{\ell}$. To see this, we refer to Corollary 16.6.12 in Voight
[Voi21] that any invertible semi-order (lattice that contains 1 and has
reduced norm equal to the ring $R=\mathbb{Z}_{\ell}$) is an order, so that
$(I\otimes\mathbb{Z}_{\ell})\alpha_{\ell}^{-1}$ is an invertible semi-order.
So if we are given a $\mathbb{Z}$-basis for $I$, then
$I\otimes\mathbb{Z}_{\ell}$ is generated by a basis element whose reduced norm
has minimal $\ell$-adic valuation. Computing the reduced norms of the given
basis elements of $I_{1}$ and $I_{2}$ we get $[1,1,3,3]$ and $[4,4,6,4]$
respectively. So we see that $I_{1}=\mathcal{O}$ (which was obvious anyway)
and $I_{2}\otimes\mathbb{Z}_{\ell}=\mathcal{O}\otimes\mathbb{Z}_{\ell}$ for
all $\ell\neq 2$. Moreover,
$I_{2}\otimes\mathbb{Z}_{2}=\mathcal{O}\otimes\mathbb{Z}_{2}\cdot(1-\frac{3}{2}i-\frac{1}{2}ij)$
as 6 has minimal 2-adic valuation. Thus $I_{1}$ corresponds to
$w^{1}:=[1,1,\dots]\in\Omega$ and $I_{2}$ corresponds to
$w^{2}:=[1-\frac{3}{2}i-\frac{1}{2}ij,1,1,\dots]\in\Omega$ (we use
superscripts here to avoid overloading the subscripts, which we want to use
for the places). An obvious choice of basis for the vector space of
$\overline{\mathbb{F}}_{p}$ valued functions on $\Omega$ are the
characteristic functions $\mathbbm{1}_{w^{1}}$ and $\mathbbm{1}_{w^{2}}$.

To compute the Hecke operator $T_{\ell_{0}}$, we will need to work with
matrices at the $\ell_{0}$-place. Let’s compute $T_{2}$ and $T_{3}$ with
respect to the basis $\\{\mathbbm{1}_{w^{1}},\mathbbm{1}_{w^{2}}\\}$. We will
need isomorphisms
$\mathcal{O}\otimes\mathbb{Z}_{2}\cong\mathrm{M}_{2}(\mathbb{Z}_{2})$ and
$\mathcal{O}\otimes\mathbb{Z}_{3}\cong\mathrm{M}_{2}(\mathbb{Z}_{3})$. In
general, we have an isomorphism

$\displaystyle D\otimes\mathbb{Q}_{\ell}$
$\displaystyle\cong\mathrm{M}_{2}(\mathbb{Q}_{\ell})$ $\displaystyle i$
$\displaystyle\mapsto\begin{pmatrix}0&-1\\\ 1&0\end{pmatrix}$ $\displaystyle
j$ $\displaystyle\mapsto\begin{pmatrix}x&y\\\ y&-x\end{pmatrix}$

for $x,y\in\mathbb{Q}_{\ell}$ such that $x^{2}+y^{2}=-11$, when $\ell\neq 11$.
For $\mathrm{M}_{2}(\mathbb{Z}_{3})$, note that
$\mathcal{O}\otimes\mathbb{Z}_{3}$ has $\mathbb{Z}_{3}$-basis
$\\{1,i,j,ij\\}$, by using the basis for $\mathcal{O}$ computed above and
noticing that 2 is invertible in $\mathbb{Z}_{3}$. So for any
$x,y\in\mathbb{Z}_{3}$ with $x^{2}+y^{2}=-11$, the above isomorphism restricts
to an injection
$\mathcal{O}\otimes\mathbb{Z}_{3}\hookrightarrow\mathrm{M}_{2}(\mathbb{Z}_{3})$,
which must in fact be an isomorphism by maximality. We could take
$(x,y)=(\sqrt{-11},0)$ for $\sqrt{-11}$ a root of $x^{2}+11=0$ in
$\mathbb{Z}_{3}$, choosing for example the root which is $1\mod 3$ by Hensel’s
lemma.

For $\mathrm{M}_{2}(\mathbb{Z}_{2})$ we need to be a little more careful
because we need $1,i,\frac{1}{2}i+\frac{1}{2}ij,\frac{1}{2}+\frac{1}{2}j$ to
all map to elements in $\mathrm{M}_{2}(\mathbb{Z}_{2})$, rather than just
$1,i,j,ij$. If we take $(x,y)=(\sqrt{-15},2)$ for $\sqrt{-15}$ a root of
$x^{2}+15=0$ in $\mathbb{Z}_{2}$ (taking for example the root congruent to
$1\mod 4$ by Hensel’s lemma), then we see that $\frac{1}{2}+\frac{1}{2}j$ maps
to $\begin{pmatrix}\frac{1+\sqrt{-15}}{2}&1\\\
1&\frac{1-\sqrt{-15}}{2}\end{pmatrix}$, which is in
$\mathrm{M}_{2}(\mathbb{Z}_{2})$. This gives us our desired isomorphism
$\mathcal{O}\otimes\mathbb{Z}_{2}\cong\mathrm{M}_{2}(\mathbb{Z}_{2})$. Note
that if we took instead $(x,y)=(2,\sqrt{-15})$, we would then map
$\frac{1}{2}+\frac{1}{2}j$ to
$\begin{pmatrix}\frac{3}{2}&\frac{\sqrt{-15}}{2}\\\
\frac{\sqrt{-15}}{2}&-\frac{1}{2}\end{pmatrix}$, which is not in
$\mathrm{M}_{2}(\mathbb{Z}_{2})$.

We now begin our computation of $T_{2}$, starting with the value of
$T_{2}(\mathbbm{1}_{w^{1}})(w^{1})$. By definition,

$2T_{2}(\mathbbm{1}_{w^{1}})(w^{1})=\mathbbm{1}_{w^{1}}\left(\begin{pmatrix}1&0\\\
0&2\end{pmatrix}\cdot[1,1,\dots]\right)+\mathbbm{1}_{w^{1}}\left(\begin{pmatrix}1&1\\\
0&2\end{pmatrix}\cdot[1,1,\dots]\right)+\mathbbm{1}_{w^{1}}\left(\begin{pmatrix}2&0\\\
0&1\end{pmatrix}\cdot[1,1,\dots]\right)$

so we reduce to checking, for example, whether $\begin{pmatrix}1&0\\\
0&2\end{pmatrix}\cdot[1,1,\dots]=\left[\begin{pmatrix}1&0\\\
0&2\end{pmatrix},1,1,\dots\right]$ is the same as $w^{1}=[1,1,\dots]$ or
$w^{2}=[1-\frac{3}{2}i-\frac{1}{2}ij,1,1,\dots]$ as an element of $\Omega$.

The condition that $\left[\begin{pmatrix}1&0\\\
0&2\end{pmatrix},1,1,\dots\right]=[1,1,\dots]$ in $\Omega$ is equivalent to
saying that the $\mathcal{O}$-ideal $\mathcal{J}$ is principal, where
$\mathcal{J}$ is defined by
$\mathcal{J}\otimes\mathbb{Z}_{2}=(\mathcal{O}\otimes\mathbb{Z}_{2})\cdot\begin{pmatrix}1&0\\\
0&2\end{pmatrix}$ and
$\mathcal{J}\otimes\mathbb{Z}_{\ell}=\mathcal{O}\otimes\mathbb{Z}_{\ell}$ for
all $\ell\neq 2$. If this was the case, then we see that $\mathcal{J}$ must be
generated by an element $\alpha$ of $\mathcal{O}$ (since
$\mathcal{J}\otimes\mathbb{Z}_{\ell}\subset\mathcal{O}\otimes\mathbb{Z}_{\ell}$
for all $\ell$) of reduced norm $2=\mathrm{det}\begin{pmatrix}1&0\\\
0&2\end{pmatrix}$. We have previously computed a basis
$[1,i,\frac{1}{2}i+\frac{1}{2}ij,\frac{1}{2}+\frac{1}{2}j]$ for $\mathcal{O}$.
Writing $\alpha=t+x\cdot
i+y\cdot(\frac{1}{2}i+\frac{1}{2}ij)+z\cdot(\frac{1}{2}+\frac{1}{2}j)$, for
$t,x,y,z\in\mathbb{Z}$, we compute

$\mathrm{nrd}(\alpha)=(t+\frac{1}{2}z)^{2}+(x+\frac{1}{2}y)^{2}+\frac{11}{4}y^{2}+\frac{11}{4}z^{2}.$

For this to be equal to 2, we must have $y=z=0$ and $t^{2}=x^{2}=1$. So
$\mathcal{J}$ must be $\mathcal{O}\cdot(1\pm i)$. This satisfies
$\mathcal{J}\otimes\mathbb{Z}_{\ell}=\mathcal{O}\otimes\mathbb{Z}_{\ell}$ for
$\ell\neq 2$, so we only need to check whether this works at 2. In other
words, we need to check if

$\mathrm{M}_{2}(\mathbb{Z}_{2})\cdot\begin{pmatrix}1&0\\\
0&2\end{pmatrix}=\mathrm{M}_{2}(\mathbb{Z}_{2})\cdot\begin{pmatrix}1&-1\\\
1&1\end{pmatrix}$

or

$\mathrm{M}_{2}(\mathbb{Z}_{2})\cdot\begin{pmatrix}1&0\\\
0&2\end{pmatrix}=\mathrm{M}_{2}(\mathbb{Z}_{2})\cdot\begin{pmatrix}1&1\\\
-1&1\end{pmatrix}$

where our isomorphism
$\mathcal{O}\otimes\mathbb{Z}_{2}\cong\mathrm{M}_{2}(\mathbb{Z}_{2})$ sends
$1+i$ to $\begin{pmatrix}1&-1\\\ 1&1\end{pmatrix}$, and $1-i$ to
$\begin{pmatrix}1&1\\\ -1&1\end{pmatrix}$. Equivalently, we need to check if

$\begin{pmatrix}1&-1\\\ 1&1\end{pmatrix}\begin{pmatrix}1&0\\\
0&2\end{pmatrix}^{-1}\in\mathrm{GL}_{2}(\mathbb{Z}_{2})\hskip
28.45274pt\text{or}\hskip 28.45274pt\begin{pmatrix}1&1\\\
-1&1\end{pmatrix}\begin{pmatrix}1&0\\\
0&2\end{pmatrix}^{-1}\in\mathrm{GL}_{2}(\mathbb{Z}_{2}).$

We see that neither is true. So we have computed one of the terms in
$T_{2}(\mathbbm{1}_{w^{1}})(w^{1})$, namely

$\mathbbm{1}_{w^{1}}\left(\begin{pmatrix}1&0\\\
0&2\end{pmatrix}\cdot[1,1,\dots]\right)=0.$

As a sanity check, we verify that $\left[\begin{pmatrix}1&0\\\
0&2\end{pmatrix},1,1,\dots\right]=[1-\frac{3}{2}i-\frac{1}{2}ij,1,\dots]=w^{2}\in\Omega$,
so that

$\mathbbm{1}_{w^{2}}\left(\begin{pmatrix}1&0\\\
0&2\end{pmatrix}\cdot[1,1,\dots]\right)=1$

as we would expect. The isomorphism
$\mathcal{O}\otimes\mathbb{Z}_{2}\cong\mathrm{M}_{2}(\mathbb{Z}_{2})$ sends
$1-\frac{3}{2}i-\frac{1}{2}ij$ to $\begin{pmatrix}2&\frac{3-\sqrt{-15}}{2}\\\
\frac{-3-\sqrt{-15}}{2}&0\end{pmatrix}$. Let $\mathcal{J}$ be the
$\mathcal{O}$-ideal generated by the adelic point $\left(\begin{pmatrix}1&0\\\
0&2\end{pmatrix},1,1,\dots\right)$, and $\mathcal{I}=I_{2}$ the ideal
generated by $(1-\frac{3}{2}i-\frac{1}{2}ij,1,\dots)$. Then the condition that
they correspond to the same element of $\Omega$ is equivalent to the existence
of some $\alpha\in D^{\times}(\mathbb{Q})$ such that
$\mathcal{J}=\mathcal{I}\alpha$. Checking this locally, this means
$\alpha\in(\mathcal{O}\otimes\mathbb{Z}_{\ell})^{\times}$ for $\ell\neq 2$,
and at $\ell=2$ we have

(1) $\begin{pmatrix}2&\frac{3-\sqrt{-15}}{2}\\\
\frac{-3-\sqrt{-15}}{2}&0\end{pmatrix}\alpha\begin{pmatrix}1&0\\\
0&2\end{pmatrix}^{-1}\in\mathrm{GL}_{2}(\mathbb{Z}_{2}).$

We can rewrite this as

$\alpha\in\begin{pmatrix}2&\frac{3-\sqrt{-15}}{2}\\\
\frac{-3-\sqrt{-15}}{2}&0\end{pmatrix}^{-1}\mathrm{GL}_{2}(\mathbb{Z}_{2})\begin{pmatrix}1&0\\\
0&2\end{pmatrix}$

so we see that $2\alpha\in\mathrm{M}_{2}(\mathbb{Z}_{2})$, by inverting the
matrix and clearing the denominator. It follows that if $\alpha$ exists, we
must have $2\alpha\in\mathcal{O}$, and $\mathrm{nrd}(\alpha)=1$, by checking
locally. There are finitely many possibilities for $2\alpha$, namely $\pm
2,\pm 2i,\pm i\pm\frac{1}{2}\pm\frac{1}{2}j,\pm
1\pm\frac{1}{2}i\pm\frac{1}{2}ij$. We need to check if any of these satisfies
(1) when we replace $\alpha$ with the corresponding matrix in
$\frac{1}{2}\mathrm{M}_{2}(\mathbb{Z}_{2})$. A computation shows that one can
take $\alpha=\frac{1}{2}(i+\frac{1}{2}(1+j))$, where we need that actually
$\sqrt{-15}\equiv 1\mod 8$ for our choice of square root.

Returning to our computation of $T_{2}(\mathbbm{1}_{w^{1}})(w^{1})$, we need
to compute the remaining terms $\mathbbm{1}_{w^{1}}\left(\begin{pmatrix}1&1\\\
0&2\end{pmatrix}\cdot[1,1,\dots]\right)$ and
$\mathbbm{1}_{w^{1}}\left(\begin{pmatrix}2&0\\\
0&1\end{pmatrix}\cdot[1,1,\dots]\right)$. By the same argument as above, it
suffices to check whether

$\begin{pmatrix}1&-1\\\ 1&1\end{pmatrix}\begin{pmatrix}1&1\\\
0&2\end{pmatrix}^{-1}\in\mathrm{GL}_{2}(\mathbb{Z}_{2})\hskip
28.45274pt\text{or}\hskip 28.45274pt\begin{pmatrix}1&1\\\
-1&1\end{pmatrix}\begin{pmatrix}1&1\\\
0&2\end{pmatrix}^{-1}\in\mathrm{GL}_{2}(\mathbb{Z}_{2})$

for the first term, and whether

$\begin{pmatrix}1&-1\\\ 1&1\end{pmatrix}\begin{pmatrix}2&0\\\
0&1\end{pmatrix}^{-1}\in\mathrm{GL}_{2}(\mathbb{Z}_{2})\hskip
28.45274pt\text{or}\hskip 28.45274pt\begin{pmatrix}1&1\\\
-1&1\end{pmatrix}\begin{pmatrix}2&0\\\
0&1\end{pmatrix}^{-1}\in\mathrm{GL}_{2}(\mathbb{Z}_{2})$

for the second. The first two are true and the last two are not. So we deduce
that

$\mathbbm{1}_{w^{1}}\left(\begin{pmatrix}1&1\\\
0&2\end{pmatrix}\cdot[1,1,\dots]\right)=1\hskip 28.45274pt\text{and}\hskip
28.45274pt\mathbbm{1}_{w^{1}}\left(\begin{pmatrix}2&0\\\
0&1\end{pmatrix}\cdot[1,1,\dots]\right)=0.$

Therefore

$2T_{2}(\mathbbm{1}_{w^{1}})(w^{1})=0+1+0=1.$

We can also deduce that $2T_{2}(\mathbbm{1}_{w^{2}})(w^{1})=3-1=2$.

One similarly shows that $2T_{2}(\mathbbm{1}_{w^{1}})(w^{2})=3$ and so
$2T_{2}(\mathbbm{1}_{w^{2}})(w^{2})=0$. The required computation is to show
that the $\mathcal{O}$-ideals generated by
$\left(g\cdot\begin{pmatrix}2&\frac{3-\sqrt{-15}}{2}\\\
\frac{-3-\sqrt{-15}}{2}&0\end{pmatrix},1,1,\dots\right)$, for
$g=\begin{pmatrix}1&0\\\ 0&2\end{pmatrix},\begin{pmatrix}1&1\\\
0&2\end{pmatrix}$ and $\begin{pmatrix}2&0\\\ 0&1\end{pmatrix}$, are principal
$\mathcal{O}$-ideals. The generators can be taken to be
$\alpha=-i+\frac{1}{2}-\frac{1}{2}j,i+\frac{1}{2}-\frac{1}{2}j$ and $2$
respectively.

It follows that
$2T_{2}(\mathbbm{1}_{w^{1}})=\mathbbm{1}_{w^{1}}+3\mathbbm{1}_{w^{2}}$ and
$2T_{2}(\mathbbm{1}_{w^{2}})=2\mathbbm{1}_{w^{1}}$, so $T_{2}$ has matrix
$\frac{1}{2}\begin{pmatrix}1&2\\\ 3&0\end{pmatrix}$ with respect to the basis
$\\{\mathbbm{1}_{w^{1}},\mathbbm{1}_{w^{2}}\\}$. The eigenvalues are
$\lambda=\frac{-2}{2},\frac{3}{2}\in\overline{\mathbb{F}}_{11}$.

The Hecke operator $T_{3}$ can be computed in a similar way. We give one
example evaluating the summand

$\mathbbm{1}_{w^{2}}\left(\begin{pmatrix}1&0\\\
0&3\end{pmatrix}\cdot\left[\begin{pmatrix}2&\frac{3-\sqrt{-15}}{2}\\\
\frac{-3-\sqrt{-15}}{2}&0\end{pmatrix},1,1,\dots\right]\right)=\mathbbm{1}_{w^{2}}\left(\left[\begin{pmatrix}2&\frac{3-\sqrt{-15}}{2}\\\
\frac{-3-\sqrt{-15}}{2}&0\end{pmatrix},\begin{pmatrix}1&0\\\
0&3\end{pmatrix},1,1,\dots\right]\right)$

of $3T_{3}(\mathbbm{1}_{w^{2}})(w^{2})$. One could do this by checking whether
the $\mathcal{O}$-ideal $\mathcal{J}$ generated by the adelic point in the
square brackets is principal. If it is, then this value of
$\mathbbm{1}_{w^{2}}$ is $0$. This only works because $\Omega$ has two
elements. In general, we need to check if $\mathcal{J}$ is in the same left
ideal class as the $\mathcal{O}$-ideal $\mathcal{I}=I_{2}$ generated by the
adelic point $\left(\begin{pmatrix}2&\frac{3-\sqrt{-15}}{2}\\\
\frac{-3-\sqrt{-15}}{2}&0\end{pmatrix},1,1,\dots\right)$. So we need to check
if there exists $\alpha\in D^{\times}$ such that
$\mathcal{J}=\mathcal{I}\alpha$. Checking this locally, we need (for the two
isomorphisms $D\otimes\mathbb{Q}_{2}\cong\mathrm{M}_{2}(\mathbb{Q}_{2})$ and
$D\otimes\mathbb{Q}_{3}\cong\mathrm{M}_{2}(\mathbb{Q}_{3})$ specified)

(2) $\begin{pmatrix}2&\frac{3-\sqrt{-15}}{2}\\\
\frac{-3-\sqrt{-15}}{2}&0\end{pmatrix}\alpha\begin{pmatrix}2&\frac{3-\sqrt{-15}}{2}\\\
\frac{-3-\sqrt{-15}}{2}&0\end{pmatrix}^{-1}\in\mathrm{GL}_{2}(\mathbb{Z}_{2})$

and

(3) $\alpha\begin{pmatrix}1&0\\\
0&3\end{pmatrix}^{-1}\in\mathrm{GL}_{2}(\mathbb{Z}_{3})$

and $\alpha\in(\mathcal{O}\otimes\mathbb{Z}_{\ell})^{\times}$ for $\ell\neq
2,3$. The first two conditions imply that
$2\alpha\in\mathcal{O}\otimes\mathbb{Z}_{2}$ and
$\alpha\in\mathcal{O}\otimes\mathbb{Z}_{3}$. So $2\alpha\in\mathcal{O}$, and
$\mathrm{nrd}(\alpha)=3$. There are finitely many possibilities for $2\alpha$.

Before we go through all the possibilities for $2\alpha$ and check whether
they satisfy the two equations, we remark that for equation (2) we only really
need to work with $2\alpha$ and the matrix
$\begin{pmatrix}2&\frac{3-\sqrt{-15}}{2}\\\
\frac{-3-\sqrt{-15}}{2}&0\end{pmatrix}$ modulo some power of 2 (and for
equation (3) we only need $2\alpha$ modulo some power of 3). Indeed, using the
fact that our choice of $\sqrt{-15}$ is congruent to $1\mod 8$, we have

$\begin{pmatrix}2&\frac{3-\sqrt{-15}}{2}\\\
\frac{-3-\sqrt{-15}}{2}&0\end{pmatrix}\equiv\begin{pmatrix}2&1\\\
2&0\end{pmatrix}\mod 4.$

Suppose $2\alpha$ has matrix $\begin{pmatrix}a_{2}&b_{2}\\\
c_{2}&d_{2}\end{pmatrix}\in\mathrm{M}_{2}(\mathbb{Z}_{2})$. Then equation (2)
tells us (after inverting the matrix) that we need

$\begin{pmatrix}2&\frac{3-\sqrt{-15}}{2}\\\
\frac{-3-\sqrt{-15}}{2}&0\end{pmatrix}\begin{pmatrix}a_{2}&b_{2}\\\
c_{2}&d_{2}\end{pmatrix}\begin{pmatrix}0&\frac{-3+\sqrt{-15}}{2}\\\
\frac{3+\sqrt{-15}}{2}&2\end{pmatrix}\in 4\mathrm{M}_{2}(\mathbb{Z}_{2}).$

Note that the norm condition on $\alpha$ will then guarantee that we land in
$4\mathrm{GL}_{2}(\mathbb{Z}_{2})$ not just $4\mathrm{M}_{2}(\mathbb{Z}_{2})$.
Working modulo 4, we need

$\begin{pmatrix}2&1\\\ 2&0\end{pmatrix}\begin{pmatrix}a_{2}&b_{2}\\\
c_{2}&d_{2}\end{pmatrix}\begin{pmatrix}0&-1\\\ 2&2\end{pmatrix}\equiv 0\mod
4.$

Expanding this out, this is equivalent to

(4) $2\mid a_{2},\hskip 30.00005pt4\mid c_{2},\hskip 30.00005pt2\mid d_{2}.$

Similarly, if $2\alpha$ has matrix $\begin{pmatrix}a_{3}&b_{3}\\\
c_{3}&d_{3}\end{pmatrix}\in\mathrm{M}_{2}(\mathbb{Z}_{3})$, then equation (3)
is equivalent to

(5) $3\mid b_{3},\hskip 30.00005pt3\mid d_{3}.$

So now we look through $2\alpha\in\mathcal{O}$ of reduced norm 12. Write

$2\alpha=t\cdot 1+x\cdot i+y\cdot\frac{1}{2}(i+ij)+z\cdot\frac{1}{2}(1+j)$

for $t,x,y,z\in\mathbb{Z}$. We also compute the images of the basis elements
$1,i,\frac{1}{2}(i+ij),\frac{1}{2}(1+j)$ in $\mathrm{M}_{2}(\mathbb{Z}_{2})$
and $\mathrm{M}_{2}(\mathbb{Z}_{3})$, then reduce them modulo 4 and 3
respectively:

$i\mapsto\begin{pmatrix}0&-1\\\ 1&0\end{pmatrix}\mod 4\hskip
70.0001pti\mapsto\begin{pmatrix}0&-1\\\ 1&0\end{pmatrix}\mod 3$
$\frac{1}{2}(i+ij)\mapsto\begin{pmatrix}-1&0\\\ 1&1\end{pmatrix}\mod 4\hskip
70.0001pt\frac{1}{2}(i+ij)\mapsto\begin{pmatrix}0&0\\\ 1&0\end{pmatrix}\mod
3.$ $\frac{1}{2}(1+j)\mapsto\begin{pmatrix}1&1\\\ 1&0\end{pmatrix}\mod 4\hskip
70.0001pt\frac{1}{2}(1+j)\mapsto\begin{pmatrix}1&0\\\ 0&0\end{pmatrix}\mod 3$

It follows that

$2\alpha\mapsto\begin{pmatrix}t-y+z&-x+z\\\ x+y+z&t+y\end{pmatrix}\mod 4\hskip
70.0001pt2\alpha\mapsto\begin{pmatrix}t+z&-x\\\ x+y&t\end{pmatrix}\mod 3.$

Hence equations (4) and (5) tell us that there exists $2\alpha\in\mathcal{O}$
of reduced norm 12 satisfying equations (2) and (3), if and only if we can
find $t,x,y,z\in\mathbb{Z}$ such that

$2\mid t-y+z,t+y,\hskip 20.00003pt4\mid x+y+z,\hskip 20.00003pt3\mid
x,t,\hskip
20.00003pt(t+\frac{1}{2}z)^{2}+(x+\frac{1}{2}y)^{2}+\frac{11}{4}y^{2}+\frac{11}{4}z^{2}=12$

where the last equation tells us the reduced norm is 12. We can check that
there are no such solutions. For example, we see that $z$ must be even, and
then from the norm condition we see that $\lvert z\rvert\leq 2$. Trying $z=2$,
the norm condition tells us that we must have $(t,x,y)=(0,0,0),(-2,0,0)$ or
$(-1,\pm 1,0)$, none of which satisfy the congruence conditions. For $z=-2$ we
similarly must have $(t,x,y)=(0,0,0),(2,0,0)$ or $(1,\pm 1,0)$ which also does
not work. And finally for $z=0$ we need
$t^{2}+(x+\frac{1}{2}y)^{2}+\frac{11}{4}y^{2}=12$. Since $3\mid t$, in one
case we have $t^{2}=9$, and then in $(x+\frac{1}{2}y)^{2}+\frac{11}{4}y^{2}=3$
there are no solutions with $4\mid x+y$ and $3\mid x$. Otherwise we have $t=0$
and $(x+\frac{1}{2}y)^{2}+\frac{11}{4}y^{2}=12$ with $2\mid y$, $4\mid x+y$
and $3\mid x$, which has no solutions, checking $y=0,\pm 2$.

We deduce that

$\mathbbm{1}_{w^{2}}\left(\begin{pmatrix}1&0\\\
0&3\end{pmatrix}\cdot\left[\begin{pmatrix}2&\frac{3-\sqrt{-15}}{2}\\\
\frac{-3-\sqrt{-15}}{2}&0\end{pmatrix},1,1,\dots\right]\right)=0.$

Performing the remaining calculations, using the relevant mod 3 and 4 matrices
we have already written down above, we find that $T_{3}$ has matrix
$\frac{1}{3}\begin{pmatrix}2&2\\\ 3&1\end{pmatrix}$ with respect to the basis
$\\{\mathbbm{1}_{w^{1}},\mathbbm{1}_{w^{2}}\\}$. We compute the eigenvalues to
be $\frac{-1}{3},\frac{4}{3}\in\overline{\mathbb{F}}_{11}$.

Comparing the matrices for $T_{2}$ and $T_{3}$, they are simultaneously
diagonalisable (as expected) with eigenvectors $\scriptsize\begin{pmatrix}2\\\
-3\end{pmatrix}$ and $\scriptsize\begin{pmatrix}1\\\ 1\end{pmatrix}$. The
corresponding eigenvalues are
$(a_{2},a_{3})=\left(\frac{-2}{2},\frac{-1}{3}\right)=(-1,-4)$ and
$(a_{2},a_{3})=\left(\frac{3}{2},\frac{4}{3}\right)=(7,5)$, viewing
$a_{2},a_{3}$ as elements of $\overline{\mathbb{F}}_{11}$. In view of Serre’s
Theorem 1.1, one might wonder what mod 11 modular forms give rise to these
eigenvalues. The first comes from $\theta^{9}(\Delta)=q-q^{2}-4q^{3}+\dots\mod
11$, which has minimal weight filtration 120, and the second from the Hasse
invariant $E_{10}$.

##  3\. Explicit isomorphisms
$\mathcal{O}\otimes\mathbb{Z}_{\ell}\cong\mathrm{M}_{2}(\mathbb{Z}_{\ell})$

We now work with any prime $p$. Let $D$ be the unique quaternion algebra over
$\mathbb{Q}$ ramified exactly at $\\{p,\infty\\}$. It turns out that one can
take $D\cong\left(\frac{-1,-p}{\mathbb{Q}}\right)$ and
$\left(\frac{-2,-p}{\mathbb{Q}}\right)$ when respectively, $p\equiv 3\mod 4$
(or $p=2$), and $p\equiv 5\mod 8$. In the remaining case $p\equiv 1\mod 8$, we
can take $D\cong\left(\frac{-r,-p}{\mathbb{Q}}\right)$ for any prime $r\equiv
3\mod 4$ with $\left(\frac{r}{p}\right)=-1$. This can be verified by
computations with the Hilbert symbol as in [Voi21] Chapter 12. We will write
$D=\left(\frac{-\epsilon,-p}{\mathbb{Q}}\right)$ for an appropriate
$\epsilon$.

In the example of the previous section, we wrote down explicit isomorphisms
$\mathcal{O}\otimes\mathbb{Z}_{\ell}\cong\mathrm{M}_{2}(\mathbb{Z}_{\ell})$.
In general this is tricky to do, complicated by the fact that $\mathcal{O}$
might properly contain the order with $\mathbb{Z}$-basis $\\{1,i,j,ij\\}$ \-
we can have nontrivial denominators. See also [Voi13] for an algorithm for
computing such isomorphisms, which arose as a byproduct of other more involved
algorithms. Let $\mathcal{O}$ have $\mathbb{Z}$-basis
$\\{s^{1},s^{2},s^{3},s^{4}\\}$. What we need to do is find matrices
$A,B\in\mathrm{M}_{2}(\mathbb{Z}_{\ell})$ (corresponding to $i,j$) such that

$A^{2}=-\epsilon,\hskip 20.00003ptB^{2}=-p,\hskip 20.00003ptAB=-BA,$

and such that the matrices corresponding to $s^{1},s^{2},s^{3},s^{4}$, which a
priori have entries in $\mathbb{Q}_{\ell}$, actually have entries in
$\mathbb{Z}_{\ell}$. This latter condition just imposes some congruences on
the entries of $A$ and $B$. For example, in the case $p=11$ using the given
basis for $\mathcal{O}$, we also require that

$\frac{1}{2}(A+AB)\in\mathrm{M}_{2}(\mathbb{Z}_{\ell})\hskip
50.00008pt\text{and}\hskip
50.00008pt\frac{1}{2}(1+B)\in\mathrm{M}_{2}(\mathbb{Z}_{\ell})$

which only imposes congruence conditions when $\ell=2$. If we can do this in
the general case, then this gives us an isomorphism
$D\otimes\mathbb{Q}_{\ell}\cong\mathrm{M}_{2}(\mathbb{Q}_{\ell})$, which
restricts to an injection
$\mathcal{O}\otimes\mathbb{Z}_{\ell}\hookrightarrow\mathrm{M}_{2}(\mathbb{Z}_{\ell})$.
But $\mathcal{O}\otimes\mathbb{Z}_{\ell}$ is a maximal order in
$D\otimes\mathbb{Q}_{\ell}$, so this injection must actually be our desired
isomorphism.

The main observation is that, for our purposes, we really only need the
matrices corresponding to the $s^{1},s^{2},s^{3},s^{4}$ modulo some
sufficiently large power of $\ell$. Consequently, we only need to compute $A$
and $B$ modulo some $\ell^{n_{\ell}}$. This was hinted at in the computation
of $T_{3}$ in the example above. We will describe a formula for a sufficiently
large $n_{\ell}$ later. So we need to search for $A_{0}$ and $B_{0}$ in
$\mathrm{M}_{2}(\mathbb{Z}/\ell^{n_{\ell}}\mathbb{Z})$ for some $n_{\ell}$,
which satisfy

$A_{0}^{2}=-\epsilon,\hskip 20.00003ptB_{0}^{2}=-p,\hskip
20.00003ptA_{0}B_{0}=-B_{0}A_{0}\mod\ell^{n_{\ell}}$

and the congruence conditions imposed by the basis of $\mathcal{O}$ (we take
$n_{\ell}$ sufficiently large so that these congruences can be viewed as
congruences modulo $\ell^{n_{\ell}}$). We know that such $A_{0}$ and $B_{0}$
exist because we know that there exists an isomorphism
$\mathcal{O}\otimes\mathbb{Z}_{\ell}\cong\mathrm{M}_{2}(\mathbb{Z}_{\ell})$.
Since $i,j\in\mathcal{O}$ have reduced trace 0, we can furthermore assume that
$A_{0}$ and $B_{0}$ are trace-free. Then such a solution can be found by a
finite enumeration of all matrices in
$\mathrm{M}_{2}(\mathbb{Z}/\ell^{n_{\ell}}\mathbb{Z})$ (a more efficient
method would be to use the lemma below repeatedly). The claim then is that
these solutions can be lifted to our desired $A$ and $B$ (although we do not
need to write down $A$ and $B$, just know that $A_{0}$ and $B_{0}$ lift). Note
that $A$ and $B$ will automatically satisfy the congruence conditions from the
basis of $\mathcal{O}$ because we are lifting from $A_{0}$ and $B_{0}$. This
is the content of the following lemma (for $\ell\neq 2$).

######  Lemma 3.1.

Suppose we have trace-free matrices
$A_{0},B_{0}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{m}\mathbb{Z})$ for $\ell\neq p$
an odd prime and $m\geq 2$, and suppose they satisfy

$A_{0}^{2}=-\epsilon\mod\ell^{m},\hskip
20.00003ptB_{0}^{2}=-p\mod\ell^{m},\hskip
20.00003ptA_{0}B_{0}=-B_{0}A_{0}\mod\ell^{m}.$

Then we can find trace-free matrices
$A_{1},B_{1}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{m+1}\mathbb{Z})$ satisfying

$A_{1}^{2}=-\epsilon\mod\ell^{m+1},\hskip
20.00003ptB_{1}^{2}=-p\mod\ell^{m+1},\hskip
20.00003ptA_{1}B_{1}=-B_{1}A_{1}\mod\ell^{m+1}$

with $A_{1}\equiv A_{0}\mod\ell^{m}$ and $B_{1}\equiv B_{0}\mod\ell^{m}$. It
follows that we can lift to desired matrices
$A,B\in\mathrm{M}_{2}(\mathbb{Z}_{\ell})$ by induction.

###### Proof.

Our proof involves writing out all the matrix entries and multiplying them
together. The requirement that the matrices be trace-free simplify our
calculations. Let

$A_{0}=\begin{pmatrix}a_{1}&a_{2}\\\
a_{3}&-a_{1}\end{pmatrix}\mod\ell^{m}\hskip
50.00008ptB_{0}=\begin{pmatrix}b_{1}&b_{2}\\\
b_{3}&-b_{1}\end{pmatrix}\mod\ell^{m}.$

Lifting these to (trace-free) matrices modulo $\ell^{m+1}$, we will write

$A_{1}=A_{0}+\ell^{m}X\mod\ell^{m+1}\hskip
50.00008ptB_{1}=B_{0}+\ell^{m}Y\mod\ell^{m+1}$

for trace-free matrices

$X=\begin{pmatrix}x_{1}&x_{2}\\\ x_{3}&-x_{1}\end{pmatrix}\mod\ell\hskip
50.00008ptY=\begin{pmatrix}y_{1}&y_{2}\\\ y_{3}&-y_{1}\end{pmatrix}\mod\ell.$

A useful calculation is the following: if $P=\begin{pmatrix}p_{1}&p_{2}\\\
p_{3}&-p_{1}\end{pmatrix}$ and $Q=\begin{pmatrix}q_{1}&q_{2}\\\
q_{3}&-q_{1}\end{pmatrix}$ are trace-free matrices, then

$PQ+QP=\begin{pmatrix}2p_{1}q_{1}+p_{2}q_{3}+p_{3}q_{2}&0\\\
0&2p_{1}q_{1}+p_{2}q_{3}+p_{3}q_{2}\end{pmatrix}.$

It follows that if we lift $A_{0}$ and $B_{0}$ to any trace-free matrices
modulo $\ell^{m+1}$, also denoted $A_{0}$ and $B_{0}$, we have that

$A_{0}^{2}=-\epsilon+\ell^{m}(*)\mod\ell^{m+1},\hskip
20.00003ptB_{0}^{2}=-p+\ell^{m}(*)\mod\ell^{m+1},\hskip
20.00003ptA_{0}B_{0}+B_{0}A_{0}=\ell^{m}(*)\mod\ell^{m+1}$

where the $(*)$ are all scalar matrices modulo $\ell$. The conditions on $X$
and $Y$ coming from those on $A_{1}$ and $B_{1}$ are the following:

$2a_{1}x_{1}+a_{2}x_{3}+a_{3}x_{2}=(*)\mod\ell,\hskip
20.00003pt2b_{1}y_{1}+b_{2}y_{3}+b_{3}y_{2}=(*)\mod\ell$
$(2a_{1}y_{1}+a_{2}y_{3}+a_{3}y_{2})+(2b_{1}x_{1}+b_{2}x_{3}+b_{3}x_{2})=(*)\mod\ell$

for some scalars $(*)\mod\ell$. We can rewrite this as

$\begin{pmatrix}2a_{1}&a_{3}&a_{2}&0&0&0\\\ 0&0&0&2b_{1}&b_{3}&b_{2}\\\
2b_{1}&b_{3}&b_{2}&2a_{1}&a_{3}&a_{2}\end{pmatrix}\cdot\small\begin{pmatrix}x_{1}\\\
x_{2}\\\ x_{3}\\\ y_{1}\\\ y_{2}\\\ y_{3}\end{pmatrix}=(*)\mod\ell$

for some arbitrary vector $(*)\in\mathbb{F}_{\ell}^{3}$. This is always
possible if the vectors
$\begin{pmatrix}2a_{1}&a_{3}&a_{2}\end{pmatrix}\mod\ell$ and
$\begin{pmatrix}2b_{1}&b_{3}&b_{2}\end{pmatrix}\mod\ell$ are linearly
independent. Since $\ell\neq 2$, linear dependence is equivalent to the
existence of a nonzero scalar $\lambda$ such that $A_{0}=\lambda
B_{0}\mod\ell$, or that either $A_{0}$ or $B_{0}$ is 0 mod $\ell$. The latter
two cases are not possible because otherwise $A_{0}^{2}=0\mod\ell^{2}$ or
$B_{0}^{2}=0\mod\ell^{2}$. Since $m\geq 2$, this means that $\ell^{2}$ divides
$\epsilon$ or $p$, which does not happen (we had to use $\ell^{2}$ in case
$\epsilon=r$ and $\ell=r$). And in the first case,
$A_{0}B_{0}+B_{0}A_{0}=0\mod\ell$ tells us that
$A_{0}^{2}=B_{0}^{2}=0\mod\ell$, which is false since $\ell\neq p$. Hence we
can always lift $A_{0},B_{0}\mod\ell^{m}$ to $A_{1},B_{1}\mod\ell^{m+1}$. ∎

###  3.1. The case $\ell=2$

When $\ell=2$, the argument of Lemma 3.1 does not work, analogous to the
difficulty of using a naive Hensel’s lemma for finding square roots in
$\mathbb{Z}_{2}$. We will make use of a generalised Hensel’s lemma for
multiple variables, which can be found as Theorem 3.3 in Conrad’s notes [Con],
specialised to the case of $\mathbb{Q}_{2}$ with its usual absolute value
$\lvert\cdot\rvert$.

######  Theorem 3.2.

Let
$\mathbf{f}=(f_{1},f_{2},\dots,f_{d})\in\mathbb{Z}_{2}[X_{1},X_{2},\dots,X_{d}]^{d}$
and $\mathbf{a}=(a_{1},\dots,a_{d})\in\mathbb{Z}_{2}^{d}$ satisfy

$\left\lVert\mathbf{f}(\mathbf{a})\right\rVert<\lvert
J_{\mathbf{f}}(\mathbf{a})\rvert^{2}$

where $J_{\mathbf{f}}$ is the Jacobian of $f$ \- the determinant of its
derivative matrix - and the norm of a vector is defined to be the maximum of
the absolute values of its entries. Then there is a unique
$\mathbf{\alpha}\in\mathbb{Z}_{2}^{d}$ such that
$\mathbf{f}(\mathbf{\alpha})=0$ and
$\left\lVert\mathbf{\alpha}-\mathbf{a}\right\rVert<\lvert
J_{\mathbf{f}}(\mathbf{a})\rvert$.

To see how to apply this, we are looking for matrices
$A,B\in\mathrm{M}_{2}(\mathbb{Z}_{2})$ satisfying

$A^{2}=-\epsilon,\hskip 20.00003ptB^{2}=-p,\hskip 20.00003ptAB=-BA,$

which also satisfy certain congruence conditions mod 4 (the highest power of 2
possibly dividing denominators in $s^{1},s^{2},s^{3},s^{4}$ \- see Proposition
3.7 to follow). Because we know
$\mathcal{O}\otimes\mathbb{Z}_{2}\cong\mathrm{M}_{2}(\mathbb{Z}_{2})$, we know
that such $A$ and $B$ exist, so we can find such a solution modulo some power
of 2 bigger than 4 and try to lift to $\mathbb{Z}_{2}$. If
$A=\begin{pmatrix}a_{1}&a_{2}\\\ a_{3}&-a_{1}\end{pmatrix}$ and
$B=\begin{pmatrix}b_{1}&b_{2}\\\ b_{3}&-b_{1}\end{pmatrix}$ with entries in
$\mathbb{Z}_{2}$, then the conditions

$A^{2}=-\epsilon,\hskip 20.00003ptB^{2}=-p,\hskip 20.00003ptAB=-BA,$

are equivalent to

(6) $a_{1}^{2}+a_{2}a_{3}=-\epsilon,\hskip
30.00005ptb_{1}^{2}+b_{2}b_{3}=-p,\hskip
30.00005pt2a_{1}b_{1}+a_{2}b_{3}+a_{3}b_{2}=0.$

######  Lemma 3.3.

Suppose we have $a,b,c,x,y,z\in\mathbb{Z}$ satisfying

(7) $a^{2}+bc=-\epsilon\mod 128,\hskip 30.00005ptx^{2}+yz=-p\mod 128,\hskip
30.00005pt2ax+bz+cy=0\mod 128.$

Then these are congruent to some
$a_{1},a_{2},a_{3},b_{1},b_{2},b_{3}\in\mathbb{Z}_{2}$ modulo 128
respectively, satisfying equation (6).

###### Proof.

We have 3 equations and 6 variables, so to apply Theorem 3.2 we need to fix 3
variables. For example, if we fixed $(b,c,x)$ and considered the polynomials

$f_{1}(X_{1},X_{2},X_{3})=X_{1}^{2}+bc+\epsilon,\hskip
20.00003ptf_{2}(X_{1},X_{2},X_{3})=x^{2}+X_{2}X_{3}+p,\hskip
20.00003ptf_{3}(X_{1},X_{2},X_{3})=2xX_{1}+bX_{3}+cX_{2}$

then we know that $\mathbf{f}(a,y,z)=0\mod 128$. Note $128=2^{7}$. The
derivative matrix is

$(D\mathbf{f})(X)=\begin{pmatrix}2X_{1}&0&0\\\ 0&X_{3}&X_{2}\\\
2x&c&b\end{pmatrix}.$

In order to lift to a solution
$a_{1},a_{2},a_{3},b_{1},b_{2},b_{3}\in\mathbb{Z}_{2}$, we need $16=2^{4}$ to
not divide

$J_{\mathbf{f}}(a,y,z)=2a(bz-cy).$

Whether this holds depends on the $a,b,c,x,y,z$ we were given. If this does
not hold for our particular $a,b,c,x,y,z$, then we could instead fix some of
the other variables, replacing $\mathbf{f}$ with some $\mathbf{g}$, and check
whether 16 divides the new value of $J_{\mathbf{g}}$. This means that the
proof reduces to an analysis of several cases depending on the parities of the
$a,b,c,x,y,z$.

######  Notation 3.4.

Let $\mathbf{f}_{r,s,t}$ denote the length 3 vector of polynomials in 3
variables obtained by fixing the variables other than
$r,s,t\in\\{a,b,c,x,y,z\\}$. So for example we considered the case
$(r,s,t)=(a,y,z)$ above.

We compute the following Jacobians:

(8) $(D\mathbf{f}_{a,x,b})(X)=\begin{pmatrix}2X_{1}&0&c\\\ 0&2X_{2}&0\\\
2X_{2}&2X_{1}&z\end{pmatrix}\hskip
30.00005ptJ_{\mathbf{f}_{a,x,b}}(a,x,b)=4x(az-cx).$

(9) $(D\mathbf{f}_{a,x,c})(X)=\begin{pmatrix}2X_{1}&0&b\\\ 0&2X_{2}&0\\\
2X_{2}&2X_{1}&y\end{pmatrix}\hskip
30.00005ptJ_{\mathbf{f}_{a,x,c}}(a,x,c)=4x(ay-bx).$

(10) $(D\mathbf{f}_{a,x,y})(X)=\begin{pmatrix}2X_{1}&0&0\\\ 0&2X_{2}&z\\\
2X_{2}&2X_{1}&c\end{pmatrix}\hskip
30.00005ptJ_{\mathbf{f}_{a,x,y}}(a,x,y)=4a(cx-az).$

(11) $(D\mathbf{f}_{a,x,z})(X)=\begin{pmatrix}2X_{1}&0&0\\\ 0&2X_{2}&y\\\
2X_{2}&2X_{1}&b\end{pmatrix}\hskip
30.00005ptJ_{\mathbf{f}_{a,x,z}}(a,x,z)=4a(bx-ay).$

(12) $(D\mathbf{f}_{b,y,z})(X)=\begin{pmatrix}c&0&0\\\ 0&X_{3}&X_{2}\\\
X_{3}&c&X_{1}\end{pmatrix}\hskip 30.00005ptJ_{\mathbf{f}_{b,y,z}}(b,y,z)=c(bz-
cy).$

Now we split into several cases. Firstly, assume $p,\epsilon\neq 2$ are odd.
We will frequently use from equation (7) that $bz+cy$ is divisible by $2ax$
mod 128, and in particular is even.

  1. (i)

$a,x$ both even. From equation (7), we see that $b,c,y,z$ are all odd. But
$4\mid bz+cy$ and so $4\nmid bz-cy$. So using (12), we can lift using the fact
that $16\nmid c(bz-cy)$.

  2. (ii)

$a$ odd and $x$ even. We see that $y,z$ are odd and $bc$ is even. Then use
(10) and the fact that $16\nmid 4a(cx-az)$.

  3. (iii)

$a$ even and $x$ odd. We see that $b,c$ are odd and $yz$ is even. Then use (8)
and the fact that
$16\nmid 4x(az-cx)$.

  4. (iv)

$a,x$ both odd. Then $a^{2}\equiv x^{2}\equiv 1\mod 4$. From the way we
defined $\epsilon$, we have that $p\equiv-\epsilon\mod 4$ (when neither is
equal to 2). By symmetry, suppose $p\equiv 1\mod 4$. Then we see that we must
have $yz\equiv 2\mod 4$. By symmetry, suppose $y$ is odd and $z$ is even but
not divisible by 4. Then since $bz+cy$ is even, we must have that $c$ is even.
If we then have $b$ even, use (11), and $16\nmid 4a(bx-ay)$. If instead $b$ is
odd, then because $4\nmid z$ we know $bz\equiv 2\mod 4$. But $a$ and $x$ are
odd, so $4\nmid 2ax$ and therefore $4\nmid bz+cy$. It follows that $c$ is
divisible by 4. Then we use (10), where $4a(cx-az)$ is divisible by 8 but not
by 16. The other cases are symmetric.

Finally we consider the case when either $p$ or $\epsilon$ is 2 (we cannot
have both). Firstly, consider $\epsilon=2$, so $p\equiv 5\mod 8$.

  1. (i)

$a,x$ both even. We see that $y,z$ are odd. Since $a^{2}+bc=-2\mod 128$ and
$a$ is even, exactly one of $b,c$ is even. But then $2\nmid bz+cy$ is a
contradiction.

  2. (ii)

$a$ odd and $x$ even. We see that $b,c,y,z$ are all odd. We also have from
$2ax\mid bz+cy$ that $4\mid bz+cy$, and therefore $4\nmid bz-cy$. Then use
(12) and the fact that $16\nmid c(bz-cy)$.

  3. (iii)

$a$ even and $x$ odd. We see that $bc$ and $yz$ are even. Because
$a^{2}+bc=-2\mod 128$ and $a$ is even, exactly one of $b,c$ is even.
Similarly, $x^{2}+yz\equiv-1\mod 4$ and $x$ is odd, so exactly one of $y,z$ is
even. We also know that $bz+cy$ is even. Thus either $b,y$ are even and $c,z$
are odd, or $b,y$ are odd and $c,z$ are even. In the first case use (8) and in
the second case use (9).

  4. (iv)

$a,x$ both odd. We see that $b,c$ are odd and $yz$ is even. Again we have that
exactly one of $y,z$ is even. If $y$ is even use (9) and if $z$ is even use
(8).

The only property of $p$ that we use is that $p\equiv 1\mod 4$. If we took
$p=2$, then $\epsilon=1$ is also 1 mod 4. So this case is symmetric to the
above. ∎

The upshot of all this work is the following:

######  Corollary 3.5.

Let $\ell$ be any prime, and let $n_{\ell}$ be any integer at least 2, where
we also ask that $n_{2}\geq 7$. Suppose we can find trace-free matrices
$A_{0},B_{0}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{n_{\ell}}\mathbb{Z})$
satisfying

$A_{0}^{2}=-\epsilon,\hskip 20.00003ptB_{0}^{2}=-p,\hskip
20.00003ptA_{0}B_{0}=-B_{0}A_{0}\mod\ell^{n_{\ell}}.$

Then these lift to matrices $A,B\in\mathrm{M}_{2}(\mathbb{Z}_{\ell})$ with
$A\equiv A_{0}\mod\ell^{n_{\ell}}$ and $B\equiv B_{0}\mod\ell^{n_{\ell}}$ such
that

$A^{2}=-\epsilon,\hskip 20.00003ptB^{2}=-p,\hskip 20.00003ptAB=-BA.$

So suppose we can find for $n_{\ell}\geq 2$, or $n_{2}\geq 7$ (for example by
exhaustion of finitely many matrices in
$\mathrm{M}_{2}(\mathbb{Z}/\ell^{n_{\ell}}\mathbb{Z})$, or working through the
Hensel argument for $\ell\neq 2$) such matrices $A_{0}$ and $B_{0}$ which
satisfy the congruence conditions determined by the basis of $\mathcal{O}$. In
other words, if we mapped $i\mapsto A_{0}$ and $j\mapsto B_{0}$, then the
induced map on $s^{1},s^{2},s^{3},s^{4}$ sends them to well defined matrices
modulo $\ell^{n_{\ell}-2}$ (the 2 accounts for denominators when writing the
$s^{1},s^{2},s^{3},s^{4}$ in terms of $i,j$ \- see below). Then $A_{0}$ and
$B_{0}$ lift to $A,B\in\mathrm{M}_{2}(\mathbb{Z}_{\ell})$ such that the map
determined by $i\mapsto A$ and $j\mapsto B$ gives an isomorphism
$\mathcal{O}\otimes\mathbb{Z}_{\ell}\cong\mathrm{M}_{2}(\mathbb{Z}_{\ell})$.

######  Remark 3.6.

The following Proposition in Pizer’s paper [Piz80] (Proposition 5.2) gives
explicit $\mathbb{Z}$-bases for a maximal order of our quaternion algebra $D$.
We see in particular that the only primes dividing a denominator are 2 and $r$
(when $p\equiv 1\mod 8$ and $\epsilon=r$), with power at most $2^{2}$ and $r$.

######  Proposition 3.7.

A maximal order of $D$ is given by the $\mathbb{Z}$-basis:

$\displaystyle\frac{1}{2}(1+i+j+ij),i,j,ij$ $\displaystyle\text{ if }p=2$
$\displaystyle\frac{1}{2}(1+j),\frac{1}{2}(i+ij),j,ij$ $\displaystyle\text{ if
}p\equiv 3\mod 4$ $\displaystyle\frac{1}{2}(1+j+ij),\frac{1}{4}(i+2j+ij),j,ij$
$\displaystyle\text{ if }p\equiv 5\mod 8$
$\displaystyle\frac{1}{2}(1+j),\frac{1}{2}(i+ij),\frac{1}{r}(j+a\cdot ij),ij$
$\displaystyle\text{ if }p\equiv 1\mod 8$

where $a$ is some integer such that $r\mid a^{2}p+1$.

This means we can explicitly write down the congruences we want our matrices
$A_{0}$ and $B_{0}$ in the above Corollary to satisfy. We know that these
matrices exist for $\ell\neq p$ by the ramification properties of the
quaternion algebra $D$.

######  Condition 3.8.

We want to find matrices
$A_{0},B_{0}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{n_{\ell}}\mathbb{Z})$, for
$n_{\ell}\geq 2$ and $n_{2}\geq 7$ satisfying

$A_{0}^{2}=-\epsilon,\hskip 20.00003ptB_{0}^{2}=-p,\hskip
20.00003ptA_{0}B_{0}=-B_{0}A_{0}\mod\ell^{n_{\ell}},$

and also

$\displaystyle 2\mid 1+A_{0}+B_{0}+A_{0}B_{0}$ $\displaystyle\text{ if }p=2$
$\displaystyle 2\mid 1+B_{0},\hskip 10.00002pt2\mid A_{0}+A_{0}B_{0}$
$\displaystyle\text{ if }p\equiv 3\mod 4$ $\displaystyle 2\mid
1+B_{0}+A_{0}B_{0},\hskip 10.00002pt4\mid A_{0}+2B_{0}+A_{0}B_{0}$
$\displaystyle\text{ if }p\equiv 5\mod 8$ $\displaystyle 2\mid 1+B_{0},\hskip
10.00002pt2\mid A_{0}+A_{0}B_{0},\hskip 10.00002ptr\mid B_{0}+a\cdot
A_{0}B_{0}$ $\displaystyle\text{ if }p\equiv 1\mod 8$

where we remind ourselves that when $p\equiv 1\mod 8$, we need $\epsilon=r$ is
a prime congruent to $3\mod 4$ with $\left(\frac{r}{p}\right)=-1$, and $a$ is
some integer such that $r\mid a^{2}p+1$, which we choose in writing down the
basis in Proposition 3.7. Note that these last four congruences are vacuous
unless $\ell=2$ or $r$.

##  4\. Weight 0 mod $p^{2}-1$ and level 1, for general $p$

We now work with any prime $p$. Let $D$ be the unique quaternion algebra over
$\mathbb{Q}$ ramified exactly at $\\{p,\infty\\}$ and let $\Omega:=U\backslash
D^{\times}(\mathbb{A}_{f})/D^{\times}(\mathbb{Q})$, where
$U:=\mathcal{O}_{p}^{\times}\times\prod\limits_{l\neq
p}\mathcal{O}_{\ell}^{\times}$. We will compute the Hecke operator
$T_{\ell_{0}}$ on $\Omega$, which will give us the weight $0\mod p^{2}-1$
eigenvalues on $\Omega(1)$. The argument in the example above largely
generalises to this case.

We explain part of this using the matrices of the previous section. Suppose we
had some $w^{i}=[w_{2}^{i},w_{3}^{i},\dots]\in\Omega$ and
$w^{j}=[w_{2}^{j},w_{3}^{j},\dots]\in\Omega$ corresponding to left ideal
classes of $\mathcal{O}$ (so almost all $w_{\ell}^{i},w_{\ell}^{j}$ can be
taken to be 1), and we wanted to know if $g_{k}\cdot w^{j}=w^{i}\in\Omega$,
for some $g_{k}$ appearing in $T_{\ell_{0}}$. Denote by $\mathcal{J}$ the left
$\mathcal{O}$-ideal with local generators
$\\{w_{2}^{j},w_{3}^{j},\dots,g_{k}\cdot w_{\ell_{0}}^{j},\dots\\}$, where we
view $g_{k}\in\mathrm{M}_{2}(\mathbb{Z}_{\ell_{0}})$ as an element of
$\mathcal{O}\otimes\mathbb{Z}_{\ell_{0}}$. Denote by $\mathcal{I}$ the left
$\mathcal{O}$-ideal with local generators $\\{w_{2}^{i},w_{3}^{i},\dots\\}$.
Then we need to check whether there exists $\alpha\in D^{\times}(\mathbb{Q})$
such that $\mathcal{J}=\mathcal{I}\alpha$ (the question of determining when
two $\mathcal{O}$-ideals are in the same ideal class, for $\mathcal{O}$ an
Eichler order, has been studied in [KV12], but in our case we have local
generators for the ideals, meaning that a basis for an ideal is not obvious).
This means that for all $\ell\neq\ell_{0}$, we require

(13)
$w_{\ell}^{i}\alpha(w_{\ell}^{j})^{-1}\in(\mathcal{O}\otimes\mathbb{Z}_{\ell})^{\times}$

and also

(14)
$w_{\ell_{0}}^{i}\alpha(w_{\ell_{0}}^{j})^{-1}g_{k}^{-1}\in(\mathcal{O}\otimes\mathbb{Z}_{\ell_{0}})^{\times}.$

We deduce the following conditions on $\alpha$: let $\mathcal{V}_{i,j}$ be the
set of primes $\ell$ at which at least one of $w_{\ell}^{i}$ and
$w_{\ell}^{j}$ is not 1, throwing out $p$ and $\ell_{0}$. For all $\ell$, we
temporarily define
$m_{\ell}=\mathrm{max}(\mathrm{nrd}(w_{\ell}^{i}),\mathrm{nrd}(w_{\ell}^{j}))$.
Then for all $\ell\not\in\mathcal{V}_{i,j}\cup\\{p,\ell_{0}\\}$, equation (13)
is equivalent to

(15) $\alpha\in(\mathcal{O}\otimes\mathbb{Z}_{\ell})^{\times}\hskip
20.00003pt\ell\not\in\mathcal{V}_{i,j}\cup\\{p,\ell_{0}\\}.$

For $\ell=p$, because $D$ is ramified at $p$, equation (13) is equivalent to

(16)
$v_{p}(\mathrm{nrd}(\alpha))=v_{p}(\mathrm{nrd}(w_{\ell}^{j}))-v_{p}(\mathrm{nrd}(w_{\ell}^{i})),$

where $v_{p}$ denotes the usual $p$-adic valuation on $\mathbb{Z}$. For
$\ell\in\mathcal{V}_{i,j}$, equation (13) tells us that

(17)
$v_{\ell}(\mathrm{nrd}(\alpha))=v_{\ell}(\mathrm{nrd}(w_{\ell}^{j}))-v_{\ell}(\mathrm{nrd}(w_{\ell}^{i}))\hskip
20.00003pt\ell\in\mathcal{V}_{i,j}.$

Additionally, since
$\alpha\in(w_{\ell}^{i})^{-1}\cdot(\mathcal{O}\otimes\mathbb{Z}_{\ell})^{\times}\cdot
w_{\ell}^{j}$, and because $\mathrm{nrd}(w_{\ell}^{i})$ has $\ell$-adic
valuation at most $m_{\ell}$ by definition, we see that

(18)
$\ell^{m_{\ell}}\alpha\in\mathcal{O}\otimes\mathbb{Z}_{\ell}\cong\mathrm{M}_{2}(\mathbb{Z}_{\ell})\hskip
20.00003pt\ell\in\mathcal{V}_{i,j}.$

A similar argument using equation (14) shows that

(19)
$v_{\ell_{0}}(\mathrm{nrd}(\alpha))=v_{\ell_{0}}(\mathrm{nrd}(w_{\ell_{0}}^{j}))-v_{\ell}(\mathrm{nrd}(w_{\ell_{0}}^{i}))+1$

and

(20)
$\ell_{0}^{m_{\ell_{0}}+1}\alpha\in\mathcal{O}\otimes\mathbb{Z}_{\ell_{0}}\cong\mathrm{M}_{2}(\mathbb{Z}_{\ell_{0}}).$

Combining equations (15) to (20), we see that we can compute rational numbers

$M=\ell_{0}\prod\limits_{\ell\in\mathcal{V}_{i,j}\cup\\{p,\ell_{0}\\}}\ell^{m_{\ell}}$

and

$K=\ell_{0}\prod\limits_{l\in\mathcal{V}_{i,j}\cup\\{p,\ell_{0}\\}}\ell^{v_{\ell}(\mathrm{nrd}(w_{\ell}^{j}))-v_{\ell}(\mathrm{nrd}(w_{\ell}^{i}))}$

such that

$M\alpha\in\mathcal{O}\hskip 20.00003pt\text{and}\hskip
20.00003pt\mathrm{nrd}(\alpha)=K.$

Note that we can rewrite, for $\ell\neq p,\ell_{0}$, the condition
$w_{\ell}^{i}\alpha(w_{\ell}^{j})^{-1}\in\mathcal{O}\otimes\mathbb{Z}_{\ell}$
(being a unit is then guaranteed by the norm condition) as saying

$w_{\ell}^{i}\cdot
M\alpha\cdot\overline{w_{\ell}^{j}}\in\ell^{m_{\ell}+v_{\ell}(\mathrm{nrd}(w_{\ell}^{j}))}\mathcal{O}\otimes\mathbb{Z}_{\ell},$

where $\overline{w_{\ell}^{j}}$ denotes the standard involution in
$D\otimes\mathbb{Q}_{\ell}$. We can do the same for $\ell_{0}$, using
$\overline{g_{k}}=\mathrm{adj}(g_{k})$ the adjugate matrix of $g_{k}$, which
gives an extra factor of $\ell_{0}$. Since
$m_{\ell}+v_{\ell}(\mathrm{nrd}(w_{\ell}^{j}))\leq 2m_{\ell}$, to check this
condition we only really need $w_{\ell}^{i}$, $M\alpha$ and $w_{\ell}^{j}$
modulo $\ell^{2m_{\ell}}$. Similarly, we only really need $w_{\ell_{0}}^{i}$,
$M\alpha$ and $w_{\ell_{0}}^{j}$ modulo $\ell_{0}^{2m_{\ell_{0}}+2}$. This
means we can make use of the matrices computed in the previous section to
rephrase our conditions on $\alpha$. Let $s^{1},s^{2},s^{3},s^{4}$ be an
integer basis for $\mathcal{O}$, taking for instance the basis of Proposition
3.7. Since $M\alpha\in\mathcal{O}$, we can write

$M\alpha=t\cdot s^{1}+x\cdot s^{2}+y\cdot s^{3}+z\cdot s^{4}$

for variables $t,x,y,z$ which are to take values in $\mathbb{Z}$. Let $\ell$
be a prime in $\mathcal{V}_{i,j}\cup\\{\ell_{0}\\}$. We can identify
$M\alpha\mod\ell^{2m_{\ell}+2}$ with a matrix
$\begin{pmatrix}a_{\ell}&b_{\ell}\\\
c_{\ell}&-a_{\ell}\end{pmatrix}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{2m_{\ell}+2}\mathbb{Z})$,
where $a_{\ell},b_{\ell},c_{\ell}$ are
$(\mathbb{Z}/\ell^{2m_{\ell}+2}\mathbb{Z})$-linear functions in $t,x,y,z$
which can be computed. We can also, for any $\ell\neq p$, identify
$w_{\ell}^{i}$ and $w_{\ell}^{j}$ with matrices
$W_{\ell}^{i},W_{\ell}^{j}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{2m_{\ell}+2}\mathbb{Z})$.

We have that $g_{k}\cdot w^{j}=w^{i}\in\Omega$ if and only if we can find some
$t,x,y,z\in\mathbb{Z}$ such that the following conditions hold:

(21) $\begin{dcases*}\mathrm{nrd}(M\alpha)=KM^{2}\\\
W_{\ell}^{i}\cdot\begin{pmatrix}a_{\ell}&b_{\ell}\\\
c_{\ell}&-a_{\ell}\end{pmatrix}\cdot\mathrm{adj}(W_{\ell}^{j})\in\ell^{m_{\ell}+v_{\ell}(\det(W_{\ell}^{j}))}\cdot\mathrm{M}_{2}(\mathbb{Z}/\ell^{2m_{\ell}+2}\mathbb{Z})\hskip
30.00005pt\text{ for $\ell\in\mathcal{V}_{i,j}$}\\\
W_{\ell_{0}}^{i}\cdot\begin{pmatrix}a_{\ell_{0}}&b_{\ell_{0}}\\\
c_{\ell_{0}}&-a_{\ell_{0}}\end{pmatrix}\cdot\mathrm{adj}(W_{\ell_{0}}^{j})\cdot\mathrm{adj}(g_{k})\in\ell_{0}^{m_{\ell_{0}}+v_{\ell_{0}}(\det(W_{\ell_{0}}^{j}))+2}\cdot\mathrm{M}_{2}(\mathbb{Z}/\ell_{0}^{2m_{\ell_{0}}+2}\mathbb{Z}).\end{dcases*}$

The first condition tells us that $t,x,y,z\in\mathbb{Z}$ satisfy some
quadratic equation. Because the reduced norm is a positive definite quadratic
form in the $t,x,y,z$ (due to ramification at $\infty$), this means that there
are only finitely many solutions to the quadratic equation. We can then
enumerate them (for example, diagonalising the quadratic form, computing the
finitely many solutions with the new basis, and then solving for $t,x,y,z$).
Once we do so, it remains to check whether they satisfy the last two
conditions of (21). By expanding them out, these conditions can be interpreted
as congruence conditions on $t,x,y,z$ modulo $\ell^{2m_{\ell}+2}$ for
$\ell\in\mathcal{V}_{i,j}\cup\\{\ell_{0}\\}$, or more precisely modulo
$\ell^{m_{\ell}+v_{\ell}(\det(W_{\ell}^{j}))}$ and
$\ell_{0}^{m_{\ell_{0}}+v_{\ell_{0}}(\det(W_{\ell_{0}}^{j}))+2}$. This allows
us to determine whether $g_{k}\cdot w^{j}=w^{i}\in\Omega$, and hence compute a
matrix representative for the Hecke operator $T_{\ell_{0}}$. We are now ready
to present the algorithm. This should be read in conjunction with the
following Table of Notation. The column for ’Corresponding Matrices’ refers to
matrices generated using the methods of Section 3.

Table of Notation

Notation |  Definition |  Corresponding Matrices
---|---|---
$D=\left(\frac{-\epsilon,-p}{\mathbb{Q}}\right)$ |  Quaternion algebra ramified at $\\{p,\infty\\}$. |
$\mathcal{O}$ |  A maximal order of $D$. |
$I_{1},\dots,I_{h}$ |  Representatives of the left ideal classes of $\mathcal{O}$. |
$\mathcal{B}_{1},\dots,\mathcal{B}_{h}$ |  $\mathbb{Z}$-bases for $I_{1},\dots,I_{h}$. |
$\mathcal{V}$ |  The set of primes $\ell$ for which in some $\mathcal{B}_{j}$ all elements have reduced norm divisible by $\ell$, excluding $p$ and including $\ell_{0}$. |
$i,j$ |  Generators for $D$. |  $A_{\ell},B_{\ell}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{n_{\ell}}\mathbb{Z})$ for each $\ell\in\mathcal{V}$.
$\\{s^{1},s^{2},s^{3},s^{4}\\}$ |  A $\mathbb{Z}$-basis for $\mathcal{O}$. |  $S^{1}_{\ell},S_{\ell}^{2},S_{\ell}^{3},S_{\ell}^{4}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{2m_{\ell}+2}\mathbb{Z})$ for each $\ell\in\mathcal{V}$.
$w^{j}=[w_{2}^{j},w_{3}^{j},w_{5}^{j},\dots]\in\Omega$ |  The elements of $\Omega$ corresponding to the $I_{j}$. The square brackets means the double coset represented by the adelic point $(w_{2}^{j},w_{3}^{j},\dots)$. From the way we compute this, almost all $w_{\ell}^{j}$ will be 1. |  $W_{\ell}^{j}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{2m_{\ell}+2}\mathbb{Z})$ corresponding to the $w_{\ell}^{j}$ for each $\ell\in\mathcal{V}$.
$m_{\ell}$, $n_{\ell}=2m_{\ell}+4$ for $\ell\neq 2$, and $n_{2}=\max(7,2m_{2}+4)$ |  $m_{\ell}:=\max\limits_{j}(v_{\ell}(\mathrm{nrd}(w_{\ell}^{j})))$. |
$g_{0},\dots,g_{\ell_{0}}\in\mathrm{M}_{2}(\mathbb{Z}_{\ell_{0}})$ |  The matrices $\begin{pmatrix}1&0\\\ 0&\ell_{0}\end{pmatrix},\begin{pmatrix}1&1\\\ 0&\ell_{0}\end{pmatrix},\dots,$ $\begin{pmatrix}1&\ell_{0}-1\\\ 0&\ell_{0}\end{pmatrix},\begin{pmatrix}\ell_{0}&0\\\ 0&1\end{pmatrix}$. |
$\mathbbm{1}_{w^{j}}$ |  The characteristic function $\Omega\to\overline{\mathbb{F}}_{p}$ of the point $w^{j}\in\Omega$. |
$e_{i,j,k}\in\\{0,1\\}$ |  $e_{i,j,k}=\mathbbm{1}_{w^{i}}(g_{k}\cdot w^{j})$ for $1\leq i,j\leq h$ and $0\leq k\leq\ell_{0}$. The multiplication $g_{k}\cdot w^{j}$ means $[w_{2}^{j},w_{3}^{j},\dots,g_{k}\cdot w_{\ell_{0}}^{j},\dots]$, with multiplication occuring only in the $\ell_{0}$-th place. |
$\mathcal{V}_{i,j}\subset\mathcal{V}$ |  The set of primes $\ell$ such that at least one of $w_{\ell}^{i}$ and $w_{\ell}^{j}$ is not 1, excluding $p$ and $\ell_{0}$. |

######  Algorithm 4.1.

Input: distinct primes $p$ and $\ell_{0}$.

Output: a matrix representing the action of the Hecke operator $T_{\ell_{0}}$
on the space of all functions $\Omega\to\overline{\mathbb{F}}_{p}$.

  1. (i)

Define a quaternion algebra $D=\left(\frac{-\epsilon,-p}{\mathbb{Q}}\right)$
over $\mathbb{Q}$, ramified exactly at $\\{p,\infty\\}$. Define a maximal
order $\mathcal{O}$ with integer basis given as in Proposition 3.7, for which
we denote the basis elements $\\{s^{1},s^{2},s^{3},s^{4}\\}$. Compute the left
ideal classes $I_{1},\dots,I_{h}$ of $\mathcal{O}$, and bases
$\mathcal{B}_{1},\dots,\mathcal{B}_{h}$ for them.

  2. (ii)

Compute the points $w^{j}=[w_{2}^{j},w_{3}^{j},w_{5}^{j},\dots]\in\Omega$
corresponding to $I_{j}$ for each $j$ as follows. We take $w_{\ell}^{j}$ to be
any generator of $I_{j}\otimes\mathbb{Z}_{\ell}$ (which we know is principal).
To do this, for our basis $\mathcal{B}_{j}$, compute the reduced norm of each
of the four elements and set $w_{\ell}^{j}$ to be any of these elements whose
reduced norm has minimal $\ell$-adic valuation. Note that for almost all
$\ell$ this valuation is zero, so we can instead take $w_{\ell}^{j}=1$, and do
so when possible.

  3. (iii)

Determine the set $\mathcal{V}$, defined in the Table of Notation. For each
$\ell\in\mathcal{V}\cup\\{p\\}$, compute $m_{\ell}$ and $n_{\ell}$. For each
$\ell\in\mathcal{V}$, compute matrices
$A_{\ell},B_{\ell}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{n_{\ell}}\mathbb{Z})$
satisfying Condition 3.8. Using these, compute matrices corresponding to the
$s^{1},s^{2},s^{3},s^{4}$, which in any case are well defined modulo
$\ell^{2m_{\ell}+2}$. Denote these by
$S_{\ell}^{i}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{2m_{\ell}+2}\mathbb{Z})$ for
each $\ell\in\mathcal{V}$. By expressing each $w_{\ell}^{j}\in\mathcal{B}_{j}$
as a $\mathbb{Z}$-linear combination of $s^{1},s^{2},s^{3},s^{4}$, we can
compute matrices
$W_{\ell}^{j}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{2m_{\ell}+2}\mathbb{Z})$
corresponding to the $w_{\ell}^{j}$.

######  Remark 4.2.

So far we have only mentioned $\ell_{0}$ as that it needed to be added to
$\mathcal{V}$. If one wanted to compute several Hecke operators at once, they
could add all the primes for the operators into $\mathcal{V}$. Then in the
above steps we computed all the relevant matrices, to save us repeating the
calculations if we were to compute the Hecke operators one by one.

  4. (iv)

Let $\mathbbm{1}_{w^{1}},\dots,\mathbbm{1}_{w^{h}}$ be the characteristic
functions of the points $w^{1},\dots,w^{h}\in\Omega$. This is a basis for the
vector space of $\overline{\mathbb{F}}_{p}$-valued functions on $\Omega$. Let
$g_{0},\dots,g_{\ell_{0}-1},g_{\ell_{0}}\in\mathrm{M}_{2}(\mathbb{Z}_{\ell_{0}})$
be the matrices
$\begin{pmatrix}1&0\\\ 0&\ell_{0}\end{pmatrix},\begin{pmatrix}1&1\\\
0&\ell_{0}\end{pmatrix},\dots,\begin{pmatrix}1&\ell_{0}-1\\\
0&\ell_{0}\end{pmatrix},\begin{pmatrix}\ell_{0}&0\\\ 0&1\end{pmatrix}$. Define
the quantity $e_{i,j,k}$ for $1\leq i,j\leq h$ and $0\leq k\leq\ell_{0}$ by

$e_{i,j,k}=\mathbbm{1}_{w^{i}}(g_{k}\cdot w^{j}).$

Then by definition we have the formula

$T_{\ell_{0}}(\mathbbm{1}_{w^{i}})(w^{j})=\frac{1}{\ell_{0}}\cdot\sum\limits_{k=0}^{\ell_{0}}e_{i,j,k}.$

This is then the $(j,i)$-th entry of the matrix for $T_{\ell_{0}}$ with
respect to the basis $\\{\mathbbm{1}_{w^{1}},\dots,\mathbbm{1}_{w^{h}}\\}$.
Hence it remains to compute this quantity $e_{i,j,k}$.

  5. (v)

Fix $i,j$. Determine the set $\mathcal{V}_{i,j}$. Compute the quantities

$M=\ell_{0}\prod\limits_{\ell\in\mathcal{V}_{i,j}\cup\\{p,\ell_{0}\\}}\ell^{m_{\ell}}$

and

$K=\ell_{0}\prod\limits_{\ell\in\mathcal{V}_{i,j}\cup\\{p,\ell_{0}\\}}\ell^{v_{\ell}(\mathrm{nrd}(w_{\ell}^{j}))-v_{\ell}(\mathrm{nrd}(w_{\ell}^{i}))}.$

  6. (vi)

Check if there exist integers $t,x,y,z\in\mathbb{Z}$ such that the following
conditions hold:

$\begin{dcases*}\mathrm{nrd}(t\cdot s^{1}+x\cdot s^{2}+y\cdot s^{3}+z\cdot
s^{4})=KM^{2}\\\ W_{\ell}^{i}\cdot\begin{pmatrix}a_{\ell}&b_{\ell}\\\
c_{\ell}&-a_{\ell}\end{pmatrix}\cdot\mathrm{adj}(W_{\ell}^{j})\in\ell^{m_{\ell}+v_{\ell}(\det(W_{\ell}^{j}))}\cdot\mathrm{M}_{2}(\mathbb{Z}/\ell^{2m_{\ell}+2}\mathbb{Z})\hskip
30.00005pt\text{ for $\ell\in\mathcal{V}_{i,j}$}\\\
W_{\ell_{0}}^{i}\cdot\begin{pmatrix}a_{\ell_{0}}&b_{\ell_{0}}\\\
c_{\ell_{0}}&-a_{\ell_{0}}\end{pmatrix}\cdot\mathrm{adj}(W_{\ell_{0}}^{j})\cdot\mathrm{adj}(g_{k})\in\ell_{0}^{m_{\ell_{0}}+v_{\ell_{0}}(\det(W_{\ell_{0}}^{j}))+2}\cdot\mathrm{M}_{2}(\mathbb{Z}/\ell_{0}^{2m_{\ell_{0}}+2}\mathbb{Z}).\end{dcases*}$

where $\begin{pmatrix}a_{\ell}&b_{\ell}\\\
c_{\ell}&-a_{\ell}\end{pmatrix}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{2m_{\ell}+2}\mathbb{Z})$
is the matrix corresponding to $t\cdot s^{1}+x\cdot s^{2}+y\cdot s^{3}+z\cdot
s^{4}$. If such $t,x,y,z$ exist, set $e_{i,j,k}$ to be 1, and otherwise 0.
Note that the only dependence on $k$ is in the last condition.

##  5\. Introducing weight and level

We now discuss what modifications must be done when computing the Hecke
eigenvalues mod $p$ of general weight and level on the quaternion side. In the
previous section we checked whether two elements of $\Omega$ are the same by
checking if they determine isomorphic invertible left $\mathcal{O}$-ideals.
The point is that if we now attach $\pi N$-structure to our ideals, we need to
determine whether this isomorphism sends one $\pi N$-structure to the other.
Our aim is to compute the Hecke operators $T_{\ell_{0}}$, for $\ell_{0}\nmid
pN$, on the space of functions $\Omega(N)=U(N)\backslash
D^{\times}(\mathbb{A}_{f})/D^{\times}(\mathbb{Q})\to\overline{\mathbb{F}}_{p}$.
If we wanted to isolate the Hecke eigenvalues arising from weight $k\mod
p^{2}-1$, then we need to restrict to the functions which satisfy
$f(\mu\cdot[x_{\ell}])=\mu^{-k}f([x_{\ell}])$, where
$\mu\in\mathcal{O}_{p}^{\times}/\mathcal{O}_{p}^{\times}(1)\cong\mathbb{F}_{p^{2}}^{\times}$
acts on $[x_{\ell}]$ by multiplication in the $p$-place. In our case, we can
identify
$\mathcal{O}_{p}^{\times}/\mathcal{O}_{p}^{\times}(1)\cong\mathbb{F}_{p^{2}}^{\times}$
with $\\{s+ti\mid s,t\in\mathbb{F}_{p}\text{ not both zero}\\}$, which is
closed under multiplication, where $i$ and $j$ are the generators of $D$ ($j$
can be viewed as a uniformiser $\pi$ of $\mathcal{O}_{p}^{\times}$).

Firstly, we write down the elements of $\Omega(N)$. For $U$ defined as
$\mathcal{O}_{p}^{\times}\times\prod\limits_{\ell\neq
p}\mathcal{O}_{\ell}^{\times}$ previously, we have

$U/U(N)\cong\mathbb{F}_{p^{2}}^{\times}\times\prod\limits_{\ell\neq
p}\mathrm{GL}_{2}(\mathbb{Z}/\ell^{v_{\ell}(N)}\mathbb{Z})\cong\mathbb{F}_{p^{2}}^{\times}\times\mathrm{GL}_{2}(\mathbb{Z}/N\mathbb{Z}).$

Hence, for our points $w^{1},\dots,w^{h}$ of $\Omega$, we need to multiply on
the left by representatives of $\mathbb{F}_{p^{2}}^{\times}$ and
$\mathrm{GL}_{2}(\mathbb{Z}/N\mathbb{Z})$ at the appropriate places, in order
to determine all the elements of $\Omega(N)$. One then arrives at the set of
points $v_{\mu,\gamma}^{j}\in\Omega(N)$, running over $1\leq j\leq h$,
$\mu\in\mathbb{F}_{p^{2}}^{\times}$ and
$\gamma\in\mathrm{GL}_{2}(\mathbb{Z}/N\mathbb{Z})$, and these are all the
points of $\Omega(N)$. This is defined in the Updated Table of Notation on the
following page. Relevant changes from the notation in the previous section are
in bold. Note that $v_{\mu,\gamma}^{j}$ reduces to $w^{j}$ when we quotient by
$U$ in $\Omega=U\backslash\Omega(N)$.

Once again, an obvious choice of basis for functions
$\Omega(N)\to\overline{\mathbb{F}}_{p}$ is given by the characteristic
functions $\mathbbm{1}_{v_{\mu,\gamma}^{j}}$. One is then led to computing the
following quantity:

$e_{(i,\mu,\gamma),(j,\mu^{\prime},\gamma^{\prime}),k}=\mathbbm{1}_{v_{\mu,\gamma}^{i}}(g_{k}\cdot
v_{\mu^{\prime},\gamma^{\prime}}^{j})$

for $1\leq i,j\leq h$, $0\leq k\leq\ell_{0}$,
$\mu,\mu^{\prime}\in\mathbb{F}_{p^{2}}^{\times}$ and
$\gamma,\gamma^{\prime}\in\mathrm{GL}_{2}(\mathbb{Z}/N\mathbb{Z})$. Then we
have the formula

$T_{\ell_{0}}(\mathbbm{1}_{v_{\mu,\gamma}^{i}})(v_{\mu^{\prime},\gamma^{\prime}}^{j})=\frac{1}{\ell_{0}}\cdot\sum\limits_{k=0}^{\ell_{0}}e_{(i,\mu,\gamma),(j,\mu^{\prime},\gamma^{\prime}),k}.$

If we index the rows and columns of the matrix for $T_{\ell_{0}}$, with
respect to this basis, by triples $(i,\mu,\gamma)$, then the
$((j,\mu^{\prime},\gamma^{\prime}),(i,\mu,\gamma))$-th entry is this value
above. We observe that
$e_{(i,\mu,\gamma),(j,\mu^{\prime},\gamma^{\prime}),k}=0$ if $e_{i,j,k}=0$,
for $e_{i,j,k}$ as defined in step (iv) in Algorithm 4.1. This is because if
$v_{\mu,\gamma}^{i}=g_{k}\cdot
v_{\mu^{\prime},\gamma^{\prime}}^{j}\in\Omega(N)$, then they generate left
$\mathcal{O}$-ideals with $\pi N$-structure that are isomorphic; in particular
the ideals are isomorphic, and so $w^{i}=g_{k}\cdot w^{j}$. One can think of
this as replacing $e_{i,j,k}$ in Algorithm 4.1 with a permutation matrix,
depending on $i,j,k$, permuting the pairs $(\mu,\gamma)$.

So now we see how to compute
$e_{(i,\mu,\gamma),(j,\mu^{\prime},\gamma^{\prime}),k}$. It is 0 if
$e_{i,j,k}=0$. If $e_{i,j,k}=1$, then from Algorithm 4.1 we compute some
$\alpha\in D^{\times}(\mathbb{Q})$ such that for all $\ell\neq\ell_{0}$,

$w_{\ell}^{i}\alpha(w_{\ell}^{j})^{-1}\in(\mathcal{O}\otimes\mathbb{Z}_{\ell})^{\times},$

and also

$w_{\ell_{0}}^{i}\alpha(w_{\ell_{0}}^{j})^{-1}g_{k}^{-1}\in(\mathcal{O}\otimes\mathbb{Z}_{\ell_{0}})^{\times}.$

What we need to check now is whether we also have

(22) $\mu\cdot
w_{p}^{i}\cdot\alpha\cdot(w_{p}^{j})^{-1}\cdot(\mu^{\prime})^{-1}\in\mathcal{O}_{p}^{\times}(1)$

and for $\ell\mid N$

(23) $\gamma_{\ell}\cdot
w_{\ell}^{i}\cdot\alpha\cdot(w_{\ell}^{j})^{-1}\cdot(\gamma^{\prime}_{\ell})^{-1}\in\mathcal{O}_{\ell}^{\times}(N).$

In other words, we need to compute
$w_{p}^{i}\cdot\alpha\cdot(w_{p}^{j})^{-1}$, which we know is in
$\mathcal{O}_{p}^{\times}$ by definition of $\alpha$, and then check if this
reduces to $\mu^{-1}\mu^{\prime}\in\mathbb{F}_{p^{2}}^{\times}$ modulo the
uniformiser $\pi=j$. We also need to compute for each $\ell\mid N$ the terms
$w_{\ell}^{i}\cdot\alpha\cdot(w_{\ell}^{j})^{-1}$, which we know are in
$\mathcal{O}_{\ell}^{\times}$, and then check whether they reduce to
$\gamma_{\ell}^{-1}\gamma^{\prime}_{\ell}\in\mathrm{GL}_{2}(\mathbb{Z}/\ell^{v_{\ell}(N)}\mathbb{Z})$
modulo $\ell^{v_{\ell}(N)}$. To make sense of this, we need to write down
matrices at the primes dividing $N$ as well, so we extend our set
$\mathcal{V}$ in the Updated Table of Notation.

We are now ready to write out the algorithm for the general case.

Updated Table of Notation

Notation |  Definition |  Corresponding Matrices
---|---|---
$\mathcal{V}$ |  The set of primes $\ell$ for which in some $\mathcal{B}_{j}$ all elements have reduced norm divisible by $\ell$, excluding $p$, and including $\ell_{0}$ and all primes dividing $N$. |
$i,j$ |  |  $A_{\ell},B_{\ell}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{n_{\ell}}\mathbb{Z})$ for each $\ell\in\mathcal{V}$.
$\\{s^{1},s^{2},s^{3},s^{4}\\}$ |  |  $S^{1}_{\ell},S_{\ell}^{2},S_{\ell}^{3},S_{\ell}^{4}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{2m_{\ell}\mathbf{+v_{\ell}(N)}+2}\mathbb{Z})$ for each $\ell\in\mathcal{V}$.
$w^{j}=[w_{2}^{j},w_{3}^{j},w_{5}^{j},\dots]\in\Omega$ |  The elements of $\Omega$ corresponding to the $I_{j}$. The square brackets means the double coset represented by the adelic point $(w_{2}^{j},w_{3}^{j},\dots)$. From the way we compute this, almost all $w_{\ell}^{j}$ will be 1. |  $W_{\ell}^{j}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{2m_{\ell}\mathbf{+v_{\ell}(N)}+2}\mathbb{Z})$ corresponding to the $w_{\ell}^{j}$ for each $\ell\in\mathcal{V}$.
$v_{\ell}(N)$ |  The $\ell$-adic valuation of $N$. |
$m_{\ell}$, $n_{\ell}=2m_{\ell}\mathbf{+v_{\ell}(N)}+4$ for $\ell\neq 2$, and $n_{2}=\max(7,2m_{2}+\mathbf{v_{2}(N)}+4)$ |  $m_{\ell}:=\max\limits_{j}(v_{\ell}(\mathrm{nrd}(w_{\ell}^{j})))$. |
$\mathcal{O}_{p}^{\times}/\mathcal{O}_{p}^{\times}(1)\cong\mathbb{F}_{p^{2}}^{\times}$ |  Identified with ${\\{s+ti\mid s,t\in\mathbb{F}_{p}\text{ not both zero}\\}}$. |
$v_{\mu,\gamma}^{j}=[v_{2,\mu,\gamma}^{j},v_{3,\mu,\gamma}^{j},\dots]\in\Omega(N)$ |  Where $v_{\ell,\mu,\gamma}^{j}=\begin{dcases*}w_{\ell}^{j}&if $\ell\neq p\text{ and }\ell\nmid N$\\\ \mu\cdot w_{p}^{j}&if $\ell=p$\\\ \gamma_{\ell}\cdot w_{\ell}^{j}&if $\ell\mid N$\end{dcases*}$ for $\mu\in\mathbb{F}_{p^{2}}^{\times}$ and $\gamma\in\mathrm{GL}_{2}(\mathbb{Z}/N\mathbb{Z})$ with reduction $\gamma_{\ell}$ mod $\ell^{v_{\ell}(N)}$. To be precise, we should choose lifts of $\mu$ to $\mathcal{O}_{p}^{\times}$ and $\gamma_{\ell}$ to $\mathcal{O}_{\ell}^{\times}\cong\mathrm{GL}_{2}(\mathbb{Z}_{\ell})$. |
$\mathbbm{1}_{v_{\mu,\gamma}^{j}}$ |  The characteristic function $\Omega(N)\to\overline{\mathbb{F}}_{p}$ of the point $v_{\mu,\gamma}^{j}\in\Omega(N)$. |
$e_{(i,\mu,\gamma),(j,\mu^{\prime},\gamma^{\prime}),k}\in\\{0,1\\}$ |  $e_{(i,\mu,\gamma),(j,\mu^{\prime},\gamma^{\prime}),k}=\mathbbm{1}_{v_{\mu,\gamma}^{i}}(g_{k}\cdot v_{\mu^{\prime},\gamma^{\prime}}^{j})$ for $1\leq i,j\leq h$, $0\leq k\leq\ell_{0}$, $\mu,\mu^{\prime}\in\mathbb{F}_{p^{2}}^{\times}$ and $\gamma,\gamma^{\prime}\in\mathrm{GL}_{2}(\mathbb{Z}/N\mathbb{Z})$. |
$\mathcal{V}_{i,j}\subset\mathcal{V}$ |  The set of primes $\ell$ such that at least one of $w_{\ell}^{i}$ and $w_{\ell}^{j}$ is not 1, excluding $p$ and $\ell_{0}$, and including all primes dividing $N$. |

######  Algorithm 5.1.

Input: a prime $p$ and level $N$ coprime to $p$, together with a prime
$\ell_{0}$ coprime to $pN$.

Output: a matrix representing the action of the Hecke operator $T_{\ell_{0}}$
on the space of all functions $\Omega(N)\to\overline{\mathbb{F}}_{p}$.

  1. (i)

Define a quaternion algebra $D=\left(\frac{-\epsilon,-p}{\mathbb{Q}}\right)$
over $\mathbb{Q}$, ramified exactly at $\\{p,\infty\\}$. Define a maximal
order $\mathcal{O}$ with integer basis given as in Proposition 3.7, for which
we denote the basis elements $\\{s^{1},s^{2},s^{3},s^{4}\\}$. Compute the left
ideal classes $I_{1},\dots,I_{h}$ of $\mathcal{O}$, and bases
$\mathcal{B}_{1},\dots,\mathcal{B}_{h}$ for them.

  2. (ii)

Compute the points $w^{j}=[w_{2}^{j},w_{3}^{j},w_{5}^{j},\dots]\in\Omega$
corresponding to $I_{j}$ for each $j$ as follows. We take $w_{\ell}^{j}$ to be
any generator of $I_{j}\otimes\mathbb{Z}_{\ell}$ (which we know is principal).
To do this, for our basis $\mathcal{B}_{j}$, compute the reduced norm of each
of the four elements and set $w_{\ell}^{j}$ to be any of these elements whose
reduced norm has minimal $\ell$-adic valuation. Note that for almost all
$\ell$ this valuation is zero, so we can instead take $w_{\ell}^{j}=1$, and do
so when possible.

  3. (iii)

Determine the set $\mathcal{V}$, defined in the Updated Table of Notation. For
each $\ell\in\mathcal{V}\cup\\{p\\}$, compute $m_{\ell}$ and $n_{\ell}$. For
each $\ell\in\mathcal{V}$, compute matrices
$A_{\ell},B_{\ell}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{n_{\ell}}\mathbb{Z})$
satisfying Condition 3.8. Using these, compute matrices corresponding to the
$s^{1},s^{2},s^{3},s^{4}$, which in any case are well defined modulo
$\ell^{2m_{\ell}+v_{\ell}(N)+2}$. Denote these by
$S_{\ell}^{i}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{2m_{\ell}+v_{\ell}(N)+2}\mathbb{Z})$
for each $\ell\in\mathcal{V}$. By expressing each
$w_{\ell}^{j}\in\mathcal{B}_{j}$ as a $\mathbb{Z}$-linear combination of
$s^{1},s^{2},s^{3},s^{4}$, we can compute matrices
$W_{\ell}^{j}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{2m_{\ell}+v_{\ell}(N)+2}\mathbb{Z})$
corresponding to the $w_{\ell}^{j}$.

  4. (iv)

Fix $i,j$. We will compute
$e_{(i,\mu,\gamma),(j,\mu^{\prime},\gamma^{\prime}),k}$, where $1\leq i,j\leq
h$, $0\leq k\leq\ell_{0}$, $\mu,\mu^{\prime}\in\mathbb{F}_{p^{2}}^{\times}$
and $\gamma,\gamma^{\prime}\in\mathrm{GL}_{2}(\mathbb{Z}/N\mathbb{Z})$.
Determine the set $\mathcal{V}_{i,j}$. Compute

$M=\ell_{0}\prod\limits_{l\in\mathcal{V}_{i,j}\cup\\{p,\ell_{0}\\}}\ell^{m_{\ell}}$

and

$K=\ell_{0}\prod\limits_{l\in\mathcal{V}_{i,j}\cup\\{p,\ell_{0}\\}}\ell^{v_{\ell}(\mathrm{nrd}(w_{\ell}^{i}))-v_{\ell}(\mathrm{nrd}(w_{\ell}^{j}))}.$

  5. (v)

We firstly compute $e_{i,j,k}$ as in Algorithm 4.1. Check if there exist
integers $t,x,y,z\in\mathbb{Z}$ such that the following conditions hold:

$\begin{dcases*}\mathrm{nrd}(t\cdot s^{1}+x\cdot s^{2}+y\cdot s^{3}+z\cdot
s^{4})=KM^{2}\\\ W_{\ell}^{i}\cdot\begin{pmatrix}a_{\ell}&b_{\ell}\\\
c_{\ell}&-a_{\ell}\end{pmatrix}\cdot\mathrm{adj}(W_{\ell}^{j})\in\ell^{m_{\ell}+v_{\ell}(\det(W_{\ell}^{j}))}\cdot\mathrm{M}_{2}(\mathbb{Z}/\ell^{2m_{\ell}+v_{\ell}(N)+2}\mathbb{Z})\hskip
30.00005pt\text{ for $\ell\in\mathcal{V}_{i,j}$}\\\
W_{\ell_{0}}^{i}\cdot\begin{pmatrix}a_{\ell_{0}}&b_{\ell_{0}}\\\
c_{\ell_{0}}&-a_{\ell_{0}}\end{pmatrix}\cdot\mathrm{adj}(W_{\ell_{0}}^{j})\cdot\mathrm{adj}(g_{k})\in\ell_{0}^{m_{\ell_{0}}+v_{\ell_{0}}(\det(W_{\ell_{0}}^{j}))+2}\cdot\mathrm{M}_{2}(\mathbb{Z}/\ell_{0}^{2m_{\ell_{0}}+2}\mathbb{Z}).\end{dcases*}$

where $\begin{pmatrix}a_{\ell}&b_{\ell}\\\
c_{\ell}&-a_{\ell}\end{pmatrix}\in\mathrm{M}_{2}(\mathbb{Z}/\ell^{2m_{\ell}+v_{\ell}(N)+2}\mathbb{Z})$
is the matrix corresponding to $t\cdot s^{1}+x\cdot s^{2}+y\cdot s^{3}+z\cdot
s^{4}$. If such $t,x,y,z$ exist, set $e_{i,j,k}$ to be 1, and otherwise 0.
Note that the only dependence on $k$ is in the last condition.

  6. (vi)

If $e_{i,j,k}=0$, set
$e_{(i,\mu,\gamma),(j,\mu^{\prime},\gamma^{\prime}),k}=0$ for all
$\mu,\mu^{\prime},\gamma,\gamma^{\prime}$. Otherwise, taking our solution
$(t,x,y,z)$ from the above step, compute the matrices

$\overline{Q_{\ell}}:=W_{\ell}^{i}\cdot\frac{1}{M}\begin{pmatrix}a_{\ell}&b_{\ell}\\\
c_{\ell}&-a_{\ell}\end{pmatrix}\cdot(W_{\ell}^{j})^{-1}\mod\ell^{v_{\ell}(N)}\in\mathrm{GL}_{2}(\mathbb{Z}/\ell^{v_{\ell}(N)}\mathbb{Z})$

for $\ell\mid N$, and

$Q_{p}:=w_{p}^{i}\cdot\frac{1}{M}(t\cdot s^{1}+x\cdot s^{2}+y\cdot
s^{3}+z\cdot s^{4})\cdot(w_{p}^{j})^{-1}\in\mathcal{O}_{p}^{\times}.$

Writing $Q_{p}$ in terms of $i$ and $j$, let
$\overline{Q_{p}}\in\mathbb{F}_{p^{2}}^{\times}$ be the reduction modulo $j$,
where we view the elements of $\mathbb{F}_{p^{2}}^{\times}$ as $\\{s+ti\mid
s,t\in\mathbb{F}_{p}\text{ not both zero}\\}$, which is a group under
multiplication.

Then for each $\mu\in\mathbb{F}_{p^{2}}^{\times}$ and
$\gamma\in\mathrm{GL}_{2}(\mathbb{Z}/N\mathbb{Z})$, if we denote the reduction
mod $\ell^{v_{\ell}(N)}$ of $\gamma$ by $\gamma_{\ell}$, define

(24)
$e_{(i,\mu,\gamma),(j,\mu^{\prime},\gamma^{\prime}),k}=\begin{dcases*}1&if
$\mu^{\prime}=\mu\cdot\overline{Q_{p}}\in\mathbb{F}_{p^{2}}^{\times}$, and
$\gamma_{\ell}^{\prime}=\gamma_{\ell}\overline{Q_{\ell}}\in\mathrm{GL}_{2}(\mathbb{Z}/\ell^{v_{\ell}(N)}\mathbb{Z})$
for all $\ell\mid N$\\\ 0&otherwise\end{dcases*}$

  7. (vii)

If we index the rows and columns of the matrix for $T_{\ell_{0}}$, with
respect to the basis consisting of $\mathbbm{1}_{v_{\mu,\gamma}^{i}}$, by
triples $(i,\mu,\gamma)$, then the
$((j,\mu^{\prime},\gamma^{\prime}),(i,\mu,\gamma))$-th entry is

$\frac{1}{\ell_{0}}\cdot\sum\limits_{k=0}^{\ell_{0}}e_{(i,\mu,\gamma),(j,\mu^{\prime},\gamma^{\prime}),k}.$

This gives us the matrix for $T_{\ell_{0}}$.

######  Remark 5.2.

We end by discussing how to obtain the matrix for $T_{\ell_{0}}$ with respect
to a basis for the space of weight $k$ functions
$\Omega(N)\to\overline{\mathbb{F}}_{p}$. This basis can be given by
$f_{i,\gamma}$ over $1\leq i\leq h$ and
$\gamma\in\mathrm{GL}_{2}(\mathbb{Z}/N\mathbb{Z})$, defined by

$f_{i,\gamma}=\sum\limits_{\mu\in\mathbb{F}_{p^{2}}^{\times}}\mu^{-k}\mathbbm{1}_{v_{\mu,\gamma}^{i}}.$

We know that $T_{\ell_{0}}$ preserves this space. Fix $(i,\gamma)$. By
linearity, we can compute

$T_{\ell_{0}}(f_{i,\gamma})=\sum\limits_{\mu\in\mathbb{F}_{p^{2}}^{\times}}\mu^{-k}T_{\ell_{0}}(\mathbbm{1}_{v_{\mu,\gamma}^{i}})$

using the matrix from Algorithm 5.1, which is the matrix for $T_{\ell_{0}}$
with respect to the $\mathbbm{1}_{v_{\mu,\gamma}^{i}}$. We know we can write

$T_{\ell_{0}}(f_{i,\gamma})=\sum\limits_{j,\gamma^{\prime}}a_{j,\gamma^{\prime}}f_{j,\gamma^{\prime}}$

for some $a_{j,\gamma^{\prime}}\in\mathbb{F}_{p^{2}}$. Then we see that

$a_{j,\gamma^{\prime}}=T_{\ell_{0}}(f_{i,\gamma})(v_{1,\gamma^{\prime}}^{j}),$

which is the coefficient of $\mathbbm{1}_{v_{1,\gamma^{\prime}}^{j}}$ in

$\sum\limits_{\mu\in\mathbb{F}_{p^{2}}^{\times}}\mu^{-k}T_{\ell_{0}}(\mathbbm{1}_{v_{\mu,\gamma}^{i}}).$

If we index the rows and columns of the matrix for $T_{\ell_{0}}$, with
respect to the basis $\\{f_{i,\gamma}\\}$, by pairs $(i,\gamma)$, then the
$((j,\gamma^{\prime}),(i,\gamma))$-th entry of this matrix is this
$a_{j,\gamma^{\prime}}$.

## References

  * [BCP97] Wieb Bosma, John Cannon, and Catherine Playoust, _The Magma algebra system. I. The user language_ , J. Symbolic Comput. 24 (1997), no. 3-4, 235–265, Computational algebra and number theory (London, 1993). MR MR1484478
  * [Buz] Kevin Buzzard, _Computing modular forms on definite quaternion algebras_ , available at https://www.ma.imperial.ac.uk/ buzzard/maths/research/notes/.
  * [Con] Keith Conrad, _A multivariable Hensel’s lemma_ , available at https://kconrad.math.uconn.edu/blurbs/.
  * [CS01] Caterina Consani and Jasper Scholten, _Arithmetic on a quintic threefold_ , Internat. J. Math. 12 (2001), no. 8, 943–972. MR 1863287
  * [Del69] Pierre Deligne, _Formes modulaires et représentations $l$-adiques_, Séminaire Bourbaki 11 (1968-1969), 139–172 (fre).
  * [Dem05] Lassina Dembélé, _Explicit computations of Hilbert modular forms on ${\mathbb{Q}}(\sqrt{5})$_, Experiment. Math. 14 (2005), no. 4, 457–466. MR 2193808
  * [Dem07] by same author, _Quaternionic Manin symbols, Brandt matrices, and Hilbert modular forms_ , Math. Comp. 76 (2007), no. 258, 1039–1057. MR 2291849
  * [Koh01] David R. Kohel, _Hecke module structure of quaternions_ , Class field theory—its centenary and prospect (Tokyo, 1998), Adv. Stud. Pure Math., vol. 30, Math. Soc. Japan, Tokyo, 2001, pp. 177–195. MR 1846458
  * [KV12] Markus Kirschmer and John Voight, _Corrigendum: Algorithmic enumeration of ideal classes for quaternion orders_ , SIAM J. Comput. 41 (2012), no. 3, 714. MR 2967473
  * [Piz80] Arnold Pizer, _An algorithm for computing modular forms on $\Gamma_{0}(N)$_, Journal of Algebra 64 (1980), no. 2, 340–390.
  * [SL96] J-P. Serre and Ron Livne, _Two letters on quaternions and modular forms (mod $p$)_, Israel Journal of Mathematics 95 (1996), 281–299.
  * [SW05] Jude Socrates and David Whitehouse, _Unramified Hilbert modular forms, with examples relating to elliptic curves_ , Pacific J. Math. 219 (2005), no. 2, 333–364. MR 2175121
  * [Voi13] John Voight, _Identifying the matrix ring: algorithms for quaternion algebras and quadratic forms_ , Quadratic and higher degree forms, Dev. Math., vol. 31, Springer, New York, 2013, pp. 255–298. MR 3156561
  * [Voi21] John Voight, _Quaternion algebras_ , Graduate Texts in Mathematics, Springer Cham, 2021.
  * [Wie06] Gabor Wiese, _Mod $p$ modular forms_, available at https://wstein.org/msri06/wiese/, 2006.