The Cayley graphs associated with some quasi-perfect Lee codes are Ramanujan graphs

Khodakhast Bibak, Bruce M. Kapron, Srinivasan VenkateshIEEE Trans. Information Theory 2016 · DOI · OpenReview

TL;DR

This paper proves that certain Cayley graphs, constructed using the units of Gaussian integers modulo a prime $p \equiv 3 \pmod{4}$, are Ramanujan graphs. This resolves a conjecture linking these graphs to quasi-perfect Lee codes and offers new insights into the interplay between number theory, spectral graph theory, and coding theory.

What Problem Does This Paper Address?

The paper tackles a conjecture posed by Camarero and Martínez concerning the spectral properties of specific Cayley graphs. These graphs, denoted $G_p = \text{Cay}(\mathbb{Z}_p[i], S_2)$, are built upon the ring of Gaussian integers modulo a prime $p$ where $p \equiv 3 \pmod{4}$, and $S_2$ represents the set of units in this ring. Camarero and Martínez had previously shown that these graphs are related to 2-quasi-perfect Lee codes and conjectured that $G_p$ would be a Ramanujan graph for primes $p \equiv 3 \pmod{4}$. The authors aim to prove this conjecture, bridging a gap between coding theory and spectral graph theory. The broader context involves the famous Golomb-Welch conjecture about the non-existence of perfect Lee codes, suggesting that understanding these related structures could offer new avenues for research.

Methods

The authors leverage a combination of established results from spectral graph theory and number theory. A key tool is Deligne's bound (1977), which provides a powerful estimate for certain trigonometric sums. This is combined with a result by Lovász (1975) or Babai (1979) that characterizes the eigenvalues of Cayley graphs of finite Abelian groups in terms of group characters.

Specifically, the proof proceeds as follows:

  1. Identifying the Group and Generating Set: The ring $\mathbb{Z}_p[i]$ for $p \equiv 3 \pmod{4}$ is identified as the finite field $\mathbb{F}_{p^2}$. The additive group of this field is $\mathbb{Z}_p[i]$, and the set of units $S_2$ serves as the generating set for the Cayley graph $G_p$.
  2. Determining Graph Properties: The paper establishes that $G_p$ is $(p+1)$-regular. This is crucial because Ramanujan graphs are defined by a bound on their non-trivial eigenvalues relative to their degree.
  3. Eigenvalue Analysis: Using the Lovász/Babai theorem, the eigenvalues of $G_p$ are related to characters of the additive group $\mathbb{Z}_p[i]$. The trivial character yields the largest eigenvalue $p+1$. For non-trivial characters, Deligne's bound is applied to estimate the magnitude of the corresponding eigenvalues.
  4. Applying the Ramanujan Bound: The estimated magnitudes of the non-trivial eigenvalues are shown to be less than or equal to $2\sqrt{p+1}$, which is the defining condition for a Ramanujan graph.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and proofs rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Bridging Number Theory and Spectral Graph Theory: The paper beautifully demonstrates how deep results from number theory (specifically, properties of Gaussian integers and finite fields) can be used to prove sophisticated statements in spectral graph theory.
  • The Power of Character Theory: The use of group characters to understand the eigenvalues of Cayley graphs is a powerful technique, and this paper showcases its effectiveness in a concrete, non-trivial example.
  • Ramanujan Graphs as "Optimal" Expanders: The paper reinforces the idea that Ramanujan graphs are spectrally "optimal" expanders, meaning they have excellent connectivity properties for their degree. This has implications for network design, error-correcting codes, and other applications where efficient communication or information transmission is key.
  • Connection to Coding Theory: The resolution of the conjecture directly links the spectral properties of these graphs to the existence of quasi-perfect Lee codes, suggesting a deeper structural relationship between these seemingly disparate areas.

Key Results

The main result is the proof that for any prime $p \equiv 3 \pmod{4}$, the Cayley graph $G_p = \text{Cay}(\mathbb{Z}_p[i], S_2)$ is a Ramanujan graph.

  • $G_p$ is a $(p+1)$-regular graph.
  • The largest eigenvalue of $G_p$ is $p+1$.
  • All other eigenvalues $\lambda$ of $G_p$ satisfy $|\lambda| \leq 2\sqrt{p+1}$.
  • The paper also shows that $G_p$ is not bipartite, implying the existence of odd cycles within the graph.

Limitations and Future Work

  • Specific Prime Condition: The proof specifically addresses primes $p \equiv 3 \pmod{4}$. The paper mentions that Camarero and Martínez's work on quasi-perfect Lee codes applied to primes $p \equiv \pm 5 \pmod{12}$, and the conjecture itself was for primes $p \equiv 3 \pmod{4}$. It would be interesting to explore if similar results hold for other classes of primes.
  • Generalization to Other Rings: The current work focuses on Gaussian integers. Investigating Cayley graphs over other rings and their spectral properties could be a fruitful direction.
  • Golomb-Welch Conjecture: The authors explicitly state that their techniques might provide new ideas towards the famous Golomb-Welch conjecture on the existence of perfect Lee codes. This remains an open and significant problem in coding theory.
  • Explicit Constructions: While this paper proves the existence of Ramanujan graphs with specific properties, the ongoing quest for explicit and efficient constructions of Ramanujan graphs for various parameters continues to be an active area of research.

Summary updated

Abstract

Let $\Z_n[i]$ be the ring of Gaussian integers modulo a positive integer $n$. Very recently, Camarero and Mart\'{i}nez [IEEE Trans. Inform. Theory, {\bf 62} (2016), 1183--1192], showed that for every prime number $p>5$ such that $p\equiv \pm 5 \pmod{12}$, the Cayley graph $\mathcal{G}_p=\textnormal{Cay}(\Z_p[i], S_2)$, where $S_2$ is the set of units of $\Z_p[i]$, induces a 2-quasi-perfect Lee code over $\Z_p^m$, where $m=2\lfloor \frac{p}{4}\rfloor$. They also conjectured that $\mathcal{G}_p$ is a Ramanujan graph for every prime $p$ such that $p\equiv 3 \pmod{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\'{a}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 towards the famous Golomb--Welch conjecture on the existence of perfect Lee codes.
BibTeX
@article{bibak2016cayley,
  author = {Khodakhast Bibak and Bruce M. Kapron and Srinivasan Venkatesh},
  title = {{The Cayley graphs associated with some quasi-perfect Lee codes are Ramanujan graphs}},
  journal = {IEEE Trans. Information Theory},
  year = {2016},
  doi = {10.1109/tit.2016.2595778},
}
Figure