betaFeedback

WorksComputer Science

New Results on the Subfield Metric

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λ>1. Finally, we complement the collection of classical coding-theoretic bounds available for the λλ-subfield metric by deriving Griesmer-, Elias- and Johnson-type bounds.

Introduction

The λ\lambda-subfield metric was introduced by Grassl, Horlemann and Weger in [7], motivated by asymmetric quantum error correction. For a vector over Fqm\mathbb{F}_{q^m}, the λ\lambda-subfield weight distinguishes between nonzero coordinates contained in the base field Fq\mathbb{F}_q, having weight 1, and coordinates outside the base field, which we weight with λ≥1\lambda\ge1. Hence, for λ=1\lambda= 1 one recovers the Hamming metric, while for larger values of λ\lambda, errors outside the base field are penalized more.

While the λ\lambda-subfield metric is defined coordinate-wise (like the Hamming metric), its dependence on the distinguished subfield Fq⊆Fqm\mathbb{F}_q \subseteq\mathbb{F}_{q^m} suggests a connection to the rank metric. Indeed, the rank metric also exploits the Fq\mathbb{F}_q-structure of Fqm\mathbb{F}_{q^m}: rather than merely counting which coordinates are nonzero, it measures the Fq\mathbb{F}_q-dimension of the Fq\mathbb{F}_q-linear space spanned by all coordinates. It is therefore natural to ask, which features of the λ\lambda-subfield metric are inherited from the Hamming metric, which from the rank metric, and which are genuinely specific to the new metric.

Our first answer to this question comes from codes that are optimal with respect to a Singleton-like bound. In the Hamming metric and in the rank metric, the corresponding optimal codes are the well-known Maximum Distance Separable (MDS) and Maximum Rank Distance (MRD) codes, respectively. We call codes attaining the Singleton-like bound in the λ\lambda-subfield metric from [7] Maximum λ\lambda-subfield Distance (Mλ\lambdaD) codes and show that they fit naturally between these two classical families. More precisely, for codes of length nn over Fqm\mathbb{F}_{q^m}, we establish the hierarchy MRD⊆MλD⊆MDS\mathrm{MRD} \subseteq\mathrm{M}\lambda\mathrm{D} \subseteq\mathrm{MDS}, for m≥nm \ge n.

This first result extends observations from [7] and suggests that the λ\lambda-subfield metric lies in between these two metrics. We further derive structural restrictions on their parameters and investigate how the Mλ\lambdaD property changes with different values of λ\lambda.

This naturally raises the question of how large the class of Mλ\lambdaD codes actually is. The density of codes attaining a Singleton-like bound can vary considerably with the underlying metric. In the Hamming metric, MDS codes are dense as the field size grows and sparse as the length of the code grows. On the other hand, the asymptotic behavior of MRD codes is more subtle and has only recently been understood: While Fqm\mathbb{F}_{q^m}-linear MRD codes are dense for qq growing [12], the larger class of Fq\mathbb{F}_q-linear MRD codes are neither dense nor sparse [1, 2, 6, 9].

For other metrics the situation can be even more restrictive: in the Lee metric, non-trivial linear codes attaining the corresponding Singleton-like bounds essentially do not exist [3], while Maximum Homogeneous Distance codes over finite chain rings were recently shown to consist essentially only of lifted MDS codes [13]. Thus, maximum-distance codes can range from abundant families to almost nonexistent ones, depending on the underlying metric.

Following the general framework for densities of codes developed in [8], we determine the density of linear and sublinear Mλ\lambdaD codes in several asymptotic regimes, such as the length nn, the base field size qq or the extension degree for the field of linearity ℓ\ell tending to infinity.

The inclusions MRD ⊆\subseteq Mλ\lambdaD ⊆\subseteq MDS also allow us to ask a more refined question: how large is the family of Mλ\lambdaD codes within the set of MDS codes and how many Mλ\lambdaD codes are MRD.

We next turn to optimal codes for a Plotkin-like bound given in [7]. These are constant-weight codes in the λ\lambda-subfield metric. The classification of such codes has recently been completed for other non-Hamming metrics, including the Lee metric [3] and the homogeneous metric over finite chain rings [13]. For the λ\lambda-subfield metric, we construct a family of constant-weight codes and following the characterization of constant weight codes by Wood [15], we show that, for λ>1\lambda> 1, every non-degenerate linear constant-weight code is equivalent to a repetition of this construction.

Finally, we extend the collection of classical bounds known for the λ\lambda-subfield metric. Building on the Singleton-, Plotkin-, sphere-packing- and Gilbert–Varshamov-like bounds established in [7], we derive Griesmer-, Elias- and Johnson-like bounds.

The Johnson-like bounds provide another interesting comparison with the Hamming metric and the rank metric. In the Hamming metric, the classical Johnson bound gives a list-decoding radius beyond half the minimum distance, ensuring that the list of closest codewords remains polynomial in size. In contrast, the same approach in the rank metric does not work as shown in [14]. For the λ\lambda-subfield metric, we obtain a non-trivial list-decoding radius by exploiting its additive structure and the framework in [11]. Thus, in this respect, the λ\lambda-subfield metric behaves more similarly to the Hamming metric than to the rank metric.

Together, these results show that the λ\lambda-subfield metric is not simply a weighted variant of the Hamming metric: its theory combines features from the Hamming and the rank metric, while exhibiting its own extremal and asymptotic behavior.

The paper is organized as follows. In Section 2, we introduce the necessary notation and recall the Hamming, rank and λ\lambda-subfield metrics. Section 3 studies linear and sublinear Mλ\lambdaD codes and Section 4 investigates their asymptotic density. Section 5 characterizes all constant-weight codes. In Section 6, we derive and compare several Johnson-type bounds, while Section 7 establishes additional classical bounds in the λ\lambda-subfield metric. Finally, we conclude the paper with open problems and future directions in Section 8. Parts of the results presented in this paper originated in the bachelor’s theses of the first two authors and within the MISTI research exchange program of the third author.

Preliminaries

We begin by fixing the notation and recalling the basic notions used throughout the paper.

Let qq be a prime power and let Fqm\mathbb{F}_{q^m} be the finite field with qmq^m elements, with multiplicative group Fqm×\mathbb{F}_{q^m}^{\times}.

We denote by [n][n] the integers from 11 to nn and for a set SS, we denote by ∣S∣\lvert S\rvert its cardinality.

We denote the identity matrix of size n×nn \times n by Id⁡n\operatorname{Id}_n and for a matrix AA, we denote by ATA^{\mathsf{T}} its transpose. O\mathcal{O} denotes the big O notation, that is, f(n)=O(g(n))f(n) = \mathcal{O}(g(n)) if there exist constants C>0C > 0 and n0n_0 such that ∣f(n)∣≤C∣g(n)∣\lvert f(n)\rvert\le C\lvert g(n)\rvert for all n≥n0n \ge n_0.

Throughout this paper, we fix ℓ\ell to be a divisor of mm and denote by s=m/ℓs = m/\ell. We consider the field extension Fqℓ⊆Fqm\mathbb{F}_{q^\ell} \subseteq\mathbb{F}_{q^m} with [Fqm:Fqℓ]=s[\mathbb{F}_{q^m} : \mathbb{F}_{q^\ell}] = s.

A linear code of length nn and dimension kk over Fqm\mathbb{F}_{q^m} is a kk-dimensional Fqm\mathbb{F}_{q^m}-subspace C⊆Fqmn\mathcal{C} \subseteq\mathbb{F}_{q^m}^n. We refer to such a code as an [n,k]qm[n,k]_{q^m} code. More generally, an Fqℓ\mathbb{F}_{q^\ell}-linear (or sublinear) code is a kk-dimensional Fqℓ\mathbb{F}_{q^\ell}-subspace of Fqmn\mathbb{F}_{q^m}^n and is denoted by [n,k]qℓ/qm[n,k]_{q^\ell/q^m}.

For a matrix G∈Fqmk×nG \in\mathbb{F}_{q^m}^{k \times n}, we denote by ⟨G⟩Fqℓ\langle G\rangle_{\mathbb{F}_{q^\ell}} its row span over Fqℓ\mathbb{F}_{q^\ell}. We call GG a generator matrix of a Fqℓ\mathbb{F}_{q^\ell}-linear code C\mathcal{C} if C=⟨G⟩Fqℓ\mathcal{C} = \langle G\rangle_{\mathbb{F}_{q^\ell}}.

The dual code C⊥\mathcal{C}^{\perp} consists of all vectors which are orthogonal to all codewords, i.e.,

C⊥={x∈Fqmn∣⟨x,c⟩=0 ∀c∈C},\mathcal{C}^{\perp} = \{x \in\mathbb{F}_{q^m}^n \mid\langle x,c\rangle= 0\ \forall c \in\mathcal{C}\},

where ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle denotes the standard inner product.

A linear isometry on Fqmn\mathbb{F}_{q^m}^n for a weight wt⁡\operatorname{wt} is a linear map, which preserves the weight, i.e., wt⁡(x)=wt⁡(φ(x))\operatorname{wt}(x) = \operatorname{wt}(\varphi(x)) for all x∈Fqmnx \in\mathbb{F}_{q^m}^n. If a code C′\mathcal{C}' is the image of a code C\mathcal{C} under such an isometry, i.e., φ(C)=C′\varphi(\mathcal{C}) = \mathcal{C}', then we call the two codes equivalent with respect to the weight wt⁡\operatorname{wt}.

We call a code non-degenerate if no coordinate is identically zero on the whole code.

We next recall the Hamming metric and the rank metric, which will serve as the main points of comparison for the λ\lambda-subfield metric.

Definition 1. For x∈Fqmnx \in\mathbb{F}_{q^m}^n, the Hamming weight is given by its number of nonzero entries, i.e.,

wt⁡H(x)=∣{i∈[n]∣xi≠0}∣,\operatorname{wt}_{H}(x) = \lvert\{i \in[n] \mid x_i \ne0\}\rvert,

and the rank weight is given by

wt⁡R(x)=dim⁡Fq(⟨x1,…,xn⟩Fq).\operatorname{wt}_{R}(x) = \dim_{\mathbb{F}_q}(\langle x_1,\ldots,x_n\rangle_{\mathbb{F}_q}).

The induced distances between x,y∈Fqmnx,y \in\mathbb{F}_{q^m}^n are then given by dH(x,y)=wt⁡H(x−y)d_H(x,y) = \operatorname{wt}_H(x-y) and dR(x,y)=wt⁡R(x−y)d_R(x,y) = \operatorname{wt}_R(x-y).

For a [n,k]qm[n,k]_{q^m} linear code C\mathcal{C}, one defines its minimum Hamming distance, respectively minimum rank distance, as

dH(C)=min⁡{wt⁡H(x)∣x∈C, x≠0},d_H(\mathcal{C}) = \min\{\operatorname{wt}_H(x) \mid x \in\mathcal{C},\ x \ne0\},

respectively as

dR(C)=min⁡{wt⁡R(x)∣x∈C, x≠0}.d_R(\mathcal{C}) = \min\{\operatorname{wt}_R(x) \mid x \in\mathcal{C},\ x \ne0\}.

Whenever the code C\mathcal{C} is clear from the context, we may simply write dHd_H, respectively dRd_R.

In the Hamming metric, the well-known Singleton bound gives an upper bound on dHd_H given the other parameters n,kn,k.

Theorem 2 (Singleton bound). Let C\mathcal{C} be an [n,k]qm[n,k]_{q^{m}} code. Then

dH(C)≤n−k+1.d_{H}(\mathcal{C}) \le n-k+1.

Also in the rank metric, a Singleton-like bound has been established.

Theorem 3 (Rank-metric Singleton-like bound). Let C\mathcal{C} be an [n,k]qm[n,k]_{q^{m}} code. Then

mk≤max⁡{n,m}(min⁡{n,m}−dR(C)+1).mk \le\max\{n,m\}\left(\min\{n,m\}-d_{R}(\mathcal{C})+1\right).

In particular, if n≤mn \le m, we note that the rank-metric Singleton-like bound simplifies to

dR(C)≤n−k+1.d_{R}(\mathcal{C}) \le n-k+1.

The codes attaining the corresponding Singleton bounds are known as Maximum Distance Separable (MDS) and Maximum Rank Distance (MRD) codes, respectively.

We now recall the λ\lambda-subfield metric introduced in [7].

References

  1. [1]Jared Antrobus and Heide Gluesing-Luerssen. Maximal Ferrers diagram codes: constructions and genericity considerations. IEEE Transactions on Information Theory, 65(10):6204–6223, 2019.arxiv.org/abs/1804.00624
  2. [2]Eimear Byrne and Alberto Ravagnani. Partition-balanced families of codes and asymptotic enumeration in coding theory. Journal of Combinatorial Theory, Series A, 171:105169, 2020.arxiv.org/abs/1805.02049
  3. [3]Eimear Byrne and Violetta Weger. Bounds in the Lee metric and optimal codes. Finite Fields and Their Applications, 87:102151, 2023.arxiv.org/abs/2112.06635
  4. [4]Philippe Delsarte. Bilinear forms over a finite field, with applications to coding theory. Journal of combinatorial theory, Series A, 25(3):226–241, 1978.DOI
  5. [5]Ernest Mukhamedovich Gabidulin. Theory of codes with maximum rank distance. Problemy peredachi informatsii, 21(1):3–16, 1985.
  6. [6]Heide Gluesing-Luerssen. On the sparseness of certain linear MRD codes. Linear Algebra and its Applications, 596:145–168, 2020.
  7. [7]Markus Grassl, Anna-Lena Horlemann, and Violetta Weger. The subfield metric and its application to quantum error correction. Journal of Algebra and Its Applications, 23(07):2550063, 2024.DOI
  8. [8]Anina Gruica, Anna-Lena Horlemann, Alberto Ravagnani, and Nadja Willenborg. Densities of codes of various linearity degrees in translation-invariant metric spaces. Designs, Codes and Cryptography, 92(3):609–637, 2024.DOI
  9. [9]Anina Gruica and Alberto Ravagnani. Common complements of linear subspaces and the sparseness of MRD codes. SIAM Journal on Applied Algebra and Geometry, 6(2):79–110, 2022.arxiv.org/abs/2011.02993
  10. [10]Anina Gruica and Alberto Ravagnani. Common complements of linear subspaces and the sparseness of mrd codes. SIAM Journal on Applied Algebra and Geometry, 6(2):79–110, 2022.arxiv.org/abs/2011.02993
  11. [11]Venkatesan Guruswami and Madhu Sudan. Extensions to the johnson bound. Manuscript, February, page 3, 2001.
  12. [12]Alessandro Neri, Anna-Lena Horlemann-Trautmann, Tovohery Randrianarisoa, and Joachim Rosenthal. On the genericity of maximum rank distance and Gabidulin codes. Designs, Codes and Cryptography, 86(2):341–363, 2018.
  13. [13]Andreas Pyka and Violetta Weger. On optimal homogeneous-metric codes. arXiv preprint arXiv:2603.27334, 2026.arxiv.org/abs/2603.27334
  14. [14]Antonia Wachter-Zeh. Bounds on polynomial-time list decoding of rank metric codes. In 2013 IEEE International Symposium on Information Theory, pages 519–523. IEEE, 2013.
  15. [15]Jay Wood. The structure of linear codes of constant weight. Transactions of the American Mathematical Society, 354(3):1007–1026, 2002.
  16. [16]Jay A Wood. Extension theorems for linear codes over finite rings. In International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, pages 329–340. Springer, 1997.DOI

Paper details

vlnc:W_mk4evtq8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents