PaperlayerView exact revision on arXiv

Source-linked AI summary

The spectral relation between irreducible cyclic codes and generalized Paley graphs

Ricardo A. Podestá, Denis E. Videla

arXiv:2609.28546v1cs.ITmath.COmath.IT

TL;DR

Earlier code–graph relations particularly concerned 2-weight irreducible cyclic codes, while this work studies weight distributions of arbitrary irreducible cyclic codes through generalized Paley graphs. Theorem 4.3 relates the weight distribution of C(k, q/r) to the spectrum of the integral connected graph Γ(kr, q). The weight distribution of C(k, q/r) and the spectrum of Γ(k_r, q) determine each other, with matching frequencies and multiplicities.

  • Problem

    Earlier code–graph relations particularly concerned 2-weight irreducible cyclic codes, while this work studies weight distributions of arbitrary irreducible cyclic codes through generalized Paley graphs.

    Source: §1 · pp. 1–2

  • Method

    Theorem 4.3 relates the weight distribution of C(k, q/r) to the spectrum of the integral connected graph Γ(kr, q).

    Source: §1.3 · p. 4

  • Results

    The weight distribution of C(k, q/r) and the spectrum of Γ(k_r, q) determine each other, with matching frequencies and multiplicities.

    Source: §1 · p. 1

  • Takeaways & Limitations

    Known GP-graph spectra can be used to compute weight enumerators of certain irreducible cyclic codes, and conversely.

    Source: §1 · p. 1

    Not every generalized Paley graph Γ(k, q) corresponds to an irreducible cyclic code.

    Source: The spectral relation between codes… · p. 11

Abstract

from arXiv · show

Let $p$ be a prime and $\mathbb{F}_q/\mathbb{F}_r$ a finite field extension with $q=p^m$ and $r=p^s$. For any $k\mid q-1$, we consider $r$-ary irreducible cyclic codes (ICC) of the form $C(k,q/r) = \{(Tr_{q/r}(\gamma \omega^{ik})_{i=0}^{n-1})\}_{\gamma \in \mathbb{F}_r}$, with $\omega$ a primitive element of $\mathbb{F}_q$ and $ n= \tfrac{q-1}{k}$, and generalized Paley (GP) graphs $\Gamma(k,q) = Cay(\mathbb{F}_q, \{ x^k : x \in \mathbb{F}_q^* \})$. We show that there is a simple closed formula relating the weight distribution of $C(k,q/r)$ with the spectrum of $\Gamma(k_r,q)$, where $k_r=\gcd(k, \frac{q-1}{r-1})$. Then, we give $Spec(\Gamma(k,q))$ explicitly for those graphs associated with irreducible 2-weight cyclic codes in the semiprimitive and exceptional cases. Finally, we give the weight enumerators of irreducible cyclic codes associated with Hamming GP-graphs.

1. Introduction: preliminaries and results

The paper establishes a two-way relation between irreducible cyclic-code weight distributions and generalized Paley-graph spectra, then uses it to derive further results for codes and graphs.

1. Introduction: preliminaries and results

  • Earlier work described several code–graph relations, particularly for 2-weight irreducible cyclic codes and strongly regular graphs.Source: §1 · p. 1

1.1. The GP-graphs Γ(k, q).

1.3. Outline and results.

  • The paper states that its code setup can always be taken with q = rh under the specified conditions on n, q, and k.This normalization is the content of Theorem 3.1.Source: §1.3 · p. 4
  • The weight distribution of C(k, q/r) and the spectrum of Γ(k_r, q) determine each other, with matching weight frequencies and eigenvalue multiplicities.Here k_r = gcd(k, (q−1)/(r−1)); the p-ary case pairs C(k, q) with Γ(k, q).Source: §1.3 · p. 4
  • For ICCs over the same finite field and of the same dimension, the paper gives a reduction formula for weight enumerators and establishes an equivalence relation for r-ary cyclic codes.Source: §1.3 · p. 5
  • The spectral correspondence translates 1-weight codes to complete graphs and 2-weight codes to semiprimitive GP-graphs; the paper gives spectra for eleven exceptional GP-graphs.The eleven graphs are associated with the eleven exceptional irreducible cyclic codes.Source: §1.3 · p. 5
  • The paper obtains weight distributions for some new r-ary irreducible cyclic codes associated with Hamming GP-graphs.Source: §1.3 · p. 5

2. Preliminaries on GP-graphs and their spectrum

This section introduces generalized Paley graphs as Cayley graphs on finite fields and recalls how Gaussian periods describe their spectra. It also summarizes known spectral families and basic graph conditions.

Gaussian periods and spectrum

Graph definition and properties

  • A generalized Paley graph uses the finite field as its vertex group and the nonzero k-th powers as its connection set.It is undirected exactly when q is even or, for odd q, k divides (q−1)/2.Source: §2 · p. 5

Gaussian periods and spectrum

  • The graph is connected exactly when ord_n(p)=m, where n=(q−1)/k and q=p^m.The section also notes known spectra for complete, Paley, small-k, Hamming, and semiprimitive generalized Paley graphs.Source: §2 · p. 5, The spectrum of GP-graphs · p. 6

3. Equivalent trace representations of ICCs

Irreducible cyclic codes can be represented as trace codes, and representations obtained from different extensions can yield the same code. The section identifies a minimal extension for a given length and dimension.

Trace representations

  • An irreducible cyclic code over F_r can be expressed as a trace code from an extension F_q/F_r.This follows from Delsarte’s relation between subfield subcodes and traced dual codes.Source: §3 · p. 7

Minimal representation

  • For fixed length and dimension, trace constructions from different extensions give the same irreducible cyclic code.The minimal representation uses q=r^h, where h=ord_n(r).Source: §3 · p. 7
  • The irreducible cyclic code over F_9 of length 5 has dimension 2 and is given as C_9(16, 3^4).The paper identifies this as the minimal representation, although it can also be obtained by tracing down from larger extensions.Source: §3 · p. 8

4. The spectral relation between C(k, q/r) and Γ(kr, q)

The section relates irreducible cyclic-code weight distributions to generalized Paley graph spectra through Gaussian periods. Under the stated conditions, the correspondence works in both directions and includes eigenvalue multiplicities.

The spectral relation

  • Gaussian periods provide the common expression linking code weights and generalized Paley graph eigenvalues.The graph in the correspondence is connected and integral under the stated code parameter conditions.Source: §4 · p. 9, The spectral relation between codes… · pp. 9–10
  • The weight distribution of C(k,q/r) and the spectrum of Γ(k_r,q), with k_r=gcd(k,(q−1)/(r−1)), determine each other.The relation connects each codeword weight to a graph eigenvalue, and each weight frequency to that eigenvalue’s multiplicity.Source: The spectral relation between codes… · p. 10

Consequences and scope

  • A t-weight code corresponds to a graph with t+1 distinct eigenvalues.The zero weight corresponds to the principal eigenvalue, the minimum distance to the second-largest eigenvalue, and the maximum weight to the smallest eigenvalue.Source: The spectral relation between codes… · p. 11
  • Not every generalized Paley graph corresponds to an irreducible cyclic code; the corresponding graph must be connected and integral.Conversely, a connected integral generalized Paley graph has at least one corresponding irreducible cyclic code, though the code need not be unique.Source: The spectral relation between codes… · pp. 11–12

5. The spectral correspondence and weight enumerators

The correspondence is not bijective: the section characterizes the codes associated with a single integral connected graph, then examines weight-enumerator relations that can connect codes of different lengths.

5.1. The spectral correspondence.

  • For an integral connected Γ(k,q), the spectrally corresponding r-ary irreducible cyclic codes are characterized by C(kt,q) with t dividing r−1 and gcd(t,n(r−1))=1.The graph determines the spectra of all codes in this family.Source: §5.1 · p. 13
  • In the p=7, q=343 example, Γ(19,343) determines the spectra of codes of lengths 18 and 9.The two codes are C(19,343) and C(38,343), respectively.Source: §5.1 · pp. 13–14

5.2. Weight enumerators.

  • The section also relates weight enumerators of r-ary irreducible cyclic codes of different lengths but the same dimension when their associated graph parameter k_r agrees.The result is stated for codes whose dimensions agree and whose k_r parameters coincide.Source: §5.2 · p. 14
  • The code’s weight enumerator is obtained from that of the code by squaring the variable.The example illustrates a weight-enumerator relation between codes of different lengths.Source: §5.2 · p. 14
  • The paper defines weight-enumerator equivalence by equality after possibly different positive-integer substitutions for the variables.It establishes that this is an equivalence relation and that ordinary linear-code equivalence implies it, but the converse need not hold.Source: §5.2 · p. 14

6. From few weight irreducible cyclic codes to graphs

This section translates few-weight irreducible cyclic codes into graph properties, with a precise correspondence for one- and two-weight codes. It uses that relation to characterize and compute spectra for exceptional two-weight cases, and to connect some higher-weight codes to GP-graphs.

6. From few weight irreducible cyclic codes to graphs

  • The cited classification characterizes two-weight irreducible cyclic codes, with a general-case extension noted alongside its original GRH-based p-ary formulation.Schmidt and White's characterization assumes GRH and reduces computation to the p-ary case; Vega's extension covers the general case.Source: §6 · p. 15

6.1. The GP-graphs from one and two-weight ICCs.

  • A one-weight code corresponds exactly to a complete Γ(kr,q), while a two-weight code corresponds exactly to a strongly regular Γ(kr,q).The section notes that this crystalline correspondence is possible only for one- and two-weight codes.Source: §6.1 · p. 15, §6 · p. 15

6.2. Some GP-spectra from 2-weight exceptional p-ary ICCs.

  • The proposed classification of exceptional two-weight irreducible cyclic codes as a complete list remains conjectural.Schmidt and White conjectured that the exceptional pairs are all such codes, and the section reports that the conjecture remains open.Source: §6.2 · p. 16
  • For eleven exceptional pairs, Γ(k,q) is a connected strongly regular graph with explicitly specified non-principal eigenvalues and multiplicities; computations tabulate eight pairs.The computations for the remaining three pairs are omitted because they are too large.Source: §6.2 · pp. 16, 17, 19
  • Weight frequencies in the exceptional and semiprimitive cases give the multiplicities of the corresponding graph eigenvalues, completing the weight distributions of exact two-weight codes.The exceptional-code weights are taken from Schmidt and White's expressions; the section supplies their frequencies.Source: §6.2 · pp. 18–19
  • For some integral connected GP-graphs with k = 3, 4, or 5, the spectral correspondence yields irreducible cyclic codes with k weights.The stated graph setting has p ≡ 1 (mod k) and m = kt; Hamming GP-graphs also yield codes with 3, 4, or 5 weights for the listed cases.Source: §6.2 · p. 19

7. Weight enumerators of Hamming ICCs

The section defines Hamming irreducible cyclic codes through their associated Hamming GP-graphs and applies the spectral relation to derive their weight enumerators. It also gives divisibility and extremal-weight properties, including a special-case corollary.

7. Weight enumerators of Hamming ICCs

  • A Hamming irreducible cyclic code is an ICC whose corresponding GP-graph Γ(kr,q) is Hamming.The associated graph is specified as Γ(kr,q), where q = p^m = rh and h = ord_n(r).Source: Hamming GP-graphs and Hamming ICCs · p. 20
  • For Hamming irreducible cyclic codes satisfying the stated parameter conditions, the spectral relation gives a weight-enumerator formula and a reductive property.The theorem assumes nr = b(p^a−1) for positive integers a and b.Source: Hamming GP-graphs and Hamming ICCs · p. 20
Loading 2609.28546v1…