CS Paper Radar

Chordal Construction of Column-Twisted Reed--Solomon Codes

Anuj Kumar Bhagat, Krishna Kaipa

cs.IT ·submitted 2026-10-22 13:34 UTC · v1
hot direction

Abstract

A $[n,k]_q$ Generalized Reed--Solomon (GRS) code can be represented, up to monomial equivalence, by a projective system consisting of $n$ points on a degree $(k-1)$ rational normal curve (RNC) $C_{k-1}$ in PG$(k-1,q)$. We use the term \textit{Column-Twisted Reed--Solomon (CTRS)} codes broadly for $[n,k]_q$ codes whose projective system contains at least $(k+2)$ points on a $C_{k-1}$ of PG$(k-1,q)$. By a chord of $C_{k-1}$, we mean a line which is either a tangent, a real secant, or an imaginary secant of $C_{k-1}$. Roth and Lempel constructed non-GRS MDS $[n,k]_q$ codes by considering projective systems consisting of $(n-1)$ points on $C_{k-1}$ together with a point on a tangent line. More recently, Liu et al. obtained non-GRS $[n, k]_q$ MDS codes by considering projective systems consisting of $(n-2)$ points on $C_{k-1}$ together with a pair of points on a real secant. In the case when $q$ is odd, the length of these codes satisfies $k+4 \leq n \leq (q+3)/2$. In this article, we construct non-GRS $[n,k]_q$ MDS codes by considering projective systems consisting of $(n-2)$ points on $C_{k-1}$ together with a pair of Galois conjugate points on an imaginary secant. For odd $q$, these codes have lengths satisfying $k+4 \le n\le (q+5)/2$, thereby improving both the attainable lengths and dimension ranges of previous TRS and CTRS constructions. In particular, our code attains the length $(q+5)/2$ for every $3\le k\le (q-3)/2$. We use a geometric argument to establish the non-GRS property of CTRS codes for the range $3\le k \le n-4$, while the traditional method of comparison with the Schur square of GRS codes proves the non-GRS property only for the narrower range $3\le k \le n/2$. We also determine the structure of the dual of any CTRS code.

Closest papers

Nearest neighbours by meaning across the whole index.

Deep holes of full-length Reed--Solomon codes

cs.IT ·2026-10-21 ·Bocong Chen, Jing Huang
similarity 0.71
Abstract · 28 pages

For every prime power $q>19683$, we settle the Cheng--Murray deep-hole problem for full-length Reed--Solomon codes in every dimension $2\le k\le q-2$, with the characteristic-two cases stated explicitly. For odd $q$, the deep holes are precisely the words of degree $k$. For even $q$ and $k\ge3$, the same conclusion holds except for an additional family when $k=q-3$. In even characteristic and dimension two, every deep hole has a unique expression $a h(X)+bX+c$, where $a\ne0$ and $h$ is a normalized $o$-polynomial. The proof combines quadratic quotient algebras, graph-theoretic weighted independent-set inequalities, and planar arc completion. We also obtain normal rational curve rigidity in the corresponding nonexceptional dimensions, the projective Reed--Solomon covering radii, and distinct-coordinate solvability and remainder criteria.

0.53

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

cs.IT math.CO ·2026-11-04 ·Xinghao Wu, Junling Zhou
theory similarity 0.67
Abstract · 6 pages

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

0.33

On Proximity Gaps for One-Point Algebraic Geometric Codes

cs.IT ·2026-10-29 ·Songsong Li, Chaoping Xing, Chen Yuan, Ruiqi Zhu
theory similarity 0.66
Abstract · 43 pages

Proximity gaps and correlated agreement underpin the soundness of interactive oracle proofs. We establish these properties for general one-point algebraic geometry (AG) codes, extending corresponding results for Reed-Solomon codes. For codes of length $n$ over $\mathbb F_q$ with designed distance $n-m$, write $ρ=m/n$ and fix $ρ\in(0,1)$. For polynomial curves of degree at most $\ell$ and any $0<\varepsilon<1$, we prove correlated agreement with multiplicative slack $\varepsilon$ and soundness $O(\ell(\ell+1)/(\varepsilon q))$ whenever $e\le(1-\varepsilon)(n-m)/2$, with no additional genus penalty. This gives asymptotically good AG code families from Garcia--Stichtenoth tower of unbounded length over a fixed field with soundness bounds independent of $n$, beyond the RS restriction $n\le q$. We also establish mutual correlated agreement up to radius $(1-\sqrtρ-η)n$, with soundness $O(\ell n/(η^3q))$ for $0<η<1-\sqrtρ$. Our half designed distance proof combines auxiliary divisors, simultaneous Berlekamp-Welch interpolation, and error-incidence counting to obtain a common polynomial representation without a Polishchuk-Spielman divisibility lemma. Finally, two counterexamples on the Garcia-Stichtenoth tower show limitations beyond half the minimum distance, at radii below the Johnson bound and with positive slack. The first requires a positive constant soundness lower bound independent of $q$ and $n$, precluding a uniform $O(1/q)$ guarantee throughout the Johnson regime. The second fixes the field and lets the relative gap above half distance tend to zero while ruling out correlated agreement for every soundness parameter $σ<1$, with positive limiting rate and relative error radius.

0.22

Sunflowers of Reed--Solomon Codes

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

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

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

Breaking linearity in the sum-rank metric: MSRD codes from switched $σ$-rational normal curves

cs.IT math.CO ·2026-10-08 ·Daniele Bartoli, Giovanni Giuseppe Grimaldi, Giovanni Longobardi
similarity 0.64
Abstract

We construct a family of scalar-closed, non-additive maximum sum-rank distance codes (MSRD) by switching norm components of a $σ$-rational normal curve and lifting the resulting point set through a linearized Reed--Solomon syndrome map. We characterize the admissible switches by a multiplicative stability condition on the norm classes. In particular, for $1 \leq n_i \leq m$, $N=n_1+\ldots+n_{\ell}$ and $2\leqδ\leq N-1$, every partition of $\mathbb{F}_q^*$ satisfying a specific condition, referred to as Condition $(\diamond)$, yields a code in $\mathbb{F}_{q^m}^{N}$ of size $q^{m(N-δ+1)}$ and minimum sum-rank distance $δ$; the code is non-additive whenever a curve component is retained. For $\ell\geq2$ these appear to be the first non-additive MSRD codes in the literature, all previously known families with more than one block being $\mathbb{F}_q$-linear. Moreover, every code of the family has the same sum-rank weight distribution as an $\mathbb{F}_{q^m}$-linear MSRD code with the same parameters, although the geometry of the switched set distinguishes it from linearized Reed--Solomon codes. In the single-block case, an explicit rank isometry identifies the construction with the cone codes of Durante, Grimaldi and Longobardi.

0.36

Exact Minimum Extension Degrees for Reed Solomon Codes under Linear and Nonlinear Repair at the Cut Set Bound

cs.IT ·2026-10-25 ·Yuhan Li
theoryhot direction similarity 0.63
Abstract · 21 pages

We study the minimum extension degree required for a Reed--Solomon code to admit exact $\mathbb{F}_q$-linear repair at the cut-set bound from every prescribed set of $d$ helpers. Let $s=d-k+1$, and let $Q_s(n)$ be the minimum product of $n$ pairwise coprime integers, each at least $s$. For every prime power $q$ and all $3\le k<d<n\le2d-2$, we prove that the minimum degree over $\mathbb{F}_q$ is exactly $sQ_s(n)$. When all surviving nodes are helpers, we also characterize the admissible extension degrees and bound the number of coordinates that can attain the cut-set bound. The required achievability follows from existing construction methods; we give a short existence proof using splitting subspaces. For a family of parameters with $n>2d-2$, we obtain strictly smaller extension degrees, showing that the range restriction cannot be omitted altogether. Finally, we prove that a nonlinear repair scheme attaining the cut-set bound induces an $\mathbb{F}_p$-linear repair scheme on the same code, where $p$ is the characteristic. Consequently, the extension-degree lower bounds over the prime field remain valid without a linearity assumption.

0.51