Source-linked AI summary
A new family of linear maximum rank distance codes
John Sheekey
TL;DR
Linear MRD-codes beyond the Gabidulin family were largely unavailable for general parameters, and some classifications remained open. The paper constructs Hk(η, h), proves it is an MRD-code with Gabidulin parameters, and analyzes equivalence and automorphism structure. The family includes codes inequivalent to generalised Gabidulin codes and includes Generalised Twisted Fields.
Problem
For many parameters, no linear MRD-codes other than generalised Gabidulin codes were known, while classification of some MRD-codes remained incomplete.
Method
The paper constructs Hk(η, h) using a q-degree constraint on linearized polynomials and studies code equivalence through automorphism groups and scattered-subspace correspondences.
Results
Each Hk(η, h) is an MRD-code with the same parameters as Gk, and the family contains codes inequivalent to generalised Gabidulin codes.
Takeaways & Limitations
The construction extends the known family of linear MRD-codes and includes the Generalised Twisted Fields family.
Takeaways & Limitations
Classification remains open for 8-dimensional spaces of M4(F3) with minimum rank-distance 3, and it is unknown whether every relevant k = 2 code contains a semifield spread set.
Abstract
from arXiv · showhide
In this article we construct a new family of linear maximum rank distance (MRD) codes for all parameters. This family contains the only known family for general parameters, the Gabidulin codes, and contains codes inequivalent to the Gabidulin codes. This family also contains the well-known family of semifields known as Generalised Twisted Fields. We also calculate the automorphism group of these codes, including the automorphism group of the Gabidulin codes.
1 Preliminaries
The paper establishes rank-metric terminology, equivalence operations, duality, and links between MRD-codes and semifield structures. Existing classifications remain limited, motivating broader classification and construction results.
- Rank metric codes: MRD-codes are finite-field rank-metric codes meeting the Singleton-like bound, with parameters determined by length, dimension, and minimum distance.Rank distance is defined by rank(X − Y), and linearity may be over a subfield.
- (Pre)semifields and quasifields: Semifields and presemifields correspond to specific linear MRD-codes, while quasifields correspond more generally to possibly nonlinear MRD-codes with k = 1.For semifields, code equivalence corresponds to isotopy, and adjoint-equivalence corresponds to isotopy to a transpose.
- Equivalence: Two codes are equivalent under invertible left and right Fq-linear transformations together with a field automorphism, all preserving rank distance.The stabilizer under these operations is the code’s automorphism group.
- Duality: Delsarte duality maps an [nm, nk, m − k + 1]p MRD-code to an [nm, n(m − k), k + 1]p MRD-code.Equivalence is preserved under Delsarte duality, connecting classifications of certain MRD-codes to semifield classifications.
2 Linearized polynomials, and properties of the Gabidulin code
Linearized polynomials identify matrices over finite fields and provide the framework for Gabidulin codes. The section derives their rank properties, equivalence behavior, adjoints, and full automorphism group.
- Linearized polynomials: Every Fq-linear transformation of Fqn is represented uniquely by a linearized polynomial of q-degree at most n − 1.These polynomials form a composition ring isomorphic to Mn(Fq).
- Gabidulin codes: A linearized polynomial of q-degree k has rank at least n − k, yielding MRD-codes Gk,s with dimension nk and minimum rank-distance n − k + 1.The rank bound follows from the maximum number of roots, and also from a more general cyclic-Galois-extension theorem.
- Gabidulin codes: Generalised Gabidulin codes consist of linearized polynomials whose exponents advance by a fixed q^s step, with the ordinary Gabidulin family given by s = 1.The coefficient map between different step sizes need not preserve rank distance, and some resulting codes are inequivalent.
- Automorphisms and adjoints: The Gabidulin code is invariant under scalar composition and the Frobenius action, and these symmetries form its full stabilizer.Each Gabidulin code is also equivalent to its adjoint, while the generalised families Gk,s have the same automorphism group as Gk.
- Equivalent subspaces: Theorem 3 characterizes subspaces of Gk equivalent to Gr as spaces G(f,g), formed by composing Gr with invertible linearized polynomials subject to a q-degree constraint.The condition is degq(f) + degq(g) ≤ k − r, after normalizing the constant coefficient of f.
3 Construction of new linear MRD-codes
The paper constructs twisted Gabidulin codes H_k(η,h), a family of linear MRD-codes with Gabidulin parameters, and establishes their duality, equivalence, automorphism, and semifield connections.
- Construction: The norm identity N(f_0) = (−1)^{kn}N(f_k) is necessary for rank n−k but is not sufficient when k > 1.The converse failure limits how directly the norm condition can characterize minimum-rank elements.
- Construction: The key construction H_k(η,h) consists of linearized polynomials whose highest coefficient is constrained by f_k = ηf_0^{q^h}.The family is defined for linearized polynomials of q-degree at most k ≤ n−1.
- Construction: Each H_k(η,h) is an MRD-code with dimension nk and minimum rank distance n−k+1, matching the parameters of G_k.The proof uses the rank bound for linearized polynomials together with the norm condition from Lemma 3.
- Duality: The adjoint of H_k(η,h) is equivalent to H_k(η^{−q^{k−h}}, k−h), while its Delsarte dual is H_{n−k}(−η^{q^{n−h}}, n−h).These identities connect the family across adjoint and dual constructions.
- Equivalence and automorphisms: H_k(0,h) = G_k, so the family contains Gabidulin codes; for η ≠ 0, its automorphism analysis yields codes inequivalent to generalised Gabidulin codes in the stated parameter range.For k ∉ {1,n−1}, H_k(η,h) is not equivalent to G_{k,s}; the exceptional cases are k ∈ {1,n−1} and h ∈ {0,1}.
- Semifield connections: When k = 1, H_k(η,h) is a semifield spread set corresponding to a generalised twisted field, motivating the name twisted Gabidulin codes.The family is F_{q^n}-linear exactly when h = 0; h = k instead gives a different Singer-cycle symmetry without F_{q^n}-linearity.
4 Representations as matrices and vectors
The paper represents linearized polynomials as matrices using multiplication and Frobenius matrices over a chosen basis, then illustrates Gabidulin and twisted Gabidulin codes for q = 3 and n = 4.
- Matrix representation: An Fq-basis of Fqn yields matrices A and S for multiplication by a primitive element and the Frobenius automorphism.The basis {1, α, . . . , α^n−1} makes A a companion matrix, while a normal basis would make S a permutation matrix; the paper chooses the former.
- Example parameters: For q = 3 and n = 4, the paper chooses α ∈ F81 satisfying α4 = α + 1 and represents field elements by coordinate columns.
- Gabidulin code: The Gabidulin code G2 has an 8-dimensional basis formed by the matrices AiSj for i ∈ {0, . . . , 3} and j ∈ {0, 1}.
- Examples of codes: The first four matrices form G1, corresponding to F81, while the first four matrices in the alternative construction form H1(α, 1), corresponding to a generalised twisted field.
- Examples of codes: H2(α, 0) is F81-linear and inequivalent to G2, whereas H2(α, 1) is only F3-linear.
- Open problem: Classifying all 8-dimensional subspaces of M4(F3) with minimum rank-distance 3 remains open.
5 MRD-codes, scattered subspaces and scattered linear sets
The paper connects maximum scattered subspaces, scattered linear sets, and MRD-codes through graph spaces of linearized polynomials, and proves that equivalence of the relevant subspaces matches code equivalence.
- Scattered subspaces: A scattered subspace meets every element of the Desarguesian spread in dimension at most 1, with maximum possible dimension n.
- Scattered linear sets: Linear sets arise from projectivising Fq-subspaces, and scatteredness is characterised by attaining the largest possible set size.
- Polynomial correspondence: For a linearized polynomial f, the graph Uf = {(y, f(y)) : y ∈ Fqn} is scattered exactly when rank(f − βx) ≥ n − 1 for every β ∈ Fqn.
- Polynomial correspondence: The associated code Cf = ⟨x, f⟩Fqn is an Fqn-linear MRD-code of dimension 2n and minimum distance n − 1.
- Equivalence: Equivalent graph spaces induce equivalent MRD-codes, and conversely, so equivalence of scattered subspaces and their associated codes coincides.
- Equivalence: Equal or equivalent linear sets need not correspond to equivalent subspaces or codes; generalised Gabidulin examples can share a linear set while remaining inequivalent.