TY - JOUR

T1 - Common Complements of Linear Subspaces and the Sparseness of MRD Codes

AU - Gruica, Anina

AU - Ravagnani, Alberto

N1 - Funding Information:
\ast Received by the editors June 23, 2021; accepted for publication (in revised form) October 26, 2021; published electronically April 11, 2022. https://doi.org/10.1137/21M1428947 Funding: The authors were partially supported by the Dutch Research Council through grant OCENW.KLEIN.539. \dagger Department of Mathematics and Computer Science, Eindhoven University of Technology, 5612 AZ, The Netherlands ([email protected], [email protected]).

PY - 2022

Y1 - 2022

N2 - Motivated by applications to the theory of rank-metric codes, we study the problem of estimating the number of common complements of a family of subspaces over a finite field in terms of the cardinality of the family and its intersection structure. We derive upper and lower bounds for this number, along with their asymptotic versions as the field size tends to infinity. We then use these bounds to describe the general behavior of common complements with respect to sparseness and density, showing that the decisive property is whether or not the number of spaces to be complemented is negligible with respect to the field size. By specializing our results to matrix spaces, we obtain upper and lower bounds for the number of maximum-rank-distance (MRD) codes in the rank metric. In particular, we answer an open question in coding theory, proving that MRD codes are sparse for all parameter sets as the field size grows, with only very few exceptions. We also investigate the density of MRD codes as their number of columns tends to infinity, obtaining a new asymptotic bound. Using properties of the Euler function from number theory, we then show that our bound improves on known results for most parameter sets. We conclude the paper by establishing general structural properties of the density function of rank-metric codes.

AB - Motivated by applications to the theory of rank-metric codes, we study the problem of estimating the number of common complements of a family of subspaces over a finite field in terms of the cardinality of the family and its intersection structure. We derive upper and lower bounds for this number, along with their asymptotic versions as the field size tends to infinity. We then use these bounds to describe the general behavior of common complements with respect to sparseness and density, showing that the decisive property is whether or not the number of spaces to be complemented is negligible with respect to the field size. By specializing our results to matrix spaces, we obtain upper and lower bounds for the number of maximum-rank-distance (MRD) codes in the rank metric. In particular, we answer an open question in coding theory, proving that MRD codes are sparse for all parameter sets as the field size grows, with only very few exceptions. We also investigate the density of MRD codes as their number of columns tends to infinity, obtaining a new asymptotic bound. Using properties of the Euler function from number theory, we then show that our bound improves on known results for most parameter sets. We conclude the paper by establishing general structural properties of the density function of rank-metric codes.

KW - density

KW - MRD code

KW - rank-metric code

UR - http://www.scopus.com/inward/record.url?scp=85128828029&partnerID=8YFLogxK

U2 - 10.1137/21M1428947

DO - 10.1137/21M1428947

M3 - Article

AN - SCOPUS:85128828029

SN - 2470-6566

VL - 6

SP - 79

EP - 110

JO - SIAM Journal on Applied Algebra and Geometry

JF - SIAM Journal on Applied Algebra and Geometry

IS - 2

ER -