# Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric

Zeyu Guo Department of Computer Science and Engineering, The Ohio State
University<EMAIL_ADDRESS>Chaoping Xing School of Electronic Information
and Electric Engineering, Shanghai Jiao Tong University<EMAIL_ADDRESS>Chen Yuan School of Electronic Information and Electric Engineering, Shanghai
Jiao Tong University<EMAIL_ADDRESS>Zihan Zhang Department of Computer
Science and Engineering, The Ohio State University<EMAIL_ADDRESS>
###### Abstract

Gabidulin codes, serving as the rank-metric counterpart of Reed–Solomon codes,
constitute an important class of maximum rank distance (MRD) codes. However,
unlike the fruitful positive results about the list decoding of Reed–Solomon
codes, results concerning the list decodability of Gabidulin codes in the rank
metric are all negative so far. For example, in contrast to Reed–Solomon
codes, which are always list decodable up to the Johnson bound in the Hamming
metric, Raviv and Wachter-Zeh (IEEE TIT, 2016 and 2017) constructed a class of
Gabidulin codes that are not even combinatorially list decodable beyond the
unique decoding radius in the rank metric. Proving the existence of Gabidulin
codes with good combinatorial list decodability in the rank metric has
remained a long-standing open problem.

In this paper, we resolve the aforementioned open problem by showing that,
with high probability, random Gabidulin codes over sufficiently large
alphabets attain the optimal generalized Singleton bound for list decoding in
the rank metric. In particular, they achieve list decoding capacity in the
rank metric.

Our work is significantly influenced by the recent breakthroughs in the
combinatorial list decodability of Reed–Solomon codes, especially the work by
Brakensiek, Gopi, and Makam (STOC 2023). Our major technical contributions,
which may hold independent interest, consist of the following: (1) We initiate
the study of “higher order MRD codes” and provide a novel unified theory,
which runs parallel to the theory of “higher order MDS codes” developed by
Brakensiek, Gopi, and Makam. (2) We prove a natural analog of the GM-MDS
theorem, proven by Lovett (FOCS 2018) and Yildiz and Hassibi (IEEE TIT, 2019),
which we call the GM-MRD theorem. In particular, our GM-MRD theorem for
Gabidulin codes are strictly stronger than the GM-MDS theorem for Gabidulin
codes, proven by Yildiz and Hassibi (IEEE TIT, 2019).

###### Contents

  1. 1 Introduction
    1. 1.1 List Decodability of Reed–Solomon Codes
    2. 1.2 List Decodability of Rank-Metric codes and Gabidulin Codes
    3. 1.3 Our Results
      1. 1.3.1 Optimal List Decodability of Random Gabidulin Codes
      2. 1.3.2 Higher Order MRD Codes
      3. 1.3.3 The GM-MRD Theorem
  2. 2 Preliminaries
    1. 2.1 Rank-Metric Codes and Gabidulin Codes
    2. 2.2 The MRD Property of the Generic Linear Code
  3. 3 Generic Kernel Patterns
    1. 3.1 Generalized Hall’s Theorem for Vector Spaces
    2. 3.2 Generic Kernel Patterns of Order at Most $\ell$
  4. 4 The GM-MRD Theorem
    1. 4.1 Proof of the GM-MRD Theorem
    2. 4.2 Proof of 4.7
  5. 5 Equivalence Between $\operatorname{GKP}(\ell)$ and $\operatorname{MRD}(\ell)$
    1. 5.1 Formula for Generic Intersection Dimension: Proof of 1.16
    2. 5.2 Proof of 1.13
  6. 6 Equivalence Between $\operatorname{MRD}(\ell)$ and $\operatorname{LD-MRD}({\leq}\,\ell-1)$ up to Duality
    1. 6.1 An Alternative Characterization of $\operatorname{MRD}(\ell)$ Over $\mathbb{F}/\mathbb{F}_{q}$
    2. 6.2 Proof of Theorem 1.14
  7. 7 Putting It Together
  8. 8 Conclusions and Future Directions
  9. A Field Size Lower Bound for $\operatorname{LD-MRD}(\ell)$

##  1 Introduction

A rank-metric code is a collection of matrices in $\mathbb{F}_{q}^{m\times n}$
with $m\geq n$, where the distance between two matrices $A$ and $B$ is defined
to be the rank of $A-B$. Introduced by Delsarte [Del78] as a combinatorial
curiosity, rank-metric codes have since developed into a field of study with
applications and connections spanning network coding [KK07, SKK08, KK08,
SK09], space-time coding [LGB03, LK05], cryptography [Gib96, Gib95, Loi10,
Loi17], and pseudorandomness [FS12, FG15, GWX16, GRX21, GVJZ23].

A rank-metric code $C$, with rate $R$ and relative minimum distance $\delta$,
must satisfy the Singleton bound $1-R\geq\delta$. If the equality $1-R=\delta$
is attained, then the code $C$ is called a Maximum Rank Distance (MRD) code.
Gabidulin codes [Del78, Gab85, Rot91], an important class of MRD codes, can be
viewed as the linearized versions of Reed–Solomon codes. They are defined
through the evaluation of linearized polynomials within a subspace. This
perspective positions Gabidulin codes as a perfect analogy to Reed–Solomon
codes in the rank metric setting. Similar to Reed–Solomon codes, one can
design highly efficient encoding and unique decoding algorithms for Gabidulin
codes by generalizing the Berlekamp–Welch algorithm [KK08]. However, regarding
the list decoding regime, it is unknown whether exist any Gabidulin codes that
can be list decoded beyond the unique decoding radius. In comparison, the
celebrated Guruswami–Sudan list decoding algorithm [GS99] can list decode any
Reed–Solomon code up to the Johnson bound. Thus, a long-standing open problem
remains for rank-metric codes:

######  Open Problem 1.1.

Are Gabidulin codes algorithmically or combinatorially list
decodable111Combinatorial list decodability refers to the condition where the
output list of candidate codewords, within the list decoding radius, is small,
whereas algorithmic list decodability further requires that there exists an
efficient algorithm outputting this list. beyond the unique decoding radius in
the rank metric?

In this paper, we provide a positive answer to the “combinatorial” aspect of
this problem. Namely, we prove that Gabidulin codes with random evaluation
subspaces are combinatorially list decodable up to the generalized Singleton
bound with high probability in the rank metric. Our approach is inspired by
the recent progress regarding the list decodability of random Reed–Solomon
codes.

###  1.1 List Decodability of Reed–Solomon Codes

In the Hamming metric, the Singleton bound [Sin64] states that any code with a
rate $R$ and relative minimum distance $\delta$ must satisfy $R+\delta\leq 1$.
Codes that attain this bound are called Maximally Distance Separable (MDS)
codes. Reed–Solomon codes are a class of Hamming-metric codes that attain the
Singleton bound. This bound was recently generalized to the list decoding
setting by investigating the list decoding of Reed–Solomon codes. Shangguan
and Tamo222Before the work of Shangguan and Tamo, Rudra and Wootters [RW14]
were the first to show that random RS codes are list decodable beyond the
Johnson radius for some parameter regimes. Their methodology is purely
analytic instead of algebraic. [ST20] proposed the generalized Singleton bound
$\rho\leq\frac{L}{L+1}(1-R)$, where $\rho$ is the list decoding radius and $L$
is the list size. Moreover, they showed that such a bound is achievable for
$L=2,3$. Since then, there have been some efforts to prove the tightness of
this bound [GLS+21, FKS22, GST23]. A major breakthrough was made by
Brakensiek, Gopi, and Makam [BGM23] in proving that this generalized Singleton
bound holds for any list size $L$. In particular, their argument demonstrated
that Reed–Solomon codes with random evaluation points defined over
$\mathbb{F}_{q}$ (where $q$ is exponential in the length of the code) can
attain the generalized Singleton bound with high probability.

The exponential size of the field is inevitable [BGM22]. If we accept a
$\varepsilon$ gap from this bound, i.e.,
$\rho=\frac{L}{L+1}(1-R-\varepsilon)$, then the size of the field can be
reduced to $O_{\varepsilon}(n^{2})$ [GZ23] and further to $O_{\varepsilon}(n)$
[AGL23]. In the context of constant-sized field sizes, Brakensiek, Dhar, Gopi,
and Zhang [BDGZ23] showed that algebraic geometry codes with random evaluation
points defined over $\mathbb{F}_{q}$, with $q=\exp(O(1/\varepsilon^{2}))$, can
be list decoded up to the radius $\frac{L}{L+1}(1-R-\varepsilon)$. The
exponential dependence of $q$ on $1/\varepsilon$ was proved to be necessary
($q\geq\exp(\Omega(1/\varepsilon))$) in [AGL24]. Also, based on the frameworks
built by [BGM23, GZ23, AGL23], Ron-Zewi, Venkitesh, and Wootters [RZVW24]
recently showed similar list decodability phenomenon holds for polynomial
ideal codes, which includes several well-studied families of error-correcting
codes such as Reed–Solomon codes, folded Reed–Solomon codes, and multiplicity
codes.

Our understanding of the generalized Singleton bound is nearly complete,
thanks to the recent progress mentioned above. One might ask whether this
generalized Singleton bound holds for codes in other metrics, such as the rank
metric. We note that a code with a minimum rank distance of $d$ is also a code
with a minimum Hamming distance of at least $d$. Thus, the argument for the
upper bound of the generalized Singleton bound can be applied
straightforwardly. However, proving the tightness of this upper bound appears
to be highly non-trivial.

###  1.2 List Decodability of Rank-Metric codes and Gabidulin Codes

Let us first review some results concerning the list decoding of rank-metric
codes. Ding [Din14] proposed the Gilbert-Varshamov bound (GV) for the list
decoding of rank-metric codes. Specifically, she showed that, with high
probability, a random rank-metric code can be list decodable up to the GV
bound, and any rank-metric code cannot be list decodable beyond this GV bound.
In [Din14], the list size for random linear rank-metric codes is given as
$O\left((\frac{1}{\varepsilon})^{\frac{1}{\varepsilon}}\right)$, a result of
the limited randomness available for these codes. Guruswami and Resch [GR18]
adopted the ideas from [GHK10] to further reduce the list size of random
linear rank-metric codes to a constant $O(1/\varepsilon)$. The results
mentioned above are not explicit. Meanwhile, Guruswami, Wang, and Xing [GWX16]
presented the first explicit class of rank-metric codes with efficient list
decoding algorithms capable of decoding up to the Singleton bound. Their
construction involved carefully selecting a subcode of the Gabidulin code
using a tool known as subspace designs [GK13], thereby reducing the list size
to a constant. Later on, Xing and Yuan [XY18] introduced another explicit
class of rank-metric codes that can be list decoded up to the Singleton bound.
Their construction borrowed ideas from folded Reed–Solomon codes to fold
Gabidulin codes in a similar manner. To approach the Singleton bound, the
column-to-row ratio $\frac{n}{m}$ should be close to $0$. In the regime where
the column-to-row ratio is constant, the construction from [XY18] remains
applicable and can correct up to a $\frac{2}{3}(1-2R)$ fraction of errors. By
modifying this approach, Liu, Xing, and Yuan [LXY23] presented an explicit
construction of list decodable rank-metric codes with a ratio of $2/3$. An
open question remains: Can we explicitly construct a class of rank-metric
codes with a column-to-row ratio of $1$ that is list decodable beyond the
unique decoding radius? For comparison, the Gilbert–Varshamov (GV) bound
argument suggests that, with high probability, there exist random rank-metric
codes with a column-to-row ratio of $1$ that can be list decoded up to a
radius of $1-\sqrt{R}$, which is strictly larger than the unique decoding
radius of $\frac{1-R}{2}$.

Although there are a few positive results for the list decoding of rank-metric
codes, the findings regarding the list decoding of Gabidulin codes have been
predominantly negative so far. Wachter-Zeh [Wac13] proved that any square
Gabidulin codes—where “square” indicates that the column-to-row ratio is
$1$—cannot be list decoded beyond a radius of $1-\sqrt{R}$. Furthermore, Raviv
and Wachter-Zeh [RWZ16, RWZ17] constructed a class of Gabidulin codes that
cannot be list decoded to any radius beyond the unique decoding radius.
Despite these negative results, our work demonstrates the existence of
Gabidulin codes that can be list decoded up to the generalized Singleton
bound. We briefly review some applications based on the list decoding of rank-
metric codes or Gabidulin codes and discuss the implications of our results.

##### Code-based cryptography.

Rank-metric code-based cryptosystems have been studied since 1991 [PT91,
CS96]. Rank-metric codes play an important role in designing post-quantum
cryptosystems. Two well-known systems, RQC [AMAB+19a] and ROLLO [AMAB+19b],
have been considered for the NIST standardization. The main advantage of rank-
metric codes is that the hard problems in the rank metric, such as the generic
decoding problem, seem harder to solve than their counterparts in the Hamming
metric. The random syndrome decoding (RSD) problem, in particular, assumes
that it is computationally hard to decode a random
$[n,k]_{\mathbb{F}_{q^{m}}}$-linear code333See Section 2 for the definition of
$[n,k]_{\mathbb{F}_{q^{m}}}$-linear codes. in the rank metric. Recent
developments in attacks based on Göbner bases [BBB+20, BBC+20] have
significantly impacted the security parameters of cryptosystems relying on the
hardness of the search RSD problem. Given that the search RSD problem is not
as hard as previously believed, the list search version of the RSD problem,
which is strictly harder than the search RSD problem, might be considered.
This problem outputs a list of codewords within a given radius of a random
$[n,k]_{\mathbb{F}_{q^{m}}}$-linear code. The Gabidulin code list search RSD
problem was thought to be more challenging than the list search RSD problem
[RJB+20], mainly because only negative results were available for the list
decoding of Gabidulin codes. Faure and Loidreau [FL05] proposed the
Faure–Loidreau (FL) cryptosystem, which is connected with the list decoding of
Gabidulin codes. The original FL cryptosystem was compromised by exploiting
the list decoding of interleaved Gabidulin codes. However, the revised FL
cryptosystem, LIGA [RPW21], which relies on the hardness of list decoding
Gabidulin codes, is resistant to this attack. The hardness assumption for the
list decoding of Gabidulin codes suggests that it is computationally difficult
to find all codewords of a Gabidulin code within the list decoding radius
$1-\sqrt{R}$. Prior to our work, it was widely believed that the output list
for this list decoding problem should be exponential. Thus, our work enhances
the understanding of the list decoding of Gabidulin codes, which could
significantly impact the design of rank-metric code-based cryptosystems.

##### Pseudorandomness.

Rank-metric codes and Gabidulin codes have also found applications and
connections in the field of pseudorandomness. In [FG15], Forbes and Guruswami
studied various objects related to “linear-algebraic pseudorandomness.” They
specifically proved that bilinear lossless two-source rank condensers are
equivalent to linear rank-metric codes. Consequently, they showed that
Gabidulin codes translate into optimal two-source rank condensers. Inspired by
the explicit constructions of subcodes of Gabidulin codes that are list
decodable in the rank metric [GX13, GWX16], Guruswami, Resch, and Xing [GRX21]
presented an explicit construction of dimension expanders, which can be seen
as the linear-algebraic analogs of expander graphs. This construction achieves
excellent “lossless” expansion. Cheraghchi, Didier, and Shokrollahi [CDS11]
used Gabidulin codes to construct explicit affine extractors for a restricted
family of affine sources over large fields, which have applications in wiretap
protocols. In [GVJZ23], Guo, Volk, Jalan, and Zuckerman considered
$(\varepsilon,e)$-biased sources over $\mathbb{F}_{p}$. These are random
sources $\mathcal{X}$ over $\mathbb{F}_{p}^{n}$ that are $\varepsilon$-biased
against all but a subgroup $H$ of characters, where $|H|\leq e$, thereby
generalizing affine sources of small codimension. Using Gabidulin codes, they
constructed deterministic extractors that extract almost all the min-entropy
from such sources. This construction was further utilized as a component in
constructing extractors for other algebraic sources.

Rank-metric codes have also been connected to other problems studied in
theoretical computer science, such as low-rank recovery [FS12]. Despite these
applications, we believe that the potential use of rank-metric codes in
theoretical computer science has not been fully explored. In particular, given
the intimate connection between pseudorandomness and error-correcting codes in
the Hamming metric, especially those with good list decodability or list
recoverability [GUV09, Vad12], it is conceivable that rank-metric codes and
Gabidulin codes may find similar applications.

###  1.3 Our Results

Our main results can be divided into three parts:

  1. 1.

The optimal (combinatorial) list decodability of random Gabidulin codes over
sufficiently large alphabets in the rank metric.

  2. 2.

The formulation of three notions of “higher order MRD codes”, which we denote
as $\operatorname{GKP}(\ell)$, $\operatorname{MRD}(\ell)$, and
$\operatorname{LD-MRD}(\ell)$, and the demonstration of their equivalence.

  3. 3.

A result we call the $\operatorname{GM-MRD}$ theorem, which states that
symbolic Gabidulin codes satisfy $\operatorname{GKP}(\ell)$ for all $\ell$.

The first two items constitute a theory parallel to that of Brakensiek, Gopi,
and Makam [BGM23], who demonstrated the optimal list decodability of random
Reed-Solomon codes over sufficiently large alphabets and established the
equivalence among three notions of “higher order MDS codes.” The third item,
i.e., the GM-MRD theorem, serves as a rank-metric analog to the _GM-MDS
theorem_ , which was conjectured in [DSY14b] and subsequently proved in
[Lov18, YH19b]. In the following, we will explain each of these three items in
detail.

####  1.3.1 Optimal List Decodability of Random Gabidulin Codes

Recall that for $\rho\in[0,1]$, a code $C\subseteq\Sigma^{n}$ over an alphabet
$\Sigma$ is said to be _$(\rho,\ell)$ -list decodable_ if for any
$\bm{y}\in\mathbb{F}_{q}^{n}$, it holds that

$|\\{\bm{x}\in C:d(\bm{x},\bm{y})\leq\rho n\\}|\leq\ell.$

where $d(\bm{x},\bm{y})$ denotes the distance between $\bm{x}$ and $\bm{y}$.
Here $\rho$ is called the list decoding radius and $\ell$ is called the list
size.

In [ST20], Shangguan and Tamo proved the _generalized Singleton bound_ for
list decoding, generalizing the classical Singleton bound for unique decoding.
For linear codes, this generalized Singleton bound states that if
$C\subseteq\mathbb{F}_{q}^{n}$ is an $[n,k]$-linear code that is
$(\rho,\ell)$-list decodable in the Hamming metric, then it holds that
$\rho\leq\frac{\ell}{\ell+1}\left(1-\frac{k}{n}\right)$.

Note that the rank distance $d_{R}(\bm{x},\bm{y})$ between
$\bm{x},\bm{y}\in\mathbb{F}_{q^{m}}^{n}$ is always bounded by their the
Hamming distance $d_{H}(\bm{x},\bm{y})$. This is because $\bm{x}-\bm{y}$,
viewed as an $m\times n$ matrix over $\mathbb{F}_{q}$, has at most
$d_{H}(\bm{x},\bm{y})$ nonzero columns. It follows that a $(\rho,\ell)$-list
decodable code $C\subseteq\mathbb{F}_{q}^{n}$ in the Hamming metric remains
$(\rho,\ell)$-list decodable in the rank metric. This immediately implies that
the generalized Singleton bound continues to hold in the rank metric:

######  Lemma 1.2 (Generalized Singleton bound for rank-metric codes).

Let $C\subseteq\mathbb{F}_{q^{m}}^{n}$ be an
$[n,k]_{\mathbb{F}_{q^{m}}}$-linear code that is $(\rho,\ell)$-list decodable
in the rank metric. Then it holds that

$\rho\leq\frac{\ell}{\ell+1}\left(1-\frac{k}{n}\right).$

The central objects studied in this paper are _Gabidulin codes_. For integers
$m\geq n\geq k$ and elements
$\alpha_{1},\dotsc,\alpha_{n}\in\mathbb{F}_{q^{m}}$ that are linearly
independent over $\mathbb{F}_{q}$, the corresponding Gabidulin code over
$\mathbb{F}_{q^{m}}$ is defined to be the $[n,k]_{\mathbb{F}_{q^{m}}}$-linear
code

$\mathcal{G}_{n,k}(\alpha_{1},\dotsc,\alpha_{n}):=\left\\{(f(\alpha_{1}),\ldots,f(\alpha_{n})):\;f(X)=\sum_{i=1}^{k}c_{i}X^{q^{i-1}},c_{1},\dots,c_{k}\in\mathbb{F}_{q}^{m}\right\\}\subseteq\mathbb{F}_{q^{m}}^{n}.$

Our main theorems state that, for random $\alpha_{1},\dots,\alpha_{n}$ and
sufficiently large $m$, with high probability, the Gabidulin code
$\mathcal{G}_{n,k}(\alpha_{1},\dotsc,\alpha_{n})$ over $\mathbb{F}_{q^{m}}$
are list decodable up to a radius that exactly attains the generalized
Singleton bound.

######  Theorem 1.3 (Informal version of 7.2).

Let $(\alpha_{1},\dots,\alpha_{n})$ be uniformly distributed over the set of
all vectors in $\mathbb{F}_{q^{m}}^{n}$ whose coordinates are linearly
independent over $\mathbb{F}_{q}$.444While we assume that
$(\alpha_{1},\dots,\alpha_{n})$ is sampled from the set of all vectors with
$\mathbb{F}_{q}$-linearly independent coordinates, one can also sample it from
the whole set $\mathbb{F}_{q^{m}}^{n}$ given that most vectors in this set
have $\mathbb{F}_{q}$-linearly independent coordinates. This distinction is
unimportant. Suppose $m\geq cnk\ell+\log_{q}(1/\delta)$, where $c$ is a large
enough absolute constant. Then it holds with probability at least $1-\delta$
that the Gabidulin code $\mathcal{G}_{n,k}(\alpha_{1},\dots,\alpha_{n})$ over
$\mathbb{F}_{q^{m}}$ is
$\left(\frac{L}{L+1}\left(1-{k}/{n}\right),L\right)$-list decodable for all
$L\in[\ell]$ in the rank metric.

######  Corollary 1.4 (Informal version of 7.3).

Let $(\alpha_{1},\dots,\alpha_{n})$ be uniformly distributed over the set of
all vectors in $\mathbb{F}_{q^{m}}^{n}$ whose coordinates are linearly
independent over $\mathbb{F}_{q}$. Suppose $m\geq
cnk/\varepsilon+\log_{q}(1/\delta)$, where $c$ is a large enough absolute
constant. Then it holds with probability at least $1-\delta$ that the
Gabidulin code $\mathcal{G}_{n,k}(\alpha_{1},\dots,\alpha_{n})$ over
$\mathbb{F}_{q^{m}}$ is
$\left(1-R-\varepsilon,\frac{1-R}{\varepsilon}\right)$-list decodable, where
$R=k/n$ is the rate of the code.

In fact, we prove the stronger statement that
$\mathcal{G}_{n,k}(\alpha_{1},\dots,\alpha_{n})$ is, with high probability,
_average-radius list decodable_ with the parameters stated in 1.3 and 1.4. See
7.2 and 7.3 for details. Average-radius list decodability is stronger than
standard list decodability, which we will discuss shortly when defining the
notion $\operatorname{LD-MRD}(\ell)$.

##### Field size lower bound.

1.3 shows that Gabidulin codes over $\mathbb{F}_{q^{m}}$ can attain the
Singleton bound (even in the sense of average-radius list decodability) for
some $m=O_{\ell}(n^{2})$. To complement this upper bound, we establish a
matching lower bound on the field size via a technique developed in [AGL24].

######  Theorem 1.5 (Informal version of A.1).

Let $\ell\geq 2$. Let $C\subseteq\mathbb{F}_{q^{m}}^{n}$ be a rank-metric code
over $\mathbb{F}_{q^{m}}$ of rate $R$. If $C$ is
$\left(\frac{\ell}{\ell+1}(1-R),\ell\right)$-average-radius list decodable
(see 1.11) and $R\in[c,1-c-\ell/n]$ for some constant $c>0$, then
$m=\Omega_{\ell}(n^{2})$.

####  1.3.2 Higher Order MRD Codes

Maximum rank distance (MRD) codes are the counterparts of maximum distance
separable (MDS) codes in the rank metric. Recall for $m\geq n\geq k$, an
$[n,k]_{\mathbb{F}_{q^{m}}}$-linear rank-metric code $C$ is a MRD code if its
minimum (rank) distance $d(C)$ attains the Singleton bound, i.e.,
$d(C)=n-k+1$.

Brakensiek, Gopi, and Makam [BGM23] studied three different definitions of
“higher order MDS codes,” which they call $\operatorname{GZP}(\ell)$,
$\operatorname{MDS}(\ell)$, and $\operatorname{LD-MDS}(\ell)$ codes.
Amazingly, they proved that these three notions are equivalent in a certain
rigorous sense. This equivalence was crucially used in their proof that
generic Reed–Solomon codes achieve list decoding capacity.

This raises the questions of whether similar notions of “higher order MRD
codes” exist, and if so, whether there is also an equivalence among them. In
this paper, we show that the answer to both questions is yes.

Specifically, we introduce the notions of $\operatorname{GKP}(\ell)$,
$\operatorname{MRD}(\ell)$, and $\operatorname{LD-MRD}(\ell)$ codes. Just as
the MRD property strengthens the MDS property, each of these three notions
strengthens their counterpart in the Hamming metric, as studied in [BGM23].
Furthermore, we establish an equivalence among these three notions. This
equivalence plays a crucial role in our proof that, with high probability,
random Gabidulin codes achieve list decoding capacity in the rank metric.

##### Rank-metric codes over a general field $\mathbb{F}/\mathbb{F}_{q}$.

Before defining the three notions of “higher order MRD codes,” we note that,
for convenience, we will present these definitions over a general extension
field $\mathbb{F}$ of $\mathbb{F}_{q}$, which may be infinite. This generality
allows us to easily discuss the “symbolic Gabidulin code,” defined over a
function field $\mathbb{F}_{q}(Z_{1},\dots,Z_{n})$. For infinite $\mathbb{F}$,
while it is no longer possible to view a vector
$\bm{v}=(v_{1},\dots,v_{n})\in\mathbb{F}^{n}$ as a matrix over
$\mathbb{F}_{q}$ and discuss its rank (since $m=[\mathbb{F}:\mathbb{F}_{q}]$
is infinite), we can still define the rank of $\bm{v}$ as

$\mathrm{rank}_{\mathbb{F}_{q}}(\bm{v}):=\dim_{\mathbb{F}_{q}}(\mathrm{span}_{\mathbb{F}_{q}}\\{v_{1},\ldots,v_{n}\\}).$
(1)

With this revised definition of rank, the concept of linear rank-metric codes
over $\mathbb{F}_{q^{m}}$ can easily be extended to those over a general field
$\mathbb{F}/\mathbb{F}_{q}$, and fortunately, all necessary facts and
properties continue to hold. For a more comprehensive discussion about linear
rank-metric codes over a general field $\mathbb{F}/\mathbb{F}_{q}$, we refer
the readers to Section 2.

######  $\blacktriangleright\operatorname{GKP}(\ell)$.

Given $k\leq n$, a _zero pattern_ is a tuple of sets
$\mathcal{S}=(S_{1},\dots,S_{k})$ with $S_{i}\subseteq[n]$. For an
$[n,k]_{\mathbb{F}}$ linear code $C$ with a generator matrix
$G\subseteq\mathbb{F}^{n\times k}$, we say $C$ _attains_ a zero pattern
$\mathcal{S}$ if there exists an invertible matrix
$M_{\mathcal{S}}\in\mathbb{F}^{k\times k}$ such that for
$(i,j)\in[k]\times[n]$, the $(i,j)$-th entry of $M_{\mathcal{S}}G$ is zero if
$j\in S_{i}$, i.e., $M_{\mathcal{S}}G$ exhibits the zero pattern
$\mathcal{S}$.

This notion was driven by applications such as those discussed in [DSY14a,
YS13, YSZ14] in order to find linear MDS codes with sparse generator matrices.
A natural question emerges: What are the zero patterns that linear MDS codes
such as Reed–Solomon codes can attain? To understand this, the notion of
_generic zero patterns_ (GZPs) was defined in [BGM23], which originated from
[DSY14a]: A zero pattern $\mathcal{S}=(S_{1},\ldots,S_{k})$ is called a
generic zero pattern if

$\left|\bigcap_{i\in\Omega}S_{i}\right|\leq k-|\Omega|\qquad\text{for all
nonempty }\Omega\subseteq[k].$ (2)

It is not difficult to prove that (2) is a necessary condition for a linear
MDS code to attain the zero pattern $\mathcal{S}$. It was conjectured in
[DSY14a] that for any zero pattern $\mathcal{S}$, there exist MDS codes with
alphabet size $q\geq n+k-1$ attaining $\mathcal{S}$. This conjecture, known as
the _$\operatorname{GM-MDS}$ conjecture_, was later proven by Lovett [Lov18]
and independently by Yildiz and Hassibi [YH19b], and has become the GM-MDS
theorem. In fact, their proofs imply the stronger statement that generic
Reed–Solomon codes attain all GZPs. This theorem was further generalized in
[BDG23] to any polynomial codes, whereas the original version only deals with
the Reed–Solomon codes. Another generalization was recently proved in [RZVW24]
to establish the near-optimal list decodability of folded Reed–Solomon codes.

We define a more general notion, which we call generic kernel patterns (GKPs).
It appears to be more suitable for studying rank-metric codes, including MRD
codes.

######  Definition 1.6 (Generic kernel pattern (GKP)).

Given $k\leq n$ and a finite field $\mathbb{F}_{q}$, a _kernel pattern_ is a
tuple $\mathcal{V}=(V_{1},\ldots,V_{k})$ of $\mathbb{F}_{q}$-linear subspaces
of $\mathbb{F}_{q}^{n}$, We say a kernel pattern $\mathcal{V}$ is a _generic
kernel pattern_ (GKP) if for any nonempty $\Omega\subseteq[k]$, it holds that

$\dim\left(\bigcap_{i\in\Omega}V_{i}\right)\leq k-|\Omega|.$ (3)

In addition, we say a kernel pattern $\mathcal{V}$ has _order $\ell$_ if
$\mathcal{V}$ has exactly $\ell$ distinct nonzero subspaces.

Next, we define a linear code attaining a kernel pattern.

######  Definition 1.7.

Let $C$ be an $[n,k]_{\mathbb{F}}$-linear code with a generator matrix
$G\times\mathbb{F}^{k\times n}$. Let $\mathcal{V}=(V_{1},\ldots,V_{k})$ be a
kernel pattern and $(A_{1},\ldots,A_{k})$ be a tuple of $k$ full rank matrices
such that $A_{i}\in\mathbb{F}_{q}^{n\times\dim V_{i}}$ with $\langle
A_{i}\rangle=V_{i}$555For a matrix $H\in\mathbb{F}_{q}^{n\times\ell}$, we
denote $\langle H\rangle$ to be the linear subspace of $\mathbb{F}_{q}^{n}$
spanned by the columns of $H$.. We say $C$ _attains_ the kernel pattern
$\mathcal{V}$ if there is an invertible matrix $M\in\mathbb{F}^{k\times k}$
such that $\bm{m}_{i}GA_{i}=0$ for all $i\in[k]$, where $\bm{m}_{i}$ is the
$i$-th row of $M$.

The paper [BGM23] formulated a notion of higher order MDS codes called
GZP($\ell$). A linear code is GZP($\ell$) if it is MDS and attains all GZPs of
order at most $\ell$. We now formulate a rank-metric counterpart and a
strengthening of this notion:

######  Definition 1.8 ($\mathrm{GKP}(\ell)$).

Given a $[n,k]_{\mathbb{F}}$-linear code $C\subseteq\mathbb{F}^{n}$ with a
generator matrix $G\in\mathbb{F}^{k\times n}$, $C$ is said to be
$\mathrm{GKP}_{q}(\ell)$, or simply $\mathrm{GKP}(\ell)$, if $C$ is an MRD
code and attains all GKPs of order at most $\ell$.

######  Remark 1.9.

GKPs can be seen as a generalization of GZPs. For a GZP
$\mathcal{S}=(S_{1},\ldots,S_{k})$ with $S_{i}\subseteq[n]$, define
$\mathcal{V}=(V_{1},\dots,V_{k})$, where

$V_{i}=\left\\{(v_{1},\dots,v_{n})\in\mathbb{F}_{q}^{n}:v_{j}=0\text{ for
}j\in[n]\setminus S_{i}\right\\}.$

Then $\mathcal{S}$ is a GZP if and only if $\mathcal{V}$ is a GKP. Moreover,
an $[n,k]_{\mathbb{F}}$-linear code $C\subseteq\mathbb{F}^{n}$ over a field
$\mathbb{F}/\mathbb{F}_{q}$ attains $\mathcal{S}$ if and only if it attains
$\mathcal{V}$. Consequently, GKP($\ell$) codes are also GZP($\ell$).

We also prove an analog of the GM-MDS theorem, which we call the
_$\operatorname{GM-MRD}$ theorem_. Roughly speaking, it states that Gabidulin
codes attain all GKPs. This theorem is crucial in proving our main result that
random Gabidulin codes has the optimal list decodability in the rank metric. A
detailed discussion about the GM-MRD theorem is given at the end of this
section.

######  $\blacktriangleright\operatorname{MRD}(\ell)$.

One characterization of an $[n,k]_{\mathbb{F}}$-linear code
$C\subseteq\mathbb{F}^{n}$ being MDS is that its generator matrix
$G\subseteq\mathbb{F}^{k\times n}$ is an $\operatorname{MDS}$ matrix, meaning
that any $k$ columns of $G$ are linearly independent. Strengthening this
condition, for any $\ell\geq 1$, Brakensiek et al. [BGM23] defined an
$\operatorname{MDS}(\ell)$ code to be a linear code with a generator matrix
$G\subseteq\mathbb{F}^{k\times n}$ such that for any subsets
$S_{1},\dots,S_{\ell}\subseteq[n]$, each of size at most $k$, it holds that

$\dim\left(\bigcap_{i=1}^{\ell}G_{S_{i}}\right)=\dim\left(\bigcap_{i=1}^{\ell}W_{S_{i}}\right),$
(4)

where $W$ is the symbolic matrix $\left(Z_{i,j}\right)_{i\in[k],j\in[n]}$ over
the function field in the variables $Z_{1,1},\dots,Z_{k,n}$, and $G_{S}$
(resp. $W_{S}$) denotes the span of the columns of $G$ (resp. $W$) with
indices in $S$. Note that by definition, $\operatorname{MDS}(\ell)$ codes are
also $\operatorname{MDS}(\ell^{\prime})$ for $\ell^{\prime}\leq\ell$, and
$\operatorname{MDS}(1)$ codes are just (linear) $\operatorname{MDS}$ codes due
to the fact that the symbolic matrix $W$ is an MDS matrix.

To define the rank-metric counterpart of $\operatorname{MDS}(\ell)$, we first
express the column span $G_{S}$ in a linear-algebraic manner for
$S\subseteq[n]$ of size at most $k$. Let $I_{S}$ denote the $n\times|S|$
matrix that, when restricted to the subset of rows with indices in $S$,
becomes the identity matrix, and contains only zeros outside these rows. Then
$GI_{S}$ is precisely the $k\times|S|$ submatrix of $G$ formed by the columns
of $G$ with indices in $S$. Thus, $G_{S}$ is just the column space of
$GI_{S}$.

Suppose $\mathbb{F}$ is an extension field of $\mathbb{F}_{q}$. We extend the
notion of $\operatorname{MDS}(\ell)$ by replacing the matrix $I_{S}$ by an
arbitrary full-rank matrix $A\in\mathbb{F}_{q}^{n\times d}$, where $d\leq k$.
For convenience, we introduce the notations $G_{A}$ and $G_{V}$ as follows:
Define $G_{A}:=GA\in\mathbb{F}^{k\times d}$. Let
$V\subseteq\mathbb{F}_{q}^{n}$ be the column space of $A$ over
$\mathbb{F}_{q}$, and denote by $G_{V}\subseteq\mathbb{F}^{k}$ the column
space of $G_{A}$ over $\mathbb{F}$. This is well-defined as $G_{V}$ depends
only on $V$, not on $A$. Indeed, $G_{V}$ equals the $\mathbb{F}$-span of
$\sigma_{G}(V)$, where $\sigma_{G}:\mathbb{F}^{n}\to\mathbb{F}^{k}$ is the
linear map $\bm{v}\mapsto G\bm{v}$.

######  Definition 1.10 ($\operatorname{MRD}(\ell)$).

Let $\mathbb{F}$ be an extension field of $\mathbb{F}_{q}$. We say an
$[n,k]_{\mathbb{F}}$-linear code $C\subseteq\mathbb{F}^{n}$ is
$\operatorname{MRD}_{q}(\ell)$, or simply $\operatorname{MRD}(\ell)$, if for
any $\mathbb{F}_{q}$-linear subspaces $V_{1},\dots,V_{\ell}$ of
$\mathbb{F}_{q}^{n}$, each of dimension at most $k$, it holds that

$\dim_{\mathbb{F}}\left(\bigcap_{i=1}^{\ell}G_{V_{i}}\right)=\dim_{\mathbb{K}}\left(\bigcap_{i=1}^{\ell}W_{V_{i}}\right),$
(5)

where $W$ is the symbolic matrix $\left(Z_{i,j}\right)_{i\in[k],j\in[n]}$ over
the function field $\mathbb{K}:=\mathbb{F}_{q}(Z_{1,1},\dots,Z_{k,n})$.

By definition, $\operatorname{MRD}(\ell)$ codes are also
$\operatorname{MRD}(\ell^{\prime})$ for $\ell^{\prime}\leq\ell$. Moreover, it
can be shown that $\operatorname{MRD}(1)$ codes are just (linear)
$\operatorname{MRD}$ codes due to the fact that the symbolic matrix $W$ has
the MRD property. See Lemma 2.10 and Lemma 2.15.

Finally, we note that the condition (5) implies (4) by choosing the subspaces
$V_{i}$ to be the column space of $I_{S_{i}}$ over $\mathbb{F}_{q}$, i.e., the
subspace of all vectors $\bm{v}\in\mathbb{F}_{q}^{n}$ whose coordinates with
indices in $[n]\setminus S_{i}$ are zero. Consequently, all
$\operatorname{MRD}(\ell)$ codes are also $\operatorname{MDS}(\ell)$.

######  $\blacktriangleright\operatorname{LD-MRD}(\ell)$.

Recall that a code $C\subseteq\Sigma^{n}$ is $(\rho,\ell)$-list decodable if
for any $\bm{y}\in\Sigma^{n}$, it holds that $|\\{\bm{c}\in
C:d(\bm{c},\bm{y})\leq\rho n\\}|\leq\ell$. Equivalently, for any
$\bm{y}\in\Sigma^{n}$ and $\ell+1$ distinct codewords
$\bm{c}_{0},\dots,\bm{c}_{\ell}\in C$,

$\max_{0\leq i\leq\ell}d(\bm{c}_{i},\bm{y})>\rho n.$ (6)

The stronger notion of _$(\rho,\ell)$ -average-radius list decodability_ is
defined in the same way, except that we replace the maximum of the distances
$d(\bm{c}_{i},\bm{y})$ in (6) by the average of these distances. The formal
definition is given as follows.

######  Definition 1.11 (Average-radius list decodability).

A code $C\subseteq\Sigma^{n}$ is $(\rho,\ell)$ average-radius list decodable
if for any $\bm{y}\in\Sigma^{n}$ and $\ell+1$ distinct codewords
$\bm{c}_{0},\bm{c}_{1},\dots,\bm{c}_{\ell}\in C$, it holds that

$\frac{1}{\ell+1}\sum_{i=0}^{\ell}{d(\bm{y},\bm{c}_{i})}>\rho n.$

Recall that for an $[n,k]_{\mathbb{F}}$ linear code $C$, the list decoding
radius $\rho$ of $C$ satisfies the generalized Singleton bound
$\rho\leq\frac{\ell}{\ell+1}\left(1-\frac{k}{n}\right)$, both in the Hamming
metric and the rank metric. Roth [Rot22] first studied $\operatorname{LD-
MDS}(\ell)$ codes, which he referred to as
strongly-$\left(\frac{\ell(n-k)}{\ell+1},\ell\right)$-list decodable codes.
These are linear codes that meet the generalized Singleton bound under the
stricter criterion of average-radius list decodability. Inspired by Roth’s
work, Brakensiek, Gopi, and Makam further explored $\operatorname{LD-
MDS}(\ell)$ codes in their paper [BGM23].

We consider the natural rank-metric counterpart of $\operatorname{LD-
MDS}(\ell)$, defined as follows.

######  Definition 1.12 ($\operatorname{LD-MRD}(\ell)$).

Let $\mathbb{F}$ be an extension field of $\mathbb{F}_{q}$. We say an
$[n,k]_{\mathbb{F}}$-linear code $C\subseteq\mathbb{F}^{n}$ is
$\operatorname{LD-MRD}_{q}(\ell)$, or simply $\operatorname{LD-MRD}(\ell)$, if
$C$ is $\left(\frac{\ell}{\ell+1}\left(1-{k}/{n}\right),\ell\right)$-average-
radius list decodable in the rank metric. In other words, $C$ is
$\operatorname{LD-MRD}(\ell)$ if for any $\bm{y}\in\mathbb{F}^{n}$ and
$\ell+1$ distinct codewords $\bm{c}_{0},\bm{c}_{1},\dots,\bm{c}_{\ell}\in C$,
it holds that

$\sum_{i=0}^{\ell}{d_{R}(\bm{y},\bm{c}_{i})}>\ell(n-k),$

where
$d_{R}(\bm{y},\bm{c}_{i})=\mathrm{rank}_{\mathbb{F}_{q}}(\bm{y}-\bm{c}_{i})$
(see (1) for the definition of $\mathrm{rank}_{\mathbb{F}_{q}}$). We say $C$
is $\operatorname{LD-MRD}({\leq}\,\ell)$ if it is $\operatorname{LD-
MRD}(\ell^{\prime})$ for all $\ell^{\prime}\in[\ell]$.

It is straightforward to deduce from the definitions that all
$\operatorname{LD-MRD}({\leq}\,\ell)$ codes are MRD for all $\ell\geq 1$. For
a formal proof, see Lemma 2.12. In addition, all $\operatorname{LD-MRD}(\ell)$
codes are also $\operatorname{LD-MDS}(\ell)$. This follows from the fact that
the rank distance $d_{R}(\bm{x},\bm{y})$ is always bounded by the Hamming
distance $d_{H}(\bm{x},\bm{y})$.

##### Equivalence of higher order MRD codes.

Similar to the equivalence among the various notions of higher order MDS codes
established in [BGM23], we establish the equivalence among the three notions
of higher order MRD codes.

######  Theorem 1.13 ($1^{st}$ equivalence theorem).

For $\ell\geq 1$, a linear code $C$ over $\mathbb{F}/\mathbb{F}_{q}$ is
$\operatorname{GKP}(\ell)$ if and only if it is $\operatorname{MRD}(\ell)$.

######  Theorem 1.14 ($2^{nd}$ equivalence theorem).

For $\ell\geq 1$, a linear code $C$ over $\mathbb{F}/\mathbb{F}_{q}$ is
$\operatorname{MRD}(\ell+1)$ if and only if its dual code $C^{\perp}$ is
$\operatorname{LD-MRD}({\leq}\,\ell)$.

Combining the two theorems yields the following corollary.

######  Corollary 1.15.

Let $C$ be a linear code over $\mathbb{F}/\mathbb{F}_{q}$. Then the following
are all equivalent for $\ell\geq 1$:

  1. 1.

$C$ is $\operatorname{GKP}(\ell+1)$,

  2. 2.

$C$ is $\operatorname{MRD}(\ell+1)$, and

  3. 3.

$C^{\perp}$ is $\operatorname{LD-MRD}({\leq}\,\ell)$.

##### Dimension of generic intersections.

In the course of proving the equivalence among the three notions of higher
order MRD codes, we will establish the following formula for the dimension of
the intersection of a collection of subspaces $W_{V_{i}}$, where $W$ is the
symbolic matrix $(Z_{i,j})_{i\in[k],j\in[n]}$. This formula is used in both
the proof of 1.13 and that of 1.14.

######  Theorem 1.16 (Formula for generic intersection dimension).

Let $W$ be the $k\times n$ symbolic matrix $(Z_{i,j})_{i\in[k],j\in[n]}$ over
$\mathbb{F}:=\mathbb{F}_{q}(Z_{1,1},\dots,Z_{k,n})$. Let
$V_{1},\dots,V_{\ell}$ be subspaces of $\mathbb{F}_{q}^{n}$, each of dimension
at most $k$. Then

$\dim_{\mathbb{F}}\left(\bigcap_{i\in[\ell]}W_{V_{i}}\right)=\max_{P_{1}\sqcup
P_{2}\sqcup\cdots\sqcup
P_{s}=[\ell]}\left(\sum_{i\in[s]}\dim_{\mathbb{F}_{q}}\left(\bigcap_{j\in
P_{i}}V_{j}\right)-(s-1)k\right).$

The above formula generalizes a similar formula proven in [BGM23]. More
specifically, the formula in [BGM23] has the same form as (56), except it only
considers subspaces of the form $W_{S}$ for $S\subseteq[n]$ of size at most
$k$, i.e., $W_{S}$ is the span of the columns of $W$ with indices in $S$. As
discussed, every such $W_{S}$ can be realized as some $W_{V}$, where we choose
$V$ to be the subspace of all vectors $\bm{v}\in\mathbb{F}_{q}^{n}$ whose
coordinates with indices in $[n]\setminus S_{i}$ are all zero. On the other
hand, there are many subspaces $W_{V}$ that do not come from any $W_{S}$.
Thus, our formula is more general than that in [BGM23] and may be of
independent interest.

####  1.3.3 The GM-MRD Theorem

Similar to the GM-MDS theorem, which states that generic zero patterns are all
attained by Reed–Solomon codes, the GM-MRD theorem states that generic kernel
patterns are all attained by Gabidulin codes. We present two versions of the
GM-MRD theorem. The first one applies to symbolic Gabidulin codes, whereas the
second one applies to Gabidulin codes over finite fields.

######  Theorem 1.17 (GM-MRD theorem, informal version of 4.1).

Let $1\leq k\leq n$. Let $\mathbb{F}$ be the function field
$\mathbb{F}_{q}(Z_{1},\dots,Z_{n})$ be a function field. Then the
$[n,k]_{\mathbb{F}}$-linear symbolic Gabidulin code
$\mathcal{G}_{n,k}(Z_{1},\dots,Z_{n})$ defined by the generator matrix
$G=\left(Z_{j}^{q^{i-1}}\right)_{i\in[k],j\in[n]}\in\mathbb{F}^{k\times n}$ is
$\mathrm{GKP}(\ell)$ for all $\ell\geq 1$.

In the detailed version (4.1) of the above theorem, we also establish a bound
on the degree of $\det(M_{\mathcal{V}})\in\mathbb{F}[Z_{1},\dots,Z_{n}]$, for
each generic kernel pattern $\mathcal{V}$, where
$M_{\mathcal{V}}\in\mathbb{F}^{k\times k}$ is an invertible matrix such that
$MG$ exhibits the kernel pattern $\mathcal{V}$. By combining this degree bound
with the Schwartz–Zippel lemma and the union bound, we derive the finite field
GM-MRD theorem.

######  Theorem 1.18 (GM-MRD theorem, finite field version, 4.2).

Let $1\leq k\leq n\leq m$ and $\ell\geq 1$. Let
$(\alpha_{1},\dots,\alpha_{n})$ be uniformly distributed over the set of all
vectors in $\mathbb{F}_{q^{m}}^{n}$ whose coordinates are linearly independent
over $\mathbb{F}_{q}$. Then with probability at least
$1-3kq^{nk\cdot\min\\{\ell,k\\}+k-m}$, the $[n,k]_{\mathbb{F}_{q^{m}}}$-linear
Gabidulin code $\mathcal{G}_{n,k}(\alpha_{1},\dots,\alpha_{n})$ is
$\mathrm{GKP}(\ell)$.

We note that Yildiz and Hassibi previously proved that Gabidulin codes attain
all generic zero patterns, thus establishing the GM-MDS theorem for Gabidulin
codes ([YH19a], see also [YRH20]). However, as discussed, generic zero
patterns form only a subset of generic kernel patterns, making our GM-MRD
theorem formally stronger than the GM-MDS theorem for Gabidulin codes.

Similarly, while various other GM-MDS theorems have been established so far
[Lov18, YH19b, BDG23, RZVW24], including the “ultimate GM-MDS conjecture”
formulated in [BDG23], these theorems all focus on the attainability of zero
patterns rather than kernel patterns. Our GM-MRD theorem is, to our knowledge,
the first result that explores the broader category of kernel patterns, which
are more naturally connected with rank-metric codes, including MRD codes.
Understanding the inner connection between our GM-MRD theorem and the various
GM-MDS theorems, and even finding a unifying theory, would be very
interesting.

##### Proof of the GM-MRD theorem and $s$-admissible tuples.

Our proof of the GM-MRD theorem (1.17) follows the same structure of the
proofs of the GM-MDS theorem as presented in [Lov18, YH19b]. The approach
involves a careful induction on a collection of $\mathbb{F}_{q}$-linear spaces
$V_{1},\dots,V_{m}$, along with integers $r_{1},\dots,r_{m}\geq 1$, where
$r_{i}$ represents the “slackness” in the dimension of $V_{i}$. The induction
step is divided into several cases, enabling us to simplify each instance
gradually. Eventually, we arrive at the boundary instances for which the
theorem is straightforward to verify.

The proofs in [Lov18, YH19b] are very similar, focusing on subsets of the $n$
evaluation points $Z_{1},\dots,Z_{n}$, whereas we consider “evaluation
subspaces” spanned by linear forms in $Z_{1},\dots,Z_{n}$ over
$\mathbb{F}_{q}$. In addition, we need to consider $q$-linearized polynomials
and their composition in contrast to general polynomials and their
multiplication as used in the aforementioned works.

A serious difficulty that arises in the proof is the non-commutative nature of
the composition of $q$-linearized polynomials. More specifically, even though
our focus is on subspaces $V_{i}$ of linear forms in $Z_{1},\dots,Z_{n}$, the
induction steps require us to also consider subspaces that are the images of
$V_{i}$ under $q$-linearized polynomials
$f\in(\mathbb{F}_{q}[Z_{1},\dots,Z_{n}])[X]$, which may include nonlinear
forms in $Z_{1},\dots,Z_{n}$. To capture the structure of the tuples
$(V_{1},\dots,V_{m})$ that may arise, we introduce the notion of _$s$
-admissible tuples_ of subspaces (4.3), where $s$ is a parameter that bounds
the dimension of each subspace $V_{i}$. The family of $s$-admissible tuples is
carefully defined to be closed under the induction steps and to exhibit a
useful structure that facilitates the proof. For details, we refer the reader
to Section 4.

##### Duality of Gabidulin codes.

The last ingredient we need is the fact that the dual code of a Gabidulin code
is again a Gabidulin code (7.1).

Using the duality, our main theorem—that random Gabidulin codes have the
optimal list decodability (1.3)—follows readily from the equivalence of higher
order MRD codes and the GM-MRD theorem. More specifically, by 1.15, to prove
the claim that a random Gabidulin code $C$ over a sufficiently large finite
field $\mathbb{F}_{q^{m}}$ is $\operatorname{LD-MRD}({\leq}\,\ell)$ with high
probability, we need only demonstrate that its dual code $C^{\perp}$ is
$\operatorname{GKP}(\ell+1)$ with high probability. However, the dual code
$C^{\perp}$ is again a random Gabidulin code. Therefore, the claim easily
follows from the finite field GM-MRD theorem (4.2).

### Acknowledgments

The authors would like to thank Joshua Brakensiek, Manik Dhar, and Sivakanth
Gopi for many useful discussions and suggestions that helped this paper. Part
of this work was carried out while the first author and the fourth author were
visiting the Simons Institute for the Theory of Computing at UC Berkeley. They
would like to thank the institute for its support and hospitality.

##  2 Preliminaries

We first introduce the basic notation. Define $\mathbb{N}=\\{0,1,\dots\\}$,
$\mathbb{N}^{+}=\\{1,2,\dots\\}$, and $[n]=\\{1,\ldots,n\\}$. Denote by
$\mathbb{F}_{q}$ the finite field of size $q$. We use $\mathbb{F}$ to denote a
field that is an extension of $\mathbb{F}_{q}$. Let
$\overline{\mathbb{F}}_{q}$ be the algebraic closure of $\mathbb{F}_{q}$.

All vectors are column vectors unless stated otherwise. For
$v_{1},\ldots,v_{n}$ in a vector space $V$ over $\mathbb{F}$, the
$\mathbb{F}$-subspace $V$ spanned by $v_{1},\ldots,v_{n}$ is denoted by
$\mathrm{span}_{\mathbb{F}}\\{v_{1},\ldots,v_{n}\\}$, or simply
$\mathrm{span}\\{v_{1},\ldots,v_{n}\\}$ if $\mathbb{F}$ is clear from the
context. The set of $m\times n$ matrices over $\mathbb{F}$ is denoted by
$\mathbb{F}^{m\times n}$. The sum of two linear subspaces
$V_{1},V_{2}\subseteq\mathbb{F}^{n}$ is
$V_{1}+V_{2}:=\\{\bm{v}_{1}+\bm{v}_{i}:\bm{v}_{1}\in V_{1},\bm{v}_{2}\in
V_{2}\\}$. If $V_{1}\cap V_{2}=\\{0\\}$, we also write $V_{1}\oplus V_{2}$
instead of $V_{1}+V_{2}$. A _complement_ of a subspace $V_{1}\subseteq V$ in
$V$ is another subspace $V_{2}\subseteq V$ such that $V=V_{1}\oplus V_{2}$.
Denote by $V^{\perp}\subseteq\mathbb{F}^{n}$ the dual space of
$V\subseteq\mathbb{F}^{n}$ with respect to the inner product, i.e.,
$V^{\perp}=\\{\bm{v}\in\mathbb{F}^{n}:\bm{v}^{T}\bm{u}=0,\forall\bm{u}\in
V\\}$. Note that $\dim V^{\perp}=n-\dim V$ and $(V^{\perp})^{\perp}=V$.

We need the following two lemmas about vector spaces.

######  Lemma 2.1.

Let $V_{1},\ldots,V_{\ell}$ be subspaces of $\mathbb{F}^{n}$. Then
$\left(\bigcap_{i=1}^{\ell}V_{i}\right)^{\perp}=\sum_{i=1}^{\ell}V_{i}^{\perp}$.

###### Proof.

First, note that
$V_{i}^{\perp}\subseteq\left(\bigcap_{i=1}^{\ell}V_{i}\right)^{\perp}$ for all
$i\in[\ell]$. So
$\sum_{i=1}^{\ell}V_{i}^{\perp}\subseteq\left(\bigcap_{i=1}^{\ell}V_{i}\right)^{\perp}$.
Conversely, to prove that
$\sum_{i=1}^{\ell}V_{i}^{\perp}\supseteq\left(\bigcap_{i=1}^{\ell}V_{i}\right)^{\perp}$,
we will show the equivalent statement that
$\left(\sum_{i=1}^{\ell}V_{i}^{\perp}\right)^{\perp}\subseteq\bigcap_{i=1}^{\ell}V_{i}$.
Let $\bm{u}\in\left(\sum_{i=1}^{\ell}V_{i}^{\perp}\right)^{\perp}$. Then for
all $i\in[\ell]$, we have $\bm{u}\in(V_{i}^{\perp})^{\perp}=V_{i}$. So
$\bm{u}\in\bigcap_{i=1}^{\ell}V_{i}$. It follows that
$\left(\sum_{i=1}^{\ell}V_{i}^{\perp}\right)^{\perp}\subseteq\bigcap_{i=1}^{\ell}V_{i}$.
∎

######  Lemma 2.2.

Let $A_{1},\ldots,A_{m},B_{1},\ldots,B_{m}$ be subspaces of $\mathbb{F}^{n}$.
Then

$\dim\left(\bigcap_{i=1}^{m}(A_{i}+B_{i})\right)\leq\dim\left(\bigcap_{i=1}^{m}A_{i}\right)+\sum_{i=1}^{m}\dim(B_{i}).$

###### Proof.

Note that the inequality trivially holds if $B_{i}=\\{0\\}$ for all $i\in[m]$.
Then, we replace $\\{0\\}$ by $B_{i}$ for $i=1,\dots,m$ and note that the
replacement increases RHS by $\dim B_{i}$ and LHS by at most $\dim B_{i}$. The
claim follows. ∎

#####  $q$-linearized polynomials.

A polynomial of the form $f(X)=\sum_{i=0}^{\ell}a_{i}X^{q^{i}}$ with
coefficients $a_{i}$ in a commutative algebra $A$ over $\mathbb{F}_{q}$ is
called a _$q$ -linearized_ polynomial over $A$. It has the property that
$f(a+b)=f(a)+f(b)$ and $f(ca)=cf(a)$ for $a,b\in A$ and $c\in\mathbb{F}_{q}$.
The $q$-degree of $f(X)$, denoted by $\deg_{q}(f)$, is defined to be the
largest integer $\ell\geq 0$ such that $a_{\ell}\neq 0$. Throughout this
paper, $f$ is always a $q$-linearized polynomial unless stated otherwise. We
often view an extension field $\mathbb{F}$ of $\mathbb{F}_{q}$ as a
$\mathbb{F}_{q}$-linear space. For any $\mathbb{F}_{q}$-subspace
$V\subseteq\mathbb{F}$, define $f(V):=\\{f(\alpha):\alpha\in V\\}$, which is a
$\mathbb{F}_{q}$-linear subspace of $\mathbb{F}$ when $f$ is a $q$-linearized
polynomial.

For $\alpha_{1},\dots,\alpha_{m}\in\mathbb{F}$, where $\mathbb{F}$ is an
extension field of $\mathbb{F}_{q}$, the matrix

$M_{\alpha_{1},\dots,\alpha_{m}}=\left(\alpha_{i}^{q^{j-1}}\right)_{i\in[m],j\in[m]}\in\mathbb{F}^{m\times
m}$

is called the _Moore matrix_ associated with $\alpha_{1},\dots,\alpha_{m}$.
The following lemma characterizes its nonsingularity. For a proof, see, e.g.,
[Gos97, Lemma 1.3.3].

######  Lemma 2.3.

$\det(M_{\alpha_{1},\dots,\alpha_{m}})\neq 0$ if and only if
$\alpha_{1},\ldots,\alpha_{m}$ are linearly independent over $\mathbb{F}_{q}$.

We also need the following lemma regarding polynomials that vanish precisely
on an $\mathbb{F}_{q}$-linear subspace of $\mathbb{F}$.

######  Lemma 2.4.

Let $\mathbb{F}$ be an extension field of $\mathbb{F}_{q}$ and let
$V\subseteq\mathbb{F}$ be an $\mathbb{F}_{q}$-linear subspace. Then
$f=\prod_{\alpha\in V}(X-\alpha)\in\mathbb{F}[X]$ is a $q$-linearized
polynomial.

###### Proof.

Let $m=\dim V$ and let $\alpha_{1},\dots,\alpha_{m}$ form a basis of $V$.
Define the matrix

$M=\begin{pmatrix}\alpha_{1}&\alpha_{1}^{q}&\cdots&\alpha_{1}^{q^{m-1}}&\alpha_{1}^{q^{m}}\\\
\alpha_{2}&\alpha_{2}^{q}&\cdots&\alpha_{2}^{q^{m-1}}&\alpha_{2}^{q^{m}}\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
\alpha_{m}&\alpha_{m}^{q}&\cdots&\alpha_{m}^{q^{m-1}}&\alpha_{m}^{q^{m}}\\\
X&X^{q}&\cdots&X^{q^{m-1}}&X^{q^{m}}\end{pmatrix}\in\mathbb{F}(X)^{(m+1)\times(m+1)}.$

Note that the coefficient of $X^{q^{m}}$ in $\det(M)$ is
$\det(M_{\alpha_{1},\dots,\alpha_{m}})$, which is nonzero by Lemma 2.3. So
$\det(M)$ is a $q$-linearized polynomial of degree $q^{m}$ with the leading
coefficient $\det(M_{\alpha_{1},\dots,\alpha_{m}})$. It vanishes at any
$\mathbb{F}_{q}$-linear combination of $\alpha_{1},\dots,\alpha_{m}$, i.e., it
vanishes on the set $V$. So
$g:=\det(M_{\alpha_{1},\dots,\alpha_{m}})^{-1}\cdot\det(M)$ is a monic
$q$-linearized polynomial vanishing on $V$. But $f$ is another monic
polynomial that vanishes on $V$. So $f-g$ is a polynomial over $\mathbb{F}$ of
degree less that $q^{m}=|V|$ that vanishes on $V$. This implies $f-g=0$, i.e.,
$f=g$. So $f$ is a $q$-linearized polynomial. ∎

For a $k\times n$ matrix $G$ over an extension field $\mathbb{F}$ of
$\mathbb{F}_{q}$ and an $n\times\ell$ matrix $A$ over $\mathbb{F}_{q}$, define
$G_{A}:=GA\in\mathbb{F}^{k\times\ell}$. We denote by $\langle A\rangle$ the
$\mathbb{F}_{q}$-subspace of $\mathbb{F}_{q}^{n}$ spanned by the columns of
$A$. For an $\mathbb{F}_{q}$-subspace $V\subseteq\mathbb{F}_{q}^{n}$ and
$A\in\mathbb{F}_{q}^{n\times\dim V}$ such that $V=\langle A\rangle$, define
$G_{V}\subseteq\mathbb{F}^{k}$ to be the column span of $G_{A}$ over
$\mathbb{F}$.

##### Linear codes.

Let $\mathbb{F}$ be a field. An _$[n,k]_{\mathbb{F}}$ linear code_ (or
_$[n,k]_{\mathbb{F}}$ code_ for short) is simply a subspace of
$\mathbb{F}^{n}$ of dimension $k$. The _dual code_ of an $[n,k]_{\mathbb{F}}$
code $C$ is the $[n,n-k]_{\mathbb{F}}$ code $C^{\perp}$.

For an $[n,k]_{\mathbb{F}}$ code $C$, a matrix $G\in\mathbb{F}^{k\times n}$ is
said to be a _generator matrix_ of $C$ if
$C=\\{G^{T}\bm{u}:u\in\mathbb{F}^{k}\\}$, and a matrix
$H\in\mathbb{F}^{(n-k)\times n}$ is said to be a _parity check matrix_ of $C$
if $C=\\{\bm{v}\in\mathbb{F}^{n}:H\bm{v}=0\\}$. A generator matrix of $C$ is
also a parity check matrix of the dual code $C^{\perp}$. Similarly, a parity
check matrix of $C$ is also a generator matrix of $C^{\perp}$.

###  2.1 Rank-Metric Codes and Gabidulin Codes

We first review some basic facts and results about rank-metric codes. The
_rank distance_ $d(A,B)$ between two matrices $A,B\in\mathbb{F}_{q}^{m\times
n}$ is defined to be the rank of $A-B$, i.e., $d(A,B):=\mathrm{rank}(A-B)$.
Indeed, this defines a distance [Gab85]. A rank-metric code $C$ is a subset of
$\mathbb{F}_{q}^{m\times n}$ whose rate and minimum distance are given by

$R(C):=\frac{\log_{q}\left|C\right|}{nm}\quad\text{ and }\quad
d(C):=\min_{\begin{subarray}{c}A,B\in C\\\ A\neq B\end{subarray}}d(A,B).$

Without loss of generality, we always assume that $m\geq n$, since otherwise
we can exchange $n$ and $m$. It is convenient to treat an $m\times n$ matrix
$A$ over $\mathbb{F}_{q}$ as a vector
$\bm{v}=(v_{1},\ldots,v_{n})\in\mathbb{F}_{q^{m}}^{n}$ by identifying
$\mathbb{F}_{q}^{m}$ with $\mathbb{F}_{q^{m}}$ (by fixing a basis of
$\mathbb{F}_{q^{m}}$) and viewing each column of $A$ as an element in
$\mathbb{F}_{q^{m}}$. Then, we have
$\mathrm{rank}(A)=\dim_{\mathbb{F}_{q}}(\mathrm{span}_{\mathbb{F}_{q}}\\{v_{1},\ldots,v_{n}\\})$.
In this way, a rank-metric code $C$ may be viewed as a subset of
$\mathbb{F}_{q^{m}}^{n}$, and we can study linear rank-metric codes, i.e,
codes that are $\mathbb{F}_{q^{m}}$-subspaces.

##### Linear rank-metric codes over a general field
$\mathbb{F}/\mathbb{F}_{q}$.

It is convenient for us to consider a general notion of linear rank-metric
codes $C\subseteq\mathbb{F}^{n}$ over a field $\mathbb{F}/\mathbb{F}_{q}$ that
can even be infinite. To properly define this notion, we first define the
$\mathbb{F}_{q}$-rank and the kernel subspace of a vector
$\bm{v}\in\mathbb{F}^{n}$.

######  Definition 2.5 ($\mathbb{F}_{q}$-rank).

Let $\mathbb{F}$ be an extension field of $\mathbb{F}_{q}$. For
$\bm{v}=(v_{1},\dots,v_{n})\in\mathbb{F}^{n}$, define

$\mathrm{rank}_{\mathbb{F}_{q}}(\bm{v}):=\dim_{\mathbb{F}_{q}}(\mathrm{span}_{\mathbb{F}_{q}}\\{v_{1},\ldots,v_{n}\\}),$

called the _$\mathbb{F}_{q}$ -rank_ of $\bm{v}$.

######  Definition 2.6 (Kernel subspace).

For $\bm{v}=(v_{1},\dots,v_{n})\in\mathbb{F}^{n}$, define the
_$\mathbb{F}_{q}$ -kernel subspace_ (or simply the _kernel subspace_) of
$\bm{v}$ to be

$\ker_{\mathbb{F}_{q}}(\bm{v}):=\left\\{\bm{u}\in\mathbb{F}_{q}^{n}:\bm{u}^{T}\bm{v}=0\right\\}=\left\\{(u_{1},\dots,u_{n})\in\mathbb{F}_{q}^{n}:\sum_{i=1}^{n}u_{i}v_{i}=0\right\\}.$

The following lemma can be seen as an alternative definition of the
$\mathbb{F}_{q}$-rank.

######  Lemma 2.7.

$\mathrm{rank}_{\mathbb{F}_{q}}(\bm{v})=n-\dim_{\mathbb{F}_{q}}(\ker_{\mathbb{F}_{q}}(\bm{v}))$.

###### Proof.

Consider the $\mathbb{F}_{q}$-linear map $\mathbb{F}_{q}^{n}\to\mathbb{F}$
sending $\bm{u}\in\mathbb{F}_{q}^{n}$ to $\bm{u}^{T}\bm{v}$. The image of this
map is $\mathrm{span}_{\mathbb{F}_{q}}\\{v_{1},\ldots,v_{n}\\}$, whose
dimension is $\mathrm{rank}_{\mathbb{F}_{q}}(\bm{v})$ by definition. The
kernel of this map is $\ker_{\mathbb{F}_{q}}(\bm{v})$. So
$\mathrm{rank}_{\mathbb{F}_{q}}(\bm{v})=n-\dim_{\mathbb{F}_{q}}(\ker_{\mathbb{F}_{q}}(\bm{v}))$.
∎

We can now define the notion of a linear rank-metric code over a field
$\mathbb{F}/\mathbb{F}_{q}$.

######  Definition 2.8 (Linear rank-metric code).

Let $\mathbb{F}$ be an extension field of $\mathbb{F}_{q}$. An
_$[n,k]_{\mathbb{F}}$ $($linear$)$ rank-metric code_ is simply an
$[n,k]_{\mathbb{F}}$ code $C\subseteq\mathbb{F}^{n}$ equipped with the
distance function $d_{R}:\mathbb{F}^{n}\times\mathbb{F}^{n}\to\mathbb{N}$
defined by
$d_{R}(\bm{v},\bm{v}^{\prime}):=\mathrm{rank}_{\mathbb{F}_{q}}(\bm{v}-\bm{v}^{\prime})$.
The _minimum distance_ of $C$ is

$d(C):=\min_{\begin{subarray}{c}\bm{v},\bm{v}^{\prime}\in C\\\
\bm{v}\neq\bm{v}^{\prime}\end{subarray}}d_{R}(\bm{v},\bm{v}^{\prime})=\min_{\mathbf{0}\neq\bm{v}\in
C}\mathrm{rank}_{\mathbb{F}_{q}}(\bm{v}).$

In analogy with the classical scenario, one can prove the Singleton bound for
linear rank-metric codes.

######  Theorem 2.9 (Singleton bound).

Let $C$ be an $[n,k]_{\mathbb{F}}$ rank-metric code. Then $d(C)\leq
n-k+1$.666We remark that when $\mathbb{F}=\mathbb{F}_{q^{m}}$, there exists a
Singleton bound, $|C|\leq q^{m(n-d+1)}$, that also applies to nonlinear rank-
metric codes $C\subseteq\mathbb{F}^{n}$ [Gab85]. However, this bound is given
in terms of the size of the code, not the dimension, making it inapplicable
when $\mathbb{F}$ is infinite.

###### Proof.

There exists a nonzero codeword $\bm{v}=(v_{1},\dots,v_{n})\in C$ whose first
$k-1$ coordinates are zero. So
$d(C)\leq\mathrm{rank}_{\mathbb{F}_{q}}(\bm{v})=\dim_{\mathbb{F}_{q}}(\mathrm{span}_{\mathbb{F}_{q}}\\{v_{1},\ldots,v_{n}\\})=\dim_{\mathbb{F}_{q}}(\mathrm{span}_{\mathbb{F}_{q}}\\{v_{k},\ldots,v_{n}\\})\leq
n-k+1$. ∎

$[n,k]_{\mathbb{F}}$ rank-metric codes $C$ that attain the Singleton bound
(i.e., $d(C)=n-k+1$) are called MRD codes. The next lemma gives an alternative
characterization of MRD codes, which is crucial in this paper.

######  Lemma 2.10.

Let $G\in\mathbb{F}^{k\times n}$ be a generator matrix of an
$[n,k]_{\mathbb{F}}$ code $C$. Then the following are all equivalent:

  1. 1.

$C$ is $\operatorname{MRD}$.

  2. 2.

For any $A\in\mathbb{F}_{q}^{n\times k}$ of full rank, the matrix
$GA\in\mathbb{F}^{k\times k}$ also has full rank.

  3. 3.

For any $k^{\prime}\leq k$ and any $A^{\prime}\in\mathbb{F}_{q}^{n\times
k^{\prime}}$ of full rank, the matrix $GA^{\prime}\in\mathbb{F}^{k\times
k^{\prime}}$ also has full rank.

###### Proof.

Item 3 obviously implies Item 2. To see the converse, for any
$A^{\prime}\in\mathbb{F}_{q}^{n\times k^{\prime}}$ of full rank, where
$k^{\prime}\leq k$, we may extend $A^{\prime}$ to a matrix
$A\in\mathbb{F}_{q}^{n\times k}$ of full rank. As the columns of $GA^{\prime}$
form a subset of the columns of $GA$, if $GA$ has full rank (i.e., its columns
are linearly independent over $\mathbb{F}$), then so does $GA^{\prime}$. So
Item 2 implies Item 3.

To see that Item 2 implies Item 1, assume to the contrary that $C$ is not MRD,
i.e., there exists a nonzero codeword $\bm{v}\in C\subseteq\mathbb{F}^{n}$
such that $\mathrm{rank}_{\mathbb{F}_{q}}(\bm{v})\leq n-k$. Then, there exists
$A\in\mathbb{F}_{q}^{n\times k}$ of rank $k$ such that $\bm{v}^{T}A=0$. The
row vector $\bm{v}^{T}$ can be written as $\bm{x}^{T}G$ for some nonzero
$\bm{x}\in\mathbb{F}^{k}$. Then $\bm{x}^{T}GA=0$, implying that $GA$ does not
have full rank.

Conversely, to see that Item 1 implies Item 2, assume that $GA$ does not have
full rank for some $A\in\mathbb{F}_{q}^{n\times k}$ of full rank. Then there
exists nonzero $\bm{x}\in\mathbb{F}^{k}$ such that $\bm{x}^{T}GA=0$. Let
$\bm{v}=G^{T}\bm{x}=(\bm{x}^{T}G)^{T}\in\mathbb{F}^{n}$, which is a nonzero
codeword. Then $\bm{v}^{T}A=0$. As $A$ has rank $k$, we have
$\mathrm{rank}_{\mathbb{F}_{q}}(\bm{v})\leq n-k$ and hence $d(C)\leq n-k$. So
$C$ is not MRD. ∎

######  Lemma 2.11.

Let $C$ be an $[n,k]_{\mathbb{F}}$ code. If $C$ is $\operatorname{MRD}$, then
$C^{\perp}$ is also $\operatorname{MRD}$.

###### Proof.

By definition, $C^{\perp}$ is an $[n,n-k]_{\mathbb{F}}$ code. Let
$G\in\mathbb{F}^{k\times n}$ be a generator matrix of $C$, which is also a
parity check matrix of $C^{\perp}$. Assume to the contrary that $C^{\perp}$ is
not MRD. Then there exists nonzero $\bm{v}=(v_{1},\dots,v_{n})\in C^{\perp}$
such that $\mathrm{rank}_{\mathbb{F}_{q}}(\bm{v})=r\leq k$. By definition,
$\dim_{\mathbb{F}_{q}}(\mathrm{span}_{\mathbb{F}_{q}}\\{v_{1},\ldots,v_{n}\\})=r$.
Pick $z_{1},\dots,z_{r}\in\mathbb{F}$ that form a basis of
$\mathrm{span}_{\mathbb{F}_{q}}\\{v_{1},\ldots,v_{n}\\}$ over
$\mathbb{F}_{q}$, and let $\bm{z}=(z_{1},\dots,z_{r})\in\mathbb{F}^{r}$. Then
$\bm{v}=A\bm{z}$ for some $A\in\mathbb{F}_{q}^{n\times r}$ of rank $r$. As
$\bm{v}\neq 0$, we have $\bm{z}\neq 0$. Finally, as $\bm{v}\in C^{\perp}$, we
have $0=G\bm{v}=GA\bm{z}$. So $GA\in\mathbb{F}^{k\times r}$ does not have full
rank. By Lemma 2.10, $C$ is not MRD. ∎

We also record the basic fact that the properties of
$\operatorname{GKP}(\ell)$, $\operatorname{MRD}(\ell)$, and $\operatorname{LD-
MRD}({\leq}\,\ell)$ all imply the $\operatorname{MRD}$ property.

######  Lemma 2.12.

Let $\ell\geq 1$. A code that is $\operatorname{GKP}(\ell)$,
$\operatorname{MRD}(\ell)$, or $\operatorname{LD-MRD}({\leq}\,\ell)$ is also
$\operatorname{MRD}$.

###### Proof.

By definition, we only need to verify that an $\operatorname{LD-MRD}(1)$ code
is $\operatorname{MRD}$. Suppose $C$ is an $[n,k]_{\mathbb{F}}$ code that is
$\operatorname{LD-MRD}(1)$. Then $C$ is $\left(\rho,1\right)$-average radius
list decodable in the rank metric, where $\rho=\frac{1}{2}(1-k/n)$. Let
$\bm{v},\bm{v}^{\prime}\in C$ such that $d_{R}(\bm{v},\bm{v}^{\prime})=d(C)$,
and let $\bm{y}=\bm{v}$. Then
$d(C)=d_{R}(\bm{v},\bm{v}^{\prime})=d_{R}(\bm{y},\bm{v})+d_{R}(\bm{y},\bm{v}^{\prime})>2n\rho=n-k$.
So $d(C)\geq n-k+1$, i.e., $C$ is MRD. ∎

##### Gabidulin codes.

The most famous MRD codes are Gabidulin codes, which are defined by using the
evaluation of linearized polynomials. We briefly review the construction of
Gabidulin codes [Gab85] and extend it to a general field
$\mathbb{F}/\mathbb{F}_{q}$.

######  Definition 2.13 (Gabidulin code over $\mathbb{F}$).

Let $0<k\leq n$ be integers. Let $\mathbb{F}$ be an extension field of
$\mathbb{F}_{q}$ such that $[\mathbb{F}:\mathbb{F}_{q}]\geq n$. Let
$\alpha_{1},\dotsc,\alpha_{n}\in\mathbb{F}$ be linearly independent over
$\mathbb{F}_{q}$. Define

$\mathcal{G}_{n,k}(\alpha_{1},\dotsc,\alpha_{n}):=\left\\{\bm{x}_{f}=(f(\alpha_{1}),\ldots,f(\alpha_{n})):\;f\in\mathbb{F}[X]~{}\text{is
$q$-linearized and}~{}\deg_{q}(f)\leq k-1\right\\}.$

which is an $[n,k]_{\mathbb{F}}$ rank-metric code of minimum distance
$\min_{f\neq 0,\deg_{q}(f)<k}\mathrm{rank}_{\mathbb{F}_{q}}(\bm{x}_{f})$.

For a nonzero codeword
$\bm{x}_{f}=(f(\alpha_{1}),\ldots,f(\alpha_{n}))\in\mathcal{G}_{n,k}(\alpha_{1},\dotsc,\alpha_{n})$,
using the fact that $f$ is $q$-linearized, we have

$\ker_{\mathbb{F}_{q}}(\bm{x}_{f})=\left\\{(u_{1},\dots,u_{n})\in\mathbb{F}_{q}^{n}:\left(\sum_{i=1}^{n}u_{i}f(\alpha_{i})\right)=0\right\\}=\left\\{(u_{1},\dots,u_{n})\in\mathbb{F}_{q}^{n}:f\left(\sum_{i=1}^{n}u_{i}\alpha_{i}\right)=0\right\\}$

whose dimension over $\mathbb{F}_{q}$ is bounded by $k-1$ since
$\alpha_{1},\dots,\alpha_{n}$ are linearly independent over $\mathbb{F}_{q}$
and $f$ has at most $\deg(f)\leq q^{k-1}$ roots. So
$\mathrm{rank}_{\mathbb{F}_{q}}(\bm{x}_{f})\geq n-k+1$ by Lemma 2.7. This
shows that Gabidulin codes are MRD codes.

###  2.2 The MRD Property of the Generic Linear Code

We now show that the symbolic matrix $W=(Z_{i,j})_{i\in[k],j\in[n]}$ with
variables $Z_{i,j}$, which can be seen as a generator matrix of the
$[n,k]_{\mathbb{F}}$ “generic” linear code over
$\mathbb{F}=\mathbb{F}_{q}(Z_{1,1},\dots,Z_{k,n})$, has the MRD property. To
prove this statement, we need a tool known as the _Cauchy–Binet formula_.

######  Fact 2.14 (Cauchy–Binet formula (see, e.g., [Tao23])).

Let $\mathbb{F}$ be a field and $n\geq r$. Let $A$ be an $r\times n$ matrix
and $B$ be an $n\times r$ matrix over $\mathbb{F}$. For a subset
$S\subseteq[m]$ of size $r$, denote by $A_{S}$ the $r\times r$ submatrix of
$A$ whose columns are selected by $S$, and similarly, denote by $B^{S}$ the
$r\times r$ submatrix of $B$ whose rows are selected by $S$. Then,

$\det\left(AB\right)=\sum_{\begin{subarray}{c}S\subseteq[n]\\\
|S|=r\end{subarray}}\det(A_{S})\det(B^{S}).$

######  Lemma 2.15.

Let $r\leq k\leq n$ be positive integers. Let $W$ be the $k\times n$ matrix
$(Z_{i,j})_{i\in[k],j\in[n]}$ over the function field
$\mathbb{F}_{q}(Z_{1,1},\dots,Z_{k,n})$. Let $A$ be an $n\times r$ matrix of
full rank over $\mathbb{F}_{q}$. Then
$WA\in\mathbb{F}_{q}(Z_{1,1},\dots,Z_{k,n})^{k\times r}$ has the full rank of
$r$.

###### Proof.

By replacing $W$ with its top $r\times n$ submatrix, we may assume $k=r$. By
the Cauchy–Binet formula,

$\det\left(WA\right)=\sum_{\begin{subarray}{c}S\subseteq[n]\\\
|S|=r\end{subarray}}{\det(W_{S})\det(A^{S})}.$

Since $A$ is a full rank matrix over $\mathbb{F}_{q}$, there exists
$S\subseteq[n]$ of size $r$ such that $\det(A^{S})\neq 0$. Note that
$\det(W_{S})\neq 0$, which follows by expanding $\det(W_{S})$ into a linear
combination of monomials and using the fact that the entries of $W$ are
distinct variables $Z_{i,j}$. So $\det(W_{S})\det(A^{S})\neq 0$. For any
$S^{\prime}\subseteq[n]$ of size $r$, every monomial of
$\det(W_{S^{\prime}})\det(A^{S^{\prime}})$ has the form $Z_{1,i_{1}}\cdots
Z_{r,i_{r}}$ where $\\{i_{1},\dots,i_{r}\\}=S^{\prime}$. So the monomials of
$\det(W_{S})\det(A^{S})$ are different from those of
$\det(W_{S^{\prime}})\det(A^{S^{\prime}})$ when $S\neq S^{\prime}$. It follows
that $\det(WA)\neq 0$, i.e., $WA$ has full rank. ∎

##  3 Generic Kernel Patterns

In this section, we develop a structural theory regarding the concept of a
_generic kernel pattern_ of order $\ell$ over a finite field $\mathbb{F}_{q}$.
The notion of generic kernel patterns that we introduce can be viewed as a
natural generalization of _generic zero patterns_ studied in [DSY14b, Lov18,
YH19b, BGM23].

Recall that a tuple $\mathcal{V}=(V_{1},V_{2},\ldots,V_{k})$, where each
$V_{i}$ is a linear subspace of $\mathbb{F}_{q}^{n}$, is called a generic
kernel pattern over $\mathbb{F}_{q}$ if for every nonempty set
$\Omega\subseteq[k]$, we have

$\dim\left(\bigcap_{i\in\Omega}V_{i}\right)\leq k-|\Omega|.$

Furthermore, $\mathcal{V}$ is said to be _of order $\ell$_ if there are
exactly $\ell$ distinct nonzero subspaces among $V_{1},V_{2},\dots,V_{k}$.

We will now establish a general framework to precisely characterize generic
kernel patterns of order at most $\ell$, which play a crucial role in
understanding the list decodability of Gabidulin codes. To achieve this, we
will develop a linear-algebraic analog of the _generalized Hall’s theorem_ as
proved by Brakensiek, Gopi, and Makam in [BGM23].

We remark that, although the statements and proofs in this section are
presented over $\mathbb{F}_{q}$, sufficient for our applications, they remain
valid over a general field $\mathbb{F}$.

###  3.1 Generalized Hall’s Theorem for Vector Spaces

We start by proving the following theorem, which can be seen as a linear-
algebraic analog of [DSY14b, Theorem 2].

######  Theorem 3.1 (Hall’s theorem for vector spaces).

Let $n$ and $k$ be integers with $n\geq k\geq 0$. Let $V_{1},\dots,V_{k}$ be
subspaces of $\mathbb{F}_{q}^{n}$. Suppose

$\dim\left(\sum_{i\in\Omega}V_{i}\right)\geq n-k+|\Omega|$ (7)

holds for all nonempty $\Omega\subseteq[k]$. Then there exist subspaces
$V^{\prime}_{i}\subseteq V_{i}$, $i=1,\dots,k$, such that

  1. 1.

$\dim\left(\sum_{i\in\Omega}V^{\prime}_{i}\right)\geq n-k+|\Omega|$ for all
nonempty $\Omega\subseteq[k]$, and

  2. 2.

$\dim V^{\prime}_{i}=n-k+1$ for all $i\in[k]$.

###### Proof.

Our proof closely follows that of [DSY14b, Theorem 2]. First, if there exist
subspaces $\widetilde{V}_{1}\subseteq V_{1},\dots,\widetilde{V}_{k}\subseteq
V_{k}$ such that (7) holds for $\widetilde{V}_{1},\dots,\widetilde{V}_{k}$ and
at least one subspace $\widetilde{V}_{i}$ is a proper subspace of $V_{i}$,
then we may replace $V_{i}$ by $\widetilde{V}_{i}$ and prove the claim for the
new subspaces $\widetilde{V}_{1},\dots,\widetilde{V}_{k}$, which would imply
the claim for the original subspaces $V_{1},\dots,V_{k}$. By repeatedly doing
this, we may assume that $(V_{1},\dots,V_{k})$ is minimal (with respect to
component-wise inclusion) subject to the condition (7).

We will show that for the minimal $(V_{1},\dots,V_{k})$ satisfying (7), the
claim holds by choosing $V_{i}^{\prime}=V_{i}$ for $i\in[k]$. Note that Item 1
is just (7) as $V_{i}^{\prime}=V_{i}$. Assume to the contrary that Item 2 does
not hold. Then there exists $r\in[k]$ such that

$\dim V_{r}\geq n-k+2\geq 2.$ (8)

This is because we have $\dim V_{i}\geq n-k+1$ for all $i\in[k]$ by Item 1
and, as Item 2 does not hold, the equality is not attained for some $i\in[k]$.

Pick linearly independent $a,b\in V_{r}$ and let $V_{a,b}$ be a complement of
$\mathrm{span}\\{a,b\\}$ in $V_{r}$, i.e.,
$V_{r}=V_{a,b}\oplus\mathrm{span}\\{a,b\\}$. For $i\in[k]$, define

$V_{i}^{a}=\begin{cases}V_{a,b}\oplus\mathrm{span}\\{a\\},&\text{ if }i=r,\\\
V_{i},&\text{ otherwise, }\end{cases}\quad\text{and}\quad
V_{i}^{b}=\begin{cases}V_{a,b}\oplus\mathrm{span}\\{b\\},&\text{ if }i=r,\\\
V_{i},&\text{ otherwise. }\end{cases}$

By the minimality of $(V_{1},\dots,V_{k})$, both $(V_{1}^{a},\dots,V_{k}^{a})$
and $(V_{1}^{b},\dots,V_{k}^{b})$ violate (7). Moreover, (7) is violated only
for nonempty sets $\Omega\subseteq[k]$ that contain $r$ since $V_{i}^{a}$ and
$V_{i}^{b}$ agree with $V_{i}$ if $i\neq r$. Therefore, there exist
$A,B\subseteq[k]$ not containing $r$ such that

$\dim\left(\sum_{i\in
A\cup\\{r\\}}V_{i}^{a}\right)<n-k+|A|+1\quad\text{and}\quad\dim\left(\sum_{i\in
B\cup\\{r\\}}V_{i}^{b}\right)<n-k+|B|+1.$

On the other hand, note that $\sum_{i\in
A\cup\\{r\\}}V_{i}^{a}\supseteq\sum_{i\in A}V_{i}$ and $\dim(\sum_{i\in
A}V_{i})\geq n-k+|A|$. So we must have

$\dim\left(\sum_{i\in
A\cup\\{r\\}}V_{i}^{a}\right)=n-k+|A|\quad\text{and}\quad\sum_{i\in
A\cup\\{r\\}}V_{i}^{a}=\sum_{i\in A}V_{i}.$ (9)

Similarly,

$\dim\left(\sum_{i\in
B\cup\\{r\\}}V_{i}^{b}\right)=n-k+|B|\quad\text{and}\quad\sum_{i\in
B\cup\\{r\\}}V_{i}^{b}=\sum_{i\in B}V_{i}.$ (10)

It follows that

$\left(\sum_{i\in A\cup\\{r\\}}V_{i}^{a}\right)\cap\left(\sum_{i\in
B\cup\\{r\\}}V_{i}^{b}\right)=\left(\sum_{i\in
A}V_{i}\right)\cap\left(\sum_{i\in B}V_{i}\right).$ (11)

As $V_{r}=V_{r}^{a}+V_{r}^{b}$, we also have

$\left(\sum_{i\in A\cup\\{r\\}}V_{i}^{a}\right)+\left(\sum_{i\in
B\cup\\{r\\}}V_{i}^{b}\right)=\sum_{i\in A\cup B\cup\\{r\\}}V_{i}.$ (12)

Then

$\displaystyle 2(n-k)+|A|+|B|$ (13)
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:via},\eqref{eq:vib}}}{{=}}\dim\left(\sum_{i\in
A\cup\\{r\\}}V_{i}^{a}\right)+\dim\left(\sum_{i\in
B\cup\\{r\\}}V_{i}^{b}\right)$ $\displaystyle=\dim\left(\left(\sum_{i\in
A\cup\\{r\\}}V_{i}^{a}\right)+\left(\sum_{i\in
B\cup\\{r\\}}V_{i}^{b}\right)\right)+\dim\left(\left(\sum_{i\in
A\cup\\{r\\}}V_{i}^{a}\right)\cap\left(\sum_{i\in
B\cup\\{r\\}}V_{i}^{b}\right)\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{ff1},\eqref{ff2}}}{{=}}\dim\left(\sum_{i\in
A\cup B\cup\\{r\\}}V_{i}\right)+\dim\left(\left(\sum_{i\in
A}V_{i}\right)\cap\left(\sum_{i\in B}V_{i}\right)\right).$

By (7), we have

$\dim\left(\sum_{i\in A\cup B\cup\\{r\\}}V_{i}\right)\geq n-k+|A\cup B|+1.$
(14)

We claim that

$\dim\left(\left(\sum_{i\in A}V_{i}\right)\cap\left(\sum_{i\in
B}V_{i}\right)\right)\geq n-k+|A\cap B|$ (15)

which will be proved shortly. Then

$\displaystyle 2(n-k)+|A|+|B|$
$\displaystyle\stackrel{{\scriptstyle\eqref{ff3}}}{{=}}\dim\left(\sum_{i\in
A\cup B\cup\\{r\\}}V_{i}\right)+\dim\left(\left(\sum_{i\in
A}V_{i}\right)\cap\left(\sum_{i\in B}V_{i}\right)\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:sum-of-
vi},\eqref{ff4}}}{{\geq}}2(n-k)+|A|+|B|+1,$

which is impossible. So Item 2 holds.

It remains to prove $\eqref{ff4}$. In the case where $A\cap B\neq\emptyset$,
this follows immediately from $\eqref{1}$ and the fact that
$\dim\left(\left(\sum_{i\in A}V_{i}\right)\cap\left(\sum_{i\in
B}V_{i}\right)\right)\geq\dim\left(\sum_{i\in A\cap B}V_{i}\right)$. Now
assume $A\cap B=\emptyset$. By (9) and (10), we have
$V_{r}^{a}\subseteq\sum_{i\in A}V_{i}$ and $V_{r}^{b}\subseteq\sum_{i\in
B}V_{i}$. This implies

$\dim\left(\left(\sum_{i\in A}V_{i}\right)\cap\left(\sum_{i\in
B}V_{i}\right)\right)\geq\dim\left(V_{r}^{a}\cap V_{r}^{b}\right)=\dim
V_{a,b}=\dim
V_{r}-2\stackrel{{\scriptstyle\eqref{eq:Vr}}}{{\geq}}n-k=n-k+|A\cap B|,$

which proves (15). ∎

Instead of directly using 3.1, we will in fact use its dual version, which is
stated as follows.

######  Corollary 3.2 (Hall’s theorem for vector spaces, the dual version).

Let $n$ and $k$ be integers with $n\geq k\geq 0$. Let $V_{1},\dots,V_{k}$ be
subspaces of $\mathbb{F}_{q}^{n}$. Suppose

$\dim\left(\bigcap_{i\in\Omega}V_{i}\right)\leq k-|\Omega|$ (16)

holds for all nonempty $\Omega\subseteq[k]$. Then there exist subspaces
$V^{\prime}_{i}$ of $\mathbb{F}_{q}^{n}$ containing $V_{i}$, $i=1,\dots,k$,
such that

  1. 1.

$\dim\left(\bigcap_{i\in\Omega}V^{\prime}_{i}\right)\leq k-|\Omega|$ for all
nonempty $\Omega\subseteq[k]$, and

  2. 2.

$\dim V^{\prime}_{i}=k-1$ for all $i\in[k]$.

###### Proof.

Let $H_{i}=V_{i}^{\perp}\subseteq\mathbb{F}_{q}^{n}$ for $i\in[k]$. For any
nonempty $\Omega\subseteq[k]$, we have
$\left(\bigcap_{i\in\Omega}V_{i}\right)^{\perp}=\sum_{i\in\Omega}H_{i}$ by
Lemma 2.1. So (16) is equivalent to
$\dim\left(\sum_{i\in\Omega}H_{i}\right)\geq n-k+|\Omega|$. Applying 3.1 to
$H_{1},\dots,H_{k}$, we obtain subspaces $H_{i}^{\prime}\subseteq H_{i}$ such
that $\dim\left(\sum_{i\in\Omega}H^{\prime}_{i}\right)\geq n-k+|\Omega|$ for
all nonempty $\Omega\subseteq[k]$ and $\dim H^{\prime}_{i}=n-k+1$ for all
$i\in[k]$.

Let $V_{i}^{\prime}=(H_{i}^{\prime})^{\perp}$ for $i\in[k]$, so that
$V_{i}^{\prime}\supseteq V_{i}$. For every nonempty $\Omega\subseteq[k]$, we
have
$\left(\bigcap_{i\in\Omega}V_{i}^{\prime}\right)^{\perp}=\sum_{i\in\Omega}H_{i}^{\prime}$
by Lemma 2.1. So
$\dim\left(\bigcap_{i\in\Omega}V^{\prime}_{i}\right)=n-\dim\left(\sum_{i\in\Omega}H^{\prime}_{i}\right)\leq
k-|\Omega|$, proving Item 1. And for $i\in[k]$, we have $\dim
V^{\prime}_{i}=\dim(H^{\prime}_{i})^{\perp}=n-\dim H^{\prime}_{i}=k-1$,
proving Item 2. ∎

We also need the following equivalence.

######  Proposition 3.3.

Let $n$ and $k$ be integers with $n\geq k\geq 0$. Let $V_{1},\ldots,V_{\ell}$
be subspaces of $\mathbb{F}_{q}^{n}$, each of dimension at most $k$. Then the
following are equivalent.

  1. 1.

There exist integers $\delta_{1},\ldots,\delta_{\ell}\geq 0$ such that for
every nonempty $\Omega\subseteq[\ell]$,

$\dim\left(\bigcap_{i\in\Omega}V_{i}\right)\leq
k-\sum_{i\in\Omega}\delta_{i}.$ (17)

  2. 2.

The pattern $(T_{1},\ldots,T_{k})$ that consists of $\delta_{i}$ copies of
$V_{i}$ for $i\in[\ell]$ and additional $k-\sum_{i=1}^{\ell}\delta_{i}$ copies
of $\\{0\\}$ is a generic kernel pattern.777We assume that the set of copies
of each $V_{i}$ is disjoint from both the set of copies of any other
$V_{i^{\prime}}$ (even if $V_{i}=V_{i^{\prime}}$) and the set of the
additional $k-\sum_{j=1}^{\ell}\delta_{j}$ copies of $\\{0\\}$ (even if
$V_{i}=\\{0\\}$). That is, for every nonempty $\Omega^{\prime}\subseteq[k]$,

$\dim\left(\bigcap_{i\in\Omega^{\prime}}T_{i}\right)\leq k-|\Omega^{\prime}|.$
(18)

###### Proof.

We first prove that Item 1 implies Item 2. Let
$d=k-\sum_{i=1}^{\ell}\delta_{i}$. Let $\Omega^{\prime}\subseteq[k]$ be a
nonempty set. We want to show that (18) holds. If $\Omega^{\prime}$ contains
at least one $i\in[k]$ with $T_{i}=\\{0\\}$, then (18) holds trivially. So
assume $T_{i}\neq\\{0\\}$ for all $i\in\Omega^{\prime}$. Moreover, we may
assume that for each $V_{i}$ that appears in $(T_{i})_{i\in\Omega^{\prime}}$,
all the $\delta_{i}$ copies of $V_{i}$ also appear, since including these
copies does not change LHS of (18) and can only decrease RHS. With this
assumption, (18) just becomes (17).

To prove the other direction, consider any nonempty $\Omega\subseteq[\ell]$.
Let $\Omega^{\prime}$ be the subset of $[k]$ that consists of the indices of
all the $\delta_{i}$ copies of $V_{i}$ in $[k]$ for $i\in\Omega$ and no other
indices. Applying (18) with the set $\Omega^{\prime}$ then yields (17). ∎

The following theorem is a linear-algebraic analog of the generalized Hall’s
theorem as proved in [BGM23].

######  Theorem 3.4 (Generalized Hall’s theorem for vector spaces).

Let $n$ and $k$ be integers with $n\geq k\geq 0$. Let $V_{1},\ldots,V_{\ell}$
be subspaces of $\mathbb{F}_{q}^{n}$, each of dimension at most $k$. Suppose
there exist integers $\delta_{1},\ldots,\delta_{\ell}\geq 0$ such that for
every nonempty $\Omega\subseteq[\ell]$, (17) holds. Then, there exist
subspaces $V^{\prime}_{i}\supseteq V_{i}$ of dimension $k-\delta_{i}$,
$i=1,\dots,\ell$, such that for every nonempty $\Omega\subseteq[\ell]$, (17)
also holds for $V^{\prime}_{1},\ldots,V^{\prime}_{\ell}$, i.e.,
$\dim\left(\bigcap_{i\in\Omega}V^{\prime}_{i}\right)\leq
k-\sum_{i\in\Omega}\delta_{i}$.

Note that 3.4 can also be viewed as a generalization of 3.2, taking into
account the “multiplicities” $\delta_{i}$. Indeed, 3.2 can be derived from 3.4
by setting $\ell=k$ and choosing $\delta_{1}=\dots=\delta_{\ell}=1$.

###### Proof of 3.4.

By (17), we have $\dim V_{i}\leq k-\delta_{i}$ for $i\in[\ell]$. If $\dim
V_{i}=k-\delta_{i}$ holds for all $i\in[\ell]$, then we are done by choosing
$V_{i}^{\prime}=V_{i}$. So assume this is not the case. Without loss of
generality, we may assume $\dim V_{1}<k-\delta_{1}$.

We want to extend $V_{1}$ to a larger subspace $V^{\prime}_{1}$ of dimension
$k-\delta_{1}$ while still satisfying (17) for all nonempty
$\Omega\subseteq[\ell]$. If $\delta_{1}=0$, then we can choose any subspace
$V^{\prime}_{1}$ of dimension $k$ containing $V_{1}$. This is because (17)
holds for any nonempty $\Omega\subseteq[\ell]$ that excludes $1$. Adding $1$
to $\Omega$ can only decrease LHS of (17) while RHS remains unchanged.

Now assume $\delta_{1}>0$. By 3.3, there exists a generic kernel pattern
$(T_{1},\ldots,T_{k})$ consisting of $\delta_{i}$ copies of $V_{i}$ for
$i\in[\ell]$ and $k-\sum_{i=1}^{\ell}\delta_{i}$ copies of $\\{0\\}$. For
$i\in[\ell]$, let $J_{i}$ be the set of indices $j\in[k]$ such that $T_{j}$ is
among the $\delta_{i}$ copies of $V_{i}$. So $|J_{i}|=\delta_{i}$. Fix an
arbitrary subspace $V\subseteq\mathbb{F}_{q}^{n}$ of dimension $k$ such that
$V_{1}\subseteq V$.

Let $S_{i}=T_{i}\cap V$ for $i\in[k]$. The fact that $(T_{1},\ldots,T_{k})$ is
a generic kernel pattern implies that $(S_{1},\ldots,S_{k})$ is also a generic
kernel pattern as replacing $T_{i}$ with $S_{i}$ can only decrease LHS of
(18). Applying 3.2 to $S_{1},\dots,S_{k}\subseteq V$ and the ambient space
$V$, we see that there exist subspaces $S^{\prime}_{i}$ of $V$ containing
$S_{i}$, $i=1,\dots,k$, such that $\dim S_{i}^{\prime}=k-1$ for $i\in[k]$ and

$\dim\left(\bigcap_{i\in\Omega}S^{\prime}_{i}\right)\leq
k-|\Omega|\quad\text{for nonempty }\Omega\subseteq[k].$ (19)

For $i\in[\ell]$, we define

$U_{i}=\begin{cases}\bigcap_{j\in J_{i}}S^{\prime}_{j},&\text{ if
}J_{i}\neq\emptyset,\\\ V,&\text{ otherwise}.\end{cases}$ (20)

For $i\in[\ell]$, if $J_{i}\neq\emptyset$, then $U_{i}\supseteq\bigcap_{j\in
J_{i}}S_{j}=V_{i}\cap V$. And if $J_{i}=\emptyset$, then $U_{i}=V\supseteq
V_{i}\cap V$. So $V_{i}\cap V\subseteq U_{i}$ in either case. In particular,
as $V_{1}\subseteq V$, we have $V_{1}=V_{1}\cap V\subseteq U_{1}$.

We claim that $\dim U_{1}=k-\delta_{1}$. If $J_{1}=\emptyset$, then
$\delta_{1}=|J_{1}|=0$ and $\dim U_{1}=\dim V=k=k-\delta_{1}$. So the claim
holds in the case. Now consider the case where $J_{1}\neq\emptyset$. By (19)
and (20), we have

$\dim U_{1}=\dim\left(\bigcap_{i\in J_{1}}S^{\prime}_{i}\right)\leq
k-|J_{1}|=k-\delta_{1}.$

Moreover, since each $S^{\prime}_{i}$ is a subspace of $V$ of codimension one,
we have

$\dim U_{1}=\dim\left(\bigcap_{j\in J_{1}}S^{\prime}_{i}\right)\geq
k-|J_{1}|=k-\delta_{1}.$

This proves the claim that $\dim U_{1}=k-\delta_{1}$.

Next, we show that (17) still holds for all nonempty $\Omega\subseteq[\ell]$
after replacing $V_{1}$ by $U_{1}$. We only need to verify this for nonempty
$\Omega\subseteq[\ell]$ that contains $1$. Fix such $\Omega$ and let
$\Omega^{\prime}=\bigcup_{i\in\Omega}J_{i}\subseteq[k]$. Note
$|\Omega^{\prime}|=\sum_{i\in\Omega}|J_{i}|$ since the sets $J_{i}$ are
disjoint. Then

$\displaystyle
k-\sum_{i\in\Omega}\delta_{i}=k-\sum_{i\in\Omega}|J_{i}|=k-|\Omega^{\prime}|\stackrel{{\scriptstyle\eqref{eq:Si-
intersection}}}{{\geq}}\dim\left(\bigcap_{i\in\Omega^{\prime}}S^{\prime}_{i}\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:def-
Ui}}}{{=}}\dim\left(\bigcap_{i\in\Omega}U_{i}\right)\geq\dim\left(U_{1}\cap\bigcap_{i\in\Omega\setminus\\{1\\}}(V_{i}\cap
V)\right)=\dim\left(U_{1}\cap\bigcap_{i\in\Omega\setminus\\{1\\}}V_{i}\right),$

where the last step uses the fact that $U_{1}\subseteq V$ and the second last
step uses the fact that $V_{i}\cap V\subseteq U_{i}$ for $i\in[\ell]$. So (17)
holds with $U_{1}$ in place of $V_{1}$.

By repeating the above argument, we obtain subspaces $V^{\prime}_{i}\supseteq
V_{i}$ of dimension $k-\delta_{i}$, where $i=1,\dots,\ell$, that satisfy (17)
for all nonempty $\Omega\subseteq[\ell]$. This completes the proof. ∎

######  Corollary 3.5.

Let $n$ and $k$ be integers with $n\geq k\geq 0$. Let
$\mathcal{T}=(T_{1},\ldots,T_{k})$ be a generic kernel pattern consisting of
$\delta_{i}$ copies of $V_{i}\subseteq\mathbb{F}_{q}^{n}$ for $i\in[\ell]$ and
$k-\sum_{i=1}^{\ell}\delta_{i}$ copies of $\\{0\\}$. Then, there exist
subspaces $V^{\prime}_{i}\supseteq V_{i}$ of dimension $k-\delta_{i}$,
$i=1,\dots,\ell$, such that
$\mathcal{T^{\prime}}=(T^{\prime}_{1},\ldots,T^{\prime}_{k})$ consisting of
$\delta_{i}$ copies of $V^{\prime}_{i}$ for $i\in[\ell]$ and
$k-\sum_{i=1}^{\ell}\delta_{i}$ copies of $\\{0\\}$ is a generic kernel
pattern.

###### Proof.

Combining 3.3 and 3.4 proves the corollary. ∎

###  3.2 Generic Kernel Patterns of Order at Most $\ell$

The main result of this subsection is the following statement, which gives a
characterization of general kernel patterns of order at most $\ell$.

######  Lemma 3.6.

Let $n$, $k$, and $d$ be integers with $n\geq k\geq d\geq 0$. Let
$V_{1},\ldots,V_{\ell}$ be subspaces of $\mathbb{F}_{q}^{n}$, each of
dimension at most $k$. Then the following are equivalent.

  1. 1.

There exists a generic kernel pattern $\mathcal{T}:=(T_{1},T_{2},\dots,T_{k})$
consisting solely of copies of $V_{1},\ldots,V_{\ell}$ and an additional $d$
copies of $\\{0\\}$.

  2. 2.

There exist integers $\delta_{1},\ldots,\delta_{\ell}\geq 0$ such that
$\sum_{i=1}^{\ell}\delta_{i}=k-d$ and for every nonempty
$\Omega\subseteq[\ell]$,

$\dim\left(\bigcap_{i\in\Omega}V_{i}\right)\leq
k-\sum_{i\in\Omega}\delta_{i}.$ (21)

  3. 3.

For all partitions $P_{1}\sqcup P_{2}\sqcup\cdots\sqcup P_{s}=[\ell]$, we have

$\sum_{i=1}^{s}\dim\left(\bigcap_{j\in P_{i}}V_{j}\right)\leq(s-1)k+d.$ (22)

###### Proof.

By 3.3, Item 1 is equivalent to Item 2. And Item 2 implies Item 3 because for
any partition $P_{1}\sqcup P_{2}\sqcup\cdots\sqcup P_{s}=[\ell]$, we have

$\sum_{i=1}^{s}\dim\left(\bigcap_{j\in
P_{i}}V_{j}\right)\stackrel{{\scriptstyle\eqref{eq:cond2}}}{{\leq}}\sum_{i=1}^{s}\left(k-\sum_{j\in
P_{i}}\delta_{j}\right)=sk-(k-d)=(s-1)k+d.$

Finally, we prove that Item 3 implies Item 2 via an induction on $\ell$. When
$\ell=1$, Item 2 and Item 3 are the same. Now consider $\ell\geq 2$ and assume
that Item 3 implies Item 2 for $\ell^{\prime}<\ell$. We say a partition
$P_{1}\sqcup P_{2}\sqcup\cdots\sqcup P_{s}$ of $[\ell]$ is _tight_ if (22)
holds with equality.

Suppose Item 3 holds. We claim that there exist subspaces
$V^{\prime}_{i}\supseteq V_{i}$ of dimension at most $k$, $i=1,\dots,\ell$,
such that for these new subspaces, which we call _padded subspaces_ , Item 3
still holds and there exists a partition $P_{1}\sqcup P_{2}\sqcup\cdots\sqcup
P_{s}$ of $[\ell]$ with $s\geq 2$ that is tight.

The remaining proof consists of two parts: We will first prove the above
claim. Then we will show that Item 2 holds for the padded subspaces
$V_{1}^{\prime},\dots,V_{\ell}^{\prime}$. This suffices since Item 2 then
holds for the original subspaces $V_{1},\dots,V_{\ell}$ as well by the fact
that $\bigcap_{i\in\Omega}V_{i}\subseteq\bigcap_{i\in\Omega}V_{i}^{\prime}$
for all nonempty $\Omega\subseteq[\ell]$.

For convenience, define $V_{\Omega}=\bigcap_{i\in\Omega}V_{i}$ for nonempty
$\Omega\subseteq[\ell]$. Applying Item 3 to the coarsest partition of $[\ell]$
shows that $\dim V_{[\ell]}\leq d$.

To prove the claim, we repeatedly select pairs $(V_{i},\bm{v})$, where $\dim
V_{i}<k$ and $\bm{v}\in\mathbb{F}_{q}^{n}\setminus V_{i}$, and then replace
$V_{i}$ with $V_{i}\oplus\mathrm{span}(\bm{v})$, until one of the partitions
of $[\ell]$ becomes tight.888Note that at least one partition becomes tight
when (or before) $\dim V_{i}=k$ for all $i\in[k]$. This is because (1) if all
$V_{i}$ have dimension $k$, then we would have $\sum_{i=1}^{\ell}\dim
V_{i}=\ell k\geq(\ell-1)k+d$, and (2) replacing $V_{i}$ with
$V_{i}\oplus\mathrm{span}(\bm{v})$ increases LHS of (22) by at most one. If
the tight partition $P_{1}\sqcup\cdots\sqcup P_{s}$ arising this way satisfies
$s\geq 2$, then we are done. So assume $s=1$, i.e., $\dim V_{[\ell]}=d$. In
this case, we show that we can continue padding the subspaces $V_{i}$ until
another partition with $s\geq 2$ becomes tight, while maintaining $\dim
V_{[\ell]}=d$.

For $i\in[\ell]$, applying Item 3 to the partition
$\\{i\\}\sqcup([\ell]\setminus\\{i\\})$ of $[\ell]$ shows

$\dim V_{i}+\dim\left(\bigcap_{j\in[\ell]\setminus\\{i\\}}V_{j}\right)\leq
k+d.$ (23)

By inclusion-exclusion and the fact that $\dim V_{[\ell]}=d$, we have that for
$i\in[\ell]$,

$\dim\left(V_{i}+\bigcap_{j\in[\ell]\setminus\\{i\\}}V_{j}\right)=\dim
V_{i}+\dim\left(\bigcap_{j\in[\ell]\setminus\\{i\\}}V_{j}\right)-\dim
V_{[\ell]}\stackrel{{\scriptstyle\eqref{eq:special-partition}}}{{\leq}}k.$

If there exists $i\in[\ell]$ such that
$\dim\left(V_{i}+\bigcap_{j\in[\ell]\setminus\\{i\\}}V_{j}\right)=k$, then
(23) must hold with equality. In this case, the partition
$\\{i\\}\sqcup[\ell]\setminus\\{i\\}$ is tight and we are done. So assume

$\dim\left(V_{i}+\bigcap_{j\in[\ell]\setminus\\{i\\}}V_{j}\right)<k\leq
n\quad\text{ for all }i\in[\ell].$ (24)

Fix arbitrary $i\in[\ell]$. By (24), there exists a vector
$\bm{v}\in\mathbb{F}_{q}^{n}\setminus(V_{i}+\bigcap_{j\in[\ell]\setminus\\{{i}\\}}V_{j})$.
Let $V_{i}^{\prime}=V_{i}\oplus\mathrm{span}(\bm{v})$. Then

$\displaystyle\dim\left(V_{i}^{\prime}\cap\left(\bigcap_{j\in[\ell]\setminus\\{i\\}}V_{j}\right)\right)$
$\displaystyle=\dim
V_{i}^{\prime}+\dim\left(\bigcap_{j\in[\ell]\setminus\\{i\\}}V_{j}\right)-\dim\left(V_{i}^{\prime}+\left(\bigcap_{j\in[\ell]\setminus\\{i\\}}V_{j}\right)\right)$
$\displaystyle=\dim
V_{i}+1+\dim\left(\bigcap_{j\in[\ell]\setminus\\{i\\}}V_{j}\right)-\dim\left(V_{i}+\left(\bigcap_{j\in[\ell]\setminus\\{i\\}}V_{j}\right)\right)-1$
(since $\bm{v}\notin V_{i}+\bigcap_{j\in[\ell]\setminus\\{i\\}}V_{j}$)
$\displaystyle=\dim V_{[\ell]}=d.$

Thus, replacing $V_{i}$ with $V_{i}^{\prime}$ preserves the fact that $\dim
V_{[\ell]}=d$. We continue this process until a partition
$P_{1}\sqcup\cdots\sqcup P_{s}$ with $s\geq 2$ becomes tight. This proves the
claim.

Next, we verify that Item 2 holds for the padded subspaces. For ease of
notation, we still denote the padded subspaces by $V_{1},\dots,V_{\ell}$. Fix
a tight partition $P_{1}\sqcup\cdots\sqcup P_{s}$ of $[\ell]$ with $s\geq 2$,
which exists after padding.

Consider arbitrary $i\in[s]$. Recall that $V_{P_{i}}=\bigcap_{j\in
P_{i}}V_{j}$. Let $k_{i}=k-\dim V_{P_{i}}$, so that $\dim V_{P_{i}}=k-k_{i}$.
Let $W_{i}$ be a complement of $V_{P_{i}}$ in $\mathbb{F}_{q}^{n}$. For each
$j\in P_{i}$, let $T_{j}:=V_{j}\cap W_{i}$. For $j\in P_{i}$, as
$\mathbb{F}_{q}^{n}=V_{P_{i}}\oplus W_{i}$ and $V_{j}\supseteq V_{P_{i}}$, we
see that $V_{j}=V_{P_{i}}\oplus T_{j}$ and $\dim T_{j}=\dim V_{j}-\dim
V_{P_{i}}\leq k-(k-k_{i})=k_{i}$.

Consider an arbitrary partition $Q_{1}\sqcup\cdots\sqcup Q_{t}$ of $P_{i}$. As
$P_{1}\sqcup\cdots\sqcup P_{i-1}\sqcup Q_{1}\sqcup\cdots\sqcup Q_{t}\sqcup
P_{i+1}\sqcup\cdots\sqcup P_{s}$ is a partition of $[\ell]$, by Item 3, we
have

$\sum_{j=1}^{t}\dim V_{Q_{j}}+\sum_{j\in[s]\setminus\\{i\\}}\dim
V_{P_{j}}\leq(s+t-2)k+d.$ (25)

As the partition $P_{1}\sqcup\cdots\sqcup P_{s}$ of $[\ell]$ is tight, we also
have

$\sum_{j=1}^{s}\dim V_{P_{j}}=(s-1)k+d.$ (26)

Define $T_{\Omega}=\bigcap_{j\in\Omega}T_{j}$ for nonempty $\Omega\subseteq
P_{i}$. Then

$\displaystyle\sum_{j=1}^{t}\dim T_{Q_{j}}$
$\displaystyle=\left(\sum_{j=1}^{t}\dim V_{Q_{j}}\right)-t\cdot\dim V_{P_{i}}$
$\displaystyle=\left(\sum_{j=1}^{t}\dim
V_{Q_{j}}+\sum_{j\in[s]\setminus\\{i\\}}\dim
V_{P_{j}}\right)-\sum_{j=1}^{s}\dim V_{P_{j}}-(t-1)\dim V_{P_{i}}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:partition-
PQ},\eqref{eq:partition-P}}}{{\leq}}(s+t-2)k+d-((s-1)k+d)-(t-1)(k-k_{i})=(t-1)k_{i}.$

This shows that Item 3 holds for the subspaces $(T_{j})_{j\in P_{i}}$ indexed
by $P_{i}$ (instead of by $[\ell]$), where the parameter $d$ is set to zero.

Let $\ell_{i}=|P_{i}|$. Note that $\ell_{i}<\ell$ since $s\geq 2$. Identifying
$P_{i}$ with $[\ell_{i}]$ and applying the induction hypothesis, we see that
there exist integers $\delta_{j}\geq 0$ for all $j\in P_{i}$ such that

$\sum_{j\in P_{i}}\delta_{j}=k_{i}$ (27)

and for all nonempty $\Omega\subseteq P_{i}$,

$\dim T_{\Omega}\leq k_{i}-\sum_{j\in\Omega}\delta_{j}.$ (28)

As $i\in[s]$ is arbitrary, we can perform the above procedure for
$i=1,\dots,s$, which yields $\delta_{j}$ for all $j\in[\ell]$. We now verify
that $\delta_{1},\dots,\delta_{\ell}$ satisfy Item 2. First, observe that

$\sum_{i=1}^{\ell}\delta_{i}=\sum_{i=1}^{s}\sum_{j\in
P_{i}}\delta_{j}\stackrel{{\scriptstyle\eqref{eq:sum-of-
delta}}}{{=}}\sum_{i=1}^{s}k_{i}=\sum_{i=1}^{s}\bigg{(}k-\dim
V_{P_{i}}\bigg{)}\stackrel{{\scriptstyle\eqref{eq:partition-P}}}{{=}}k-d.$

So it remains to verify (21) for all nonempty $\Omega\subseteq[\ell]$. Fix
nonempty $\Omega\subseteq[\ell]$. Let
$I=\\{i\in[s]:P_{i}\cap\Omega\neq\emptyset\\}$. Consider $i\in I$. Recall that
for $j\in P_{i}$, the complement $T_{j}$ of $V_{P_{i}}$ in $V_{j}$ is chosen
to be $V_{j}\cap W_{i}$, where $W_{i}$ is a complement of $V_{P_{i}}$ in
$\mathbb{F}_{q}^{n}$. It follows that for any $J\subseteq P_{i}$,

$\bigcap_{j\in J}V_{j}=V_{P_{i}}\oplus\left(\bigcap_{j\in
J}T_{j}\right)=V_{P_{i}}\oplus T_{J}.$ (29)

Then, we have

$\displaystyle\dim\left(\bigcap_{i\in\Omega}V_{i}\right)=\dim\left(\bigcap_{i\in
I}\bigcap_{j\in
P_{i}\cap\Omega}V_{j}\right)\stackrel{{\scriptstyle\eqref{eq:intersection-of-
Vi}}}{{=}}\dim\left(\bigcap_{i\in I}\left(V_{P_{i}}\oplus
T_{P_{i}\cap\Omega}\right)\right)$ $\displaystyle\leq\dim\left(\bigcap_{i\in
I}V_{P_{i}}\right)+\sum_{i\in I}\dim\left(T_{P_{i}\cap\Omega}\right)$ (by
Lemma 2.2)
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:T-omega}}}{{\leq}}\dim\left(\bigcap_{i\in
I}V_{P_{i}}\right)+\sum_{i\in I}\left(k_{i}-\sum_{j\in
P_{i}\cap\Omega}\delta_{j}\right)$ $\displaystyle=\dim\left(\bigcap_{i\in
I}V_{P_{i}}\right)-\sum_{i\in I}\dim
V_{P_{i}}+k|I|-\sum_{j\in\Omega}\delta_{j}$ (as $\dim V_{P_{i}}=k-k_{i}$)
$\displaystyle=\dim\left(\bigcap_{i\in
I}V_{P_{i}}\right)+\sum_{i\in[s]\setminus I}\dim V_{P_{i}}-\sum_{i\in[s]}\dim
V_{P_{i}}+k|I|-\sum_{j\in\Omega}\delta_{j}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:partition-P}}}{{=}}\dim\left(\bigcap_{i\in
I}V_{P_{i}}\right)+\sum_{i\in[s]\setminus I}\dim
V_{P_{i}}-((s-1)k+d)+k|I|-\sum_{j\in\Omega}\delta_{j}$
$\displaystyle\leq(s-|I|)k+d-((s-1)k+d)+k|I|-\sum_{j\in\Omega}\delta_{j}$
$\displaystyle=k-\sum_{j\in\Omega}\delta_{j},$

where the second last step follows by applying (22) to the partition of
$[\ell]$ consisting of the set $\bigcup_{i\in I}P_{i}$ and the sets $P_{j}$
for $j\in[s]\setminus I$. So Item 2 holds, which concludes the proof. ∎

######  Remark 3.7.

The proof of the above lemma closely follows that of [BGM23, Lemma 2.8], which
gives a characterization of general zero patterns of order at most $\ell$.
However, some details differ due to our focus on vector spaces instead of
plain sets. For example, the proof of [BGM23, Lemma 2.8] uses the pigeonhole
principle to argue that one can continue padding a collection of sets until
some partition $P_{1}\sqcup P_{2}\sqcup\dots\sqcup P_{s}=[\ell]$ with $s\geq
2$ becomes tight. For us, such a simple argument does not work, as extending a
subspace $V_{i}$ to $V_{i}\oplus\mathrm{span}\\{\bm{v}\\}$ for a vector
$\bm{v}\not\in V_{i}$ would introduce elements that are not in
$V_{i}\cup\\{\bm{v}\\}$. Instead, our proof for the feasibility of padding is
based on the inequality (23), derived in turn from Item 3 of Lemma 3.6. We
find our argument to be more general and believe it may be of independent
interest.

##  4 The GM-MRD Theorem

In this section, we prove the GM-MRD theorem, which states that symbolic
Gabidulin code over $\mathbb{F}=\mathbb{F}_{q}(Z_{1},\dots,Z_{n})$ is
$\mathrm{GKP}(\ell)$ for all $\ell$. For the convenience of applications, we
have formulated the theorem as follows.

######  Theorem 4.1 (GM-MRD theorem).

Let $1\leq k\leq n$ be integers. Let
$\mathbb{F}=\mathbb{F}_{q}(Z_{1},\dots,Z_{n})$ and
$G=\left(Z_{j}^{q^{i-1}}\right)_{i\in[k],j\in[n]}\in\mathbb{F}^{k\times n}$.
For every generic kernel pattern $\mathcal{V}=(V_{1},\dots,V_{k})$ and
matrices $A_{1},\dots,A_{k}$, where $A_{i}\in\mathbb{F}_{q}^{n\times\dim
V_{i}}$ and $\langle A_{i}\rangle=V_{i}$, there exists a matrix
$M_{\mathcal{V}}\in\mathbb{F}^{k\times k}$ such that

  1. 1.

$M_{\mathcal{V}}$ is invertible,

  2. 2.

$\bm{m}_{i}GA_{i}=0$ for all $i\in[k]$, where $\bm{m}_{i}$ denotes the $i$-th
row of $M_{\mathcal{V}}$, and

  3. 3.

The entries of $M_{\mathcal{V}}$ are polynomials in $Z_{1},\dots,Z_{n}$ over
$\mathbb{F}_{q}$ of degree at most $q^{k-1}$.

In particular, the symbolic Gabidulin code
$\mathcal{G}_{n,k}(Z_{1},\dots,Z_{n})$ over $\mathbb{F}$ is
$\mathrm{GKP}(\ell)$ for all $\ell\geq 1$.

4.1 implies the following result, which states that a random Gabidulin code
over a large enough finite field is, with high probability,
$\mathrm{GKP}(\ell)$ for all $\ell$.

######  Theorem 4.2 (GM-MRD theorem, finite field version).

Let $1\leq k\leq n\leq m$ be integers. Let $\ell\geq 1$. Let
$(\alpha_{1},\dots,\alpha_{n})$ be uniformly distributed over the set of all
vectors in $\mathbb{F}_{q^{m}}^{n}$ whose coordinates are linearly independent
over $\mathbb{F}_{q}$. Then with probability at least
$1-3kq^{nk\cdot\min\\{\ell,k\\}+k-m}$, the Gabidulin code
$\mathcal{G}_{n,k}(\alpha_{1},\dots,\alpha_{n})$ over $\mathbb{F}_{q^{m}}$ is
$\mathrm{GKP}(\ell)$.

###### Proof.

Note that we may permute the subspaces $V_{i}$ in a generic kernel pattern
$\mathcal{V}=(V_{1},\dots,V_{k})$ without affecting whether
$\mathcal{G}_{n,k}(\alpha_{1},\dots,\alpha_{n})$ attains $\mathcal{V}$. Up to
permutation, each generic kernel pattern $\mathcal{V}$ of order at most $\ell$
can be represented by a list of subspaces $V_{1},\dots,V_{\ell^{\prime}}$ of
dimension at most $k-1$, where $\ell^{\prime}\leq\min\\{\ell,k\\}$, together
with their multiplicities $\delta_{1},\dots,\delta_{\ell^{\prime}}\in[k]$.
Each $V_{i}$ can be represented by a matrix
$A_{i}\in\mathbb{F}_{q}^{n\times(k-1)}$ satisfying $V_{i}=\langle
A_{i}\rangle$, for which there are at most $q^{n(k-1)}$ choices. So the number
of generic kernel patterns we need to consider is bounded by

$\mathcal{N}:=\sum_{\ell^{\prime}=1}^{\min\\{\ell,k\\}}(kq^{n(k-1)})^{\ell^{\prime}}\leq\sum_{\ell^{\prime}=1}^{\min\\{\ell,k\\}}q^{nk\ell^{\prime}}\leq
2q^{nk\cdot\min\\{\ell,k\\}}.$

First assume that $(\alpha_{1},\dots,\alpha_{n})$ is uniformly distributed
over $\mathbb{F}_{q^{m}}^{n}$ at random. Consider a fixed generic kernel
pattern $\mathcal{V}$. Let $M_{\mathcal{V}}$ be as in 4.1, whose entries are
polynomials in $Z_{1},\dots,Z_{n}$ over $\mathbb{F}_{q}$. For
$(\alpha_{1},\dots,\alpha_{n})\in\mathbb{F}_{q^{m}}^{n}$ and $i\in[k]$, we
have $\overline{\bm{m}}_{i}\overline{G}A_{i}=0$ by Item 2 of 4.1, where
$\overline{\bm{m}}_{i}$ is the $i$-th row of
$M_{\mathcal{V}}|_{Z_{1}=\alpha_{1},\dots,Z_{n}=\alpha_{n}}$ and
$\overline{G}$ is the generator matrix
$\left(\alpha_{j}^{q^{i-1}}\right)_{i\in[k],j\in[n]}$ of
$\mathcal{G}_{n,k}(\alpha_{1},\dots,\alpha_{n})$. By Item 3 of 4.1, the degree
of $\det\left(M_{\mathcal{V}}\right)$ is at most $kq^{k-1}$. By the
Schwartz–Zippel lemma,
$\det\left(M_{\mathcal{V}}|_{Z_{1}=\alpha_{1},\dots,Z_{n}=\alpha_{n}}\right)=0$
holds with probability at most $\delta:=kq^{k-1}/q^{m}=kq^{k-m-1}$. And when
$\det\left(M_{\mathcal{V}}|_{Z_{1}=\alpha_{1},\dots,Z_{n}=\alpha_{n}}\right)\neq
0$, we know that $\mathcal{G}_{n,k}(\alpha_{1},\dots,\alpha_{n})$ attains
$\mathcal{V}$.

By the union bound, the probability that
$\mathcal{G}_{n,k}(\alpha_{1},\dots,\alpha_{n})$ attains all generic kernel
patterns of order at most $\ell$, i.e., it is $\mathrm{GKP}(\ell)$, is at
least $1-\mathcal{N}\delta$, assuming that
$\alpha:=(\alpha_{1},\dots,\alpha_{n})$ is drawn from the uniform distribution
$U$ over $\mathbb{F}_{q^{m}}^{n}$. But $\alpha$ is actually drawn from the
uniform distribution $U_{S}$ over $S$, where $S$ denotes the set of all
vectors in $\mathbb{F}_{q^{m}}^{n}$ whose coordinates are linearly independent
over $\mathbb{F}_{q}$. However, note that $\Pr_{\alpha\sim U}[\alpha\not\in
S]\leq(1+q+\dots+q^{n-1})/q^{m}\leq q^{n-m}$. So the statistical distance
between $U$ and $U_{S}$ is bounded by $q^{n-m}$. So for $\alpha\sim U_{S}$,
the probability that $\mathcal{G}_{n,k}(\alpha_{1},\dots,\alpha_{n})$ is
$\mathrm{GKP}(\ell)$ is at least

$1-\mathcal{N}\delta-q^{n-m}\geq 1-2q^{nk\cdot\min\\{\ell,k\\}}\cdot
kq^{k-m-1}-q^{n-m}\geq 1-3kq^{nk\cdot\min\\{\ell,k\\}+k-m},$

which complete the proof. ∎

###  4.1 Proof of the GM-MRD Theorem

In the following, fix $n\in\mathbb{N}^{+}$ and let
$\mathbb{F}=\mathbb{F}_{q}(Z_{1},\dots,Z_{n})$. For a subset
$S\subseteq\mathbb{F}$, denote by $\mathbb{F}_{q}[S]$ the
$\mathbb{F}_{q}$-subalgebra of $\mathbb{F}$ generated by the elements in $S$.
In particular, $\mathbb{F}_{q}[S]\subseteq\mathbb{F}_{q}[Z_{1},\dots,Z_{n}]$
if $S\subseteq\mathbb{F}_{q}[Z_{1},\dots,Z_{n}]$.

######  Definition 4.3.

We say a tuple $(V_{i})_{i\in[m]}$ of $\mathbb{F}_{q}$-subspaces $V_{i}$ of
$\mathbb{F}_{q}[Z_{1},\dots,Z_{n}]$ is _$s$ -admissible_ if there exist
$\mathbb{F}_{q}$-subspaces $V,W$ of
$\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{n}\\}$ and a nonzero
$q$-linearized polynomial $f\in(\mathbb{F}_{q}[W])[X]$ in $X$ such that

  1. 1.

$\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{n}\\}=V\oplus W$,

  2. 2.

$\dim V\leq s$, and

  3. 3.

$V_{1},\dots,V_{m}\subseteq f(V)$.

Note that in the above definition, as $f$ is $q$-linearized, the map $u\mapsto
f(u)$ defines an isomorphism between the $\mathbb{F}_{q}$-linear spaces $V$
and $f(V)$.

We can apply an invertible linear transformation to
$\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{n}\\}$ over $\mathbb{F}_{q}$,
mapping $V$ to $\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{\dim V}\\}$
and $W$ to $\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{\dim V+1},\dots,Z_{n}\\}$.
Thus, 4.3 states that, after applying an invertible linear transformation over
$\mathbb{F}_{q}$, the spaces $V_{1},\dots,V_{m}$ are contained in
$f(\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{d}\\})$ for some $d\leq s$,
and $f$ is a $q$-linearized polynomial whose coefficients are in
$\mathbb{F}_{q}[Z_{d+1},\dots,Z_{n}]$. Importantly, $f$ is evaluated only on
the $\mathbb{F}_{q}$-linear span of $Z_{1},\dots,Z_{d}$ while its coefficients
do not depend on $Z_{1},\dots,Z_{d}$. This fact is crucially used in the proof
of 4.7 (specifically in Case 3 of the proof).

The following lemma follows straightforwardly from the definition.

######  Lemma 4.4.

Let $(V_{i})_{i\in[m]}$ be $s$-admissible and let $V_{i}^{\prime}$ be an
$\mathbb{F}_{q}$-subspace of $V_{i}$ for $i\in[m]$. Then
$(V_{i}^{\prime})_{i\in[m]}$ is also $s$-admissible.

For $k\geq m\geq 1$ and $s\geq 0$, define

$V_{k,m,s}:=\left\\{((V_{i},r_{i}))_{i\in[m]}:(V_{i})_{i\in[m]}\text{ is
$s$-admissible},r_{i}\in\mathbb{N}^{+},\dim(V_{i})+r_{i}\leq
k,\sum_{i=1}^{m}r_{i}=k\right\\}.$

For each $\mathcal{S}=((V_{i},r_{i}))_{i\in[m]}\in V_{k,m,s}$, we associate
with it a matrix $M_{\mathcal{S}}\in\mathbb{F}^{k\times k}$, defined as
follows.

######  Definition 4.5 (Matrix $M_{\mathcal{S}}$).

Let $\mathcal{S}=((V_{i},r_{i}))_{i\in[m]}\in V_{k,m,s}$. For $i\in[m]$, let

$f_{i}(X)=\prod_{\alpha\in
V_{i}}(X-\alpha)^{q^{k-\dim(V_{i})-r_{i}}}=\sum_{j=0}^{k-r_{i}}a_{i,j}X^{q^{j}}$
(30)

which is a $q$-linearized polynomial in $X$ with coefficients in
$\mathbb{F}_{q}[Z_{1},\dots,Z_{n}]\subseteq\mathbb{F}$ by Lemma 2.4. Define
the matrix

$M_{\mathcal{S}}=\begin{pmatrix}M_{1}\\\ M_{2}\\\ \vdots\\\
M_{m}\end{pmatrix}\in\mathbb{F}^{k\times k}$ (31)

where

$M_{i}=\begin{pmatrix}a_{i,0}&a_{i,1}&\cdots&a_{i,k-r_{i}-1}&a_{i,k-r_{i}}&0&\cdots&0\\\
0&a_{i,0}^{q}&\cdots&a_{i,k-r_{i}-2}^{q}&a_{i,k-r_{i}-1}^{q}&a_{i,k-r_{i}}^{q}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&0\\\
0&0&\cdots&a_{i,0}^{q^{r_{i}-1}}&a_{i,1}^{q^{r_{i}-1}}&a_{i,2}^{q^{r_{i}-1}}&\cdots&a_{i,k-r_{i}}^{q^{r_{i}-1}}\end{pmatrix}\in\mathbb{F}^{r_{i}\times
k}.$ (32)

In other words, for $(j,j^{\prime})\in[r_{i}]\times[k]$, the
$(j,j^{\prime})$-th entry of $M_{i}$ is the coefficient of
$X^{q^{j^{\prime}-1}}$ in $f_{i}(X)^{q^{j-1}}$.

We will derive 4.1 from the following theorem.

######  Theorem 4.6.

Let $\mathcal{S}=((V_{i},1))_{i\in[k]}\in V_{k,k,s}$ such that for all
nonempty $\Omega\subseteq[k]$,

$\dim\left(\bigcap_{i\in\Omega}V_{i}\right)\leq k-|\Omega|.$

Then $\det(M_{\mathcal{S}})\neq 0$.

4.6 is, in turn, derived from the following more general statement.

######  Theorem 4.7.

Let $\mathcal{S}=((V_{i},r_{i}))_{i\in[m]}\in V_{k,m,s}$. Then
$\det(M_{\mathcal{S}})\neq 0$ iff for all nonempty $\Omega\subseteq[m]$,

$\dim\left(\bigcap_{i\in\Omega}V_{i}\right)+\sum_{i\in\Omega}r_{i}\leq\max_{i\in\Omega}\\{\dim(V_{i})+r_{i}\\}.$
(33)

Note that 4.6 follows from 4.7 by choosing $m=k$ and $r_{i}=1$ for $i\in[m]$.
We now derive 4.1 from 4.6.

###### Proof of 4.1 given 4.6.

Consider generic kernel pattern $\mathcal{V}=(V_{1},\dots,V_{k})$ and matrices
$A_{1},\dots,A_{k}$, where $A_{i}\in\mathbb{F}_{q}^{n\times\dim V_{i}}$ and
$\langle A_{i}\rangle=V_{i}$. Let $\\{e_{1},\dots,e_{n}\\}$ be the standard
basis of $\mathbb{F}_{q}^{n}$. Let
$\sigma:\mathbb{F}_{q}^{n}\to\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{n}\\}$
be the $\mathbb{F}_{q}$-linear isomorphism sending $e_{j}$ to $Z_{j}$ for
$j\in[n]$. Define $V_{i}^{\prime}=\sigma(V_{i})$ for $i\in[k]$. Let
$\mathcal{S}=((V_{i}^{\prime},1))_{i\in[k]}$. As
$\mathcal{V}=(V_{1},\dots,V_{k})$ is a generic kernel pattern and $\sigma$ is
an $\mathbb{F}_{q}$-linear isomorphism, we see that $\mathcal{S}\in V_{k,k,n}$
and that $\dim\left(\bigcap_{i\in\Omega}V_{i}^{\prime}\right)\leq k-|\Omega|$
for nonempty $\Omega\subseteq[k]$. So $\det(M_{\mathcal{S}})\neq 0$ by 4.6,
where $M_{\mathcal{S}}\in\mathbb{F}^{k\times k}$ is as defined in 4.5. By
definition, for $i\in[k]$, each entry of the $i$-th row of $M_{\mathcal{S}}$
is a coefficient of $f_{i}$, where $f_{i}(X)=\prod_{\alpha\in
V_{i}^{\prime}}(X-\alpha)^{q^{k-\dim(V_{i}^{\prime})-1}}$. As each $\alpha\in
V_{i}^{\prime}$ is a linear form in $Z_{1},\dots,Z_{n}$ over $\mathbb{F}_{q}$,
we conclude that the entries of $M_{\mathcal{S}}$ are polynomials in
$Z_{1},\dots,Z_{n}$ over $\mathbb{F}_{q}$ of degree at most $q^{k-1}$.

Choose $M_{\mathcal{V}}$ to be $M_{\mathcal{S}}$. Then Item 1 and Item 3 of
4.1 hold by the above discussions. It remains to verify Item 2. Let $i\in[k]$.
Suppose the $i$-th row of $M_{\mathcal{V}}=M_{\mathcal{S}}$ is
$\bm{m}_{i}=(c_{1},\dots,c_{k})$, or equivalently,
$f_{i}(X)=\sum_{j=1}^{k}c_{j}X^{q^{j-1}}$. Consider arbitrary
$\bm{v}=(v_{1},\dots,v_{n})\in V_{i}\subseteq\mathbb{F}_{q}^{n}$. As
$G=\left(Z_{j}^{q^{i}-1}\right)_{i\in[k],j\in[n]}$, we have

$\bm{m}_{i}G\bm{v}=(f_{i}(Z_{1}),\dots,f_{i}(Z_{n}))\bm{v}=f_{i}\left(\sum_{j=1}^{n}v_{i}Z_{i}\right)=0,$
(34)

where the second equality holds since $f_{i}$ is $q$-linearized, and the last
equality holds since $f_{i}$ vanishes on $V_{i}^{\prime}$ and
$\sum_{j=1}^{n}v_{i}Z_{i}=\sigma(\bm{v})\in V_{i}^{\prime}$. Choosing $\bm{v}$
to be the columns of $A_{i}$ in (34) shows that $\bm{m}_{i}GA_{i}=0$. So Item
2 holds. ∎

###  4.2 Proof of 4.7

It remains to prove 4.7. To this end, we introduce the following lemma, which
characterizes the nonsingularity of a matrix $M_{\mathcal{S}}$ in terms of the
compositions of $q$-linearized polynomials.

######  Lemma 4.8.

Let $\mathcal{S}=((V_{i},r_{i}))_{i\in[m]}\in V_{k,m,s}$. For $i\in[m]$, let
$f_{i}$ be given as in (30). Then, $\det(M_{\mathcal{S}})=0$ if and only if
there exist $q$-linearized polynomials $g_{1},\ldots,g_{m}\in\mathbb{F}[X]$,
not all zero, such that the $q$-degree of each $g_{i}$ is at most $r_{i}-1$
and $\sum_{i=1}^{m}g_{i}\circ f_{i}=0$.

###### Proof.

Suppose $\det(M_{\mathcal{S}})=0$. Then there exists nonzero
$\bm{y}\in\mathbb{F}^{k}$ such that $\bm{y}\cdot M_{\mathcal{S}}=\mathbf{0}$.
Write $\bm{y}=(\bm{y}_{1},\ldots,\bm{y}_{m})\in\mathbb{F}^{k}$ with
$\bm{y}_{i}=(y_{i,1},\ldots,y_{i,r_{i}})\in\mathbb{F}^{r_{i}}$. For $i\in[m]$,
let $f_{i}(X)\in\mathbb{F}[X]$ and $M_{i}\in\mathbb{F}^{r_{i}\times k}$ be as
in (30) and (32) respectively, and let
$g_{i}(X)=\sum_{j=1}^{r_{i}}y_{i,j}X^{q^{j-1}}\in\mathbb{F}[X]$. By
definition, $\bm{y}_{i}\cdot M_{i}$ is precisely the vector of the first $k$
coefficients of the $q$-linearized polynomial

$\sum_{j=1}^{r_{i}}y_{i,j}\cdot f_{i}(X)^{q^{j-1}}=(g_{i}\circ f_{i})(X).$

So $\mathbf{0}=\bm{y}\cdot M_{\mathcal{S}}=\sum_{i=1}^{m}\bm{y}_{i}\cdot
M_{i}$ is the vector of the first $k$ coefficients of the $q$-linearized
polynomial $\sum_{i=1}^{m}g_{i}\circ f_{i}$. By definition, for $i\in[m]$, we
have $\deg_{q}(f_{i})=k-r_{i}$ and $\deg_{q}(g_{i})\leq r_{i}-1$. It follows
that the $q$-degree of $\sum_{i=1}^{m}g_{i}\circ f_{i}$ is at most $k-1$. So
$\sum_{i=1}^{m}g_{i}\circ f_{i}=0$.

Conversely, suppose there exist $q$-linearized polynomials
$g_{1},\ldots,g_{m}\in\mathbb{F}[X]$, not all zero, such that the $q$-degree
of each $g_{i}$ is at most $r_{i}-1$ and $\sum_{i=1}^{m}g_{i}\circ f_{i}=0$.
Find the nonzero vector
$\bm{y}=(\bm{y}_{1},\ldots,\bm{y}_{m})\in\mathbb{F}^{k}$ via
$\bm{y}_{i}=(y_{i,1},\ldots,y_{i,r_{i}})\in\mathbb{F}^{r_{i}}$ and
$g_{i}(X)=\sum_{j=1}^{r_{i}}y_{i,j}X^{q^{j-1}}$. Reversing the above proof
shows $\bm{y}\cdot M_{\mathcal{S}}=\mathbf{0}$. So $\det(M_{\mathcal{S}})=0$.
∎

Now we are ready to prove 4.7. Our proof is based on an induction on the
parameter $(k,m,s)$ in the lexicographical order, following the approach in
[YH19b]. The main difference is that the product of polynomials is replaced by
the composition of $q$-linearized polynomials, which is not commutative.
Consequently, we need to adapt the proof in [YH19b] to circumvent this
obstacle.

###### Proof of 4.7.

We first prove the “only if” direction. Assume that for some nonempty
$\Omega\subseteq[m]$, the inequality (33) does not hold. We will show that
$\det(M_{\mathcal{S}})=0$. Let $V_{0}=\bigcap_{i\in\Omega}V_{i}$,
$r_{0}=\sum_{i\in\Omega}r_{i}$ and
$k^{\prime}=\max_{i\in\Omega}\\{\dim(V_{i})+r_{i}\\}$. Then
$\dim(V_{0})+r_{0}>k^{\prime}$ as (33) does not hold.

Let $M^{*}$ be the $r_{0}\times k$ submatrix of $M_{\mathcal{S}}$ obtained by
removing all blocks $M_{i}$ for $i\notin\Omega$. By the definitions (30) and
(32), the first $k-k^{\prime}$ columns of $M^{*}$ are zero. We remove these
$k-k^{\prime}$ columns and denote by $M^{\prime}$ the resulting $r_{0}\times
k^{\prime}$ matrix. The matrix $M^{\prime}$ consists of the blocks
$M^{\prime}_{i}$ for $i\in\Omega$, placed vertically, each given by

$M_{i}^{\prime}=\begin{pmatrix}b_{i,0}&b_{i,1}&\cdots&b_{i,k^{\prime}-r_{i}-1}&b_{i,k^{\prime}-r_{i}}&0&\cdots&0\\\
0&b_{i,0}^{q}&\cdots&b_{i,k^{\prime}-r_{i}-2}^{q}&b_{i,k^{\prime}-r_{i}-1}^{q}&b_{i,k^{\prime}-r_{i}}^{q}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&0\\\
0&0&\cdots&b_{i,0}^{q^{r_{i}-1}}&b_{i,1}^{q^{r_{i}-1}}&b_{i,2}^{q^{r_{i}-1}}&\cdots&b_{i,k^{\prime}-r_{i}}^{q^{r_{i}-1}}\end{pmatrix}\in\mathbb{F}^{r_{i}\times
k^{\prime}}$ (35)

where each $b_{i,j}$ is determined via $b_{i,j}=a_{i,j+k-k^{\prime}}$ and
$a_{i,j+k-k^{\prime}}$ denotes the coefficient of $X^{q^{j+k-k^{\prime}}}$ in
$f_{i}(X)=\prod_{\alpha\in V_{i}}(X-\alpha)^{q^{k-\dim(V_{i})-r_{i}}}$.
Therefore,

$\prod_{\alpha\in
V_{i}}(X-\alpha)^{q^{k-\dim(V_{i})-r_{i}}}=\sum_{j=0}^{k^{\prime}-r_{i}}b_{i,j}\left(X^{q^{k-k^{\prime}}}\right)^{q^{j}}.$
(36)

Pick a basis $\alpha_{1},\dots,\alpha_{h}$ of $V_{0}$ over $\mathbb{F}_{q}$,
where $h=\dim V_{0}$. Let $\alpha_{i}^{\prime}=\alpha_{i}^{q^{k-k^{\prime}}}$
for $i\in[h]$. Then $\alpha^{\prime}_{1},\dots,\alpha^{\prime}_{h}$ are
linearly independent over $\mathbb{F}_{q}$. Let $H=(\alpha_{\ell}^{\prime
q^{j-1}})_{j\in[k^{\prime}],\ell\in[h]}\in\mathbb{F}^{k^{\prime}\times h}$.
Then $H$ has full rank by Lemma 2.3. For each $i\in\Omega$, as $V_{0}\subseteq
V_{i}$, the polynomial in (36) vanishes at $\alpha_{1},\dots,\alpha_{h}$,
i.e., $\sum_{j=0}^{k^{\prime}-r_{i}}b_{i,j}\alpha_{\ell}^{\prime q^{j}}=0$ for
$\ell\in[h]$. Equivalently, $M_{i}^{\prime}H=0$ for $i\in\Omega$. So
$M^{\prime}H=0$. Therefore,

$\mathrm{rank}(M^{*})=\mathrm{rank}(M^{\prime})\leq
k^{\prime}-\min\\{k^{\prime},h\\}=\max\\{0,k^{\prime}-\dim V_{0}\\}<r_{0}.$

So $M^{*}$ does not have full row rank. It follows that $M_{\mathcal{S}}$ does
not have full row rank either. So $\det(M_{\mathcal{S}})=0$.

Next, we prove the “if” direction via an induction on $(k,m,s)$ with respect
to the lexicographical order:

If $m=1$, then $r_{1}=k$ and $V_{1}=\\{0\\}$. In this case, the matrix
$M_{\mathcal{S}}$ is the $k\times k$ identity matrix by the definitions (30),
(31), and (32). In particular, $\det(M_{\mathcal{S}})\neq 0$.

If $s=0$, then all $V_{i}$ are zero since $(V_{i})_{i\in[m]}$ is
$s$-admissible. In this case, (33) implies that $m=1$ and $r_{1}=k$. So
$M_{\mathcal{S}}$ is again the $k\times k$ identity matrix and
$\det(M_{\mathcal{S}})\neq 0$.

Now suppose $k\geq m\geq 2$ and $s\geq 1$. Assume the “if” direction holds for
all $(k^{\prime},m^{\prime},s^{\prime})$ that are smaller than $(k,m,s)$ in
lexicographical order. Let $\mathcal{S}=((V_{i},r_{i}))_{i\in[m]}\in
V_{k,m,s}$ such that (33) holds for all nonempty $\Omega\subseteq[m]$. We will
show that $\det(M_{\mathcal{S}})\neq 0$ by dividing the proof into the
following three cases:

##### Case 1:

There exists $\Omega_{1}\subseteq[m]$ such that $2\leq|\Omega_{1}|\leq m-1$
and

$\dim\left(\bigcap_{i\in\Omega_{1}}V_{i}\right)+\sum_{i\in\Omega_{1}}r_{i}=\max_{i\in\Omega_{1}}\\{\dim(V_{i})+r_{i}\\}.$
(37)

In this case, let $\Omega_{2}=\\{0\\}\cup([m]\setminus\Omega_{1})$. Then
$2\leq|\Omega_{1}|,|\Omega_{2}|\leq m-1$. Define
$V_{0}=\bigcap_{i\in\Omega_{1}}V_{i}$ and $r_{0}=\sum_{i\in\Omega_{1}}r_{i}$.
Then (37) becomes

$\dim(V_{0})+r_{0}=\max_{i\in\Omega_{1}}\\{\dim(V_{i})+r_{i}\\}.$ (38)

As $(V_{i})_{i\in[m]}$ is $s$-admissible, there exist
$\mathbb{F}_{q}$-subspaces
$V,W\subseteq\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{n}\\}$ and a
nonzero $q$-linearized polynomial $f\in(\mathbb{F}_{q}[W])[X]$ in $X$ such
that $\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{n}\\}=V\oplus W$, $\dim
V\leq s$, and $V_{1},\dots,V_{m}\subseteq f(V)$. Fix a complement
$\overline{V}_{0}$ of $V_{0}$ in $f(V)$, so that
$f(V)=V_{0}\oplus\overline{V}_{0}$. For $i\in\Omega_{1}$, let
$V_{i}^{\prime}=V_{i}\cap\overline{V}_{0}$, which is a complement of $V_{0}$
in $V_{i}$. Let $\mathcal{S}_{1}=((V_{i}^{\prime},r_{i}))_{i\in\Omega_{1}}$
and $\mathcal{S}_{2}=((V_{i},r_{i}))_{i\in\Omega_{2}}$. As
$\dim(V^{\prime}_{i})+r_{i}=\dim(V_{i})-\dim(V_{0})+r_{i}\stackrel{{\scriptstyle\eqref{eq:gkp-
tight-2}}}{{\leq}}r_{0}$ for $i\in\Omega_{1}$ and
$\sum_{i\in\Omega_{1}}r_{i}=r_{0}$, we have $\mathcal{S}_{1}\in
V_{r_{0},|\Omega_{1}|,s}$. As

$k=\sum_{i=1}^{m}r_{i}=\sum_{i\in\Omega_{1}}r_{i}+\sum_{i\in[m]\setminus\Omega_{1}}r_{i}=r_{0}+\sum_{i\in[m]\setminus\Omega_{1}}r_{i}=\sum_{i\in\Omega_{2}}r_{i},$

$\dim(V_{i})+r_{i}\leq k$ for $i\in[m]\setminus\Omega_{1}$, and
$\dim(V_{0})+r_{0}\stackrel{{\scriptstyle\eqref{eq:gkp-
tight-2}}}{{=}}\max_{i\in\Omega_{1}}\\{\dim(V_{i})+r_{i}\\}\leq k$, we also
have $\mathcal{S}_{2}\in V_{k,|\Omega_{2}|,s}$.

Next, we check that
$\mathcal{S}_{1}=((V_{i}^{\prime},r_{i}))_{i\in\Omega_{1}}$ and
$\mathcal{S}_{2}=((V_{i},r_{i}))_{i\in\Omega_{2}}$ both satisfy the condition
(33). Indeed, for any nonempty $\Omega\subseteq\Omega_{1}$,

$\displaystyle\dim\left(\bigcap_{i\in\Omega}V^{\prime}_{i}\right)+\sum_{i\in\Omega}r_{i}$
$\displaystyle=\dim\left(\bigcap_{i\in\Omega}V_{i}\right)-\dim(V_{0})+\sum_{i\in\Omega}r_{i}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eqn:key-
new}}}{{\leq}}\max_{i\in\Omega}\\{\dim(V_{i})-\dim(V_{0})+r_{i}\\}=\max_{i\in\Omega}\\{\dim(V^{\prime}_{i})+r_{i}\\}.$

And for any nonempty $\Omega\subseteq\Omega_{2}$, if $0\notin\Omega$, then
(33) holds for $\mathcal{S}_{2}$ and $\Omega$ since $\Omega\subseteq[m]$.
Otherwise, let
$\Omega^{\prime}=\Omega\setminus\\{0\\}\subseteq[m]\setminus\Omega_{1}$, and
we have

$\displaystyle\dim\left(\bigcap_{i\in\Omega}V_{i}\right)+\sum_{i\in\Omega}r_{i}$
$\displaystyle=\dim\left(\bigcap_{i\in\Omega^{\prime}\cup\Omega_{1}}V_{i}\right)+\sum_{i\in\Omega^{\prime}\cup\Omega_{1}}r_{i}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eqn:key-
new}}}{{\leq}}\max_{i\in\Omega^{\prime}\cup\Omega_{1}}\\{\dim(V_{i})+r_{i}\\}\stackrel{{\scriptstyle\eqref{eq:gkp-
tight-2}}}{{=}}\max_{i\in\Omega}\\{\dim(V_{i})+r_{i}\\},$

where the first equality holds since $V_{0}=\bigcap_{i\in\Omega_{1}}V_{i}$,
$r_{0}=\sum_{i\in\Omega_{1}}r_{i}$, and the union
$\Omega^{\prime}\cup\Omega_{1}$ is a disjoint union.

For $i\in\\{0\\}\cup[m]$, let $f_{i}$ be the $q$-linearized polynomial defined
in (30). That is,

$f_{i}(X)=\prod_{\alpha\in
V_{i}}(X-\alpha)^{q^{k-\dim(V_{i})-r_{i}}}\in(\mathbb{F}_{q}[V_{i}])[X].$

We now build from $\mathcal{S}_{1}=((V_{i}^{\prime},r_{i}))_{i\in\Omega_{1}}$
a new tuple $\mathcal{S}_{1}^{*}$, defined as

$\mathcal{S}_{1}^{*}=((f_{0}(V_{i}^{\prime}),r_{i}))_{i\in\Omega_{1}}$

Denote by $f|_{V}$ the isomorphism $a\mapsto f(a)$ from $V$ to $f(V)$. Let
$V^{\prime}=f|_{V}^{-1}(\overline{V}_{0})\subseteq V$ and $W^{\prime}=W\oplus
f|_{V}^{-1}(V_{0})$. Then
$\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{n}\\}=V^{\prime}\oplus
W^{\prime}$, $f(V^{\prime})=\overline{V}_{0}$, and $f(W^{\prime})=f(W)\oplus
V_{0}$. Here $f$ is a nonzero $q$-linearized polynomial with coefficients in
$\mathbb{F}_{q}[W]$. And $f_{0}$ is a nonzero $q$-linearized polynomial with
coefficients in $\mathbb{F}_{q}[V_{0}]$. As $V_{0}\subseteq f(W^{\prime})$ and
the coefficients of $f$ are in
$\mathbb{F}_{q}[W]\subseteq\mathbb{F}_{q}[W^{\prime}]$, we see that
$\mathbb{F}_{q}[V_{0}]\subseteq\mathbb{F}_{q}[W^{\prime}]$. It follows that
$f_{0}\circ f$ is a nonzero $q$-linearized polynomial with coefficients in
$\mathbb{F}_{q}[W^{\prime}]$. Note that for $i\in\Omega_{1}$, we have

$f_{0}(V_{i}^{\prime})\subseteq f_{0}(\overline{V}_{0})=(f_{0}\circ
f)(V^{\prime}),$

where $\dim V^{\prime}\leq\dim V\leq s$. By definition, the tuple
$(f_{0}(V_{i}^{\prime}))_{i\in\Omega_{1}}$ is $s$-admissible.

Also, note that $f_{0}$ defines an isomorphism from $\overline{V}_{0}$ to
$f(\overline{V}_{0})$, mapping each $V_{i}^{\prime}$ to
$f_{0}(V_{i}^{\prime})$. As
$\mathcal{S}_{1}=((V_{i}^{\prime},r_{i}))_{i\in\Omega_{1}}$ is in
$V_{r_{0},|\Omega_{1}|,s}$ and satisfies (33), the same holds for
$\mathcal{S}_{1}^{*}=((f_{0}(V_{i}^{\prime}),r_{i}))_{i\in\Omega_{1}}$.
Applying the induction hypothesis to $\mathcal{S}_{1}^{*}$ and
$\mathcal{S}_{2}$ shows that $\det(M_{\mathcal{S}_{1}^{*}})$ and
$\det(M_{\mathcal{S}_{2}})$ are nonzero.

For $i\in\Omega_{1}$, let
$t_{i}=r_{0}-\dim(V_{i}^{\prime})-r_{i}=(\dim(V_{0})+r_{0})-(\dim(V_{i})+r_{i})\stackrel{{\scriptstyle\eqref{eq:gkp-
tight-2}}}{{\geq}}0$, and define the $q$-linearized polynomial

$f_{i}^{*}(X)=\prod_{\alpha\in
f_{0}(V_{i}^{\prime})}(X-\alpha)^{q^{t_{i}}}=\prod_{\alpha\in
f_{0}(V_{i}^{\prime})}(X-\alpha)^{q^{r_{0}-\dim(V_{i}^{\prime})-r_{i}}}$

whose $q$-degree is

$\deg_{q}(f_{i}^{*})=\dim(V_{i}^{\prime})+t_{i}=\dim(V_{i})-\dim(V_{0})+t_{i}=r_{0}-r_{i}.$
(39)

For $i\in\Omega_{1}$,

$\displaystyle f_{i}(X)$ $\displaystyle=\prod_{\alpha\in
V_{i}}(X-\alpha)^{q^{k-\dim(V_{i})-r_{i}}}=\prod_{\beta\in
V_{i}^{\prime}}\prod_{\alpha\in
V_{0}}(X-\alpha-\beta)^{q^{k-\dim(V_{0})-r_{0}+t_{i}}}$ (40)
$\displaystyle=\prod_{\beta\in
V_{i}^{\prime}}f_{0}(X-\beta)^{q^{t_{i}}}=\prod_{\beta\in
V_{i}^{\prime}}(f_{0}(X)-f_{0}(\beta))^{q^{t_{i}}}$
$\displaystyle=\prod_{\alpha\in
f_{0}(V_{i}^{\prime})}(f_{0}(X)-\alpha)^{q^{t_{i}}}=(f_{i}^{*}\circ
f_{0})(X).$

We now prove $\det(M_{\mathcal{S}})\neq 0$ by applying Lemma 4.8. Consider
arbitrary $q$-linearized polynomials $g_{1},\dots,g_{m}\in\mathbb{F}[X]$ such
that the $q$-degree of $q_{i}(X)$ is at most $r_{i}-1$ for $i\in[m]$ and
$\sum_{i=1}^{m}g_{i}\circ f_{i}=0$. Define
$g_{0}=\sum_{i\in\Omega_{1}}g_{i}\circ f_{i}^{*}$. Note that

$\deg_{q}(g_{0})\leq\max_{i\in\Omega_{1}}\left\\{\deg_{q}(f_{i}^{*})+\deg_{q}(g_{i})\right\\}\stackrel{{\scriptstyle\eqref{eq:q-degree-
fi}}}{{\leq}}\max_{i\in\Omega_{1}}\\{(r_{0}-r_{i})+(r_{i}-1)\\}=r_{0}-1.$

Also, it holds that

$0=\sum_{i=1}^{m}g_{i}\circ
f_{i}\stackrel{{\scriptstyle\eqref{eq:compose}}}{{=}}\sum_{i\in\Omega_{1}}g_{i}\circ
f_{i}^{*}\circ f_{0}+\sum_{i\in[m]\setminus\Omega_{1}}g_{i}\circ
f_{i}=\sum_{i\in\Omega_{2}}g_{i}\circ f_{i},$ (41)

where the last equality holds since $\sum_{i\in\Omega_{1}}g_{i}\circ
f_{i}^{*}=g_{0}$. By Lemma 4.8, (41), and the fact that
$\det(M_{\mathcal{S}_{2}})\neq 0$, we have $g_{i}=0$ for all $i\in\Omega_{2}$.
In particular, $g_{0}=0$. Therefore,

$\sum_{i\in\Omega_{1}}g_{i}\circ f_{i}^{*}=g_{0}=0.$ (42)

By Lemma 4.8, (42), and the fact that $\det(M_{\mathcal{S}_{1}^{*}})\neq 0$,
we have $g_{i}=0$ for all $i\in\Omega_{1}$. So $g_{i}=0$ for all $i\in[m]$. By
Lemma 4.8, we conclude that $\det(M_{\mathcal{S}})\neq 0$.

##### Case 2:

There exists an unique integer $i\in[m]$ such that $\dim(V_{i})+r_{i}=k$.

Without loss of generality, suppose $i=m$. Let $M_{1},\dots,M_{m}$ be as in
(32). Since

$\dim(V_{m})+r_{m}=k>\dim(V_{i})+r_{i}\quad\text{ for }i=1,\dots,m-1,$ (43)

by the definitions (30), (31), and (32), the entries in first column of
$M_{\mathcal{S}}$ are all zero except that the $(1,1)$-th entry of the block
$M_{m}$ is the coefficient of $X$ in $f_{m}=\prod_{\alpha\in
V_{m}}(X-\alpha)$, which we denote by $c\in\mathbb{F}$. Note that
$c=\prod_{\alpha\in V_{m}/\\{0\\}}(-\alpha)\neq 0$. Let
$M^{\prime}\in\mathbb{F}^{(k-1)\times(k-1)}$ be the submatrix of
$M_{\mathcal{S}}$ obtained by removing the first column of $M_{\mathcal{S}}$
and the first row of the block $M_{m}$. By the above observation about
$M_{\mathcal{S}}$,

$\det(M_{\mathcal{S}})=\pm c\cdot\det(M^{\prime}).$ (44)

Assume $r_{m}>1$. Let
$\mathcal{S}^{\prime}=((V_{i},r_{i}^{\prime}))_{i\in[m]}$, where
$r_{i}^{\prime}=r_{i}$ for $i\in[m-1]$ and $r_{m}^{\prime}=r_{m}-1$. By (43)
and the fact $\sum_{i=1}^{m}r^{\prime}_{i}=k-1$, we have
$\mathcal{S}^{\prime}\in V_{k-1,m,s}$. Next, we verify that
$\mathcal{S}^{\prime}$ satisfies (33) for nonempty $\Omega\subseteq[m]$. If
$m\not\in\Omega$, this holds since $\mathcal{S}$ satisfies (33) and
$r_{i}^{\prime}=r_{i}$ for $i\in[m-1]$. On the other hand, if $m\in\Omega$,
then

$\dim\left(\bigcap_{i\in\Omega}V_{i}\right)+\sum_{i\in\Omega}r^{\prime}_{i}=\dim\left(\bigcap_{i\in\Omega}V_{i}\right)+\left(\sum_{i\in\Omega}r_{i}\right)-1\stackrel{{\scriptstyle\eqref{eqn:key-
new}}}{{\leq}}\max_{i\in\Omega}\\{\dim(V_{i})+r_{i}\\}-1\stackrel{{\scriptstyle\eqref{eq:not-
tight}}}{{=}}\max_{i\in\Omega}\\{\dim(V_{i})+r^{\prime}_{i}\\}.$

So again $\mathcal{S}^{\prime}$ satisfies (33). By the induction hypothesis,
$\det(M_{\mathcal{S}^{\prime}})\neq 0$.

The matrix $M_{\mathcal{S}^{\prime}}$ consists of the blocks $M^{\prime}_{i}$
for $i\in[m]$, placed vertically, each given by

$M_{i}^{\prime}=\begin{pmatrix}b_{i,0}&b_{i,1}&\cdots&b_{i,(k-1)-r_{i}^{\prime}-1}&b_{i,(k-1)-r_{i}^{\prime}}&0&\cdots&0\\\
0&b_{i,0}^{q}&\cdots&b_{i,(k-1)-r_{i}^{\prime}-2}^{q}&b_{i,(k-1)-r_{i}^{\prime}-1}^{q}&b_{i,(k-1)-r_{i}^{\prime}}^{q}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\ddots&0\\\
0&0&\cdots&b_{i,0}^{q^{r_{i}^{\prime}-1}}&b_{i,1}^{q^{r_{i}^{\prime}-1}}&b_{i,2}^{q^{r_{i}^{\prime}-1}}&\cdots&b_{i,(k-1)-r_{i}^{\prime}}^{q^{r_{i}^{\prime}-1}}\end{pmatrix}\in\mathbb{F}^{r_{i}^{\prime}\times(k-1)}$

where each $b_{i,j}$ is determined via

$\prod_{\alpha\in
V_{i}}(X-\alpha)^{q^{(k-1)-\dim(V_{i})-r_{i}^{\prime}}}=\sum_{j=0}^{(k-1)-r_{i}^{\prime}}b_{i,j}X^{q^{j}},$
(45)

or equivalently

$\prod_{\alpha\in
V_{i}}(X-\alpha)^{q^{k-\dim(V_{i})-r_{i}^{\prime}}}=\sum_{j=1}^{k-r_{i}^{\prime}}b_{i,j-1}^{q}X^{q^{j}}.$
(46)

By (45) and (46), we have $b_{i,j}=a_{i,j}$ if $i=m$ and
$b_{i,j}=a_{i,j+1}^{1/q}$ if $i\in[m-1]$. By the definition of $M^{\prime}$,
we see that each entry of $M^{\prime}$ is exactly the $q$-th power of the
corresponding entry of $M_{\mathcal{S}^{\prime}}$. As the map $x\mapsto x^{q}$
is a ring endomorphism of $\mathbb{F}$, this implies
$\det(M^{\prime})=\det(M_{\mathcal{S}^{\prime}})^{q}$. As
$\det(M_{\mathcal{S}^{\prime}})$ is nonzero, so is $\det(M^{\prime})$. Then
$\det(M_{\mathcal{S}})\neq 0$ by (44).

Now assume $r_{m}=1$. Let $\mathcal{S}^{\prime}=((V_{i},r_{i}))_{i\in[m-1]}$.
In this case, we have $S^{\prime}\in V_{k-1,m-1,s}$ by (43) and the fact that
$\sum_{i=1}^{m-1}r_{i}=k-1$. The tuple $\mathcal{S}^{\prime}$ satisfies (33)
since $\mathcal{S}$ does. By the induction hypothesis, we have
$\det(M_{\mathcal{S}^{\prime}})\neq 0$. Also, similar to the case where
$r_{m}>1$, each entry of $M^{\prime}$ is again the $q$-th power of the
corresponding entry of $M_{\mathcal{S}^{\prime}}$, and this implies
$\det(M^{\prime})=\det(M_{\mathcal{S}^{\prime}})^{q}\neq 0$.999The only
difference is that when $r_{m}>1$, we replace $(V_{m},r_{m})$ by
$(V_{m},r_{m}-1)$; whereas when $r_{m}=1$, we remove the pair
$(V_{m},r_{m})=(V_{m},1)$ and also decrease $m$ by one. Again, we conclude
that $\det(M_{\mathcal{S}})\neq 0$ by (44).

##### Case 3:

Neither Case 1 nor Case 2 holds. In other words, for any nonempty
$\Omega\subseteq[m]$ such that $2\leq|\Omega|\leq m-1$,

$\dim\left(\bigcap_{i\in\Omega}V_{i}\right)+\sum_{i\in\Omega}r_{i}\leq\max_{i\in\Omega}\\{\dim(V_{i})+r_{i}\\}-1$
(47)

and there exist distinct $i_{1},i_{2}\in[m]$ such that

$\dim(V_{i_{1}})+r_{i_{1}}=\dim(V_{i_{2}})+r_{i_{2}}=\max_{i\in[m]}\\{\dim(V_{i})+r_{i}\\}.$
(48)

Without loss of generality, assume $i_{1}=m-1$ and $i_{2}=m$. First, note that
if $V_{m-1}=V_{m}$, then

$\dim(V_{m-1}\cap
V_{m})+r_{m-1}+r_{m}=\dim(V_{m})+r_{m-1}+r_{m}>\max\\{\dim(V_{m-1})+r_{m-1},\dim(V_{m})+r_{m}\\}$

contradicting (33) with $\Omega=\\{m-1,m\\}$. So $V_{m-1}\neq V_{m}$.

As $(V_{i})_{i\in[m]}$ is $s$-admissible, there exist
$\mathbb{F}_{q}$-subspaces
$V,W\subseteq\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{n}\\}$ and a
nonzero $q$-linearized polynomial $f\in(\mathbb{F}_{q}[W])[X]$ in $X$ such
that $\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{n}\\}=V\oplus W$, $\dim
V\leq s$, and $V_{1},\dots,V_{m}\subseteq f(V)$. As $V_{m-1}\neq V_{m}$,
either $V_{m-1}\neq f(V)$ or $V_{m}\neq f(V)$. Without loss of generality,
assume $V_{m}\neq f(V)$. Note that applying an invertible linear
transformation to the variables $Z_{1},\dots,Z_{n}$ over $\mathbb{F}_{q}$
induces a ring isomorphism of
$\mathbb{F}_{q}[Z_{1},\dots,Z_{n}]\ni\det(M_{\mathcal{S}})$, which preserves
the (non)zeroness of $\det(M_{\mathcal{S}})$. By applying such a linear
transformation, we may assume
$V=\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{d}\\}$,
$f|_{V}^{-1}(V_{m})\subseteq\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{d-1}\\}$
and $W=\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{d+1},\dots,Z_{n}\\}$, where
$d:=\dim V\leq s$.

Let
$\pi:V=\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{d}\\}\to\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{d-1}\\}$
be the projection sending $u=\sum_{i=1}^{d}c_{i}Z_{i}$ to
$u|_{Z_{d}=0}=\sum_{i=1}^{d-1}c_{i}Z_{i}$. As $f\in(\mathbb{F}_{q}[W])[X]$
does not depend on $Z_{d}$, we have

$f(\alpha)|_{Z_{d}=0}=f(\alpha|_{Z_{d}=0})=f(\pi(\alpha))\quad\text{ for
}\alpha\in V.$ (49)

For $i\in[m]$, let $\widetilde{V}_{i}=f|_{V}^{-1}(V_{i})$,
$\widetilde{V}_{i}^{\prime}=\pi(\widetilde{V}_{i})\subseteq\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{d-1}\\}$
and $V_{i}^{\prime}=f(\widetilde{V}_{i}^{\prime})=f(\pi(\widetilde{V}_{i}))$.
Note that

$V_{m}^{\prime}=f(\pi(\widetilde{V}_{m}))=f(\widetilde{V}_{m})=V_{m}$ (50)

where the second equality holds since
$\widetilde{V}_{m}=f|_{V}^{-1}(V_{m})\subseteq\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{d-1}\\}$.
More generally, for $i\in[m]$,

$\dim V_{i}^{\prime}=\dim
f(\pi(\widetilde{V}_{i}))=\dim\pi(\widetilde{V}_{i})\geq\dim(\widetilde{V}_{i})-1=\dim(V_{i})-1.$
(51)

For $i\in[m]$, we have

$\displaystyle\prod_{\alpha\in
V_{i}}(X-\alpha|_{Z_{d}=0})^{q^{k-\dim(V_{i})-r_{i}}}$
$\displaystyle=\prod_{\alpha\in\widetilde{V}_{i}}(X-f(\alpha)|_{Z_{d}=0})^{q^{k-\dim(V_{i})-r_{i}}}$
(52)
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:restriction}}}{{=}}\prod_{\alpha\in\widetilde{V}_{i}}(X-f(\pi(\alpha)))^{q^{k-\dim(V_{i})-r_{i}}}$
$\displaystyle=\prod_{\alpha\in
V_{i}^{\prime}}(X-\alpha)^{q^{k-\dim(V_{i})-r_{i}+\dim(\widetilde{V}_{i})-\dim(V_{i}^{\prime})}}$
$\displaystyle=\prod_{\alpha\in
V_{i}^{\prime}}(X-\alpha)^{q^{k-\dim(V_{i}^{\prime})-r_{i}}}.$

Let
$V^{\prime}=\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{1},\dots,Z_{d-1}\\}\subseteq
V$ and
$W^{\prime}=\mathrm{span}_{\mathbb{F}_{q}}\\{Z_{d},\dots,Z_{n}\\}\supseteq W$.
Then $V^{\prime}_{i}=f(\pi(\widetilde{V}_{i}))\subseteq f(V^{\prime})$ for
$i\in[m]$. Note that $f$ is a $q$-linearized polynomial with coefficients in
$\mathbb{F}_{q}[W]\subseteq\mathbb{F}_{q}[W^{\prime}]$. Also note that $\dim
V^{\prime}=d-1\leq s-1$. By definition, $(V_{i}^{\prime})_{i\in[m]}$ is
$(s-1)$-admissible. Let
$\mathcal{S}^{\prime}=(V_{i}^{\prime},r_{i})_{i\in[m]}$. As $\dim
V_{i}^{\prime}\leq\dim\widetilde{V}_{i}=\dim V_{i}$ for $i\in[m]$, we have by
definition that $\mathcal{S}^{\prime}\in V_{k,m,s-1}$.

Next, we verify that $\mathcal{S}^{\prime}$ satisfies (33) for all nonempty
$\Omega\subseteq[m]$. If $|\Omega|=1$, then (33) holds trivially for