CS Paper Radar

Annihilator and twisted Euclidean duality for quasi-polycyclic codes

Tushar Bag, Edgar Martínez-Moro, Daniel Panario

cs.IT cs.DM ·submitted 2026-09-22 16:06 UTC · v1
theory

Abstract

Let $f\in\mathbb F_q[x]$ be a monic polynomial of degree $m$ with $f(0)\ne 0$, and let $\mathcal R=\mathbb F_q[x]/\langle f\rangle$. Under coefficient expansion, a quasi-polycyclic (QP) code of index $n$ corresponds to an $\mathcal R$-submodule of $\mathcal R^n$. In this paper, we study QP codes with respect to the annihilator duality. We show that this form is non-degenerate and that the annihilator dual of a QP code is again a QP code. We also give an equivalent description of the dual in terms of the $\mathcal R$-valued dot product, which leads to self-orthogonality criteria. We determine the Gram matrix of the annihilator form and obtain an explicit formula for its determinant. In coefficient coordinates, this shows that the annihilator dual can be viewed as a twisted Euclidean dual. Using this description, we characterize when a coordinatewise $\mathbb F_q$-linear map converts annihilator duality into ordinary Euclidean duality. For squarefree $f$, we show that annihilator duality decomposes into ordinary Euclidean duality on the components arising from the Chinese Remainder Theorem. This gives simple criteria for self-orthogonal, self-dual, dual-containing, and complementary-dual QP codes. We show how the annihilator dual interacts with the Hamming weight enumerator and compute the MacWilliams transform associated with that duality. Finally, we apply these results to Calderbank--Shor--Steane and Steane-enlarged quantum-code constructions over $\mathcal R$ and, when a suitable duality-preserving coordinate map exists, over $\mathbb F_q$. This gives binary and ternary stabilizer codes with minimum-distance lower bounds matching the best known bounds, most of which arise from rings $\mathcal R$ that are not fields.

Closest papers

Nearest neighbours by meaning across the whole index.

Linear Equivalence of Full Weight Spectrum Cyclic Orbit Codes

cs.IT cs.GT ·2026-11-03 ·Minjia Shi, Ferruh Ozbudak
theory similarity 0.70
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

Cyclically covering subspaces and additive perfect codes

cs.IT math.COmath.NT ·2026-11-09 ·Yangcheng Li, Pingzhi Yuan
theory similarity 0.67
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

Hull variation of algebraic geometry codes under divisor twists

cs.IT ·2026-11-18 ·Erik Mendoza, Sihem Mesnager, Luciane Quoos
theory similarity 0.65
Abstract

The hull $\mathrm{Hull}(\mathcal{C})=\mathcal{C}\cap\mathcal{C}^{\perp}$ of a linear code $\mathcal{C}\subseteq\mathbb{F}_q^n$ interpolates between linear complementary dual (LCD) codes, with trivial hull, and self-dual codes. Its dimension is preserved by coordinate permutations but not by scalings $\mathcal{C}\mapsto\mathbf{x}\cdot\mathcal{C}$, $\mathbf{x}\in(\mathbb{F}_q^*)^n$. This governs the complexity of Sendrier's support-splitting algorithm and decides whether an equivalence class contains LCD codes. We study this hull-variation problem, formalised by Chen, for algebraic geometry codes $\mathcal{C}(D,G)$ over a function field $\mathcal{F}/\mathbb{F}_q$ of genus $g>0$, where scalings are twists of $G$ by principal divisors; as a natural relaxation, we allow twists $G\mapsto G+L$ by arbitrary divisors. Writing $\mathcal{C}(D,G)^{\perp}=\mathcal{C}(D,H)$, with $H=D-G+W$, $W$ canonical, a twist acts by $(G,H)\mapsto(G+L,H-L)$. Whenever $\gcd(G+L,H-L)$ is non-special, the hull dimensions of $\mathcal{C}(D,G+L)$ and $\mathcal{C}(D,G)$ differ by exactly $\frac12(\mathrm{deg}|G-H|-\mathrm{deg}|G-H+2L|)$. For a genuine scaling, $L=-(z)$, this variation is bounded by $2[\mathcal{F}:\mathbb{F}_q(z)]$. Under the same hypothesis, we obtain an upper bound on the hull dimension depending only on $D$ and $W$, and characterise exactly when it is attained by a scaling of it. These bounds shed new light on Chen's maximal hull dimension; explicit scalings on Kummer extensions show that the first is sharp. We construct explicit twists that raise, respectively lower, the hull dimension by prescribed amounts, one unit at a time, and apply them to two classical families. Starting from known LCD codes, we reach every hull dimension in an explicit range; starting from a self-dual code ($q$ even) or a code of maximal hull dimension ($q$ odd), we descend to $0$, yielding LCD codes of various dimensions.

0.16

On the structure of polynomial ideal codes and additive Reed--Solomon codes

cs.IT ·2026-10-15 ·Umberto Martínez-Peñas, Rubén Rodríguez-Ballesteros
similarity 0.64
Abstract

We study structural properties of polynomial ideal (PI) codes and additive Reed--Solomon (aRS) codes in the folded Hamming metric (equivalently, the Hamming metric over a larger alphabet). We first determine the maximum possible length of PI codes, prove that the dual of every PI code is a generalized PI code, and deduce that PI codes are dually QMDS together with an explicit formula for their weight distribution. We then show that PI codes defined by irreducible polynomials correspond to aRS codes with pairwise nonconjugate evaluation points. For these aRS codes, the previous results on PI codes apply (duality, QMDS property and weight distribution). We show that, asymptotically, aRS codes with nonconjugate evaluation points achieve the same length as PI codes. We also compute the permutation group of such aRS codes. We also extend the family of PI codes to consider arbitrary polynomial modules (not necessarily pairwise coprime), and study when these and general aRS codes satisfy the QMDS and dually QMDS properties.

0.15

Hermitian Duality and Syndrome Structure of CSS-Type Codes over the ring $\mathbb{Z}_q[i]$

cs.IT ·2026-09-13 ·Akanksha Tiwari, Ritumoni Sarma
similarity 0.62
Abstract

We study the algebraic structure of principal ideal codes and CSS-type stabilizer constructions over the ring $ R_q=\mathbb Z_q[i],$ where every prime divisor of $q$ is congruent to $1$ modulo $4$. Although such ring-based constructions have recently been considered in the context of classical and quantum error correction, the precise relationship among principal ideal cardinalities, Hermitian duality, algebraic cosets, and stabilizer syndromes requires further structural analysis. We obtain cardinality formulas for principal ideals and their annihilators. For a length-one principal ideal code $C=\langleα\rangle$, we show that its Hermitian dual is $ C^{\perp_H}=\operatorname{Ann}(σ(α)). $ For nested codes satisfying $ C_2^{\perp_H}\subseteq C_1\subseteq C_2, $ we determine the corresponding CSS-type stabilizer and prove that the kernel of the physical $X$-error syndrome map is $ \ker(\operatorname{Syn}_X)=C_2. $ Consequently, $C_2/C_1$ parametrizes logical $X$-operator classes and $R_q^n/C_2$ parametrizes physical $X$-error syndrome classes. Using this syndrome quotient, we construct a transversal of $C_2$ in $R_q^n$ whose elements have pairwise distinct physical $X$-error syndromes. The corresponding $X$-type error family is correctable by stabilizer syndrome measurement, yielding a syndrome-based recovery procedure that is consistent with the stabilizer structure. Explicit examples illustrate the resulting duality, cardinality, and syndrome structure.

0.26

On cyclic codes generated by cyclotomic polynomials

cs.IT ·2026-11-18 ·Alonso S. Castellanos, Gyan Morales Solis, Guilherme Tizziotti
similarity 0.62
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.25

Revisiting the Weight Spectrum of the Affine Grassmann Code $C^{\mathbb{A}}(2,m)$

cs.IT ·2026-09-09 ·Rohit Yadav
similarity 0.61
Abstract · 9 Pages

Affine Grassmann codes, introduced by Beelen, Ghorpade and Høholdt, are linear codes over $\mathbb{F}_q$ obtained by evaluating linear combinations of minors of a generic matrix. The weight spectrum of the affine Grassmann code $C^{\mathbb{A}}(2,m)$ was determined by Piñero and Singh via a case analysis on the rank of an associated alternating matrix. We give an independent and more streamlined derivation, valid for all $m\ge4$ and every prime power $q$, in which each codeword is written in a compact matrix form and its Hamming weight is expressed through a single closed formula involving two explicit affine subspaces and their intersection.

0.23

Euclidean and Hermitian Self-Orthogonal Codes from Divisible Codes

cs.IT ·2026-11-10 ·Ziling Heng, Chenkun Xie
theory similarity 0.61
Abstract · 26 pages

Self-orthogonality and divisibility are two fundamental properties of linear codes, and the relationship between them has long been of interest. Huffman and Pless (2003) showed that every binary \(4\)-divisible code is Euclidean self-orthogonal, that a ternary code is Euclidean self-orthogonal if and only if it is \(3\)-divisible, and that a quaternary code is Hermitian self-orthogonal if and only if it is \(2\)-divisible. The general case remained open for a long time. In 2024, Li and Heng settled the odd-characteristic case, proving that every \(p\)-divisible code over \(\F_{p^m}\), with \(p\) odd, that contains the all-one vector is Euclidean self-orthogonal. In this paper we treat the even-characteristic case: we prove that every \(4\)-divisible code over \(\F_{2^m}\) containing the all-one vector is Euclidean self-orthogonal. We also prove that, for every prime \(p\), every \(p\)-divisible linear code over \(\F_{q^2}\), where \(q=p^m\), that contains the all-one vector is Hermitian self-orthogonal. In addition, we generalize the Hermitian criterion to the Galois self-orthogonal case, proving that any $p$-divisible linear code over $\gf_{q^r}$ that contains the all-one vector is $\ell$-Galois self-orthogonal for \(\ell\in\{1,\dots,r-1\}\). These criteria make the construction of self-orthogonal codes from divisible codes simple and efficient. As applications, we recover the known Euclidean and Hermitian self-orthogonality of generalized Reed--Muller codes and obtain several infinite families of new Euclidean and Hermitian self-orthogonal codes, which give rise to infinite families of quantum codes with excellent parameters.

0.11