The Cayley Graphs Associated With Some Quasi-Perfect Lee Codes Are Ramanujan Graphs
Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan · IEEE Transactions on Information Theory · 2016
Let Zn[i] be the ring of Gaussian integers modulo a positive integer n. Very recently, Camarero and Martinez et al. showed that for every prime number p > 5 such that p ≡ ±5 (mod 12), the Cayley graph ςp= Cay(Zp[i], S2), where S2is the set of units of Zp[i], induces a two-quasi-perfect Lee code over Zpm, where m = 2[p/4]. They also conjectured that ςpis a Ramanujan graph for every prime p, such that p ≡ 3 (mod 4). In this paper, we solve this conjecture. Our main tools are Deligne's bound from 1977 for estimating a particular kind of trigonometric sum and a result of Lovász from 1975 (or of Babai from 1979) which gives the eigenvalues of Cayley graphs of finite Abelian groups. Our proof techniques may motivate more work in the interactions between spectral graph theory, character theory, and coding theory, and may provide new ideas toward the famous Golomb-Welch conjecture on the existence of perfect Lee codes.