CS Paper Radar

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

Guanghui Zhang, Zhengbang Zha

cs.IT ·submitted 2026-11-08 08:09 UTC · v1
theory

Abstract

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.

Comment
18 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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

Six Families of Binary Codes Arising from Ding's Conjectures

cs.IT ·2026-09-29 ·Xiaoqiang Wang, Shiyan Xiong, Mu yuan, Jing Qiu, Dabin Zheng +1 more
theory similarity 0.70
Abstract

Ding \cite{Ding2016} proposed ten conjectures on binary linear codes arising from Boolean functions. Four of them, namely Conjectures 38--41, were subsequently proved by Göloğlu and Krasnayová \cite{GologluKrasnayova2019}. In this paper, we investigate the remaining six conjectures, namely Conjectures 19, 27, 30, 33, 34, and 37. For Conjectures~19 and~27, we obtain common weight restrictions and several infinite five-weight families. For Conjecture~30, we prove that every admissible code has three, four, or five nonzero weights, and an explicit four-weight example disproves the original ``three or five weights'' assertion. For Conjecture~33, an infinite five-weight family is obtained. For Conjecture~34, we obtain a general $(2h+1)$-weight upper bound and give an explicit six-weight counterexample, showing that the original ``three or five weights'' assertion is false in general, where $h$ is a positive integer. The case $h=3$ with $3\nmid m$ is also completely determined. Finally, Conjecture~37 is completely resolved by combining the known results of Ahmadi and Shafaeiabr \cite{AhmadiShafaeiabr2023} with the treatment of the two remaining classes $(a)$ and $(b)$.

0.04

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

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

Infinite families of 3-designs from linear and nonlinear codes

cs.IT ·2026-09-14 ·Shiyan Xiong, Xiaoqiang Wang, Dabin Zheng, Qinqin Ji
similarity 0.69
Abstract

The connection between coding theory and combinatorial $t$-designs is an important research topic at the intersection of coding theory and combinatorics. Let $q=p^m$, where $p$ is an odd prime and $m\geq 2$. In this paper, we investigate a class of linear codes $\mathcal{C}$ over $\mathbb{F}_{q^2}$ and their connection with combinatorial $3$-designs. By analyzing the relevant structural properties of $\mathcal{C}$ and $\mathcal{C}^{\perp}$, we show that the supports of the codewords of every nonzero weight in $\mathcal{C}$ and {the supports of the codewords of weight $4$ in $\mathcal{C}^{\perp}$} form $3$-designs. We further investigate a class of nonlinear codes $\mathcal{C}_2$ associated with $\mathcal{C}$, and prove that the supports of the codewords of every nonzero Hamming weight in $\mathcal{C}_2$ also form $3$-designs. These results identify further classes of linear and nonlinear codes whose codewords support combinatorial $3$-designs. In particular, the nonlinear case provides additional examples of codes supporting $3$-designs, a topic for which relatively few results are currently available. As applications, we construct from $\mathcal{C}^{\perp}$ an entanglement-assisted quantum error-correcting code with parameters $[[q+1,q-3,4;4]]_q$. We also prove that $\mathcal{C}$ is an all-symbol locally repairable code with locality $3$. Furthermore, we show that the code $\mathcal{C}$ {meets the Singleton-type bound for locally repairable codes} and hence is optimal in some cases.

0.22

Deep holes of full-length Reed--Solomon codes

cs.IT ·2026-10-21 ·Bocong Chen, Jing Huang
similarity 0.69
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

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

Cubical Sheaf Complexes with Constant Expansion with Applications to Asymptotically Good qLTCs

cs.IT cs.CCquant-ph ·2026-09-23 ·Yeyuan Chen, Miryam Mi-Ying Huang, Yinchen Liu, Er-Cheng Tang
theoryhighly cited similarity 0.68
Abstract

For every fixed integers $r \ge 4$ and $2 \le k \le r-2$, we construct $r$-dimensional cubical sheaf complexes whose degree-$k$ CSS codes have positive constant rate, linear distance, and constant soundness, with bounded row and column weights. Taking $r=4$ and $k=2$ gives a family of asymptotically good binary qLTCs. At the core of our construction is a uniform product-expansion theorem for explicit Reed-Solomon codes on norm-one evaluation sets. The key point is that the expansion constant stays bounded away from zero as the local code lengths grow. We place these codes on arithmetic cubical complexes, obtaining constant local expansion for both the resulting sheaf and its dual. Together with the local-to-global framework of Dinur, Lin, and Vidick (FOCS 2024) and sheaf duality, this gives linear distance and constant soundness, while an asymmetric choice of local code dimensions gives positive rate. The resulting codes are explicit and polynomial-time computable.

0.35