---
abstract: 'This work deals with partial MDS (PMDS) codes, a special class of locally repairable codes, used for distributed storage system. We first show that a known construction of these codes, using Gabidulin codes, can be extended to use any maximum rank distance code. Then we define a standard form for the generator matrices of PMDS codes and use this form to give an algebraic description of PMDS generator matrices. This implies that over a sufficiently large finite field a randomly chosen generator matrix in PMDS standard form generates a PMDS code with high probability. This also provides sufficient conditions on the field size for the existence of PMDS codes.'
author:
- 'Alessandro Neri and Anna-Lena Horlemann-Trautmann'
bibliography:
- 'PMDS\_stuff.bib'
title: Random Construction of Partial MDS Codes
---

Introduction
============

In a distributed storage system a file $x\in {{\mathbb{F}}}_q^k$ (where ${{\mathbb{F}}}_q$ denotes the finite field of cardinality $q$), is encoded and stored as some codeword $c\in {{\mathbb{F}}}_q^n$, over several storage nodes. Each of these nodes is assumed, for simplicity, to store exactly one coordinate of $c$. In case some of the nodes fail, we want to be able to recover the lost information using as little effort as possible. The *locality* of a code plays an important role in this context, and it denotes the number of nodes one has to contact for repairing a lost node. We call the set of nodes one has to contact if a given node fails, the locality group of that node. For this work we assume that the locality groups are distinct. *Partial MDS codes* are *maximally recoverable* codes in this setting, i.e., any erasure pattern that is information theoretically correctable is correctable with such a code.

It is known that maximally recoverable codes in general, and PMDS codes in particular, exist for any locality configuration if the field size is large enough [@ch07]. Furthermore, some constructions of PMDS codes are known, e.g. [@bl13; @bl14; @bl16; @ch15; @go14].

In this paper we describe a random construction of PMDS codes, by prescribing a generator matrix of the respective code in a specific form, which we will call *PMDS standard form*. If we fill the non-prescribed coordinates of this generator matrix with random values, by high probability, the resulting code is PMDS, if the underlying field size is large enough. We derive a lower bound on this probability (depending on the field size). This gives rise to a lower bound on the necessary field size for PMDS codes to exist. With some final adjustments on the random construction we get a lower bound that improves the one of [@ch07].

Preliminaries
=============

PMDS codes
----------

Consider a distributed storage system with $m$ disjoint locality groups, where the $i$-th group is of size $n_i$ ($i=1,\dots,m$) and can correct any $r_i$ erasures. First we set the locality for the code to be $\ell \in \mathbb N$. We can divide the coordinates of the code into blocks of length $n_1, \dots, n_m$, where $n_i=\ell+r_i$, such that each block represents a locality group.

We denote an MDS code of length $n$ and dimension $k$ by $[n,k]$-MDS code. We use the definition of PMDS codes given in [@ht17], which generalizes the definition of [@bl13].

Let $\ell,m, r_1,\dots,r_m \in \mathbb N$. Define $n:=\sum_{i=1}^m (r_i+\ell)$ and let $C\subseteq {{\mathbb{F}}}_q^n$ be a linear code of dimension $k<n$ with generator matrix $$\label{eq:genmatrix}
G= \left( B_1 \mid \dots \mid B_m \right) \in {{\mathbb{F}}}_q^{k\times n}$$ such that $B_i\in {{\mathbb{F}}}_q^{k\times ( r_i + \ell)}$. Then $C$ is a $[n,k, \ell ; r_1,\dots,r_m]$-*partial-MDS (PMDS) code* (with locality $\ell$) if

-   for $i\in \{1,\dots,m\}$ the row space of $B_i$ is a $[r_i+\ell, \ell ]$-MDS code, and

-   for any $r_i$ erasures in the $i$-th block ($i=1,\dots, m$), the remaining code (after puncturing the coordinates of the erasures) is a $[m\ell, k]$-MDS code.

The erasure correction capability of PMDS codes is as follows:

\[lem:PMDScap\][@ht17 Lemma 3] A $[n,k, \ell ; r_1,\dots,r_m]$-PMDS code can correct any $r_i$ erasures in the $i$-th block (simultaneously) plus $s:= m\ell -k$ additional erasures anywhere in the code.

We can see that the definition of PMDS codes given makes sense only for $k\geq \ell$. In case of equality, or in the case that $m=1$ there exist only trivial PMDS codes, i.e. the only PMDS codes are MDS codes.

It was shown in [@ht17] that a code is a $[n,k, \ell; r_1,\dots,r_m]$-PMDS code if and only if it is maximally recoverable (for the respective locality group configuration). The same results had previously been shown in [@go14 Lemma 4] for the case $r_1=r_2=\dots = r_m$.

Now we give a summary on known results about PMDS codes.

[@ch07]\[prop4\] Maximally recoverable (MR) codes of length $n$ and dimension $k$ exist for any locality configuration over any finite field of size $q> \binom{n-1}{k-1}$.

MR codes are PMDS codes for disjoint locality blocks. Therefore, Proposition \[prop4\] implies that PMDS codes exist for any set of parameters when the field size is large enough.

A construction of PMDS codes based on rank-metric and MDS codes was given in [@ca17], when $r_1=r_2=\dots=r_m$. This gives the following existence result:

[@ca17] $[n,k,\ell; r,\dots,r]$-PMDS codes with $m$ locality blocks of the same length exist over a finite field of size $q^{n-mr}$.

Furthermore, some specific constructions of PMDS codes, for particular values of $s$ or of the $r_i$, are given in [@bl13; @bl14; @bl16; @go14]. In particular, a general construction for PMDS codes with $s=1$ was given in [@ht17]. This construction is based on the concatenation of several MDS codes as building blocks.

[@ht17 Corollary 14]

1.  For any integers $m\geq 2 $ and $\ell,r_1,\dots,r_m \geq 1$ there exists a $[n,k=m\ell-1, \ell; r_1,\dots,r_m]$-PMDS code over any field ${{\mathbb{F}}}_q$ with $q\geq \max_i\{r_i\}+\ell$.

2.  If there exists $h\in \mathbb N$ such that $\ell\in \{3,2^h-1\}$ and $\max_i \{r_i\} +\ell = 2^h+1$, then there exists a $[n,k=m\ell-1, \ell; r_1,\dots,r_m]$-PMDS code over ${{\mathbb{F}}}_q$ with $q=2^h= \max_i\{r_i\}+\ell -1$.

In [@ht17] the authors also show that this construction is basically the only one possible, i.e., every PMDS with $s=1$ is of this form, giving thus a characterization for this set of parameters. However, for $s\geq 2$ there is no characterization yet for PMDS codes.

Zarisky topology over finite fields
-----------------------------------

Let ${{\mathbb{F}}}$ be a field, and ${{\mathbb{F}}}[x_1,\ldots,x_N]$ be the polynomial ring over ${{\mathbb{F}}}$. Denote by $\bar{{{\mathbb{F}}}}$ the algebraic closure of ${{\mathbb{F}}}$. For a subset $S\subseteq {{\mathbb{F}}}[x_1,\ldots,x_N]$ we define the *algebraic set* $$V(S): = \{{\boldsymbol}\alpha \in \bar{{\mathbb{F}}}_q^r \mid f({\boldsymbol}\alpha) = 0, \forall f \in S\} .$$

The *Zariski topology* on $\bar{{{\mathbb{F}}}}^N$ is defined as the topology whose closed sets are the algebraic sets, while the complements of the Zariski-closed sets are the *Zariski-open sets* [@ha13b Ch. I, Sec. 1].

A subset $A\subset\bar{{{\mathbb{F}}}}^N$ is called a *generic set* if $A$ contains a non-empty Zariski-open set.

In classical geometry one studies the Zariski topology over the complex numbers. In this framework, a generic set inside $\mathbb C^N$ is dense and its complement is contained in an algebraic set of dimension at most $N-1$.

If one wants to consider generic sets restricted to a finite field ${{\mathbb{F}}}_q$, the situation is slightly different. Here, for a subset $T\subseteq{{\mathbb{F}}}_q^N$ one can always find a set of polynomials $S\subseteq {{\mathbb{F}}}_q[x_1,\dots,x_N]$ such that $$T=\{{\boldsymbol}\alpha \in {{\mathbb{F}}}_q^N \mid f({\boldsymbol}\alpha) = 0, \forall f \in S\}.$$ and therefore the Zariski topology restricted to ${{\mathbb{F}}}_q^N$ is the discrete topology. This means that it is not useful to extend the notion of generic sets to finite fields since it would not give any information.

However, given a set of polynomials $S\subseteq{{\mathbb{F}}}_q[x_1,\ldots,x_N]$, we can define the set of *${{\mathbb{F}}}_q$-rational points* as $$V(S;{{\mathbb{F}}}_{q}): = \{{\boldsymbol}\alpha \in  {{\mathbb{F}}}_{q}^N \mid f({\boldsymbol}\alpha) = 0, \forall f \in S\} .$$ In this setting the Schwartz-Zippel Lemma implies an analog result to the one of generic sets, as explained in the following.

[@le98p Lemma 1.1]\[lem:SZ\] Let $f\in {{\mathbb{F}}}_q[x_1,\dots,x_N]$ be a non-zero polynomial of total degree $d \geq 0$. Let $T\subseteq \bar{{{\mathbb{F}}}}$ be a finite set and let $\alpha_1,   \dots, \alpha_N$ be selected at random independently and uniformly from $T$. Then $$\Pr\big(f(\alpha_1,\ldots,\alpha_N)=0\big)\leq\frac{d}{|T|}.$$

As a consequence of this result we have that, in case the size of $S$ and the total degrees of the polynomials in $S$ do not depend on the finite field, the proportion between the cardinality of $ V(S;{{\mathbb{F}}}_{q})$ and the cardinality of the whole space ${{\mathbb{F}}}_q^N$ goes to $0$ as $q$ grows. Vice versa, for growing $q$ the probability that a random point is in the complement of $ V(S;{{\mathbb{F}}}_{q})$ tends to $1$. This result will be crucial in Section \[sec:topprob\] for our random construction of PMDS codes.

Rank-metric codes
-----------------

We now give some known facts about rank-metric codes. Recall that ${\mathbb{F}_{q^N}}$ is isomorphic to ${\mathbb{F}_q}^N$ as an ${\mathbb{F}_q}$- vector space. From this it easily follows that ${\mathbb{F}_{q^N}}^n\cong {\mathbb{F}_q}^{N\times n}$. Then we can give the following definition.

The *rank distance* $d_R$ on ${{\mathbb{F}}}_q^{N\times n}$ is defined by $$d_R(U,V):= {\mathrm{rank}}(U-V) , \quad U,V \in {{\mathbb{F}}}_q^{N\times n}.$$ Analogously, if $\boldsymbol u,\boldsymbol v \in {\mathbb{F}_{q^N}}^n$, then $d_R(\boldsymbol u,\boldsymbol v)$ is the rank of the difference of the respective matrix representations in ${{\mathbb{F}}}_q^{N\times n}$.

Observe that the definition of rank distance in the case of vectors in ${\mathbb{F}_{q^N}}^n$ does not depend on the choice of the basis. Moreover it can be shown that the function $d_R: {\mathbb{F}_{q^N}}^n \times {\mathbb{F}_{q^N}}^n \rightarrow {{\mathbb{R}}}_{\geq 0}$ is a metric.

An *${\mathbb{F}_{q^N}}$-linear rank-metric code* ${\mathcal{C}}$ of length $n$ and dimension $k$ is a $k$-dimensional subspace of ${\mathbb{F}_{q^N}}^n$ equipped with the rank distance. The *minimum distance* of ${\mathcal{C}}$ is defined as $$d_R({\mathcal{C}}):=\min\left\{d_R({\boldsymbol}u,{\boldsymbol}v) \mid {\boldsymbol}u,{\boldsymbol}v\in {\mathcal{C}}, {\boldsymbol}u\neq {\boldsymbol}v\right\}.$$

\[th:SB\][@ro91 Theorem 1] Let ${\mathcal{C}}\subseteq {\mathbb{F}_{q^N}}^n$ be an ${\mathbb{F}_{q^N}}$-linear rank-metric code of dimension $k$. Then $$d_R({\mathcal{C}})\leq n-k+1.$$

Codes attaining the Singleton-like bound are called *Maximum Rank Distance (MRD) Codes*.

A necessary and sufficient condition for the existence of MRD codes is that $n\leq N$. In this framework, a characterization for ${\mathbb{F}_{q^N}}$-linear MRD codes in terms of their generator matrices was given in [@ho16 Corollary 2.12], which in turn is based on a result given in [@ga85]. For this we define the set $${\mathcal E}_q(k,n):=\left\{E \in {{\mathbb{F}}}_q^{k\times n} \mid {\mathrm{rank}}(E)=k\right\}.$$

\[prop:MRDCrit\] Let $G\in {{\mathbb{F}}}_{q^m}^{k\times n}$ be a generator matrix of a rank-metric code $\mathcal{C}\subseteq {{\mathbb{F}}}_{q^m}^n$. Then $\mathcal{C}$ is an MRD code if and only if $${\mathrm{rank}}(GE^T) =k$$ for all $E\in {\mathcal E}_q(k,n)$.

General construction using rank metric codes
============================================

In this section we generalize the construction given in [@ca17]. In that work the authors use Gabidulin codes in order to build $[n,k, \ell, r,\ldots,r]$-PMDS codes. We will show that this construction also works for different $r_i$, and that Gabidulin codes can be replaced by any linear MRD codes.

Fix $n, k,\ell, r_1,\ldots,r_m$, and let $\widetilde{G} \in {\mathbb{F}_{q^N}}^{k\times m\ell}$ be the generator matrix of a MRD code. For the existence of an MRD code we need $N\geq m\ell$. Moreover, for every $i=1,\ldots, m$, we consider a $[\ell+r_i,\ell]$-MDS code over ${\mathbb{F}_q}$ with generator matrix $M_i$, and define $$\label{eq:MDSblock}
 M:=\left(\begin{array}{cccc} M_1 & 0 & \ldots & 0 \\
0 & M_2 &\ldots & 0 \\
\vdots &  & \ddots & \vdots \\
0 & \ldots & 0 & M_m
\end{array}\right) \in {\mathbb{F}_q}^{m\ell \times n}.$$ We can now formulate our PMDS construction.

\[thm16\] Let $\widetilde{G} \in {\mathbb{F}_{q^N}}^{k\times m\ell}$ be the generator matrix of a MRD code and let $M$ be the matrix defined in (\[eq:MDSblock\]). Then the matrix $\widetilde{G}M$ is a generator matrix for a $[n,k,\ell,r_1,\ldots,r_m]$-PMDS code over ${\mathbb{F}_{q^N}}$.

Let $G:=\widetilde{G}M$ and let $S\in \mathcal T_{k,\ell}(G)$ be the submatrix obtained by selecting columns $h_1,\ldots,h_{k_j}$ from the $j$th block for $j=1,\ldots,m$, where $k_i\leq \ell$ and $k_1+\ldots+k_m=k$. $S$ is equal to $\widetilde{G}\widetilde{M}$, where $$\widetilde{M}=\left(\begin{array}{cccc} N_1 & 0 & \ldots & 0 \\
0 & N_2 &\ldots & 0 \\
\vdots &  & \ddots & \vdots \\
0 & \ldots & 0 & N_m
\end{array}\right),$$ and $N_j$ is the $\ell \times k_j$ submatrix of $M_j$ obtained by the respective selected columns. Since $M_i$ generates an $[\ell+r_i, \ell]$-MDS code, any $\ell$ columns of $M_i$ are linearly independent. Thus, ${\mathrm{rank}}(N_i)=k_i$ and ${\mathrm{rank}}(\widetilde{M})=k_1+\ldots+k_m=k$. By Proposition \[prop:MRDCrit\] we have that $\det(\widetilde{G}\widetilde{M})\neq 0$, and we conclude the proof using Proposition \[prop:PMDS\].

\[cor:exPMDS\] Let $m\geq 2 $ and $\ell,r_1,\dots,r_m \geq 1$, $k\geq \ell$ be positive integers. Then, for every prime $p$ and every positive integer $L\geq n_0m\ell$ there exists a $[n,k,\ell,r_1,\ldots,r_m]$-PMDS code over ${{\mathbb{F}}}_{p^L}$, where $$n_0=\min\{j \in {{\mathbb{N}}}\mid p^j \geq \ell + r_i-1, \mbox{ for } i=1,\ldots,m\}.$$

A MRD code in ${\mathbb{F}_{q^N}}^{ m\ell}$ exists if $N\geq m\ell$. Suitable MDS codes over ${{\mathbb{F}}}_q$ for the matrix in exist if $q\geq \max\{\ell + r_i - 1\}$. The statement follows from Theorem \[thm16\] with $q=p^{n_0}$ and $L=n_0N$.

Algebraic description of PMDS codes
===================================

We will now define a standard form for generator matrices of PMDS codes. This standard form is the main tool for the random construction of PMDS codes.

\[thm:stform\] Let $m\geq 2 $ and $s, \ell,r_1,\dots,r_m \geq 1$ and let ${\mathcal{C}}$ be a $[n,k=m\ell-s, \ell; r_1,\dots,r_m]$-PMDS code over a field ${{\mathbb{F}}}_q$. Then ${\mathcal{C}}$ has a generator matrix of the form $$\label{eq:stform}
{G}= \left({B}_1 \mid \dots \mid {B}_m \right),$$ where

-   ${B}_i=({C}_i \mid {D}_i)$, ${C}_i \in {{\mathbb{F}}}_q^{k \times \ell}$ and ${D}_i \in {{\mathbb{F}}}_q^{k\times r_i}$ for $i=1,\ldots, m$, and

-   the submatrix ${G}_{C}=\left({C}_1 \mid \dots \mid {C}_m \right)$ is of the form $${G}_C=\left[ I_{k} \mid A \right],$$ with $A$ being superregular.

Let $\widetilde{G}$ be a generator matrix for ${\mathcal{C}}$ of the form (\[eq:genmatrix\]), i.e. $$\widetilde{G}= \left(\widetilde{B}_1 \mid \dots \mid \widetilde{B}_m \right).$$ Puncturing every block $\widetilde{B}_i$ in the last $r_i$ columns, we get that the submatrix $\widetilde{G}_C$ is the generator matrix of a $[m\ell,k]$-MDS code. Operating on the rows of such a submatrix we can transform it to a matrix $G_C=\left[ I_{k} \mid A \right]$, with $A$ superregular. I.e., there exists an invertible matrix $P \in \mathrm{GL}_k({\mathbb{F}_q})$ such that $P\widetilde{G}_C=\left[ I_{k} \mid A \right]$, and therefore the matrix $G:=P\widetilde{G}$ is a generator matrix of ${\mathcal{C}}$ of the required form.

We now consider the entries $a_{w,z}$ of $A$ as variables $x_{w,z}$ for $w=1,\ldots,k$ amd $z=1,\ldots,s$. We know that the column space of ${D}_i$ is inside the column space of ${C}_i$, by the parameters of the block MDS codes. This means that every column in ${{D}_i}$ is a linear combination of the columns of ${{C}_i}$. If we denote by ${{D}_i}^{(j)}$ the $j$th column of ${{D}_i}$, then $$\label{eq:columns}
{{D}_i}^{(j)}=\sum_{t=1}^{\ell}y_{t,i,j}{{C}_i}^{(t)}$$ for some $y_{t,i,j}$, which we also consider variable. This way we can consider a $k\times n$ generator matrix as a matrix in ${{\mathbb{F}}}_q[x_{w,z}, y_{t,i,j}]^{k\times n}$ (where ${{\mathbb{F}}}_q[x_{w,z}, y_{t,i,j}]$ denotes the polynomial ring in all $x_{w,z}, y_{t,i,j}$).

Let $R=\sum_{i=1}^m r_i$. We denote $\boldsymbol{\alpha} := (\alpha_{w,z})_{w,z}\in {{\mathbb{F}}}_q^{sk}$ and $\boldsymbol{\beta} := (\beta_{t,i,j})_{t,i,j} \in {{\mathbb{F}}}_q^{\ell R}$. If we replace the variables $x_{w,z}, y_{t,i,j}$ described above in a matrix in PMDS standard form by the values $\alpha_{w,z}, \beta_{t,i,j}$, we denote the corresponding generator matrix by $$G(\boldsymbol{\alpha},\boldsymbol{\beta}).$$ Analogously we will denote the variable form by $ G(\boldsymbol{x},\boldsymbol{y})$.

However, a general matrix of this form is not necessarily a generator matrix of a PMDS code for any values $\boldsymbol{\alpha},\boldsymbol{\beta}$. The following proposition shows what needs to be fulfilled to generate a PMDS code:

\[prop:PMDS\] A matrix $G\in {{\mathbb{F}}}_q^{k\times n}$ generates a $[n,k=m\ell-s, \ell; r_1,\dots,r_m]$-PMDS code if and only if, every submatrix in the set $$\mathcal T_{k,\ell}(G):=\left\{S\in {{\mathbb{F}}}^{k \times k} \mid \begin{array}{l}S \mbox{ is a submatrix of } G \mbox{ with }\\ \mbox{ at most }  \ell \mbox{ columns per block } B_i \end{array}\right\}$$ has non-zero determinant.

This follows from the definition of PMDS, cf. also [@ht17].

The above results give an algebraic description of the generator matrix of a $[n,k=m\ell-s, \ell; r_1,\dots,r_m]$-PMDS code over ${{\mathbb{F}}}_q$, as follows. If we consider the variable form of a generator matrix $G$ as above, and the polynomial $$\label{eq:poly}
p(\boldsymbol{x},\boldsymbol{y}):= \mathrm{lcm} \{ \det S \mid S\in\mathcal T_{k,\ell}(G)\} \in  {{\mathbb{F}}}_q[x_{w,z}, y_{t,i,j}],$$ then, we have that $G(\boldsymbol{\alpha},\boldsymbol{\beta})$ generates a $[n,k=m\ell-s, \ell; r_1,\dots,r_m]$-PMDS code over ${{\mathbb{F}}}_q$ if and only if $p(\boldsymbol{\alpha},\boldsymbol{\beta})$ is non-zero.

Topological and probability results {#sec:topprob}
===================================

In this section we first deal with the algebraic description of the generator matrix of a PMDS code in the algebraic closure of the finite field where we want our code to be built. After that, we analyze the probability that a code whose generator matrix is of the form $G(\boldsymbol{\alpha},\boldsymbol{\beta})$ is PMDS. Moreover, we also study the existence of PMDS codes for given parameters $n,k,\ell, s, r_1,\ldots,r_m$ and $R=\sum_{i=1}^m r_i$, giving sufficient conditions on the field size. Although for $s=1$ this problem was completely solved in [@ht17], for $s\geq 2$ this is still an open problem.

We denote the set of valid entries for PMDS generator matrices over the algebraic closure of the finite field ${\mathbb{F}_q}$ by $$\small{\mathcal A_{\mathrm{PMDS}}:=\left\{(\boldsymbol{\alpha},\boldsymbol{\beta}) \in \bar{{{\mathbb{F}}}}_q^{sk}\times \bar{{{\mathbb{F}}}}_q^{\ell R}  \mid \mathrm{row space}(G(\boldsymbol{\alpha},\boldsymbol{\beta})) \mbox{ is PMDS}\right\},}$$ Then the following result holds.

\[th:gen\] $\mathcal A_{\mathrm{PMDS}}$ is a generic set.

By Proposition \[prop:PMDS\] we have that $$\mathcal A_{\mathrm{PMDS}}:=\left\{(\boldsymbol{\alpha},\boldsymbol{\beta}) \in \bar{{{\mathbb{F}}}}_q^{sk}\times \bar{{{\mathbb{F}}}}_q^{\ell R} \mid p(\boldsymbol{\alpha},\boldsymbol{\beta})\neq 0 \right\},$$ and therefore $\mathcal A_{\mathrm{PMDS}}$ is a Zariski open set.

Concerning the non-emptiness, let $q=p^{t_0}$. From Corollary \[cor:exPMDS\] there exists a $[n,k,\ell,r_1,\ldots,r_m]$-PMDS code ${\mathcal{C}}$ over ${{\mathbb{F}}}_{p^L}$, for some $L$ multiple of $t_0$. By Theorem \[thm:stform\], ${\mathcal{C}}$ has a generator matrix of the form $G(\boldsymbol{\alpha},\boldsymbol{\beta})$, therefore $(\boldsymbol{\alpha},\boldsymbol{\beta})\in \mathcal A_{\mathrm{PMDS}}$.

This means that over the algebraic closure, by probability $1$, for randomly chosen $\boldsymbol{\alpha},\boldsymbol{\beta}$ the matrix $G(\boldsymbol{\alpha},\boldsymbol{\beta})$ generates a PMDS code. For underlying *finite* fields, this implies that for growing field size this probability will tend to $1$. We now derive a probability formula depending on the field size.

We can easily observe that the entries of $G(\boldsymbol{x},\boldsymbol{y})$ are polynomials of total degree $0,1$ or $2$. In particular, if $t:=\lceil\frac{s}{\ell}\rceil$ and we write $G(\boldsymbol{x},\boldsymbol{y})$ as in , then the entries of the blocks ${{D}_i}$ are polynomials of degree at most $1$ for $i=1,\ldots, m-t$, and of degree at most $2$ for the last $t$ blocks. To estimate the degree of $p(\boldsymbol{x},\boldsymbol{y}) $ we need the following lemma.

\[lem:Vid\] $$\sum_{j=0}^r (r-j)\binom{m}{j}\binom{n}{r-j}=n\binom{m+n-1}{r-1}.$$

\[lem:deg\] The total degree of the polynomial $p(\boldsymbol{x},\boldsymbol{y})$, defined as in (\[eq:poly\]), satisfies the inequality $$\deg p(\boldsymbol{x},\boldsymbol{y}) \leq 2(n-k)\binom{n-1}{k-1}.$$

It holds that $$\mathcal T_{k,\ell}(G) \subset \mathcal M_k(G):=\{ S \in {\mathbb{F}_q}^{k\times k} \mid S \mbox{ is a submatrix of } G\},$$ hence the polynomial $p(\boldsymbol{x},\boldsymbol{y})$ divides the polynomial $$q(\boldsymbol{x},\boldsymbol{y}):=\mathrm{lcm}\{\det S \mid S\in \mathcal M_k(G)\}.$$ Observe that the entries of the first $k$ columns of the submatrix ${G}_C$ have degree 0. Let $t:=\lceil\frac{s}{\ell}\rceil$. Then the entries of the columns corresponding to the blocks ${{D}_i}$ for $i=1,\ldots, m-t$ have degree at most $1$, as well as the last $m\ell -k$ columns of ${G}_C$. Finally, the columns of the blocks ${{D}_i}$ for $i=m-t+1,\ldots, m$, have degree at most $2$. In particular, all the entries of the blocks ${{D}_i}$ and the last $m\ell -k$ columns of ${G}_C$ have degree at most $2$. Therefore, $$\begin{aligned}
\deg q(\boldsymbol{x},\boldsymbol{y}) &\leq \sum_{S \in \mathcal M_k(G)} \deg \det S \\
&\leq \sum_{j_0=0}^k2(k-j_0) \binom{k}{j_0}\binom{n-k}{k-j_0}\\
&=2(n-k)\binom{n-1}{k-1}\end{aligned}$$ where the last equality follows from Lemma \[lem:Vid\]. Since $\deg p(\boldsymbol{x},\boldsymbol{y}) \leq \deg q(\boldsymbol{x},\boldsymbol{y})$ we conclude the proof.

We can now formulate a lower bound for the probability that a randomly chosen generator matrix in PMDS standard form generates a PMDS code over a finite field ${{\mathbb{F}}}_q$:

\[thm:Prob\] Let the entries of $\boldsymbol{\alpha}$ and $\boldsymbol{\beta}$ be uniformly and independently chosen at random in ${\mathbb{F}_q}$. Then $$\mathrm{Pr}\{\mathrm{row space}(G(\boldsymbol{\alpha},\boldsymbol{\beta})) \mbox{ is PMDS  }\}\geq 1- \frac{2(n-k)\binom{n-1}{k-1}}{q}.$$

We have $$\begin{aligned}
 &\mathrm{Pr}\{\mathrm{row space}(G(\boldsymbol{\alpha},\boldsymbol{\beta})) \mbox{ is PMDS }\} \\
=&\mathrm{Pr}\{(\boldsymbol{\alpha},\boldsymbol{\beta}) \notin V(p(\boldsymbol{x},\boldsymbol{y});{\mathbb{F}_q})\}  \\
=&1-\mathrm{Pr}\{p(\boldsymbol{\alpha},\boldsymbol{\beta})=0\} \\
\geq& 1-\frac{\deg p(\boldsymbol{x},\boldsymbol{y})}{q}\geq 1 - \frac{2(n-k)\binom{n-1}{k-1}}{q},\end{aligned}$$

where the last two inequalities follow from Lemmas \[lem:SZ\] and \[lem:deg\], respectively.

From this we can deduce an existence result for PMDS codes over finite fields of a given minimal size.

If $q>2(n-k)\binom{n-1}{k-1}$ then there exists a $[n,k,\ell,r_1,\ldots,r_m]$-PMDS code over the finite field ${\mathbb{F}_q}$.

One notices that this is not an improvement over the known existence result from Proposition \[prop4\].

However, we can improve the above result, considering a step-by-step construction. We will again consider a generator matrix in PMDS standard form as in . We start with an $[m\ell,k]$-MDS code over a finite field ${\mathbb{F}_q}$ and write its generator matrix as $(C_1 \mid \dots \mid C_m)$. For this purpose it is sufficient that $q\geq m\ell -1$. Then we construct the first column $D_1^{(1)}$ of the block $D_1$ as in (\[eq:columns\]). Every entry will be a degree $1$ polynomial in the variables $y_{t,1,1}$ for $t=1,\ldots,\ell$. Imposing that every $k\times k$ minor of $$G':=\left( {C}_1\mid {D}_1^{(1)} \mid {C}_2\mid \ldots \mid {C}_m \right)$$ is non-zero, we get the condition $p'(y_{t,1,1})\neq 0$, where $$p'(y_{t,1,1})=\mathrm{lcm}\{ \det S \mid S \in \mathcal T_{k,\ell}(G')\}.$$ Using Lemma \[lem:SZ\], we obtain $$\mathrm{Pr}\{p'(\beta_{t,1,1})= 0\}\leq \frac{\deg p'}{q}.$$ In this situation $\deg p' \leq \binom{m\ell}{k-1}$, therefore for $q> \binom{m\ell}{k-1}$ we have that there exists at least one evaluation of $p'$ that is non-zero and such that $G'(\beta_{t,1,1})$ generates a $[n,k,\ell, 1,0,\ldots,0]$-PMDS code.

Repeating this construction step by step, we get a $[n,k,\ell,r_1,\ldots,r_{m-1},r_{m}-1]$-PMDS code. From that code we build the last column ${D}_m^{(r_m)}$ of the block ${D}_m$ again as in (\[eq:columns\]): $${D}_m^{(r_m)}=\sum_{t=1}^{\ell}y_{t,m,r_m}{C}_m^{(t)}.$$ In the end we get the matrix

$$\label{eq:G}
{G}(y_{t,m,r_m})=({C}_1\mid {D}_1 \mid \ldots \mid {C}_m \mid {D}_m ),$$

where the matrix ${G}(y_{t,m,r_m})$ without the last column generates a $[n,k,\ell,r_1,\ldots,r_{m-1},r_{m}-1]$-PMDS code, and the entries of the last column are polynomials of total degree at most $1$ in the variables $y_{t,m,r_m}$, for $t=1,\ldots,\ell$.

Let $m, n, k, n_1,\ldots,n_m, f_1,\ldots,f_m$ be positive integers such that $n=\sum_i n_i$. Let $N_0:=0$, $N_i:=\sum_{j=1}^i n_j$ and $J_i=\{N_{i-1}+1,\ldots,N_i\}$ for $i=1,\ldots,m-1$. We define the set $$\mathcal M(k;n_1\ldots,n_m;f_1,\ldots,f_m)
=\> \left\{I \subset \{1,\ldots,n\}\mid |I|=k, |I\cap J_i|\leq f_i\right\}$$ and $M(k;n_1\ldots,n_m;f_1,\ldots,f_m)$ as its cardinality.

Let ${G}(y_{t,m,r_m})$ be as in (\[eq:G\]). The total degree of the polynomial $$\tilde{p}(y_{t,m,r_m}):=\mathrm{lcm}\{\det S \mid S\in \mathcal T_{k,\ell}({G}(y_{t,m,r_m}))\}$$ is less or equal to $$M(k-1;\ell+r_1\ldots,\ell+r_{m-1},\ell+r_m-1;\ell,\ldots,\ell,\ell-1) =: M^*.$$

The polynomial $\tilde{p}(y_{t,m,r_m})$ has degree less or equal to $\sum \deg \det S$. By assumption all the determinants $\det S$ for $S$ not containing the last column are non zero elements in ${\mathbb{F}_q}$. The only polynomials with degree $1$ are the determinants of $k\times k$ submatrices involving the last column, and they are exactly $M^*$ many.

\[cor25\] If $q>M^*$ then there exists a $[n,k,\ell,r_1,\ldots,r_m]$-PMDS code over the finite field ${\mathbb{F}_q}$.

To our knowledge there is no closed formula for $M^*$. However, it is easy to see that $M^* \leq \binom{n-1}{k-1}$ and that the inequality is strict if any of the conditions $|I\cap J_i|\leq f_i$ is non-empty. Hence, Corollary \[cor25\] improves upon Proposition \[prop4\].

Conclusion
==========

We gave a generalization of a known PMDS code construction based on rank-metric codes. Furthermore, we investigated a random construction of PMDS codes by prescribing a PMDS standard form. We derived a lower bound on the probability that a randomly filled matrix in PMDS standard form generates a PMDS code. This probability implies a lower bound on the field size needed for such codes to exist. In the end we gave a step-by-step construction of such a generator matrix to improve this lower bound on the necessary field size.
