EXPLICIT CONSTRUCTIONS OF RAMANUJAN COMPLEXES OF TYPE Ã_{d}

ALEXANDER LUBOTZKY, BETH SAMUELS, AND UZI VISHNE

Abstract. In this paper we present for every d ≥ 2 and every local field F of positive characteristic, explicit constructions of Ramanujan complexes which are quotients of the Bruhat-Tits building B_{d}(F) associated with PGL_{d}(F).

1. Introduction

In [LSV] we defined and proved the existence of Ramanujan complexes, see also [B1], [CSZ] and [Li]. The goal of this paper is to present an explicit construction of such complexes.

Our work is based on the lattice constructed by Cartwright and Steger [CS]. This remarkable discrete subgroup Γ of PGL_{d}(F), when F is a local field of positive characteristic, acts simply transitively on the vertices of the Bruhat-Tits building B_{d}(F), associated with PGL_{d}(F). By choosing suitable congruence subgroups of Γ, we are able to present the 1-skeleton of the corresponding finite quotients of B_{d}(F) as Cayley graphs of explicit finite groups, with specific sets of generators. The simplicial complex structure is then defined by means of these generators.

Let \left[{d \atop k}\right]_{q} denote the number of subspaces of dimension k of 𝔽_{q}^{d}.

Theorem 1.1. Let q be a prime power, d ≥ 2, e ≥ 1 (e > 1 if q = 2).

Then, the group G = PGL_{d}(𝔽_{q^{e}}) has an (explicit) set S of \left[{d \atop 1}\right]_{q} +\left[{d \atop 2}\right]_{q} + ⋯ + \left[{d \atop d−1}\right]_{q} generators, such that the Cayley complex of G with respect to S is a Ramanujan complex, covered by B_{d}(F), when F = 𝔽_{q}((y)).

The Cayley complex of G with respect to a set of generators S is the simplicial complex whose 1-skeleton is the Cayley graph Cay(G; S), where a subset of i+1 vertices is an i-cell iff every two vertices comprise an edge. The generators in Theorem 1.1 are explicitly given in Section 9.

Date: February 19, 2004.

This research was supported by the NSF and the BSF (U.S.-Israel).

In the case d = 2 there are two types of Ramanujan graphs, bipartite, and non-bi-partite ([LPS], [Mo], [Lu1]). Here too, given r dividing d, we produce r-partite complexes, by proving an analog of Theorem 1.1 for every subgroup of PGL_{d}(𝔽_{q^{e}}) containing PSL_{d}(𝔽_{q^{e}}). There is also a version of the theorem for subgroups of PGL_{d}(L) where L is a finite local ring.

The paper is organized as follows: In Section 2 we describe affine buildings of type Ã_{d} in general, in the language of O-sublattices of F^{d} (where O is the valuation ring of F). The Cartwright-Steger group Γ is constructed in Sections 3–4. Our construction slightly differs from theirs, but is more convenient for the computations to follow. The simply transitive action of Γ on the building is used in Section 5 to describe the defining relations of Γ.

In Section 6 we present and analyze the finite Ramanujan quotients. In particular, we use [LSV] to show that the complexes constructed here are Ramanujan. We should note that the proof of this result in [LSV] relies on what is called the global ‘Jacquet-Langlands correspondence’ for function fields (a correspondence between automorphic representations of a division algebra and of GL_{d}, cf. [HT, Thm VI.1.1] for the characteristic zero case). The case of function fields is also considered by experts to be true, as the main ingridients of the proof are known, though the task of writing down a complete proof has not been carried out yet.

Originally, Γ is a group of d^{2} × d^{2} matrices over a ring R. Section 8 provides an explicit embedding of Γ into d × d matrices over a finite extension of R. In Section 9 this embedding is refined to identify finite quotients of Γ with subgroups of PGL_{d}(L) which contain PSL_{d}(L), where L is a finite local ring; a detailed algorithm is given, with an example in Section 10. In particular the generators of Γ are given as d×d matrices over 𝔽_{q}[x]. For the convenience of the reader, we include a glossary in the final section.

Added in Proof: We recently learned that Alireza Sarveniazi [Sa] has also given an explicit construction of Ramanujan complexes.

2. Buildings

To every reductive algebraic group over a local field one can associate a building, which is a certain simplicial complex, on which the group acts (see [R]). This complex plays the role of a symmetric space for Lie groups.

Recall that a complex is a structure composed of i-cells, where the 0-cells are called the vertices, and an i-cell is a set of i + 1 vertices.

A complex is simplicial if every subset of a cell is also a cell. The iskeleton is the set of all i-cells in the complex. Buildings are in fact clique complexes, which means that a set of i + 1 vertices is a cell iff every two vertices form a 1-cell. This property holds for quotient complexes, which will be the subject of Section 6.

We will now describe the affine building associated to PGL_{d}(F), where F is a local field. These are called ‘buildings of type Ã_{d−1}’ because of the Dynkin diagram of the associated Weil group (which is isomorphic to S_{d}⋉ℤ^{d−1}). Let O denote the valuation ring of F, choose a uniformizer ϖ (so for F = 𝔽_{q}((y)), O = 𝔽_{q}[[y]] and ϖ = y), and assume O/ϖO = 𝔽_{q}. Consider the O-lattices of full rank in F^{d}. For every lattice L, ϖL is a sublattice, and as 𝔽_{q}-vector spaces L/ϖL ≅ 𝔽_{q}^{d}. We define an equivalence relation by setting L ∼ sL for every s ∈ F^{×}.

Remark 2.1. Let ⟨ϖ⟩ denote the multiplicative subgroup of F^{×} generated by ϖ, and let O^{×} be the invertible elements of O. Then F^{×} = ⟨ϖ⟩ · O^{×}.

Since L = sL for any element s ∈ O^{×}, the equivalence classes have the form [L] = {ϖ^{i}L}_{i∈ℤ}. Let B^{0} be the graph whose vertices are the equivalence classes. There is an edge from [L] to a class x ∈ B^{0}, iff there is a representative L′ ∈ x such that ϖL ⊂ L′ ⊂ L. Notice that this is a symmetric relation, since then ϖL′ ⊂ ϖL ⊂ L′.

The vertices of B^{0} form the 0-skeleton of a complex B, and the edges are the 1-skeleton, B^{1}. As i-cells of B we take the complete subgraphs of size i + 1 of B^{0}, which correspond to flags

ϖL_{0} ⊂ L_{i} ⊂ ⋯ ⊂ L_{1} ⊂ L_{0};

the i-skeleton is denoted B^{i}. It immediately follows that B has (d − 1)-cells (corresponding to maximal flags in quotients L/ϖL). It also follows that there are no higher dimensional cells.

The group GL_{d}(F) acts transitively on lattices by its action on bases. moreover note that the action preserves inclusion of lattices. We call L_{0} = O^{d} ⊆ F^{d} the standard lattice. If τ ∈ GL_{d}(F) has entries in O, then τL_{0} ⊆ L_{0}. The stabilizer of L_{0} in G is thus the maximal compact subgroup GL_{d}(O). According to the definition of the equivalence relation, the scalar matrices of GL_{d}(F) act trivially on B, so the action of GL_{d}(F) induces a well defined action of PGL_{d}(F) on (the vertices of) B, which is easily seen to be an action of an automorphism group. Again, the stabilizer of [L_{0}] is the maximal compact subgroup PGL_{d}(O). The set of vertices can thus be identified with PGL_{d}(F)/PGL_{d}(O).

Since the only ideals of O are powers of ⟨ϖ⟩, The Invariant Factor Theorem for F asserts that any matrix in GL_{d}(F) can be decomposed as aga′ for a, a′ ∈ GL_{d}(O) and g = diag(ϖ^{i_{1}}, …, ϖ^{i_{d}}), where i_{1} ≤ ⋯ ≤ i_{t} are integers. If L = aga′L_{0} = agL_{0}, then ϖ^{−i_{1}}L = a(ϖ^{−i_{1}}g)L_{0} ⊆ L_{0}, and on the other hand ϖ^{−i_{d}}L = a(ϖ^{−i_{d}}g)L_{0} ⊇ L_{0}, so any two lattices of maximal rank are commensurable. Moreover in this case, L_{0}/ϖ^{−i_{1}}L is annihilated by ϖ^{i_{d}−i_{1}}, and so is a module over O/ϖ^{i_{d}−i_{1}}O, a local ring of order q^{i_{d}−i_{1}}. In particular [L_{0} :ϖ^{−i_{1}}L] is a q power.

This basic fact allows to define a color function ϱ: B^{0}→ℤ/d by ϱ(L) = log_{q} [L_{0} :ϖ^{i}L] for large enough i; this function is well defined since [ϖ^{i}L:ϖ^{i+1}L] = q^{d}. Also notice that ϱ([τL_{0}]) = ν_{0}(det(τ)) (mod d), when ν_{0} is the valuation of F. This shows that SL_{d}(F) is color preserving, while on the other hand, τ_{ϖ} = diag(ϖ, 1, …, 1) has determinant ϖ, so ϱ(τ_{ϖ}(L)) = ϱ(L) + 1 for every L. It follows that GL_{d}(F) acts transitively on colors.

The color is additive in the sense that if L′′ ⊆ L′, then ϱ(L′′) = ϱ(L′)+log_{q} [L′:L′′]. Similarly if L ⊆ L_{0} and τ ∈ GL_{d}(F), then ϱ(τL) = ϱ(τL_{0}) + ϱ(L).

The colors provide us with d Hecke operators, defined on functions of B^{0} by summation over the neighbors of fixed color-shift:

A_{k}f(x) = ∑_{y∼x, ϱ(y)−ϱ(x)≡k} f(y).

These operators generate the Hecke algebra H(PGL_{d}(F), PGL_{d}(O)) (see [LSV, Sec. 2] for more details).

For 1 ≤ t < d, let B[t] denote the graph defined on the vertices B^{0}, with the edges (x, x′) ∈ B^{1} for which there are L ∈ x and L′ ∈ x′ such that L′ ⊆ L and [L:L′] = q^{t} (in particular, ϱ(x) − ϱ(x′) = t).

Remark 2.2. If L′ ⊂ L is a sublattice of index q, then [L], [L′] are connected in B^{1}.

Proof. We need to prove that ϖL ⊆ L′, but this is obvious since L/L′ is annihilated (as an O-module) by multiplication by ϖ. □

For every L′ ⊆ L there is a composition series of sublattices L′ = L^{(m)} ⊆ L^{(m−1)} ⊆ ⋯ ⊆ L^{(0)} = L, such that [L^{(i)} :L^{(i+1)}] = q. It follows that B[1] is a connected (directed) subgraph of B. In fact, B[1] determines B^{1}, and thus all of B:

Proposition 2.3. Vertices x, x′ are connected in B^{1} iff there is a chain x_{0}, x_{1}, …, x_{d} ∈ B^{0} such that x_{0} = x_{d} = x, (x_{i}, x_{i+1}) ∈ B[1] for i = 0, …, d − 1, and such that x′ ∈ {x_{1}, …, x_{d−1}}.

Proof. First assume that such a chain exists, and choose representatives L_{i} ∈ x_{i} with L_{d} = ϖL_{0}. By the definition of B[1], we may assume that [L_{i}:L_{i+1}] = q and then L_{d} ⊂ ⋯ ⊂ L_{2} ⊂ L_{1} ⊂ L_{0}. In particular ([L_{i}], [L_{0}]) ∈ B^{1} for every i.

On the other hand, if

(1)  ϖL_{0} ⊂ L′ ⊂ L_{0}

are lattices, we can lift a maximal flag in L/ϖL_{0} ≅ 𝔽_{q}^{d} to a maximal chain of lattices refining (1), resulting in a chain x_{0}, …, x_{d}. □

Corollary 2.4. If (x, x′) ∈ B[t], then there is a path of length t in B[1] from x to x′.

Using this criterion, it is easy to see that if the greatest common divisor (t′, d) equals t, and (x, x′) ∈ B[t′], then there is a path from x to x′ in B[t]. In particular, B[t′] has the same connected components as B[t]. The final result of this section is not needed in the rest of the paper.

We thank the referee for some simplification in the proof of the following proposition.

Proposition 2.5. Let t be a divisor of d. If t divides ϱ(x′)−ϱ(x), then there is a path from x to x′ in the (directed) graph B[t] defined above.

Proof. We may assume x = [L_{0}], and x′ = [L] with L = aga′L_{0} = agL_{0}, a, a′ ∈ GL_{d}(O) and g = diag(ϖ^{i_{1}}, …, ϖ^{i_{d}}). We may assume 0 ≤ i_{1} ≤ ⋯ ≤ i_{d}, and in particular L ⊆ L_{0}. If the claim is true for gL_{0} ⊆ L_{0}, then acting with a we get a chain from aL_{0} = L_{0} to L; we can thus assume a = 1.

Before going on by induction, we multiply L by a power of ϖ so that

(2)  i_{1} ≥ \frac{t}{d − t}(i_{d} − i_{1}).

Now, by assumption, i_{1} + ⋯ + i_{d} = rt for some r ∈ ℕ.

Case 1. If i_{d−t+1} > i_{1}, then we can lower t of the entries i_{2}, …, i_{d}, each by 1, keeping the increasing order. Let i′_{1}, …, i′_{d} denote the resulting values and g′ = diag(ϖ^{i′_{1}}, …, ϖ^{i′_{d}}). Then gL_{0} ⊂ g′L_{0} ⊆ L_{0} with [g′L_{0} :gL_{0}] = q^{t} and ϖg′L_{0} ⊆ gL_{0}, so (g′L_{0}, gL_{0}) ∈ B[t]. Since the condition i_{1} ≥ \frac{d}{t}(i_{d} − i_{1}) still holds (as i_{1} was not changed), we are done by induction on r.

Case 2. Now assume i_{d−t+1} = i_{1}; let j be maximal with i_{j} = i_{1}. If j = d then i_{1} = ⋯ = i_{d} so L ≡ L_{0} and we are done. Therefore assume j < d. Of course j ≥ d − t + 1. If i_{1} = 0 then i_{d} = 0 too by the assumption (2), so L = L_{0} and again we are done. Assume i_{1} > 0 and j < d. In the first step we can lower i_{j+1}, …, i_{d}, but we also have to lower i_{1}, …, i_{t−(d−j)} in order to change exactly t components. We continue lowering the highest entries, using the remaining d − t entries

[figure: 𝔽_{q^{d}}((y)); k_{1} = 𝔽_{q^{d}}(y); F = 𝔽_{q}((y)); k = 𝔽_{q}(y); R; O = 𝔽_{q}[[y]]; R_{T}] Figure 1

i_{t−(d−j)+1}, …, i_{j} whenever necessary. In each of the next d/t − 1 steps, i_{d} is lowered by one with i_{1} unharmed—so at the end our condition (2) is still met. The d/t modules we constructed form a chain in L_{0}, climbing from L using B[t] steps, and ending with indices which now sum up to rt − d, so again we are done by induction. □

Vertices x and x′ for which (t, d) does not divide ϱ(x′) − ϱ(x) cannot be connected in B[t], so we proved that B[t] has (t, d) connected components for every 1 ≤ t < d.

3. The arithmetic lattice

Let 𝔽_{q} denote the field of order q (a prime power), and 𝔽_{q^{d}} the extension of dimension d. Let ϕ denote a generator of the Galois group Gal(𝔽_{q^{d}}/𝔽_{q}). Fix a basis ζ_{0}, …, ζ_{d−1} for 𝔽_{q^{d}} over 𝔽_{q}. ζ_{i} = ϕ^{i}(ζ_{0}).

Extend ϕ to an automorphism of the function field k_{1} = 𝔽_{q^{d}}(y) by setting ϕ(y) = y; the fixed subfield is k = 𝔽_{q}(y), of co-dimension d. Let ν_{y} denote the valuation defined by ν_{y}(a_{m}y^{m} +⋯+a_{n}y^{n}) = m (a_{m} ≠ 0, m < n), and set F = 𝔽_{q}((y)), the completion with respect to ν_{y}, and O = 𝔽_{q}[[y]], its ring of integers.

Let

R = 𝔽_{q} [y, \frac{1}{y}, \frac{1}{1 + y} ] ⊆ k,

and let R_{T} denote the subring

(3)  R_{T} = 𝔽_{q} [y, \frac{1}{1 + y} ] .

Since 1 + y is invertible in O, R_{T} ⊆ O.

For a commutative R_{T} -algebra S (namely a commutative ring with unit which is an R_{T} -module, e.g. k, F, R or R/I for an ideal I⊲R), we denote by y the element y · 1 ∈ S. For such S we define an S-algebra A(S), by

A(S) = ⨁_{i,j=0}^{d−1} Sζ_{i}z^{j},

with the relations

(4)  zζ_{i} = ϕ(ζ_{i})z,  z^{d} = 1 + y.

The center of A(S) is S. We will frequently use the fact that for an R_{T} -algebra S, A(S) = A(R_{T})⊗_{R_{T}} S. It is well known that A(k) is a central simple algebra, and so there is a norm map A(k)^{×}→k^{×}, which induces a norm map A(S)^{×}→S^{×} for every S ⊆ k. The norm map is a homogeneous form of degree d (in the coefficients of the basis elements {ζ_{i}z^{j}}), so the norm is also defined for quotients A(S/I). We remark that 𝔽_{q^{d}}⊗_{𝔽_{q}}S is Galois over S and 1 + y is invertible in S, so A(S) is an Azumaya algebra over S (see [DI], where they are called ‘central separable algebras’). This fact will not be used in the rest of the paper.

If A(S) ≅ M_{d}(S), we say that A(S) is split. We need a criterion for this to happen. If S_{1} = 𝔽_{q^{d}}⊗_{𝔽_{q}}S is a field (so necessarily S is a subfield), then A(S) is the cyclic algebra (S_{1}/S, ϕ, 1+y) = S_{1}[z] with the relations in (4). This is a simple algebra of degree d over its center S. Recall Wedderburn’s norm criterion for cyclic algebras [Jac, Cor. 1.7.5]: the algebra A(S) = (S_{1}/S, ϕ, 1 + y) splits iff 1 + y is a norm in the field extension S_{1}/S. More generally, the exponent of (S_{1}/S, ϕ, 1 + y) (i.e. its order in the Brauer group Br(S)) is the minimal i > 0 such that (1 + y)^{i} is a norm. In particular, if this exponent is d = [S_{1} :S], A(S) is a division algebra (since the exponent of a central simple algebra is always bounded by the degree of the underlying division algebra).

The algebra A(R) will later be used to construct the desired complexes. As mentioned above, A(R) ⊆ A(k), k being the ring of fractions of R; moreover, A(k) is the ring of central fractions of this algebra,

A(k) = (R − {0})^{−1}A(R).

We now consider completions of A(k). The global field k = 𝔽_{q}(y) has the minus degree valuation, defined for f, g ∈ 𝔽_{q}[y] by ν(f/g) = deg(g) − deg(f). Also recall that the other nonarchimedean discrete valuations of 𝔽_{q}(y) are in natural correspondence with the prime polynomials of 𝔽_{q}[y]. For a prime polynomial p ∈ 𝔽_{q}[y], the valuation is defined by ν_{p}(p^{i}f/g) = i, where f, g are polynomials prime to p. The ring of p-adic integers in k is 𝔽_{q}[y]_{p} = {f/g: (p, g) = 1}. The completion

\xymatrix{GL_{d}(F) \ar[r]^{det} & F^{×} \\ A(R)^{×} \ar@{^{(}->}[u] \ar[r]^{N} & R^{×} \ar@{^{(}->}[u]}

Figure 2

with respect to a valuation ν = ν_{p} is k_{ν} = 𝔽_{q}[y]_{p}((p)) = {∑_{i=−v}^{∞} α_{i}p^{i}} (which we will also denote by k_{p}). The ring of integers of k_{p} is O_{p} = 𝔽_{q}[y]_{p}[[p]]. The notation ν_{1/y} is used for the degree valuation, since the completion of k with respect to this valuation is 𝔽_{q}((1/y)); moreover, filtration by the ideal ⟨1/y⟩ of the ring of integers 𝔽_{q}[[1/y]] determines the valuation.

The Albert-Brauer-Hasse-Noether Theorem describes division algebras over k in terms of their local invariants, which translates to an injection Br(k)→⊕Br(k_{p}). More precisely, the d-torsion part of Br(k_{p}) is cyclic of order d for every valuation ν_{p}. Since k_{1,p}/k_{p} is always unramified (where k_{1,p} is the completion of k_{1} under ν_{p}), these d classes can be written as the cyclic algebras (k_{1,p}/k_{1}, ϕ, ϖ^{i}) for i = 0, …, d−1, where ϖ is a uniformizer. If (k_{1}/k, ϕ, c) is a cyclic k-algebra, the local invariants are determined by the values ν(c) ([P, Chaps. 17–18] is a standard reference, though the focus is on number fields).

There are only two valuations ν of k for which ν(1 + y) ≠ 0, namely ν_{1+y} and ν_{1/y}, for which the values are 1 and −1, respectively. We thus have

Proposition 3.1. The completions A(𝔽_{q}((1/y))) and A(𝔽_{q}((1 + y))) of A(k) are division algebras. On the other hand, for any other completion k_{ν} of k, A(k_{ν}) splits.

In particular

(5)  A(R) ⊆ A(k)⊗_{k}F = A(F) ≅ M_{d}(F).

The same argument embeds

(6)  A(R_{T}) ⊆ A(O) ≅ M_{d}(O).

We use the algebras A(S) to define algebraic group schemes. For an R_{T} -algebra S, let G̃′(S) = A(S)^{×}, the invertible elements of A(S), and G′(S) = A(S)^{×}/S^{×}. Recall that for every R_{T} -algebra S, one can define a multiplicative function A(S)→S^{×} called the reduced norm (e.g. by taking the determinant in a splitting extension of S). In particular, the diagram in Figure 2 commutes. We can thus define G̃′_{1}(S) as the set of elements of G̃′(S) of norm 1, and G′_{1}(S) as the image of G̃′_{1}(S) under the map G̃′(S)→G′(S) (see the square in the middle of Figure 5).

Remark 3.2. The sequence

1⟶μ_{d}(S)⟶G̃′_{1}(S)⟶G′_{1}(S)⟶1

is exact, where μ_{d}(S) is the group of d-roots of unity in S.

These group schemes are parallel to the classical groups G̃(S) = GL_{d}(S), G(S) = PGL_{d}(S), G̃_{1}(S) = SL_{d}(S) and G_{1}(S) = PSL_{d}(S). If A(S) is a matrix ring, we have that G̃′(S) = G̃(S) and G′(S) = G(S).

It is useful to have equivalent definitions for the groups G′(S) for various rings S. Fix the ordered basis

{ζ_{0}, …, ζ_{d−1}, ζ_{0}z, …, ζ_{d−1}z, …, ζ_{0}z^{d−1}, …, ζ_{d−1}z^{d−1}}

of A(S) over S. Conjugation by an invertible element a ∈ A(S) is a linear transformation of the algebra. Let i_{S}: G′(S)→GL_{d^{2}}(S) be the induced embedding. If S ⊆ S′, then the diagram

\xymatrix{G′(S′) \ar[r]^{i_{S′}} & GL_{d^{2}}(S′) \\ G′(S) \ar@{^{(}->}[u] \ar[r]^{i_{S}} & GL_{d^{2}}(S) \ar@{^{(}->}[u]}

commutes.

Proposition 3.3. Let R_{T} ⊆ S ⊆ S′ be commutative rings, such that S is a Noetherian unique factorization domain. Then

i_{S}G′(S) = i_{S′}G′(S′) ∩ GL_{d^{2}}(S),

the intersection taken in GL_{d^{2}}(S′).

Proof. The inclusion i_{S}G′(S) ⊆ i_{S′}G′(S′) ∩ GL_{d^{2}}(S) is trivial since A(S) ⊆ A(S′). Let α ∈ i_{S′}G′(S′) ∩ GL_{d^{2}}(S), then α is an isomorphism of algebras (since it is induced by an element of A(S′)) and preserves S (as it belongs to GL_{d^{2}}(S)). It is thus an automorphism of A(S), which must be inner [AG, Thm. 3.6]. □

The proposition covers, in particular, S = R_{T} , R, k, k_{ν}, O_{ν}, and R̄_{T}, and R̄ which are defined in Section 8, with an arbitrary extension S′ (usually taken to be from the same list).

Proposition 3.4. G′(R) is a discrete subgroup of G(F).

Proof. Let p = 1 + y. The ring R = 𝔽_{q}[\frac{1}{y}, y, \frac{1}{1+y}] embeds (diagonally) as a discrete subgroup of the product

F × k_{1/y} × k_{p}.

This can be seen by letting a_{n} = \frac{f_{n}(y)}{y^{in}(1+y)^{jn}} be a sequence of non-zero elements in R (with f_{n}(λ) ∈ 𝔽_{q}[λ] and i_{n}, j_{n} ≥ 0) such that a_{n}→0. We then have that ν_{y}(a_{n})→∞, which implies i_{n} = 0 for n large enough and ν_{y}(f_{n}(y))→∞. Likewise, ν_{p}(a_{n})→∞, so j_{n} = 0 for n large enough. This implies that ν_{1/y}(a_{n})→ − ∞, which is a contradiction.

It follows that the diagonal embedding of G′(R) into

G′(F) × G′(k_{1/y}) × G′(k_{p})

is discrete. But an algebraic group over a local field is compact iff it has rank zero [PR]. Therefore, by Proposition 3.1, G′(k_{1/y}) and G′(k_{p}) are compact, and G′(R) is discrete in the other component G′(F) = G(F). □

In fact, from general results it follows that G′(R) is a cocompact lattice in G′(F), but we will show it directly when we demonstrate that G′(R) acts transitively on the vertices of the affine building of G(F) = PGL_{d}(F).

Consider G(O) = PGL_{d}(O), a maximal compact subgroup of G(F), which is equal to G′(O) by Equation (6). Viewing K = i_{O}G′(O) and i_{R}G′(R) as subgroups of i_{F} G′(F) ⊆ GL_{d^{2}}(F), the intersection

(7)  i_{R_{T}} G′(R_{T}) = K ∩ i_{R}G′(R)

is finite, being the intersection of discrete and compact subgroups (note that R ∩ O = R_{T}).

Proposition 3.5. G′(R_{T}) is a semidirect product of ⟨z⟩ ≅ ℤ/dℤ acting on 𝔽_{q^{d}}^{×}/𝔽_{q}^{×}.

Proof. Recall that R_{T} = 𝔽_{q}[y, 1/(1+y)], so that A(R_{T}) = 𝔽_{q^{d}}[y, 1/(1+ y), z] with the relations zαz^{−1} = ϕ(α) (α ∈ 𝔽_{q^{d}}) and z^{d} = 1+y. Setting y = z^{d} − 1, we see that A(R_{T}) = 𝔽_{q^{d}}[z, z^{−1}] is a skew polynomial ring with one invertible variable over 𝔽_{q^{d}}. Every element of A(R_{T}) has a monomial αz^{r} (α ∈ 𝔽_{q^{d}}^{×}) with r maximal, called the upper monomial (with respect to z), and similarly every element has a lower monomial. The upper monomial of a product fg is equal to the product of the respective upper monomial, and likewise for the lower monomials.

Now let f, g ∈ A(R_{T}) be elements with fg = 1, then the product of the upper monomials and that of the lower monomials are both equal to 1, proving that f and g are monomials. Thus, the invertible elements of A(R_{T}) are G̃(R_{T}) = {αz^{i}: α ∈ 𝔽_{q^{d}}^{×}, i ∈ ℤ}. The result is obtained by taking this modulo the center. □

4. A simply transitive action on B

We continue with the notation of the last section. The embedding (5) of A(R) into M_{d}(F) induces embeddings G̃′(R) ↪ GL_{d}(F) and G′(R) ↪ PGL_{d}(F), so G′(R) acts on B^{0}. Notice that G′(k) is dense in G′(F) = G(F), so its action on B^{0} is transitive.

In [CS], Cartwright and Steger present a subgroup of G′(k), which acts simply transitively on the vertices of the building B. Identifying B^{0} with a group, when possible, is an important tool in the description of finite quotients of B. We will use the Cartwright-Steger group, constructed in a different way. In particular we construct the group as a subgroup of G′(R), which is easily shown to be discrete. The proof that it acts transitively relies on the existence of an element of the appropriate norm, and that the action is simple is seen by a relatively easy computation of the group scheme over various rings.

Recall that A(R) = R[ζ_{i}, z] where zζ_{i}z^{−1} = ϕ(ζ_{i}) and z^{d} = 1 + y, and let

b = 1 − z^{−1} ∈ A(R).

Proposition 4.1. The reduced norm of b in A(R) is y/(1 + y).

Proof. Recall that A(R) ⊆ A(k) and that the restriction of the norm function of A(k) to A(R) is the norm function of A(R). As is the case for matrices, if a ∈ A(R) generates a subalgebra of dimension d, its norm N(a) is the free coefficient in the characteristic polynomial of a multiplied by (−1)^{d}.

The minimal polynomial of z is λ^{d}−(1+y), so that N(z) = (−1)^{d−1}(1+ y). Likewise, the minimal polynomial of z −1 is (λ+1)^{d} −(1+y), with the free coefficient −y, so that N(z − 1) = (−1)^{d−1}y. Finally, since b = z^{−1}(z − 1), N(b) = N(z − 1)/N(z) = y/(1 + y). □

Since 1 + y is invertible in O, we claim

Corollary 4.2. N(b) ≡ y (mod O^{×}).

Under the embedding (6), b ∈ A(R_{T}) ⊆ M_{d}(O), so bL_{0} ⊆ L_{0}, where L_{0} = O^{d} is the standard lattice. By the corollary, and since the diagram in Figure 2 commutes, we have [L_{0} :bL_{0}] = q. Note that b is not invertible in A(R_{T}) (since the norm y/(1 + y) is not invertible in R_{T}), but b is invertible in A(R).

Let Ω denote the set of neighbors of [L_{0}] in B which have color 1; they correspond to sublattices of index q in L_{0}. Consider the element

b_{u} = ubu^{−1} = 1 − \frac{u}{ϕ(u)}z^{−1}

where u ∈ 𝔽_{q^{d}}^{×} ⊆ A(R)^{×}. The embedding A(R) ⊆ M_{d}(F) extends the regular embedding 𝔽_{q^{d}} ↪ M_{d}(𝔽_{q}) (via the basis ζ_{0}, …, ζ_{d−1}), and in particular it takes u to a matrix with coefficients in 𝔽_{q}. This proves that uL_{0} = L_{0}, and since GL_{d}(F) preserves the structure of B, u permutes the vertices in Ω. Moreover, the sublattices of index q of L_{0} correspond to the points of the projective space 𝔽_{q^{d}}^{×}/𝔽_{q}^{×} via the isomorphism L_{0}/yL_{0} ≅ 𝔽_{q^{d}}. The action of u on the latter space is by multiplication, so 𝔽_{q^{d}}^{×} ⊆ A(R)^{×} acts transitively on Ω. Finally, we have that b_{u}(L_{0}) = ubu^{−1}L_{0} = u(bL_{0}), so we proved Proposition 4.3. For every lattice L_{1} ∈ Ω, there is an element u ∈ 𝔽_{q^{d}}^{×} (unique up to multiplication by 𝔽_{q}^{×}) such that b_{u}L_{0} = L_{1}.

Definition 4.4. Let Γ̃ denote the subgroup

(8)  Γ̃ = ⟨b_{u}: u ∈ 𝔽_{q^{d}}^{×}/𝔽_{q}^{×}⟩

of G̃′(R) = A(R)^{×}, and let Γ be the image of Γ̃ under the projection G̃′(R)→G′(R). Proposition 4.5. Γ acts transitively on B^{0}. Proof. We show that L_{0} can be taken to any of its sublattices L by an element of Γ. The proof is by induction on [L_{0} :L]. If [L_{0} :L] = q, then L ∈ Ω and b_{u}L_{0} = L for some u. Assume [L_{0} :L] > q, and let L ⊆ L′ ⊆ L_{0} be an intermediate sublattice such that [L′:L] = q. By the induction hypothesis there is an element c ∈ Γ such that cL_{0} = L′. The lattices in cΩ are the sublattices of index q of L′, so for some u ∈ 𝔽_{q^{d}}^{×}, we have that c(b_{u}L_{0}) = L, which proves our claim. □

Corollary 4.6. If L ⊆ L_{0} and [L_{0} :L] = q^{ℓ}, then there are u_{1}, …, u_{ℓ} ∈ 𝔽_{q^{d}}^{×}/𝔽_{q}^{×} such that [L] = b_{u_{1}} … b_{u_{ℓ}}[L_{0}].

Moreover, if L ⊆ L′ ⊆ L_{0} where [L_{0} :L′] = q^{k} and [L′] = b_{u_{1}} … b_{u_{k}}[L_{0}], then for suitable u_{k+1}, …, u_{ℓ} we have [L] = b_{u_{1}} … b_{u_{k}}b_{u_{k+1}} … b_{u_{ℓ}}[L_{0}].

Let R_{0} = 𝔽_{q}[1/y]. As R_{0} does not contain R_{T}, A(R_{0}) is not defined, so we cannot define G′(R_{0}) in the usual way. However, following Proposition 3.3, we set G′(R_{0}) = i_{k}G′(k) ∩ GL_{d^{2}}(R_{0}).

As mentioned in the introduction, Cartwright and Steger present in [CS] a group Γ′ which acts simply transitively on B^{0}. Their group is defined as follows:

Definition 4.7. The group Γ′ is composed of the elements of G′(R_{0}) which modulo 1/y are upper triangular with identity d×d blocks on the diagonal.

A careful computation, using b_{u}^{−1} = 1 + \frac{1}{y} ∑_{i=0}^{d−1} uϕ^{i}(u)^{−1}z^{i}, reveals that

(9) b_{u}(ζz^{k})b_{u}^{−1} = ζz^{k} + f_{u,k}(ζ) ∑_{i=0}^{k−1} \frac{u}{ϕ^{i}(u)}z^{i} + \frac{1}{y}f_{u,k}(ζ) ∑_{i=0}^{d−1} \frac{u}{ϕ^{i}(u)}z^{i}

for every 0 ≤ k < d and ζ ∈ 𝔽_{q^{d}}, where f_{u,k}(ζ) = \frac{ϕ^{k}u}{u}ζ − \frac{ϕ^{k−1}u}{ϕ^{−1}u}ϕ^{−1}ζ.

It follows that b_{u} ∈ Γ′, so Γ = ⟨b_{u}⟩ ⊆ Γ′. This leads to an easy proof of the main property of Γ:

Proposition 4.8. The group Γ acts simply transitively on B^{0}, namely, for K = G(O),

(10)  Γ · K = G(F),
(11)  Γ ∩ K = 1.

In particular, Γ = Γ′.

Proof. The first equation, equivalent to Γ acting transitively on B^{0} = G(F)/K, was proved in Proposition 4.5. To compute the intersection, note that Γ ∩ K ⊆ Γ′ ∩ K ⊆ G′(R) ∩ K = G′(R_{T}) by Equation (7), so Γ ∩ K ⊆ G′(R_{T}) ∩ Γ′. Let ζz^{j} be an element of G′(R_{T}) ∩ Γ′ for ζ ∈ 𝔽_{q^{d}}^{×} and j = 0, …, d − 1 (see Proposition 3.5). By the definition of Γ′, the d^{2} × d^{2} matrix representing ζz^{j} should be upper triangular modulo 1/y. Now, (ζz^{j})z(ζz^{j})^{−1} = \frac{ζ}{ϕ(ζ)}z, so ζ ∈ 𝔽_{q}^{×}. Furthermore for every a ∈ 𝔽_{q^{d}}, (ζz^{j})a(ζz^{j})^{−1} = ϕ^{j}(a), proving that j = 0 and ζz^{j} is central; thus Γ′ ∩ K = 1. This proves that Γ′ acts simply transitively on G(F)/K, and since Γ ⊆ Γ′, these groups are equal. □

Proposition 4.9. The group Γ is a normal subgroup of G′(R), and G′(R) = G′(R_{T})⋉Γ. Moreover,

(12)  G′(R_{0}) = G′(R).

Proof. Let g ∈ G′(R), and write g = γa for γ ∈ Γ ⊆ G′(R) and a ∈ K. Then a = γ^{−1}g ∈ K ∩ G′(R) = G′(R_{T}), by Equation (7), and G′(R) = Γ · G′(R_{T}).

The generators of Γ are permuted by G′(R_{T}): (ζ_{i}z^{j})b_{u}(ζ_{i}z^{j})^{−1} = b_{ζ_{i}ϕ^{j}(u)}, so Γ⊲G′(R). Moreover, Γ ∩ G′(R_{T}) ⊆ Γ ∩ K = 1, proving the second claim.

Finally, G′(R_{0}) ⊆ G′(R) but direct inspection using Equation (9), shows that Γ and G′(R_{T}) are contained in GL_{d^{2}}(R_{0}) (see [CS, Thm. 2.6]).

□

\xymatrix{Γ \ar[r]^{det} \ar[dr]^{δ} \ar[d]_{γ↦γ[L_{0}]} & F^{×}/F^{×}^{d}O^{×} \ar[d]^{y↦1} \\ B_{0} \ar[r]^{ϱ} & ℤ/dℤ}

Figure 3

Since Γ acts simply transitively, we can identify B^{0} with Γ by γ ↦ γ[L_{0}]. Recall that by Equation (5), Γ ⊆ PGL_{d}(F). The determinant (modulo scalars) thus takes γ ↦ det(γ) · F^{×}^{d} ∈ F^{×}/F^{×}^{d}. Considering this modulo O^{×} (which is superfluous if d is prime to q), we obtain the cyclic group F^{×}/F^{×}^{d}O^{×} ≅ ⟨y⟩/⟨y^{d}⟩. Moreover, since ϱ(b_{u}x) = ϱ(x) + 1 and N(b_{u}) ≡ y (mod O^{×}) by Corollary 4.2, the diagram in Figure 3 commutes. We let δ denote the color map Γ→ℤ/d. Letting Γ_{1} = Ker(δ), the short sequence

1⟶Γ_{1}⟶Γ ⟶^{δ} ℤ/dℤ⟶1

is exact.

Corollary 4.10. [Γ:Γ_{1}] = d.

5. The geometry of Γ

By definition, Γ is generated by the elements b_{u} = u(1 − z^{−1})u^{−1} of G′(R), where u ranges over 𝔽_{q^{d}}^{×}/𝔽_{q}^{×}.

Since b_{u} = 1 − \frac{u}{ϕ(u)}z^{−1}, for every u, there is a unique r ∈ 𝔽_{q^{d}}^{×} with N(r) = 1, such that b_{u} = b_{(r)} = 1 − rz^{−1}, where N = N_{𝔽_{q^{d}}/𝔽_{q}} is the norm map.

Remark 5.1. For every u ≠ v ∈ 𝔽_{q^{d}}^{×}/𝔽_{q}^{×} there are unique u′, v′ ∈ 𝔽_{q^{d}}^{×}/𝔽_{q}^{×} such that

(13)  b_{u}b_{u′} = b_{v}b_{v′}.

Proof. The conceptual reason is that since b_{u}L_{0} ≠ b_{v}L_{0}, their intersection L = b_{u}L_{0} ∩ b_{v}L_{0} is a submodule of index q^{2} of L_{0} (which contains yL_{0}), and so by Corollary 4.6 there are unique u′, v′ such that L = b_{u}b_{u′}L_{0} = b_{v}b_{v′}L_{0}. Since Γ acts simply transitively, b_{u}b_{u′} = b_{v}b_{v′}.

Computationally, assume first d > 2. Since (1 − rz^{−1})(1 − r′z^{−1}) = 1 − (r + r′)z^{−1} + rϕ^{−1}(r′)z^{−2}, b_{(r)}b_{(r′)} = b_{(s)}b_{(s′)} in Γ iff

r + r′ = s + s′ and rϕ^{−1}(r′) = sϕ^{−1}(s′).

The unique solution is r′ = \frac{s−r}{ϕs−ϕr}ϕ(s) and s′ = \frac{s−r}{ϕs−ϕr}ϕ(r), where r′ and s′ indeed have norm 1.

If d = 2 then (as elements of Γ̃) b_{(−r)}b_{(r)} = 1 − \frac{rϕ(r)}{1+y}, which is in the center R = Z(A(R)). Therefore in Γ, b_{(r)}^{−1} = b_{(−r)}. Now the unique solution to the above equation is b_{(r)}b_{(−r)} = 1 = b_{(s)}b_{(−s)}. □

The following is essentially a reformulation of the simply connectedness of B.

Theorem 5.2. Let Γ′ be the abstract group generated by {x_{u}: u ∈ 𝔽_{q^{d}}^{×}/𝔽_{q}^{×}}, with the relations x_{u′}x_{u} = x_{v′}x_{v} whenever b_{u′}b_{u} = b_{v′}b_{v} in Γ, and a single relation x_{u_{1}} … x_{u_{d}} = 1 for some u_{1}, …, u_{d} such that

(14)  r = b_{u_{1}} … b_{u_{d}} = 1

in Γ. Then x_{u} ↦ b_{u} is an isomorphism Γ′→Γ.

Proof. Since Γ acts simply transitively, b_{u_{1}}^{ϵ_{1}} … b_{u_{n}}^{ϵ_{n}} = 1 iff b_{u_{1}}^{ϵ_{1}} … b_{u_{n}}^{ϵ_{n}}L = y^{i}L for some lattice L and i ∈ ℤ.

[figure: L_{0}; b_{u_{1}}L_{0}; b_{v_{1}}L_{0}; δL_{0}; γL_{0}] Figure 4

We first claim that every equation γ = b_{u_{1}} … b_{u_{n}} = b_{v_{1}} … b_{v_{n}} (both expressions of the same length) can be obtained from the relations of type (13). Indeed, for n ≤ 2 the claim is obvious.

If u_{n} = v_{n} then we are done by induction, so we assume u_{n} ≠ v_{n}. By the above remark there are u′ and v′ such that δ = b_{u_{n}}b_{u′} = b_{v_{n}}b_{v′}, and then δL_{0} = b_{u_{1}}L_{0} ∩ b_{v_{1}}L_{0} is of index q^{2} in L_{0}, and contains γL_{0}. By Corollary 4.6 there are w_{3}, …, w_{n} such that γL_{0} = δb_{w_{3}} … b_{w_{n}}L_{0}. By induction the equations b_{u_{2}} … b_{u_{n}} = b_{u′}b_{w_{3}} … b_{w_{n}} and b_{v_{2}} … b_{v_{n}} = b_{v′}b_{w_{3}} … b_{w_{n}} follow from the relations (13), and so is the case with b_{u_{1}}b_{u_{2}} … b_{u_{n}} = b_{u_{1}}b_{u′}b_{w_{3}} … b_{w_{n}} = b_{v_{1}}b_{v′}b_{w_{3}} … b_{w_{n}} = b_{v_{1}}b_{v_{2}} … b_{v_{n}}, which proves our claim. In particular, all the relations of the form (14) are equivalent modulo the relations (13).

Let u ∈ 𝔽_{q^{d}}^{×}/𝔽_{q}^{×}. Using Corollary 4.6 we see that b_{u}^{−1} is equal to a product of d − 1 generators. Given a relation, we can thus assume it has the form b_{u_{1}} … b_{u_{n}} = 1. Then b_{u_{1}} … b_{u_{n}}L_{0} = y^{i}L_{0} where n = di, so b_{u_{1}} … b_{u_{n}} = r^{i} is an equality of elements of equal length, which follows from the relations (13) by the above claim.

□

Remark 5.3. If d is a power of char F, then equation (14) takes a particularly simple form: b_{1}^{d} = (1 − z^{−1})^{d} = 1 − z^{−d} = \frac{y}{1+y} ∈ R^{×}, so b_{1}^{d} = 1 in Γ.

From the theorem, together with the case d = 2 of Remark 5.1, we obtain

Corollary 5.4. If d = 2, then the defining relations of Γ are b_{(r)}^{−1} = b_{(−r)}. In particular, if q is odd then Γ is free on \frac{q+1}{2} generators, and if q is even then Γ is a free product of q + 1 cyclic groups of order 2.

6. Finite quotients of B

In this section we specify quotients of Γ, whose Cayley graphs (with respect to the generators b_{u}) define Ramanujan complexes. These quotients are shown to be subgroups of PGL_{d} which contain PSL_{d}, over a pre-determined finite local ring.

Recall the definitions of G̃′, G̃′_{1}, G′ and G′_{1} from Section 3. Let S be an R_{T} -algebra, and I⊲S an ideal. The map S→S/I induces an epimorphism of algebras A(S)→A(S/I). It also induces a homomorphism G̃′(S)→G̃′(S/I) (which, in general, is not onto). The kernel of this map is called the congruence subgroup of G̃′(S) with respect to I and denoted by G̃′(S, I). We define the group G′(S, I) as the image of G̃′(S, I) under the natural mapping G̃′(S)→G′(S), and G̃′_{1}(S, I) = G̃′_{1}(S) ∩ G̃′(S, I). Likewise G′_{1}(S, I) = G′(S, I) ∩ G′_{1}(S). (Notice that G′_{1}(S, I) = {aS^{×}: a ∈ G̃′_{1}(S), a ∈ S^{×} + IA(S)}, while G̃′_{1}(S, I) = {a: a ∈ G̃′_{1}(S), a ∈ 1 + IA(S)}, so the map

G̃′_{1}(S, I)→G′_{1}(S, I)

induced by G̃′(S)→G′(S) may not be onto). See Figure 5.

Let I⊲R. We define the congruence subgroup of Γ to be

(15)  Γ(I) = Γ ∩ G′(R, I),

[figure: G̃′(S, I); G̃′(S); G̃′(S/I); G̃′_{1}(S, I); G̃′_{1}(S); G̃′_{1}(S/I); G′(S, I); G′(S); G′(S/I); G′_{1}(S, I); G′_{1}(S); G′_{1}(S/I)] Figure 5

a normal subgroup of G′(R) (by Proposition 4.9). Recall that Γ acts simply transitively on the vertices of B = G(F)/K, where K = G(O). The set of vertices in the quotient complex B_{I} = Γ(I)\G(F)/K is isomorphic to Γ/Γ(I). To make this an isomorphism of complexes, we need to define a complex structure on Γ/Γ(I).

The generators {b_{u}} correspond to the neighbors of color 1 of [L_{0}]. More generally, by Corollary 4.6 the neighbors of color k correspond to the products b_{u_{1}} … b_{u_{k}} which are headers of a product of d generators which equals 1. The 1-skeleton of B_{I} is thus the Cayley graph of Γ/Γ(I) with respect to these generators (for k = 1, …, d − 1), and there are ‘partial Laplacian operators’ A_{k} of Γ/Γ(I), induced from the Hecke operators of B. Frequently, these are the colored Laplacian operators (i.e. they can be defined for Γ/Γ(I) directly); we address this issue towards the end of this section. The higher dimensional cells of Γ/Γ(I) are then defined to make it a clique complex. Thus, Γ(I)\G(F)/K and Γ/Γ(I) become isomorphic complexes.

Remark 6.1. If f(λ) ∈ 𝔽_{q}[λ] is divisible by λ, then G′(R_{0}, ⟨f(1/y)⟩) ⊆ G′(R_{0}, ⟨1/y⟩) ⊆ Γ, by Definition 4.7 of Γ′ and Equation (12). In this case Γ(I) = G′(R_{0}, I) (where I = ⟨f(1/y)⟩) so Γ(I)\B ≅ Γ/Γ(I).

Let C = {(z_{1}, …, z_{d}) ∈ ℂ^{d}: |z_{i}| = 1, z_{1} … z_{d} = 1} and σ: C→ℂ^{d−1} the map defined by (z_{1}, …, z_{d}) ↦ (λ_{1}, …, λ_{d−1}), where

λ_{k} = q^{k(d−k)/2}σ_{k}(z_{1}, …, z_{d})

and σ_{k} are the symmetric functions. Then 𝔖_{d} = σ(C) is the simultaneous spectrum of the Hecke operators A_{1}, …, A_{d−1} acting on B [LSV, Thm. 2.9].

Recall [LSV] that B_{I} is called a Ramanujan complex if the eigenvalues of every non-trivial simultaneous eigenvector v ∈ L^{2}(B_{I}), A_{k}v = λ_{k}v, satisfy (λ_{1}, …, λ_{d−1}) ∈ 𝔖_{d}. It can be shown that the closure of the union of the sets of simultaneous eigenvalues over any family of quotients of B (with unbounded injective radius) contains 𝔖_{d}.

The following theorem relies on one of the main results of [LSV], for which we assume the global Jacquet-Langlands correspondence for function fields. See the introduction for more details.

Theorem 6.2. For every d ≥ 2 and every 0 ≠ I⊲R, the Cayley complex of Γ/Γ(I) is a Ramanujan complex.

Proof. Write I = Rp for some polynomial p ∈ 𝔽_{q}[y] which is prime to y and 1 + y, then I ∩ R_{0} is generated by y^{−e}p where e = deg(p). Let I′ = ⟨y^{−e−1}p⟩⊲R_{0}. Set N = G′(R_{0}, I′), then N ⊆ Γ by Remark 6.1, and hence N ⊆ Γ(I) (this property is not satisfied by the more ‘natural’ candidate G′(R_{0}, ⟨y^{−e}p⟩)).

In the notation of [LSV], D = A(k) is the division algebra used to define G′ = D^{×}/Z^{×}, F is the completion of k with respect to ν_{0} = ν_{y}, and the ramification places are T = {ν_{1/y}, ν_{1+y}}. The ring R_{0} is

R_{0} = ⋂_{ν∈V−{ν_{0}}}(k ∩ O_{ν}) = 𝔽_{q}[1/y],

where V is the set of valuations of k. Since

R = ⋂_{ν∈V−T ∪{ν_{0}}}(k ∩ O_{ν}),

every ideal of R restricts to an ideal of R_{0} which is prime to T.

Note that I′ is prime to ν_{1+y} (since ν_{1+y}(p) = 0). In [LSV, Thm. 1.3(a)] we prove that X = N\B = N\ΓK/K is Ramanujan. This complex is isomorphic to Γ/N by NγK ↦ γN, so Γ/N is Ramanujan. Since N ⊆ Γ(I), Γ/Γ(I) is also Ramanujan. □

Our next goal is to identify Γ/Γ(I) as an abstract group. We assume that I is a power of a prime ideal (so R/I is a finite local ring). Let ⟨p⟩ = \sqrt{I} denote the radical of I, so I = ⟨p^{s}⟩ for some s ≥ 1, where p ∈ 𝔽_{q}[y] is prime. By definition of Γ(I), we have that

Γ/Γ(I) = Γ/(Γ ∩ G′(R, I))
≅ (Γ · G′(R, I))/G′(R, I)
⊆ G′(R)/G′(R, I)
↪ G′(R/I) ≅ PGL_{d}(R/I),

where the final isomorphism follows from Wedderburn’s theorem that A(R/I) ≅ M_{d}(R/I).

Theorem 6.3. The map G′_{1}(R)→G′_{1}(R/I) is onto.

Proof. Let 𝔸 denote the ring of adelés over k, and 𝔸_{0} = 𝔸/F. Since G̃′_{1} is connected, simply connected and simple, and G̃′_{1}(F) is non-compact, the strong approximation theorem ([PR, Thm. 7.2], [Pr]) asserts that G̃′_{1}(k)G̃′_{1}(F) is dense in G̃′_{1}(𝔸) (see [LSV, Sec. 3.2]). Therefore, G̃′_{1}(k) is dense in G̃′_{1}(𝔸_{0}). Let U = G̃′_{1}(k_{1/y})G̃′_{1}(k_{1+y}) ∏_{ν≠ν_{1/y},ν_{1+y},ν_{y}} G̃′_{1}(O_{ν}),

an open subgroup of G̃′_{1}(𝔸_{0}). Then G̃′_{1}(R) = G̃′_{1}(k) ∩ U is dense in U.

In particular, G′_{1}(R) is dense in G′_{1}(O_{p}), where O_{p} is the ring of integers in the completion k_{p}. (Notice that R/I ≅ O_{p}/P_{p}^{s} where P_{p} is the maximal ideal of O_{p}). Since G′_{1}(R/I) ≅ PSL_{d}(R/I) which is finite, it is enough to show that the map from G′_{1}(O_{p}) to G′_{1}(R/I) = G′_{1}(O_{p}/P_{p}^{s}) is onto.

Let c ∈ G′_{1}(O_{p}/P_{p}^{s}), so c is an automorphism of A(O_{p}/P_{p}^{s}) which is induced by an element c̃ of norm one in A(O_{p}/P_{p}^{s}). Lift it to an element ã of A(O_{p}), then N(ã) ∈ O_{p} and is equivalent to 1 modulo P_{p}^{s}; thus ã is invertible and in G′(O_{p}).

If d is prime to |O_{p}/P_{p}|, then there is some α ∈ O_{p} such that α^{d} = N(ã), so N(α^{−1}ã) = 1. Thus the automorphism induced by α^{−1}ã on A(O_{p}) is in G′_{1}(O_{p}), call it a. Now a covers c, and we are done.

When d is not necessarily prime to |O_{p}/P_{p}|, we construct an element of A(O_{p}) by induction. Let v ∈ 𝔽_{q^{d}} be an element with tr_{𝔽_{q^{d}}/𝔽_{q}}(v) = 1. Take ã_{s} = ã. Assume N(ã_{i}) ≡ 1 (mod p^{i}) for some i ≥ s. Write N(ã_{i}) ≡ 1 + gp^{i} (mod p^{i+1}) for some g ∈ R. Let ã_{i+1} = (1 − vgp^{i})ã_{i}, so ã_{i+1} ≡ ã_{i} (mod p^{i}). Since N(1 − vgp^{i}) = ∏_{j=0}^{d−1}(1 − ϕ^{j}(vg)p^{i}) ≡ 1 − gp^{i} (mod p^{i+1}) by our choice of v, we have N(ã_{i+1}) ≡ (1−gp^{i})(1+gp^{i}) ≡ 1 (mod p^{i+1}). Now let ã_{0} = lim ã_{i}. Then N(ã_{0}) = lim N(ã_{i}) = 1, and ã_{0} ≡ ã_{s} (mod I), proving that the image of ã_{0} in G̃′_{1}(O_{p}/P_{p}^{s}) is c̃. Consequently, the image of ã_{0} in G′_{1}(O_{p}) covers c. □

Let H = G′(R, I), H_{1} = H ∩ G′_{1}(R) = G′_{1}(R, I) and Γ_{1} = Γ ∩ G′_{1}(R). (Note that the map G̃′_{1}(R)→G′(R) takes Γ̃_{1} = Γ̃ ∩ G̃′_{1}(R) to {γR^{×}: γ ∈ Γ̃, N(γ) = 1} which may be a proper subgroup of Γ_{1} = {γR^{×}: γ ∈ Γ̃, N(γ) ∈ R^{×}^{d}}).

In order to complete the identification of Γ/Γ(I), we need to compute the index of some subgroups of G′(R). From the definition of R, it follows that R^{×} = 𝔽_{q}^{×}{y^{i}(1 + y)^{j}: i, j ∈ ℤ}. The norm map A(R)^{×}→R^{×} is onto, since N(b_{u}) = y/(1 + y), N(z) = 1 + y and the norm 𝔽_{q^{d}}^{×}→𝔽_{q}^{×} is onto. Therefore, the map G′(R)→R^{×}/R^{×}^{d}, defined by aR^{×} ↦ N(a)R^{×}^{d}, is also surjective. If aR^{×} is in the kernel, then N(a) = t^{d} for some t ∈ R^{×}, and then N(t^{−1}a) = 1 and aR^{×} = t^{−1}aR^{×} ∈ G′_{1}(R). It follows that G′(R)/G′_{1}(R) ≅ R^{×}/R^{×}^{d}, and

(16)  [G′(R):G′_{1}(R)] = [R^{×}:R^{×}^{d}] = d^{2}(d, q − 1).

On the other hand, from Corollary 4.10, Corollary 4.9 and Proposition 3.5, we obtain

(17)  [G′(R):Γ_{1}] = \frac{q^{d} − 1}{q − 1}d^{2}.

Corollary 6.4. Γ_{1} is not contained in any congruence subgroup G′_{1}(R, I) for 0 ≠ I⊲R (I ≠ R).

Proof. We may assume I is maximal. By Theorem 6.3 the index of G′_{1}(R, I) in G′_{1}(R) is |PSL_{d}(R/I)| ≥ |PSL_{d}(𝔽_{q})| > \frac{q^{d}−1}{(q−1)(d,q−1)}, so

that [G′(R):G′_{1}(R, I)] = d^{2}(d, q − 1)[G′_{1}(R):G′_{1}(R, I)] > \frac{q^{d}−1}{q−1}d^{2} = [G′(R):Γ_{1}]. □

Corollary 6.5. For every I⊲R, G′_{1}(R) = Γ_{1}·H_{1} where H_{1} = G′_{1}(R, I).

Proof. By Proposition 4.9, Γ and H are normal in G′(R), so Γ_{1}H_{1} is normal in G′_{1}(R), and Γ_{1}H_{1}/H_{1} is normal in G′_{1}(R)/H_{1} ≅ G′_{1}(R/I), which is isomorphic to PSL_{d}(R/I).

Recall that I = ⟨p⟩^{s} where p is prime, and R/⟨p⟩ = 𝔽_{q^{α}} for an appropriate α. First assume that PSL_{d}(𝔽_{q^{α}}) is simple, so that d > 2 or q^{α} > 3. The group PSL_{d}(R/I) has normal subgroups N_{j} = Ker(PSL_{d}(R/I)→PSL_{d}(R/⟨p⟩^{j})). Now, the composition factors are PSL_{d}(R/I)/N_{1} ≅ PSL_{d}(R/⟨p⟩), and the N_{j}/N_{j+1} for j = 1, …, s − 1, which are all isomorphic to the zero-trace subalgebra of M_{d}(𝔽_{q^{α}}), and are irreducible PSL_{d}(𝔽_{q^{α}})-modules. If N⊴PSL_{d}(R/I) is a normal subgroup which is not contained in N_{1}, then PSL_{d}(R/I)/N_{1} ≅ N/(N ∩N_{1}) is a group of order power of q, which thus has a normal subgroup of index q, producing an impossible composition factor.

This proves Γ_{1}H_{1} = G_{1}, for otherwise Γ_{1}H_{1}/H_{1} is a proper normal subgroup of G_{1}/H_{1}, which is therefore contained in N_{1}/H_{1} = G′_{1}(R, \sqrt{I}), contradicting the last corollary.

In the special case d = 2 and |R/I| = 3, G′_{1}(R)/H_{1} ≅ A_{4} and has no non-trivial normal subgroups of index ≤ 2 = [G′_{1}(R):Γ_{1}]. The case |R/I| = 2 is impossible since the prime generator p must be different than y and 1 + y, and so it cannot be linear over 𝔽_{2}. □

There is a delicate point here: the claim that G′_{1}(R) = Γ_{1} · G′_{1}(R, I) holds for every proper ideal of R, but cannot be extended to the wider class of ideals of R_{0} (in the form G′_{1}(R) = Γ_{1} · G′_{1}(R_{0}, I)); indeed, we saw in the proof of Theorem 6.2 that G′_{1}(R_{0}, I) ⊆ Γ_{1} for suitable ideals of R_{0}.

From this and the definition of Γ_{1} and H_{1}, it follows that for the subgroups of G′(R) appearing in Figure 6, the intersections and products can be read from the lattice. The only non-trivial equality is Γ_{1}H_{1}(Γ ∩ H) = Γ_{1}H ∩ ΓH_{1}, and this too is easily checked (if γ_{1}h = γh_{1} for γ_{1} ∈ Γ_{1}, γ ∈ Γ, h ∈ H and h_{1} ∈ H_{1}, then γ^{−1}γ_{1} = h_{1}h^{−1} ∈ Γ ∩ H so γ_{1}(h_{1}h^{−1})^{−1}h_{1} ∈ Γ_{1}H_{1}(Γ ∩ H)).

In particular, the quotients of the extensions denoted by double lines are isomorphic to PSL_{d}(R/I).

Let L = R/I. We now observe that

PSL_{d}(L) ≅ Γ_{1}H_{1}/H_{1} ≅ Γ_{1}H/H ⊆ ΓH/H ⊆ G′(R)/H ⊆ PGL_{d}(L),

so we proved

Theorem 6.6. Γ_{I} = Γ/Γ(I) ≅ ΓH/H is a subgroup of PGL_{d}(L) which contains PSL_{d}(L).

Proposition 6.7. Let r denote the order of y/(1+y) in L^{×}/L^{×}^{d}. Then [Γ_{I}:PSL_{d}(L)] = r.

Proof. The composition Γ_{I} ≅ ΓH/H ↪ PGL_{d}(R/I) ⟶^{N} L^{×}/L^{×}^{d} carries Γ_{I} to the subgroup generated by N(b) = y/(1 + y), and its kernel is Γ_{1}H/H ≅ PSL_{d}(L). □

The index of PSL_{d}(L) in Γ_{I} can be interpreted in another way. As mentioned above, the color map δ: Γ→ℤ/d of Figure 3 is in fact an isomorphism Γ/Γ_{1}→ℤ/d, so it induces an isomorphism ΓH/Γ_{1}H ≅ Γ/Γ_{1}(Γ∩ H)→ℤ/r. In other words, there is an r-coloring of ΓH/H.

A remark about colors is in order. For the building B, there is a d × d matrix n_{ij} of integers, such that every vertex of color i has n_{ij} neighbors of color j (in fact n_{ij} = \left[{d \atop |i−j|}\right]_{q} − δ_{ij}, where \left[{d \atop k}\right]_{q} is the number of subspaces of dimension k of 𝔽_{q}^{d}), and in particular n_{ii} = 0 (so the graph is d-partite).

A quotient complex B_{I} which has a d_{1}-coloring still satisfies this property, for the ‘folded’ d_{1} × d_{1} matrix whose (i′, j′) entry is the sum of n_{ij} over i ≡ i′ (mod d_{1}) and j ≡ j′ (mod d_{1}). Naturally the most interesting case is when the quotient has d colors, which the above theorem guarantees quite often:

[figure: G′(R); ΓH; Γ_{1}H; ΓH_{1}; H; Γ_{1}H ∩ ΓH_{1}; Γ; H_{1}(Γ ∩ H); G′_{1} = Γ_{1}H_{1}; Γ_{1}(Γ ∩ H); H_{1}; Γ ∩ H; Γ_{1}; Γ_{1} ∩ H_{1}]

Figure 6. Subgroups of G′(R)

Corollary 6.8. If y/(1 + y) has order d in L^{×}/L^{×}^{d}, then there is a well defined color epimorphism δ_{L}: Γ/Γ(I)→ℤ/dℤ.

7. Construction with given index over PSL_{d}(L)

We combine the results obtained so far to prove Theorem 1.1, in the following, stronger version (the assumption q^{e} > 4d^{2} + 1 is only needed here to control the index r).

Theorem 7.1. Let q be a prime power, d ≥ 2, s ≥ 1, e ≥ 1 (e > 1 if q = 2), and r a divisor of (d, q^{e} − 1). Assume d is prime to q, or s = 1. Also assume that q^{e} > 4d^{2} + 1.

Then, for a suitable prime polynomial p ∈ 𝔽_{q}[y] of degree e and for L = 𝔽_{q}[y]/⟨p(y)^{s}⟩, the (unique) subgroup G of PGL_{d}(L) which has index r over PSL_{d}(L) has a set of \left[{d \atop 1}\right]_{q} +\left[{d \atop 2}\right]_{q} +⋯+\left[{d \atop d−1}\right]_{q} generators, such that the Cayley graph of G with respect to these generators determines a Ramanujan complex.

Let J⊲R be a prime ideal and I = J^{s} for some s ≥ 1. Let L_{0} = R/J ≅ 𝔽_{q^{e}}, the residue field of L = R/I.

Notice that PGL_{d}(L)/PSL_{d}(L) ≅ L^{×}/L^{×}^{d} is usually not a cyclic group, so Γ_{I} may not be the full group PGL_{d}(L). However, in two important cases, namely if d is prime to q or if L = L_{0}, the quotient L^{×}/L^{×}^{d} ≅ L_{0}^{×}/L_{0}^{×}^{d} is cyclic.

We want to choose the generator of J so that Γ/Γ(I) has a predetermined index over PSL_{d}(L). Write J = ⟨p⟩. p is a prime polynomial different than y and 1 + y, since R = 𝔽_{q}[y, 1/y, 1/(1 + y)]. In particular, if q = 2 then we must assume e ≥ 2.

It is convenient to have a uniform bound on the number of nongenerators of a finite field.

Lemma 7.2. Let q be a prime power and e > 1, and let 𝔽_{q^{e}} be a field of order q^{e}. There are less than 2q^{e/2} elements of 𝔽_{q^{e}} which do not generate it over 𝔽_{q}.

Proof. We need to bound the size of the union of the maximal subfields of dimensions e/p, for the prime divisors p of e. If e is a prime or equals 4, then the statement is obvious, so we assume e ≥ 6 and is not a prime. Let C = 9/q.

We claim that for every prime p ≥ 3 dividing e, q^{e/p} < Cp^{−2}q^{e/2}. Indeed, since e is not a prime, p ≤ e/2. Now, in the range 3 ≤ p ≤ e/2, h(p) = 2 log(p) − (e/2 − e/p) log(q) obtains its maximum on one of the boundaries, and so is bounded by

max(h(3), h(e/2)) = max(log(9)−e log(q)/6, 2 log(e/2)−(e/2−2) log(q)).

This decreases with e, and is thus bounded by its value at e = 6, namely log(9/q).

Since ∑_{p≥3} p^{−2} < 2/9 (summing over all the primes), we have that ∑_{p|e} q^{e/p} < (1 + C ∑ p^{−2})q^{e/2} < (1 + 2/q)q^{e/2}. □

Proposition 7.3. Let q, d, s, r and e be as in Theorem 7.1.

If q^{e} > 4d^{2} + 1, then there is a polynomial p ∈ 𝔽_{q}[y] of degree e, such that for J = ⟨p⟩⊲R and I = J^{s}, L_{0} = R/J is the field of order q^{e}, and [Γ_{I}:PSL_{d}(L)] = r where L = R/I.

Proof. The assumption that s = 1 or d is prime to q guarantees that L^{×}/L^{×}^{d} ≅ L_{0}^{×}/L_{0}^{×}^{d}.

Let α be an element of 𝔽_{q^{e}} whose order in 𝔽_{q^{e}}^{×}/𝔽_{q^{e}}^{×}^{d} is r. Let α_{1} = \frac{α}{1−α}. The map α ↦ α_{1} is one-to-one.

There are \frac{q^{e}−1}{(d,q^{e}−1)}ϕ(r) ≥ \frac{q^{e}−1}{(d,q^{e}−1)} suitable elements α, and α_{1} belongs to a proper subfield of 𝔽_{q^{e}} in less than 2q^{e/2} ≤ \frac{q^{e}−1}{(d,q^{e}−1)} cases. We can thus assume α_{1} generates 𝔽_{q^{e}} as a field. Then, the minimal polynomial f ∈ 𝔽_{q}[y] of α_{1} has degree e. Take I = ⟨f^{s}⟩. Then L_{0} = R/⟨f⟩ is isomorphic to 𝔽_{q^{e}}, and the image of y in L_{0} satisfies y/(1 + y) ↦ α_{1}/(1 + α_{1}) = α. It has order r in L_{0}^{×}/L_{0}^{×}^{d}, and we are done by Proposition 6.7. □

Recall that the group Γ ⊆ G′(R) (Definition 4.4) is generated by the \left[{d \atop 1}\right]_{q} = \frac{q^{d}−1}{q−1} elements b_{u} = u(1−z^{−1})u^{−1}, which can be viewed as d^{2} ×d^{2} matrices over R_{0} = 𝔽_{q}[1/y]; see Proposition 3.3 and the definition of i_{R} there.

Let G be the group generated by these matrices over R_{0}/(y^{−e}p)^{s}. Then G ≅ Γ_{I} and, therefore, has index r over PSL_{d}(L). For each k = 1, …, d − 1, the generators of color k of G are the products b_{u_{1}} … b_{u_{k}}, which can be extended to a product of d generators which equals 1 (see Section 5 and Proposition 2.3); in particular, every b_{u} is a generator of color 1. See [CS, Sec. 4] for an alternative description of the generators (as elements of A(k)).

The description of the complex constructed from the Cayley graph is given at the beginning of Section 6. Theorem 6.2 then completes the proof of Theorem 7.1.

8. Splitting A(R)

So far Γ is viewed as a group of d^{2} × d^{2} matrices, and the representation of Γ as d × d matrices is over the completion F of k. To facilitate the explicit constructions of finite quotients in the next section, we now present a splitting extension of dimension d for G′(k) (and G′(R)).

Fix an element β ∈ 𝔽_{q^{d}} such that tr(β) ∈ 𝔽_{q} is non-zero. Let k̄_{1} = 𝔽_{q^{d}}(x), with the obvious action of Gal(𝔽_{q^{d}}/𝔽_{q}), so the fixed field is k̄ = 𝔽_{q}(x). Then the norm N_{𝔽_{q^{d}}(x)/𝔽_{q}(x)}(1 + βx) is a polynomial of degree d in 𝔽_{q}[x], which has the form 1 + t_{1}x + ⋯ + t_{d}x^{d} for some t_{i} ∈ 𝔽_{q}. Then t_{1} = tr(β) ≠ 0 by assumption, and t_{d} = N_{𝔽_{q^{d}}/𝔽_{q}}(β) ≠ 0, since β ≠ 0.

We embed k = 𝔽_{q}(y) into k̄ by mapping

(18)  y ↦ t_{1}x + ⋯ + t_{d}x^{d}.

Now k becomes a subfield of codimension d of 𝔽_{q}(x).

Proposition 8.1. Taking the completion, 𝔽_{q}((x)) = 𝔽_{q}((y)), and even 𝔽_{q}[[x]] = 𝔽_{q}[[y]].

Proof. Before giving the proof, we should explain the notation. By 𝔽_{q}((x)) we mean, as usual, the field of Taylor series {∑_{i=−v}^{∞} α_{i}x^{i}} with coefficients from 𝔽_{q}; 𝔽_{q}[[x]] is the subring of elements of the form ∑_{i=0}^{∞} α_{i}x^{i}. As abstract fields, it trivially holds that 𝔽_{q}((y)) ≅ 𝔽_{q}((x)).

[figure: 𝔽_{q^{d}}((y)); 𝔽_{q^{d}}(x); F = 𝔽_{q}((y)); k_{1} = 𝔽_{q^{d}}(y); 𝔽_{q}(x); k = 𝔽_{q}(y); R̄; O = 𝔽_{q}[[y]]; R; R̄_{T}; R_{T}] Figure 7

But now 𝔽_{q}((y)) is the subfield of 𝔽_{q}((x)) consisting of Taylor series in the element y of Equation (18).

Working in 𝔽_{q}((y)), Equation (18) has a solution for x by Hensel’s lemma (since the derivation at zero, namely t_{1}, is non-zero). In fact, the solution has the form x = \frac{1}{t_{1}} y − \frac{t_{2}}{t_{1}^{3}} y^{2} + …, so that x ∈ 𝔽_{q}[[y]]. □

Tensoring with 𝔽_{q^{d}}, we also have that 𝔽_{q^{d}}((y)) = 𝔽_{q^{d}}((x)). Define R̄_{T} = 𝔽_{q}[x, 1/(1 + y)] and R̄ = 𝔽_{q}[x, 1/y, 1/(1 + y)], so that R_{T} ⊆ R̄_{T} and R ⊆ R̄. Since 1 + y is invertible in 𝔽_{q}[[y]], R̄_{T} ⊆ 𝔽_{q}[[y]]. The rings mentioned so far appear in Figure 7.

Notice that 𝔽_{q}(x) is a splitting field of A(k), as 1 + y = N(1 + βx) is a norm in the extension 𝔽_{q^{d}}(x)/𝔽_{q}(x). We thus obtain the chain of inclusions

(19) A(R) ⊆ A(k) ↪ A(k)⊗_{k}𝔽_{q}(x)
≅ M_{d}(𝔽_{q}(x)) ↪ M_{d}(𝔽_{q}((x))) = M_{d}(𝔽_{q}((y))),

refining Equation (5). The last equality in this chain follows from Proposition 8.1.

In fact, A(R̄_{T}) is already split, and we now present an explicit isomorphism A(R̄_{T}) ≅ M_{d}(R̄_{T}).

\xymatrix{A(k̄) \ar[r]^{≅} & Endk̄(k̄⊗𝔽_{q^{d}}) \\ A(R̄_{T}) \ar@{^{(}->}[u] \ar[r] & EndR̄_{T} (R̄_{T} ⊗𝔽_{q^{d}}) \ar@{^{(}->}[u]}

Figure 8

Proposition 8.2. Let M = R̄_{T} ⊗𝔽_{q^{d}}, and let ρ: M→ EndR̄_{T} (M) be the regular representation, defined by ρ: r⊗u ↦ ρ_{r}⊗ρ_{u}, where ρ_{r}(r′) = rr′ for r′ ∈ R̄_{T}, and ρ_{u}(u′) = uu′ for u ∈ 𝔽_{q^{d}}.

The map ρ is extended by z ↦ 1⊗ϕ + ρ_{x}⊗ρ_{β}ϕ to an isomorphism

A(R̄_{T}) ⟶^{∼} EndR̄_{T} (M).

Proof. By the definition ρ(z) = ρ(1 + βx) · (1⊗ϕ), so that ρ(z)^{−1} = (1⊗ϕ^{−1}) · ρ(1 + βx)^{−1}. We need to check the defining relations of A(R̄_{T}). Let r⊗u, r′⊗u′ ∈ M; then

ρ(z)ρ(r⊗u)(r′⊗u′) = ρ(z)(rr′⊗uu′)
= (1 + βx)(rr′⊗ϕ(uu′))
= (1 + βx)(r⊗ϕ(u))(r′⊗ϕ(u′))
= ρ(r⊗ϕ(u))(1 + βx)(r′⊗ϕ(u′))
= ρ(r⊗ϕ(u))ρ(z)(r′⊗u′),

so that ρ(z)ρ(r⊗u)ρ(z)^{−1} = ρ(r⊗ϕ(u)). Also, ρ(z)^{d} = (ρ(1 + βx) · (1⊗ϕ))^{d} = ρ(N(1 + βx)) · (1⊗ϕ)^{d} = ρ(1 + y).

To check that the extended ρ is an embedding, let k̄ = 𝔽_{q}(x), and recall that A(k̄) ≅ Endk̄(k̄⊗𝔽_{q^{d}}) by the norm condition. The result then follows from the commutativity of the diagram in Figure 8, and the fact that A(R̄_{T}) and EndR̄_{T} (M) have the same rank d^{2} over R̄_{T}.

□

Since R̄_{T} ⊗𝔽_{q^{d}} is a free module of rank d over R̄_{T}, we obtain an isomorphism A(R̄_{T}) ≅ M_{d}(R̄_{T}).

Example 8.3. Suppose q = 7 and d = 3, and let α = \sqrt[3]{2} over 𝔽_{7}, so that 𝔽_{7^{3}} = 𝔽_{7}[α]. If ϕ is the Frobenius automorphism, we have that ϕ(α) = α^{7} = 4α. As a normal basis of 𝔽_{7^{3}}/𝔽_{7} we take ζ_{0} = 1 + α + α^{2} and ζ_{i} = ϕ^{i}(ζ_{0}). We choose β = α − 2 (so that tr(β) = 1). Of course {ζ_{i}} form a basis of R̄_{T} ⊗𝔽_{7^{3}} as a free module over R̄_{T}. Computing directly, we find that N(1+βx) = 1+x−2x^{2}+x^{3}, so that y = x−2x^{2}+x^{3}.

In order to present an embedding of A(R̄_{T}) = 𝔽_{7^{3}}[x, 1/(1+y)][z] into M_{3}(𝔽_{7}[x, 1/(1+y)]), we need to describe the images of 𝔽_{7^{3}}, x, 1/(1+y) and z. For the subfield, check that

α ↦ (\begin{matrix}6 & 3 & 6 \\ 5 & 5 & 6 \\ 5 & 3 & 3 \end{matrix})

defines the embedding 𝔽_{7^{3}}→M_{3}(𝔽_{7}) via the basis we chose. Secondly, x and 1/(1+y) are scalars in R̄_{T} and so are mapped to scalar matrices. Finally, since ϕ(ζ_{i}) = ζ_{i+1}, by the above proposition we have

z ↦ ρ(1 + βx) · (1⊗ϕ)
= (\begin{matrix}1+4x & 3x & 6x \\ 5x & 1+3x & 6x \\ 5x & 3x & 1+x \end{matrix}) · (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) = (\begin{matrix}3x & 6x & 1+4x \\ 1+3x & 6x & 5x \\ 3x & 1+x & 5x \end{matrix}) .

One can check that over R̄_{T}, z^{3} is the scalar matrix 1 + y.

9. Explicit constructions

In this section we show how to choose the generator p^{s} ∈ 𝔽_{q}[y] of I, such that Γ_{I} = Γ/Γ(I) will have an explicit representation as d × d matrices over L. The construction works for arbitrary q, d, e = deg(p) and s ≥ 1, but we do not try to control the index r of Γ_{I} over PSL_{d}(L) (which can be computed by Proposition 6.7).

Recall that H = G′(R, I). Our current realization of ΓH/H as a subgroup of PGL_{d}(R/I) is inexplicit, as we use the abstract isomorphism G′(R/I) ≅ PGL_{d}(R/I). We do have an explicit embedding of i_{R} of G′(R) into d^{2} × d^{2} matrices over R, as described before Proposition 3.3, but for practical reasons it is more convenient to have a representation of dimension d.

In Proposition 8.2 (and Example 8.3) we gave an explicit isomorphism of A(R̄_{T}) to matrices over R̄_{T}, which in particular embeds G′(R) ↪ PGL_{d}(R̄). Given I⊲R, there is an ideal Ī⊲R̄ such that I = Ī∩ R (since R̄ = R[x] is an integral extension over R and R̄ is a principal ideal domain). Let L̄ = R̄/Ī, then there is a natural embedding L ⊆ L̄, and we thus have an embedding G′(L) ↪ PGL_{d}(L̄).

We will show that it is possible to choose I so that L̄ ≅ L, where the image of x in L (which is what we need for the splitting map of Proposition 8.2) is explicitly identified.

We need some details on the possible choices of Ī. Write y(λ) = t_{1}λ + ⋯ + t_{d}λ^{d} for the polynomial defined by Equation (18), so y(x) is our usual element y of 𝔽_{q}[x]. If p(λ) ∈ 𝔽_{q}[λ] is irreducible and not equal to λ or λ + 1, then p(y) ∈ R generates a prime ideal J⊲R. Since the embedding of R into R̄ is by sending y to y(x), J lifts to the ideal J̄ = ⟨p(y(x))⟩ of R̄. Let p(y(λ)) = g_{1}(λ) … g_{t}(λ) be the decomposition into prime factors over 𝔽_{q} and J̄_{i} = ⟨g_{i}(x)⟩⊲R̄, then ⟨p(y(x))⟩ = J̄_{1} … J̄_{t}, where each J̄_{i} is a prime ideal of R̄ covering J. If α is a root of g_{i} in some extension, then y(α) ∈ 𝔽_{q}[α] is a root of p(λ), so p splits in 𝔽_{q}[α] and thus deg(p(λ)) | [𝔽_{q}[α]:𝔽_{q}] = deg(g_{i}). This shows once more that L̄_{0}^{i} = R̄/J̄_{i} is an extension of L_{0} = R/J, and in fact [L̄_{0}^{i}:L_{0}] = deg(g_{i})/ deg(p). We remark that the degrees of the g_{i} are not necessarily equal.

Let γ_{j} be the roots of p(λ) in L_{0}, then p(λ) = ∏(λ−γ_{j}) and p(y(λ)) = ∏(y(λ) − γ_{j}). In particular the roots of p(y(λ)) are roots of the factors y(λ) − γ_{j}. Let α be a root of p(y(λ)) coming from an irreducible factor g_{i}(λ). Then L̄_{0}^{i} = 𝔽_{q}[α] = L_{0}[α] (since a generator γ_{j} of L_{0} equals y(α)). It follows that p(y(λ)) has a factor g_{i} of degree deg(p) iff L̄_{0}^{i} = L_{0}, iff y(λ) − γ_{j} has a root in L_{0} for some j (a condition which is easily seen to be independent of j).

We now show that J = ⟨p(y)⟩⊲R can be chosen so that L̄_{0} = L_{0} and L̄ = L, which provides an explicit realization of Theorem 6.6.

Theorem 9.1. Let q be a prime power and d an integer. Assume q^{e} ≥ 4d^{2}. Then there are irreducible polynomials p, g ∈ 𝔽_{q}[λ] of degree e such that for every s ≥ 1, the embedding R→R̄ induces an isomorphism R/I ≅ R̄/Ī for I = ⟨p(y)^{s}⟩⊲R and Ī = ⟨g(x)^{s}⟩⊲R̄.

Proof. Let 𝔽_{q^{e}} be the field of order q^{e}. For every α ∈ 𝔽_{q^{e}}, consider the element y(α). Since deg(y(λ)) = d, there are at most d elements α with the same y(α), so in particular (by Lemma 7.2), y(α) is not a generator of 𝔽_{q^{e}} for less than 2dq^{e/2} choices of α. By the assumption on e, we can choose α for which γ = y(α) generates the field of q^{e} elements (so necessarily α is also a generator). Let p(λ) and g(λ) be the minimal polynomials of γ and α over 𝔽_{q}, respectively. Since α and γ are generators, deg(p) = deg(g) = e.

Now let I = ⟨p(y)^{s}⟩⊲R and Ī = ⟨g(x)^{s}⟩⊲R̄. Since g(x) | p(y(x)) and g(x) is prime, I = Ī∩ R, and so L = R/I embeds into L̄ = R̄/Ī. Since deg(p) = deg(g), |L| = |L̄|, and so they are isomorphic. □

The same choice of p and g works for every s ≥ 1, so the proposition shows that in fact the fraction field k̄ = k[x] of R̄ is contained in the completion k_{p}.

We conclude this section with a detailed algorithm giving the generators for a Cayley complex of PGL_{d}(L). Let q be a given prime power, d ≥ 2, and e ≥ 1. Assume q^{e} ≥ 4d^{2}.

Algorithm 9.2. (1) In practice, the elements of 𝔽_{q^{d}} are polynomials of degree at most d over 𝔽_{q}, modulo a fixed irreducible polynomial of degree d. Fix a basis ζ_{0}, …, ζ_{d−1} for 𝔽_{q^{d}} over 𝔽_{q}. Let ϕ be any generator of Gal(𝔽_{q^{d}}/𝔽_{q}) (namely exponentiation by q^{ℓ} where ℓ is any fixed integer prime to d). Let β ∈ 𝔽_{q^{d}} be an element with β + ⋯ + ϕ^{d−1}(β) ≠ 0, let t_{1}, …, t_{d} ∈ 𝔽_{q} be defined by (1+βλ) … (1+ϕ^{d−1}(β)λ) = 1+t_{1}λ+⋯+t_{d−1}λ^{d−1}, and set y(λ) = t_{1}λ + ⋯ + t_{d−1}λ^{d−1}. For an element c ∈ 𝔽_{q^{d}}^{×}, ρ(c) ∈ GL_{d}(𝔽_{q}) is the matrix defined by c · ζ_{j} = ∑_{i=0}^{d−1} (ρ(c))_{ij}ζ_{i}. Likewise, let φ ∈ GL_{d}(𝔽_{q}) be the matrix defined by ϕ(ζ_{j}) = ∑_{i=0}^{d−1} φ_{ij}ζ_{i}.

(2) Let α ∈ 𝔽_{q^{e}} be an element such that γ = y(α) generates 𝔽_{q^{e}} as a field (the existence of which is guaranteed by Theorem 9.1). A quick way to check this property is to verify that γ^{q^{e′}} ≠ γ for every proper divisor e′ of e. Let p(λ) and g(λ) be the minimal polynomials (of degree e) of γ and α, respectively, over 𝔽_{q} (found by Gaussian elimination on 1, γ, …, γ^{e} or 1, α, …, α^{e}).

(3) Fix s ≥ 1. Let L̄ denote the ring of polynomials of degree < es in the variable x, with operations modulo g(x)^{s}. Let ρ(z) ∈ GL_{d}(L) be the matrix (1 + ρ(β)x) · φ, as in Proposition 8.2 and the example following it. Let b = 1 − ρ(z)^{−1} (Gauss elimination can be used to invert ρ(z), where the inverse of f(x) ∈ L is computed via the extended Euclid’s algorithm for f(λ) and g(λ)^{s}). For every u ∈ 𝔽_{q^{d}}^{×}/𝔽_{q}^{×} (one representative from each class), set b_{u} = ρ(u)bρ(u)^{−1}.

(4) The matrices {b_{u}} generate a subgroup G of PGL_{d}(L), which contains PSL_{d}(L). The index r = [G:PSL_{d}(L)] can be computed using Proposition 6.7.

(5) For every k = 1, …, d − 1, let S_{k} denote the set of products b_{u_{1}} … b_{u_{k}}. There will be \left[{d \atop k}\right]_{q} different products (up to scalar multiples over L), and S_{d−k} is the set of inverses of S_{k}.

(6) The Cayley complex of G with respect to S_{1} ∪ … ∪ S_{d−1} defines a simplicial complex (the clique complex of the Cayley graph). This complex is Ramanujan by Theorem 6.2.

10. An example

We demonstrate the construction of the group Γ, and the embedding into d^{2} × d^{2} and d × d matrices. We choose q = 2 and d = 3, and write 𝔽_{8} = 𝔽_{2}[v | v^{3} = v +1]. Fix the basis {ζ_{0}, ζ_{1}, ζ_{2}} = {1, v, v^{2}} for 𝔽_{8} over 𝔽_{2}. Then {ζ_{i}z^{j}} is a basis for A(R) = R[v, z | v^{3} = v + 1, z^{3} = 1 + y, zvz^{−1} = v^{2}] over R = 𝔽_{2}[y, 1/y, 1/(1+y)]. By definition, Γ ⊆ A(R)^{×} is generated by the conjugates u(1−z^{−1})u^{−1} for u ∈ 𝔽_{8}^{×}/𝔽_{2}^{×} = 𝔽_{8}^{×} = ⟨v⟩.

These generators act on A(R) by conjugation, and the corresponding 9 × 9 matrices over R are given in the right-hand column of Table 9 (they are all of the form a + by^{−1} for a, b ∈ GL_{9}(𝔽_{2})).

The relations of Γ were discussed in Section 5. If we set b_{i} = v^{i}(1 − z^{−1})v^{−i}, conjugation by v induces an outer automorphism of order 7 (namely b_{i} ↦ b_{i+1}), and the defining relations are

b_{0}b_{3} = b_{4}b_{2} = b_{6}b_{5},
b_{0}b_{5} = b_{2}b_{1} = b_{3}b_{6},
b_{0}b_{6} = b_{1}b_{4} = b_{5}b_{3},
b_{0}b_{3}b_{1} = 1,

and their v-conjugates.

We continue to find a representation of dimension 3 of a finite quotient of Γ. The first step is to define R as a subring of R̄ = R[x], so we need to choose β with tr(β) ≠ 0; here we take β = 1 + v, so that 1 + y = N_{𝔽_{8}/𝔽_{2}}(1 + βx) = 1 + x + x^{3} and y(x) = x + x^{3}. Then R ↪ R̄ by sending y ↦ y(x).

Mimicking Example 8.3, the embedding A(R) ↪ PGL_{3}(R̄) is defined by

v ↦ (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}) ,

z ↦ ρ(1 + βx) · (1⊗ϕ)
= (\begin{matrix}1+x & 0 & x \\ x & 1+x & x \\ 0 & x & 1+x \end{matrix}) · (\begin{matrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \end{matrix}) = (\begin{matrix}1+x & x & x \\ x & x & 1 \\ 0 & 1+x & 1 \end{matrix}) .

One checks that z^{3} is mapped to the scalar matrix 1+x+x^{3} = 1+y(x),

so z^{−1} = \frac{1}{1+y(x)}z^{2}, and b = 1−z^{−1} ↦ \frac{1}{1+y(x)} (\begin{matrix}x + x^{3} & x^{2} & x + x^{2} \\ x & x^{3} & 1 + x + x^{2} \\ x + x^{2} & 1 + x^{2} & 1 + x^{3} \end{matrix}),

where 1 + y(x) is invertible in R̄ by definition. We emphasize that this embedding is not onto (since A(R) does not split).

Finally, we present a finite quotient of Γ. Choose e = 4, so Γ will map onto PGL_{3}(L) where L is a finite local ring whose residue field is 𝔽_{16} (in general Γ could be mapped onto a subgroup of PGL_{3}(L) containing PSL_{3}(L)). Applying the proof of Theorem 9.1 and the algorithm given in Section 9, we look for an element α ∈ 𝔽_{16} such that y(α) is a generator.

Arbitrarily choosing an irreducible polynomial of degree 4 over 𝔽_{2}, we set 𝔽_{16} = 𝔽_{2}[t | t^{4} + t + 1 = 0]. It then turns out that y(t) = t^{3} + t is a generator (since y(t^{2}) ≠ y(t)), so we choose α = t and γ = y(t). The minimal polynomial of α is of course g(λ) = λ^{4} + λ + 1, and the minimal polynomial of γ is computed to be p(λ) = λ^{4} + λ^{3} + λ^{2} + λ + 1. Now g(λ) divides p(y(λ)) = p(λ^{3} + λ) = λ^{12} + λ^{9} + λ^{7} + λ^{6} + λ^{5} + λ^{4} + λ^{2} + λ + 1 = g(λ)(λ^{8} + λ^{4} + λ^{3} + λ^{2} + 1), so for any s ≥ 1, when we take I = ⟨p(y)^{s}⟩ and Ī = ⟨g(x)^{s}⟩, we have R∩Ī = I. Since deg(p) = deg(g), R/I ≅ R̄/Ī = 𝔽_{2}[x]/⟨(x^{4} + x + 1)^{s}⟩.

The index over PSL_{d} is the order of y/(1 + y) = y^{3} + y + 1 in 𝔽_{2}[y]/⟨y^{4} + y^{3} + y^{2} + y + 1⟩ modulo its cubes; the order is 3, so Γ maps onto PGL_{d}(L). The 3×3 matrices over R̄ corresponding to the generators b_{i} of Γ/(G′(R, I) ∩ Γ) ≅ PGL_{3}(R/I) are given in the intermediate column of Table 9. The Cayley graph with respect to these generators is Ramanujan by Theorem 6.2.

11. Glossary

A(S) — an S-algebra for any R_{T} -algebra S with the relations given in Equation (4) (see Section 3).

B = B_{d}(F) — Bruhat-Tits building = PGL_{d}(F)/PGL_{d}(O) = G(F)/K B^{0} — the set of vertices of B B^{i} — the i-skeleton of B B_{I} = Γ(I)\G(F)/K ≅ Γ/Γ(I) d — an integer ≥ 1 F = 𝔽_{q}((y)) = k_{y} (see Figure 1) G̃′(S) = A(S)^{×} (in particular G̃′(R) = A(R)^{×}, and likewise for the

other groups defined over R or other R_{T} -algebras).

G′(S) = A(S)^{×}/S^{×}. G̃′_{1}(S) — elements of G̃′(S) of norm 1 G′_{1}(S) — the image of G̃′_{1}(S) under the map G̃′(S)→G′(S) (see Fig-

ure 5)

G̃(S) = GL_{d}(S) G(S) = PGL_{d}(S) G̃_{1}(S) = SL_{d}(S) G_{1}(S) = PSL_{d}(S) G̃′(S, I) — congruence subgroup of G̃′(S); kernel of G̃′(S)→G̃′(S/I) G′(S, I) — the image of G̃′(S, I) under the projection G̃′(S)→G′(S)

(for other congruence subgroups, see Section 6 and in particular Figure 5)

Γ̃ = ⟨b_{u}: u ∈ 𝔽_{q^{d}}^{×}/𝔽_{q}^{×}⟩ (see Section 4 for definition of b_{u} ∈ A(R))

Γ — the image of Γ̃ under G̃′(R)→G′(R) Γ(I) = Γ ∩ G′(R, I)

b_{u} ∈ PGL_{3}(R̄)  b_{u} ∈ GL_{9}(R)

b_{0}  (\begin{matrix}x+x^{3} & x^{2} & x+x^{2} \\ x & x^{3} & 1+x+x^{2} \\ x+x^{2} & 1+x^{2} & 1+x^{3} \end{matrix})  (\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix})+ \frac{1}{y} (\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \end{matrix})

b_{1}  (\begin{matrix}1+x+x^{2}+x^{3} & x+x^{2} & 1+x^{2} \\ 1+x & x^{2}+x^{3} & 1 \\ 1+x^{2} & x & x^{3} \end{matrix}) (\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix})+ \frac{1}{y} (\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \end{matrix})

b_{2}  (\begin{matrix}1+x^{2}+x^{3} & 1+x^{2} & x \\ 1+x+x^{2} & x+x^{3} & x^{2} \\ x & 1+x & x^{2}+x^{3} \end{matrix})  (\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix})+ \frac{1}{y} (\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \end{matrix})

b_{3} (\begin{matrix}x+x^{2}+x^{3} & x & 1+x \\ 1 & 1+x+x^{2}+x^{3} & x+x^{2} \\ 1+x & 1+x+x^{2} & x+x^{3} \end{matrix}) (\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix})+ \frac{1}{y} (\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 \end{matrix})

b_{4} (\begin{matrix}1+x^{3} & 1+x & 1+x+x^{2} \\ x^{2} & 1+x^{2}+x^{3} & 1+x^{2} \\ 1+x+x^{2} & 1 & 1+x+x^{2}+x^{3} \end{matrix}) (\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix})+ \frac{1}{y} (\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \end{matrix})

b_{5}  (\begin{matrix}x^{3} & 1+x+x^{2} & 1 \\ x+x^{2} & x+x^{2}+x^{3} & x \\ 1 & x^{2} & 1+x^{2}+x^{3} \end{matrix}) (\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix})+ \frac{1}{y} (\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix})

b_{6}  (\begin{matrix}x^{2}+x^{3} & 1 & x^{2} \\ 1+x^{2} & 1+x^{3} & 1+x \\ x^{2} & x+x^{2} & x+x^{2}+x^{3} \end{matrix})  (\begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix})+ \frac{1}{y} (\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \end{matrix})

Figure 9. Generators of Γ in the example of Section 10

Γ_{1} = Γ ∩ G′_{1}(R) (see Figure 6) H = G′(R, I) H_{1} = H ∩ G′_{1}(R) I = ⟨p^{s}⟩⊲R, p ∈ 𝔽_{q}[y] is a prime and s ≥ 1 k = 𝔽_{q}(y) (see Figure 1) k_{1} = 𝔽_{q^{d}}(y) (see Figure 1) k_{p} — the completion of k with respect to p k̄ = 𝔽_{q}(x) L = R/I, a finite local ring L_{0} = R/J = R/⟨p⟩, the residue field of L L̄ = R̄/Ī O = 𝔽_{q}[[y]] — the ring of integers of F O_{p} — the ring of integers of k_{p} q — a fixed prime power, the order of the finite field 𝔽_{q} R_{T} = 𝔽_{q}[y, 1/(1 + y)] ⊆ O R = 𝔽_{q}[y, 1/y, 1/(1 + y)] R_{0} = 𝔽_{q}[1/y] R̄ = R[x] R̄_{T} = R_{T} [x] ϱ: B^{0}→ℤ/dℤ — the color function of the building ν_{p} — valuation of k for the prime polynomial p ∈ 𝔽_{q}[y] ν_{1/y} — the minus degree valuation of k y — a transcendental variable over 𝔽_{q}, generates k

References

[AG] M. Auslander and O. Goldman, The Brauer group of a commutative ring, Trans. Amer. Math. Soc. 97, 367–409, (1960).

[B1] C.M. Ballantine, Ramanujan Type Buildings, Canad. J. Math. 52(6), 1121– 1148, (2000).

[CS] D.I. Cartwright and T. Steger, A Family of Ã_{n}-Groups, Israel J. Math. 103 125–140, (1998).

[CSZ] D.I. Cartwright, P. Solé and A. Żuk, Ramanujan Geometries of type Ã_{n}, Discrete Math. 269, 35–43, (2003).

[DI] F. DeMeyer and E. Ingraham, Separable Algebras over Commutative Rings, Lecture Notes in Mathematics 181, Springer-Verlag, 1970.

[HT] R. Harris and R. Taylor, The Geometry and Cohomology of Simple Shimura Varieties, Anals of Math. Studies. 151, Princeton Univ. Press, 2001.

[Jac] N. Jacobson, Finite Dimensional Division Algebras over Fields, Springer, 1996.

[Li] W.-C. W. Li, Ramanujan Hypergraphs, preprint, (2003).

[Lu1] A. Lubotzky, Discrete Groups, Expanding Graphs and Invariant Measures, Progress in Math. 125, Birkhäuser, 1994.

[LPS] A. Lubotzky, R. Philips and P. Sarnak, Ramanujan graphs, Combinatorica 8, 261–277, (1988).

[LSV] A. Lubotzky, B. Samuels and U. Vishne, Ramanujan Complexes of Type Ã_{d}, preprint.

[Mo] M. Morgenstern, Existence and explicit constructions of q+1 regular Ramanujan graphs for every prime power q, J. Combin. Theory Ser. B 62(1), 44–62, (1994).

[P] R.S. Pierce, Associative Algebras, Springer, GTM 88, 1982.

[PR] V. Platonov and A. Rapinchuk, Algebraic Groups and Number Theory, Pure and Applied Mathematics 139, 1994.

[Pr] G. Prasad, Strong approximation for semi-simple groups over function fields, Ann. Math. 105, 553–572, (1977).

[R] M. Ronan, Lectures on Buildings, Academic Press, 1989.

[Sa] A. Sarveniazi, Ramunajan (n_{1}, n_{2}, ..., n_{d−1})-regular hypergraphs based on Bruhat-Tits Buildings of type Ã_{d−1}, arxiv.org/math.NT/0401181.

[Sc] W. Scharlau, Quadratic Forms, Queen’s papers in Pure and Applied Math. 22, Queen’s Univ., Kingston, Ontario, 1969.

Dept. of Math., Hebrew Univ., Givat Ram, Jerusalem 91904, Israel

  E-mail address: alexlub@math.huji.ac.il

Dept. of Math., Yale University, 10 Hillhouse Av., New-Haven CT 06520, USA

  E-mail address: beth.samuels@yale.edu

Dept. of Math., Yale University, 10 Hillhouse Av., New-Haven CT 06520, USA

Current address: Dept. of Math., Bar-Ilan University, Ramat-Gan 52900, Israel

  E-mail address: vishne@math.biu.ac.il