Finite upper half planes over finite fields (Q1908796)

This paper extends results of the author, N. Celniker, S. Poulos, the reviewer, C. Trimble and E. Velasquez on finite upper half planes over finite fields of odd characteristic to finite fields of characteristic 2. The properties of these graphs were discussed in a series of papers. See the reviewer's article [Exp. Math. 5, 15-32 (1996)] for a survey on this subject for fields of odd characteristic. In the survey we also consider finite Euclidean graphs. More details can be found in the author, \textit{S. Poulos}, the reviewer, \textit{C. Trimble} and \textit{E. Velasquez} [Contemp. Math. 173, 15-70 (1994; Zbl 0813.11034)]. The finite upper half plane graphs were created in an effort to find a finite model of the Poincaré upper half plane similar to the finite model of the circle given by \(\mathbb{Z}/n \mathbb{Z}\), viewed as a circle graph. Let \(\mathbb{F}_q\) be a field of odd characteristic. Fix \(\delta\) a non-square in \(\mathbb{F}_q \). The finite upper half plane \(H_q\) consists of points \(x + y \sqrt \delta\) with \(x,y\) in \(\mathbb{F}_q \) and \(y \neq 0\). If \(\mathbb{F}_q\) has even characteristic, one replaces \(\sqrt \delta\) with a root of some irreducible quadratic over \(\mathbb{F}_q\). Just as in the real case if \(g = {a \;b \choose c \;d}\in GL(2, \mathbb{F}_q)\), we can see that \((az + b)/(cz + d)\) is in \(H_q\) if \(z\) is in \(H_q\). Thus one can identify \(H_q\) with \(G/K\), if \(K\) is the subgroup of \(G\) which fixes \(\theta\). There is an analogue of the Poincaré distance defined by \(d(z,w) = {N(z - w) \over \text{Im} z \text{Im} w}\), where if \(z = x + y \theta\), with \(x,y \in \mathbb{F}_q\), we set \(y = \text{Im} z\). And the norm of \(z\) is \(Nz = z \overline z\), where \(\overline z = x + y \overline \theta\), where \(\overline \theta\) is the other root of the irreducible quadratic satisfied by \(\theta\); i.e. \(\overline \theta = \theta^q \). The distance is \(G\)-invariant. Fix \(a \in \mathbb{F}_q\). The graph \(X (\theta, a)\) has as vertices the elements of \(H_q\) and two vertices \(z,w\) are connected by an edge if \(d(z,w) = a\). If \(a \neq 0\) or \(T^2 - 4N\), where the irreducible quadratic satisfied by \(\theta\) is \(x^2 - Tx + N\), the graph has degree \(q + 1\). Over \(\mathbb{F}_4\), the author finds that the icosahedron occurs as one of these graphs. In general many of the graphs are isomorphic. If \(a \neq 0\) or \(T^2 - 4N\), the graphs are connected by Theorem 3.4 of the paper. Theorem 2.10 of the paper shows that the graphs \(X (\theta, a)\) are highly regular and thus one can collapse the adjacency matrix to a \(q \times q\) matrix with the same eigenvalues. See \textit{B. Bollobás} [Graph Theory, Springer (1979; Zbl 0411.05032), p. 159]. Many facts about the collapsed adjacency matrix are proved; e.g., that the entries are among the numbers 0, 1, 2, and \(q + 1\), while any given row has at most 2 entries equal to 1. These results were proved by \textit{S. Poulos} [Ph. D. Thesis, UCSD (1991)] for fields of odd characteristic. Theorems 3.5 and 3.6 show that the girth and diameter of a connected finite upper half plane graph is at most 4. Then conditions are given that determine when 3 occurs. One object of the work is a study of the spectra of adjacency matrices. In particular one asks: Are the graphs \(X (\theta, a)\) Ramanujan in the sense of \textit{A. Lubotzky}, \textit{R. Phillips} and \textit{P. Sarnak} [Combinatorica 8, 261-277 (1988; Zbl 0661.05035)]? This means that if \(\lambda\) is an eigenvalue of the adjacency matrix with \(|\lambda |\neq q + 1\), is it true that \(|\lambda |\leq 2 \sqrt q\)\ ? Such graphs are best possible expanders among \((q + 1)\)-regular graphs as the number of vertices goes to infinity. Here, of course, as \(q\) goes to infinity, so does the degree. Another property of Ramanujan graphs is that the simple random walk on \(X (\theta, a)\) converges particularly rapidly to uniform. Other references for the subject include \textit{A. Lubotzky} [Discrete groups, expanding graphs and invariant measures, Prog. Math. 125 (1994; Zbl 0826.22012)] and \textit{P. Sarnak} [Some applications of modular forms, Cambridge Tracts Math. 99 (1990; Zbl 0721.11015)]. For odd characteristic, the graphs were proved to be Ramanujan using work of \textit{J. Soto-Andrade} [Proc. Symp. Pure Math. 47, 305-316 (1987; Zbl 0652.20047)] and \textit{N. Katz} [J. Reine Angew. Math. 438, 143-161 (1993; Zbl 0798.11053)]. For fields of even characteristic the graphs were proved to be Ramanujan by \textit{R. Evans} [Finite Fields Appl. 1, 376-394 (1995; Zbl 0844.11078)] and \textit{N. Katz} [Finite Fields Appl. 1, 395-398 (1995; see following review)]. See also \textit{Winnie Li} [Astérisque 228, 101-120 (1995; Zbl 0844.11076)] for estimates of the exponential sums involved (in odd characteristic). Li does not require \(\ell\)-adic étale cohomology. Instead she uses A. Weil's proof of the Riemann hypothesis for zeta functions of function fields associated to curves. Finally the author shows that for \(a \neq 0\) or \(T^2 - 4N\), if \(q \neq 3\), the complement of the graph \(X (\theta, a)\) is Ramanujan. And he proves that for fields of even characteristic, 0 is not an eigenvalue of the adjacency matrix.