Isomorphic gcd-graphs over polynomial rings

Technical Summary: Isomorphic GCD-Graphs over Polynomial Rings

Problem Statement
This paper investigates the structural and spectral properties of GCD-graphs defined over polynomial rings $F_q[x]$ modulo a monic polynomial $f$, denoted as $G_f(D)$. A GCD-graph is a Cayley graph on the additive group of the ring $F_q[x]/f$ where two vertices $a, b$ are adjacent if and only if $\gcd(a-b, f) \in D$, with $D$ being a subset of the divisors of $f$ (excluding $f$ itself).

The study is motivated by the analogy between number fields ($\mathbb{Z}$) and function fields ($F_q[x]$). While GCD-graphs over $\mathbb{Z}$ have been extensively studied, particularly regarding their integrality and the conditions under which they are isomorphic or isospectral, the behavior over polynomial rings presents distinct challenges and opportunities. Specifically, the authors address two central questions:

1. The So Conjecture: Does a GCD-graph $G_n(D)$ over $\mathbb{Z}$ uniquely determine the set $D$ (up to isomorphism)? The paper investigates the analog of this conjecture in the function field setting.
2. The Sander-Sander Conjecture: Is the set $D$ uniquely determined by the spectral vector (the list of eigenvalues with multiplicity) of the GCD-graph?

Methodology
The authors employ a combination of algebraic graph theory, character theory for finite rings, and computational experimentation.

• Algebraic Framework: The study utilizes the character theory of $F_q[x]/f$, which is determined by non-degenerate functionals, analogous to the role of primitive roots of unity in $\mathbb{Z}/n\mathbb{Z}$. This allows for the explicit description of graph spectra using Ramanujan sums adapted to polynomial rings.
• Matrix Analysis: To address the uniqueness of $D$ given the spectrum, the authors construct a matrix $C_f$ composed of Ramanujan sums $c(g, h)$. They prove that the determinant of this matrix is non-zero, establishing its invertibility.
• Graph Decomposition: For the case where $f$ is a prime power ($f = P^k$), the authors analyze the graph structure using the concept of homogeneous sets and the wreath product (lexicographic product). This allows for the decomposition of complex GCD-graphs into simpler components.
• Computational Verification: The authors use the Python library NetworkX to generate experimental data, verifying theoretical claims and discovering specific constructions of isomorphic graphs with different generating sets.

Key Contributions and Results

1. Spectral Determination of $D$ (The Sander-Sander Analog):
   The paper proves that for a fixed $f \in F_q[x]$, the set $D$ is uniquely determined by the spectral vector of $G_f(D)$. This is achieved by showing that the matrix of Ramanujan sums $C_f$ is invertible (Proposition 2.4). Consequently, the weak conjecture of Sander-Sander holds true in the function field setting: if two GCD-graphs over $F_q[x]$ have the same eigenvalues (counted with multiplicity), they are defined by the same set $D$.

2. Graph-Theoretic Properties for Prime Powers:
   When $f = P^k$ is a prime power, the authors establish several structural properties:

   • Connectivity: $G_{P^k}(D)$ is connected if and only if $1 \in D$.
   • Bipartiteness: The graph is bipartite if and only if $F_q = F_2$, $\deg(P)=1$, and $D=\{1\}$.
   • Perfectness: $G_{P^k}(D)$ is a perfect graph.
   • Decomposition: The graph can be decomposed into a wreath product of simpler graphs based on the presence of specific divisors in $D$.
   • Spectral Bounds: The authors derive explicit formulas for eigenvalues and prove that the largest eigenvalue corresponds to the degree of the graph. They also show that for prime power moduli, the spectrum uniquely determines the graph structure (Theorem 4.16).

3. Isomorphism of GCD-Graphs (Refuting the So Conjecture Analog in Function Fields):
   Contrary to the case over $\mathbb{Z}$, where the conjecture that isomorphic GCD-graphs must have identical generating sets remains open, the paper demonstrates that over $F_q[x]$, non-trivial isomorphisms exist between graphs with different $D$ and potentially different moduli.

   • Unitary Cayley Graphs: The authors classify isomorphism classes of unitary Cayley graphs ($G_f(\{1\})$) based on the "factorization type" of $f$ (the count of irreducible factors of each degree). They show that graphs defined by polynomials with different radicals can be isomorphic if their factorization types match (Proposition 5.4).
   • General GCD-Graphs: The paper provides explicit constructions of isomorphic GCD-graphs $G_f(D_1) \cong G_f(D_2)$ where $D_1 \neq D_2$. These constructions rely on the existence of distinct irreducible factors of the same degree within $f$. For instance, if $f = f_1 f_2$ with $\deg(f_1) = \deg(f_2)$, specific choices of $D_1$ and $D_2$ yield isomorphic graphs (Proposition 5.9, Proposition 5.12).
   • Significance of the Difference: The authors attribute this stark difference between $\mathbb{Z}$ and $F_q[x]$ to the fact that in function fields, distinct polynomials $f$ and $g$ can yield isomorphic quotient rings ($F_q[x]/f \cong F_q[x]/g$), a phenomenon impossible in the integer case.

Significance and Claims
The paper claims to extend the line of research connecting GCD-graphs to number theory and ring theory by establishing a robust analogy between the integer and polynomial cases while highlighting critical divergences.

• Confirmation: It confirms that the spectral vector determines the generating set $D$ in the function field setting, validating the Sander-Sander conjecture analog.
• Refutation: It refutes the analog of So's conjecture specifically for the function field setting ($F_q[x]$), demonstrating that isomorphic GCD-graphs with distinct generating sets are "not uncommon" in this context. The paper notes that the conjecture remains open for the integer case ($\mathbb{Z}$) and leaves open the question of whether the conjecture might still hold for the restricted family of GCD-graphs over $F_q[x]$ where the irreducible factors of the modulus have distinct degrees.
• Novelty: The paper provides the first systematic study of graph-theoretic properties (such as perfectness, clique numbers, and independence numbers) for GCD-graphs over polynomial rings, noting that many of these results were previously unaddressed even for the integer case.

The authors maintain a modest tone regarding the scope of their findings, noting that their constructions of isomorphic graphs rely specifically on the existence of irreducible factors of the same degree. They leave open the question of whether So's conjecture might still hold for the restricted family of GCD-graphs where the irreducible factors of the modulus have distinct degrees.