Graph spectra for finite upper half planes over rings (Q1899426)

Graphs attached for finite analogues of the Poincaré upper half plane over rings \(\mathbb{Z}/ p^r \mathbb{Z}\) are introduced for \(p\) an odd prime. The spectra of these graphs for \(r=2\) are shown to be related to those for \(r=1\) which were studied earlier. In contrast to the case \(r=1\), we find that the graphs are not Ramanujan graphs when \(r=2\) and \(p\geq 5\). Histograms of the eigenvalues for \(r=1\) and 2 are also compared. The graphs over rings are of interest for connections with \(p\)-adic upper half-planes as well as fundamental domains for congruence subgroups of the modular group \(\text{SL} (2, \mathbb{Z})\). ``An outline of the paper follows. Section 1 defines the distance \(d(z, w)\) for \(z,w\in H_R\), the finite upper half-plane. For \(a\in R= \mathbb{Z}/ p^r \mathbb{Z}\), define the graph \(X_R (\delta, a)\) to have as vertices the elements of \(H_R\). Two vertices \(z\), \(w\) are connected if \(d(z, w)= a\). Theorem 1 shows that if \(a\not\equiv 0\) or \(4\delta \pmod p\), the graph \(X_R (\delta, a)\) is regular of degree \(p^r+ p^{r-1}\). Theorem 2 (proved elsewhere by the first author) says that \(X_R (\delta, a)\) is a Cayley graph for the affine group over \(R\) defined in (1.3). In particular, the graph is connected. Section 2 concerns the representations of the affine group \(\text{Aff} (\mathbb{Z}/ p^2 \mathbb{Z})\). Then the Fourier transform for this group is used to block-diagonalize the adjacency operator for our graphs (see Theorem 3). Section 3 gives properties of the spectra of the graphs \(X_{\mathbb{Z}/ p^2 \mathbb{Z}} (\delta, a)\). The spectra can be subdivided into one, \((p-1)\), and \((p^2 -p)\) dimensional eigenvalues according to the various representations of \(\text{Aff} (\mathbb{Z}/ p^2 \mathbb{Z})\) (by Theorem 3). Theorem 4 shows that the one-dimensional eigenvalues can be computed explicitly. Often they are 0. Otherwise they are either a cosine or \(p\) times an eigenvalue for the corresponding graph \(\text{mod } p\). Theorem 5 is the analogous result for the \((p-1)\)-dimensional eigenvalues. Proposition 3 allows one to halve the size of the matrix giving the \((p^2- p)\)-dimensional eigenvalues. It is useful in computer programs. Proposition 4 relates spectra of \(X_{\mathbb{Z}/ p^2 \mathbb{Z}} (\delta, a)\) and \(X_{\mathbb{Z}/ p^2 \mathbb{Z}} (\delta, 4\delta- a)\). Figures 1 and 2 of Section 3 are histograms for the eigenvalues of various graphs over \(\mathbb{Z}/ p\mathbb{Z}\) and \(\mathbb{Z}/ p^2 \mathbb{Z}\). The difference between rings and fields is very striking. Theorem 6 shows that for primes \(p\geq 5\) the graphs \(X_{\mathbb{Z}/ p^2 \mathbb{Z}} (\delta, a)\) are not Ramanujan. Once more the difference between rings and fields could not be more blatant!''.