The Bellaterra graphs are Ramanujan

Introduction

Three permutations $a$, $b$, $c$ of the binary words of length $n$ define a finite graph: from $w$ take one step to $a(w)$, $b(w)$, or $c(w)$. For the Bellaterra automaton these permutations are involutions, so the adjacency matrix is symmetric and has row sum three. The question is whether the resulting graphs remain uniformly well connected as $n$ grows. We prove the precise spectral estimate

for every eigenvalue on the nonconstant subspace.

§ 2 defines the graphs and explains why this is the cubic Ramanujan bound. The proof uses exact identities that hold at every level, followed by a stated theorem from arithmetic.

The expansion problem

The problem of constructing expander or Ramanujan families from finite automata was posed by Grigorchuk [4 Section 12, Problem 12.3(a, b)]. Ramanujan graphs of valence $q+1$ with $q$ an odd prime power, generated by automata, were constructed by Bondarenko, Grigorchuk and Vdovina in [2 Theorem 2]. For the Bellaterra level graphs, Grigorchuk explicitly asked whether they form an expander family [5 Example 10.2 and Problem 10.1, p. 155]. Malyshev and Pak subsequently formulated the two-sided expansion conjecture [7 Conjecture 1.3]. We prove the stronger Ramanujan estimate for the cubic adjacency operator defined below.

A guide to the proof

The construction compares three descriptions of the same finite set:

The first set carries the automaton action. The second carries fractional-linear transformations arising from three quaternions. The third is a finite arithmetic class set on which a Hecke operator is defined. Here $\mathcal{E}_n$ is an order, a quaternionic analogue of a ring of integers, with a congruence condition at the level prime. Definitions appear before these objects are used in the proof.

The first bijection 1.1 is proved by six multiplication identities. The second follows from a base class-number-one calculation. We then prove that the sum of the three arithmetic permutations is the Hecke operator on all ideal classes. Finally, Jacquet–Langlands and the Hilbert modular Ramanujan theorem bound its nonconstant eigenvalues.

The Bellaterra graphs and the theorem

Rooted trees, sections, and finite automata

The rooted binary tree has vertex set $\{0,1\}^{*}$, the finite words in two letters. Its root is the empty word. The two children of $w$ are $w0,w1$, and its level $n$ is $V_n=\{0,1\}^{n}$. A rooted-tree automorphism is a permutation of the vertices that fixes the root and preserves adjacency. Equivalently, it preserves word length and the operation of deleting the last letter.

Every such automorphism $g$ has a permutation of the first letter and two automorphisms $g_0,g_1$ of the remaining word:

The maps $g_e$ are called its sections. The notation $g=(g_0,g_1)_\sigma$ is called wreath recursion; an identity $\sigma$ is omitted. Iterating gives the section $g|_w$ at any word. A finite invertible automaton specifies finitely many states by their first-letter permutations and their sections, which are again among the states. It reads one letter, writes one letter, and moves to the indicated state for the remaining input.

For a word $w\in\{0,1\}^{*}$, define the Bellaterra states by

All three fix the empty word. In wreath-recursion notation this is

This is the Bellaterra automaton, with the binary coordinates complemented relative to [9 Section 5]. More precisely, if $\delta_n$ complements every letter of a word of length $n$, then conjugating the convention $a=(c,b)$, $b=(b,c)$, $c=(a,a)_\sigma$ by $\delta_n$ gives (2). Thus the convention does not affect the graphs or their spectra.

For example,

The recursion defines a bijection at every level by induction on word length. The same induction shows that the states are involutions: their squares have identity first-letter action and sections among the preceding-level squares. We write $\mathcal{B}=\langle a,b,c\rangle$ for the group they generate.

Schreier graphs and their adjacency matrices

If a group generated by involutions acts on a set, its Schreier graph has that set as vertices and one transition $v\mapsto s(v)$ for each chosen generator $s$. For a transitive action it can also be described on the cosets $B/H$, where $H$ is the stabilizer of a vertex. The generating set is part of the graph data. Two different generators may connect the same pair of vertices.

The Bellaterra level graph $G_n$ is the graph with this adjacency matrix. Edges are counted with their state labels and multiplicities. A fixed state contributes one to a diagonal entry, so a fixed-point petal is a half-loop in the degree convention used here.

Thus $M_n$ is a real symmetric matrix with nonnegative integral entries and row sum three. A drawn half-loop contributes one diagonal entry, so its degree contribution is one. This convention is fixed by (3); ordinary loops counted twice would define a different operator. On functions, the same operator is $(M_n f)(w) = f(a(w)) + f(b(w)) + f(c(w))$.

Example 2.2 (The first level). Both $a$ and $b$ fix 0 and 1, while $c$ interchanges them. Hence

At each vertex the first two states supply the two fixed-state contributions, and the third supplies the edge to the other vertex.

We use the inner product $\langle f,g\rangle= \sum_{w\in V_n} \overline{f(w)}g(w)$. The constant function $\mathbf{1}$ always has eigenvalue 3. Its orthogonal complement is

For any graph defined by three involutions $s_1,s_2,s_3$,

It follows that the eigenspace of 3 consists of the functions constant on each connected component. Its dimension is therefore the number of components. This observation will prove connectedness at the end of the argument.

The spectral question

The adjacency operator of the infinite cubic tree has spectral radius $2\sqrt{2}$. A connected cubic graph is called Ramanujan when every adjacency eigenvalue other than the trivial values 3 and, if present, $-3$, lies in $[-2\sqrt{2},2\sqrt{2}]$. The same spectral definition applies to our involution graphs, with the matrix convention above. We prove the stronger statement that every eigenvalue on $\mathbf{1}^{\perp}$ belongs to that interval; in particular, $-3$ does not occur.

The normalized adjacency or random-walk operator is $P_n=M_n/3$. It chooses one of the three states with probability $1/3$. A family has a uniform absolute spectral gap, or is a family of two-sided expanders, if there is an $\varepsilon>0$ independent of $n$ such that $\lVert P_n|_{\mathbf{1}^{\perp}}\rVert\leq1-\varepsilon$. The Ramanujan estimate gives the explicit gap $\varepsilon=1-2\sqrt{2}/3>0$.

The theorem will be proved in § 8.

Deletion of the last letter commutes with the three states. Thus these graphs form a compatible tower. The pullback map $J_{B,n}\mathbf{e}_w=\mathbf{e}_{w0}+\mathbf{e}_{w1}$ satisfies $M_{n+1}J_{B,n}=J_{B,n}M_n$. The arithmetic change of coordinates will preserve this tower, as well as the individual state labels. No torsion-free hypothesis will be imposed on the arithmetic group.

Dyadic arithmetic and the two primes above two

Compatible residues and the dyadic integers

The dyadic integers can be defined by

An element is a sequence of residues modulo 2, 4, 8, $\ldots$ that agree under reduction. Addition and multiplication are performed in every residue ring. For $x \ne0$, the valuation $v_2(x)$ is the largest integer $m$ for which $x \equiv0 \pmod{2^m}$; set $v_2(0) = +\infty$. The distance is $|x-y|_2 = 2^{-v_2(x-y)}$. Thus closeness means agreement modulo a high power of two. The fraction field is $\mathbb{Q}_2$. An element of $\mathbb{Z}_2$ is a unit, meaning that it has an inverse in $\mathbb{Z}_2$, exactly when it is odd.

Every ball $a+2^m\mathbb{Z}_2$ splits into two balls of half the dyadic radius:

These refinements form a rooted binary tree. Its level $m$ is $\mathbb{Z}/2^m\mathbb{Z}$, with parent map given by reduction. A compatible bijection between this tree and the word tree will be our map $\kappa_n$. The first input letter specifies the first residue choice, hence the least significant dyadic digit. The full coding is nonlinear: a word must not be replaced by its usual binary integer.

We use only the following elementary form of Hensel lifting. If $f$ is an integer polynomial and $x_m$ is a root modulo $2^m$ with $f'(x_m)$ odd, precisely one of $x_m$, $x_m+2^m$ is a root modulo $2^{m+1}$. Indeed,

A simple root modulo two therefore determines a unique dyadic root. All the local coordinates used below can be computed in this way to any desired finite precision.

The real quadratic field

A number field is a finite extension of $\mathbb{Q}$. Its ring of integers consists of its elements satisfying monic integer polynomials. For the real quadratic field below this ring has the indicated basis. The two real embeddings send $r$ to $\sqrt{17}$ and $-\sqrt{17}$. An element is totally positive if its images under both embeddings are positive. The field norm $N_{F/\mathbb{Q}}(x)$ is the product of its two conjugates.

Throughout, set

Both $\eta$ and $\rho$ are totally positive of norm 2. The factorization $(2)=\mathfrak{p}\mathfrak{q}$ has two distinct primes of norm 2. The prime $\mathfrak{p}$ will define the cubic Hecke operator, while $\mathfrak{q}$ will define the levels.

For clarity, a nonzero prime ideal $\mathfrak{l}$ of $\mathcal{O}_F$ has norm $\mathrm{N}\mathfrak{l}=|\mathcal{O}_F/\mathfrak{l}|$, the number of elements in its residue field. The completion $F_{\mathfrak{l}}$ records congruences modulo successive powers of $\mathfrak{l}$, just as $\mathbb{Q}_2$ records dyadic congruences. Its valuation ring, denoted $\mathcal{O}_{F,\mathfrak{l}}$, consists of the elements with nonnegative valuation. We use this notation for the completed valuation ring throughout. A uniformizer is an element of valuation one.

The equation $\omega^2-\omega-4=0$ reduces modulo two to $X(X-1)$. The two residue homomorphisms send $\omega$ to 0 and 1, respectively. They have kernels $\mathfrak{q}$ and $\mathfrak{p}$. Hensel lifting shows that both completions $F_{\mathfrak{q}}$ and $F_{\mathfrak{p}}$ are isomorphic to $\mathbb{Q}_2$, with distinct embeddings of $F$.

	Active prime $\mathfrak{p}$	Level prime $\mathfrak{q}$
$\omega$ in the residue field	1	0
$v_{\mathfrak{l}}(\rho)$	1	0
$v_{\mathfrak{l}}(\eta)$	0	1
Role in the graph	three neighbors	$2^n$ vertices

The same quaternion may have determinant of valuation one at $\mathfrak{p}$ and be an integral invertible matrix at $\mathfrak{q}$. This difference in local behavior is what permits the two roles in the construction.

The quaternion algebra and three involutions

Quaternions and projective involutions

Our quaternion algebra is the four-dimensional $F$-algebra

Its basis is $1,i,j,k$. Quaternion conjugation changes the signs of $i,j,k$; write $\bar{x}$ for the conjugate of $x$. The reduced trace is $x+\bar{x}$ and the reduced norm is $x\bar{x}$, both in $F$. For $x=x_0+x_1i+x_2j+x_3k$,

The reduced norm is multiplicative, and every element satisfies

The projective group is $D^\times/F^\times$: two nonzero quaternions define the same projective element when they differ by a nonzero scalar in $F$. Thus a noncentral trace-zero quaternion with nonzero norm defines an involution in this group, even though its square in $D$ need not equal 1.

At a completion $F_{\mathfrak{l}}$ we write $D_{\mathfrak{l}}=D\otimes_F F_{\mathfrak{l}}$. The algebra splits at that place if it is isomorphic to $M_2(F_{\mathfrak{l}})$. Under such an isomorphism, reduced trace and norm become matrix trace and determinant. At a place where the quaternion algebra is a division algebra, it is called ramified. At either real embedding the displayed norm is positive definite, so $D$ is a division algebra there. This is the meaning of totally definite in this note.

It splits at every finite place. The explicit order below certifies this through its unit discriminant: the discriminant of a maximal quaternion order is divisible by every finite ramified prime [6 Section 2]. ્ર

Orders and an explicit maximal order

An $\mathcal{O}_F$-order in $D$ is a subring containing $1$ that is also a full rank-four $\mathcal{O}_F$-lattice. Here a full lattice means a finitely generated $\mathcal{O}_F$-submodule spanning the ambient $F$-vector space. A maximal order is one not properly contained in any other order. For an order $\mathcal{R}$, write $\mathcal{R}_{\mathfrak l}=\mathcal{R}\otimes_{\mathcal{O}_F}\mathcal{O}_{F,\mathfrak l}$. The group $\mathcal{R}^{\times}$ consists of elements whose inverses also belong to the order. Specifying the integral lattice matters: it determines the congruences that will define the finite graphs.

Define

Here angle brackets denote the $\mathcal{O}_F$-span. The multiplication table

proves that $\mathcal{O}$ is an order. For $e=(1,i,u,v)$, direct calculation gives

Here the trace pairing sends $(x,y)$ to $\operatorname{trd}(xy)$. Its determinant measures the local index of the integral lattice. To see the maximality test directly, an inclusion of orders multiplies the trace determinant by the square of the change-of-basis determinant. Trace pairings on orders are integral. A unit determinant leaves no room for a nontrivial local index, so the order is maximal. Equivalently, its reduced discriminant ideal, whose square is the trace discriminant ideal, is $(1)$. In particular, $D$ is unramified at all finite primes. The multiplication table and determinant are finite algebraic checks of the exact integral order used in the proof.

The generators

The following pure quaternions will act as the three automaton states:

Their order coordinates are

In particular $A,B,C\in\mathcal{O}$. The relation $1+\alpha^2=3\rho$ gives

Thus the projective classes of $A,B,C$ are involutions. Also

The residue of $\omega$ at $\mathfrak{q}$ is zero. To check a crucial congruence in the entire order, rewrite (11) as

It follows that

The local coordinate at the level prime

Identify $\mathbb{F}_{q}$ with $\mathbb{Q}_{2}$. This embedding selects the even root $\alpha\in\mathbb{Z}_{2}$ of $X^{2}+3X-2$, so $\alpha\equiv10\pmod{16}$. Let $z\in\mathbb{Z}_{2}$ be the even root of $z^{2}+z+2=0$; then $z\equiv2\pmod8$. Hensel’s lemma gives both roots uniquely with these parities. A splitting of $D_{\mathfrak{q}}$ is

Multiplication verifies the quaternion relations. In this same coordinate,

Every entry is integral. Equation (9) shows that this inclusion of orders is an equality:

The arithmetic order and the subsequent coding thus use precisely the same local lattice.

By (14), $A$, $B$, $C$ lie in the scalar-modulo-2 subgroup of $\operatorname{GL}_{2}(\mathbb{Z}_{2})$. Each preserves $x\in2\mathbb{Z}_{2}$. In the coordinate $x=2t$, a matrix $g=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ in this subgroup acts as

Here $a,d$ are odd and $b,c$ are even, so the denominator is odd. The three induced permutations on $\mathbb{Z}/2^{n}\mathbb{Z}$ are therefore completely specified by (10), (15), and (17).

They commute with reduction modulo powers of two: denominators are units, and subtraction of two fractional-linear expressions preserves congruences. Their adjacency sum will be denoted by $C_{n}$. This already defines an explicit sequence of cubic arithmetic graphs on $\mathbb{Z}/2^{n}\mathbb{Z}$, before any ideal-class or automorphic terminology is introduced.

The cubic lattice tree and its binary branch

The local tree

Let $L_{0}=\mathbb{Z}_{2}$. A lattice in $\mathbb{Q}_{2}^{2}$ is a free rank-two $\mathbb{Z}_{2}$-submodule spanning $\mathbb{Q}_{2}^{2}$. Two lattices are homothetic if one is a nonzero scalar multiple of the other. The vertices of the Bruhat–Tits tree are their homothety classes $[L]$. Two classes are adjacent if representatives satisfy

For fixed $L$, the intermediate lattices correspond to the one-dimensional subspaces of $L/2L\simeq\mathbb{F}_{2}^{2}$. There are exactly three such lines. Hence every vertex has three neighbors.

The elementary-divisor theorem over $\mathbb{Z}_{2}$ gives a convenient description of the graph. Every homothety class has the form $[\mathbb{Z}_{2}v+2^{m}\mathbb{Z}_{2}w]$, where $(v,w)$ is a basis of $L_{0}$ and $m\ge0$. Call $m its elementary-divisor height relative to $[L_0]$. Directly calculating the three neighbors shows that a vertex of height $m>0$ has one neighbor of height $m-1$ and two of height $m+1$. Thus the graph is connected and has no cycles, and height is exactly distance from $[L_0]$. The lattice graph is a tree, and the region beyond a chosen edge is a rooted binary tree.

The group $\operatorname{PGL}_2(\mathbb{Q}_2)=\operatorname{GL}_2(\mathbb{Q}_2)/\mathbb{Q}_2^\times$ acts by $[L]\mapsto[gL]$. The stabilizer of $[L_0]$ is $\operatorname{PGL}_2(\mathbb{Z}_2)$. An integral matrix with determinant of valuation one has elementary divisors $1,2$, up to units, and therefore moves $[L_0]$ to a neighbor. At the active prime $p$, this applies to $A,B,C$ because their reduced norm is $\rho$.

The branch used for the finite levels

The ends of this tree are identified with $\mathbb{P}^1(\mathbb{Q}_2)$, the one-dimensional subspaces of $\mathbb{Q}_2^2$. In the affine chart whose column representative is $(x,1)$, the ends in the branch reducing to $(0,1)$ modulo two are $x\in2\mathbb{Z}_2$. Writing $x=2t$, the next $n$ binary choices give $t\bmod2^n$. This is the geometric meaning of the local coordinate (17).

By (14), the three quaternions act as the identity on the three initial directions at $q$. They preserve the selected branch and act on every finite level within it. The two local roles can therefore be stated without arithmetic shorthand: the same three group elements move to neighbors in one cubic tree and permute a finite binary level in the other. Quaternionic groups acting on products of trees, their congruence quotients, and the Hecke interpretation of adjacency are treated in [8 Sections 2, 3, and 6].

An explicit conjugacy at every level

We now identify the three arithmetic permutations with the three automaton states. The idea is to imitate prefixing a word by 0 or 1 with two dyadic maps $h_0,h_1$. For example, the automaton rule $a(0w)=0b(w)$ becomes the identity $\widetilde{A}h_0=h_0\widetilde{B}$. Six such identities will give the entire recursion. This is the explicit step that connects the arithmetic construction to this particular automaton.

Six identities and two contractions

Composition of fractional-linear maps is matrix multiplication, and scalar multiples define the same map. We can therefore search for the prefix maps directly in the four-dimensional quaternion algebra. Define

Multiplication in $D$, using $\alpha^2=2-3\alpha$, gives

The two reduced norms are

These are identities in a four-dimensional algebra over $\mathbb{Q}[\alpha]/(\alpha^2+3\alpha-2)$, so they require only rational arithmetic to verify.

In the local splitting (15), write $U_s=H_s/4$. For completeness their matrices are

They are integral because $\alpha$ is even. The specified residues of $\alpha$, $z$ give

Also $\rho+1=2-\alpha\equiv8\pmod{16}$, so

Write $U_s=\begin{pmatrix}a_s&b_s\\c_s&d_s\end{pmatrix}$ and define

Proof. By (23), $a_s,b_s,c_s$ are even, $d_s$ is odd, $a_s\equiv2\pmod{4}$, and $b_s/2\equiv s\pmod{2}$. The denominator in (24) is odd, and $h_s(t)\equiv s\pmod{2}$. Subtracting the two fractions gives

which proves (25) and injectivity. For $y\equiv s\pmod{2}$, the inverse is explicitly

The numerator is even, and the denominator has valuation one because $a_s\equiv2\pmod{4}$ and $c_s$ is even. This lies in $\mathbb{Z}_2$ and solves $h_s(t)=y$, proving surjectivity.

The valuation identity says exactly that each $h_s$ multiplies dyadic distances by $1/2$. After $n$ such maps, changing the input by an integral amount changes the output by a multiple of $2^n$. This is the precision statement needed for a proof at every level.

The vertex bijections

For $w=w_1\cdots w_n\in V_n$, set

Thus the first letter is the outermost contraction. The final argument $0$ can be replaced by any element of $\mathbb{Z}_2$ without changing the residue modulo $2^n$, by (25).

Proof. The disjoint images in Lemma 6.1, followed by (25) within each image, prove by induction that the $2^n$ words give distinct residues modulo $2^n$. Hence $\kappa_n$ is a bijection. For the compatibility statement, the terminal argument changes from $0$ to $h_e(0)$ after the same first $n$ contractions; their combined contraction factor is $2^{-n}$. Pass from (19) to projective Möbius transformations. Scalar signs disappear, and conjugation by the coordinate $x=2t$ gives

These are precisely the six transitions in (2). For example, pushing $\widetilde{A}$ through $h_{w_1}\cdots h_{w_n}$ replaces the word by $a(w)$ and leaves a terminal state $\widetilde{g}$, for some $g\in\{A,B,C\}$:

The terminal value belongs to $\mathbb{Z}_2$, and the $n$ contractions make its replacement by $0$ invisible modulo $2^n$. This proves the first identity in (28); the other two follow in the same way.

The inverse coding is equally explicit. Given $t\in\mathbb{Z}_2$, record its parity $s_1$ and replace it by $h_{s_1}^{-1}(t)$. Record the new parity $s_2$ and repeat. Lemma 6.1 guarantees that each step is defined. This recovers a unique infinite word; the forward coding recovers $t$ as its compatible sequence of residues. At finite level, the first $n$ steps recover the unique word $\kappa_n^{-1}(t\bmod2^n)$.

The matrices and the maps between levels

Let $T_n:\mathbb{C}^{V_n}\to\mathbb{C}^{\mathbb{Z}/2^n\mathbb{Z}}$ be the permutation matrix

A permutation matrix changes the names of the vertices. In particular, it preserves the inner product and the eigenvalues of adjacency. Proposition 6.2 gives

Define pullback maps by

Equation (29) implies

For the alternative Bellaterra convention used in [9], the vertex map is $\kappa_n\circ\delta_n$.

The ideal-class graph and its Hecke operator

The coding has already proved that the automaton graphs and the explicit residue graphs are isomorphic. To invoke an arithmetic spectral theorem, we must identify the residue graph with the whole arithmetic class graph, including every vertex and every neighbor. That is the purpose of this section.

Eichler orders and congruence stabilizers

An Eichler order is the intersection of two maximal orders. At a split local place, it is conjugate to

Here $\pi$ is a uniformizer and $m \ge0$. The exponent $m$ is its local level exponent. The product of $\mathfrak{p}^{m}$ over the finite primes is its level ideal. Geometrically, $m$ is the distance between the two vertices whose endomorphism rings are the maximal orders being intersected. Its projective unit group fixes that segment pointwise.

For $n \ge0$, specify a global order $\mathcal{E}_n \subset\mathcal{O}$ by

These local conditions define the order by intersection in $D$. Conjugation by $\operatorname{diag}(2^{n+1},1)$ gives

Thus $\mathcal{E}_n$ is an Eichler order of level $\mathfrak{q}^{n+2}$. The shift by two has a geometric explanation. Put

Directly computing their endomorphism rings gives

The endpoints have distance $n+2$: one is one edge on the other side of the base vertex, while the second is $n+1$ edges into the chosen branch. The local level consequently records $n+2$ edges, although our finite set has only $n$ binary choices.

At $n=0$, its projective local unit group is

Indeed, a unit in the matrix order has odd diagonal entries and even off-diagonal entries, and over $\mathbb{F}_2$ this means reduction to the identity. The group $K$ acts transitively on $t\bmod2^n$ in (17): use the translations $\begin{pmatrix}1&2^nt\\0&1\end{pmatrix}$. Its stabilizer of $0\bmod2^n$ is the projective image $K_n$ of $(\mathcal{E}_n)_{\mathfrak{q}}^\times$. Consequently

Ideal classes, class numbers, and the mass

A fractional ideal of $\mathcal{O}_F$ is an $\mathcal{O}_F$-lattice in $F$. The ordinary ideal class group identifies two such ideals when they differ by multiplication by an element of $F^\times$. The narrow class group permits multiplication only by totally positive elements. Their cardinalities are the ordinary and narrow class numbers. Narrow class number one will ensure that the only exceptional arithmetic eigenfunction is the constant function.

For an order $\mathcal{R}\subset D$, a right $\mathcal{R}$-ideal means a full lattice $I\subset D$ with $I\mathcal{R}\subset I$; fractional lattices are allowed. It is locally principal if $I_{\mathfrak{l}}=x_{\mathfrak{l}}\mathcal{R}_{\mathfrak{l}}$ for some $x_{\mathfrak{l}}\in D_{\mathfrak{l}}^\times$ at every finite prime. Two such ideals represent the same class if $I=dJ$ for a $d\in D^\times$. Multiplication is on the left because these are right ideals. Their finite class set is $\operatorname{Cl}(\mathcal{R})$ and its cardinality is $h(\mathcal{R})$.

The left order of $I$ is $\mathcal{R}_I=\{x\in D:xI\subseteq I\}$. Its projective unit group is $\mathcal{R}_I^\times/\mathcal{O}_F^\times$. For locally principal ideals of a definite order these groups are finite. The mass is the weighted count

The mass formula is a standard arithmetic input [6 Section 5]. For a totally definite quaternion algebra over a totally real field of degree $d$, with finite discriminant $(1)$, and an Eichler order of level $\mathfrak{N}$, its specialization is

Here $\zeta_F$ is the Dedekind zeta function, initially $\sum_{\mathfrak{a}\ne0}(N\mathfrak{a})^{-s}$ over nonzero integral ideals for $\Re(s)>1$, continued to $s=-1$. In our case its value is elementary to compute. We will also prove that every weight in the mass is one, so the mass is the actual number of vertices.

Proof. The quadratic Minkowski bound is $\sqrt{17}/2<2.1$. Every ideal class therefore has an integral representative of norm at most 2, and the two primes of norm 2 are the principal ideals $(\eta)$ and $(\rho)$. Hence the ordinary class number is one.

Put $\epsilon=4+r$, of norm $-1$. We give an elementary unit calculation. If a unit has first real value $1<u<\epsilon$, its other real value is $u'=\pm u^{-1}$. Writing $u=(a+br)/2$ gives $0<br=u-u'<2r$, because $\epsilon+\epsilon^{-1}=2r$ and $\epsilon-\epsilon^{-1}=8<2r$. Thus $b=1$, but the unit norm equation would give $a^2=13$ or 21. There is no such unit. Dividing any unit positive at the first embedding by a suitable power of $\epsilon$ places that embedding in $[1,\epsilon)$. Consequently

The second embedding of $\epsilon$ is negative, so the totally positive units are precisely $\epsilon^{2m}$, hence squares. The sign patterns of $-1$ and $\epsilon$ also show that every principal ideal has a totally positive generator. The narrow class number is therefore one.

For completeness, let $\chi(a)=\left(\frac{a}{17}\right)$ be the quadratic character: it is 1 on nonzero squares modulo 17, $-1$ on nonsquares, and 0 on multiples of 17. Its Dirichlet function is $L(s,\chi)=\sum_{a\ge1}\chi(a)a^{-s}$, initially for $\Re(s)>1$. The quadratic-field factorization is $\zeta_F(s)=\zeta_{\mathbb{Q}}(s)L(s,\chi)$. The elementary special-value formula and finite sum give

Let $\mathcal{R}$ be any Eichler order of the indicated level and let $x\in\mathcal{R}^\times$. Its reduced norm is a totally positive unit. Multiplying by a scalar unit, normalize $\operatorname{nrd}(x)=1$. If $x$ is noncentral, definiteness implies $\lvert\sigma(\operatorname{trd}(x))\rvert<2$ at both real embeddings. Write the integral trace as $t=(a+br)/2$, where $a,b\in\mathbb{Z}$ have the same parity. The difference between its two embeddings is $br$, so $\lvert b\rvert r<4$ forces $b=0$. Thus $t\in\{-1,0,1\}$.

Locally at $\mathfrak{q}$, conjugate $\mathcal{R}$ to the standard Eichler order, which is upper triangular modulo 4. A determinant-one unit has odd diagonal entries with product 1 modulo 4. Their sum is 2 modulo 4, so its trace cannot be $-1$, 0, or 1. This contradiction proves that every unit is central. The same argument applies to every left order of a locally principal ideal.

The definite Eichler mass formula [6 Section 5] now counts ideal classes without weights, because each projective unit group is trivial. The finite discriminant of $D$ is $(1)$, so the mass is

This proves all assertions.

Finite ideles as a notation for local lattices

A finite idele of $D$ is a tuple $x=(x_{\ell})_{\ell}$, with $x_{\ell}\in D_{\ell}^{\times}$, that belongs to the local order unit group at all but finitely many primes. These tuples form a group $\widehat{D}^{\times}$. The global group $D^{\times}$ embeds diagonally. Put

The tuple $x$ determines the right ideal $I_x=D\cap x\widehat{R}$. Right multiplication by local order units leaves this ideal unchanged; left multiplication by a global element changes it within its ideal class. The local-to-global description of lattices therefore gives the double-coset formula

This is bookkeeping for local generators of ideals. A tuple need not be $1$ at almost every prime; it need only be a unit there. The particular representatives used below can be chosen to be $1$ away from the level prime.

All classes and all three Hecke neighbors

Put $U_n=\widehat{\mathcal{E}}_n^{\times}$. A Brandt module is the vector space of functions on $\operatorname{Cl}(\mathcal{E}_n)$. The Hecke operator at a prime away from the level sends a function to the sum of its values on the local neighboring lattices at that prime, leaving the local data at every other prime unchanged. Its matrix in the ideal-class basis is called a Brandt matrix [3 Section 4]. The directed graph with vertices $\operatorname{Cl}(\mathcal{E}_n)$ and one edge for each neighbor, counted with its multiplicity, is called a Brandt graph. For a split prime with residue field of size $q$, the operator has $q+1$ neighbor terms. We always use this unnormalized neighbor sum.

In matrix notation, the local operator is the double coset $\operatorname{GL}_2(\mathcal{O}_{F,\mathfrak p})\operatorname{diag}(\varpi,1)\operatorname{GL}_2(\mathcal{O}_{F,\mathfrak p})$. Its right cosets parametrize the $\mathrm{N}\mathfrak p+1=3$ neighbors described in § 5. For each vertex, right multiplication of its idele representative by these cosets gives its three arithmetic neighbors. Distinct neighbors may represent the same ideal class, producing multiplicities or fixed-state entries. The next proposition identifies this entire matrix.

Proof. The following elementary coset principle is useful. If $G=HU_0$ for subgroups $H,U_0$, and $U\subseteq U_0$, then $H\backslash G/U\simeq(H\cap U_0)\backslash U_0/U$. Indeed, every orbit under left multiplication by $H$ has a representative in $U_0$. If $u,u'\in U_0$ represent the same double coset, then $u'=huv$ with $h\in H$, $v\in U$. Hence $h=u'v^{-1}u^{-1}\in H\cap U_0$, which proves both injectivity and the asserted equivalence relation.

Since $h(\mathcal{O})=1$, formula (40) says precisely that $\widehat{D}^{\times}=D^{\times}U_0$. Applying this principle gives

The group $\mathcal{E}_0^{\times}=\mathcal{O}_F^{\times}$ is central and contained in $U_n$, so its left action on $U_0/U_n$ is trivial. The only local factor in which $U_n$ differs from $U_0$ is $\mathfrak q$. Dividing both local groups by their common center and applying (36) proves the bijections. Explicit representatives are the finite ideles $u_t$, for $t\bmod2^n$, whose component at $\mathfrak q$ is

and whose other components are 1. The corresponding right ideal is $I_t = D \cap u\mathcal{E}_n$. In particular, every class has a representative $u \in\mathcal{U}_0$ supported only at $\mathfrak{q}$.

We now compute the Hecke action, including its coset direction. At $\mathfrak{p}$, identify $\mathcal{O}_{\mathfrak{p}}$ with $M_2(\mathcal{O}_{F,\mathfrak{p}})$. The elements $A,B,C$ are integral of determinant valuation one. They therefore belong to the Hecke double coset of $\operatorname{diag}(\varpi,1)$. They represent three distinct right cosets of $\mathcal{O}_{\mathfrak{p}}^{\times}$. Indeed, for distinct $g,h$ among $A,B,C$, (13) gives $\operatorname{trd}(gh)=\varpi-1$, a $\mathfrak{p}$-adic unit, while $\operatorname{nrd}(gh)=\varpi^2$. Thus the elementary divisors of $gh$ have valuations $0,2$. As $g^{-1}h=-gh/\varpi$, it is not an integral invertible matrix. Hence $g\mathcal{O}_{\mathfrak{p}}^{\times}\ne h\mathcal{O}_{\mathfrak{p}}^{\times}$. There are precisely $N\mathfrak{p}+1=3$ such cosets, so these are all of them.

For $g\in\{A,B,C\}$, let $t_g\in\widehat{D}^{\times}$ equal $g$ at $\mathfrak{p}$ and $1$ at every other finite place. Write

The element $z_g$ belongs to $\mathcal{U}_0$: away from $\mathfrak{p}$ each generator is an order unit, and at $\mathfrak{q}$ it is scalar modulo $2$. For a representative $u$ supported only at $\mathfrak{q}$, the finite ideles $u$ and $t_g$ commute. Therefore

In the quotient $K/K_n$, this is left multiplication by $g^{-1}$. But $g^{-1}=-g/\varpi$, and $-1/\varpi$ is a scalar unit at $\mathfrak{q}$, so it induces precisely the same permutation as $g$. Thus the three Hecke neighbors of a residue $t$ are $\widetilde{A}(t)$, $\widetilde{B}(t)$, and $\widetilde{C}(t)$, with their multiplicities. This proves $T_{\mathfrak{p}}=C_n$.

Remark 7.3 (Torsion and the tree). The notation $\mathcal{E}_0[1/\varpi]$ allows denominators that are powers of $\varpi$, changing integrality only at $\mathfrak{p}$. Let $P$ denote image in $D^{\times}/F^{\times}$. The arithmetic group $\Gamma=P(\mathcal{E}_0[1/\varpi]^{\times})$ acts simply transitively on the vertices of the cubic Bruhat–Tits tree at $\mathfrak{p}$. To see transitivity, prescribe a locally principal right ideal that is $\mathcal{E}_0$ away from $\mathfrak{p}$ and represents a chosen tree vertex at $\mathfrak{p}$; equation (38) makes it principal. A base-vertex stabilizer becomes an element of $\mathcal{E}_0^{\times}$ after multiplication by a scalar power of $\varpi$, hence is projectively trivial. The three generators give the three distinct neighbors by the elementary-divisor argument above. They generate $\Gamma$, and a reduced word traces a nonbacktracking path. Consequently

Here $C_2$ is the cyclic group of order two and $*$ is free product. Its usual Cayley graph with these three involutions is the cubic tree. The arithmetic realization of this free product has the additional structure of the second local action, which makes its finite Schreier graphs accessible to the Hecke bound. The abstract free product presentation alone would not impose that bound on arbitrary finite permutation actions.

These involutions invert edges. Their torsion is compatible with the construction: fixed states in a finite quotient give the diagonal contributions in (3). All vertex weights are one by Lemma 7.1.

The Ramanujan bound

The arithmetic theorem and the meaning of its terms

We state the needed spectral input in the form that matches our finite graph. This also specifies the point at which the proof uses results beyond elementary group and local matrix calculations.

The theorem below combines Jacquet–Langlands, in the form explained in [3 Theorem 3.9], with the Hilbert modular Ramanujan theorem [1 Theorem 1].

Let $\mathcal{R}$ be an Eichler order of level $\mathfrak{N}$. The orthogonal complement of the constant functions in its scalar Brandt module transfers, with the Hecke action away from $\mathfrak{N}$, to parallel-weight-two Hilbert cusp forms with trivial central character. For a prime $\mathfrak{l}\nmid\mathfrak{N}$, every corresponding unnormalized Hecke eigenvalue satisfies

This orthogonal complement is taken with respect to the standard Brandt inner product. If the projective unit groups of the left orders are all trivial, this is the ordinary inner product on the class set.

A Hilbert modular form over a totally real field is the analogue of a modular form with one upper-half-plane variable for each real embedding. Parallel weight two means weight two in every variable; for $F = \mathbb{Q}(\sqrt{17})$ the weight is $(2,2)$. Cuspidal means that the form vanishes at the cusps, the boundary points in the modular interpretation. The Jacquet–Langlands correspondence identifies the non-character part of a definite quaternionic module with such cusp forms while preserving the relevant Hecke eigenvalues. This is the analytic interpretation of the finite-dimensional vector space used here.

The scalar quaternionic module consists of complex-valued functions on the ideal classes; no extra representation is attached to a vertex. Its possible one-dimensional exceptional constituents are norm characters, functions obtained by applying a character of a field idele-class group to the reduced norm of an idele. The class-number condition will make all such functions constant. The central character records the action of scalar ideles; it is trivial when every scalar idele acts as the identity.

At a prime away from the level, choose a simultaneous Hecke eigenvector in the cuspidal subspace with eigenvalue $\lambda_{\mathfrak{l}}$. Its two Satake parameters, in the weight-two arithmetic normalization, are the roots $\beta_{\mathfrak{l}}, \gamma_{\mathfrak{l}}$ of

The Ramanujan theorem says that both roots have complex absolute value $\sqrt{\mathop{\mathrm{N}}\mathfrak{l}}$. Their sum is the eigenvalue, so the displayed bound follows by the triangle inequality. In normalized adjacency the same bound is divided by $\mathop{\mathrm{N}}\mathfrak{l}+1$. For comparison, the constant function has eigenvalue $\mathop{\mathrm{N}}\mathfrak{l}+1$, and its polynomial has roots $1$ and $\mathop{\mathrm{N}}\mathfrak{l}$. This explains why identifying and removing the constant constituent is part of the proof.

Checking the hypotheses and proving the graph theorem

Proof of Theorem 2.3. By Proposition 7.2, the entire operator $C_n$ is the unnormalized Hecke operator $T_{\mathfrak{p}}$ on the ideal classes of the Eichler order $\mathcal{E}_n$, of level $\mathfrak{q}^{n+2}$. It has three terms at every vertex. The projective unit groups of all left orders are trivial by Lemma 7.1; hence the usual inner product on this Brandt module is a constant multiple of the ordinary Euclidean inner product.

We identify the noncuspidal part. The one-dimensional automorphic constituents of a definite quaternionic module factor through the reduced norm; see [3], Definition 3.7 and equation (3.8) or [6], Section 7. At every finite place, the reduced norm of the Eichler unit group is the full local unit group: after local conjugation it contains every matrix $\operatorname{diag}(u,1)$ with $u$ a local unit. Thus such characters factor through the narrow ideal class group of $F$. This group is trivial by Lemma 7.1. The noncuspidal subspace is therefore exactly $\mathbb{C}1$, and its Hecke eigenvalue is $3$.

The orthogonal complement $1^\perp$ is the scalar cuspidal quaternionic module. The algebra $D$ is ramified at both real places and at no finite place. The Jacquet–Langlands correspondence [3], Theorem 3.9 identifies this module, with its Hecke action away from the level, with parallel-weight-$(2,2)$ Hilbert cusp forms of level $\mathfrak{q}^{n+2}$. The central character is trivial: finite central ideles act trivially on the ideal-class module because $h_F = 1$ and local central units lie in $U_n$.

The active prime $\mathfrak{p}$ is distinct from $\mathfrak{q}$, so the transferred representations are unramified at $\mathfrak{p}$. For a simultaneous Hecke eigenvector, let $\beta_{\mathfrak{p}}, \gamma_{\mathfrak{p}}$ denote the Satake parameters in the weight-two arithmetic normalization. They satisfy

The Hilbert modular Ramanujan theorem [1 Theorem 1] gives

Its hypotheses include weights $(2,2)$ over this degree-two totally real field, and its conclusion applies at all finite places, including dyadic places. Therefore

Equivalently, one can apply the Ramanujan statement for these prime ideal graphs in [6 Theorem 7.6]; here $\mathfrak{p}\nmid(17)\operatorname{disc}(D)\mathfrak{q}^{n+2}$.

Finally, (32) conjugates $M_n$ to $C_n$ by a permutation matrix preserving constants. Equation (43) therefore gives (5). Since $3 > 2\sqrt{2}$, the eigenspace of $3$ is exactly the one-dimensional constant subspace. A finite symmetric nonnegative matrix with all row sums $3$ has this property if and only if its graph is connected. This proves connectedness and the simplicity of the eigenvalue $3$, and completes the theorem. Compatibility of the intertwiners is (33). $\square$

Acknowledgement

The paper was written with Chat GPT 6 Pro editing assistance and assistance with finding known results needed for Theorem 8.1. The content of the paper was carefully checked by the authors and the authors carry the full responsibility for the content of the paper. The first author thanks Dolciani-Holloran foundation for the support. The second author thanks PSC CUNY for the support.