CS Paper Radar

New Results on the Subfield Metric

Ana Kosovac, Jeanette Plechinger, Nikola Spirovski, Violetta Weger

cs.IT ·submitted 2026-11-13 14:28 UTC · v1

Abstract

In this paper, we further develop the theory of the recently introduced $λ$-subfield metric. We investigate extremal codes, classical bounds and asymptotic densities in this setting. We first study codes attaining a Singleton-type bound, called Maximum $λ$-subfield Distance (M$λ$D) codes. We establish structural restrictions on their parameters and extend the theory to sublinear codes. We then investigate the asymptotic density of M$λ$D codes in several parameter regimes and compare their behavior with that of MDS and MRD codes. We then turn to a Plotkin-like bound, where we construct a family of constant-weight codes attaining the bound and classify all non-degenerate linear constant-weight codes for $λ>1$. Finally, we complement the collection of classical coding-theoretic bounds available for the $λ$-subfield metric by deriving Griesmer-, Elias- and Johnson-type bounds.

Closest papers

Nearest neighbours by meaning across the whole index.

Asymptotic Bounds for Codes in Toroidal Distance

cs.IT ·2026-11-19 ·Pengjie Zhong, Jinquan Luo
theory similarity 0.73
Abstract

The toroidal distance naturally describes the geometry of codes over \(\mathbb Z_q\), where distances are measured modulo \(q\). In this paper, we study asymptotic bounds for codes in \(\mathbb Z_q^n\) under the toroidal metric. We first derive an explicit asymptotic lower bound from the classical Gilbert--Varshamov bounds for the Hamming and Lee metrics, which serves as a baseline for comparison. We then develop a saddle-point approach for the toroidal metric, which yields an asymptotic Gilbert--Varshamov lower bound and an asymptotic Hamming-type upper bound. For \(3\mid q\), we embed ternary Hamming codes into \(\mathbb Z_q^n\) and obtain another asymptotic lower bound for the toroidal metric. In addition, we derive an asymptotic lower bound for Maximum Toroidal Distance (MTD) codes. We compare these lower bounds with the baseline and prove that they are nontrivial in the corresponding parameter ranges. Finally, we compare the asymptotic bounds numerically.

0.15

The ordered sum-rank metric and linearized multiplicity codes: NRT meets sum-rank

cs.IT ·2026-11-15 ·Umberto Martínez-Peñas
similarity 0.72
Abstract

In this work, we introduce linearized multiplicity codes, which are a common generalization of linearized Reed--Solomon codes and univariate multiplicity codes. We also introduce the ordered sum-rank metric, which is a common generalization of the sum-rank metric and the Niederreiter-Rosenbloom-Tsfasman (NRT) metric (or ordered Hamming metric). We provide a Singleton bound for the ordered sum-rank metric and show that linearized multiplicity codes attain it. That is, they are maximum ordered sum-rank distance (MOSRD) codes. We introduce the support lattice for the ordered sum-rank metric and study duality, support distributions and weight distributions of MOSRD codes. We also show that MOSRD codes are ordered MDS, dually quasi MSRD and, under some divisibility conditions, MSRD (and thus MDS). For linear MOSRD codes, we give lower bounds on the field extension degree by the number of matrix columns, and upper bounds on the block length by the base field size. We conclude by showing that linearized multiplicity codes attain such bounds exactly in almost all cases, and the same growth order in all cases.

0.05

Code distances of matrix rank-metric codes under Add-and-Remove transformations

cs.IT ·2026-10-02 ·Gianira N. Alfarano, Rakhi Pratihar, Adrien Vinçotte
theory similarity 0.71
Abstract

For a matrix rank-metric code $\mathcal{C}$ and an integer $i$, the $i$-th subcode distance of $\mathcal{C}$ is the largest minimum rank distance of an $i$-dimensional subcode of $\mathcal{C}$. We study how subcode distances change under the Add-and-Remove construction, in which a subcode of codimension $\ell_s$ is kept and a space of dimension $\ell_a$ is added; this construction is used, with Gabidulin codes, in the $\mathsf{MIRANDA}$ signature scheme. For arbitrary matrix codes, we give inequalities between the subcode distances of the original and of the new code, and we show that Delsarte duality interchanges $\ell_s$ and $\ell_a$. For matrix Gabidulin codes, whose subcode distances are given by an explicit formula, we show that, if $\ell_s<\max\{m,n\}$, then within each block of indices $(a-1)\max\{m,n\}+1,\ldots,a\max\{m,n\}$ not exceeding $\dim_{\mathbb{F}_q}(\mathcal{C}_s)$, all but the last $\ell_s$ subcode distances are the same as for the Gabidulin code, and the remaining ones decrease by at most one; a small example shows that such a decrease can occur. We also express the minimum distance of the new code in terms of the rank distance between the added space and the common subcode. For $\mathsf{MIRANDA}$, the lower bound on the minimum distance of the dual public code used by the known distinguisher when $\ell_s=0$ is a special case of these results; for the proposed parameters, where $\ell_s>0$, the same bound holds for a subcode of codimension $\ell_s$ of the dual public code.

0.05

Covering radius of rank-metric codes via covering lifts and clubs

cs.IT math.CO ·2026-10-08 ·Giuseppe Marino, Alessandro Neri, Alessia Vallefuoco
theory similarity 0.71
Abstract

We introduce a generator-matrix-based geometric approach to the covering radius of $\mathbb F_{q^m}$-linear rank-metric codes. Starting from the $q$-system associated with the code, we define the notion of covering lift and show that the covering radius can be recovered from the hyperplane weights of such lifts. This yields an exact criterion, in terms of the length and effective length of the code, for the covering radius to attain its largest possible value, together with the upper bound $ρ(\mathcal{C})\le \min\{m,n\}-1$ in all remaining cases. We then specialize our approach to $1$-dimensional codes, for which the effective length coincides with the minimum rank distance. In this setting, codes attaining $ρ(\mathcal{C})= \min\{m,n\}-1$ are related to covering lifts that are clubs. More generally, we characterize this case through linear maps into suitable quotient spaces, obtaining equivalent interpretations in terms of generalised evasive subspaces and auxiliary matrix rank-metric codes. These results determine the covering radius for several boundary values of the minimum distance and for all $1$-dimensional codes with extension degree $m\in\{3,4,5\}$. For $m=6$ and every $q$ we provide constructions and, for $q\in\{2,3\}$, computational results showing that $1$-dimensional rank-metric codes with the same length and minimum distance can have different covering radii.

0.05

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

cs.IT ·2026-10-29 ·Xiang Fan
theory similarity 0.70
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

Linear Codes over $\mathbb{F}_{q}+u\mathbb{F}_{q}$ associated with Simplicial Complexes, Their Gray Images, and Subfield Codes

cs.IT ·2026-09-10 ·Ankit Yadav, Akanksha Tiwari, Ritumoni Sarma
similarity 0.70
Abstract

In recent years, simplicial complexes have gained considerable attention as a useful tool for constructing distance-optimal codes over finite fields. In this article, we construct four infinite families of linear codes over the ring $\mathcal{R}=\mathbb{F}_{q}+u\mathbb{F}_{q}$ with $u^2=0$ using simplicial complexes with one or two maximal elements, and completely determine their Lee weight distributions via exponential-sum techniques. By employing a Gray map on $\mathcal{R}$, we obtain infinite families of distance-optimal codes over $\mathbb{F}_{q}$, including a near-Griesmer family, and establish sufficient conditions for their minimality. Furthermore, we investigate the corresponding subfield codes and derive sufficient conditions for their distance-optimality and minimality, yielding infinite families of Griesmer and near-Griesmer codes.

0.18

Concatenated Codes with One Inner Code: Low-Rate Gilbert-Varshamov Asymptotics from Algebraic-Geometric Codes

cs.IT ·2026-11-12 ·Yota Maeda, Ruho Kondo
theory similarity 0.70
Abstract · 25 pages

Constructing codes that attain the Gilbert-Varshamov (GV) bound while admitting efficient encoding and decoding is a fundamental problem in coding theory. We study concatenated codes that reuse a single binary inner code across all outer coordinates. To exploit existing encoding and decoding algorithms, we restrict the outer codes to random subcodes of scaled copies of prescribed algebraic codes and investigate their minimum distance. Our first contribution is a general upper bound on the minimum-distance failure probability that separates two terms controlled by the inner code's bias moments and the dual weight distribution of the prescribed code, together with sufficient conditions for exponential decay. Our second contribution is a concrete construction satisfying these conditions using algebraic-geometric codes from the Garcia-Stichtenoth tower. For every sufficiently small $\varepsilon>0$, we construct a family of random binary codes $C_m$ whose rates approach $\varepsilon^2$ and satisfy \[ \Pr\left[δ(C_m)\geq\frac12-\sqrt{\frac{\ln 2}{2}}\left(\varepsilon+\frac{\varepsilon^3}{2}\right)\right]\geq 1-2^{-c\varepsilon^4N_m}, \] for all sufficiently large $m$, where $N_m$ is the block length and $c>0$ is independent of $\varepsilon$ and $m$. Thus, the distance guarantee matches the leading coefficient of the GV bound at low rates. For each fixed $\varepsilon$, the construction uses a single inner encoding map throughout the family and admits polynomial-time encoding and unique decoding within a guaranteed radius. This answers the question of Doron, Mosheiff, and Wootters for subcodes of scaled algebraic geometry codes at low rates.

0.18

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