Ramanujan Hyper Graphs

GAFA, Geom. funct. anal. Vol. 14 (2004) 380 – 399 1016-443X/04/020380-20 DOI 10.1007/s00039-004-0461-z

c Birkh¨
auser Verlag, Basel 2004

GAFA Geometric And Functional Analysis

RAMANUJAN HYPERGRAPHS W.-C.W. Li

1

Introduction

Ramanujan graphs, first defined by Lubotzky–Phillips–Sarnak [LuPS] and independently by Margulis [Ma], are k-regular graphs whose nontrivial eigenvalues fall in the spectrum of their universal cover, the k-regular infinite tree. As indicated by the Alon–Boppana theorem [LuPS] and the result in [Li1], the Ramanujan graphs have eigenvalues small in absolute value. These graphs have good expansion property and families of such graphs have a variety of important applications in computer science. Explicit constructions of infinite families of Ramanujan graphs are known for the case k = q + 1 with q a prime power, based on quaternion groups over Q [LuPS], [Ma] and [Me] and over a function field of one variable over a finite field [Mu]. The functions on the vertices of these Ramanujan graphs can be regarded as automorphic functions for the underlying quaternion group, and the Ramanujan property of these graphs follows from the fact that the automorphic forms satisfy the Ramanujan conjecture, proved by Eichler [E] and Shimura [S] for the case of weight 2 cusp forms over Q and by Drinfeld [Dr] for the case of function fields. The Ramanujan graphs explicitly constructed in [Li2] and in [ACPTTV], [CePTTV], using number theoretic methods, are later shown in [Li3] as quotient graphs of those constructed using quaternion groups. The purpose of this paper is to extend the above to higher dimensional analogue, that is, k-regular n-hypergraphs. We shall restrict ourselves to the (q + 1)-regular n-hypergraphs whose universal covers are the Bruhat– Tits building Bn,F , where F is a nonarchimedean local field with q elements in its residue field. On an n-hypergraph there are n − 1 operators A1 , . . . , An−1 which play the role of adjacency matrix of a graph. We first The research of the author was supported in part by a grant from the National Science Foundation no. DMS 997-0651 and a grant from National Security Agency no. MDA904-03-1-0069.

Vol. 14, 2004

RAMANUJAN HYPERGRAPHS

381

prove a theorem of Alon–Boppana type, Theorem 4.1, which asserts that in a family of (q + 1)-regular n-hypergraphs {Xj } with radius approaching infinity as j increases, for each 1 ≤ i ≤ n − 1, the closure of the eigenvalues of Ai on Xj for all j contains the spectrum of Ai on the building Bn,F . This leads us to call a (q + 1)-regular n-hypergraph Ramanujan if its nontrivial eigenvalues with respect to Ai lie in the spectrum of Ai on the building Bn,F , for all 1 ≤ i ≤ n − 1. In section 5 we construct, for each prime power q and positive integer n ≥ 3, an infinite family of (q + 1)-regular n-hypergraphs based on the multiplicative group D of a division algebra of dimension n2 over a function field. For cuspidal automorphic representations of GLn over a function field, Lafforgue has proved the Ramanujan conjecture, as a consequence of [L]. Unfortunately the global Jacquet– Langlands correspondence over a function field, which presumably gives an injection from infinite-dimensional automorphic representations of D to cuspidal automorphic representations of GLn such that the corresponding representations have isomorphic local components at the places unramified in the division algebra, is not yet established for all n ≥ 3. We circumvent this difficulty by using results of Laumon–Rapoport–Stuhler [LaRS], in which the authors established the Ramanujan conjecture for automorphic representations of D which has one local component at an unramified place being a Steinberg representation. This is done by suitably choosing two division algebras and compare their trace formulae, following a suggestion of L. Clozel. The buildings considered in this paper are over local fields with positive characteristic and the Ramanujan hypergraphs are their finite quotients. In [Ba] Ballantine constructed 3-hypergraphs as quotients of the building attached to PGL3 over Q p , and proved that they are Ramanujan using representation theory. This paper is organized as follows. The combinatorial assumptions and operators for hypergraphs are introduced in section 2. While it is well known that the Bruhat–Tits building associated to PGLn over a nonarchimedean local field is a regular hypergraph, we give a complete proof of this fact in section 3 for the sake of self-containedness. We also take this opportunity to set up notation and terminologies to be used in later sections. In section 4 we study the behavior of the eigenvalues of the adjacency operators acting on functions on (the vertices of) a family of regular hypergraphs whose radii tend to infinity, and obtain a hypergraph analogue of the Alon–Boppana theorem for regular graphs. This result leads us to

382

W.-C.W. LI

GAFA

the definition of Ramanujan hypergraphs. Finally in section 5, an infinite family of (q + 1)-regular Ramanujan hypergraphs is constructed for prime powers q. The author would like to thank L. Clozel for his suggestion, J. Hoffman for his comments, and C. Ballantine, P. Sarnak, and J.-K. Yu for inspiring conversations. Part of the research was done in 2000 when the author was visiting the Institute for Advanced Study at Princeton, NJ, supported by the Ellentuck Fund, to which she expresses sincere thanks. After this paper was accepted, the author became aware of the papers [CSZ] and [LuSV] in which Ramanujan complexes of type A˜n are considered. These objects are in fact Ramanujan hypergraphs defined in this paper. The construction in these two papers deals with PGLn directly, instead of with division algebras as we do in this paper. Also, the investigation of the spectral growth is one of the themes of our paper, while it is not mentioned in these two papers.

2

Hypergraphs

An n-hypergraph X consists of a set of vertices and a set of hyperedges with each hyperedge being a simplex on n vertices so that X is an (n − 1)dimensional simplicial complex. We assume (P) (type) Each vertex x has a type τ (x) belonging to Z/nZ such that no two vertices of the same type are adjacent. The type difference t(x, y) of two vertices x and y of X is the integer between 0 and n − 1 representing τ (y) − τ (x). We define n − 1 adjacency operators Ai = Ai (X), 1 ≤ i ≤ n − 1, acting on functions f on vertices of X so that at a vertex x of X,
f (y) . Ai f (x) = y adjacent to x,t(x,y)=i

Since y is a neighbor of x with t(x, y) = i if and only if x is a neighbor of y with t(y, x) = n − i, this shows that (t) (transpose) The operators Ai and An−i are transpose of each other. Next we assume (C) (commutativity) The operators Ai , 1 ≤ i ≤ n − 1, on X commute. Proposition 2.1. The commutativity condition (C) is equivalent to

Vol. 14, 2004

RAMANUJAN HYPERGRAPHS

383

(U) (uniformity) For each pair of vertices x, y of X and any i, j ∈ Z/nZ such that τ (y) = τ (x) + i + j, the number of common neighbors of x and y of type τ (x) + i is the same as those of type τ (x) + j. Proof. Parametrize the rows and columns of each Ai by vertices of X. Then the xy-th entry of Ai is 1 if y is a neighbor of x with t(x, y) = i, and 0 otherwise. Thus the xy-th entry of Ai Aj counts common neighbors z of x and y with τ (z) = τ (x) + i and τ (y) = τ (z) + j. Hence Ai Aj = Aj Ai if and only if for all pairs of vertices x, y of X with τ (y) = τ (x) + i + j, there are as many common neighbors of x and y of type τ (x) + i as those of type 2 τ (x) + j. Since Ai + An−i is symmetric and Ai − An−i is skewsymmetric, both operators are diagonalizable. The commutativity assumption (C) then implies that they are simultaneously diagonalizable, and hence Ai and An−i are simultaneously diagonalizable. Under the assumption (C) we get (d) (diagonalizable) The operators Ai are simultaneously diagonalizable, and the space of functions on vertices of X has an orthonormal basis consisting of common eigenfunctions of the Ai ’s. Observe that if f is a (common) eigenfunction of Ai with eigenvalue αi for 1 ≤ i ≤ n − 1, then αi and αn−i are complex conjugate of each other since their sum is real and their difference is purely imaginary, as a result of Ai + An−i being symmetric and Ai − An−i being skewsymmetric. Consequently, eigenfunctions with different eigenvalues of a fixed Ai are orthogonal with respect to the usual inner product  ,  on complex valued functions supported on a finite set. An (n − 1)-dimensional hypergraph X is called (k + 1)-regular if it satisfies the following regularity condition. (R) (regularity) For i = 1, . . . , n − 1, each vertex x has exactly (kn − 1) · · · (k − 1) kn,i := i (k − 1) · · · (k − 1)(kn−i − 1) · · · (k − 1) neighbors of type τ (x) + i. Thus a (q + 1)-regular 2-hypergraph is nothing but a (q + 1)-regular bipartite graph.

3

Bruhat–Tits Buildings

Let F be a nonarchimedean local field with q elements in its residue field κ. Let OF be its ring of integers and π a uniformizing element. The goal of

384

W.-C.W. LI

GAFA

this section is to prove the following assertion and also to lay ground work for later sections. Proposition 3.1. The Bruhat–Tits building Bn,F :=PGLn (F )/PGLn (OF ) is a (q + 1)-regular n-hypergraph. Each vertex x of the building, when expressed as gGLn (OF )Z(F ) for some g ∈ GLn (F ) with Z the center of GLn , is an equivalence class of the rank n lattice Lx over OF with basis the columns of g. The determinant of g is π m times a unit in OF , and the integer m is well defined modulo n, which defines the type τ (x) of x. Two vertices x and y of Bn,F with τ (y) = τ (x)+i for some 1 ≤ i ≤ n−1 are adjacent if and only if x and y can be represented by some lattices Lx and Ly such that Lx ⊃ Ly ⊃ πLx and the index [Lx : Ly ] = q i . Vertices x1 , . . . , xn form an hyperedge if and only if the vertices x1 , . . . , xn can be represented by lattices L1 , . . . , Ln so that L1 ⊃ · · · ⊃ Ln ⊃ πL1 . Hence the condition (P) holds. Let x and y be two distinct vertices in Bn,F with a common neighbor z. Then there are lattices Lx , Ly , Lz such that Lz ⊃ Lx ⊃ πLz and Lz ⊃ Ly ⊃ πLz . Therefore Lz ⊃ Lx + Ly ⊃ Lx ∩ Ly ⊃ πLz , or equivalently, (3.1) Lx + Ly ⊃ Lx ∩ Ly ⊃ πLz ⊃ π(Lx + Ly ) . a b Write q = [Lx + Ly : Lx ] and q = [Lx + Ly : Ly ]. Then [Lx : Lx ∩ Ly ] = q b and [Ly : Lx ∩ Ly ] = q a . Interchanging the role of x and y if necessary, we may assume that b ≤ n − a. By (3.1), any common neighbor z of x and y can be represented by a lattice πLz contained in Lx ∩ Ly and containing π(Lx + Ly ). In particular, τ (z) = τ (x) + i, where i = b + d with q d = [Lx ∩ Ly : πLz ], and τ (y) = τ (z) + j, where j = c + b with q c = [πLz : π(Lx + Ly )]. Note that [Lx + Ly : Lx ∩ Ly ] = q a+b so that a + b + c + d = n. We have to show that the sublattices of Lx ∩ Ly with index q d containing π(Lx + Ly ) is equal to those with index q c . Since the quotient W := (Lx ∩ Ly )/π(Lx + Ly ) is a vector space over the residue field κ of dimension c + d, it suffices to show that W contains as many subspaces over κ of dimension c as those of dimension d. To prove this, we identify W with the additive group of a degree c + d field extension M of κ. The trace map T rM/κ defines a κ-bilinear nondegenerate pairing from M × M to κ by sending (α, β) to T rM/κ (αβ). For a κ-subspace V of M , let V ⊥ be the set of elements β in M such that T rM/κ (V β) = 0.

Vol. 14, 2004

RAMANUJAN HYPERGRAPHS

385

Then V ⊥ is a κ-subspace of M with dim V + dim V ⊥ = dim M = c + d. As V runs through all κ-subspaces of dimension c, V ⊥ runs through all κ-subspaces of dimension d. This proves (U) and hence the operators Ai on Bn,F commute. For 1 ≤ i ≤ n − 1, the operator Ai on Bn,F is the Hecke operator Ti which acts on the functions defined on vertices of Bn,F by convolution with the characteristic function of the PGLn (OF )-double coset   π     .. i   .       π   PGLn (OF ) . PGLn (OF )   1     . .  .  1 In other words, if we express this double coset as a disjoint union of αPGLn (OF ) with α ∈ Si , then
f ([gα]) , [g] ∈ Bn,F . (Ai f )([g]) = α∈Si

We may choose coset representatives α in Si to be upper-triangular with determinant π i , entries in OF , and diagonal entries being π or 1. To α we associate the vector w = (w1 , . . . , wn ) ∈ {0, 1}n so that wj = 1 if and only if the j-th diagonal entry of α is π. Call w the type of α and the set {1 ≤ j ≤ n : wj = 1}, denoted by Supp(w), the support of α or w. Clearly, the n support of any element in Si has cardinality i. Denote by Ii the set of i vectors w with support size i. To each w ∈ Ii , define e(w) = in − i(i − 1)/2 − w1 − 2w2 − · · · − nwn . Partition the representatives in Si according to the type w ∈ Ii . For each w, there are q e(w) representatives α of type w, which we shall choose as follows: (1) The jj-th entry of α is π if j ∈ Supp(w) and it is 1 otherwise; (2) For  > j, the j-th entry of α is 0 unless the jj-th entry is π and the -th entry is 1, in which case the j-th entry lies in OF modulo πOF . Call these basic matrices of type w. The regularity condition (R) will follow from Lemma 3.2. For each 1 ≤ i ≤ n − 1, we have
q e(w) . qn,i = w∈Ii

386

W.-C.W. LI

GAFA

Proof. First examine the case i = 1 and n ≥ 2. We have =  qn,1e(w) n n−1 n−2 +q + · · · + q + 1, which is equal to w∈I1 q (q − 1)/(q − 1) = q since for each 1 ≤ j ≤ n, I1 contains exactly one element w(j) whose j-th component is equal to 1, and by definition, e(w(j)) = n − j. To proceed, we prove by induction on i, and for fixed i, by induction on n ≥ i + 1. We may assume i ≥ 2. To avoid ambiguity, we shall write Ii (n) to indicate that the vectors have length n and support size i. If n = i + 1, then qn,i = qn,1 = q n−1 + q n−2 + · · · + q + 1 . On the other hand, for each 1 ≤ j ≤ n, Ii (n) contains exactly one element w(j) whose j-th component is equal to 0, and by definition, e(w(j)) = in − i(i − 1)/2 − n(n + 1)/2 + j = j − 1 since i = n − 1. This proves the desired statement for n = i + 1. Now assume n > i + 1. Partition the elements w = (w1 , . . . , wn ) in Ii (n) into two sets: those with wn = 0, which may be identified with elements in Ii (n − 1), and those with wn = 1, which, after deleting wn , may be identified with elements in Ii−1 (n − 1). To keep track of the length n of elements in Ii (n), we denote the first set by Ii (n − 1) and the second set by Ii−1 (n − 1) . Thus the sum over Ii (n) splits into two sums accordingly, and we may apply induction hypothesis for each sum. More precisely, the first sum is


q e(w ) = q i q e(w) = q i qn−1,i , w
∈Ii (n−1)


w∈Ii (n−1)

while the second
sum is




q e(w ) =

w
∈Ii−1 (n−1)





q e(w) = qn−1,i−1 .

w∈Ii−1 (n−1)

One checks easily that q i qn−1,i + qn−1,i−1 = qn,i , as desired. This completes the proof of Proposition 3.1. Since the Bruhat–Tits building is topologically contractible, it serves as a universal cover. It is a higher dimensional analogue of the tree PGL2 (Qp )/PGL2 (Zp ). Like the case of tree, we obtain finite (q + 1)-regular n-hypergraphs by dividing by suitable discrete congruence subgroups of PGL(n, F ) on the left. In what follows, we consider only (q + 1)-regular n-hypergraphs whose univesal covers are the building Bn,F . The operator spectrum of Ai acting on the space of L2 -functions on Bn,F was computed by Macdonald [M1,2]. Denote by σi (z1 , . . . , zn ) the ith elementary symmetric polynomial in z1 , . . . , zn , that is, the sum over all

Vol. 14, 2004

RAMANUJAN HYPERGRAPHS

387

possible choices of (unordered) product of i elements from z1 , . . . , zn with different indices. Let    Ωn,i := σi (z1 , . . . , zn )  z1 , . . . , zn ∈ C× , |z1 | = · · · = |zn | = 1, z1 · · · zn = 1 . Then the spectrum of Ai , 1 ≤ i ≤ n − 1, on Bn,F is dilation by q i(n−i)/2 of Ωn,i . Clearly Ai and An−i have the same spectrum. The geometric shape of Ωn,i was explicitly described by Cartwright and Steger [CS]. They showed that the boundary of Ωn,i is the curve traced by σi (eiθ , . . . , eiθ , e−i(n−1)θ ) as θ varies from 0 to 2π.

4

The Growth of the Spectra of Finite Quotients of the Bruhat–Tits Building

In this section fix a family {Xj } of finite (q + 1)-regular n-hypergraphs such that |Xj | → ∞ as j → ∞. The purpose of this section is to establish a higher dimensional analogue of the Alon–Boppana theorem. More precisely, given 1 ≤ i ≤ n − 1, the closure of the nontrivial eigenvalues of Ai on Xj as j → ∞ will at least contain the spectrum of Ai on Bn,F . As explained in [Li1], this does not hold unconditionally for a family of regular graphs. Thus we impose a simple condition on Xj by requiring the radius of Xj to go to infinity as j → ∞. Here a (q + 1)-regular n-hypergraph X is said to have radius d if d is the largest integer m such that there is a ball Bu (m) in X centered at some vertex u in X with radius m which is isomorphic to a ball of radius m in the building Bn,F . From this point on, the distance between two vertices is the length of a geodesic path connecting the two vertices via 1-simplicies; each 1-simplex has length 1. Theorem 4.1. Given complex numbers z1 , . . . , zn with |z1 | = · · · = |zn | = 1 and z1 · · · zn = 1, write λi for q i(n−i)/2 σi (z1 , . . . , zn ) for i = 1, . . . , n − 1. Let {Xj } be a family of finite (q + 1)-regular n-hypergraphs such that the radius of Xj tends to infinity as j approaches infinity. Then for each j ≥ 1, there is a function fj on the vertices of Xj of norm 1 such that for i = 1, . . . , n − 1, the norm of Ai (Xj )fj − λi fj approaches zero as j → ∞. Moreover, if z1 = · · · = zn = 1, fj may be chosen to be real-valued and orthogonal to the constant functions on Xj . Denote by  ,  the usual Hermitian inner product on complex-valued functions with finite support. Theorem 4.1 will follow from Theorem 4.2. For i = 1, . . . , n − 1, let λi be as in Theorem 4.1. If X is a finite (q +1)-regular n-hypergraph of radius d+2, then there is a function f

388

W.-C.W. LI

GAFA

on X such that for 1 ≤ i ≤ n − 1, Ai f − λi f, Ai f − λi f /f, f  approaches zero as d → ∞. If, furthermore, all zi are 1, then f may be chosen to be real-valued and perpendicular to the constant functions on X. We begin the proof of Theorem 4.2. By assumption, there is a ball Bu (d + 2) in X which is isomorphic to a ball of radius d + 2 in the building Bn,F . Since f will be zero outside the ball Bu (d + 2), we may assume that Bu (d + 2) is a ball of radius d + 2 in Bn,F and u is the coset [id]. First we analyse the vertices in Bn,F . Order the elements w in n−1 i=1 Ii so that w = (w1 , . . . , wn ) is greater than w = (w1 , . . . , wn ) if wj > wj where  . Observe that given 1 ≤ i ≤ n − 1, j is the largest index m with wm = wm among all types w ∈ Ii , w(i) := (1, . . . , 1, 0, . . . , 0)    i

is the smallest in order and the number, q e(w(i)) = q i(n−i) , of basic matrices
of type w(i) is the largest. In fact, for other w in Ii , the number q e(w ) of basic matrices of type w is at most q e(w(i))−1 . We call such w(i) minimal. Denote by M (w) a basic matrix of type w. To proceed, we need Lemma 4.3. Let M (u) and M (v) be two basic matrices of types u = (u1 , . . . , un ) and v = (v1 , . . . , vn ) respectively. Suppose um = vm for j +1 ≤ m ≤ n and uj < vj (so that u < v). Then u = (u1 , . . . ,uj−1 ,vj ,uj+1 , . . . ,un ) is greater than v = (v1 , . . . , vj−1 , uj , vj+1 , . . . , vn ), and there are basic matrices M (u ), M (v ) such that M (u)M (v) = M (u )M (v )κ for some unipotent matrix κ in GLn (OF ). Proof. Denote by uik , vik the ik-th entry of M (u), M (v), respectively. Both matrices are upper triangular with entries in OF . Further, we know from assumption that (i) ujj = 1, uij = 0 for i < j with uii = 1, and ujk = 0 for k = j; (ii) vjj = π, vij = 0 for i < j, and vjk = 0 for k > j with vjj = π; (iii) ukk = vkk for k > j.  ) of types Define below two new basic matrices U  = (uik ) and V  = (vik     u and v as prescribed. Let vik = vik for all i = j and vjk = ujk for all k. Obviously V  is a basic matrix of type v , which we call M (v ). Let ujk = vjk for all k, uij = 0 for i = j and uik = uik + uij vjk for i = j and k = j. Note that the diagonal elements of U  has type u . Further, if uij vjk is nonzero for some i = j and k = j, then i < j with uii = π and k > j with vkk = 1. Since ukk = ukk = vkk (= 1), the ik-th entry of U  can be any

Vol. 14, 2004

RAMANUJAN HYPERGRAPHS

389

element in OF mod π. This shows that U  is also a basic matrix, which we call M (u ).  The ik-th entry of M (u)M (v) is im vmk , while the ik-th entry i≤m≤k u      , which is equal to i≤m≤k u of U V is i≤m≤k uim vmk im vmk for i > j by   u v = v , and definition. If i = j, then jm mk jk j≤m≤k j≤m≤k ujm vmk =  j<m≤k vjm vmk + vjj ujk , which is also equal to vjk since for j < m ≤ k, vjm = 0 implies vmm = 1 which in turn implies vmk = 0 for m < k, and ujk = 0 for j < k. Finally we check the case i < j. In this case,

 uim vmk = (uim + uij vjm )vmk i≤m≤k

i≤m≤k, m=j

=




i≤m≤k

uim vmk − uij vjk +




uij vjm vmk ,

i≤m≤k, m=j

  which is equal to i≤m≤k uim vmk for k = j and i≤m≤k uim vmk − uij vjj for k = j by the same argument as above. Since the jj-th entry of U  V  is π and −uij vjj = −uij π, there is a unipotent matrix κ in GLn (OF ) such that M (u)M (v) = M (u )M (v )κ, This proves the lemma. Given a vertex [g] in Bn,F , by Iwasawa decomposition, we may write g = κακ with κ and κ in GLn (OF ), and α a diagonal matrix with nonzero entries being powers of π. If [g] has distance m to [id], then, modulo center, α is a product of m diagonal matrices whose nonzero entries are either 1 or π. By section 3, we may represent [g] by a product of m basic matrices. Note that if κ is a unipotent matrix in GLn (OF ) and M is a basic matrix, then κM = M  κ for some basic matrix M  of the same type as M and some unipotent matrix κ in GLn (OF ). Hence applying Lemma 4.3 repeatedly, we obtain Proposition 4.4. A vertex [g] in Bn,F of distance m to [id] can be represented as a product of m basic matrices [g] = [M (1 w) · · · M (m w)], where the types are in nonincreasing order 1 w ≥ 2w ≥ . . . ≥ mw . A vertex [g] is said to be of minimal type if each j w above is minimal. In this case, the support sequence of [g] is nonincreasing: Supp1 w ⊃ Supp2 w ⊃ . . . ⊃ Suppm w.

(4.1)

Observe that Lemma 4.5. If [g] in Bn,F is of minimal type, then the types occurring in representing [g] as a product of basic matrices are unique.

390

W.-C.W. LI

GAFA

Proof. First note that if w = (1, . . . , 1), then M (w), being π times the identity matrix, lies in the center of GLn and hence is not needed in representing an element in the building. So we may assume that the size of the support of each basic matrix in [g] = [M (1 w) · · · M (m w)] is at most n − 1. Denote by e(j) the number of types among 1 w, · · · , m w of support size j. To show the uniqueness of minimal types occurring in [g], it suffices to give an interpretation of e(j) depending only on [g]. The assumption that [g] is of minimal type implies that we may write g as a product of an upper triangular matrix b with integral entries and last diagonal entry 1 by an element x in P GLn (OF ) on the right. The diagonal entries of b are unique up to unit multiples. The expression above shows that up to a unit multiple, the jj-th entry of b is equal to π raised to (e(n − 1) + · · · + e(j))-th power. This proves the uniqueness of the e(j)’s. Denote by Mu (d) the subset of vertices of Bu (d) of minimal type, and by Mu0 (d) the set of interior points of Mu (d), namely, those vertices [g] whose support sequence (4.1) contains {1, 2, . . . , n − 1} ⊃ {1, 2, . . . , n − 2} ⊃ . . . ⊃ {1, 2} ⊃ {1} as a subsequence. Set for j = 1, . . . , n − 1 . aj = q −j(n−j)/2 z1 · · · zj Given a type w = (w1 , . . . , wn ), let wn−1 −wn 1 −w2 w2 −w3 a2 · · · an−1 . a(w) = aw 1 Lemma 4.6. a(u )a(v ).

Let u, v, u , v be as in Lemma 4.3.

Then a(u)a(v) =

Proof. In view of the definitions of u, v, u , v and a(w), it suffices to show that uj−1 −uj+1 vj−1 −1 1−vj+1 uj−1 −1 1−uj+1 vj−1 −vj+1 aj aj−1 aj = aj−1 aj aj−1 aj , aj−1 which obviously holds. Define the function f to be zero outside Mu (d + 1), and for [g] = [M (1 w) · · · M (m w)] ∈ Mu (d + 1), define f ([g]) = a(1 w) · · · a(m w) , which depends only on the type of M (j w), and hence is well defined by Lemma 4.5. Note that if δ(i) is the number of j w with support size i, then δ(1)

f ([g]) = a1 so that

δ(n−1)

· · · an−1

  f ([g]) = q (−1(n−1)δ(1)−2(n−2)δ(2)−···−(n−1)1δ(n−1))/2 ,

Vol. 14, 2004

RAMANUJAN HYPERGRAPHS

391

while the number of vertices in Mu (d+1) of the same type sequence as [g] is |f ([g])|−2 . Consequently, the inner product f, f  is equal to the number of nonincreasing sequences of length at most d + 1 of vectors w with minimal type. Such number is equal to


··· 1 =: fn−1 (d + 1) . (4.2) 0≤v1 ≤d+1 0≤v2 ≤v1

0≤vn−1 ≤vn−2

Observe that f1 (x) = x + 1, and, by induction, for m ≥ 2, fm (d) =  0≤v1 ≤d fm−1 (v1 ) is a polynomial in d over Q of degree m. Consequently we have Proposition 4.7. The number of different support sequences occurring in the elements of Mu (d + 1) is fn−1 (d + 1) defined by (4.2), which is a polynomial in d + 1 over Q of degree n − 1. Further, the function f defined above satisfies f, f  = O((d + 1)n−1 ) for n fixed and d large. Lemma 4.8. For [g] ∈ Mu0 (d), all neighbors of [g] lie in Mu (d + 1). Proof. Represent [g] by M = M (1 w) · · · M (m w) with m ≤ d. The neighbors of [g] are represented by right multiplication of M by basic matrices M (w) for all types w of length n. Since [g] lies in Mu0 (d), the types 1 w, · · · , m w are all minimal, and their supports are {1, . . . , n − 1}, . . . , {1} with multiplicities. If the support of w is {1}, then M (w) is minimal and hence [gM (w)] lies in Mu (d + 1). If w > m w, by applying Lemma 4.3 repeatedly, we may represent [gM (w)] by a product of at m + 1 basic matrices with nonincreasing types, after removing those lying in PGLn (OF ). These basic matrices all have minimal support because the supports of i w’s are as described above. This shows that [gM (w)] lies in Mu (d + 1). Now fix an i between 1 and n − 1 and [g] in the building Bn,F . Then (Ai f )([g]) is the sum of f ([gM (w)]) as w runs through all elements in Ii and M (w) runs through all basic matrices of type w. It follows from Lemmas 4.3 and 4.6 as well as the fact that a(w) = 1 for w = (1, . . . , 1) or (0, . . . , 0) that f ([gM (w)]) = f ([g])a(w) as long as [g] and [gM (w)] are simultaneously in or not in Mu (d + 1). As remarked in section 3, there are preciesely q e(w) basic matrices of type w ∈ Ii . We claim that, for w = (w1 , . . . , wn ) in Ii , q e(w) a(w) = q i(n−i)/2 z1w1 · · · znwn . To see this, we examine the powers of q and the zj ’s on both sides. On the left-hand side, the zj ’s only appear in a(w), given by wn−1 −wn wn−1 w1 −wn · · · zn−1 = z1w1 · · · zn−1 (z1 · · · zn−1 )−wn = z1w1 · · · znwn (since z1

392

W.-C.W. LI

GAFA

z1 · · · zn−1 zn = 1), which is the same as the right-hand side. The total power of q in q e(w) a(w) is in−i(i−1)/2−w1 −2w2 −· · ·−nwn −1(n−1)(w1 − w2 )/2 − 2(n − 2)(w2 − w3 )/2 − · · · − (n − 1)1(wn−1 − wn )/2, which is equal to in − i(i − 1)/2 − ((n + 1)/2)(w1 + · · · + wn ) = in − i(i − 1)/2 − i(n + 1)/2 = i(n − i)/2, also the same as the right-hand side. Combined with Lemma 4.8, we have proven Lemma 4.9. For 1 ≤ i ≤ n − 1 and [g] ∈ Mu0 (d), we have
q e(w) a(w) = λi f ([g]) . (Ai f )([g]) = f ([g]) w∈Ii

This is also valid if neither [g] nor its neighbors of type difference i lie in Mu (d + 1). Therefore Ai f − λi f is zero except possibly on (4.i) the set Mu (d + 1) − Mu0 (d) of boundary points; (4.ii) vertices in Bu (d + 2) − Mu (d + 1) which have some neighbors falling in Mu (d + 1). It remains to estimate the contribution of Ai f − λi f on these two kinds of points and compare them with f, f . Given a boundry point [g] in Mu (d + 1) − Mu0 (d) and w ∈ Ii , if one [gM (w)] does not lie in Mu (d + 1), then the same holds for all basic matrices M (w) of the same type; in this case we have f ([gM (w)]) = 0 instead of f ([g])a(w) for all basic matrices M (w) of the same type. Hence
q e(w) a(w) . Ai f ([g]) − λi f ([g]) = −f ([g]) w∈Ii ,[gM (w)]∈Mu (d+1) summand q e(w) a(w) has absolute

value q i(n−i)/2 As computed above, each n and there are less than i types occurring in the above sum (since the minimal type with support size i does not occur), we conclude that       Ai f ([g]) − λi f ([g]) < n q i(n−i)/2 f ([g]) . i This estimate holds for all elements in Mu (d + 1) − Mu0 (d) with the same support sequence as [g], and there are exactly |f ([g])|−2 such elements as observed before. Hence, for fixed n, the contribution of points in (4.i) to the inner product Ai f −λi f, Ai f −λi f  is bounded by a constant times the number of different support sequences of elements in Mu (d + 1) − Mu0 (d). Proposition 4.10. The number of different support sequences occurring in elements of Mu0 (d) is


··· 1 = fn−1 (d − n + 1) . n−1≤v1 ≤d n−2≤v2 ≤v1 −1

Here fm (x) is defined by (4.2).

1≤vn−1 ≤vn−2 −1

Vol. 14, 2004

RAMANUJAN HYPERGRAPHS

393

Proof. The left-hand side of the equation clearly is the desired number. The remaining work is to recognize it as the right-hand side. Note that for 2 ≤ j ≤ n − 1, we have vj−1 − 1 ≥ vj ≥ n − j. When n = 2, the sum is d = f1 (d − 2 + 1). We see by induction that the sum over v2 , . . . , vn−1 is equal to fn−2 (v1 − 1 − (n − 1) + 1) = fn−2 (v1 − n + 1) so that summing over v1 yields fn−1 (d − n + 1). An immediate consequence of Propositions 4.7 and 4.10 is Corollary 4.11. The number of different support sequences occurring in elements of Mu (d + 1) − Mu0 (d) is fn−1 (d + 1) − fn−1 (d − n + 1), which is O((d + 1)n−2 ) for n fixed and d → ∞. Therefore the contribution from points in (4.i) to the inner product Ai f − λi f, Ai f − λi f  is O((d + 1)n−2 ) as n fixed and d → ∞. Finally we discuss the contribution from points in (4.ii). Let [g] be a point in Bu (d + 2) − Mu (d + 1). Then f ([g]) = 0 and the nonzero contributions to (Ai f −λi f )([g]) come from the neighbors of [g] in Mu (d+1). More precisely,
    f ([g ])2 , Ai f ([g]) − λi f ([g])2 ≤ [g
]

where [g ] runs through points in Mu (d + 1) which are adjacent to [g] with type difference t([g], [g ]) = i. Note that none of the neighbors of [g] fall in Mu0 (d) because of Lemma 4.8. Further, [g ] ∈ Mu (d + 1) is a neighbor of [g] with t([g], [g ]) = i if and only if [g] is a neighbor of [g ] with t([g ], [g]) = n−i. Since each vertex has at most qn,n−i neighbors of type difference n−i, the contribution of points in (4.ii) to the inner product Ai f −λi f, Ai f −λi f 
  is at most f ([g ])2 , qn,n−i [g
]∈(4.i)

which is qn,n−i times the total number of different support types in Mu (d + 1) − Mu0 (d). Hence, from Corollary 4.11 we conclude that the contribution from points in (4.ii) to the inner product Ai f − λi f, Ai f − λi f  is also O((d + 1)n−2 ). In summary, we have shown Proposition 4.12. Ai f − λi f, Ai f − λi f  is O((d + 1)n−2 ) for n fixed and d large. Now the first part of Theorem 4.2 follows from Propositions 4.7 and 4.12. If all zi ’s are 1, then f constructed above is positive valued on Mu (d + 1) and zero elsewhere. To get a function as desired, take two vertices u and

394

W.-C.W. LI

GAFA

u in Bu (d + 1) such that the two balls Bu
([(d − 1)/2]) and Bu

([(d − 1)/2]) are disjoint and contained in Bu (d + 1). Denote by f  and f  two functions supported on Bu
([(d−2)/2]) and Bu

([(d−2)/2]), respectively, constructed by the same way as above. Then f = f  − f  has the property described in the second assertion. This completes the proof of Theorem 4.2 and hence Theorem 4.1. By property (d), let g1 , . . . , gm(j) be an orthonormal basis of functions on the vertices of Xj consisting of common eigenfunctions of all Ai (Xj ). Fix an i with 1 ≤ i ≤ n − 1. Let λj1 , . . . , λjm(j) be the corresponding eigenvalues of Ai (Xj ). Express fj in Theorem 4.1 as a linear combination of g1 , . . . , gm(j) : fj = c1 g1 + · · · + cm(j) gm(j) with complex coefficients c1 , . . . , cm(j) . |c1 |2 + · · · + |cm(j) |2 = 1. We have

The norm of fj being 1 yields

Ai (Xj )fj = c1 λj1 g1 + · · · + cm(j) λjm(j) gm(j) so that   Ai (Xj )fj −λi fj , Ai (Xj )fj −λi fj =|λj1 −λi |2 |c1 |2 +· · ·+|λjm(j) −λi |2 |cm(j) |2 , which approaches zero as j tends to ∞. If λi does not lie in the closure of the set of all λjk for j ≥ 1 and 1 ≤ k ≤ m(j), then there is a positive c such that |λjk − λi | > c for all j, k. Consequently, Ai (Xj )fj − λi fj , Ai (Xj )fj − λi fj  is at least c2 for all j, a contradiction. This proves Theorem 4.3. Let Xj be a family of (q + 1)-regular n-hypergraphs as in Theorem 4.1. Then for 1 ≤ i ≤ n − 1, the closure of the collection of eigenvalues of Ai (Xj ), j ≥ 1, contains q i(n−i)/2 Ωn,i , the spectrum of Ai on the building Bn,F . Theorem 4.3 says that the eigenvalues of large (q + 1)-regular n-hypergraphs have a tendency to grow out of the spectrum of the operators Ai on their universal cover, just like what happens for regular graphs. This motivates the following definition of Ramanujan hypergraphs, which is a natural generalization of the definition of Ramanujan graphs. See [Li1] for more discussion. Definition. A finite (k + 1)-regular n-hypergraph X is called Ramanujan if, for 1 ≤ i ≤ n − 1, all eigenvalues of Ai (X) other than kn,i ζnm , 1 ≤ m ≤ n, fall in the region ki(n−i)/2 Ωn,i . Here ζn is a primitive n-th root of unity.

Vol. 14, 2004

5

RAMANUJAN HYPERGRAPHS

395

Explicit Families of Ramanujan Hypergraphs

In this section we fix an integer n ≥ 3, a function field K, and a place v of K with q elements in its residue field. Denote by Kw the completion of K at a place w, and write F for Kv . Let D be a division algebra of center K and of dimension n2 over K, which is unramified at v and totally ramified at ∞. Denote by D the multiplicative group of D modulo its center. Let AK )/D(K∞ )D(Ov )K , XK = D(K) \ D(A  where K is a compact open subgroup of w=∞,v D(Ow ). By strong approximation theory, we may choose double coset representatives locally at v so that we get the following second expression of XK : XK = ΓK \ D(F )/D(Ov ) , where ΓK = D(K) ∩ K is a discrete subgroup of D(F ). By construction, D is unramified at v so that D(F ) = PGLn (F ) and D(F )/D(Ov ) is the building Bn,F . Hence we obtain the hypergraph structure on XK , XK = ΓK \ Bn,F . If ordv (det ΓK ) is not contained in nZ, we may replace ΓK by a congruence subgroup Γ of finite index so that ordv (det Γ) ⊆ nZ. Hence we may assume Γ = ΓK to begin with so that XK is a finite (q + 1)-regular n-hypergraph. The space A(D, K) of functions on vertices of XK are certain automorAK ). Since the 1-skeleton of XK is an n-partite graph, phic forms of D(A A(D, K) contains constant functions as well as their twists by powers of ζn . These are eigenfunctions of Ai , 1 ≤ i ≤ n − 1, with eigenvalues ζnm qn,i . The automorphic forms in the orthogonal complement of these functions lie in the space of certain infinite-dimensional automorphic irreducible repAK ). Since these automorphic forms have trivial local resentations σ of D(A component at ∞, the component of σ at ∞ is the trivial representation of D(K∞ ). If global Jacquet–Langlands correspondence over function fields were known, that is, there is an injection from infinite-dimensional automorphic AK ) such AK ) to cuspidal representations of GLn (A representations of D(A that the corresponding representations and their twists have the same Land ε-factors, then one could use Lafforgue’s result [L] to conclude that the automorphic forms on XK perpendicular to the constant functions and their twists satisfy the Ramanujan conjecture, and hence XK is a Ramanujan hypergraph. Unfortunately, the global Jacquet–Langlands correspondence is not yet completely settled. To-date, it is proved for n = 3 by

396

W.-C.W. LI

GAFA

Jacquet, Piatetskii-Shapiro and Shalika [JPS], and for prime n by Bernstein and Kazhdan. To circumvent this problem, we adopt a suggestion of Clozel by considering two division algebras and using the result by Laumon, Rapoport, and Stuhler [LaRS] instead. We may assume that the division algebra D above is totally ramified at another place ∞ with invariant opposite to that at ∞, and D is also ramified at a nonempty set S of even number of places other than v, ∞, ∞ . Let D  be another division algebra over K of degree n2 and center K which ramifies exactly at the places in S such that at each place other than ∞ and ∞ , D and D are locally isomorphic. Such D  exists since D has opposite invariants at ∞ and ∞ and hence the sum of the invariants of D over the places in S is also zero. Denote by D  the multiplicative group of D  modulo its center. We proceed to compare the infinite-dimensional irreducible AK ) using Selberg AK ) to those of D  (A automorphic representations of D(A AK ) and trace formula, which is known and simple since both D(K)\D(A AK ) are compact. The two groups D(A AK ) and D (A AK ) differ D  (K)\D (A locally only at two places w = ∞, ∞ such that D(Kw ) is the multiplicative group of a division algebra mod center while D  (Kw ) is isomorphic to P GLn (Kw ). At such a place w, the local Jacquet–Langlands correspondence, proved by Badulescu in [B] for local fields of positive characteristic, asserts the existence of a unique map JL from the set of equivalence classes of admissible irreducible representations of D(Kw ) to the equivalence classes of essentially square integrable admissible irreducible repre = JL(π ), then the character of sentations of D  (Kw ) such that if πw w  at the elements which πw is equal to (−1)n−1 times the character of πw have the same separable characteristic polynomials. Here Kw denotes the completion of K at the place w. Theorem 5.1. Given an infinite-dimensional admissible irreducible auAK ), there exists an infinitetomorphic representation π = ⊗w πw of D(A  dimensional admissible irreducible automorphic representation π  = ⊗w πw  = JL(π ) and at places AK ) such that at places w = ∞, ∞ , πw of D (A w   w = ∞, ∞ , the representations πw and πw are isomorphic. Proof. As remarked before, at w = ∞, ∞ , D(Kw ) is the multiplicative group of a division algebra mod center while D  (Kw ) is PGLn . A locally constant function fw with compact support on D(Kw ) is said to correspond to a locally constant function fw on D (Kw ), denoted by fw ↔ fw , if their orbital integrals have the same value on elements of D(Kw ) and D (Kw ) which are regular elliptic with the same characteristic polynomial, and the

Vol. 14, 2004

RAMANUJAN HYPERGRAPHS

397

orbital integrals of fw vanish on regular nonelliptic semisimple elements of D  (Kw ). By Theorem 5.3 of [B], given a locally constant function fw on D(Kw ), there is a locally constant function of compact support fw on D  (Kw ) such that they correspond. At places w = ∞, ∞ , the two local groups D(Kw ), D (Kw ) are isomorphic by construction. Using a fixed isomorphism, we identify locally constant functions with compact support of both groups via fw ↔ fw , and transport the Haar measure on D(Kw ) to D (Kw ). AK ) as given, at the places With a representation π = ⊗w πw of D(A  w = ∞, ∞ choose a locally constant function with compact support fw on D(Kw ) such that trπw (fw ) = 1 and trσw (fw ) = 0 for all admissible irreducible representations σw of D(Kw ) not equivalent to πw . At each place w = ∞, ∞ , let fw be a locally constant function with compact support on D(Kw ) so that fw is the characteristic function of the standard maximal compact subgroup of D(Kw ) for almost all w. Let fw ↔ fw for all places  (f  ) = 1 and trσ  (f  ) = 0 for w of K. Then at w = ∞, ∞ , we have trπw w w w  (K ) not equivalent to π  . all admissible irreducible representations of D w w   Then f = w fw and f  = w fw are locally constant functions with AK ), respectively. We apply the trace AK ) and D (A compact support on D(A formula for D to f and the trace formula for D  to f  and compare them. Given an admissible irreducible infinite-dimensional  automorphic rep AK ), we have trσ(f ) = w trσw (fw ), which resentation σ = ⊗w σw of D(A is equal to zero if σ∞ is not isomorphic to π∞ or σ∞
is not isomor
phic  to π∞ by our choice of fw at these two places; otherwise, trσ(f ) = w=∞,∞
trσw (fw ). Hence the contribution from the spectral side of D is 
m(σ) trσw (fw ) . (5.1) σ=⊗
w σw ,σ∞ =π∞ ,σ∞
=π∞


w=∞,∞


Here the sum is over equivalence classes of representations, and m(σ) denotes the multiplicity of σ occurring in the L2 -space. Similarly, the contribution from the spectral side of D  is 
 m(σ  ) trσw (fw ) . (5.2)
,σ
=π
,σ
=π
σ
=⊗
w σw ∞ ∞ ∞
∞


w=∞,∞


The geometric side of D  involves conjugacy classes of more elements than those occurring in the geometric side of D, namely, those from nonzero elements of number fields contained in D  but not in D. Since at w = ∞, ∞ the orbital integrals of fw vanish on regular nonelliptic semisimple elements of D  (Kw ), the contribution from these extra conjugacy classes is actually equal to zero and the remaining orbital integrals from the geometric side

398

W.-C.W. LI

GAFA

of the two trace formula are equal by our choice of local components of f and f  . This implies that the quantities (5.1) and (5.2) agree. As this is true for all locally constant functions with compact support and with fixed components at w = ∞, ∞ , and, furthermore, outside these two places the two groups D and D  are isomorphic, we conclude that m(σ) = m(σ  ) , for σ occurring in (5.1), σ  occurring in (5.2) so that their components outside ∞, ∞ are locally isomorphic. As π occurs in (5.1), this proves the theorem. Now let the representation π of Theorem 5.1 correspond to an automorphic form in A(D, K). Then the component π∞ is the trivial representation of D∞ (K∞ ). Its image under the map JL is a Steinberg representation of  (K ). By Theorem (14.12) in [LaRS] by Laumon–Rapoport–Stuhler, D∞ ∞ the Ramanujan conjecture holds at the places where π  is unramified. As both πv and πv are unramified and isomorphic, we conclude that XK is Ramanujan. This proves Theorem 5.2. For n ≥ 3 and prime power q, there exists an infinite family of finite (q + 1)-regular Ramanujan n-hypergraphs.

References [ACPTTV] J. Angel, N. Celniker, S. Poulos, A. Terras, C. Trimble, E. Velasquez, Special functions on finite upper half planes, Contemp. Math. 138 (1992), 1–26. [B] A. Badulescu, Orthogonalit´e des caract`eres pour GLn sur un corps local de caract`eristique non nulle, Manuscripta Math. 101 (2000), 49–70. [Ba] C. Ballantine, Ramanujan type buildings, Canadian J. Math. 52 (2000), 1121–1148. [CS] D. Cartwright, T. Steger, Elementary symmetric polynomials in numbers of modulus 1, Canad. J. Math. 54 (2002), 239–262. [CSZ] D. Cartwright, P. Sol´ e, A. Zuk, Ramanujan geometries of type A˜n , Discrete Math. 269 (2003), 35–43. [CePTTV] N. Celniker, S. Poulos, A. Terras, C. Trimble, E. Velasquez, Is there life on finite upper half planes?, Contemp. Math. 143 (1993), 65–88. [Dr] V.G. Drinfel’d, The proof of Petersson’s conjecture for GL(2) over a global field of characteristic p, Functional Anal. Appl. 22 (1988), 28–43.

Vol. 14, 2004

RAMANUJAN HYPERGRAPHS

399

[E]

M. Eichler, Quatern¨ are quadratische Formen und die Riemannsche Vermutung f¨ ur die Kongruenzzetafunktion, Arch. Math. 5 (1954), 355–366. [JPS] H. Jacquet, I.I. Piatetskii-Shapiro, J. Shalika, Automorphic forms on GL3 , I & II, Ann. of Math. 109 (1979), 169–258. [L] L. Lafforgue, Chtoucas de Drinfeld et correspondence de Langlands, Invent. Math. 147 (2002), 1–241. [LaRS] G. Laumon, M. Rapoport, U. Stuhler, D-elliptic sheaves and the Langlands correspondence, Invent. Math 113 (1993), 217–338. [Li1] W.-C.W. Li, On negative eigenvalues of regular graphs, C.R. Acad. Sci. Paris, t. 333, S´erie I (2001), 907–912. [Li2] W.-C.W. Li, Character sums and abelian Ramanujan graphs, J. Number Theory 41 (1992), 199–217. [Li3] W.-C.W. Li, Eigenvalues of Ramanujan graphs, Proc. of Workshop on Emerging Applications of Number Theory, (Minneapolis, MN, 1996), IMA Vol. Math. Appl. 109, Springer, New York (1999), 387–403. [LuPS] A. Lubotzky, R. Phillips, P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261–277. [LuSV] A. Lubotzky, B. Samuels, U. Vishne, Ramanujan complexes of type A˜n , preprint (2003). [M1] I.G. Macdonald, Spherical Functions on a Group of p-adic Type, Ramanujan Inst. Publications 2 (1971). [M2] I.G. Macdonald, Symmetric Functions and Hall Polynomials, second edition, Oxford Univ Press, Oxford, 1995. [Ma] G. Margulis, Explicit group theoretic constructions of combinatorial schemes and their application to the design of expanders and concentrators, Problems. Inform. Transmission 24:1 (1988), 39–46. [Me] J.-F. Mestre, La m´ethode des graphes. Exemples et applications, Proc. Int. Conf. on Class Numbers and Fundamental Units of Algebraic Number Fields, Katata, Japan (1986), 217–242. [Mu] M. Morgenstern, Existence and explicit constructions of q + 1 regular Ramanujan graphs for every prime power q, J. Comb. Theory, series B 62 (1994), 44–62. [S] G. Shimura, Correspondances modul¨ aires et les fonctions ζ de courbes alg´ebriques, J. Math. Soc. Japan 10 (1958), 1–28.

Wen-Ching Winnie Li, Department of Mathematics, Pennsylvania State University, University Park, PA 16802, USA [email protected]

Submitted: June 2003 Final version: September 2003