CS Paper Radar

Self-Orthogonal MDS Principal-Ideal Codes

Yangcheng Li, Pingzhi Yuan

cs.IT ·submitted 2026-11-19 11:24 UTC · v1
theory

Abstract

We investigate Euclidean self-orthogonality and the generalized Reed--Solomon (GRS) property for coefficient-vector codes generated by a monic polynomial $g$ and its shifts $xg,\ldots,x^{k-1}g$, of length $n=r+k$ and dimension $k$, where $°g=r$ and $3\le k\le r$. We give a complete classification, over any algebraically closed field, of the generators for which these codes are both self-orthogonal and GRS. Such generators have either distinct roots in a geometric progression satisfying explicit order and scalar conditions, or a single repeated root in certain positive characteristics. In particular, only finitely many generators occur for fixed $r$, $k$, and characteristic. We determine their maximal self-orthogonal lengths, show that the corresponding maximal-length codes are cyclic or negacyclic, and obtain exact generator counts over finite fields, together with the least fields of definition. In contrast, when $3\le k<r$, we prove that every algebraically closed field supports infinitely many pairwise monomially inequivalent self-orthogonal non-GRS maximum distance separable (MDS) codes in this family. Consequently, arbitrarily many such codes can be realized over a common finite extension of any prescribed finite field, while remaining inequivalent and non-GRS over its algebraic closure.

Comment
15 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Euclidean and Hermitian Self-Orthogonal Codes from Divisible Codes

cs.IT ·2026-11-10 ·Ziling Heng, Chenkun Xie
theory similarity 0.71
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

Sunflowers of Reed--Solomon Codes

cs.IT math.CO ·2026-09-27 ·Roni Con, Anina Gruica, Maria Montanucci, Ferdinando Zullo
similarity 0.69
Abstract

We introduce and study Reed--Solomon sunflowers, namely families of Reed--Solomon codes whose pairwise intersections are all equal to the same fixed subspace. This notion lies at the intersection of extremal subspace combinatorics and coding theory: it can be viewed as a structured version of the sunflower problem in the Grassmannian, and it naturally produces constant-dimension subspace codes with prescribed minimum distance. We focus mainly on the case in which the center is the one-dimensional space generated by the all-one vector. We give an algebraic criterion, expressed in terms of generalized $V$-matrices, ensuring that a family of Reed--Solomon codes forms such a sunflower. We then study the size of these families through counting and constructions. In dimension two, we show that all distinct Reed--Solomon codes form a sunflower and determine its size by counting Reed--Solomon codes up to affine equivalence of their evaluation vectors. For fixed dimension $k\geq3$ and length $\ell\geq2k-1$, we give an explicit recursive construction with $Ω_{k,\ell}(q^{\lfloor\ell/(2k-1)\rfloor})$ petals and a greedy existence argument with $Ω_{k,\ell}(q^{\ell-2k+2})$ petals as $q\to\infty$. We also apply the greedy argument to obtain families of $[\ell,k]_q$ MDS codes of size $Ω_{k,\ell}(q^{2(\ell-2k+2)})$, whose pairwise intersections have dimension at most one but need not be equal.

0.17

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.67
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

Algorithms for Sampling Self-Orthogonal and Totally Self-Orthogonal Codes in Odd Characteristic

cs.IT ·2026-10-06 ·Martin R. Albrecht, Benjamin Benčina, Russell W. F. Lai
position similarity 0.66
Abstract

We give an algorithm that samples uniformly random linear codes of any hull dimension and type over finite fields of odd characteristic, implying the first algorithm for sampling uniformly random self-orthogonal codes of any rate, including self-dual codes. Our algorithm is a re-visitation of the algorithm given by Albrecht, Benčina and Lai (EC'25), using the mass formulae proven by Li, Shi and Ling (IEEE Trans. Inf. Theory 71(1)). This allows us to instantiate code-based cryptographic schemes that rely on the hardness of Permutation Code Equivalence (PCE) on `random' self-dual codes for security and that were previously unable to sample them. Building on the observation by Bardet, Otmani and Saeed-Taha (ISIT'19) that Euclidean orthogonality is insufficient when considering PCE over finite extension fields due to non-trivial Galois automorphisms, we study the behaviour of what we call total orthogonality, that is orthogonality with respect to all induced Galois geometries simultaneously. We characterise total orthogonality of vectors and codes, and give an algorithm that samples linear codes with a total hull of a prescribed dimension; a subcode that acts as the hull in all Galois geometries of the ambient space. The algorithm incurs a rate decrease by a factor equal to the extension degree, however, we argue why this may be necessary in the context of PCE and explore how it limits the practicality of our algorithm. We consider the notion of Galois type of a linear code when Galois hulls are symmetric and show that all linear codes have constant Hermitian type.

0.43

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.66
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

Length Bounds for Irreducible Cyclic MDS Codes

cs.IT ·2026-10-20 ·Guanghui Zhang
theoryhot direction similarity 0.65
Abstract · 35 pages

We prove the MDS length bound for nontrivial irreducible cyclic codes of every composite length. The classical trace realization turns the MDS property into independence of elements of a multiplicative subgroup. Every nonidentity subgroup must have the full extension degree. This restriction yields length congruences, and the Frobenius-orbit description of the coefficient field gives an exact descent obstruction. A cyclotomic argument reduces each fixed dimension to finitely many parameters. For dimensions at most thirty, established geometric bounds reduce the alphabet to a small finite range; the remaining twelve parameter triples are excluded by explicit products of at most three determinant factors and a low-degree multiplier argument. An independent argument proves the composite-length theorem in arbitrary dimension. The standardness conclusion is stated separately as a conditional consequence of the classification statement of Feng, Hollmann, Li, and Xiang; the correct extension-field reduction retains a semilinear quotient. The general prime-length problem is not settled here. Neither length proof uses the automorphism classification or the recent odd-characteristic range announced by Fan.

0.34

New Constructions of Additive MDS TRS Codes

cs.IT ·2026-08-19 ·Anuj Kumar Bhagat, Ankit Yadav, Ritumoni Sarma
similarity 0.65
Abstract

Additive codes over finite fields generalize linear codes, and additive MDS codes provide a natural extension of linear MDS codes. In this article, we study additive twisted Reed--Solomon (TRS) codes and obtain new constructions of additive MDS codes. First, for additive TRS codes with twist $t=2$ and an arbitrary hook, we establish necessary and sufficient conditions for the codes to be additive MDS, thereby generalizing the results in Section 3 of [Jiayu Ma et al., New families of additive non-Reed-Solomon MDS codes]. In particular, we show that the existence of an additive MDS TRS code with $t=2$ and hook $h=0$ yields codes of larger lengths than those obtained for $t=2$ and $h=k-1$ in [Jiayu Ma et al., New families of additive non-Reed-Solomon MDS codes]. Next, we consider additive TRS codes with twist vector $\mathbf{t}=(1,2)$ and hook vector $\mathbf{h}=(0,0)$, and derive necessary and sufficient conditions for them to be additive MDS. We further establish the existence of such codes. Using the Schur square technique, we obtain mild conditions under which the constructed families are inequivalent to additive Reed--Solomon (RS) codes. Finally, we determine parity-check matrices for both families of additive MDS codes considered in this article.

0.23

Hyper-derivative Algebraic Geometry Codes via Local Expansions

cs.IT ·2026-09-16 ·Xiaofeng Liu, Hengfeng Liu, Jun Zhang, Fang-Wei Fu, Chunming Tang
theory similarity 0.65
Abstract

In this paper, we develop a systematic construction framework of hyper-derivative algebraic geometry codes via local expansions, extending hyper-derivative Reed-Solomon codes from the rational function field to general algebraic function fields. Using the residue theorem, we determine their Euclidean duals and illustrate that the duals naturally reverse. We further give criteria for reverse self orthogonality and reverse self duality in terms of two classes of bilinear forms. Finally, we provide an asymptotic bound on the rate and relative distance via function field towers.

0.28