The finite upper half space and related hypergraphs
The finite upper half plane and the Ramanujan graphs attached to it have as their origin an attempt to find a simple model of the Poincaré upper half plane. In the paper under review a higher rank analogue is found that may be viewed as providing a finite model for the symmetric space of the \(n\times n\) general linear group. See the reviewer's book [\textit{A. A. Terras}, Fourier analysis on finite groups and applications, Cambridge Univ. Press (1999; Zbl 0928.43001)] for a discussion of the finite upper half plane. Other references are: \textit{Wen-Ching Winnie Li} [Eigenvalues of Ramanujan graphs, in IMA Vol. Math. Appl. 109, 387-403 (1999; Zbl 0981.11041)], \textit{A. Lubotzky} [ Discrete groups, expanding graphs and invariant measures, Birkhäuser (1994; Zbl 0826.22012)], and \textit{A. Valette} [Sémin. Bourbaki 1996/97, Exp. No. 829, Astérisque 245, 247-276 (1997; Zbl 0929.05042)]. Let \(\delta\) be a non-square in a finite field with \(q\) elements, denoted \(\mathbb{F}_{q}\) , where \(q\) is an odd prime power. The finite upper half plane \(H_{q}\) is the set of all \(z=x+y\sqrt{\delta}\), such that \(x,y\) \(\in\) \(\mathbb{F}_{q}\) and \(y\) is non-zero. A finite analogue of the Poincaré non-Euclidean distance is defined for \(z,w\) \(\in\) \(H_{q}\) by \[ d(z,w)=\frac{N(z-w)} {\text{Im }z\text{ Im }w},\quad \overline{z}=x-y\sqrt{\delta},\quad Nz=z\overline{z},\quad \text{Im }z=y. \] This distance can be used to define the \textit{finite upper half plane graph} \(X_{q}(\delta,a)\) whose vertices are the elements of \(H_{q}\). Then put an edge between vertices \(z\) and \(w\) if \(d(z,w)=a\). The graph \(X_{3}(2,1)\) is an octahedron, for example. The finite group \(G=\text{GL}(2,\mathbb{F}_{q})\) of all \(2\times 2\) non-singular matrices with entries in \(\mathbb{F}_{q}\) acts on \(z \) in \(H_{q}\) by fractional linear transformation; i.e \(\frac{az+b}{cz+d}. \) Thus one can identify \(H_{q}\) with \(G/K\), where \(K\) is the subgroup of \(G\) fixing \(\sqrt{\delta}\). It can be shown that \(G/K\) is a symmetric space or equivalently that \((G,K)\) is a Gelfand pair, meaning that the algebra of \(K\)-bi-invariant functions on \(G\) is a commutative algebra under convolution on \(G\). The action of \(G\) leaves the distance defined above invariant. Thus we can call \(d(z,w)\) a ``point-pair invariant''. The adjacency operator on the graph leads to an analogue of the Laplace operator on a symmetric space. The spectrum of this operator is thus of interest for many reasons. See the reviewer's book mentioned above. A \(k\)-regular connected graph is said to be Ramanujan if the eigenvalues \(\lambda\) of the adjacency matrix with \(|\lambda|\neq k\) satisfy \(|\lambda|\) \(\leq\) \(2\sqrt{k-1}\). Such graphs are good expanders and provide good communications networks. It turns out that the finite upper half plane graphs are Ramanujan. Estimates for half the eigenvalues can be obtained by looking at a smaller group than \(G\), namely the affine group \(\text{Aff}(q)\) consisting of elements of \(G\) of the form \(\left(\begin{smallmatrix} y & x\\ 0 & 1 \end{smallmatrix}\right)\). However, the estimate of the rest of the eigenvalues requires the representation theory of the finite general linear group plus a study of finite analogues of spherical functions on symmetric spaces. Finally some algebraic geometry was provided by \textit{N. M. Katz} [Finite Fields Appl. 1, 395-398 (1995; Zbl 0851.11073)]. Winnie Li [loc. cit.] has found 2 alternate proofs. \textit{N. Allen} [Finite Fields Appl. 4, 393-440 (1998; Zbl 0913.05072)] considered higher dimensional analogues of the finite upper half plane graphs. Her analysis involved Cayley graphs for a small 3 component group somewhat like the 2 component affine group defined above but smaller than the 5 component group we expected. We should note incidentally that \textit{F. J. Marquez} [UCSD Ph.D. Thesis, 2001] has analyzed this 5 component group and found a finite number of new Ramanujan graphs using some clever arguments involving Kloosterman sums. In the paper under review a different approach is taken. Let us consider only the \(H_{q}^{3}\) case for simplicity. The finite quadratic extension \(\mathbb{F}_{q}(\sqrt{\delta})\) containing the finite upper half plane \(H_{q} \) is replaced by a cubic extension \(\mathbb{F}_{q}(\theta)\), where \(\theta ^{3}+a\theta^{2}+b\theta+c=0\) is an irreducible cubic. This leads to a natural subgroup \(K\) to provide the analogue of the orthogonal group in \(G\). And it replaces the 5 component group with a 6 component group. This larger group is an analogue of the affine group consisting of matrices \(\left(\begin{smallmatrix} Y& x\\ 0 & 1 \end{smallmatrix}\right),\) where \(Y\in \text{GL}(2,\mathbb{F}_{q})\), \(x\in\mathbb{F}_{q}^{2}.\) This paper shows that many of the basic facts about the upper half plane generalize the new upper half space \(H_{q}^{(3)}\) which is composed of vectors \(Z=Y \binom{\theta^2}{\theta}+X,\) where \(Y\in \text{GL}(2,\mathbb{F}_{q})\), \(X\in \mathbb{F}_{q}^{2}.\) The point-pair invariant \(d(z,w)\) defined above is replaced with a point-triple invariant\break \(k(Z_{1},Z_{2},Z_{3})\) defined using a \(3\times 3\) determinant divided by a product of three \(2\times 2\) determinants. This point-triple invariant is then used to create hypergraphs in the same way that the point-pair invariant was used to create finite upper half plane graphs. Hypergraphs are generalizations of graphs whose spectral theory has just begun to be investigated. Think of edges of graphs as 2 element sets of vertices. In hypergraphs, the edges can have more than 2 elements. In the hypergraphs defined here, the edges are 3-element sets obtained by setting the invariant \(k(Z_{1},Z_{2},Z_{3})\) equal to a constant. \textit{K. Feng} and \textit{W.-C. Winnie Li} [Spectra of hypergraphs and applications, J. Number Theory 60, 1-22 (1996; Zbl 0874.05041)] define an analogue of the adjacency operator whose eigenvalues constitute the spectrum of the hypergraph. The advantage of this definition is that it includes a definition of a Ramanujan hypergraph coming from the bound for the continuous spectrum of the universal cover of a \((k,l)\)-regular hypergraph. It is shown that the hypergraphs for \(\text{GL}(3,\mathbb{F} _{q}),q=2 \text{ or }3,\) are indeed Ramanujan in the sense of Feng and Li. We should note in closing that the author also defines hypergraphs for \(\text{GL}(n,\mathbb{F}_{q})\) in a similar manner, but the problem of checking the Ramanujanicity is still open as it is when \(n=2\) and \(q>3\). In a related paper \textit{M. G. Martínez, H. Stark}, and the reviewer [Some Ramanujan hypergraphs associated to \(\text{GL}(n,\mathbb{F}_{q})\), Proc. Am. Math. Soc. 129, No. 6, 1623-1629 (2001; Zbl 1049.11136)] two families of hypergraphs are defined using simpler \(n\)-point invariants than those of the paper under review. One of these hypergraph families includes an infinite number of Ramanujan hypergraphs. Another construction of hypergraphs attached to GL(3) can be found in the papers of \textit{C. Ballantine} [Ramanujan type buildings, Can. J. Math. 52, 1121-1148 (2000; Zbl 0999.20019) and Can. Math. Bull. 44, 385-397 (2001; Zbl 1039.11023)].
general linear group over a finite field
scientific article; zbMATH DE number 1547369
scientific article