Unimodular graphs and Eisenstein sums

Abstract

Motivated in part by combinatorial applications to certain sum-product phenomena, we introduce unimodular graphs over finite fields and, more generally, over finite valuation rings. We compute the spectrum of the unimodular graphs, by using Eisenstein sums associated to unramified extensions of such rings. We derive an estimate for the number of solutions to the restricted dot product equation $a\cdot b=r$ over a finite valuation ring. Furthermore, our spectral analysis leads to the exact value of the isoperimetric constant for half of the unimodular graphs. We also compute the spectrum of Platonic graphs over finite valuation rings, and products of such rings - e.g., $\mathbb{Z}/(N)$. In particular, we deduce an improved lower bound for the isoperimetric constant of the Platonic graph over $\mathbb{Z}/(N)$.

arXiv commentV2: minor revisions. To appear in the Journal of Algebraic Combinatorics