Introduction
The λ \lambda λ -subfield metric was introduced by Grassl, Horlemann and Weger in [7 ] , motivated by asymmetric quantum error correction. For a vector over F q m \mathbb{F}_{q^m} F q m , the λ \lambda λ -subfield weight distinguishes between nonzero coordinates contained in the base field F q \mathbb{F}_q F q , having weight 1, and coordinates outside the base field, which we weight with λ ≥ 1 \lambda\ge1 λ ≥ 1 . Hence, for λ = 1 \lambda= 1 λ = 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 F q ⊆ F q m \mathbb{F}_q \subseteq\mathbb{F}_{q^m} F q ⊆ F q m suggests a connection to the rank metric. Indeed, the rank metric also exploits the F q \mathbb{F}_q F q -structure of F q m \mathbb{F}_{q^m} F q m : rather than merely counting which coordinates are nonzero, it measures the F q \mathbb{F}_q F q -dimension of the F q \mathbb{F}_q 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λ \lambda λ D) codes and show that they fit naturally between these two classical families. More precisely, for codes of length n n n over F q m \mathbb{F}_{q^m} F q m , we establish the hierarchy M R D ⊆ M λ D ⊆ M D S \mathrm{MRD} \subseteq\mathrm{M}\lambda\mathrm{D} \subseteq\mathrm{MDS} MRD ⊆ M λ D ⊆ MDS , for m ≥ n m \ge n m ≥ 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λ \lambda λ D property changes with different values of λ \lambda λ .
This naturally raises the question of how large the class of Mλ \lambda λ D 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 F q m \mathbb{F}_{q^m} F q m -linear MRD codes are dense for q q q growing [12 ] , the larger class of F q \mathbb{F}_q 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λ \lambda λ D codes in several asymptotic regimes, such as the length n n n , the base field size q q q or the extension degree for the field of linearity ℓ \ell ℓ tending to infinity.
The inclusions MRD ⊆ \subseteq ⊆ Mλ \lambda λ D ⊆ \subseteq ⊆ MDS also allow us to ask a more refined question: how large is the family of Mλ \lambda λ D codes within the set of MDS codes and how many Mλ \lambda λ D 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 λ > 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λ \lambda λ D 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 q q q be a prime power and let F q m \mathbb{F}_{q^m} F q m be the finite field with q m q^m q m elements, with multiplicative group F q m × \mathbb{F}_{q^m}^{\times} F q m × .
We denote by [ n ] [n] [ n ] the integers from 1 1 1 to n n n and for a set S S S , we denote by ∣ S ∣ \lvert S\rvert ∣ S ∣ its cardinality.
We denote the identity matrix of size n × n n \times n n × n by Id n \operatorname{Id}_n Id n and for a matrix A A A , we denote by A T A^{\mathsf{T}} A T its transpose. O \mathcal{O} O denotes the big O notation, that is, f ( n ) = O ( g ( n ) ) f(n) = \mathcal{O}(g(n)) f ( n ) = O ( g ( n )) if there exist constants C > 0 C > 0 C > 0 and n 0 n_0 n 0 such that ∣ f ( n ) ∣ ≤ C ∣ g ( n ) ∣ \lvert f(n)\rvert\le C\lvert g(n)\rvert ∣ f ( n )∣ ≤ C ∣ g ( n )∣ for all n ≥ n 0 n \ge n_0 n ≥ n 0 .
Throughout this paper, we fix ℓ \ell ℓ to be a divisor of m m m and denote by s = m / ℓ s = m/\ell s = m / ℓ . We consider the field extension F q ℓ ⊆ F q m \mathbb{F}_{q^\ell} \subseteq\mathbb{F}_{q^m} F q ℓ ⊆ F q m with [ F q m : F q ℓ ] = s [\mathbb{F}_{q^m} : \mathbb{F}_{q^\ell}] = s [ F q m : F q ℓ ] = s .
A linear code of length n n n and dimension k k k over F q m \mathbb{F}_{q^m} F q m is a k k k -dimensional F q m \mathbb{F}_{q^m} F q m -subspace C ⊆ F q m n \mathcal{C} \subseteq\mathbb{F}_{q^m}^n C ⊆ F q m n . We refer to such a code as an [ n , k ] q m [n,k]_{q^m} [ n , k ] q m code. More generally, an F q ℓ \mathbb{F}_{q^\ell} F q ℓ -linear (or sublinear) code is a k k k -dimensional F q ℓ \mathbb{F}_{q^\ell} F q ℓ -subspace of F q m n \mathbb{F}_{q^m}^n F q m n and is denoted by [ n , k ] q ℓ / q m [n,k]_{q^\ell/q^m} [ n , k ] q ℓ / q m .
For a matrix G ∈ F q m k × n G \in\mathbb{F}_{q^m}^{k \times n} G ∈ F q m k × n , we denote by ⟨ G ⟩ F q ℓ \langle G\rangle_{\mathbb{F}_{q^\ell}} ⟨ G ⟩ F q ℓ its row span over F q ℓ \mathbb{F}_{q^\ell} F q ℓ . We call G G G a generator matrix of a F q ℓ \mathbb{F}_{q^\ell} F q ℓ -linear code C \mathcal{C} C if C = ⟨ G ⟩ F q ℓ \mathcal{C} = \langle G\rangle_{\mathbb{F}_{q^\ell}} C = ⟨ G ⟩ F q ℓ .
The dual code C ⊥ \mathcal{C}^{\perp} C ⊥ consists of all vectors which are orthogonal to all codewords, i.e.,
C ⊥ = { x ∈ F q m n ∣ ⟨ 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}\}, C ⊥ = { x ∈ F q m n ∣ ⟨ x , c ⟩ = 0 ∀ c ∈ C } ,
where ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ denotes the standard inner product.
A linear isometry on F q m n \mathbb{F}_{q^m}^n F q m n for a weight wt \operatorname{wt} wt is a linear map, which preserves the weight, i.e., wt ( x ) = wt ( φ ( x ) ) \operatorname{wt}(x) = \operatorname{wt}(\varphi(x)) wt ( x ) = wt ( φ ( x )) for all x ∈ F q m n x \in\mathbb{F}_{q^m}^n x ∈ F q m n . If a code C ′ \mathcal{C}' C ′ is the image of a code C \mathcal{C} C under such an isometry, i.e., φ ( C ) = C ′ \varphi(\mathcal{C}) = \mathcal{C}' φ ( C ) = C ′ , then we call the two codes equivalent with respect to the weight wt \operatorname{wt} 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 ∈ F q m n x \in\mathbb{F}_{q^m}^n x ∈ F q m n , the Hamming weight is given by its number of nonzero entries, i.e.,
wt H ( x ) = ∣ { i ∈ [ n ] ∣ x i ≠ 0 } ∣ , \operatorname{wt}_{H}(x) = \lvert\{i \in[n] \mid x_i \ne0\}\rvert, wt H ( x ) = ∣{ i ∈ [ n ] ∣ x i = 0 }∣ , and the rank weight is given by
wt R ( x ) = dim F q ( ⟨ x 1 , … , x n ⟩ F q ) . \operatorname{wt}_{R}(x) = \dim_{\mathbb{F}_q}(\langle x_1,\ldots,x_n\rangle_{\mathbb{F}_q}). wt R ( x ) = dim F q (⟨ x 1 , … , x n ⟩ F q ) . The induced distances between x , y ∈ F q m n x,y \in\mathbb{F}_{q^m}^n x , y ∈ F q m n are then given by d H ( x , y ) = wt H ( x − y ) d_H(x,y) = \operatorname{wt}_H(x-y) d H ( x , y ) = wt H ( x − y ) and d R ( x , y ) = wt R ( x − y ) d_R(x,y) = \operatorname{wt}_R(x-y) d R ( x , y ) = wt R ( x − y ) .
For a [ n , k ] q m [n,k]_{q^m} [ n , k ] q m linear code C \mathcal{C} C , one defines its minimum Hamming distance, respectively minimum rank distance, as
d H ( 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\}, d H ( C ) = min { wt H ( x ) ∣ x ∈ C , x = 0 } , respectively as
d R ( 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\}. d R ( C ) = min { wt R ( x ) ∣ x ∈ C , x = 0 } . Whenever the code C \mathcal{C} C is clear from the context, we may simply write d H d_H d H , respectively d R d_R d R .
In the Hamming metric, the well-known Singleton bound gives an upper bound on d H d_H d H given the other parameters n , k n,k n , k .
Theorem 2 (Singleton bound). Let C \mathcal{C} C be an [ n , k ] q m [n,k]_{q^{m}} [ n , k ] q m code. Then
d H ( C ) ≤ n − k + 1. d_{H}(\mathcal{C}) \le n-k+1. d H ( C ) ≤ 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} C be an [ n , k ] q m [n,k]_{q^{m}} [ n , k ] q m code. Then
m k ≤ max { n , m } ( min { n , m } − d R ( C ) + 1 ) . mk \le\max\{n,m\}\left(\min\{n,m\}-d_{R}(\mathcal{C})+1\right). mk ≤ max { n , m } ( min { n , m } − d R ( C ) + 1 ) .
In particular, if n ≤ m n \le m n ≤ m , we note that the rank-metric Singleton-like bound simplifies to
d R ( C ) ≤ n − k + 1. d_{R}(\mathcal{C}) \le n-k+1. d R ( C ) ≤ 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 ] .
Definition 4. Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a real number. The λ \lambda λ -subfield weight on F q m \mathbb{F}_{q^{m}} F q m is defined as
wt λ ( a ) = { 0 , a = 0 , 1 , a ∈ F q ∖ { 0 } , λ , a ∈ F q m ∖ F q . \operatorname{wt}_{\lambda}(a)=
\begin{cases}
0, & a=0,\\
1, & a\in\mathbb{F}_{q}\setminus\{0\},\\
\lambda, & a\in\mathbb{F}_{q^{m}}\setminus\mathbb{F}_{q}.
\end{cases} wt λ ( a ) = ⎩ ⎨ ⎧ 0 , 1 , λ , a = 0 , a ∈ F q ∖ { 0 } , a ∈ F q m ∖ F q .
We extend the weight to vectors x ∈ F q m n x\in\mathbb{F}_{q^{m}}^{n} x ∈ F q m n , additively, i.e.,
wt λ ( x ) = ∑ i = 1 n wt λ ( x i ) , \operatorname{wt}_{\lambda}(x)=\sum_{i=1}^{n}\operatorname{wt}_{\lambda}(x_i), wt λ ( x ) = i = 1 ∑ n wt λ ( x i ) ,
and the λ \lambda λ -subfield distance between x , y ∈ F q m n x,y\in\mathbb{F}_{q^{m}}^{n} x , y ∈ F q m n is then given by
d λ ( x , y ) = wt λ ( x − y ) . d_{\lambda}(x,y)=\operatorname{wt}_{\lambda}(x-y). d λ ( x , y ) = wt λ ( x − y ) .
Similar to the Hamming and the rank metric, the minimum λ \lambda λ -subfield distance of a linear code C \mathcal{C} C is defined as
d λ ( C ) = min { wt λ ( c ) ∣ c ∈ C , c ≠ 0 } . d_{\lambda}(\mathcal{C})=\min\{\operatorname{wt}_{\lambda}(c)\mid c\in\mathcal{C},\ c\ne0\}. d λ ( C ) = min { wt λ ( c ) ∣ c ∈ C , c = 0 } .
If the minimum λ \lambda λ -subfield distance of C \mathcal{C} C is known, we refer to it as a [ n , k , d λ ] q m [n,k,d_{\lambda}]_{q^{m}} [ n , k , d λ ] q m code.
For λ > 1 \lambda>1 λ > 1 , the F q m \mathbb{F}_{q^{m}} F q m -linear isometries of the λ \lambda λ -subfield metric are coordinate permutations and coordinatewise multiplication by elements of F q × \mathbb{F}_{q}^{\times} F q × . Thus their group is
( F q × ) n ⋊ S n . (\mathbb{F}_{q}^{\times})^{n}\rtimes S_{n}. ( F q × ) n ⋊ S n .
For λ = 1 \lambda=1 λ = 1 , the metric is the Hamming metric, whose F q m \mathbb{F}_{q^{m}} F q m -linear isometry group is given by
( F q m × ) n ⋊ S n . (\mathbb{F}_{q^{m}}^{\times})^{n}\rtimes S_{n}. ( F q m × ) n ⋊ S n .
Clearly, we have that
d H ( C ) ≤ d λ ( C ) ≤ λ d H ( C ) d_{H}(\mathcal{C})\le d_{\lambda}(\mathcal{C})\le\lambda d_{H}(\mathcal{C}) d H ( C ) ≤ d λ ( C ) ≤ λ d H ( C )
for every code C \mathcal{C} C .
This observation leads to a Singleton-like bound for the λ \lambda λ -subfield metric, as stated in [7 ] .
Theorem 5 (Singleton-like bound in λ \lambda λ -subfield metric). Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a real number and C ⊆ F q m C \subseteq\mathbb{F}_{q^m} C ⊆ F q m be a code (not necessarily linear) with minimum λ \lambda λ -subfield distance d λ d_\lambda d λ . Then
⌊ d λ − 1 λ ⌋ ≤ n − ⌈ log q m ( ∣ C ∣ ) ⌉ . \left\lfloor\frac{d_\lambda-1}{\lambda} \right\rfloor\le n-\left\lceil\log_{q^m}(|C|) \right\rceil. ⌊ λ d λ − 1 ⌋ ≤ n − ⌈ log q m ( ∣ C ∣ ) ⌉ . Thus, for linear codes of dimension k k k , we get
⌊ d λ − 1 λ ⌋ ≤ n − k . \left\lfloor\frac{d_\lambda-1}{\lambda} \right\rfloor\le n-k. ⌊ λ d λ − 1 ⌋ ≤ n − k .
In the case of linear codes, the Singleton-like bound can be further tightened as in [7 ] :
Theorem 6. Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a real number and C ⊆ F q m n C \subseteq\mathbb{F}_{q^m}^{n} C ⊆ F q m n be a linear code of dimension k k k with minimum λ \lambda λ -subfield distance d λ d_\lambda d λ . Then
d λ ≤ λ ( n − k ) + 1. d_\lambda\le\lambda(n-k)+1. d λ ≤ λ ( n − k ) + 1.
A code attaining the above bound with equality is called a maximum λ \lambda λ -subfield distance code, or Mλ \lambda λ D code.
In [7 ] , the authors also provide the size of λ \lambda λ -subfield metric balls, i.e.,
B λ ( r , n , q m ) = { x ∈ F q m n ∣ wt λ ( x ) ≤ r } . B_\lambda(r,n,q^m)=\{x\in\mathbb{F}_{q^m}^{n}\mid\operatorname{wt}_{\lambda}(x)\le r\}. B λ ( r , n , q m ) = { x ∈ F q m n ∣ wt λ ( x ) ≤ r } .
Lemma 7. Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be an integer and 0 ≤ r ≤ λ n 0\le r\le\lambda n 0 ≤ r ≤ λn be a positive integer. We have that
V λ ( r , n , q m ) : = ∣ B λ ( r , n , q m ) ∣ = ∑ j = 0 r ∑ i = 0 ⌊ j / λ ⌋ ( q m − q ) i ( n i ) ( q − 1 ) j − λ i ( n − i j − λ i ) . V_\lambda(r,n,q^m):=|B_\lambda(r,n,q^m)|
=\sum_{j=0}^{r}\sum_{i=0}^{\lfloor j/\lambda\rfloor}
(q^m-q)^i\binom{n}{i}(q-1)^{j-\lambda i}\binom{n-i}{j-\lambda i}. V λ ( r , n , q m ) := ∣ B λ ( r , n , q m ) ∣ = j = 0 ∑ r i = 0 ∑ ⌊ j / λ ⌋ ( q m − q ) i ( i n ) ( q − 1 ) j − λi ( j − λi n − i ) .
To allow also real values of λ \lambda λ , we may adapt the formula as follows:
Lemma 8. Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a real number and 0 ≤ r ≤ λ n 0\le r\le\lambda n 0 ≤ r ≤ λn . Then
V λ ( r , n , q m ) = ∑ a = 0 min { n , ⌊ r / λ ⌋ } ( n a ) ( q m − q ) a ∑ b = 0 min { n − a , ⌊ r − λ a ⌋ } ( n − a b ) ( q − 1 ) b . V_\lambda(r,n,q^m)
=
\sum_{a=0}^{\min\{n,\lfloor r/\lambda\rfloor\}}
\binom{n}{a}(q^m-q)^a
\sum_{b=0}^{\min\{n-a,\lfloor r-\lambda a\rfloor\}}
\binom{n-a}{b}(q-1)^b. V λ ( r , n , q m ) = a = 0 ∑ m i n { n , ⌊ r / λ ⌋} ( a n ) ( q m − q ) a b = 0 ∑ m i n { n − a , ⌊ r − λa ⌋} ( b n − a ) ( q − 1 ) b .
Proof. Let x ∈ F q m n x\in\mathbb{F}_{q^m}^{n} x ∈ F q m n have exactly a a a coordinates in F q m ∖ F q \mathbb{F}_{q^m}\setminus\mathbb{F}_{q} F q m ∖ F q and b b b nonzero coordinates in F q \mathbb{F}_{q} F q , thus wt λ ( x ) = λ a + b \operatorname{wt}_{\lambda}(x)=\lambda a+b wt λ ( x ) = λa + b . For fixed a a a and b b b , there are
( n a ) ( q m − q ) a ( n − a b ) ( q − 1 ) b \binom{n}{a}(q^m-q)^a\binom{n-a}{b}(q-1)^b ( a n ) ( q m − q ) a ( b n − a ) ( q − 1 ) b
such vectors. Summing over all a , b a,b a , b satisfying λ a + b ≤ r \lambda a+b\le r λa + b ≤ r gives the claim. □
In [7 ] it was observed that the λ \lambda λ -subfield metric is translation invariant, that is, the cardinality of a ball of fixed radius is independent of its center.
As we will also study codes attaining the Plotkin-type bound in the λ \lambda λ -subfield metric from [7 ] and derive analogues of the Elias and Griesmer bounds, we briefly recall their classical statements in the Hamming metric.
Theorem 9 (Plotkin bound). Let C C C be a [ n , k ] q m [n,k]_{q^m} [ n , k ] q m linear code with minimum Hamming distance d H d_H d H . Then
d H ≤ n q m k q m k − 1 ( 1 − 1 q m ) . d_H\le\frac{nq^{mk}}{q^{mk}-1}\left(1-\frac{1}{q^m}\right). d H ≤ q mk − 1 n q mk ( 1 − q m 1 ) .
Wood showed in [15 ] that all constant Hamming weight codes, i.e., codes attaining this Plotkin bound, are r r r fold repetitions of simplex codes (that is we simply repeat each coordinate r r r times).
Theorem 10 (Griesmer bound). Let C C C be an [ n , k ] q m [n,k]_{q^m} [ n , k ] q m linear code with minimum Hamming distance d H d_H d H . Then
n ≥ ∑ i = 0 k − 1 ⌈ d H q m i ⌉ n \ge\sum_{i=0}^{k-1} \left\lceil\frac{d_H}{q^{mi}} \right\rceil n ≥ i = 0 ∑ k − 1 ⌈ q mi d H ⌉
And finally, having established a Johnson bound, one can also obtain an Elias-Bassalygo bound:
Theorem 11 (Elias-Bassalygo bound). Let C ⊆ F q m n C \subseteq\mathbb{F}_{q^m}^n C ⊆ F q m n be a linear code with minimum Hamming distance d H d_H d H and let 0 ≤ r ≤ n ( 1 − 1 / q m ) 0 \le r \le n(1-1/q^m) 0 ≤ r ≤ n ( 1 − 1/ q m ) satisfy r 2 − 2 n r + d H n 1 − 1 / q m > 0 r^2-2nr+\frac{d_H n}{1-1/q^m}>0 r 2 − 2 n r + 1 − 1/ q m d H n > 0 . Then
∣ C ∣ ≤ q m n V H ( r , n , q m ) d H d H − 2 r + r 2 n ( 1 − 1 / q m ) |C| \le\frac{q^{mn}}{V_H(r,n,q^m)} \frac{d_H}{d_H-2r+\frac{r^2}{n(1-1/q^m)}} ∣ C ∣ ≤ V H ( r , n , q m ) q mn d H − 2 r + n ( 1 − 1/ q m ) r 2 d H where
V H ( r , n , q m ) = ∑ i = 0 r ( n i ) ( q m − 1 ) i V_H(r,n,q^m)=\sum_{i=0}^{r}\binom{n}{i}(q^m-1)^i V H ( r , n , q m ) = i = 0 ∑ r ( i n ) ( q m − 1 ) i denotes the volume of a Hamming ball of radius $r.
Finally, we briefly recall the Johnson bound, which provides a guaranteed list-decoding radius. In the unique decoding setting we need the balls around the codewords of radius t t t to be disjoint in order to be able to assign every received word to at most one closest codeword. On the other hand, in the list decoding setting, we consider balls of larger radius than t t t and ask: how large can the decoding radius be while keeping the number of closest codewords to a received vector polynomial?
Definition 12. Let C C C be an [ n , k ] q m [n,k]_{q^m} [ n , k ] q m linear code. We say that C C C is ( w , L ) (w,L) ( w , L ) -list decodable if for all y ∈ F q m n y \in\mathbb{F}_{q^m}^n y ∈ F q m n we have
∣ { c ∈ C ∣ d H ( y , c ) ≤ w } ∣ ≤ L . \left|\{c \in C \mid d_H(y,c) \le w\}\right| \le L. ∣ { c ∈ C ∣ d H ( y , c ) ≤ w } ∣ ≤ L .
In the Hamming metric, the following bound gives a decoding radius up to which the list size remains polynomial:
Definition 13 (Johnson radius). Let d , n d,n d , n be positive integers with d ≤ n d \le n d ≤ n . The Johnson radius is given by
J ( n , d ) = n ( 1 − 1 − d n ) = n − n ( n − d ) . J(n,d)=n\left(1-\sqrt{1-\frac{d}{n}}\right)=n-\sqrt{n(n-d)}. J ( n , d ) = n ( 1 − 1 − n d ) = n − n ( n − d ) .
Corollary 14. Let C C C be an [ n , k ] q m [n,k]_{q^m} [ n , k ] q m linear code with minimum Hamming distance d H d_H d H and let w < J ( n , d H ) w<J(n,d_H) w < J ( n , d H ) . Then C C C is ( w , L ) (w,L) ( w , L ) -list decodable with
L ≤ d H − w d H − 2 w + w 2 n . L \le\frac{d_H-w}{d_H-2w+\frac{w^2}{n}}. L ≤ d H − 2 w + n w 2 d H − w .
There also exists a q q q -ary version of this bound, which will come in handy for our comparisons:
Theorem 15. Let C C C be a [ n , k ] q m [n,k]_{q^{m}} [ n , k ] q m (not necessarily linear) code with minimum Hamming distance d H d_H d H . Then C C C is ( w , q m d H n ) (w,q^{m}d_Hn) ( w , q m d H n ) -list decodable, if
w < J q m ( n , d H ) = n q m − 1 q m ( 1 − 1 − q m q m − 1 d H n ) . w < J_{q^{m}}(n,d_H) = n\frac{q^{m}-1}{q^{m}}\left(1-\sqrt{1-\frac{q^{m}}{q^{m}-1}\frac{d_H}{n}}\right). w < J q m ( n , d H ) = n q m q m − 1 ( 1 − 1 − q m − 1 q m n d H ) .
In contrast, no analogous Johnson-type result is known for the rank metric. In fact, rank-metric codes may have exponential list size as soon as we go beyond half the minimum distance [14 ] .
One of the goals of this paper is to investigate to what extent Johnson-type arguments can be transferred to the λ \lambda λ -subfield metric.
Maximum λ \lambda λ -Subfield Distance Codes
The Singleton bound is one of the most fundamental bounds in coding theory. Codes attaining the Singleton bound with equality are of particular interest, since they maximize the minimum distance among all codes with the same length and dimension. In the Hamming metric and the rank metric this leads to the well-studied classes of MDS and MRD codes, respectively. In the λ \lambda λ -subfield metric, the corresponding extremal objects are the Maximum λ \lambda λ -Subfield Distance (Mλ \lambda λ D) codes, first introduced in [7 ] .
In this section, we investigate structural properties of linear and sublinear Mλ \lambda λ D codes. We derive restrictions on their parameters, compare Mλ \lambda λ D codes for different values of λ \lambda λ , and establish connections to MDS and MRD codes.
Linear MD codes
3.1. Linear Mλ \lambda λ D codes. Recall that a [ n , k ] q m [n,k]_{q^{m}} [ n , k ] q m linear code C C C is called a Mλ \lambda λ D code, if it attains the bound in Theorem 6, i.e., if d λ ( C ) = λ ( n − k ) + 1 d_{\lambda}(C)=\lambda(n-k)+1 d λ ( C ) = λ ( n − k ) + 1 .
The following result compares the Mλ \lambda λ D property for different values of λ \lambda λ .
Theorem 16. Let C C C be an [ n , k ] q m [n,k]_{q^{m}} [ n , k ] q m linear code and let λ 1 , λ 2 ≥ 1 \lambda_1,\lambda_2\geq1 λ 1 , λ 2 ≥ 1 be real numbers. Then the following hold:
(i) if λ 1 ≥ λ 2 \lambda_1\geq\lambda_2 λ 1 ≥ λ 2 and C C C is Mλ 1 \lambda_1 λ 1 D, then C C C is Mλ 2 \lambda_2 λ 2 D,
(ii) if λ 2 ≥ λ 1 ≥ n \lambda_2\geq\lambda_1\geq n λ 2 ≥ λ 1 ≥ n and C C C is Mλ 1 \lambda_1 λ 1 D, then C C C is Mλ 2 \lambda_2 λ 2 D.
Proof. Let us start with some notation. For a nonzero codeword c c c of C C C , we denote by a ( c ) a(c) a ( c ) the number of nonzero coordinates of c c c outside F q \mathbb{F}_q F q and by b ( c ) b(c) b ( c ) the number of nonzero coordinates of c c c contained in F q \mathbb{F}_q F q , that is: wt λ ( c ) = λ a ( c ) + b ( c ) \operatorname{wt}_{\lambda}(c)=\lambda a(c)+b(c) wt λ ( c ) = λa ( c ) + b ( c ) .
For (i), we assume that C C C is Mλ 1 \lambda_1 λ 1 D but not Mλ 2 \lambda_2 λ 2 D. As C C C is not Mλ 2 \lambda_2 λ 2 D, there must exist some c ~ ∈ C ∖ { 0 } \tilde{c}\in C\setminus\{0\} c ~ ∈ C ∖ { 0 } with wt λ 2 ( c ~ ) < λ 2 ( n − k ) + 1 \operatorname{wt}_{\lambda_2}(\tilde{c})<\lambda_2(n-k)+1 wt λ 2 ( c ~ ) < λ 2 ( n − k ) + 1 . Following our notation, we write a = a ( c ~ ) a=a(\tilde{c}) a = a ( c ~ ) and b = b ( c ~ ) b=b(\tilde{c}) b = b ( c ~ ) . If b = 0 b=0 b = 0 , then wt λ 2 ( c ~ ) = λ 2 a < λ 2 ( n − k ) + 1 \operatorname{wt}_{\lambda_2}(\tilde{c})=\lambda_2a<\lambda_2(n-k)+1 wt λ 2 ( c ~ ) = λ 2 a < λ 2 ( n − k ) + 1 and hence a ≤ n − k a\leq n-k a ≤ n − k . Similarly, in the λ 1 \lambda_1 λ 1 -subfield metric, we get that wt λ 1 ( c ~ ) = λ 1 a ≤ λ 1 ( n − k ) < λ 1 ( n − k ) + 1 \operatorname{wt}_{\lambda_1}(\tilde{c})=\lambda_1a\leq\lambda_1(n-k)<\lambda_1(n-k)+1 wt λ 1 ( c ~ ) = λ 1 a ≤ λ 1 ( n − k ) < λ 1 ( n − k ) + 1 , contradicting the Mλ 1 \lambda_1 λ 1 D property. If b ≥ 1 b\geq1 b ≥ 1 , we can upper bound the λ 1 \lambda_1 λ 1 -weight of c ~ \tilde{c} c ~ as
wt λ 1 ( c ~ ) = λ 1 a + b = λ 1 λ 2 ( λ 2 a + b ) + b ( 1 − λ 1 λ 2 ) < λ 1 λ 2 ( λ 2 ( n − k ) + 1 ) + b ( 1 − λ 1 λ 2 ) = λ 1 ( n − k ) + λ 1 λ 2 + b ( 1 − λ 1 λ 2 ) ≤ λ 1 ( n − k ) + λ 1 λ 2 + ( 1 − λ 1 λ 2 ) . \begin{aligned}
\operatorname{wt}_{\lambda_1}(\tilde{c}) &= \lambda_1a+b = \frac{\lambda_1}{\lambda_2}(\lambda_2a+b)+b\left(1-\frac{\lambda_1}{\lambda_2}\right) \\
&< \frac{\lambda_1}{\lambda_2}(\lambda_2(n-k)+1)+b\left(1-\frac{\lambda_1}{\lambda_2}\right) \\
&= \lambda_1(n-k)+\frac{\lambda_1}{\lambda_2}+b\left(1-\frac{\lambda_1}{\lambda_2}\right) \\
&\leq\lambda_1(n-k)+\frac{\lambda_1}{\lambda_2}+\left(1-\frac{\lambda_1}{\lambda_2}\right).
\end{aligned} wt λ 1 ( c ~ ) = λ 1 a + b = λ 2 λ 1 ( λ 2 a + b ) + b ( 1 − λ 2 λ 1 ) < λ 2 λ 1 ( λ 2 ( n − k ) + 1 ) + b ( 1 − λ 2 λ 1 ) = λ 1 ( n − k ) + λ 2 λ 1 + b ( 1 − λ 2 λ 1 ) ≤ λ 1 ( n − k ) + λ 2 λ 1 + ( 1 − λ 2 λ 1 ) .
::: As we assumed that λ 1 ≥ λ 2 \lambda_1 \ge\lambda_2 λ 1 ≥ λ 2 , we get that 1 − λ 1 / λ 2 ≤ 0 1-\lambda_1/\lambda_2 \le0 1 − λ 1 / λ 2 ≤ 0 and thus wt λ 1 ( c ~ ) ≤ λ 1 ( n − k ) + 1 \operatorname{wt}_{\lambda_1}(\widetilde{c}) \le\lambda_1(n-k)+1 wt λ 1 ( c ) ≤ λ 1 ( n − k ) + 1 , which again contradicts that C \mathcal{C} C is M λ 1 D M_{\lambda_1}D M λ 1 D .
For (ii), we assume that C \mathcal{C} C is M λ 1 D M_{\lambda_1}D M λ 1 D , that is for all nonzero codewords c ∈ C c \in\mathcal{C} c ∈ C we have that wt λ 1 ( c ) ≥ λ 1 ( n − k ) + 1 \operatorname{wt}_{\lambda_1}(c) \ge\lambda_1(n-k)+1 wt λ 1 ( c ) ≥ λ 1 ( n − k ) + 1 . We first show that every nonzero codeword c ∈ C c \in\mathcal{C} c ∈ C satisfies a ( c ) ≥ n − k a(c) \ge n-k a ( c ) ≥ n − k . Indeed, if a ( c ) ≤ n − k − 1 a(c) \le n-k-1 a ( c ) ≤ n − k − 1 , then, since b ( c ) ≤ n b(c) \le n b ( c ) ≤ n , we get that
wt λ 1 ( c ) = λ 1 a ( c ) + b ( c ) ≤ λ 1 ( n − k − 1 ) + n ≤ λ 1 ( n − k ) , \operatorname{wt}_{\lambda_1}(c)=\lambda_1a(c)+b(c)\le\lambda_1(n-k-1)+n\le\lambda_1(n-k), wt λ 1 ( c ) = λ 1 a ( c ) + b ( c ) ≤ λ 1 ( n − k − 1 ) + n ≤ λ 1 ( n − k ) ,
contradicting that C \mathcal{C} C is M λ 1 D M_{\lambda_1}D M λ 1 D .
If a ( c ) = n − k a(c)=n-k a ( c ) = n − k , then the M λ 1 D M_{\lambda_1}D M λ 1 D property forces b ( c ) ≥ 1 b(c)\ge1 b ( c ) ≥ 1 , as
λ 1 ( n − k ) + 1 ≤ wt λ 1 ( c ) = λ 1 a ( c ) + b ( c ) = λ 1 ( n − k ) + b ( c ) . \lambda_1(n-k)+1\le\operatorname{wt}_{\lambda_1}(c)=\lambda_1a(c)+b(c)=\lambda_1(n-k)+b(c). λ 1 ( n − k ) + 1 ≤ wt λ 1 ( c ) = λ 1 a ( c ) + b ( c ) = λ 1 ( n − k ) + b ( c ) .
Hence, for the λ 2 \lambda_2 λ 2 -subfield weight, we get that
wt λ 2 ( c ) = λ 2 ( n − k ) + b ( c ) ≥ λ 2 ( n − k ) + 1. \operatorname{wt}_{\lambda_2}(c)=\lambda_2(n-k)+b(c)\ge\lambda_2(n-k)+1. wt λ 2 ( c ) = λ 2 ( n − k ) + b ( c ) ≥ λ 2 ( n − k ) + 1.
Similarly, if a ( c ) > n − k a(c)>n-k a ( c ) > n − k , then a ( c ) ≥ n − k + 1 a(c)\ge n-k+1 a ( c ) ≥ n − k + 1 , and therefore
wt λ 2 ( c ) = λ 2 a ( c ) + b ( c ) ≥ λ 2 a ( c ) ≥ λ 2 ( n − k + 1 ) ≥ λ 2 ( n − k ) + 1. \operatorname{wt}_{\lambda_2}(c)=\lambda_2a(c)+b(c)\ge\lambda_2a(c)\ge\lambda_2(n-k+1)\ge\lambda_2(n-k)+1. wt λ 2 ( c ) = λ 2 a ( c ) + b ( c ) ≥ λ 2 a ( c ) ≥ λ 2 ( n − k + 1 ) ≥ λ 2 ( n − k ) + 1.
Thus every nonzero codeword has λ 2 \lambda_2 λ 2 -subfield weight at least λ 2 ( n − k ) + 1 \lambda_2(n-k)+1 λ 2 ( n − k ) + 1 , which implies that C \mathcal{C} C is M λ 2 D M_{\lambda_2}D M λ 2 D . □
The converse of Theorem 16(i) is, however, false in general.
Example 17. Let q = m = 2 q=m=2 q = m = 2 and let F 4 = F 2 ( α ) \mathbb{F}_4=\mathbb{F}_2(\alpha) F 4 = F 2 ( α ) with α 2 = α + 1 \alpha^2=\alpha+1 α 2 = α + 1 . Consider the [ 3 , 2 ] q m [3,2]_{q^m} [ 3 , 2 ] q m code generated by
G = ( 1 0 α 0 1 α + 1 ) G=\begin{pmatrix}1&0&\alpha\\0&1&\alpha+1\end{pmatrix} G = ( 1 0 0 1 α α + 1 )
For λ 1 = 2 \lambda_1=2 λ 1 = 2 , the minimum λ 1 \lambda_1 λ 1 -subfield distance is d λ 1 = 3 d_{\lambda_1}=3 d λ 1 = 3 , and as d λ 1 = 3 = λ 1 ( n − k ) + 1 = 2 ⋅ 1 + 1 d_{\lambda_1}=3=\lambda_1(n-k)+1=2\cdot1+1 d λ 1 = 3 = λ 1 ( n − k ) + 1 = 2 ⋅ 1 + 1 , the code is M λ 1 D M_{\lambda_1}D M λ 1 D . However, it is not M λ 2 D M_{\lambda_2}D M λ 2 D for λ 2 = 3 \lambda_2=3 λ 2 = 3 , since the codeword c ~ = ( 1 , 1 , 1 ) \widetilde{c}=(1,1,1) c = ( 1 , 1 , 1 ) has wt λ 2 ( c ~ ) = 3 < 4 = λ 2 ( n − k ) + 1 \operatorname{wt}_{\lambda_2}(\widetilde{c})=3<4=\lambda_2(n-k)+1 wt λ 2 ( c ) = 3 < 4 = λ 2 ( n − k ) + 1 .
The next result gives a stronger parameter restriction for a fixed λ > 1 \lambda>1 λ > 1 .
Theorem 18. Let λ > 1 \lambda>1 λ > 1 be a real number. If ( q m − 1 ) / ( q − 1 ) ≤ n − k (q^m-1)/(q-1)\le n-k ( q m − 1 ) / ( q − 1 ) ≤ n − k , then no linear M λ D M_\lambda D M λ D code exists.
Proof. Let N = ( q m − 1 ) / ( q − 1 ) N=(q^m-1)/(q-1) N = ( q m − 1 ) / ( q − 1 ) and choose representatives a 1 , … , a N a_1,\ldots,a_N a 1 , … , a N for the quotient F q m × / F q × \mathbb{F}_{q^m}^{\times}/\mathbb{F}_q^{\times} F q m × / F q × , where we set a 1 = 1 a_1=1 a 1 = 1 .
Let C \mathcal{C} C be an [ n , k ] q m [n,k]_{q^m} [ n , k ] q m linear code. Up to permutations of the coordinates, we may assume that C \mathcal{C} C has a generator matrix of the form G = ( I d k A ) G=(I d_k\ A) G = ( I d k A ) , for some A ∈ F q m k × ( n − k ) A\in\mathbb{F}_{q^m}^{k\times(n-k)} A ∈ F q m k × ( n − k ) . Let us write the first row as
c = ( 1 , 0 , … , 0 , b 1 , … , b n − k ) . c=(1,0,\ldots,0,b_1,\ldots,b_{n-k}). c = ( 1 , 0 , … , 0 , b 1 , … , b n − k ) .
If one of the entries b j b_j b j is zero, with j ∈ { 1 , … , n − k } j\in\{1,\ldots,n-k\} j ∈ { 1 , … , n − k } , then wt λ ( c ) ≤ 1 + λ ( n − k − 1 ) < λ ( n − k ) + 1 \operatorname{wt}_{\lambda}(c)\le1+\lambda(n-k-1)<\lambda(n-k)+1 wt λ ( c ) ≤ 1 + λ ( n − k − 1 ) < λ ( n − k ) + 1 , which implies that C \mathcal{C} C is not M λ D M_\lambda D M λ D .
We can thus assume that b j ≠ 0 b_j\ne0 b j = 0 for all j ∈ { 1 , … , n − k } j\in\{1,\ldots,n-k\} j ∈ { 1 , … , n − k } . Similarly, if some b j b_j b j lies in F q × \mathbb{F}_q^\times F q × , then
wt λ ( c ) ≤ λ ( n − k − 1 ) + 2 < λ ( n − k ) + 1 , \operatorname{wt}_{\lambda}(c)\le\lambda(n-k-1)+2<\lambda(n-k)+1, wt λ ( c ) ≤ λ ( n − k − 1 ) + 2 < λ ( n − k ) + 1 ,
again contradicting the M λ D M_\lambda D M λ D property.
It remains to assume that all b j b_j b j lie outside F q × \mathbb{F}_q^\times F q × . Note that we have n − k ≥ N n-k\ge N n − k ≥ N entries b j b_j b j , while there are only N − 1 N-1 N − 1 nontrivial cosets of F q × \mathbb{F}_q^\times F q × in F q m × \mathbb{F}_{q^m}^\times F q m × . Thus, the pigeonhole principle implies that there exist two indices j 1 , j 2 ∈ { 1 , … , n − k } j_1,j_2\in\{1,\ldots,n-k\} j 1 , j 2 ∈ { 1 , … , n − k } with j 1 ≠ j 2 j_1\ne j_2 j 1 = j 2 such that $b_{j_1} and b j 2 b_{j_2} b j 2 lie in the same coset. Thus, there exists an element a ∈ F q m × a \in\mathbb{F}_{q^m}^{\times} a ∈ F q m × such that both a − 1 b j 1 , a − 1 b j 2 ∈ F q × a^{-1}b_{j_1},a^{-1}b_{j_2} \in\mathbb{F}_q^{\times} a − 1 b j 1 , a − 1 b j 2 ∈ F q × . We can now consider the codeword a − 1 c a^{-1}c a − 1 c , given by
a − 1 c = ( a − 1 , 0 , … , 0 , a − 1 b 1 , … , a − 1 b n − k ) . a^{-1}c=(a^{-1},0,\ldots,0,a^{-1}b_1,\ldots,a^{-1}b_{n-k}). a − 1 c = ( a − 1 , 0 , … , 0 , a − 1 b 1 , … , a − 1 b n − k ) .
Thus, a − 1 c a^{-1}c a − 1 c has one coordinate (being a − 1 a^{-1} a − 1 ) of weight at most λ \lambda λ , two coordinates of weight 1, namely a − 1 b j 1 a^{-1}b_{j_1} a − 1 b j 1 and a − 1 b j 2 a^{-1}b_{j_2} a − 1 b j 2 , and at most n − k − 2 n-k-2 n − k − 2 remaining coordinates of weight at most λ \lambda λ . This implies that
wt λ ( a − 1 c ) ≤ λ + 2 + λ ( n − k − 2 ) = λ ( n − k ) + 2 − λ < λ ( n − k ) + 1 , \operatorname{wt}_{\lambda}(a^{-1}c)\leq\lambda+2+\lambda(n-k-2)=\lambda(n-k)+2-\lambda<\lambda(n-k)+1, wt λ ( a − 1 c ) ≤ λ + 2 + λ ( n − k − 2 ) = λ ( n − k ) + 2 − λ < λ ( n − k ) + 1 ,
which contradicts the M λ D M\lambda D M λ D property. □
Unlike for MDS and MRD codes, the M λ D M\lambda D M λ D property is not preserved by duality.
Example 19. Let q = m = 2 q=m=2 q = m = 2 and let F 4 = F 2 ( α ) \mathbb{F}_4=\mathbb{F}_2(\alpha) F 4 = F 2 ( α ) with α 2 = α + 1 \alpha^2=\alpha+1 α 2 = α + 1 . Consider the [ 3 , 1 ] q m [3,1]_{q^m} [ 3 , 1 ] q m code generated by
G = ( 1 α 1 + α ) . G=(1\quad\alpha\quad1+\alpha). G = ( 1 α 1 + α ) . Every nonzero codeword of C C C has λ \lambda λ -subfield weight 2 λ + 1 = λ ( n − k ) + 1 = λ ( 3 − 1 ) + 1 2\lambda+1=\lambda(n-k)+1=\lambda(3-1)+1 2 λ + 1 = λ ( n − k ) + 1 = λ ( 3 − 1 ) + 1 , so C C C is M λ D M\lambda D M λ D for every λ ≥ 1 \lambda\geq1 λ ≥ 1 .
However, the dual code C ⊥ C^\perp C ⊥ has dimension k ′ = n − k = 2 k'=n-k=2 k ′ = n − k = 2 , and ( 1 , 1 , 1 ) ∈ C ⊥ (1,1,1)\in C^\perp ( 1 , 1 , 1 ) ∈ C ⊥ . Hence d λ ( C ⊥ ) ≤ 3 d_\lambda(C^\perp)\leq3 d λ ( C ⊥ ) ≤ 3 . For λ > 2 \lambda>2 λ > 2 , this gives
d λ ( C ⊥ ) ≤ 3 < λ + 1 = λ ( n − k ′ ) + 1 = λ ( 3 − 2 ) + 1 , d_\lambda(C^\perp)\leq3<\lambda+1=\lambda(n-k')+1=\lambda(3-2)+1, d λ ( C ⊥ ) ≤ 3 < λ + 1 = λ ( n − k ′ ) + 1 = λ ( 3 − 2 ) + 1 , hence C ⊥ C^\perp C ⊥ is not M λ D M\lambda D M λ D .
Further comparisons with MDS and MRD codes are discussed in § 3.3 .
Sublinear M λ D M\lambda D M λ D codes
We now extend the notion of M λ D M\lambda D M λ D codes to codes that are linear over a proper subfield.
Recall that we fix m = ℓ s m=\ell s m = ℓ s and let C ⊆ F q m n C\subseteq\mathbb{F}_{q^m}^n C ⊆ F q m n be an [ n , k ] q ℓ / q m [n,k]_{q^\ell/q^m} [ n , k ] q ℓ / q m code.
In case of a sublinear code, we can generalize the Singleton-like bound of Theorem 5 to:
Corollary 20. Let λ ≥ 1 \lambda\geq1 λ ≥ 1 be a real number. Let C ⊆ F q m n C\subseteq\mathbb{F}_{q^m}^n C ⊆ F q m n be an [ n , k ] q ℓ / q m [n,k]_{q^\ell/q^m} [ n , k ] q ℓ / q m linear code with minimum λ \lambda λ -subfield distance d λ d_\lambda d λ . Then
⌊ d λ − 1 λ ⌋ ≤ n − ⌈ ℓ k m ⌉ . \left\lfloor\frac{d_\lambda-1}{\lambda}\right\rfloor\leq n-\left\lceil\frac{\ell k}{m}\right\rceil. ⌊ λ d λ − 1 ⌋ ≤ n − ⌈ m ℓ k ⌉ .
This follows directly from Theorem 5 , as C C C is an F q ℓ \mathbb{F}_{q^\ell} F q ℓ -vector space of dimension k k k and we have ∣ C ∣ = ( q ℓ ) k = ( q m ) k / s |C|=(q^\ell)^k=(q^m)^{k/s} ∣ C ∣ = ( q ℓ ) k = ( q m ) k / s .
Codes attaining this bound are called sublinear M λ D M\lambda D M λ D codes.
Unlike the F q m \mathbb{F}_{q^m} F q m -linear case, where we could tighten the Singleton-like bound to Theorem 6 , we cannot tighten the bound further, e.g. one might be tempted to assume that
d λ ≤ λ ( n − ⌈ k s ⌉ ) + 1. (1) d_\lambda\leq\lambda\left(n-\left\lceil\frac{k}{s}\right\rceil\right)+1. \tag*{(1)} d λ ≤ λ ( n − ⌈ s k ⌉ ) + 1. (1)
However, this quantity is not an upper bound on the minimum λ \lambda λ -subfield distance, as the following example shows:
Example 21. Let q = m = 2 q=m=2 q = m = 2 and let F 4 = F 2 ( α ) \mathbb{F}_4=\mathbb{F}_2(\alpha) F 4 = F 2 ( α ) with α 2 = α + 1 \alpha^2=\alpha+1 α 2 = α + 1 . Let us consider the F 2 \mathbb{F}_2 F 2 -linear code generated by
G = ( α α α ) . G=(\alpha\quad\alpha\quad\alpha). G = ( α α α ) . :::`
Then C C C is a [ 3 , 1 , 1 ] 4 [3,1,1]_{4} [ 3 , 1 , 1 ] 4 code with d λ ( C ) = 3 λ d_{\lambda}(C)=3\lambda d λ ( C ) = 3 λ . Since
3 λ > 2 λ + 1 = λ ( 3 − ⌈ 1 2 ⌉ ) + 1 3\lambda> 2\lambda+1=\lambda\left(3-\left\lceil\frac{1}{2}\right\rceil\right)+1 3 λ > 2 λ + 1 = λ ( 3 − ⌈ 2 1 ⌉ ) + 1
for every λ > 1 \lambda>1 λ > 1 , Equation (1) fails.
Nevertheless, Equation (1) completely characterizes sublinear M λ D \mathrm{M}_{\lambda}\mathrm{D} M λ D codes.
Corollary 22. Let λ ≥ 1 \lambda\geq1 λ ≥ 1 be a real number. An [ n , k ] q ℓ / q m [n,k]_{q^{\ell}/q^{m}} [ n , k ] q ℓ / q m linear code C C C is sublinear M λ D \mathrm{M}_{\lambda}\mathrm{D} M λ D if and only if
d λ ( C ) ≥ λ ( n − ⌈ k s ⌉ ) + 1. d_{\lambda}(C)\geq\lambda\left(n-\left\lceil\frac{k}{s}\right\rceil\right)+1. d λ ( C ) ≥ λ ( n − ⌈ s k ⌉ ) + 1.
By Corollary 20,
⌊ d λ − 1 λ ⌋ ≤ n − ⌈ k s ⌉ , \left\lfloor\frac{d_{\lambda}-1}{\lambda}\right\rfloor\leq n-\left\lceil\frac{k}{s}\right\rceil, ⌊ λ d λ − 1 ⌋ ≤ n − ⌈ s k ⌉ ,
and equality holds if
d λ ≥ λ ( n − ⌈ k s ⌉ ) + 1. d_{\lambda}\geq\lambda\left(n-\left\lceil\frac{k}{s}\right\rceil\right)+1. d λ ≥ λ ( n − ⌈ s k ⌉ ) + 1.
Many structural results from the linear setting extend directly, for example:
Corollary 23. Let λ 1 , λ 2 ≥ 1 \lambda_{1},\lambda_{2}\geq1 λ 1 , λ 2 ≥ 1 be real numbers.
(1) If λ 1 ≥ λ 2 \lambda_{1}\geq\lambda_{2} λ 1 ≥ λ 2 and C C C is a sublinear M λ 1 D \mathrm{M}_{\lambda_{1}}\mathrm{D} M λ 1 D code, then C C C is a sublinear M λ 2 D \mathrm{M}_{\lambda_{2}}\mathrm{D} M λ 2 D code.
(2) If λ 2 ≥ λ 1 ≥ n \lambda_{2}\geq\lambda_{1}\geq n λ 2 ≥ λ 1 ≥ n and C C C is a sublinear M λ 1 D \mathrm{M}_{\lambda_{1}}\mathrm{D} M λ 1 D code, then C C C is a sublinear M λ 2 D \mathrm{M}_{\lambda_{2}}\mathrm{D} M λ 2 D code.
The proof follows verbatim from Theorem 16 by replacing n − k n-k n − k with n − ⌈ k s ⌉ n-\left\lceil\frac{k}{s}\right\rceil n − ⌈ s k ⌉ . Finally, duality behaves similarly to the linear case due to the counterexample 19.
Corollary 24. Let C C C be a (sub-)linear code of length n n n and let λ = n + 1 \lambda=n+1 λ = n + 1 . If C C C is an M λ D \mathrm{M}_{\lambda}\mathrm{D} M λ D code, then C C C is an M λ ′ D \mathrm{M}_{\lambda'}\mathrm{D} M λ ′ D code for every real number λ ′ ≥ 1 \lambda'\geq1 λ ′ ≥ 1 .
Proof. If λ ′ ≤ n + 1 \lambda'\leq n+1 λ ′ ≤ n + 1 , the claim follows from Corollary 23(i) and if λ ′ ≥ n + 1 \lambda'\geq n+1 λ ′ ≥ n + 1 , then λ ′ ≥ n \lambda'\geq n λ ′ ≥ n , and the claim follows from Corollary 23(ii). □ \square □
Comparison with MDS and MRD Codes
The λ \lambda λ -subfield metric shares several features with both the Hamming metric and the rank metric. In this section, we compare M λ D \mathrm{M}_{\lambda}\mathrm{D} M λ D codes with MDS and MRD codes. In particular, we show that for m ≥ n m\geq n m ≥ n
{ M R D codes } ⊂ { M λ D codes } ⊂ { M D S codes } , \{\mathrm{MRD}\text{ codes}\}\subset\{\mathrm{M}_{\lambda}\mathrm{D}\text{ codes}\}\subset\{\mathrm{MDS}\text{ codes}\}, { MRD codes } ⊂ { M λ D codes } ⊂ { MDS codes } ,
where both inclusions are strict in general.
We first compare M λ D \mathrm{M}_{\lambda}\mathrm{D} M λ D codes with MDS codes.
Theorem 25. Let λ ≥ 1 \lambda\geq1 λ ≥ 1 be a real number. Let C ⊆ F q m n C\subseteq\mathbb{F}_{q^{m}}^{n} C ⊆ F q m n be a linear M λ D \mathrm{M}_{\lambda}\mathrm{D} M λ D code. Then C C C is MDS. Moreover,
d H ( C ) = d λ ( C ) − 1 λ + 1. d_{H}(C)=\frac{d_{\lambda}(C)-1}{\lambda}+1. d H ( C ) = λ d λ ( C ) − 1 + 1.
Proof. Since C C C is M λ D \mathrm{M}_{\lambda}\mathrm{D} M λ D , we have that d λ ( C ) = λ ( n − k ) + 1 d_{\lambda}(C)=\lambda(n-k)+1 d λ ( C ) = λ ( n − k ) + 1 . Suppose there exists a nonzero codeword c ∈ C c\in C c ∈ C with wt H ( c ) ≤ n − k \operatorname{wt}_{H}(c)\leq n-k wt H ( c ) ≤ n − k . Then wt λ ( c ) ≤ λ ( n − k ) \operatorname{wt}_{\lambda}(c)\leq\lambda(n-k) wt λ ( c ) ≤ λ ( n − k ) , contradicting the M λ D \mathrm{M}_{\lambda}\mathrm{D} M λ D property. Hence d H ( C ) ≥ n − k + 1 d_{H}(C)\geq n-k+1 d H ( C ) ≥ n − k + 1 and C C C is MDS. Substituting n − k = ( d λ ( C ) − 1 ) / λ n-k=(d_{\lambda}(C)-1)/\lambda n − k = ( d λ ( C ) − 1 ) / λ in d H ( C ) = n − k + 1 d_{H}(C)=n-k+1 d H ( C ) = n − k + 1 gives the claimed formula. □ \square □
The same relation also holds for sublinear codes.
Corollary 26. Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a real number. Let C ⊆ F q m C \subseteq\mathbb{F}_{q^m} C ⊆ F q m be an [ n , k ] q ℓ / q m [n,k]_{q^\ell/q^m} [ n , k ] q ℓ / q m linear M λ D M\lambda D M λ D code with parameters such that s = m / ℓ s=m/\ell s = m / ℓ divides k k k . Then C C C is a sublinear MDS code.
Thus, every M λ D M\lambda D M λ D code is MDS. The converse is false in general, since the M λ D M\lambda D M λ D property is not preserved under duality whereas the MDS property is. Hence the dual code of Example 19 is an example of MDS code, which is not M λ D M\lambda D M λ D .
On the other hand, the relation between M λ D M\lambda D M λ D and MRD codes depends on the extension degree m m m .
Theorem 27. Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a real number. Let C C C be a linear MRD code with m ≥ n m \ge n m ≥ n . Then C C C is M λ D M\lambda D M λ D .
Proof. Since C C C is MRD and m ≥ n m \ge n m ≥ n , we have that d R ( C ) = n − k + 1 d_R(C)=n-k+1 d R ( C ) = n − k + 1 . Hence every nonzero codeword of C C C contains at least n − k + 1 n-k+1 n − k + 1 F q \mathbb{F}_q F q -linearly independent entries. Thus, at least n − k n-k n − k entries lie outside F q \mathbb{F}_q F q and there is at least one additional nonzero entry. Therefore
wt λ ( c ) ≥ λ ( n − k ) + 1 \operatorname{wt}_{\lambda}(c) \ge\lambda(n-k)+1 wt λ ( c ) ≥ λ ( n − k ) + 1 for every nonzero codeword c ∈ C c \in C c ∈ C , and hence C C C is M λ D M\lambda D M λ D . □
As a consequence, Gabidulin codes [5 , 4 ] provide an infinite family of M λ D M\lambda D M λ D codes for m ≥ n m \ge n m ≥ n .
The corresponding implication also holds in the sublinear setting.
Corollary 28. Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a real number. Let C C C be a sublinear MRD code with m ≥ n m \ge n m ≥ n . Then C C C is a sublinear M λ D M\lambda D M λ D code.
However, the converse of Theorem 27 is false.
Example 29. Let F 16 = F 2 ( α ) \mathbb{F}_{16}=\mathbb{F}_2(\alpha) F 16 = F 2 ( α ) with α 4 = α + 1 \alpha^4=\alpha+1 α 4 = α + 1 . Consider the code C ⊆ F 2 4 4 C \subseteq\mathbb{F}_{2^4}^4 C ⊆ F 2 4 4 generated by
G = ( 1 0 α α + 1 0 1 α 2 α 2 + 1 ) . G=\begin{pmatrix}
1 & 0 & \alpha& \alpha+1 \\
0 & 1 & \alpha^2 & \alpha^2+1
\end{pmatrix}. G = ( 1 0 0 1 α α 2 α + 1 α 2 + 1 ) . Note that d λ ( C ) = 2 λ + 1 = λ ( n − k ) + 1 d_{\lambda}(C)=2\lambda+1=\lambda(n-k)+1 d λ ( C ) = 2 λ + 1 = λ ( n − k ) + 1 , and hence C C C is an M λ D M\lambda D M λ D code. However, d R ( C ) = 2 < n − k + 1 = 3 d_R(C)=2<n-k+1=3 d R ( C ) = 2 < n − k + 1 = 3 , and hence C C C is not MRD.
Note that in [7 Theorem 6.2] , a statement analogous to Theorem 27 was formulated without the assumption m ≥ n m \ge n m ≥ n . The next examples will show that this restriction is, however, necessary.
In fact, in the following we provide an example with m < n m<n m < n which is MRD but not M λ D M\lambda D M λ D , as well as an example, which is M λ D M\lambda D M λ D but not MRD.
Example 30. Consider F 8 = F 2 ( α ) \mathbb{F}_8=\mathbb{F}_2(\alpha) F 8 = F 2 ( α ) with α 3 = α + 1 \alpha^3=\alpha+1 α 3 = α + 1 and the [ 6 , 2 ] 8 [6,2]_8 [ 6 , 2 ] 8 code generated by
G = ( 1 0 1 α α 2 α 0 1 α 1 α α 2 ) . G=\begin{pmatrix}
1 & 0 & 1 & \alpha& \alpha^2 & \alpha\\
0 & 1 & \alpha& 1 & \alpha& \alpha^2
\end{pmatrix}. G = ( 1 0 0 1 1 α α 1 α 2 α α α 2 ) . This code has minimum distances d R = 3 d_R=3 d R = 3 and d λ = 2 λ + 2 d_{\lambda}=2\lambda+2 d λ = 2 λ + 2 . Thus, it is an MRD code, but not an M λ D M\lambda D M λ D code.
Example 31. Consider F 343 = F 7 ( α ) \mathbb{F}_{343}=\mathbb{F}_7(\alpha) F 343 = F 7 ( α ) with α 3 = α 2 + 3 \alpha^3=\alpha^2+3 α 3 = α 2 + 3 and the [ 6 , 2 ] 343 [6,2]_{343} [ 6 , 2 ] 343 code generated by
G = ( 1 0 α α + 1 α + 2 α + 3 0 1 α 2 α 2 + 2 α + 1 α 2 + 4 α + 4 α 2 + 6 α + 2 ) . G=\begin{pmatrix}
1 & 0 & \alpha& \alpha+1 & \alpha+2 & \alpha+3 \\
0 & 1 & \alpha^2 & \alpha^2+2\alpha+1 & \alpha^2+4\alpha+4 & \alpha^2+6\alpha+2
\end{pmatrix}. G = ( 1 0 0 1 α α 2 α + 1 α 2 + 2 α + 1 α + 2 α 2 + 4 α + 4 α + 3 α 2 + 6 α + 2 ) . This code has minimum distances d R = 2 d_R=2 d R = 2 and d λ = 4 λ + 1 d_{\lambda}=4\lambda+1 d λ = 4 λ + 1 . Thus, it is an M λ D M\lambda D M λ D code, but not an MRD code.
Density of MλD Codes
The existence of extremal codes is a classical topic in coding theory. Beyond existence, one may ask how frequently such codes occur among all codes with fixed parameters. This question has received considerable attention for MDS and MRD codes. It was shown that MDS codes are dense for q q q growing and sparse for n n n growing. The case of MRD codes is a bit more subtle, as we have to differentiate whether the codes are F q \mathbb{F}_q F q -linear or F q m \mathbb{F}_{q^m} F q m -linear. In [10 ] , it was shown that for F q m \mathbb{F}_{q^m} F q m -linear codes, MRD codes are dense for q q q growing and sparse for n n n growing. However, F q \mathbb{F}_q F q -linear MRD codes are neither dense nor sparse [1 , 2 , 6 , 9 ] .
In this section, we investigate the density of MλD codes. Following the framework developed for MDS and MRD codes in [8 ] , we study the proportion of MλD codes among all codes as either n n n or q q q grow. We consider both linear and sublinear (i.e., F q ℓ \mathbb{F}_{q^\ell} F q ℓ -linear) codes, where we also consider the density for ℓ \ell ℓ growing. We then compare the resulting behavior with the known asymptotic theory of MDS and MRD codes and compute the ratio of MλD codes within the set of MDS codes and the ratio of MRD codes within the set of MλD codes for q → ∞ q \to\infty q → ∞ .
Following the notation in [8 ] , let us denote the volume of the ball of radius r r r in F q m n \mathbb{F}_{q^m}^n F q m n by
V D ( r , n , q m ) = ∣ B D ( r , n , q m ) ∣ = ∣ { x ∈ F q m n ∣ d D ( x , 0 ) ≤ r } ∣ . V_D(r,n,q^m)=|B_D(r,n,q^m)|=\left|\left\{x\in\mathbb{F}_{q^m}^n\mid d_D(x,0)\le r\right\}\right|. V D ( r , n , q m ) = ∣ B D ( r , n , q m ) ∣ = { x ∈ F q m n ∣ d D ( x , 0 ) ≤ r } .
where D D D serves as a placeholder to describe a translation-invariant distance function on F q m n \mathbb{F}_{q^m}^n F q m n .
Definition 32 ([8 Definition 1.3] ). The density of F q ℓ \mathbb{F}_{q^\ell} F q ℓ -linear codes of minimum distance d D ( C ) d_D(C) d D ( C ) at least d d d is defined as
δ D ( d , S , n , ℓ , q m ) = ∣ { C ⊆ F q m n ∣ ∣ C ∣ = S , d D ( C ) ≥ d , C is F q ℓ -linear } ∣ ∣ { C ⊆ F q m n ∣ ∣ C ∣ = S , C is F q ℓ -linear } ∣ . \delta_D(d,S,n,\ell,q^m)=\frac{\left|\left\{C\subseteq\mathbb{F}_{q^m}^n\mid|C|=S,\ d_D(C)\ge d,\ C\text{ is }\mathbb{F}_{q^\ell}\text{-linear}\right\}\right|}{\left|\left\{C\subseteq\mathbb{F}_{q^m}^n\mid|C|=S,\ C\text{ is }\mathbb{F}_{q^\ell}\text{-linear}\right\}\right|}. δ D ( d , S , n , ℓ , q m ) = { C ⊆ F q m n ∣ ∣ C ∣ = S , C is F q ℓ -linear } { C ⊆ F q m n ∣ ∣ C ∣ = S , d D ( C ) ≥ d , C is F q ℓ -linear } .
The cardinality S = q ℓ k S=q^{\ell k} S = q ℓ k depends on the F q ℓ \mathbb{F}_{q^\ell} F q ℓ -dimension k k k of C C C .
Our goal is to understand the limiting behavior of these proportions as one of the parameters tends to infinity while the remaining parameters are fixed.
The asymptotic behavior turns out to depend strongly on the parameter regime under consideration.
The regime n → ∞ n \to\infty n → ∞
We begin with the asymptotic behavior as the code length tends to infinity.
Theorem 33. Let q q q be a prime power, m ≥ 1 m\ge1 m ≥ 1 be an integer and λ > 1 \lambda>1 λ > 1 be a real number. Fix a rate R ∈ ( 0 , 1 ) R\in(0,1) R ∈ ( 0 , 1 ) and for n ≥ 1 n\ge1 n ≥ 1 set k ( n ) = ⌊ R n ⌋ k(n)=\lfloor Rn\rfloor k ( n ) = ⌊ R n ⌋ and d λ ( n ) = λ ( n − k ( n ) ) + 1 d_\lambda(n)=\lambda(n-k(n))+1 d λ ( n ) = λ ( n − k ( n )) + 1 . Then
lim n → ∞ δ λ ( d λ ( n ) , q m k ( n ) , n , m , q m ) = 0. \lim_{n\to\infty}\delta_\lambda(d_\lambda(n),q^{mk(n)},n,m,q^m)=0. n → ∞ lim δ λ ( d λ ( n ) , q mk ( n ) , n , m , q m ) = 0. Proof. We have that
n − k ( n ) = n − ⌊ R n ⌋ ≥ n − R n = ( 1 − R ) n → n → ∞ ∞ . n-k(n)=n-\lfloor Rn\rfloor\ge n-Rn=(1-R)n\xrightarrow[n\to\infty]{}\infty. n − k ( n ) = n − ⌊ R n ⌋ ≥ n − R n = ( 1 − R ) n n → ∞ ∞. Hence, we can fix N ∈ N N\in\mathbb{N} N ∈ N large enough such that
n − k ( n ) ≥ q m − 1 q − 1 n-k(n)\ge\frac{q^m-1}{q-1} n − k ( n ) ≥ q − 1 q m − 1
for all n ≥ N n \ge N n ≥ N . By Theorem 18 , there is no [ n , k ( n ) ] q m [n,k(n)]_{q^m} [ n , k ( n ) ] q m linear MλD code if n ≥ N n \ge N n ≥ N . Thus,
δ λ ( d λ ( n ) , q m k ( n ) , n , m , q m ) = 0 \delta_\lambda(d_\lambda(n),q^{mk(n)},n,m,q^m)=0 δ λ ( d λ ( n ) , q mk ( n ) , n , m , q m ) = 0
for all n ≥ N n \ge N n ≥ N and the statement follows immediately. □
Note that this result can also be obtained, by observing that MλD codes are also MDS codes, which are sparse as n → ∞ n \to\infty n → ∞ .
The situation of sublinear MλD codes is presumably more difficult. We restrict ourselves to the case where s = m / ℓ s=m/\ell s = m / ℓ divides k k k .
Theorem 34. Let ℓ , s , d \ell,s,d ℓ , s , d be positive integers, let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a real number, and let q q q be a prime power. Then
lim n → ∞ δ λ ( λ d + 1 , q ℓ s ( n − d ) , n , ℓ , q m ) = 0. \lim_{n\to\infty}\delta_\lambda(\lambda d+1,q^{\ell s(n-d)},n,\ell,q^m)=0. n → ∞ lim δ λ ( λ d + 1 , q ℓ s ( n − d ) , n , ℓ , q m ) = 0.
Proof. Every F q ℓ \mathbb{F}_{q^\ell} F q ℓ -linear code with k = s ( n − d ) k=s(n-d) k = s ( n − d ) and minimum λ \lambda λ -subfield distance at least λ d + 1 \lambda d+1 λ d + 1 satisfies that
d = n − k s = n − ⌈ k s ⌉ d=n-\frac{k}{s}=n-\left\lceil\frac{k}{s}\right\rceil d = n − s k = n − ⌈ s k ⌉
which implies that
λ d + 1 = λ ( n − ⌈ k s ⌉ ) + 1. \lambda d+1=\lambda\left(n-\left\lceil\frac{k}{s}\right\rceil\right)+1. λ d + 1 = λ ( n − ⌈ s k ⌉ ) + 1.
Consequently, it is a sublinear MλD code and thus it is a sublinear MDS code with
d H = n − k s + 1 = d + 1. d_H=n-\frac{k}{s}+1=d+1. d H = n − s k + 1 = d + 1.
For the density, this means that
0 ≤ δ λ ( λ d + 1 , q ℓ s ( n − d ) , n , ℓ , q ℓ s ) ≤ δ H ( d + 1 , q ℓ s ( n − d ) , n , ℓ , q ℓ s ) . 0\le\delta_\lambda(\lambda d+1,q^{\ell s(n-d)},n,\ell,q^{\ell s})\le\delta_H(d+1,q^{\ell s(n-d)},n,\ell,q^{\ell s}). 0 ≤ δ λ ( λ d + 1 , q ℓ s ( n − d ) , n , ℓ , q ℓ s ) ≤ δ H ( d + 1 , q ℓ s ( n − d ) , n , ℓ , q ℓ s ) .
By [8 Theorem 4.7] , the right-hand side tends to zero as n → ∞ n\to\infty n → ∞ and the claim on the asymptotic result follows. □
Conditional Density of MλD Codes for q → ∞ q \to\infty q → ∞
For q → ∞ q \to\infty q → ∞ , MRD and MDS codes behave differently, which makes this case particularly interesting. For example, additive, i.e., F q \mathbb{F}_q F q -linear, MDS codes have previously been shown to be dense [8 ] , while additive MRD codes are sparse for q → ∞ q \to\infty q → ∞ [10 ] . For the λ \lambda λ -subfield metric, we can show, under certain parameter restrictions, that MλD codes are dense.
Theorem 35. Let n , ℓ , s , k n,\ell,s,k n , ℓ , s , k be positive integers with k ≤ n s k \le ns k ≤ n s , let λ ≥ 1 \lambda\ge1 λ ≥ 1 be an integer, and set m = ℓ s m=\ell s m = ℓ s and
d ( λ ) = λ ( n − ⌈ k s ⌉ ) + 1. d(\lambda)=\lambda\left(n-\left\lceil\frac{k}{s}\right\rceil\right)+1. d ( λ ) = λ ( n − ⌈ s k ⌉ ) + 1. If
ℓ ( k − 1 ) + ( 1 − ℓ s ) ⌈ k s ⌉ < 0 , \ell(k-1)+(1-\ell s)\left\lceil\frac{k}{s}\right\rceil<0, ℓ ( k − 1 ) + ( 1 − ℓ s ) ⌈ s k ⌉ < 0 , then
lim q → ∞ δ λ ( d ( λ ) , q ℓ k , n , ℓ , q m ) = 1. \lim_{q\to\infty}\delta_\lambda(d(\lambda),q^{\ell k},n,\ell,q^m)=1. q → ∞ lim δ λ ( d ( λ ) , q ℓ k , n , ℓ , q m ) = 1.
Proof. Let us set c = ⌈ k s ⌉ c=\left\lceil\frac{k}{s}\right\rceil c = ⌈ s k ⌉ and t = n − c t=n-c t = n − c , as then d ( λ ) − 1 = λ t d(\lambda)-1=\lambda t d ( λ ) − 1 = λ t . Recall that by Lemma 8, we have that
V λ ( d ( λ ) − 1 , n , q m ) = ∑ a = 0 t ( n a ) ( q m − q ) a ∑ b = 0 min { n − a , λ ( t − a ) } ( n − a b ) ( q − 1 ) b . V_{\lambda}(d(\lambda)-1,n,q^{m})=\sum_{a=0}^{t}\binom{n}{a}(q^{m}-q)^{a}\sum_{b=0}^{\min\{n-a,\lambda(t-a)\}}\binom{n-a}{b}(q-1)^{b}. V λ ( d ( λ ) − 1 , n , q m ) = a = 0 ∑ t ( a n ) ( q m − q ) a b = 0 ∑ m i n { n − a , λ ( t − a )} ( b n − a ) ( q − 1 ) b .
For every pair ( a , b ) (a,b) ( a , b ) occurring in the sum, we have b ≤ n − a b\le n-a b ≤ n − a . Thus
m a + b ≤ m a + n − a = ( m − 1 ) a + n ≤ ( m − 1 ) t + n . ma+b\le ma+n-a=(m-1)a+n\le(m-1)t+n. ma + b ≤ ma + n − a = ( m − 1 ) a + n ≤ ( m − 1 ) t + n .
Since t = n − c t=n-c t = n − c , this gives m a + b ≤ m ( n − c ) + c ma+b\le m(n-c)+c ma + b ≤ m ( n − c ) + c .
As all parameters except q q q are fixed, it follows that
V λ ( d ( λ ) − 1 , n , q m ) = O ( q m ( n − c ) + c ) = O ( q ℓ n s − ℓ s ⌈ k s ⌉ + ⌈ k s ⌉ ) . V_{\lambda}(d(\lambda)-1,n,q^{m})=O\left(q^{m(n-c)+c}\right)=O\left(q^{\ell ns-\ell s\left\lceil\frac{k}{s}\right\rceil+\left\lceil\frac{k}{s}\right\rceil}\right). V λ ( d ( λ ) − 1 , n , q m ) = O ( q m ( n − c ) + c ) = O ( q ℓ n s − ℓ s ⌈ s k ⌉ + ⌈ s k ⌉ ) .
Consequently,
V λ ( d ( λ ) − 1 , n , q m ) q ℓ ( n s + 1 − k ) = O ( q ℓ ( k − 1 ) + ( 1 − ℓ s ) ⌈ k s ⌉ ) . \frac{V_{\lambda}(d(\lambda)-1,n,q^{m})}{q^{\ell(ns+1-k)}}=O\left(q^{\ell(k-1)+(1-\ell s)\left\lceil\frac{k}{s}\right\rceil}\right). q ℓ ( n s + 1 − k ) V λ ( d ( λ ) − 1 , n , q m ) = O ( q ℓ ( k − 1 ) + ( 1 − ℓ s ) ⌈ s k ⌉ ) .
Since we assumed that ℓ ( k − 1 ) + ( 1 − ℓ s ) ⌈ k s ⌉ < 0 \ell(k-1)+(1-\ell s)\left\lceil\frac{k}{s}\right\rceil<0 ℓ ( k − 1 ) + ( 1 − ℓ s ) ⌈ s k ⌉ < 0 , the quotient tends to zero as q → ∞ q\to\infty q → ∞ . The claim now follows from [8 Theorem 3.5] .
The condition of Theorem 35 simplifies considerably in the linear and additive, i.e., F q \mathbb{F}_q F q -linear, settings.
Corollary 36. Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be an integer. Linear M Λ D M\Lambda D M Λ D codes with m > k m>k m > k are dense as q → ∞ q\to\infty q → ∞ .
In fact, for linear codes we have ℓ = m \ell=m ℓ = m and s = 1 s=1 s = 1 . The condition of Theorem 35 becomes
m ( k − 1 ) + ( 1 − m ) k < 0 , m(k-1)+(1-m)k<0, m ( k − 1 ) + ( 1 − m ) k < 0 , which is equivalent to k < m k<m k < m .
Corollary 37. Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be an integer. Additive M Λ D M\Lambda D M Λ D codes with m > k m>k m > k are dense as q → ∞ q\to\infty q → ∞ .
Indeed, for additive codes we have ℓ = 1 \ell=1 ℓ = 1 and s = m s=m s = m . Since k < m k<m k < m , we obtain ⌈ k s ⌉ = 1 \left\lceil\frac{k}{s}\right\rceil=1 ⌈ s k ⌉ = 1 . Substituting this into the condition of Theorem 35 yields ( k − 1 ) + ( 1 − m ) < 0 (k-1)+(1-m)<0 ( k − 1 ) + ( 1 − m ) < 0 , which is equivalent to k < m k<m k < m .
The previous theorem gives a sufficient condition in terms of the code parameters. The next result provides a simple sufficient condition involving the parameter λ \lambda λ .
Theorem 38. Let n , ℓ , s , k n,\ell,s,k n , ℓ , s , k be positive integers with k ≤ n s k\le ns k ≤ n s , set m = ℓ s m=\ell s m = ℓ s , and let λ ≥ 1 \lambda\ge1 λ ≥ 1 be an integer with λ ≤ m \lambda\le m λ ≤ m . Set
d ( λ ) = λ ( n − ⌈ k s ⌉ ) + 1. d(\lambda)=\lambda\left(n-\left\lceil\frac{k}{s}\right\rceil\right)+1. d ( λ ) = λ ( n − ⌈ s k ⌉ ) + 1. Then
lim q → ∞ δ λ ( d ( λ ) , q ℓ k , n , ℓ , q m ) = 1. \lim_{q\to\infty}\delta_{\lambda}(d(\lambda),q^{\ell k},n,\ell,q^{m})=1. q → ∞ lim δ λ ( d ( λ ) , q ℓ k , n , ℓ , q m ) = 1.
Proof. Set t = n − ⌈ k s ⌉ t=n-\left\lceil\frac{k}{s}\right\rceil t = n − ⌈ s k ⌉ , so that d ( λ ) − 1 = λ t d(\lambda)-1=\lambda t d ( λ ) − 1 = λ t . By Lemma 8, we get that
V λ ( d ( λ ) − 1 , n , q m ) = ∑ a = 0 t ( n a ) ( q m − q ) a ∑ b = 0 min { n − a , ⌊ λ ( t − a ) ⌋ } ( n − a b ) ( q − 1 ) b . V_{\lambda}(d(\lambda)-1,n,q^m)=\sum_{a=0}^{t}\binom{n}{a}(q^m-q)^a\sum_{b=0}^{\min\{n-a,\lfloor\lambda(t-a)\rfloor\}}\binom{n-a}{b}(q-1)^b. V λ ( d ( λ ) − 1 , n , q m ) = a = 0 ∑ t ( a n ) ( q m − q ) a b = 0 ∑ m i n { n − a , ⌊ λ ( t − a )⌋} ( b n − a ) ( q − 1 ) b .
For every pair ( a , b ) (a,b) ( a , b ) occurring in the sum, we have that b ≤ λ ( t − a ) b\le\lambda(t-a) b ≤ λ ( t − a ) . Hence
m a + b ≤ m a + λ ( t − a ) = λ t + ( m − λ ) a . ma+b\le ma+\lambda(t-a)=\lambda t+(m-\lambda)a. ma + b ≤ ma + λ ( t − a ) = λ t + ( m − λ ) a .
Since λ ≤ m \lambda\le m λ ≤ m and a ≤ t a\le t a ≤ t , it follows that m a + b ≤ m t ma+b\le mt ma + b ≤ m t . As all parameters except q q q are fixed, we obtain
V λ ( d ( λ ) − 1 , n , q m ) = O ( q m t ) . V_{\lambda}(d(\lambda)-1,n,q^m)=O(q^{mt}). V λ ( d ( λ ) − 1 , n , q m ) = O ( q m t ) .
Using m = ℓ s m=\ell s m = ℓ s and ⌈ k / s ⌉ ≥ k / s \left\lceil k/s\right\rceil\ge k/s ⌈ k / s ⌉ ≥ k / s , we have
m t = m ( n − ⌈ k s ⌉ ) ≤ m ( n − k s ) = ℓ ( n s − k ) . mt=m\left(n-\left\lceil\frac{k}{s}\right\rceil\right)\le m\left(n-\frac{k}{s}\right)=\ell(ns-k). m t = m ( n − ⌈ s k ⌉ ) ≤ m ( n − s k ) = ℓ ( n s − k ) .
Therefore
V λ ( d ( λ ) − 1 , n , q m ) = O ( q ℓ ( n s − k ) ) , V_{\lambda}(d(\lambda)-1,n,q^m)=O\left(q^{\ell(ns-k)}\right), V λ ( d ( λ ) − 1 , n , q m ) = O ( q ℓ ( n s − k ) ) ,
and thus,
V λ ( d ( λ ) − 1 , n , q m ) q ℓ ( n s + 1 − k ) = O ( q − ℓ ) , \frac{V_{\lambda}(d(\lambda)-1,n,q^m)}{q^{\ell(ns+1-k)}}=O(q^{-\ell}), q ℓ ( n s + 1 − k ) V λ ( d ( λ ) − 1 , n , q m ) = O ( q − ℓ ) ,
which tends to zero as q → ∞ q\to\infty q → ∞ . The claim now follows from [8 Theorem 3.5] . □
The regime ℓ → ∞ \ell\to\infty ℓ → ∞
We next consider increasing the size of the subfield over which the code is linear.
Theorem 39. Let n , s n,s n , s be positive integers, let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a real number, and let q q q be a prime power. Fix 1 ≤ k ≤ n s 1\le k\le ns 1 ≤ k ≤ n s and set
d ( λ ) = λ ( n − ⌈ k s ⌉ ) + 1. d(\lambda)=\lambda\left(n-\left\lceil\frac{k}{s}\right\rceil\right)+1. d ( λ ) = λ ( n − ⌈ s k ⌉ ) + 1. Consider the sequence ( F q ℓ s n ) ℓ ≥ 1 (\mathbb{F}_{q^{\ell s}}^{n})_{\ell\ge1} ( F q ℓ s n ) ℓ ≥ 1 . Then M λ D M\lambda D M λ D codes are dense as ℓ → ∞ \ell\to\infty ℓ → ∞ , i.e.,
lim ℓ → ∞ δ λ ( d ( λ ) , q ℓ k , n , ℓ , q ℓ s ) = 1. \lim_{\ell\to\infty}\delta_{\lambda}(d(\lambda),q^{\ell k},n,\ell,q^{\ell s})=1. ℓ → ∞ lim δ λ ( d ( λ ) , q ℓ k , n , ℓ , q ℓ s ) = 1. Proof. Set
t = n − ⌈ k s ⌉ and r = d ( λ ) − 1 = λ t . t=n-\left\lceil\frac{k}{s}\right\rceil\qquad\text{and}\qquad r=d(\lambda)-1=\lambda t. t = n − ⌈ s k ⌉ and r = d ( λ ) − 1 = λ t . Note that since n , k , s n,k,s n , k , s and λ \lambda λ are fixed, so are t t t and r r r .
Recall that by Lemma 8, we have that
V λ ( r , n , q m ) = ∑ a = 0 t ( n a ) ( q m − q ) a ∑ b = 0 min { n − a , ⌊ λ ( t − a ) ⌋ } ( n − a b ) ( q − 1 ) b . V_{\lambda}(r,n,q^m)=\sum_{a=0}^{t}\binom{n}{a}(q^m-q)^a\sum_{b=0}^{\min\{n-a,\lfloor\lambda(t-a)\rfloor\}}\binom{n-a}{b}(q-1)^b. V λ ( r , n , q m ) = a = 0 ∑ t ( a n ) ( q m − q ) a b = 0 ∑ m i n { n − a , ⌊ λ ( t − a )⌋} ( b n − a ) ( q − 1 ) b . Since q , n , λ q,n,\lambda q , n , λ and t t t are fixed, the binomial coefficients, the factors ( q − 1 ) b (q-1)^b ( q − 1 ) b , and the number of summands are all independent of ℓ \ell ℓ . Moreover, every index satisfies a ≤ t a\le t a ≤ t . Hence
V λ ( r , n , q m ) = O ( q m t ) . V_{\lambda}(r,n,q^m)=O(q^{mt}). V λ ( r , n , q m ) = O ( q m t ) .
Using m = ℓ s m=\ell s m = ℓ s and
t = n − ⌈ k s ⌉ ≤ n − k s , t=n-\left\lceil\frac{k}{s}\right\rceil\le n-\frac{k}{s}, t = n − ⌈ s k ⌉ ≤ n − s k ,
we obtain
V λ ( r , n , q m ) = O ( q ℓ s ( n − ⌈ k s ⌉ ) ) = O ( q ℓ ( n s − k ) ) . V_{\lambda}(r,n,q^m)=O\left(q^{\ell s\left(n-\left\lceil\frac{k}{s}\right\rceil\right)}\right)=O\left(q^{\ell(ns-k)}\right). V λ ( r , n , q m ) = O ( q ℓ s ( n − ⌈ s k ⌉ ) ) = O ( q ℓ ( n s − k ) ) .
Thus,
V λ ( r , n , q m ) q ℓ ( n s + 1 − k ) = O ( q − ℓ ) , \frac{V_{\lambda}(r,n,q^m)}{q^{\ell(ns+1-k)}}=O(q^{-\ell}), q ℓ ( n s + 1 − k ) V λ ( r , n , q m ) = O ( q − ℓ ) ,
which tends to zero as ℓ → ∞ \ell\to\infty ℓ → ∞ . The claim follows from [8 Theorem 3.6] . □
Relative Densities
The inclusions
{ M R D } ⊂ { M λ D } ⊂ { M D S } \{\mathrm{MRD}\}\subset\{\mathrm{M}\lambda\mathrm{D}\}\subset\{\mathrm{MDS}\} { MRD } ⊂ { M λ D } ⊂ { MDS }
naturally raise the question of how large these subclasses are inside the bigger code classes. Let δ R \delta_R δ R , δ λ \delta_\lambda δ λ , and δ H \delta_H δ H denote the densities of MRD, MλD and MDS codes, respectively. Whenever the corresponding densities are nonzero, we have
∣ M λ D ∣ ∣ M D S ∣ = δ λ δ H , ∣ M R D ∣ ∣ M λ D ∣ = δ R δ λ . \frac{|\mathrm{M}\lambda\mathrm{D}|}{|\mathrm{MDS}|}=\frac{\delta_\lambda}{\delta_H},\qquad
\frac{|\mathrm{MRD}|}{|\mathrm{M}\lambda\mathrm{D}|}=\frac{\delta_R}{\delta_\lambda}. ∣ MDS ∣ ∣ M λ D ∣ = δ H δ λ , ∣ M λ D ∣ ∣ MRD ∣ = δ λ δ R .
The first quotient can be evaluated in the asymptotic regimes where both MDS and MλD codes are dense.
Corollary 40. Let n , m , s n,m,s n , m , s be positive integers, let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a real number, and let q q q be a prime power. Assume that the hypotheses of Theorem 35 are satisfied. Then the proportion of MDS codes that are MλD satisfies
lim q → ∞ ∣ { C ⊆ F q m n ∣ C is M λ D } ∣ ∣ { C ⊆ F q m n ∣ C is MDS } ∣ = 1. \lim_{q\to\infty}\frac{\left|\left\{C\subseteq\mathbb{F}_{q^m}^{n}\mid C\text{ is M}\lambda\text{D}\right\}\right|}{\left|\left\{C\subseteq\mathbb{F}_{q^m}^{n}\mid C\text{ is MDS}\right\}\right|}=1. q → ∞ lim { C ⊆ F q m n ∣ C is MDS } { C ⊆ F q m n ∣ C is M λ D } = 1.
Corollary 41. Let n , s n,s n , s be positive integers, let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a real number, and let q q q be a prime power. Assume that m ≥ n m\ge n m ≥ n and that both MλD codes and MRD codes are dense in the considered asymptotic regime. Then the proportion of MλD codes that are MRD satisfies
lim ℓ → ∞ ∣ { C ⊆ F q m n ∣ C is MRD } ∣ ∣ { C ⊆ F q m n ∣ C is M λ D } ∣ = 1. \lim_{\ell\to\infty}\frac{\left|\left\{C\subseteq\mathbb{F}_{q^m}^{n}\mid C\text{ is MRD}\right\}\right|}{\left|\left\{C\subseteq\mathbb{F}_{q^m}^{n}\mid C\text{ is M}\lambda\text{D}\right\}\right|}=1. ℓ → ∞ lim { C ⊆ F q m n ∣ C is M λ D } { C ⊆ F q m n ∣ C is MRD } = 1.
However, when n → ∞ n\to\infty n → ∞ , both MDS and MλD codes are sparse. Consequently, the quotient ∣ M λ D ∣ ∣ M D S ∣ = δ λ δ H \frac{|\mathrm{M}\lambda\mathrm{D}|}{|\mathrm{MDS}|}=\frac{\delta_\lambda}{\delta_H} ∣ MDS ∣ ∣ M λ D ∣ = δ H δ λ cannot be determined from the density results alone and determining this relative density remains an interesting open problem.
Constant-Weight Codes in the λ-Subfield Metric
Constant-weight linear codes form an extremal class in several metric settings. In the Hamming metric, the linear constant-weight codes have been completely characterized, to be only r r r fold repetitions of simplex codes [15 ] . A simplex code is generated by a matrix, having as columns all the representatives of ( F q k m ∖ { 0 } ) / F q ∗ (\mathbb{F}_q^{km}\setminus\{0\})/\mathbb{F}_q^* ( F q k m ∖ { 0 }) / F q ∗ . That is: each non-zero vector of F q k m \mathbb{F}_q^{km} F q k m appears once, up to scalar multiples.
For constant λ \lambda λ -subfield weight codes, we will instead take all non-zero vectors of F q k m \mathbb{F}_q^{km} F q k m up to multiples of F q \mathbb{F}_q F q . Since for λ = 1 \lambda=1 λ = 1 , the λ \lambda λ -subfield metric reduces to the Hamming metric, we will restrict ourselves in this section to λ > 1 \lambda>1 λ > 1 .
Our starting point is the Plotkin-type bound derived in [7 ] . For this, we define the average λ \lambda λ -subfield weight of the alphabet F q m \mathbb{F}_{q^m} F q m to be
ω λ = 1 q m ∑ x ∈ F q m wt λ ( x ) = q − 1 + λ ( q m − q ) q m . \omega_\lambda= \frac{1}{q^m}\sum_{x\in\mathbb{F}_{q^m}}\operatorname{wt}_\lambda(x) = \frac{q-1+\lambda(q^m-q)}{q^m}. ω λ = q m 1 x ∈ F q m ∑ wt λ ( x ) = q m q − 1 + λ ( q m − q ) .
The Plotkin-type bound for linear codes can then be written as follows.
Theorem 42 (Plotkin-type bound [7 ] ). Let C ⊆ F q m n C\subseteq\mathbb{F}_{q^m}^n C ⊆ F q m n be a linear code. Then
d λ ( C ) ≤ ∣ C ∣ ∣ C ∣ − 1 n ω λ . d_\lambda(C)\leq\frac{|C|}{|C|-1}n\omega_\lambda. d λ ( C ) ≤ ∣ C ∣ − 1 ∣ C ∣ n ω λ .
Within the proof of such Plotkin-type bounds, one uses that
∑ c ∈ C ∖ { 0 } wt ( c ) ≥ d ( C ) ( ∣ C ∣ − 1 ) , \sum_{c\in C\setminus\{0\}}\operatorname{wt}(c)\geq d(C)(|C|-1), c ∈ C ∖ { 0 } ∑ wt ( c ) ≥ d ( C ) ( ∣ C ∣ − 1 ) ,
which is attained by codes, where each non-zero codeword has constant weight d d d , thus called constant-weight codes.
Definition 43. A linear code C ⊆ F q m n C\subseteq\mathbb{F}_{q^m}^n C ⊆ F q m n is called a constant λ \lambda λ -subfield weight code if there exists a w > 0 w>0 w > 0 such that wt λ ( c ) = w \operatorname{wt}_\lambda(c)=w wt λ ( c ) = w for every c ∈ C ∖ { 0 } c\in C\setminus\{0\} c ∈ C ∖ { 0 } .
For such a code, the minimum distance is equal to its nonzero constant weight. We now give an explicit construction of constant-weight codes for arbitrary dimensions.
Let us define
P q ( m , k ) = ( F q m k ∖ { 0 } ) / F q × . \mathcal{P}_q(m,k)=\left(\mathbb{F}_{q^m}^k\setminus\{0\}\right)/\mathbb{F}_q^\times. P q ( m , k ) = ( F q m k ∖ { 0 } ) / F q × .
where two vectors are equal, if they differ by multiplication with a scalar in F q × \mathbb{F}_q^\times F q × . Thus
M : = ∣ P q ( m , k ) ∣ = q m k − 1 q − 1 . M:=|\mathcal{P}_q(m,k)|=\frac{q^{mk}-1}{q-1}. M := ∣ P q ( m , k ) ∣ = q − 1 q mk − 1 .
We can choose u 1 , … , u M u_1,\ldots,u_M u 1 , … , u M as representatives of each class in P q ( m , k ) \mathcal{P}_q(m,k) P q ( m , k ) and define G m , k , q G_{m,k,q} G m , k , q as a matrix, having u 1 , … , u M u_1,\ldots,u_M u 1 , … , u M as columns, i.e., G m , k , q ∈ F q m k × M G_{m,k,q}\in\mathbb{F}_{q^m}^{k\times M} G m , k , q ∈ F q m k × M . We denote the code generated by G m , k , q G_{m,k,q} G m , k , q by S q , m , k S_{q,m,k} S q , m , k .
Theorem 44. For every prime power q q q , positive integers m , k m,k m , k and real λ ≥ 1 \lambda\geq1 λ ≥ 1 , the code S q , m , k S_{q,m,k} S q , m , k is a linear [ n , k , d λ ] q m [n,k,d_\lambda]_{q^m} [ n , k , d λ ] q m constant λ \lambda λ -subfield weight code with length n = q m k − 1 q − 1 n=\frac{q^{mk}-1}{q-1} n = q − 1 q mk − 1 and minimum distance
d λ = q m ( k − 1 ) ( 1 + λ q m − q q − 1 ) . d_\lambda=q^{m(k-1)}\left(1+\lambda\frac{q^m-q}{q-1}\right). d λ = q m ( k − 1 ) ( 1 + λ q − 1 q m − q ) .
Proof. Let v ∈ F q m k ∖ { 0 } v\in\mathbb{F}_{q^m}^k\setminus\{0\} v ∈ F q m k ∖ { 0 } and consider the codeword c = v G m , k , q c=vG_{m,k,q} c = v G m , k , q . Its coordinates c i c_i c i are of the form ⟨ v , u i ⟩ \langle v,u_i\rangle ⟨ v , u i ⟩ .
We can consider the nonzero F q m \mathbb{F}_{q^m} F q m -linear map
φ v : F q m k ⟶ F q m , u ⟼ ⟨ v , u ⟩ . \varphi_v:\mathbb{F}_{q^m}^k\longrightarrow\mathbb{F}_{q^m},\qquad u\longmapsto\langle v,u\rangle. φ v : F q m k ⟶ F q m , u ⟼ ⟨ v , u ⟩ .
The map φ v \varphi_v φ v is surjective and every fiber has cardinality q m ( k − 1 ) q^{m(k-1)} q m ( k − 1 ) .
Moreover, the multiplication of u u u by an element μ \mu μ of F q × \mathbb{F}_q^\times F q × multiplies φ v ( u ) \varphi_v(u) φ v ( u ) by the same element, that is φ v ( μ u ) = μ φ v ( u ) \varphi_v(\mu u)=\mu\varphi_v(u) φ v ( μu ) = μ φ v ( u ) . Thus, for every class [ x ] ∈ F q m × / F q × [x]\in\mathbb{F}_{q^m}^\times/\mathbb{F}_q^\times [ x ] ∈ F q m × / F q × there are exactly q m ( k − 1 ) q^{m(k-1)} q m ( k − 1 ) classes [ u ] ∈ P q ( m , k ) [u]\in\mathcal{P}_q(m,k) [ u ] ∈ P q ( m , k ) for which [ ⟨ v , u ⟩ ] = [ x ] [\langle v,u\rangle]=[x] [⟨ v , u ⟩] = [ x ] . Note that there is exactly one class in F q m × / F q × \mathbb{F}_{q^m}^{\times}/\mathbb{F}_q^{\times} F q m × / F q × which is contained in F q × \mathbb{F}_q^{\times} F q × , i.e., F q × \mathbb{F}_q^{\times} F q × itself. Hence c c c has exactly q m ( k − 1 ) q^{m(k-1)} q m ( k − 1 ) nonzero coordinates in F q \mathbb{F}_q F q .
The remaining
q m − 1 q − 1 − 1 = q m − q q − 1 \frac{q^m-1}{q-1}-1=\frac{q^m-q}{q-1} q − 1 q m − 1 − 1 = q − 1 q m − q
nonzero classes consist entirely of elements outside F q \mathbb{F}_q F q . Thus c c c has
q m ( k − 1 ) q m − q q − 1 q^{m(k-1)}\frac{q^m-q}{q-1} q m ( k − 1 ) q − 1 q m − q
coordinates in F q m ∖ F q \mathbb{F}_{q^m}\setminus\mathbb{F}_q F q m ∖ F q .
Finally, the remaining
q m k − 1 q − 1 − q m ( k − 1 ) q m − 1 q − 1 = q m ( k − 1 ) − 1 q − 1 \frac{q^{mk}-1}{q-1}-q^{m(k-1)}\frac{q^m-1}{q-1}=\frac{q^{m(k-1)}-1}{q-1} q − 1 q mk − 1 − q m ( k − 1 ) q − 1 q m − 1 = q − 1 q m ( k − 1 ) − 1
coordinates are zero.
Therefore every nonzero codeword has λ \lambda λ -subfield weight
q m ( k − 1 ) + λ q m ( k − 1 ) q m − q q − 1 , q^{m(k-1)}+\lambda q^{m(k-1)}\frac{q^m-q}{q-1}, q m ( k − 1 ) + λ q m ( k − 1 ) q − 1 q m − q ,
independently of the choice of v v v .
These constant λ \lambda λ -subfield weight codes are indeed optimal for the Plotkin-type bound of Theorem 42 .
Corollary 45. The code S q , m , k S_{q,m,k} S q , m , k attains the Plotkin bound in Theorem 42 with equality.
Proof. Since ∣ S q , m , k ∣ = q m k |S_{q,m,k}|=q^{mk} ∣ S q , m , k ∣ = q mk and M = ( q m k − 1 ) / ( q − 1 ) M=(q^{mk}-1)/(q-1) M = ( q mk − 1 ) / ( q − 1 ) , the Plotkin bound gives
∣ S q , m , k ∣ ∣ S q , m , k ∣ − 1 M ω λ = q m k q m k − 1 q m k − 1 q − 1 q − 1 + λ ( q m − q ) q m \frac{|S_{q,m,k}|}{|S_{q,m,k}|-1}M\omega_\lambda
=\frac{q^{mk}}{q^{mk}-1}\frac{q^{mk}-1}{q-1}\frac{q-1+\lambda(q^m-q)}{q^m} ∣ S q , m , k ∣ − 1 ∣ S q , m , k ∣ M ω λ = q mk − 1 q mk q − 1 q mk − 1 q m q − 1 + λ ( q m − q ) = q m ( k − 1 ) ( 1 + λ q m − q q − 1 ) , =q^{m(k-1)}\left(1+\lambda\frac{q^m-q}{q-1}\right), = q m ( k − 1 ) ( 1 + λ q − 1 q m − q ) , which is precisely the minimum distance from Theorem 44 .
We note that, for λ > 1 \lambda>1 λ > 1 , this construction produces the smallest length constant λ \lambda λ -subfield weight codes. We next show, that all constant λ \lambda λ -subfield weight codes are (up to linear λ \lambda λ -subfield isometries) r r r fold repetitions of S q , m , k S_{q,m,k} S q , m , k , hence giving a complete characterization.
Definition 46. A weight on F q m \mathbb{F}_{q^m} F q m is said to have the extension property if every linear weight-preserving map between two linear codes extends to a linear isometry of the entire ambient space. That is: for C , C ′ ⊆ F q m n C,C'\subseteq\mathbb{F}_{q^m}^n C , C ′ ⊆ F q m n two linear codes, if there exists a linear map μ : C → C ′ \mu:C\to C' μ : C → C ′ , which preserves the weight, then there exists a linear isometry μ ‾ : F q m n → F q m n \overline{\mu}:\mathbb{F}_{q^m}^n\to\mathbb{F}_{q^m}^n μ : F q m n → F q m n , such that μ ‾ ∣ C = μ \overline{\mu}|_C=\mu μ ∣ C = μ .
The extension property is the main ingredient in the structure theorem for linear constant-weight codes of Wood [15 ] . We first verify that it holds for the λ \lambda λ -subfield weight.
Proposition 47. Let λ > 1 \lambda>1 λ > 1 . The λ \lambda λ -subfield weight has the extension property.
Proof. Due to [16 Proposition 12] it is enough to show that the matrix associated to the weight has full rank. This matrix is indexed by the equivalence classes of nonzero elements under multiplication by elements of F q × \mathbb{F}_q^{\times} F q × , and its entries record the weight between representatives of these classes. For the λ \lambda λ -subfield weight, two representatives from the same class give weight 1 1 1 , while representatives from different classes give weight λ \lambda λ . Hence, the associated matrix is given by
A = ( 1 λ ⋯ λ λ 1 ⋯ λ ⋮ ⋮ ⋱ ⋮ λ λ ⋯ 1 ) ∈ R N × N , A=\begin{pmatrix}
1 & \lambda& \cdots& \lambda\\
\lambda& 1 & \cdots& \lambda\\
\vdots& \vdots& \ddots& \vdots\\
\lambda& \lambda& \cdots& 1
\end{pmatrix}\in\mathbb{R}^{N\times N}, A = 1 λ ⋮ λ λ 1 ⋮ λ ⋯ ⋯ ⋱ ⋯ λ λ ⋮ 1 ∈ R N × N ,
where N = q m − 1 q − 1 N=\frac{q^m-1}{q-1} N = q − 1 q m − 1 , and we can easily compute its determinant to be
det ( A ) = ( 1 − λ ) N − 1 ( 1 + ( N − 1 ) λ ) , \det(A)=(1-\lambda)^{N-1}(1+(N-1)\lambda), det ( A ) = ( 1 − λ ) N − 1 ( 1 + ( N − 1 ) λ ) ,
which is nonzero for λ > 1 \lambda>1 λ > 1 . Hence A A A has full rank, and the extension property follows. □ \square □
Theorem 48. Let λ > 1 \lambda>1 λ > 1 be a real number and let C ⊆ F q m n C\subseteq\mathbb{F}_{q^m}^{n} C ⊆ F q m n be a non-degenerate linear code of dimension k k k . Then C C C has constant nonzero λ \lambda λ -subfield weight if and only if it is equivalent, with respect to the λ \lambda λ -subfield metric, to an r r r -fold repetition of S q , m , k S_{q,m,k} S q , m , k for some positive integer r r r .
In particular, n = r q m k − 1 q − 1 n=r\frac{q^{mk}-1}{q-1} n = r q − 1 q mk − 1 and every nonzero codeword has weight
r q m ( k − 1 ) ( 1 + λ q m − q q − 1 ) . rq^{m(k-1)}\left(1+\lambda\frac{q^m-q}{q-1}\right). r q m ( k − 1 ) ( 1 + λ q − 1 q m − q ) .
Proof. By Proposition 47, the λ \lambda λ -subfield weight satisfies the extension property. The structure theorem for linear constant-weight codes [15 Theorem 5.4] therefore applies. Together with the smallest-length constant λ \lambda λ -subfield weight code constructed in Theorem 44, it follows that every non-degenerate linear constant-weight code is equivalent (under the λ \lambda λ -subfield metric) to a r r r fold repetition of S q , m , k S_{q,m,k} S q , m , k .
The converse follows immediately from Theorem 44, since r r r fold repetitions preserve the constant-weight property. □ \square □
Thus, for λ > 1 \lambda>1 λ > 1 , the preceding theorem gives a complete classification of non-degenerate linear constant-weight codes in the λ \lambda λ -subfield metric.
Example 49. Let q = m = 2 q=m=2 q = m = 2 and write F 4 = F 2 ( α ) \mathbb{F}_4=\mathbb{F}_2(\alpha) F 4 = F 2 ( α ) with α 2 = α + 1 \alpha^2=\alpha+1 α 2 = α + 1 . For k = 2 k=2 k = 2 , we have n = 2 4 − 1 2 − 1 = 15 n=\frac{2^4-1}{2-1}=15 n = 2 − 1 2 4 − 1 = 15 . Since F 2 × = { 1 } \mathbb{F}_2^{\times}=\{1\} F 2 × = { 1 } , the columns of the canonical generator matrix are simply all nonzero vectors of F 4 2 \mathbb{F}_4^2 F 4 2 . For example, we may take
G = ( 1 α α + 1 0 0 0 1 1 1 α α α α + 1 α + 1 α + 1 0 0 0 1 α α + 1 1 α α + 1 1 α α + 1 1 α α + 1 ) . G=\begin{pmatrix}
1 & \alpha& \alpha+1 & 0 & 0 & 0 & 1 & 1 & 1 & \alpha& \alpha& \alpha& \alpha+1 & \alpha+1 & \alpha+1 \\
0 & 0 & 0 & 1 & \alpha& \alpha+1 & 1 & \alpha& \alpha+1 & 1 & \alpha& \alpha+1 & 1 & \alpha& \alpha+1
\end{pmatrix}. G = ( 1 0 α 0 α + 1 0 0 1 0 α 0 α + 1 1 1 1 α 1 α + 1 α 1 α α α α + 1 α + 1 1 α + 1 α α + 1 α + 1 ) .
Every nonzero codeword contains precisely three zero coordinates, four nonzero coordinates in F 2 \mathbb{F}_2 F 2 , and eight coordinates in F 4 ∖ F 2 \mathbb{F}_4\setminus\mathbb{F}_2 F 4 ∖ F 2 . Hence d λ = 4 + 8 λ d_\lambda=4+8\lambda d λ = 4 + 8 λ . In particular, for λ = 2 \lambda=2 λ = 2 the code is a [ 15 , 2 , 20 ] 4 [15,2,20]_4 [ 15 , 2 , 20 ] 4 constant λ \lambda λ -subfield weight code.
Moreover, the average weight is given by
ω 2 = 1 + 2 ( 4 − 2 ) 4 = 5 4 , \omega_2=\frac{1+2(4-2)}{4}=\frac{5}{4}, ω 2 = 4 1 + 2 ( 4 − 2 ) = 4 5 ,
and the Plotkin-type bound from Theorem 42 gives
d λ ≤ 16 15 ⋅ 15 ⋅ 5 4 = 20. d_{\lambda} \le\frac{16}{15} \cdot15 \cdot\frac{5}{4} = 20. d λ ≤ 15 16 ⋅ 15 ⋅ 4 5 = 20.
Thus the code attains the Plotkin bound with equality.
Finally, we want to note that our construction is a subset of the Hamming-metric constant weight codes. In fact, if we set Q = q m Q = q^{m} Q = q m and r = ( Q − 1 ) / ( q − 1 ) r = (Q - 1)/(q - 1) r = ( Q − 1 ) / ( q − 1 ) , then the code S q , m , k S_{q,m,k} S q , m , k can be viewed as a scaled r r r -fold repetition of the Q Q Q -ary simplex code of dimension k k k , which we denote by S Q , k H S^{H}_{Q,k} S Q , k H .
Indeed, let S H S^{H} S H be a generator matrix of the Q Q Q -ary simplex code whose columns represent the points of PG ( k − 1 , Q ) \operatorname{PG}(k - 1, Q) PG ( k − 1 , Q ) , and let α 1 , … , α r \alpha_{1}, \ldots, \alpha_{r} α 1 , … , α r represent the cosets of F q × \mathbb{F}_{q}^{\times} F q × in F Q × \mathbb{F}_{Q}^{\times} F Q × . Then the columns of
[ α 1 S H ∣ α 2 S H ∣ ⋯ ∣ α r S H ] \left[\alpha_{1}S^{H} \mid\alpha_{2}S^{H} \mid\cdots\mid\alpha_{r}S^{H}\right] [ α 1 S H ∣ α 2 S H ∣ ⋯ ∣ α r S H ]
form a complete set of representatives of P q ( m , k ) \mathcal{P}_{q}(m,k) P q ( m , k ) . Hence, with this choice of representatives,
S q , m , k = { ( α 1 c , … , α r c ) ∣ c ∈ S Q , k H } . S_{q,m,k} = \left\{(\alpha_{1}c,\ldots,\alpha_{r}c) \mid c \in S^{H}_{Q,k}\right\}. S q , m , k = { ( α 1 c , … , α r c ) ∣ c ∈ S Q , k H } .
In particular, S q , m , k S_{q,m,k} S q , m , k also has constant Hamming weight
r Q k − 1 = q m ( k − 1 ) q m − 1 q − 1 , rQ^{k-1} = q^{m(k-1)}\frac{q^{m}-1}{q-1}, r Q k − 1 = q m ( k − 1 ) q − 1 q m − 1 ,
since every nonzero codeword of S Q , k H S^{H}_{Q,k} S Q , k H has Hamming weight Q k − 1 Q^{k-1} Q k − 1 .
Johnson-Type Bounds in the λ \lambda λ -Subfield Metric
The Johnson bound is one of the fundamental tools in list decoding. Besides its importance as a decoding radius, it is remarkable because it admits several different proofs, each emphasizing a different geometric or combinatorial aspect of the Hamming metric.
We consider four different approaches: a direct consequence of the Hamming Johnson bound, a Plotkin-type argument, an embedding into a Hamming space, and the general Guruswami–Sudan argument [11 ] .
For each approach, we get a different bound, which covers different parameter ranges. We then compare the respective Johnson radii in § 6.5 .
A Direct Consequence of the Hamming Johnson Bound
We begin with a first Johnson-type bound that follows immediately from the corresponding result in the Hamming metric. Recall that, for every x ∈ F q m n x \in\mathbb{F}_{q^{m}}^{n} x ∈ F q m n ,
wt λ ( x ) ≤ λ wt H ( x ) . \operatorname{wt}_{\lambda}(x) \le\lambda\operatorname{wt}_{H}(x). wt λ ( x ) ≤ λ wt H ( x ) .
Consequently, every code C ⊆ F q m n C \subseteq\mathbb{F}_{q^{m}}^{n} C ⊆ F q m n satisfies
d H ( C ) ≥ d λ ( C ) λ . d_{H}(C) \ge\frac{d_{\lambda}(C)}{\lambda}. d H ( C ) ≥ λ d λ ( C ) .
Let us denote by
B λ ( y , r , n , q m ) = { x ∈ F q m n ∣ d λ ( x , y ) ≤ r } B_{\lambda}(y,r,n,q^{m}) = \left\{x \in\mathbb{F}_{q^{m}}^{n} \mid d_{\lambda}(x,y) \le r\right\} B λ ( y , r , n , q m ) = { x ∈ F q m n ∣ d λ ( x , y ) ≤ r }
the λ \lambda λ -subfield ball around y ∈ F q m n y \in\mathbb{F}_{q^{m}}^{n} y ∈ F q m n of radius r r r , and similarly
B H ( y , r , n , q m ) = { x ∈ F q m n ∣ d H ( x , y ) ≤ r } . B_{H}(y,r,n,q^{m}) = \left\{x \in\mathbb{F}_{q^{m}}^{n} \mid d_{H}(x,y) \le r\right\}. B H ( y , r , n , q m ) = { x ∈ F q m n ∣ d H ( x , y ) ≤ r } .
Corollary 50. Let λ ≥ 1 \lambda\ge1 λ ≥ 1 and w w w be real numbers. Let C ⊆ F q m C \subseteq\mathbb{F}_{q^m} C ⊆ F q m be a code with minimum λ \lambda λ -subfield distance at least d λ d_\lambda d λ . If
w < n ( 1 − 1 − d λ λ n ) , w<n\left(1-\sqrt{1-\frac{d_\lambda}{\lambda n}}\right), w < n ( 1 − 1 − λn d λ ) , then C C C is ( w , L ) (w,L) ( w , L ) -list decodable in the λ \lambda λ -subfield metric, where
L ≤ d λ − λ w d λ − 2 λ w + λ w 2 n . L\le\frac{d_\lambda-\lambda w}{d_\lambda-2\lambda w+\frac{\lambda w^2}{n}}. L ≤ d λ − 2 λ w + n λ w 2 d λ − λ w .
Proof. Since d H ( C ) ≥ d λ / λ d_H(C)\ge d_\lambda/\lambda d H ( C ) ≥ d λ / λ , the Hamming Johnson bound of Corollary 14 applied with minimum distance d λ / λ d_\lambda/\lambda d λ / λ shows that C C C is Hamming-list decodable up to radius
w < n ( 1 − 1 − d λ λ n ) , w<n\left(1-\sqrt{1-\frac{d_\lambda}{\lambda n}}\right), w < n ( 1 − 1 − λn d λ ) ,
with list size
L ≤ d λ λ − w d λ λ − 2 w + w 2 n = d λ − λ w d λ − 2 λ w + λ w 2 n . L\le\frac{\frac{d_\lambda}{\lambda}-w}{\frac{d_\lambda}{\lambda}-2w+\frac{w^2}{n}}=\frac{d_\lambda-\lambda w}{d_\lambda-2\lambda w+\frac{\lambda w^2}{n}}. L ≤ λ d λ − 2 w + n w 2 λ d λ − w = d λ − 2 λ w + n λ w 2 d λ − λ w .
Since wt H ( x ) ≤ wt λ ( x ) \operatorname{wt}_H(x)\le\operatorname{wt}_\lambda(x) wt H ( x ) ≤ wt λ ( x ) for every x ∈ F q m x\in\mathbb{F}_{q^m} x ∈ F q m , we get that
B λ ( y , w , n , q m ) ⊆ B H ( y , w , n , q m ) B_\lambda(y,w,n,q^m)\subseteq B_H(y,w,n,q^m) B λ ( y , w , n , q m ) ⊆ B H ( y , w , n , q m )
for every y ∈ F q m y\in\mathbb{F}_{q^m} y ∈ F q m . Therefore the same list-size bound holds for the λ \lambda λ -subfield metric. □ \square □
Clearly, if we set λ = 1 \lambda=1 λ = 1 , the λ \lambda λ -subfield metric coincides with the Hamming metric and also the two Johnson bounds, i.e., Corollary 14 and Corollary 50, coincide.
Plotkin argument
Another approach is based on using a nonlinear Plotkin-like bound using the maximum weight of a code. Hence, we first require such bound for the λ \lambda λ -subfield distance.
Proposition 51. Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a real number. Let C ⊆ F q m n C\subseteq\mathbb{F}_{q^m}^n C ⊆ F q m n be a (not necessarily linear) code with minimum λ \lambda λ -subfield distance d λ ( C ) d_\lambda(C) d λ ( C ) , and let
W λ = max { wt λ ( c ) ∣ c ∈ C } . W_\lambda=\max\{\operatorname{wt}_\lambda(c)\mid c\in C\}. W λ = max { wt λ ( c ) ∣ c ∈ C } . If d λ ( C ) − 2 W λ + W λ 2 λ n > 0 d_\lambda(C)-2W_\lambda+\frac{W_\lambda^2}{\lambda n}>0 d λ ( C ) − 2 W λ + λn W λ 2 > 0 , then
∣ C ∣ ≤ d λ ( C ) d λ ( C ) − 2 W λ + W λ 2 λ n . |C|\le\frac{d_\lambda(C)}{d_\lambda(C)-2W_\lambda+\frac{W_\lambda^2}{\lambda n}}. ∣ C ∣ ≤ d λ ( C ) − 2 W λ + λn W λ 2 d λ ( C ) .
Note that the condition d λ ( C ) − 2 W λ + W λ 2 λ n > 0 d_\lambda(C)-2W_\lambda+\frac{W_\lambda^2}{\lambda n}>0 d λ ( C ) − 2 W λ + λn W λ 2 > 0 , is never satisfied for a linear code, as we have that W λ ≥ d λ W_\lambda\ge d_\lambda W λ ≥ d λ . However, for non-linear codes, this can be satisfied. For example, the non-linear code
C = { ( 1 , 1 , α ) , ( α + 1 , α , 0 ) } ⊆ F 4 3 , C=\{(1,1,\alpha),(\alpha+1,\alpha,0)\}\subseteq\mathbb{F}_4^3, C = {( 1 , 1 , α ) , ( α + 1 , α , 0 )} ⊆ F 4 3 ,
where F 4 = F 2 ( α ) \mathbb{F}_4=\mathbb{F}_2(\alpha) F 4 = F 2 ( α ) with α 2 = α + 1 \alpha^2=\alpha+1 α 2 = α + 1 and λ = 2 \lambda=2 λ = 2 is such that W λ = 4 W_\lambda=4 W λ = 4 while d λ = 6 d_\lambda=6 d λ = 6 .
Proof. Let
T = ∑ c ∈ C wt λ ( c ) T=\sum_{c\in C}\operatorname{wt}_\lambda(c) T = c ∈ C ∑ wt λ ( c )
denote the total λ \lambda λ -subfield weight of the code. Since every pair of distinct codewords has distance at least d λ ( C ) d_\lambda(C) d λ ( C ) ,
∣ C ∣ ( ∣ C ∣ − 1 ) d λ ( C ) ≤ ∑ x , y ∈ C d λ ( x , y ) . |C|(|C|-1)d_\lambda(C) \le\sum_{x,y\in C} d_\lambda(x,y). ∣ C ∣ ( ∣ C ∣ − 1 ) d λ ( C ) ≤ x , y ∈ C ∑ d λ ( x , y ) .
Writing the right-hand side coordinatewise gives
∑ x , y ∈ C d λ ( x , y ) = ∑ i = 1 n S i . \sum_{x,y\in C} d_\lambda(x,y)=\sum_{i=1}^{n}S_i. x , y ∈ C ∑ d λ ( x , y ) = i = 1 ∑ n S i .
where S i = ∑ a , b ∈ A i wt λ ( a − b ) S_i=\sum_{a,b\in A_i}\operatorname{wt}_\lambda(a-b) S i = ∑ a , b ∈ A i wt λ ( a − b ) , and A i A_i A i denotes the multiset of symbols appearing in the i i i -th coordinate of all codewords in C C C .
For any a , b ∈ F q m a,b\in\mathbb{F}_{q^m} a , b ∈ F q m , we have
wt λ ( a − b ) ≤ wt λ ( a ) + wt λ ( b ) − wt λ ( a ) wt λ ( b ) λ . \operatorname{wt}_\lambda(a-b)\le\operatorname{wt}_\lambda(a)+\operatorname{wt}_\lambda(b)-\frac{\operatorname{wt}_\lambda(a)\operatorname{wt}_\lambda(b)}{\lambda}. wt λ ( a − b ) ≤ wt λ ( a ) + wt λ ( b ) − λ wt λ ( a ) wt λ ( b ) .
Indeed, equality holds if either symbol is zero. If both are nonzero and belong to F q \mathbb{F}_q F q , the left-hand side is at most 1, whereas the right-hand side is 2 − 1 / λ ≥ 1 2-1/\lambda\ge1 2 − 1/ λ ≥ 1 . Otherwise, the right-hand side equals λ \lambda λ , which is the maximum possible symbol weight.
Summing this inequality over the multiset A i A_i A i of symbols in coordinate i i i gives
S i ≤ 2 ∣ C ∣ T i − T i 2 λ , S_i\le2|C|T_i-\frac{T_i^2}{\lambda}, S i ≤ 2∣ C ∣ T i − λ T i 2 ,
where
T i = ∑ a ∈ A i wt λ ( a ) . T_i=\sum_{a\in A_i}\operatorname{wt}_\lambda(a). T i = a ∈ A i ∑ wt λ ( a ) .
Summing over all coordinates yields
∑ x , y ∈ C d λ ( x , y ) = ∑ i = 1 n S i ≤ 2 ∣ C ∣ T − 1 λ ∑ i = 1 n T i 2 . \sum_{x,y\in C}d_\lambda(x,y)=\sum_{i=1}^{n}S_i\le2|C|T-\frac{1}{\lambda}\sum_{i=1}^{n}T_i^2. x , y ∈ C ∑ d λ ( x , y ) = i = 1 ∑ n S i ≤ 2∣ C ∣ T − λ 1 i = 1 ∑ n T i 2 .
Applying the Cauchy–Schwarz inequality gives
∑ x , y ∈ C d λ ( x , y ) ≤ 2 ∣ C ∣ T − T 2 λ n . \sum_{x,y\in C}d_\lambda(x,y)\le2|C|T-\frac{T^2}{\lambda n}. x , y ∈ C ∑ d λ ( x , y ) ≤ 2∣ C ∣ T − λn T 2 .
Since every codeword has weight at most W λ ≤ λ n W_\lambda\le\lambda n W λ ≤ λn , we have T ≤ ∣ C ∣ W λ ≤ ∣ C ∣ λ n T\le|C|W_\lambda\le|C|\lambda n T ≤ ∣ C ∣ W λ ≤ ∣ C ∣ λn . The function
f ( t ) = 2 ∣ C ∣ t − t 2 λ n f(t)=2|C|t-\frac{t^2}{\lambda n} f ( t ) = 2∣ C ∣ t − λn t 2
is increasing on [ 0 , ∣ C ∣ λ n ] [0,|C|\lambda n] [ 0 , ∣ C ∣ λn ] . Therefore,
∑ x , y ∈ C d λ ( x , y ) ≤ f ( T ) ≤ f ( ∣ C ∣ W λ ) = ∣ C ∣ 2 ( 2 W λ − W λ 2 λ n ) . \sum_{x,y\in C}d_\lambda(x,y)\le f(T)\le f(|C|W_\lambda)=|C|^2\left(2W_\lambda-\frac{W_\lambda^2}{\lambda n}\right). x , y ∈ C ∑ d λ ( x , y ) ≤ f ( T ) ≤ f ( ∣ C ∣ W λ ) = ∣ C ∣ 2 ( 2 W λ − λn W λ 2 ) .
Combining the upper and lower bounds for the total distance ∑ x , y ∈ C d λ ( x , y ) \sum_{x,y\in C}d_\lambda(x,y) ∑ x , y ∈ C d λ ( x , y ) gives
∣ C ∣ ( ∣ C ∣ − 1 ) d λ ( C ) ≤ ∣ C ∣ 2 ( 2 W λ − W λ 2 λ n ) , |C|(|C|-1)d_\lambda(C)\le|C|^2\left(2W_\lambda-\frac{W_\lambda^2}{\lambda n}\right), ∣ C ∣ ( ∣ C ∣ − 1 ) d λ ( C ) ≤ ∣ C ∣ 2 ( 2 W λ − λn W λ 2 ) ,
which immediately rearranges to
∣ C ∣ ≤ d λ ( C ) d λ ( C ) − 2 W λ + W λ 2 λ n . |C|\le\frac{d_\lambda(C)}{d_\lambda(C)-2W_\lambda+\frac{W_\lambda^2}{\lambda n}}. ∣ C ∣ ≤ d λ ( C ) − 2 W λ + λn W λ 2 d λ ( C ) .
With this bound, we can now provide a second Johnson-like bound.
Theorem 52. Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a real number. Let C ⊆ F q m n \mathcal{C} \subseteq\mathbb{F}_{q^m}^n C ⊆ F q m n be a not necessarily linear code with minimum λ \lambda λ -subfield distance d λ d_\lambda d λ . Then C \mathcal{C} C is ( w , λ n d λ ) (w,\lambda n d_\lambda) ( w , λn d λ ) -list decodable for every
w ≤ λ n ( 1 − 1 − d λ λ n + 1 λ 2 n 2 ) . w \le\lambda n \left(1-\sqrt{1-\frac{d_\lambda}{\lambda n}+\frac{1}{\lambda^2 n^2}}\right). w ≤ λn ( 1 − 1 − λn d λ + λ 2 n 2 1 ) .
Proof. We need to show that for any y ∈ F q m n y \in\mathbb{F}_{q^m}^n y ∈ F q m n we have that ∣ B λ ( y , w , n , q m ) ∩ C ∣ ≤ λ n d λ \lvert B_\lambda(y,w,n,q^m) \cap\mathcal{C}\rvert\le\lambda n d_\lambda ∣ B λ ( y , w , n , q m ) ∩ C ∣ ≤ λn d λ . By translation invariance of the λ \lambda λ -subfield metric, it is enough to consider balls centered at 0 0 0 . Let L = C ∩ B λ ( 0 , w , n , q m ) \mathcal{L}=\mathcal{C}\cap B_\lambda(0,w,n,q^m) L = C ∩ B λ ( 0 , w , n , q m ) and set L = ∣ L ∣ L=\lvert\mathcal{L}\rvert L = ∣ L ∣ . Then L \mathcal{L} L can be seen as a (not necessarily linear) code with minimum distance at least d λ d_\lambda d λ and all its codewords have λ \lambda λ -subfield weight at most w w w .
Applying Proposition 51 to L \mathcal{L} L hence gives
L ≤ d λ d λ − 2 w + w 2 λ n . L \le\frac{d_\lambda}{d_\lambda-2w+\frac{w^2}{\lambda n}}. L ≤ d λ − 2 w + λn w 2 d λ .
or equivalently, that
L ≤ λ n d λ λ n d λ − 2 λ n w + w 2 . L \le\frac{\lambda n d_\lambda}{\lambda n d_\lambda-2\lambda n w+w^2}. L ≤ λn d λ − 2 λn w + w 2 λn d λ .
Thus, to show that L ≤ λ n d λ L\le\lambda n d_\lambda L ≤ λn d λ , it suffices to ensure that λ n d λ − 2 λ n w + w 2 ≥ 1 \lambda n d_\lambda-2\lambda n w+w^2\ge1 λn d λ − 2 λn w + w 2 ≥ 1 , which is equivalent to ( λ n − w ) 2 ≥ λ 2 n 2 − λ n d λ + 1 (\lambda n-w)^2\ge\lambda^2n^2-\lambda n d_\lambda+1 ( λn − w ) 2 ≥ λ 2 n 2 − λn d λ + 1 . Since d λ ≤ λ n d_\lambda\le\lambda n d λ ≤ λn , the right-hand side is nonnegative. Thus, the condition is satisfied whenever
w ≤ λ n − λ 2 n 2 − λ n d λ + 1 , w\le\lambda n-\sqrt{\lambda^2n^2-\lambda n d_\lambda+1}, w ≤ λn − λ 2 n 2 − λn d λ + 1 ,
which is precisely the stated bound on w . □ w. \quad\square w . □
Reductions to the Hamming metric
In the λ \lambda λ -subfield metric, an error contained in the extension field contributes a weight of λ \lambda λ , whereas an error contained in the base field contributes only weight 1. This suggests representing each extension-field error by λ \lambda λ Hamming errors, thereby relating the λ \lambda λ -subfield metric to the classical Hamming metric. This leads us to the third Johnson-like bound.
First, we need to introduce some notation.
Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be an integer. Fix a set R ⊆ F q m R\subseteq\mathbb{F}_{q^m} R ⊆ F q m of representatives of the additive cosets of F q \mathbb{F}_q F q in F q m \mathbb{F}_{q^m} F q m , with 0 ∈ R 0\in R 0 ∈ R . Every x ∈ F q m x\in\mathbb{F}_{q^m} x ∈ F q m has a unique decomposition x = b + r x=b+r x = b + r , where b ∈ F q b\in\mathbb{F}_q b ∈ F q and r ∈ R r\in R r ∈ R . Define
σ : F q m → R , \sigma:\mathbb{F}_{q^m}\to R, σ : F q m → R ,
b + r ↦ r , b+r\mapsto r, b + r ↦ r ,
and
ψ : F q m → F q m λ , \psi:\mathbb{F}_{q^m}\to\mathbb{F}_{q^m}^{\lambda}, ψ : F q m → F q m λ ,
x ↦ ( σ ( x ) , … , σ ( x ) ⏟ λ − 1 , x ) . x\mapsto\left(\underbrace{\sigma(x),\ldots,\sigma(x)}_{\lambda-1},x\right). x ↦ λ − 1 σ ( x ) , … , σ ( x ) , x .
Extending ψ \psi ψ coordinatewise gives the injective map
ϕ : F q m n → F q m λ n , \phi:\mathbb{F}_{q^m}^n\to\mathbb{F}_{q^m}^{\lambda n}, ϕ : F q m n → F q m λn ,
x 1 , … , x n ↦ ( ψ ( x 1 ) , … , ψ ( x n ) ) . x_1,\ldots,x_n\mapsto\left(\psi(x_1),\ldots,\psi(x_n)\right). x 1 , … , x n ↦ ( ψ ( x 1 ) , … , ψ ( x n ) ) .
Since σ ( x ) = σ ( y ) \sigma(x)=\sigma(y) σ ( x ) = σ ( y ) if and only if x − y ∈ F q x-y\in\mathbb{F}_q x − y ∈ F q , we have
d H ( ψ ( x ) , ψ ( y ) ) = { 0 , x = y , 1 , x − y ∈ F q × , λ , x − y ∉ F q . d_H(\psi(x),\psi(y))=
\begin{cases}
0, & x=y,\\
1, & x-y\in\mathbb{F}_q^\times,\\
\lambda, & x-y\notin\mathbb{F}_q.
\end{cases} d H ( ψ ( x ) , ψ ( y )) = ⎩ ⎨ ⎧ 0 , 1 , λ , x = y , x − y ∈ F q × , x − y ∈ / F q .
That is ϕ \phi ϕ is an isometric embedding:
d H ( ϕ ( x ) , ϕ ( y ) ) = d λ ( x , y ) d_H(\phi(x),\phi(y))=d_\lambda(x,y) d H ( ϕ ( x ) , ϕ ( y )) = d λ ( x , y )
for all x , y ∈ F q m n x,y\in\mathbb{F}_{q^m}^n x , y ∈ F q m n .
Example 53. Let F 4 = F 2 ( α ) \mathbb{F}_4=\mathbb{F}_2(\alpha) F 4 = F 2 ( α ) with α 2 = α + 1 \alpha^2=\alpha+1 α 2 = α + 1 , and let λ = 2 \lambda=2 λ = 2 . The additive cosets of F 2 \mathbb{F}_2 F 2 are { 0 , 1 } \{0,1\} { 0 , 1 } and { α , α + 1 } \{\alpha,\alpha+1\} { α , α + 1 } . Thus, choosing R = { 0 , α } R=\{0,\alpha\} R = { 0 , α } gives σ ( 0 ) = 0 \sigma(0)=0 σ ( 0 ) = 0 and ψ ( 0 ) = ( 0 , 0 ) \psi(0)=(0,0) ψ ( 0 ) = ( 0 , 0 ) , σ ( 1 ) = 0 \sigma(1)=0 σ ( 1 ) = 0 and ψ ( 1 ) = ( 0 , 1 ) \psi(1)=(0,1) ψ ( 1 ) = ( 0 , 1 ) , σ ( α ) = α \sigma(\alpha)=\alpha σ ( α ) = α and ψ ( α ) = ( α , α ) \psi(\alpha)=(\alpha,\alpha) ψ ( α ) = ( α , α ) and finally σ ( α + 1 ) = α \sigma(\alpha+1)=\alpha σ ( α + 1 ) = α and ψ ( α + 1 ) = ( α , α + 1 ) \psi(\alpha+1)=(\alpha,\alpha+1) ψ ( α + 1 ) = ( α , α + 1 ) . For instance, if we consider the vector x = ( 1 , α + 1 ) x=(1,\alpha+1) x = ( 1 , α + 1 ) we get ϕ ( 1 , α + 1 ) = ( 0 , 1 , α , α + 1 ) \phi(1,\alpha+1)=(0,1,\alpha,\alpha+1) ϕ ( 1 , α + 1 ) = ( 0 , 1 , α , α + 1 ) .
Theorem 54. Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be an integer. Let C \mathcal{C} C be an [ n , k , d λ ] q m [n,k,d_\lambda]_{q^m} [ n , k , d λ ] q m linear code. If
w < λ n q m − 1 q m ( 1 − 1 − q m q m − 1 d λ λ n ) , w<\lambda n\frac{q^m-1}{q^m}\left(1-\sqrt{1-\frac{q^m}{q^m-1}\frac{d_\lambda}{\lambda n}}\right), w < λn q m q m − 1 ( 1 − 1 − q m − 1 q m λn d λ ) , then C \mathcal{C} C is ( w , L ) (w,L) ( w , L ) -list decodable with
L ≤ λ n q m d λ . L\le\lambda nq^m d_\lambda. L ≤ λn q m d λ .
Proof. The image ϕ ( C ) ⊆ F q m λ n \phi(\mathcal{C})\subseteq\mathbb{F}_{q^m}^{\lambda n} ϕ ( C ) ⊆ F q m λn is a (not necessarily linear) code with minimum Hamming distance d λ d_\lambda d λ . Moreover, for every received word r ∈ F q m n r\in\mathbb{F}_{q^m}^n r ∈ F q m n , we have that
∣ C ∩ B λ ( r , w ) ∣ = ∣ ϕ ( C ) ∩ B H ( ϕ ( r ) , w ) ∣ . \left|\mathcal{C}\cap B_\lambda(r,w)\right|=\left|\phi(\mathcal{C})\cap B_H(\phi(r),w)\right|. ∣ C ∩ B λ ( r , w ) ∣ = ∣ ϕ ( C ) ∩ B H ( ϕ ( r ) , w ) ∣ .
Thus, applying Theorem 15 to ϕ ( C ) \phi(\mathcal{C}) ϕ ( C ) gives the result. □
We again get that for λ = 1 \lambda=1 λ = 1 the bound coincides with the Hamming-metric bound in Theorem 15.
A Guruswami–Sudan Johnson Bound
The classical Hamming-metric Johnson bound can be obtained by embedding the alphabet F q m \mathbb{F}_{q^m} F q m into a Euclidean space, in such a way that distances between symbols are represented by inner products. Guruswami and Sudan [11 ] use this geometric viewpoint to derive a Johnson-type bound which can also be applied to other metrics. We adapt their argument to weight functions on finite abelian groups and then specialize it to the λ \lambda λ -subfield weight.
We first recall the following bounds on sets of unit vectors, corresponding to [11 Lemmas 3 and 4] .
Lemma 55. Let u 1 , … , u M ∈ R N u_1,\ldots,u_M\in\mathbb{R}^N u 1 , … , u M ∈ R N be unit vectors.
(1) If ⟨ u i , u j ⟩ < 0 \langle u_i,u_j\rangle<0 ⟨ u i , u j ⟩ < 0 for all i ≠ j i\ne j i = j , then M ≤ 2 N M\le2N M ≤ 2 N .
(2) If there exists ε > 0 \varepsilon>0 ε > 0 such that ⟨ u i , u j ⟩ < − ε \langle u_i,u_j\rangle<-\varepsilon ⟨ u i , u j ⟩ < − ε for all i ≠ j i\ne j i = j , then M ≤ 1 + 1 ε M\le1+\frac{1}{\varepsilon} M ≤ 1 + ε 1 .
In order to embed our metric space into a space with an inner product, we will require the following proposition, yielding a sufficient condition:
Proposition 56. Let G G G be a finite abelian group of size a a a and let w : G → R w:G\to\mathbb{R} w : G → R be a symmetric weight function, i.e., w ( g ) = w ( − g ) w(g)=w(-g) w ( g ) = w ( − g ) for all g ∈ G g\in G g ∈ G . Let us define the average weight as
ω = 1 a ∑ g ∈ G w ( g ) . \omega=\frac{1}{a}\sum_{g\in G}w(g). ω = a 1 g ∈ G ∑ w ( g ) . If
∑ g ∈ G w ( g ) χ ( g ) ∈ R ≤ 0 \sum_{g\in G}w(g)\chi(g)\in\mathbb{R}_{\leq0} g ∈ G ∑ w ( g ) χ ( g ) ∈ R ≤ 0 for every nontrivial irreducible character χ \chi χ of G G G , then there exists a matrix A ∈ R a × a A\in\mathbb{R}^{a\times a} A ∈ R a × a such that
A T A = ( ω − w ( x − y ) ) x , y ∈ G A^{\mathsf T}A=\left(\omega-w(x-y)\right)_{x,y\in G} A T A = ( ω − w ( x − y ) ) x , y ∈ G and
A ( 1 , … , 1 ) T = 0. A(1,\ldots,1)^{\mathsf T}=0. A ( 1 , … , 1 ) T = 0. Proof. Let us first consider A T A A^{\mathsf T}A A T A . For this, we define the matrix
W = ( ω − w ( x − y ) ) x , y ∈ G ∈ R a × a W=\left(\omega-w(x-y)\right)_{x,y\in G}\in\mathbb{R}^{a\times a} W = ( ω − w ( x − y ) ) x , y ∈ G ∈ R a × a and note that since w ( g ) = w ( − g ) w(g)=w(-g) w ( g ) = w ( − g ) , we get that the matrix W W W is symmetric. Moreover,
W ( 1 , … , 1 ) T = 0 , W(1,\ldots,1)^{\mathsf T}=0, W ( 1 , … , 1 ) T = 0 , since every row of W W W sums to
a ω − ∑ g ∈ G w ( g ) = 0. a\omega-\sum_{g\in G}w(g)=0. aω − g ∈ G ∑ w ( g ) = 0. Hence, it is enough to show that W W W is positive semidefinite: in this case we may choose a real matrix A A A satisfying A T A = W A^{\mathsf T}A=W A T A = W , and the condition W ( 1 , … , 1 ) T = 0 W(1,\ldots,1)^{\mathsf T}=0 W ( 1 , … , 1 ) T = 0 implies A ( 1 , … , 1 ) T = 0 A(1,\ldots,1)^{\mathsf T}=0 A ( 1 , … , 1 ) T = 0 . To determine the eigenvalues of W W W , we identify vectors indexed by G G G with functions f : G → C f:G\to\mathbb{C} f : G → C . Then matrix multiplication gives
( W f ) ( x ) = ∑ y ∈ G ( ω − w ( x − y ) ) f ( y ) . (Wf)(x)=\sum_{y\in G}\left(\omega-w(x-y)\right)f(y). ( W f ) ( x ) = y ∈ G ∑ ( ω − w ( x − y ) ) f ( y ) . Thus W W W acts by convolution with the function h ( g ) = ω − w ( g ) h(g)=\omega-w(g) h ( g ) = ω − w ( g ) . Hence the characters of G G G diagonalize W W W . For the trivial character, i.e., χ 0 ( g ) = 1 \chi_0(g)=1 χ 0 ( g ) = 1 for all g ∈ G g\in G g ∈ G , the corresponding eigenvalue is
∑ g ∈ G ( ω − w ( g ) ) = 0. \sum_{g\in G}\left(\omega-w(g)\right)=0. g ∈ G ∑ ( ω − w ( g ) ) = 0. For every nontrivial character χ \chi χ , we may use the orthogonality of characters to get that
∑ g ∈ G ( ω − w ( g ) ) χ ( g ) = − ∑ g ∈ G w ( g ) χ ( g ) , \sum_{g\in G}\left(\omega-w(g)\right)\chi(g)=-\sum_{g\in G}w(g)\chi(g), g ∈ G ∑ ( ω − w ( g ) ) χ ( g ) = − g ∈ G ∑ w ( g ) χ ( g ) , which is nonnegative by assumption. Thus all eigenvalues of W W W are nonnegative, and the claim follows. □
For finite fields, the character condition in Proposition 56 can be replaced by a condition involving hyperplanes.
Proposition 57. Let q = p h q=p^h q = p h be a prime power and let w : F q → R w:\mathbb{F}_q\to\mathbb{R} w : F q → R be a weight function which is definite and invariant under nonzero multiplication, i.e., w ( 0 ) = 0 w(0)=0 w ( 0 ) = 0 and w ( x ) = w ( a x ) w(x)=w(ax) w ( x ) = w ( a x ) for all a ∈ F p × a\in\mathbb{F}_p^\times a ∈ F p × . We then define the average weight on F q \mathbb{F}_q F q to be
ω = 1 q ∑ x ∈ F q w ( x ) . \omega=\frac{1}{q}\sum_{x\in\mathbb{F}_q}w(x). ω = q 1 x ∈ F q ∑ w ( x ) .
If
p q ∑ x ∈ H w ( x ) ≤ ω \frac{p}{q}\sum_{x\in H}w(x)\leq\omega q p x ∈ H ∑ w ( x ) ≤ ω
for every F p \mathbb{F}_p F p -hyperplane H ⊆ F q H\subseteq\mathbb{F}_q H ⊆ F q , then there exists a matrix A ∈ R q × q A\in\mathbb{R}^{q\times q} A ∈ R q × q such that
A T A = ( ω − w ( x − y ) ) x , y ∈ F q A^{\mathsf{T}}A=\left(\omega-w(x-y)\right)_{x,y\in\mathbb{F}_q} A T A = ( ω − w ( x − y ) ) x , y ∈ F q
and
A ( 1 , … , 1 ) T = 0. A(1,\ldots,1)^{\mathsf{T}}=0. A ( 1 , … , 1 ) T = 0.
Proof. The additive characters of F q \mathbb{F}_q F q are of the form
χ a ( x ) = ζ p Tr F q / F p ( a x ) , \chi_a(x)=\zeta_p^{\operatorname{Tr}_{\mathbb{F}_q/\mathbb{F}_p}(ax)}, χ a ( x ) = ζ p Tr F q / F p ( a x ) ,
where ζ p = e 2 π i / p \zeta_p=e^{2\pi i/p} ζ p = e 2 π i / p . For a ≠ 0 a\neq0 a = 0 , the kernel of χ a \chi_a χ a is an F p \mathbb{F}_p F p -hyperplane. Using the invariance w ( x ) = w ( m x ) w(x)=w(mx) w ( x ) = w ( m x ) for m ∈ F p × m\in\mathbb{F}_p^\times m ∈ F p × , we obtain
∑ x ∈ F q w ( x ) χ a ( x ) = 1 p − 1 ( − ∑ x ∈ F q × w ( x ) + p ∑ x ∈ F q × χ a ( x ) = 1 w ( x ) ) . \sum_{x\in\mathbb{F}_q}w(x)\chi_a(x)=\frac{1}{p-1}\left(-\sum_{x\in\mathbb{F}_q^\times}w(x)+p\sum_{\substack{x\in\mathbb{F}_q^\times\\\chi_a(x)=1}}w(x)\right). x ∈ F q ∑ w ( x ) χ a ( x ) = p − 1 1 − x ∈ F q × ∑ w ( x ) + p x ∈ F q × χ a ( x ) = 1 ∑ w ( x ) .
Thus, the assumed hyperplane inequality implies that this quantity is in R ≤ 0 \mathbb{R}_{\leq0} R ≤ 0 and we can apply Proposition 56. □
We can now apply the geometric argument of [11 Theorem 1] , which we quickly recall here for completeness.
Theorem 58 (Johnson bound). Let G G G be a finite abelian group of size a a a and w w w be a symmetric weight function, which satisfies the assumptions of Proposition 56, and assume additionally that w ( 0 ) = 0 w(0)=0 w ( 0 ) = 0 . Let us extend w w w additively to G n G^n G n , i.e., w ( x ) = ∑ i = 1 n w ( x i ) w(x)=\sum_{i=1}^n w(x_i) w ( x ) = ∑ i = 1 n w ( x i ) . Let ω \omega ω denote the average weight, i.e.,
ω = 1 a ∑ g ∈ G w ( g ) . \omega=\frac{1}{a}\sum_{g\in G}w(g). ω = a 1 g ∈ G ∑ w ( g ) .
Let C ⊆ G n C\subseteq G^n C ⊆ G n and let w max > 0 w_{\max}>0 w m a x > 0 and d d d be real numbers such that w ( c ) ≤ w max w(c)\leq w_{\max} w ( c ) ≤ w m a x for all c ∈ C c\in C c ∈ C and w ( c − c ′ ) ≥ d w(c-c')\geq d w ( c − c ′ ) ≥ d for all distinct c , c ′ ∈ C c,c'\in C c , c ′ ∈ C where 0 < d < n ω 0<d<n\omega 0 < d < nω . If
w max < n ω ( 1 − 1 − d n ω ) , w_{\max}<n\omega\left(1-\sqrt{1-\frac{d}{n\omega}}\right), w m a x < nω ( 1 − 1 − nω d ) ,
then ∣ C ∣ ≤ 2 n a |C|\leq2na ∣ C ∣ ≤ 2 na . Moreover, if w max < n ω w_{\max}<n\omega w m a x < nω and d − 2 w max + w max 2 n ω > 0 d-2w_{\max}+\frac{w_{\max}^2}{n\omega}>0 d − 2 w m a x + nω w m a x 2 > 0 then
∣ C ∣ ≤ d d − 2 w max + w max 2 n ω . |C|\leq\frac{d}{d-2w_{\max}+\frac{w_{\max}^2}{n\omega}}. ∣ C ∣ ≤ d − 2 w m a x + nω w m a x 2 d .
Proof. Let us write d = n ω ( 1 − δ ) d=n\omega(1-\delta) d = nω ( 1 − δ ) , and w max = n ω ( 1 − γ ) w_{\max}=n\omega(1-\gamma) w m a x = nω ( 1 − γ ) , for some real numbers δ \delta δ and γ \gamma γ . For each g ∈ G g\in G g ∈ G , let a g a_g a g denote the column of the matrix A A A from Proposition 56 indexed by g g g . Thus,
⟨ a g , a g ′ ⟩ = ω − w ( g − g ′ ) . \langle a_g,a_{g'}\rangle=\omega-w(g-g'). ⟨ a g , a g ′ ⟩ = ω − w ( g − g ′ ) .
For c ∈ C c\in C c ∈ C , define
u c = ( a c 1 ∣ ⋯ ∣ a c n ) ∈ R n a . u_c=(a_{c_1}\mid\cdots\mid a_{c_n})\in\mathbb{R}^{na}. u c = ( a c 1 ∣ ⋯ ∣ a c n ) ∈ R na .
Hence, we get that
⟨ u c , u c ′ ⟩ = n ω − w ( c − c ′ ) . \langle u_c,u_{c'}\rangle=n\omega-w(c-c'). ⟨ u c , u c ′ ⟩ = nω − w ( c − c ′ ) .
For α ≥ 0 \alpha\geq0 α ≥ 0 and distinct c , c ′ ∈ C c,c'\in C c , c ′ ∈ C , we then obtain
⟨ u c − α u 0 , u c ′ − α u 0 ⟩ = n ω − w ( c − c ′ ) − α ( 2 n ω − w ( c ) − w ( c ′ ) ) + α 2 n ω ≤ n ω ( δ − 2 α γ + α 2 ) . \begin{aligned}
\langle u_c-\alpha u_0,u_{c'}-\alpha u_0\rangle
&=n\omega-w(c-c')-\alpha(2n\omega-w(c)-w(c'))+\alpha^2n\omega\\
&\leq n\omega(\delta-2\alpha\gamma+\alpha^2).
\end{aligned} ⟨ u c − α u 0 , u c ′ − α u 0 ⟩ = nω − w ( c − c ′ ) − α ( 2 nω − w ( c ) − w ( c ′ )) + α 2 nω ≤ nω ( δ − 2 α γ + α 2 ) .
Similarly, we get that
∥ u c − α u 0 ∥ 2 ≤ n ω ( 1 − 2 α γ + α 2 ) , \|u_c-\alpha u_0\|^2\leq n\omega(1-2\alpha\gamma+\alpha^2), ∥ u c − α u 0 ∥ 2 ≤ nω ( 1 − 2 α γ + α 2 ) ,
where ∥ u ∥ = ⟨ u , u ⟩ \|u\|=\sqrt{\langle u,u\rangle} ∥ u ∥ = ⟨ u , u ⟩ denotes the Euclidean norm.
Suppose that 0 < w max < n ω 0<w_{\max}<n\omega 0 < w m a x < nω , so that 0 < γ < 1 0<\gamma<1 0 < γ < 1 . For 0 ≤ α < 1 0\leq\alpha<1 0 ≤ α < 1 , the vectors u c − α u 0 u_c-\alpha u_0 u c − α u 0 are nonzero, since ∥ u c ∥ = ∥ u 0 ∥ = n ω \|u_c\|=\|u_0\|=\sqrt{n\omega} ∥ u c ∥ = ∥ u 0 ∥ = nω . We may therefore define the unit vectors
v c = u c − α u 0 ∥ u c − α u 0 ∥ ∈ R n a . v_c=\frac{u_c-\alpha u_0}{\|u_c-\alpha u_0\|}\in\mathbb{R}^{na}. v c = ∥ u c − α u 0 ∥ u c − α u 0 ∈ R na .
Let c , c ′ c,c' c , c ′ be distinct codewords. If δ − 2 α γ + α 2 < 0 \delta-2\alpha\gamma+\alpha^2<0 δ − 2 α γ + α 2 < 0 , we get that
⟨ v c , v c ′ ⟩ ≤ δ − 2 α γ + α 2 1 − 2 α γ + α 2 . \langle v_c,v_{c'}\rangle\leq\frac{\delta-2\alpha\gamma+\alpha^2}{1-2\alpha\gamma+\alpha^2}. ⟨ v c , v c ′ ⟩ ≤ 1 − 2 α γ + α 2 δ − 2 α γ + α 2 .
Here we use that the numerator is negative and that
0 < ∥ u c − α u 0 ∥ ∥ u c ′ − α u 0 ∥ ≤ n ω ( 1 − 2 α γ + α 2 ) . 0<\|u_c-\alpha u_0\|\|u_{c'}-\alpha u_0\|\leq n\omega(1-2\alpha\gamma+\alpha^2). 0 < ∥ u c − α u 0 ∥∥ u c ′ − α u 0 ∥ ≤ nω ( 1 − 2 α γ + α 2 ) .
For the first bound, the assumption on w max w_{\max} w m a x is equivalent to γ > δ \gamma>\sqrt{\delta} γ > δ . Thus, if we set α = δ \alpha=\sqrt{\delta} α = δ , we get that
δ − 2 α γ + α 2 = 2 δ ( δ − γ ) < 0 \delta-2\alpha\gamma+\alpha^2=2\sqrt{\delta}(\sqrt{\delta}-\gamma)<0 δ − 2 α γ + α 2 = 2 δ ( δ − γ ) < 0
and the unit vectors v c v_c v c , indexed by c ∈ C c\in C c ∈ C , have strictly negative pairwise inner products. We can hence apply Lemma 55 in R n a \mathbb{R}^{na} R na to get that
∣ C ∣ ≤ 2 n a . |C|\leq2na. ∣ C ∣ ≤ 2 na .
For the second bound, we observe that
d − 2 w max + w max 2 n ω = n ω ( γ 2 − δ ) . d-2w_{\max}+\frac{w_{\max}^2}{n\omega}=n\omega(\gamma^2-\delta). d − 2 w m a x + nω w m a x 2 = nω ( γ 2 − δ ) .
Thus the assumption d − 2 w max + w max 2 n ω > 0 d-2w_{\max}+\frac{w_{\max}^2}{n\omega}>0 d − 2 w m a x + nω w m a x 2 > 0 implies γ 2 > δ \gamma^2>\delta γ 2 > δ . If we now set α = γ \alpha=\gamma α = γ , we get that
⟨ v c , v c ′ ⟩ ≤ δ − γ 2 1 − γ 2 = − ε , \langle v_c,v_{c'}\rangle\leq\frac{\delta-\gamma^2}{1-\gamma^2}=-\varepsilon, ⟨ v c , v c ′ ⟩ ≤ 1 − γ 2 δ − γ 2 = − ε ,
where ε = γ 2 − δ 1 − γ 2 > 0 \varepsilon=\frac{\gamma^2-\delta}{1-\gamma^2}>0 ε = 1 − γ 2 γ 2 − δ > 0 . For every 0 < ε ′ < ε 0<\varepsilon'<\varepsilon 0 < ε ′ < ε , these inner products are strictly less than − ε ′ -\varepsilon' − ε ′ .
We can now apply Lemma 55, which gives that
∣ C ∣ ≤ 1 + 1 ε = 1 − δ γ 2 − δ = d d − 2 w max + w max 2 n ω . |C|\le1+\frac{1}{\varepsilon}=\frac{1-\delta}{\gamma^2-\delta}=\frac{d}{d-2w_{\max}+\frac{w_{\max}^2}{n\omega}}. ∣ C ∣ ≤ 1 + ε 1 = γ 2 − δ 1 − δ = d − 2 w m a x + nω w m a x 2 d .
We now specialize this bound to the λ \lambda λ -subfield weight on F q m \mathbb{F}_{q^m} F q m , where λ ≥ 1 \lambda\ge1 λ ≥ 1 . Its average weight is given by
ω λ ⋆ = ( q m − q ) λ + ( q − 1 ) q m . \omega_\lambda^\star=\frac{(q^m-q)\lambda+(q-1)}{q^m}. ω λ ⋆ = q m ( q m − q ) λ + ( q − 1 ) .
To apply Theorem 58, we first need to verify the hyperplane condition in Proposition 57.
Let q = p h q=p^h q = p h be a prime power. The weight w λ w_\lambda w λ is positive definite and is invariant under multiplication by F p × \mathbb{F}_p^\times F p × . Let H ⊆ F q m H\subseteq\mathbb{F}_{q^m} H ⊆ F q m be an F p \mathbb{F}_p F p -hyperplane, and let s = ∣ H ∩ F q ∣ s=|H\cap\mathbb{F}_q| s = ∣ H ∩ F q ∣ . Since
dim F p ( H ∩ F q ) ≥ h − 1 , \dim_{\mathbb{F}_p}(H\cap\mathbb{F}_q)\ge h-1, dim F p ( H ∩ F q ) ≥ h − 1 ,
we have that s ≥ q / p s\ge q/p s ≥ q / p . Thus,
∑ x ∈ H w λ ( x ) = ( s − 1 ) + λ ( q m p − s ) ≤ q p − 1 + λ q m − q p . \sum_{x\in H}w_\lambda(x)=(s-1)+\lambda\left(\frac{q^m}{p}-s\right)\le\frac{q}{p}-1+\lambda\frac{q^m-q}{p}. x ∈ H ∑ w λ ( x ) = ( s − 1 ) + λ ( p q m − s ) ≤ p q − 1 + λ p q m − q .
It follows that
p q m ∑ x ∈ H w λ ( x ) ≤ q − p + λ ( q m − q ) q m < ω λ ⋆ . \frac{p}{q^m}\sum_{x\in H}w_\lambda(x)\le\frac{q-p+\lambda(q^m-q)}{q^m}<\omega_\lambda^\star. q m p x ∈ H ∑ w λ ( x ) ≤ q m q − p + λ ( q m − q ) < ω λ ⋆ .
Thus the required embedding exists, and Theorem 58 gives the following Johnson-type bound:
Corollary 59 (Johnson-type bound for the λ \lambda λ -subfield metric). Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a real number. Let C ⊆ F q m C\subseteq\mathbb{F}_{q^m} C ⊆ F q m be a code with minimum λ \lambda λ -subfield distance 0 < d λ < n ω λ 0<d_\lambda<n\omega_\lambda 0 < d λ < n ω λ , where
ω λ = ( q m − q ) λ + ( q − 1 ) q m . \omega_\lambda=\frac{(q^m-q)\lambda+(q-1)}{q^m}. ω λ = q m ( q m − q ) λ + ( q − 1 ) . If
w < n ω λ ( 1 − 1 − d λ n ω λ ) , w<n\omega_\lambda\left(1-\sqrt{1-\frac{d_\lambda}{n\omega_\lambda}}\right), w < n ω λ ( 1 − 1 − n ω λ d λ ) , then the code C C C is ( w , L ) (w,L) ( w , L ) -list decodable in the λ \lambda λ -subfield metric with
L ≤ min { 2 n q m , d d − 2 w max + w max 2 n ω } . L\le\min\left\{2nq^m,\frac{d}{d-2w_{\max}+\frac{w_{\max}^2}{n\omega}}\right\}. L ≤ min { 2 n q m , d − 2 w m a x + nω w m a x 2 d } . If we additionally have that
d λ − 2 w + w 2 n ω λ > 0 , d_\lambda-2w+\frac{w^2}{n\omega_\lambda}>0, d λ − 2 w + n ω λ w 2 > 0 , then we get the sharper bound
L ≤ d λ d λ − 2 w + w 2 n ω λ . L\le\frac{d_\lambda}{d_\lambda-2w+\frac{w^2}{n\omega_\lambda}}. L ≤ d λ − 2 w + n ω λ w 2 d λ .
Proof. Let us fix a vector y ∈ F q m n y \in\mathbb{F}_{q^m}^{n} y ∈ F q m n and consider
L = C ∩ B λ ( y , w , n , q m ) . \mathcal{L} = \mathcal{C} \cap B_{\lambda}(y,w,n,q^m). L = C ∩ B λ ( y , w , n , q m ) .
By the translation invariance of the λ \lambda λ -subfield metric, we get that the translated set L − y \mathcal{L}-y L − y has λ \lambda λ -subfield weight at most w w w and minimum distance at least d λ d_{\lambda} d λ . Applying Theorem 58 with G = ( F q m , + ) G=(\mathbb{F}_{q^m},+) G = ( F q m , + ) and ω = ω λ \omega=\omega_{\lambda} ω = ω λ gives the claimed bounds on ∣ L ∣ |\mathcal{L}| ∣ L ∣ .
If we set λ = 1 \lambda=1 λ = 1 , we again recover the Hamming-metric Johnson bound from Theorem 15 .
Comparison of the Johnson-Type Bounds
We now compare the Johnson-type decoding radii of the different bounds. Although the list sizes are relevant, our purpose here is to determine how far each argument guarantees list decodability. For fixed q q q , m m m , λ \lambda λ , as all four approaches provide polynomial list-size bounds, we will only focus on the radii rather than comparing the different list-size estimates.
To ease the notation, we will write Q = q m Q=q^m Q = q m and define δ = d λ λ n \delta=\frac{d_{\lambda}}{\lambda n} δ = λn d λ , and ρ = w n \rho=\frac{w}{n} ρ = n w . Thus δ \delta δ denotes the relative minimum distance, normalized by the maximum possible weight λ n \lambda n λn , while ρ \rho ρ denotes the decoding radius per coordinate. Hence, ρ \rho ρ may exceed 1.
Recall that the average λ \lambda λ -subfield weight in F Q \mathbb{F}_Q F Q is given by
ω λ = q − 1 + λ ( Q − q ) Q . \omega_{\lambda}=\frac{q-1+\lambda(Q-q)}{Q}. ω λ = Q q − 1 + λ ( Q − q ) .
We denote the normalized radii obtained from Corollary 50 , Theorem 52 , Theorem 54 , and Corollary 59 by ρ H a m \rho_{\mathrm{Ham}} ρ Ham , ρ P l o t k i n \rho_{\mathrm{Plotkin}} ρ Plotkin , ρ e m b \rho_{\mathrm{emb}} ρ emb , and ρ G S \rho_{\mathrm{GS}} ρ GS , respectively.
The normalized radii are given by
ρ H a m ( δ ) = 1 − 1 − δ , \rho_{\mathrm{Ham}}(\delta)=1-\sqrt{1-\delta}, ρ Ham ( δ ) = 1 − 1 − δ ,
ρ P l o t k i n ( δ ) = λ ( 1 − 1 − δ + 1 λ 2 n 2 ) , \rho_{\mathrm{Plotkin}}(\delta)=\lambda\left(1-\sqrt{1-\delta+\frac{1}{\lambda^2n^2}}\right), ρ Plotkin ( δ ) = λ ( 1 − 1 − δ + λ 2 n 2 1 ) ,
ρ e m b ( δ ) = λ Q − 1 Q ( 1 − 1 − Q Q − 1 δ ) , \rho_{\mathrm{emb}}(\delta)=\lambda\frac{Q-1}{Q}\left(1-\sqrt{1-\frac{Q}{Q-1}\delta}\right), ρ emb ( δ ) = λ Q Q − 1 ( 1 − 1 − Q − 1 Q δ ) ,
ρ G S ( δ ) = ω λ ( 1 − 1 − λ δ ω λ ) . \rho_{\mathrm{GS}}(\delta)=\omega_{\lambda}\left(1-\sqrt{1-\frac{\lambda\delta}{\omega_{\lambda}}}\right). ρ GS ( δ ) = ω λ ( 1 − 1 − ω λ λ δ ) .
We note that Corollary 50 applies for 0 < δ ≤ 1 0<\delta\leq1 0 < δ ≤ 1 , while Theorem 52 gives a nonnegative decoding radius for 1 λ 2 n 2 ≤ δ ≤ 1 \frac{1}{\lambda^2n^2}\leq\delta\leq1 λ 2 n 2 1 ≤ δ ≤ 1 . Theorem 54 additionally requires λ \lambda λ to be an integer and 0 < δ < Q − 1 Q 0<\delta<\frac{Q-1}{Q} 0 < δ < Q Q − 1 . Corollary 59 requires 0 < δ < ω λ λ 0<\delta<\frac{\omega_{\lambda}}{\lambda} 0 < δ < λ ω λ .
For a fixed x > 0 x>0 x > 0 , let us consider the function
F b ( x ) = b ( 1 − 1 − x b ) = x 1 + 1 − x / b . F_b(x)=b\left(1-\sqrt{1-\frac{x}{b}}\right)=\frac{x}{1+\sqrt{1-x/b}}. F b ( x ) = b ( 1 − 1 − b x ) = 1 + 1 − x / b x .
This expression is strictly decreasing in b b b for b ≥ x b\geq x b ≥ x . If we set
β λ = λ Q − 1 Q , \beta_{\lambda}=\lambda\frac{Q-1}{Q}, β λ = λ Q Q − 1 ,
then
β λ − ω λ = ( q − 1 ) ( λ − 1 ) Q ≥ 0 , \beta_{\lambda}-\omega_{\lambda}=\frac{(q-1)(\lambda-1)}{Q}\geq0, β λ − ω λ = Q ( q − 1 ) ( λ − 1 ) ≥ 0 ,
and we have
ω λ ≤ β λ < λ . \omega_{\lambda} \le\beta_{\lambda} < \lambda. ω λ ≤ β λ < λ .
By setting x = λ δ x = \lambda\delta x = λ δ , the monotonicity of F b ( x ) F_b(x) F b ( x ) then gives
λ ρ H a m ( δ ) < ρ e m b ( δ ) ≤ ρ G S ( δ ) . \lambda\rho_{\mathrm{Ham}}(\delta) < \rho_{\mathrm{emb}}(\delta) \le\rho_{\mathrm{GS}}(\delta). λ ρ Ham ( δ ) < ρ emb ( δ ) ≤ ρ GS ( δ ) .
Since 1 λ 2 n 2 > 0 \frac{1}{\lambda^{2}n^{2}} > 0 λ 2 n 2 1 > 0 , we have that
ρ P l o t k i n ( δ ) = λ ( 1 − 1 − δ + 1 λ 2 n 2 ) < λ ( 1 − 1 − δ ) = λ ρ H a m ( δ ) . \rho_{\mathrm{Plotkin}}(\delta) = \lambda\left(1-\sqrt{1-\delta+\frac{1}{\lambda^{2}n^{2}}}\right) < \lambda\left(1-\sqrt{1-\delta}\right) = \lambda\rho_{\mathrm{Ham}}(\delta). ρ Plotkin ( δ ) = λ ( 1 − 1 − δ + λ 2 n 2 1 ) < λ ( 1 − 1 − δ ) = λ ρ Ham ( δ ) .
In particular, since λ ≥ 1 \lambda\ge1 λ ≥ 1 , we get that
ρ G S ( δ ) > ρ H a m ( δ ) . \rho_{\mathrm{GS}}(\delta) > \rho_{\mathrm{Ham}}(\delta). ρ GS ( δ ) > ρ Ham ( δ ) .
For non-integer values of λ \lambda λ , the embedding argument does not apply, but the comparisons
ρ G S ( δ ) > λ ρ H a m ( δ ) ≥ ρ H a m ( δ ) , \rho_{\mathrm{GS}}(\delta) > \lambda\rho_{\mathrm{Ham}}(\delta) \ge\rho_{\mathrm{Ham}}(\delta), ρ GS ( δ ) > λ ρ Ham ( δ ) ≥ ρ Ham ( δ ) ,
and
ρ G S ( δ ) > ρ P l o t k i n ( δ ) \rho_{\mathrm{GS}}(\delta) > \rho_{\mathrm{Plotkin}}(\delta) ρ GS ( δ ) > ρ Plotkin ( δ )
are still valid.
Thus ρ G S ( δ ) \rho_{\mathrm{GS}}(\delta) ρ GS ( δ ) is the largest of these four radii. However, if δ ≥ ω λ / λ \delta\ge\omega_{\lambda}/\lambda δ ≥ ω λ / λ , Corollary 59 does not apply, while another bound may still be applicable.
Figure 1. Comparison of the normalized Johnson radii.
For the parameters q = 2 q = 2 q = 2 , m = 8 m = 8 m = 8 and λ = 2 \lambda= 2 λ = 2 , we have that λ = 2 \lambda= 2 λ = 2 , β λ = 510 256 \beta_{\lambda} = \frac{510}{256} β λ = 256 510 , and ω λ = 509 256 \omega_{\lambda} = \frac{509}{256} ω λ = 256 509 . As these values are close, only two curves are distinguishable in the plot.
Further Classical Bounds
The original paper introducing the λ \lambda λ -subfield metric [7 ] established several classical coding-theoretic bounds, including Singleton-, Plotkin-, sphere-packing and Gilbert–Varshamov-type bounds. In this section, we complement these results with a Griesmer- and an Elias-type bounds.
A Griesmer-Type Bound
We first relate the minimum λ \lambda λ -subfield distance of a linear code to its minimum Hamming distance.
Lemma 60. Let w w w be a weight function on F q m \mathbb{F}_{q^m} F q m , which can be extended additively to F q m n \mathbb{F}_{q^m}^n F q m n . Let us define its average weight on F q m \mathbb{F}_{q^m} F q m as
ω = 1 q m − 1 ∑ a ∈ F q m × w ( a ) . \omega= \frac{1}{q^m-1}\sum_{a\in\mathbb{F}_{q^m}^{\times}} w(a). ω = q m − 1 1 a ∈ F q m × ∑ w ( a ) . Let C ⊆ F q m n \mathcal{C} \subseteq\mathbb{F}_{q^m}^n C ⊆ F q m n be linear code of minimum distance d d d , then
d ≤ ω d H ( C ) . d \leq\omega d_H(\mathcal{C}). d ≤ ω d H ( C ) .
Proof. Let c ∈ C ∖ { 0 } c \in\mathcal{C} \setminus\{0\} c ∈ C ∖ { 0 } be a codeword of minimum Hamming weight d H ( C ) d_H(\mathcal{C}) d H ( C ) . By averaging over the w w w -weight for all α c \alpha c α c over α ∈ F q m × \alpha\in\mathbb{F}_{q^m}^{\times} α ∈ F q m × we get
1 q m − 1 ∑ α ∈ F q m × w ( α c ) = ω d H ( C ) . \frac{1}{q^m-1}\sum_{\alpha\in\mathbb{F}_{q^m}^{\times}} w(\alpha c) = \omega d_H(\mathcal{C}). q m − 1 1 α ∈ F q m × ∑ w ( α c ) = ω d H ( C ) .
Hence at least one nonzero scalar multiple of c c c has w w w -weight at most this average, i.e., for some α c ∈ C \alpha c \in\mathcal{C} α c ∈ C , we have that w ( α c ) ≤ ω d H ( C ) w(\alpha c) \leq\omega d_H(\mathcal{C}) w ( α c ) ≤ ω d H ( C ) and since d ≤ w ( α c ) d \leq w(\alpha c) d ≤ w ( α c ) we get the claim. □
For the λ \lambda λ -subfield weight, we observe that averaging over all nonzero elements in F q m \mathbb{F}_{q^m} F q m gives
ω λ ⋆ = q − 1 + λ ( q m − q ) q m − 1 . \omega_\lambda^{\star} = \frac{q-1+\lambda(q^m-q)}{q^m-1}. ω λ ⋆ = q m − 1 q − 1 + λ ( q m − q ) .
From this, we can get a Griesmer-type bound for the λ \lambda λ -subfield metric.
Theorem 61 (Griesmer-type bound). Let C ⊆ F q m n \mathcal{C} \subseteq\mathbb{F}_{q^m}^n C ⊆ F q m n be an [ n , k , d λ ] q m [n,k,d_\lambda]_{q^m} [ n , k , d λ ] q m linear code. Then
n ≥ ∑ i = 0 k − 1 ⌈ d λ q m i ω λ ⋆ ⌉ . n \geq\sum_{i=0}^{k-1}\left\lceil\frac{d_\lambda}{q^{mi}\omega_\lambda^{\star}}\right\rceil. n ≥ i = 0 ∑ k − 1 ⌈ q mi ω λ ⋆ d λ ⌉ .
Proof. By Lemma 60, we get that
d H ( C ) ≥ d λ ω λ ⋆ . d_H(\mathcal{C}) \geq\frac{d_\lambda}{\omega_\lambda^{\star}}. d H ( C ) ≥ ω λ ⋆ d λ .
Now we simply apply the classical Hamming-metric Griesmer bound over F q m \mathbb{F}_{q^m} F q m to get
n ≥ ∑ i = 0 k − 1 ⌈ d H ( C ) q m i ⌉ ≥ ∑ i = 0 k − 1 ⌈ d λ q m i ω λ ⋆ ⌉ . n \geq\sum_{i=0}^{k-1}\left\lceil\frac{d_H(\mathcal{C})}{q^{mi}}\right\rceil\geq\sum_{i=0}^{k-1}\left\lceil\frac{d_\lambda}{q^{mi}\omega_\lambda^{\star}}\right\rceil. n ≥ i = 0 ∑ k − 1 ⌈ q mi d H ( C ) ⌉ ≥ i = 0 ∑ k − 1 ⌈ q mi ω λ ⋆ d λ ⌉ .
□
An Elias–Bassalygo-Type Bound
We next show that the classical Elias–Bassalygo averaging argument in the Hamming metric extends directly to the λ \lambda λ -subfield metric. The essential ingredient is the translation invariance of the λ \lambda λ -subfield metric. Recall that we denote by
B λ ( y , r , n , q m ) = { x ∈ F q m n ∣ d λ ( x , y ) ≤ r } B_\lambda(y,r,n,q^m)=\{x\in\mathbb{F}_{q^m}^n\mid d_\lambda(x,y)\leq r\} B λ ( y , r , n , q m ) = { x ∈ F q m n ∣ d λ ( x , y ) ≤ r }
the λ \lambda λ -subfield ball around y ∈ F q m n y\in\mathbb{F}_{q^m}^n y ∈ F q m n of radius r r r and that V λ ( r , n , q m ) V_\lambda(r,n,q^m) V λ ( r , n , q m ) denotes the volume of a λ \lambda λ -subfield ball.
Lemma 62 (Elias–Bassalygo averaging). Let C ⊆ F q m n \mathcal{C} \subseteq\mathbb{F}_{q^m}^n C ⊆ F q m n be a code and let r ≥ 0 r \ge0 r ≥ 0 . Then there exists y ∈ F q m n y \in\mathbb{F}_{q^m}^n y ∈ F q m n such that
∣ C ∩ B λ ( y , r , n , q m ) ∣ ≥ ∣ C ∣ V λ ( r , n , q m ) q m n . |\mathcal{C} \cap B_\lambda(y,r,n,q^m)| \ge\frac{|\mathcal{C}|V_\lambda(r,n,q^m)}{q^{mn}}. ∣ C ∩ B λ ( y , r , n , q m ) ∣ ≥ q mn ∣ C ∣ V λ ( r , n , q m ) .
Proof. We consider the set
P = { ( c , y ) ∈ C × F q m n ∣ d λ ( c , y ) ≤ r } . \mathcal{P}=\{(c,y)\in\mathcal{C}\times\mathbb{F}_{q^m}^n\mid d_\lambda(c,y)\le r\}. P = {( c , y ) ∈ C × F q m n ∣ d λ ( c , y ) ≤ r } .
and prove the statement using a double counting argument. When counting with respect to c c c , the translation invariance gives that
∣ P ∣ = ∣ C ∣ V λ ( r , n , q m ) . |\mathcal{P}|=|\mathcal{C}|V_\lambda(r,n,q^m). ∣ P ∣ = ∣ C ∣ V λ ( r , n , q m ) .
On the other hand, when counting with respect to y y y , we get that
∣ P ∣ = ∑ y ∈ F q m n ∣ C ∩ B λ ( y , r , n , q m ) ∣ . |\mathcal{P}|=\sum_{y\in\mathbb{F}_{q^m}^n}|\mathcal{C}\cap B_\lambda(y,r,n,q^m)|. ∣ P ∣ = y ∈ F q m n ∑ ∣ C ∩ B λ ( y , r , n , q m ) ∣.
Hence, the average intersection size is given by
∣ C ∣ V λ ( r , n , q m ) q m n , \frac{|\mathcal{C}|V_\lambda(r,n,q^m)}{q^{mn}}, q mn ∣ C ∣ V λ ( r , n , q m ) ,
and therefore at least one center y y y has an intersection of at least this size. □
Combining this averaging argument with an estimate for the λ \lambda λ -subfield volume gives an Elias-type upper bound.
Theorem 63 (Elias-Bassalygo-type bound). Let C ⊆ F q m n \mathcal{C} \subseteq\mathbb{F}_{q^m}^n C ⊆ F q m n be a code of minimum λ \lambda λ -subfield distance d λ d_\lambda d λ . Suppose that every code of minimum distance at least d λ d_\lambda d λ contained in a λ \lambda λ -subfield ball of radius r r r has cardinality at most L ( r , d λ ) L(r,d_\lambda) L ( r , d λ ) . Then
∣ C ∣ ≤ q m n V λ ( r , n , q m ) L ( r , d λ ) . |\mathcal{C}| \le\frac{q^{mn}}{V_\lambda(r,n,q^m)}L(r,d_\lambda). ∣ C ∣ ≤ V λ ( r , n , q m ) q mn L ( r , d λ ) .
Proof. By Lemma 62, there exists a center y y y such that
∣ C ∩ B λ ( y , r , n , q m ) ∣ ≥ ∣ C ∣ V λ ( r , n , q m ) q m n . |\mathcal{C}\cap B_\lambda(y,r,n,q^m)|\ge\frac{|\mathcal{C}|V_\lambda(r,n,q^m)}{q^{mn}}. ∣ C ∩ B λ ( y , r , n , q m ) ∣ ≥ q mn ∣ C ∣ V λ ( r , n , q m ) .
The (not necessarily linear) subcode C ∩ B λ ( y , r , n , q m ) \mathcal{C}\cap B_\lambda(y,r,n,q^m) C ∩ B λ ( y , r , n , q m ) still has minimum distance at least d λ d_\lambda d λ , and by assumption its cardinality is at most L ( r , d λ ) L(r,d_\lambda) L ( r , d λ ) .
Thus
∣ C ∣ V λ ( r , n , q m ) q m n ≤ L ( r , d λ ) , \frac{|\mathcal{C}|V_\lambda(r,n,q^m)}{q^{mn}}\le L(r,d_\lambda), q mn ∣ C ∣ V λ ( r , n , q m ) ≤ L ( r , d λ ) ,
which gives the claim. □
In particular, inserting any of the Johnson-type list-size bounds from Section 6 into Theorem 63 yields an explicit Elias–Bassalygo-type bound for the λ \lambda λ -subfield metric. In particular, if we insert the list size of Corollary 50, we get the following bound:
Applying Corollary 50 in Theorem 63 gives the following explicit bound.
Corollary 64. Let λ ≥ 1 \lambda\ge1 λ ≥ 1 be a real number and let C ⊆ F q m n \mathcal{C} \subseteq\mathbb{F}_{q^m}^n C ⊆ F q m n be a code with minimum λ \lambda λ -subfield distance d λ > 0 d_\lambda> 0 d λ > 0 . Let r r r be a real number with
0 ≤ r < n ( 1 − 1 − d λ λ n ) . 0\le r<n\left(1-\sqrt{1-\frac{d_\lambda}{\lambda n}}\right). 0 ≤ r < n ( 1 − 1 − λn d λ ) .
Then,
∣ C ∣ ≤ q m n V λ ( r , n , q m ) d λ − λ r d λ − 2 λ r + λ r 2 n |C| \le\frac{q^{mn}}{V_{\lambda}(r,n,q^m)}\frac{d_{\lambda}-\lambda r}{d_{\lambda}-2\lambda r+\frac{\lambda r^2}{n}} ∣ C ∣ ≤ V λ ( r , n , q m ) q mn d λ − 2 λ r + n λ r 2 d λ − λ r
Proof. By Corollary 50, every λ \lambda λ -subfield ball of radius r r r contains at most
d λ − λ r d λ − 2 λ r + λ r 2 n \frac{d_{\lambda}-\lambda r}{d_{\lambda}-2\lambda r+\frac{\lambda r^2}{n}} d λ − 2 λ r + n λ r 2 d λ − λ r
codewords of C C C . The result now follows from Theorem 63.
Conclusion
In this paper, we continued the study of the recently introduced λ \lambda λ -subfield metric by developing several aspects of its theory. Our results cover extremal codes, classical bounds and asymptotic densities.
We first investigated Maximum λ \lambda λ -subfield Distance (Mλ \lambda λ D) codes. Besides establishing structural restrictions and their relation to MDS and MRD codes, we introduced sublinear Mλ \lambda λ D codes and studied their asymptotic density. We further constructed a family of constant-weight codes attaining the Plotkin bound and, using the extension theorem of Wood, obtained a classification of all non-degenerate linear constant-weight codes for λ > 1 \lambda> 1 λ > 1 .
We also complemented the collection of classical coding-theoretic bounds available for the λ \lambda λ -subfield metric by deriving Griesmer-, Elias- and Johnson-type bounds. Together with the previously known Singleton-, Plotkin-, sphere-packing-, and Gilbert-Varshamov-type bounds, this provides a broad analogue of the classical theory for the Hamming metric and the rank metric.
Our results show that many fundamental concepts from classical coding theory admit natural analogues in the λ \lambda λ -subfield metric. At the same time, several questions remain open. In particular, explicit constructions of Mλ \lambda λ D codes beyond the currently known families, and efficient decoding algorithms remain largely unexplored. We hope that the results presented here provide a foundation for further investigations into the λ \lambda λ -subfield metric and its applications in coding theory and quantum error correction.
Acknowledgments
Violetta Weger’s work was supported by the Technical University of Munich—Institute for Advanced Study.
Violetta Weger is funded by the European Union ERC-StG CODES - 101304377. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.