418 W.-C. W. LI, RAMANUJAN GRAPHS AND RAMANUJAN HYPERGRAPHS
Theorem 2.2. [Li, [23]] Given complex numbers z1, ... , Zn with lz1I = · · · = lznl =
1, write Ai for qi(n-i)/^2 O"i(z1, ... , Zn) for i = 1, ... , n - l. Let { Xj} be a family of
finite (q + l)-regular n-hypergmphs such that the radius of xj tends to infinity as j
approaches infinity. Then for each j 2: 1, there is a function fj on the vertices of
Xj of norm 1 such that for i = 1, ... , n - l, the norm of Ai (Xj) fj -Ai fj approaches
zero as j ---; oo. Moreover, if z 1 = · · · =Zn = 1, fj is real-valued and orthogonal to
the constant functions on Xj.We sketch the proof of this theorem. It suffices to show that if X is a finite
(q + 1)-regular n-hypergraph of radius d + 2, then there is a function f on X suchthat for 1 :::; i :::; n - 1, (Ad - Ai f, Ad - Ai J) / (!, J) approaches zero as d ---; oo.
Here the inner product of two functions g 1 ,g 2 on the vertex set V(X) of Xis
(g1,g2) = "L gl(x)g2(x).
xEV(X)
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 the ball ofradius d + 2 in Bn,F and u is the coset
[id]. Our strategy is to find a suitable large subset of the ball as the support of f
such that (a) one has good control of the neighbors of points in the support; (b) for
1 :::; i :::; n - l , f is an eigenfunction of Ai with eigenvalue Ai on the "interior" of its
support; and ( c) the set of the "boundary" points of the support is small compared
to the size of the " interior" points.
We begin by analyzing the vertices in Bn,F· Order the elements win LJ:-/ Ji
so that w = ( w 1 , ... , wn) is greater than w' = ( w~, ... , w~) if Wj > wj where j is
the largest index m with Wm "I-w~. Observe that given 1 :::; i :::; n - 1, among all
types w Eh
w(i) := (1, ... , 1, 0, ... , 0)
'""--v---'is the smallest in order, and there are qe(w(i)) = qi (n-i) number of basic matrices
of this type, among those of support size i. For other w' in h qe(w') is at most
q e(w(i))-l _ We call such w(i) minimal. Denote by M(w) a basic matrix of type w.
The following Lemma plays an important role in representing cosets in the
building.
Lemma 2.3. Let M(u) and M(v) be two basic matrices of types u = (u 1 , ... , un)
and v = (v1, ... vn) respectively. Suppose Um = Vm for j + 1 :::; m :::; n and Uj < Vj
(so that u < v). Then u' = (u 1 , ... ,Uj-l,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).
By Iwasawa decomposition, an element g in GLn(F) can be expressed as a
product g = "'a"'' with "' and "'' in G Ln ( 0 F), and a a diagonal matrix with
nonzero entries being powers of 1r. If the vertex [g] in Bn,F has distance m to
[id], then, modulo center, a is a product of m diagonal matrices whose nonzero