CS Paper Radar

A Complete Characterization of $q$-Ary $2$-Designs in Doubly-Extended Reed-Solomon Codes

Xinghao Wu, Junling Zhou

cs.IT math.CO ·submitted 2026-11-04 02:52 UTC · v1
theory

Abstract

Let $\mathcal{C}_k$ be the doubly-extended Reed--Solomon code with parameters $[q+1, k, q-k+2]_q$. We give a complete characterization of when its codewords of a fixed weight form $q$-ary 2-designs. The main ingredient is an exact criterion showing that the number of $r$-subsets of $\mathbb{F}_q^*$ with a prescribed product is independent of that product if and only if $\gcd(r, q-1)=1$. Applying this criterion to the minimum-weight codewords of $\mathcal{C}_k$, we prove that they form a $q$-ary 2-design if and only if $\gcd(k-1, q-1)=1$. We further establish a propagation result for MDS codes showing that the $q$-ary 2-design property at minimum weight implies the same property at every nonzero weight. Consequently, $\mathcal{C}_k$ holds $q$-ary 2-designs at all nonzero weights if and only if $\gcd(k-1, q-1)=1$.

Comment
6 pages

Closest papers

Nearest neighbours by meaning across the whole index.

A Characterization of $q$-Ary $2$-Designs and a $3$-Design Obstruction for Doubly-Extended Reed-Solomon Codes

cs.IT ·2026-11-08 ·Guanghui Zhang, Zhengbang Zha
theory similarity 0.86
Abstract · 18 pages

Let $\mathcal{C}_k$ be the doubly extended Reed--Solomon code with parameters $[q+1,k,q-k+2]_q$, where $q\ge3$ is a prime power and $2\le k\le q$. We prove a conjecture of Wu and Zhou by showing that the minimum-weight codewords of $\mathcal{C}_k$ do not form a $q$-ary $3$-design when $2\le k\le q-1$. Using shortening, we extend this obstruction to every nonempty weight class with $3\le w<q+1$. We also establish that each individual nonempty positive-weight class of $\mathcal{C}_k$ forms a $q$-ary $2$-design if and only if $\gcd(k-1,q-1)=1$. Consequently, every nonempty positive-weight class below full support has exact $q$-ary design strength $2$ when this coprimality condition holds, and $1$ otherwise.The three-design obstruction follows by applying a classical subset-product character identity to a marginal covering count for three prescribed nonzero symbols. The comparison between weights rests on a covering-count formulation of the classical MDS coset-weight relations. For every linear $[n,k,d]_q$ MDS code with $2\le k\le n-1$, this formulation shows that the $q$-ary $2$-design property at any one nonempty positive weight is equivalent to the same property at every nonempty positive weight.More generally, for $2\le t\le\min\{k,d\}$, we prove that the $q$-ary $t$-design property at any $t-1$ distinct nonempty positive weights forces it at all nonempty positive weights.

0.07

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

On Almost MDS codes holding $(n-k-1)$-designs and an open problem on Witt design

cs.IT math.NT ·2026-10-21 ·Huakai Wei, Shiyuan Qiang, Shaofang Hong
similarity 0.74
Abstract · 18 pages

Let $\mathcal{C}$ be an almost maximum distance separable (AMDS) code over the finite fields with parameters $[n,k,n-k]$ whose minimum-weight codewords support an $(n-k-1)$-$(n,n-k,λ)$ design. We first determine the parameters of the dual code $\mathcal{C}^{\bot}$. We also characterize the design and its complementary design supported by the minimum weight codewords of $\mathcal{C}^{\bot}$. In particular, we present explicit formulas for the weight enumerators of all subset codes of $\mathcal{C}^{\bot}$ with length at least $k+1$. These formulas are completely determined by the cardinality of the subset, the dimension, together with the parameter $λ$, and are independent of the specific choice of subsets. As an application, we answer an open problem posed by Wang, Tang and Ding in 2023 by proving that the $3$-design supported by the minimum-weight codewords in their proposed cyclic dual code is isomorphic to the complementary design of the Witt spherical geometry design.

0.28

The Minimum Subpacketization of Reed-Solomon Codes with Linear Repair Achieving the Cut-Set Bound

cs.IT ·2026-10-27 ·Weijun Fang, Jing Qiu, Shu-Tao Xia, Fang-Wei Fu
surveytheory similarity 0.73
Abstract · 33 pages

In this paper, we study the minimum subpacketization of $(n,k)$ Reed-Solomon (RS) codes over $\mathbb{F}_{q^\ell}$ admitting cut-set-optimal exact $\mathbb{F}_q$-linear repair of every coordinate from any $d$ helpers. For $3\le k<d\le n-1$, write $s=d+1-k$ and denote this minimum by $\ell_{min}(n,k,d;q)$. Using divisibility and relative-degree constraints on cross-ratio fields of evaluation sets, we establish $\ell_{min}(n,k,d;q)\ge sG_s(d+1)$, where $G_s(m)$ is the minimum product of $m$ pairwise coprime integers, each at least $s$. Let $Δ_s(n,d)$ be the minimum of $lcm(a_1,\ldots,a_n)$ over positive integers $a_1,\ldots,a_n$ satisfying $lcm(a_j:j\in J\cup\{i\})\ge s~lcm(a_j:j\in J)$ for every $d$-subset $J\subseteq[n]$ and every $i\in[n]\setminus J$. We construct RS codes with subpacketization $sΔ_s(n,d)$ and further prove that $\ell_{min}(n,k,d;q)=sΔ_s(n,d)=sG_s(n)$ whenever $d(d+2)\geq 4(n+1)$, for every prime power $q$. In particular, this determines the minimum subpacketization in the full-helper case $d=n-1$, resolving the corresponding exact linear-repair case of Open Problem 20 posed by Ramkumar et al. in their survey on codes for distributed storage. We further give a finite formula for $G_s(n)$ and determine the exact threshold for its closed-form expression in terms of the first $n$ primes. For fixed $k$ and $d$, we prove $\log\ell_{min}(n,k,d;q)= Θ_{k,d}(\log n\log\log n)$ as $n\to\infty$, using divisor-function estimates and cover-free families. An affine-plane construction shows that $Δ_s(n,d)<G_s(n)$ for some parameters, so $sG_s(n)$ is not a universal formula. We conjecture that $\ell_{min}(n,k,d;q)=sΔ_s(n,d)$ for every prime power $q$ and all $3\le k<d\le n-1$.

0.43

Generalized Hamming Weights and Subcode Support Weight Distributions of Twisted Reed-Solomon Codes

cs.IT ·2026-10-12 ·Chao Liu, Hao Chen, Dabin Zheng, Yaqi Chen
similarity 0.73
Abstract · 38 pages

In this paper, we determine the generalized Hamming weight hierarchies of two classes of twisted Reed--Solomon (TRS) codes. For TRS codes with one twist, we first determine all possible values of the generalized Hamming weights. We then give a complete characterization of the weight hierarchy in terms of the minimum distance of the dual code. Explicit conditions are derived for the minimum distances of the code and its dual, which make the whole weight hierarchy explicitly computable. As special cases, the obtained results recover several known characterizations for TRS codes to be MDS, NMDS codes, and $s$-gap AMDS codes. For TRS codes with two twists, we similarly determine the complete generalized Hamming weight hierarchy. In this case, the higher generalized Hamming weights are determined by the first two generalized Hamming weights of the dual code, for which explicit rank conditions are also obtained. In addition, we further determine the subcode support weight distributions of this class of single-twist TRS codes. More precisely, for each $1 \le r \le k$, we derive an explicit formula for the number of $r$-dimensional subcodes with a prescribed support size, thereby giving a complete description of the support distribution of subcodes.

0.22

Sunflowers of Reed--Solomon Codes

cs.IT math.CO ·2026-09-27 ·Roni Con, Anina Gruica, Maria Montanucci, Ferdinando Zullo
similarity 0.72
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

Quantum MDS codes from complements of unions of finite-field subsets

cs.IT math-phmath.QA ·2026-09-09 ·Naihong Hu, Hong Ji
similarity 0.72
Abstract · 37 pages

Let $q$ be an odd prime power. We use complements of unions of subsets of $\mathbb F_{q^2}$ as locator sets and establish a sufficient condition under which a generalized Reed--Solomon (GRS) code is Hermitian self-orthogonal. Using cosets of multiplicative subgroups and sets with prescribed trace or norm values, we construct five families of Hermitian self-orthogonal GRS codes over $\mathbb F_{q^2}$. The Hermitian construction then yields five corresponding families of $q$-ary quantum maximum-distance-separable (MDS) codes. Under suitable parameter conditions, these quantum codes have minimum distances greater than $q/2+1$. By comparing codes of the same length, we give conditions under which our codes have strictly larger minimum distances than those obtainable from several previously known constructions based on trace maps, linear transformations, and cosets of multiplicative subgroups, either directly or via the propagation rule. We further show that such improvements occur for infinitely many values of $q$.

0.22

Optimal Ordering-Free Two-Dimensional Insdel Reed-Solomon Codes via Cross-Ratios

cs.IT ·2026-11-16 ·Runqing Qiu, Shixin Zhu, Yang Li, San Ling
similarity 0.71
Abstract · 16 pages

Insertion-deletion (insdel) codes correct synchronization errors. By the half-Singleton bound, an ${[n,2]}_q$ code has minimum insdel distance at most $2n-4$. The smallest field size of two-dimensional Reed--Solomon (RS) codes attaining this bound is $Θ(n^3)$. Unlike the minimum Hamming distance, the minimum insdel distance of an RS code depends on the ordering of its evaluation points. An evaluation set is called ordering-free if every ordering of its points gives an RS code attaining the half-Singleton bound. In this paper, we first show that for $n\ge6$ every ${[n,2]}_q$ code attaining the half-Singleton bound is an RS code, and hence $q\ge\binom{n}{3}+2$. Secondly, we show that an ordering-free evaluation set with $n\ge6$ points in $\mathbb{F}_q$ satisfies $n<q^{1/3}+2$, and that it has at most $r+1$ points if $q=r^3$ for a prime power $r\ge3$. Finally, by using cross-ratios, we construct an ordering-free evaluation set with $r+1$ points in $\mathbb{F}_{r^3}$ for every prime power $r$. Hence, the bound $r+1$ is attained for $r\ge3$. Moreover, the constructed set is even robust against permutations combined with insdel errors.

0.14