CS Paper Radar

The spectral relation between irreducible cyclic codes and generalized Paley graphs

Ricardo A. Podestá, Denis E. Videla

cs.IT math.CO ·submitted 2026-09-23 03:15 UTC · v1

Abstract

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}(γω^{ik})_{i=0}^{n-1})\}_{γ\in \mathbb{F}_r}$, with $ω$ a primitive element of $\mathbb{F}_q$ and $ n= \tfrac{q-1}{k}$, and generalized Paley (GP) graphs $Γ(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 $Γ(k_r,q)$, where $k_r=\gcd(k, \frac{q-1}{r-1})$. Then, we give $Spec(Γ(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.

Comment
23 pages, 4 tables

Closest papers

Nearest neighbours by meaning across the whole index.

The weight enumerators of irreducible cyclic codes of length $2^\ell$

cs.IT math.CO ·2026-10-08 ·Ricardo A. Podestá, Denis E. Videla
similarity 0.74
Abstract · 19 pages, 3 tables

Using the spectral relation between irreducible cyclic codes (ICC) and generalized Paley (GP) graphs recently found by the authors, we study the weight distribution of irreducible cyclic codes of length $2^\ell$, $\ell \in \mathbb{N}$. These codes were previously studied by Sharma, Bakshi and Raka, who divided them into two families (each having two cases). First we characterize the GP-graphs spectrally related to these families of ICCs: they are complete, semiprimitive, Hamming, or Cartesian products of semiprimitive GP-graphs. We then compute the spectrum of these graphs and hence, by the mentioned spectral relation we finally obtain neat explicit expressions for the weight enumerators of all the irreducible cyclic codes of length $2^\ell$ with $\ell \in \mathbb{N}$.

0.11

Equal Hamming Weights at Fixed Root Order and Applications to Constacyclic MDS Codes

cs.IT ·2026-10-31 ·Li Zhu, Hongfeng Wu
theory similarity 0.66
Abstract

For a fixed positive integer $n>1$, we study the prime powers $q$ coprime to $n$ for which all monic irreducible factors of $Φ_n$ over $\F_q$ have the same coefficient Hamming weight. Cyclotomic orbit coefficients give a finite, effective classification of these fields. Outside finitely many computable characteristics, every factor has the support of its characteristic-zero orbit polynomial; the uniform condition $p>2^{\varphi(n)}$ suffices. In each remaining characteristic, extension exponents reduce to divisors of $\ord_n(p)$, and an integer variance identity expressed by polynomial gcd degrees decides equal weight. The same coefficient data determine the full weight distribution. As an application, we prove that an MDS constacyclic code with an irreducible generator forces every irreducible polynomial of the same root order to have full support, including factors associated with different constacyclic constants. This yields a uniform gcd and norm obstruction. We develop its short-multiplier extension, give a prime-order cubic family, and establish an explicit quadratic-residue exclusion without a prime-square alphabet or a near-square length hypothesis.

0.20

Cyclically covering subspaces and additive perfect codes

cs.IT math.COmath.NT ·2026-11-09 ·Yangcheng Li, Pingzhi Yuan
theory similarity 0.66
Abstract · 20 pages

Let $h_q(n)$ be the largest codimension of a subspace of $\mathbb{F}_q^n$ whose cyclic shifts cover the whole space. For $r>0$, we characterize the inequality $h_q(n)\ge r$ in terms of cyclic $\mathbb{F}_q$-linear codes over vector alphabets with covering radius one, no nonzero word of block weight one, and a scalar dual generated by the shifts of one word. For $k,m\ge2$, let $I_q(j)$ count the monic irreducible polynomials of degree $j$ over $\mathbb{F}_q$. If $k$ is prime or $m\ge2\sum_{j=1}^{k-1}I_q(j)+2$, we prove that a cyclic $\mathbb{F}_q$ linear perfect code of length $\frac{q^{km}-1}{q^k-1}$ over $\mathbb{F}_q^k$ exists if and only if $\gcd(m,q-1)=1$. When this condition holds, we also obtain \(h_q\!\left(\frac{q^{km}-1}{q^k-1}\right)=k(m-1).\) Restriction of scalars gives the same criterion for every $m\ge2$ when $q$ is odd, $q+1$ is a power of two, and $k=2p$ with $p$ prime. We also show that $h_q(q^k+1)=k$ exactly when $q$ is even, for every $k\ge1$.

0.12

Linear Equivalence of Full Weight Spectrum Cyclic Orbit Codes

cs.IT cs.GT ·2026-11-03 ·Minjia Shi, Ferruh Ozbudak
theory similarity 0.66
Abstract · 12 pages

We determine the linear-equivalence classes within the two families of full weight spectrum one-orbit cyclic subspace codes. This solves the second open problem posed by Castello, Polverino and Zullo [J. Combin. Theory Ser. A 212 (2025) 106005]. For the first family, the criterion is a fractional linear transformation over $\F_q$ followed by a power of $q$-Frobenius. For the second family, it is an affine transformation over $\F_{q^2}$ together with a power of $q$-Frobenius. We use polynomial spaces over finite fields, the linear-isometry theorem for cyclic orbit codes, and trace duality. The arguments include parameters belonging to proper subfields of the ambient field.

0.13

On cyclic codes generated by cyclotomic polynomials

cs.IT ·2026-11-18 ·Alonso S. Castellanos, Gyan Morales Solis, Guilherme Tizziotti
similarity 0.65
Abstract

Let $n$ be a composite positive integer coprime to $\operatorname{char}(\mathbb{F}_q)$ and let $t = \operatorname{lpf}(n)$ be the least prime factor of $n$. In this paper we study the cyclic codes $\mathcal{C}_{n,t} = \langle Q_n(X)Q_t(X)\rangle$ and $\mathcal{C}_{n,t,1} = \langle Q_n(X)Q_t(X)Q_1(X)\rangle$ over $\mathbb{F}_q$, where $Q_d(X)$ denotes the $d$-th cyclotomic polynomial. These codes extend the families $\mathcal{C}_n = \langle Q_n(X)\rangle$ and $\mathcal{C}_{n,1} = \langle Q_n(X)Q_1(X)\rangle$ recently studied by Bhagat and Sarma. We determine the exact minimum distances of $\mathcal{C}_{n,t}$ and $\mathcal{C}_{n,t,1}$, showing that $d(\mathcal{C}_{n,t,1}) = 2t$ and that $d(\mathcal{C}_{n,t})$ equals $t$ if $t^2 \nmid n$, and $2t$ if $t^2 \mid n$. For the dual codes, we establish $d(\mathcal{C}_{n,t}^\perp) = 2^{ω(n)}$, handling the case $ω(n) \le 2$ via the Hartmann--Tzeng bound, and the case $ω(n) \ge 3$ via a direct-sum decomposition $\mathcal{C}_{n,t}^\perp = \mathcal{C}_n^\perp \oplus \mathcal{V}_t$ and the tensor-product structure of $\mathcal{C}_n^\perp$ over its prime-power components. As applications, we show that all four code families are linear complementary dual (LCD) and locally recoverable (LRC), and we determine their locality parameters, identifying several infinite families that are $r$-optimal or $d$-optimal with respect to the Singleton-type bound for LRC codes.

0.11

Norm-One Torus Decompositions and Decoding of Gashkov-Sidel'nikov Codes

cs.IT math.CO ·2026-09-17 ·Minjia Shi, Shitao Li, Yuhong Xia, Tor Helleseth, Ferruh Ozbudak
similarity 0.64
Abstract

Let $q=3^m$, let $K=\mathbb F_{q^2}$, and let \[\mathcal T=\{x\in K^*:\operatorname{N}_{K/\mathbb F_q}(x)=1\}.\] For both cyclic and constacyclic Gashkov-Sidel'nikov codes, we show that the set of signed parity-check column labels is precisely $\mathcal T$. Consequently, the decoding problem separates into two stages: determining the minimum error weight associated with a syndrome $S$ and constructing an error vector attaining this minimum. We identify the former quantity with the minimum additive length of $S$ with respect to $\mathcal T$ and determine it exactly by the norm and the quadratic character of $\mathbb F_q$. We also determine the complete coset-weight distribution and recover the known covering radius $3$. For the constructive part, we use quadratic-character sums and Weil bounds to construct a coset leader for every syndrome of coset weight three. The resulting procedures give complete maximum-likelihood decoders.

0.23

Near-MDS codes of lengths q+6 and q+7 from conics in PG(2,q), q odd

cs.IT math.CO ·2026-08-18 ·Sinan Donmez, Atilla Akpinar, Rumi Melih Pelen
similarity 0.64
Abstract · 18 pages, 2 figures

Near maximum distance separable (NMDS) codes of dimension 3 and length n over the finite field with q elements are equivalent to (n,3)-arcs in PG(2,q). For every odd prime power q we construct, by adding five suitable points to a conic of PG(2,q), a family of [q+6,3,q+3] NMDS codes and determine their weight distributions completely; three distinct weight enumerators occur, governed by two explicit quadratic-character conditions on the parameters. For every odd prime power q, no code of our family is monomially equivalent to a code of the recent [q+6,3,q+3] NMDS family of Fan, Wang and Xu, even where the weight enumerators of the two families coincide: the separating invariant is a triple of geometric data attached to the underlying arc. Extending the configuration by a sixth point on a distinguished external line, we further obtain [q+7,3,q+4] NMDS codes, together with their weight distributions, for every odd prime power q >= 11 (admissible parameters exist for no q <= 9); the existence proof combines exact and Weil-type character sum estimates with a finite computer verification. Our proofs are purely geometric and rest on a simple counting identity for the trisecant lines of a point set obtained by extending a conic. All the codes constructed are optimal locally recoverable codes with locality 2.

0.32

Support periods of polynomials and support-primitive decomposition of constacyclic codes over Galois rings

cs.IT math.NT ·2026-10-21 ·Li Zhu, Hongfeng Wu
similarity 0.63
Abstract

Let \(A=\GR(p^e,r)\) have residue field \(\F_q\), and let \(λ\in A^\times\). We relate coefficient compression of monic divisors of \(X^N-λ\) to support-primitive decomposition of constacyclic codes. At a simple-root length, the support period of every nonconstant monic divisor is preserved at each coefficient precision and equals the order of the multiplicative stabilizer of its root set. For a cyclic Frobenius-orbit polynomial, the multiple equal-difference structure determines its support period, core degree, and least relative degree of an unramified extension over which all its basic-irreducible factors are binomials. Coordinate projections give every constacyclic code over a finite commutative ring a unique maximal interleaving into copies of one support-primitive code. At simple-root lengths over \(A\), the intrinsic period of a code is the greatest common divisor of the periods of its torsion codes. The decomposition yields distance and duality formulas and the arithmetic Singleton bound for free codes. At every length, a nonzero code over \(A\) has the same minimum Hamming distance as its highest torsion code, which gives a refined bound. At repeated-root lengths, identical torsion filtrations can occur with different intrinsic periods, while a class of nonzero codes obtained by substitution from simple-root generators retains the same core and minimum distance. Trace matrices recover the coefficients of basic-irreducible cores using unit pivots, and local Hensel corrections lift compressed factors directly. For \(X^n-1\) with \(p\nmid n\), lifting and output have quasi-linear bit cost in the compressed representation when the arithmetic data and residue factorizations are given.

0.25