Integral Cayley graphs over a finite symmetric algebra
Tung T. Nguyen, Nguy ê ~ \tilde{\text{\^{e}}} n Duy Tân · 2024
Read Integral Cayley graphs over a finite symmetric algebra by Tung T. Nguyen, Nguy ê ~ \tilde{\text{\^{e}}} n Duy Tân (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-00307.txt.
Description
Abstract . A graph is called integral if its eigenvalues are integers. In this article, we provide the necessary and sufficient conditions for a Cayley graph over a finite symmetric algebra R R to be integral. This generalizes the work of So who studies the case where R R is the ring of integers modulo n . n.
Catalog record
| CREATOR | Tung T. Nguyen, Nguy ê ~ \tilde{\text{\^{e}}} n Duy Tân |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-00307
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Integral Cayley graphs over a finite symmetric algebra Thanks: TTN is partially supported by an AMS-Simons Travel Grant. NDT is partially supported by the Vietnam National Foundation for Science and Technology Development (NAFOSTED) under grant number 101.04-2023.21 Tung T. Nguyen, Nguy ê ~ \tilde{\text{\^{e}}} n Duy Tân Abstract . A graph is called integral if its eigenvalues are integers. In this article, we provide the necessary and sufficient conditions for a Cayley graph over a finite symmetric algebra R R to be integral. This generalizes the work of So who studies the case where R R is the ring of integers modulo n . n. We also explain some number-theoretic constructions of finite symmetric algebras arising from global fields, which we hope could pave the way for future studies on Paley graphs associated with a finite Hecke character. 1991 Mathematics Subject Classification Primary 11R58, 05E40, 05C50 1. Introduction An undirected graph G is said to be integral if all of its eigenvalues are integers. The notion of integral graphs was first introduced by Harary and Schwenk in [ 5 ] . In the same article, the authors asked whether one can classify integral graphs. Since then, there has been a vast literature on this topic. We refer interested readers to [ 1 ] for a survey about known examples of integral graphs. While the general question is quite challenging, the situation becomes more manageable when we consider graphs with additional structures, such as Cayley graphs over a finite ring. In this case, we can exploit the interplay between the additive and multiplicative structures of the ring to study the arithmetics of these Cayley graphs. As one might naturally expect, this investigation bridges various fields, including number theory, character theory, and commutative algebra. Below, we provide further details about some old and recent studies for this line of research. In [ 8 ] , Klotz and Sander study unitary Cayley graphs over \Z/n and their natural generalization: the gcd-graphs G_{n}(D) where D is a subset of proper divisors of n . Let us quickly recall the definition of G_{n}(D) . The vertices of G_{n}(D) are elements of the finite ring \Z/n and two elements a,b are adjacent if \gcd(a-b,n)\in D. Using the theory of Ramanujan sums, Klotz and Sander show that the gcd-graphs G_{n}(D) are integral. They also ask whether the converse is also true; namely, if a Cayley graph over \Z/n is integral, is it true that it is a gcd-graph? So (2016) in [ 13 ] provides an affirmative answer to this question. For the reader’s convenience, we recall So’s theorem ( [ 13 , Theorem 7.1] ) in terms of Cayley graphs over \Z/n as follows. Theorem (So’s theorem) . A undirected Cayley graph G=\Gamma(\Z/n,S(G)) is integral if and only if S(G) is a union of the G_{n}(d)^{\prime}s . Here for each d\mid n , G_{n}(d)=\{m\in\Z/n\mid\gcd(m,n)=d\}. In [ 11 ] , inspired by the analogy between number fields and function fields, we study gcd-graphs over polynomial rings. Among various things that we find, we show that the spectrum of these gcd-graphs also has an explicit formula via Ramanujan sums. An important insight of our work is the notion of a symmetric \F_{p} -algebra (see [ 11 , Definition 6.2] ). By their very definition, symmetric algebras are self-dual, and consequently, their characters are parametrized by their elements, which allows us to calculate the associated Gauss and Ramanujan sums quite explicitly. In this article, we apply this circle of ideas to study integral graphs over a finite ring. Our main goal here is to generalize So’s theorem to finite symmetric algebras (we refer the reader to the Definition 2.2 for the precise definition of a symmetric algebra.) More precisely, we prove the following. Theorem 1.1 . Let R be a finite symmetric \Z/n -algebra and S\subset R\setminus\{0\} such that S=-S . Then the undirected graph \Gamma(R,S) is integral if and only if S is stable under the action of (\Z/n)^{\times}. We remark that our main theorem works for all S but since we only work with undirected graphs, we impose the above conditions on S . When R=\Z/n , this recovers So’s theorem. We note, however, that our theorem applies to a much wider class of finite rings. More precisely, as we will show in the last section, all finite quotients of the ring of integers in a global field are symmetric. We believe that this observation could pave the way for future studies on gcd-graphs over such rings as well as Paley graphs associated with finite Hecke characters (see 3.13 ). 2. Main results Let R be a finite \Z/n -algebra. In this paper, we study Cayley graphs of the form \Gamma(R,S) where S is a symmetric subset of R\setminus\{0\} . We recall that \Gamma(R,S) is the undirected graph equipped with the following data. (1) The vertex set of \Gamma(R,S) is R. (2) Two elements a,b\in R are adjacent if there exists s\in S such that b=a+s. We are interested in the case where \Gamma(R,S) is integral; i.e, all of their eigenvalues are integers. By the circulant diagonalization theorem for finite abelian groups (see [ 7 ] ), the spectrum of \Gamma(R,S) is given by the family \left\{\sum_{s\in S}\widehat{\psi}(s)\right\}_{\widehat{\psi}}, where \widehat{\psi} runs over the dual group \widehat{R}:={\rm Hom}(R,\C^{\times}) of all characters of (R,+) . We remark that since R is an \Z/n -algebra, \widehat{\psi}(s)^{n}=1 for all \widehat{\psi}\in\widehat{R} and s\in R. As a result, once we fix a primitive n th root of unity \zeta_{n}\in\C^{\times} , an element \widehat{\psi}\in\widehat{R} can be expressed uniquely in the form \widehat{\psi}(s)=\zeta_{n}^{\psi(s)}, where \psi\colon R\to\Z/n is a group homomorphism. For the rest of our discussion, we will use this formulation to identify \widehat{\psi} and \psi . Since R is an \Z/n -algebra, (\Z/n)^{\times} acts naturally on R . The following proposition gives a sufficient condition for \Gamma(R,S) to be integral. Proposition 2.1 . Suppose that S is stable under the action of (\Z/n)^{\times}. Then \Gamma(R,S) is an integral graph. Proof. The Galois group of \Q(\zeta_{n})/\Q is naturally isomorphic to (\Z/n)^{\times}. More precisely, the map \chi:(\Z/n)^{\times}\to\Gal(\Q(\zeta_{n})/\Q), defined by sending a\mapsto\sigma_{a} , where \sigma_{a}(\zeta_{n})=\zeta_{n}^{a} , is an isomorphism. For each \psi\in\Hom(R,\Z/n) and a\in(\Z/n)^{\times} , we have \sigma_{a}\left(\sum_{s\in S}\widehat{\psi}(s)\right)=\sigma_{a}\left(\sum_{s\in S}\zeta_{n}^{{\psi}(s)}.\right)=\sum_{s\in S}\zeta_{n}^{a\psi(s)}=\sum_{s\in S}\zeta_{n}^{\psi(as)}=\sum_{s\in S}\zeta_{n}^{\psi(s)}. The last equality follows from the fact that S is stable under the action of (\Z/n)^{\times} . This shows that \sum_{s\in S}\zeta_{n}^{\psi(s)}\in\Z. We conclude that \Gamma(R,S) is integral. ∎ Our goal is to study the converse of 2.1 . In this article, we provide a partial answer to this question. More precisely, we will show that the converse of 2.1 holds for the class of symmetric \Z/n -algebras, whose definition we now recall. Definition 2.2 . A finite \Z/n -algebra R is called symmetric if there exists \psi\in\Hom(R,\Z/n) such that the kernel of \psi does not contain any non-zero ideal of R. When \psi exists, we call it a non-degenerate linear functional on R. Example 2.3 . \Z/n is a symmetric \Z/n -algebra, where the identity map from \Z/n to itself is a non-degenerate linear functional. More generally, as we will show in Section 3 , a finite quotient of the ring of integers in a global field is a symmetric algebra. Let R