Finite analogues of Euclidean space

DOI10.1016/0377-0427(95)00261-8MaRDI QIDQ1919452zbMATH OpenOpenAlexFDO

Publication date 11 November 1997

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-0427(95)00261-8

adjacency operators finite Euclidean graphs Gauß sums generalized Kloosterman sums Ramanujan graphs

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Extremal problems in graph theory (05C35) Gauss and Kloosterman sums; generalizations (11L05) Other character sums and Gauss sums (11T24) Other matrix groups over finite fields (20H30)

Review text

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.

Recommendations

Cites work

Cited in

(31)

This page was built for publication: Finite analogues of Euclidean space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1919452)