PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Giuseppe Marino, Alessandro Neri, Alessia Vallefuoco

arXiv:2610.11926v1math.COcs.ITmath.IT

TL;DR

Rank-metric covering radii have comparatively fewer known results, and determining them requires controlling distances across all cosets. This paper uses generator-matrix-based covering lifts to characterize the radius, derive effective-length bounds, and study one-dimensional codes.

  • Problem

    Comparatively few results are known for rank-metric covering radii, whose determination requires controlling distances across all cosets of a code.

    Source: §1 · p. 2

  • Method

    The paper associates covering lifts with a code’s q-system and recovers covering radius from their hyperplane weights.

    Source: §1 · p. 2

  • Results

    δ≥m exactly characterizes ρ(C)=m; for δ<m, ρ(C)≤min{m,n}−1, while [1] [3] codes for q∈{2,3} can have radii 4 or 5.

    Source: §1 · p. 3

  • Takeaways & Limitations

    For m=6 and q∈{2,3}, one-dimensional codes with the same length and minimum distance can have different covering radii.

    Source: §1 · p. 3

    The paper assumes m,n>1 and 0<k<n; the cited lower-bound argument applies only when m≥n.

    Source: §2.1 · p. 4, §5.1 · p. 26

Abstract

from arXiv · show

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

1 Introduction

Because comparatively few results address rank-metric covering radii, the paper develops a generator-matrix-based geometric approach using covering lifts. It gives an effective-length criterion and specializes the framework to one-dimensional codes.

1 Introduction

  • The approach replaces parity-check geometry with generator-matrix geometry, translating vectors far from the code into hyperplane-weight conditions on covering lifts.A vector is far from the code when adding it as a generator-matrix row makes the codewords involving it have large rank.Source: §1 · p. 2
  • ρ(C)=m exactly when δ≥m; otherwise, ρ(C)≤min{m,n}−1.Here δ=n−n′, where n′ is the effective length.Source: §1 · p. 3
  • For a one-dimensional code with m≥n, ρ(C)=n−1 exactly when V has an (n−d)-covering lift that is an (n−d)-club with P of weight n−d.In this setting, effective length equals minimum distance d.Source: §1 · p. 3
  • The extremal-radius condition is also characterized through linear maps and subspaces, with interpretations using generalised evasive subspaces and auxiliary matrix codes.The auxiliary matrix-code formulation expresses the covering radius as δ plus the largest covering radius in a family of associated codes.Source: §1 · p. 3
  • The results determine one-dimensional covering radii for several boundary distances and all m∈{3,4,5}; for q∈{2,3}, [1] [3] codes can have radius 4 or 5.Thus, in the stated m=6 cases, length and minimum distance do not determine covering radius.Source: §1 · p. 3

2 Preliminaries

The preliminaries relate rank-metric codes to q-systems through generator matrices and hyperplane weights, then recall t-clubs and results about these projective-line subspaces.

2.1 Rank-metric codes and q-systems

  • The paper considers codes up to Fq-linear rank-metric equivalence and assumes m,n>1 and 0<k<n..Source: §2.1 · p. 4
  • A generator matrix’s column span over Fq gives the associated q-system, and codeword ranks can be read through hyperplane weights of that system.The paper states a one-to-one correspondence between equivalence classes of nondegenerate codes and q-systems with matching parameters.Source: §2.1 · pp. 5–6

2.2 t-clubs on the projective line

  • A t-club of rank n has one point of weight t and every other point of weight at most one.For t=1, a t-club is a scattered subspace with a point of weight one.Source: §2.2 · p. 6
  • The preliminaries recall club constructions and nonexistence results, including that no 2-club of rank 5 exists for any prime power q.The paper also notes constructions, classification results, and nonexistence results for particular parameters [12].Source: §2.2 · pp. 6–7

3 A geometric link with the covering radius

The section characterizes covering radius through hyperplane weights of lifts of a code’s q-system. It derives effective-length bounds and a puncturing result for transferring large covering radii.

3 A geometric link with the covering radius

  • Appending a candidate vector as a new generator-matrix row turns its distance from C into a minimum-rank condition on the resulting codewords.The proof uses the ranks of rows involving the appended coordinate to encode distance at least t.Source: §3 · p. 8
  • A δ-covering lift projects onto U and meets P in dimension δ; hyperplanes through P have weight δ plus the corresponding weight in U.The weight formula is wt_eU(H)=wt_U(Φ(H))+δ.Source: §3 · p. 9
  • ρ(C)≥t exactly when some δ-covering lift eU has μP(eU)≤n−t.This is the section’s central link between code covering radius and lift hyperplane weights.Source: §3 · p. 10
  • ρ(C)=m exactly when δ≥m; if δ<m, then ρ(C)≤min{m,n}−1.The bound follows from the effective length n′ through δ=n−n′.Source: §3 · p. 12
  • If every length-m code with effective length r has radius m−1, then the stated length-n codes with effective length s+r have radius at least m−1 for 0≤s≤n−m.The result is obtained by puncturing to a length-m code.Source: §3 · p. 13

4 Covering radius of [n, 1]qm/q codes

This section studies covering radii of one-dimensional rank-metric codes, using covering lifts and related geometric and linear-map formulations to characterize when the upper bound is attained. It also determines covering radii in boundary and small-extension cases and reports computations for m = 6, including codes with the same length and minimum distance but different covering radii.

4 Covering radius of [n, 1]qm/q codes

  • The effective length equals minimum rank distance d, and equivalence classes correspond to scalar-multiplication orbits of V; codes with equal length and distance can have different covering radii.Source: §4 · pp. 13–14
  • For an [n,1,d]_{q^m/q} code, ρ(C)=m exactly when δ=n−d≥m; otherwise ρ(C)≤min{m,n}−1.Source: §4 · p. 14

4.1 Codes attaining the upper bound

  • When m≥n, ρ(C)=n−1 exactly when a covering lift is a δ-club of rank n with weight δ at ⟨(0,1)⟩; for m<n, the stated (m−d)-club condition suffices for ρ(C)=m−1.The sufficient condition requires m−d<δ<m and weight m−d at ⟨(0,1)⟩.Source: §4.1 · pp. 14–15
  • If n≥m and every [m,1,r]_{q^m/q} code has covering radius m−1, then every [n,1,s+r]_{q^m/q} code has covering radius at least m−1 for 0≤s≤n−m.Source: §4.1 · p. 15
  • For δ<m, ρ(C)=min{m,n}−1 is equivalent to a linear-map condition: some W of dimension δ and Fq-linear f:V→Fq^m satisfy dim_q{x∈V:f(x)−λx∈W}≤n−min{m,n}+1 for every λ.Equivalently, dim_q(Im(π_W∘(f−λ id_V)))≥min{m,n}−δ−1 for every λ.Source: §4.1 · p. 15
  • The linear-map criterion is equivalent to the associated subspace being (S,n−min{m,n}+1)-evasive; when m≥n, this specializes to (S,1)-evasive.Source: §4.1 · p. 17
  • For δ=n−d<m, ρ(C)=min{m,n}−1 exactly when some δ-dimensional W gives the auxiliary code A_{V,W} covering radius min{m,n}−δ−1.A_{V,W} is formed from the maps x↦π_W(λx) in Hom_q(V,Fq^m/W), equipped with rank metric.Source: §4.1 · pp. 17–18
  • Upper-bound equality holds exactly when some Fq-subspace W ⊆ Fq^m of dimension n − d satisfies ρ(A_V,W) = min{m, n} − δ − 1.Source: §4.1 · p. 19
  • A map B is a deep hole of A_V,W exactly when its associated covering lift maximizes n − μ_P among covering lifts with kernel {0} × W.When W satisfies the equality criterion, condition (8) holds for f exactly when π_W ◦ f is a deep hole.Source: §4.1 · p. 19

4.2 Boundary cases

  • For an [n, 1, d]qm/q code C with δ = n − d and d ∈ {1, 2, min{m, n} − 1, min{m, n}}, ρ(C) is m if δ ≥ m and min{m, n} − 1 if δ < m.Source: §4.2 · p. 19
  • For n ≥ m and s ∈ {0, …, n − m}, every [n, 1, s + 1]q^m/q and [n, 1, s + 2]q^m/q code has covering radius at least m − 1.Source: §4.2 · p. 22

4.3 Special cases

  • For m ∈ {3, 4, 5}, ρ(C) = m when n ≥ m + d, and otherwise ρ(C) = min{m, n} − 1 except at (m, n, d) = (5, 5, 3), where it is 3.The exception follows from the absence of a 2-club of rank 5 in F2^5 and the lower bound in Proposition 5.1.Source: §4.3 · pp. 22–23
  • For [1] [3]q6/q codes, V = λFq^3 guarantees radius 5, but radius 5 does not require this form of V.For q = 3, computations found 28 further equivalence classes with radius 5 beyond the scalar-subfield class.Source: §4.3 · p. 24
  • For [1] [3]q6/q codes, computations found 22 of 23 classes with radius 4 and one with radius 5 for q = 2, versus 29 of 94 classes with radius 5 for q = 3.For q = 3, the 29 classes include the class arising from a scalar multiple of F3^3.Source: §4.3 · p. 24
  • For q ∈ {2, 3}, every [1]q6/q and [1] [3]q6/q code has radius 4, while every [7] [1]q6/q code has radius 5.Source: §4.3 · p. 24
  • For [6, 1, 3]_{q^6/q} codes with q in {2, 3}, both covering radii 4 and 5 occur, so n and d do not determine the radius.The reported MAGMA computations establish these occurrences for q = 2 and q = 3.Source: §4.3 · p. 25

5 Comparison with known results

This section compares the paper’s covering-radius results with bounds by Gadouleau and Yan and Byrne and Ravagnani, then relates its quotient-space characterization to [18] while distinguishing its requirements.

5.1 Gadouleau and Yan results

  • For any m and n, ρ(C) ≤ min{m, n−k}; the Gadouleau–Yan lower bound applies only when m ≥ n.The lower bound therefore gives no information when n > m.Source: §5.1 · p. 26

5.2 Byrne and Ravagnani results

  • For degenerate codes, the dual-distance bound gives only ρ(C) ≤ min{m, n}, whereas Proposition 3.11 can yield ρ(C) ≤ min{m, n}−1 when n < m+n′.Here n′ is the code’s effective length.Source: §5.2 · p. 26
  • For 1<d<n, A_i(C⊥)>0 for every i∈[n], so the external-distance bound recovers Corollary 4.4 only at d∈{1,n}.At intermediate distances, dual codewords attain every weight from 1 to n.Source: §5.2 · p. 26

5.3 Gruica, Ravagnani, Sheekey and Zullo results

  • The quotient-space characterization shares the rank-intersection mechanism of [18, Theorem 6.3] but does not require its graph family to form a partial spread.The comparison also notes that [18, Theorem 6.3] assumes minimum distance equal to the matrix code’s number of rows.Source: §5.3 · p. 28
  • Optimizing over the auxiliary codes A_V,W recovers the original code’s covering radius, while the club connection adds a geometric ingredient absent from [18, Theorem 6.3].When 0<δ<d, the graph family need not be a partial spread.Source: §5.3 · p. 28

Declaration on the use of AI tools

The authors used generative AI tools only for language/readability improvements and assistance with MAGMA code; they state that the mathematical content was developed by the authors, who reviewed the assisted text and verified the code and output.

Declaration on the use of AI tools

  • Generative AI tools were used to improve the manuscript’s language and readability.The authors specify these were among only two purposes for using the tools.Source: Declaration on the use of AI tools · p. 28
  • Generative AI tools also assisted in writing the MAGMA code used for computations in Section 4.3.Source: Declaration on the use of AI tools · p. 28
  • The authors state that they developed all mathematical content, including definitions, results, and proofs.They also reviewed and edited AI-assisted text, checked the code, verified its output, and take responsibility for the publication’s content.Source: Declaration on the use of AI tools · p. 28
Loading 2610.11926v1…