CS Paper Radar

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

Huakai Wei, Shiyuan Qiang, Shaofang Hong

cs.IT math.NT ·submitted 2026-10-21 13:44 UTC · v1

Abstract

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.

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

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

MDS codes containing a fixed subcode over finite field extensions

cs.IT math.NT ·2026-10-25 ·Yangcheng Li, Pingzhi Yuan
theoryhot direction similarity 0.72
Abstract · 17 Pages

Let $2\le k\le n$ and let $U\le\mathbb{F}_q^n$ be a fixed $(k-1)$-dimensional linear code. We study the $[n,k]$ maximum distance separable (MDS) codes over finite extensions of $\mathbb{F}_q$ that contain the scalar extension of $U$. Our approach constructs an auxiliary linear code from \(U\). Its full-weight words characterize the desired MDS completions. We prove that \(U\) admits an \([n,k]\) MDS completion over some finite extension of \(\mathbb{F}_q\) if and only if \(d(U)\ge n-k+1\). When this condition holds, the number of these MDS codes over $\mathbb{F}_{q^m}$ is \[\#\left\{W\le\mathbb{F}_{q^m}^n:U\otimes_{\mathbb{F}_q}\mathbb{F}_{q^m}\subseteq W,\ \dim_{\mathbb{F}_{q^m}} W=k,\ W\text{ is MDS}\right\}=\frac{χ_{δ_GM(G)}(q^m)}{q^m-1},\] where $G$ is a generator matrix of $U$, $δ_GM(G)$ is its represented derived matroid, and $χ_{δ_GM(G)}$ is its characteristic polynomial. In particular, the formula determines existence over each extension field and the least extension degree for which such an MDS code exists. Examples show that these counts may distinguish different representations of the same column matroid, while monomially inequivalent codes may have identical counts over every finite extension.

0.28

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

Subcodes with Prescribed Hull Dimensions in Linear Codes:Enumeration, Containment, and Asymptotic Distributions

cs.IT ·2026-10-26 ·Linhan Xiong, Hongwei Liu, Liren Lin
similarity 0.70
Abstract · 39 pages

Mass formulas for prescribed hull dimensions have mainly been studied for linear codes viewed as subspaces of the whole space. We study internal enumeration for an arbitrary fixed parent code. Let $C$ be an $[n,k]_q$ linear code with an $\ell$-dimensional hull, and let $s$ be the subcode dimension. We determine the number of subcodes with prescribed dimension, hull dimension, and type over finite fields of both even and odd characteristic. We decompose the parent code into an LCD complement and its hull, and use projection to reduce enumeration to the corresponding problem inside the LCD complement. This yields explicit formulas refined by complete type and shows that the counts depend only on the relevant parameters, not on the particular parent code or its length. The known whole-space mass formulas and the enumeration of LCD subcodes of LCD codes arise as special cases. Motivated by code extension, we also study the dual containment problem: for a fixed code, we enumerate larger codes containing it with prescribed hull dimension and type. By duality, this problem is converted into the subcode enumeration problem already solved above, leading to corresponding conditional mass formulas. Finally, we investigate the asymptotic distributions arising from the exact enumeration formulas. When both the subcode dimension $s$ and $k-\ell-s$ tend to infinity, the hull distribution is governed by the LCD complement, and the limiting proportions are explicit constants determined by the field, the prescribed hull dimension, and the relevant type. When $s$ approaches or exceeds the dimension $k-\ell$ of the LCD complement, we determine the asymptotic proportion of subcodes attaining the minimum possible hull dimension and establish the associated concentration behavior. Analogous asymptotic results are obtained for the containment problem.

0.23

On the MDS conjecture in even characteristic

cs.IT math.CO ·2026-10-20 ·Bocong Chen, Jing Huang
theoryhot direction similarity 0.69
Abstract · 34 pages

We prove that every nontrivial linear $[n,k]$ maximum distance separable (MDS) code over a finite field $\F_q$ of characteristic two satisfies $n\le q+1$, except in dimensions $k=3$ and $k=q-1$, where $n\le q+2$. This resolves the linear MDS conjecture in even characteristic.

0.24

Covering Radius and Deep Holes of Hyperderivative Reed-Solomon Codes under the NRT Metric

cs.IT ·2026-10-12 ·Zhihao Zhu, Haojie Gu, Jun Zhang, Yu Li
similarity 0.69
Abstract

The deep hole problem is a fundamental problem in coding theory, and it has many important applications in code constructions and cryptography. The deep hole problem of Reed-Solomon codes has gained a lot of attention. As a generalization of Reed-Solomon codes under Hamming metric, we study the covering radius and deep holes of Hyperderivative Reed-Solomon (HRS) codes under the Niederreiter-Rosenbloom-Tsfasman (NRT) metric. We determine the NRT covering radius of HRS code and characterize its NRT deep holes via Maximum Distance Separable (MDS) extensions and polynomial remainder conditions. We further relate the enumeration of NRT deep holes to the characteristic polynomial of an associated hyperplane arrangement. We also provide three classes of explicit NRT deep-hole constructions, propose a Cheng-Murray type conjecture for HRS codes under the NRT metric and obtain a conditional low-layer description. Using these characterizations, we derive exact enumeration formulas in several special cases.

0.19

The Support-Distribution Conditions for MSRD Codes Reduce to a Single Inequality

cs.IT ·2026-10-29 ·Xiang Fan
theory similarity 0.69
Abstract · 18 pages

Byrne, Gluesing-Luerssen, and Ravagnani determined the number of codewords with a prescribed nonzero support in a linear maximum sum-rank distance code whose blocks have a common number of columns. Their formula depends only on the code parameters and the support dimensions. Evaluating it for arbitrary parameters gives a family of necessary nonnegativity conditions for existence. We prove their conjecture that this family is equivalent to the condition at the vector of total dimension $d+1$ obtained by filling the longest blocks first, where $d$ is the distance parameter. The resulting explicit criterion applies over every finite field $\mathbb F_q$, for all row numbers $n_i\leqslant m$ and $1\leqslant d<N$, where $m$ is the common number of columns and $N$ is the total number of rows. It also covers the boundary cases in which this vector fills each of its nonzero blocks completely, not explicitly included in the conjecture's displayed parameter range. The proof uses a generating function and an exchange identity to reduce the problem to vectors obtained by filling the longest blocks first. We then estimate alternating sums of elementary symmetric polynomials, with a separate argument for $q=2$. The dual conditions admit the same reduction. For codes that exist, the joint condition follows from sphere-packing bounds for the code and its dual. An infinite family of parameters satisfies the joint condition but admits no such linear code.

0.22