Finite analogues of Euclidean space (Q1919452)

Let \(\mathbb{F}_q\) be the finite field with \(q=p^r\) elements for \(p\) an odd prime. Define a ``distance'' on \(\mathbb{F}^n_q\) by \(d(x,y)={^t(x-y)}(x-y)\) for column vectors \(x,y\in\mathbb{F}^n_q\) and join two vertices \(x,y\in\mathbb{F}^n_q\) by an edge iff \(d(x,y)= a\), where \(a\in\mathbb{F}_q\) is fixed. This defines a graph \(E_q(n,a)\) associated with \(\mathbb{F}^n_q\). For \((q,n,a)\neq(q,2,0)\) with \(-1\) not a square in \(\mathbb{F}_q\), the graph \(E_q(n,a)\) is a connected regular graph of known degree (see Theorem 1). The eigenvalues of the adjacency operators can be expressed in terms of Gauß sums and generalized Kloosterman sums. If \(\lambda\) is an eigenvalue of the adjacency operator with \(\lambda\) different from the degree of the graph, then Weil's estimate for Kloosterman sums yields \(|\lambda|\leq 2q^{(n-1)/2}\). From this it is not hard to prove that for \(n=3\) many of the above graphs are Ramanujan and many are not Ramanujan. It is further shown that for fixed \(q\) and \(n\) the set of graphs \(E_q(n,a)\) splits into very few isomorphism classes. Hence, these finite Euclidean graphs differ from the graphs constructed for the non-Euclidean finite upper half plane. -- The paper is illustrated by some beautiful plots in Mathematica.