Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.20983 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911634599968768 |
|---|---|
| author | Appuswamy, Rathinakumar Bazzani, Marco Congero, Spencer Connelly, Joseph Ekaireb, Matthew Zeger, Kenneth |
| author_facet | Appuswamy, Rathinakumar Bazzani, Marco Congero, Spencer Connelly, Joseph Ekaireb, Matthew Zeger, Kenneth |
| contents | Let $C$ be an $[n,k]$ linear code chosen uniformly at random over a finite field $\mathbb{F}_q$ of size $q$. The following asymptotic probability of $C$ being maximum distance separable (MDS) as $q,n,k\to\infty$ is known: If $\frac{1}{q}\binom{n}{k} \to 0$, then $P(C\ \text{is MDS}) \to 1$. We demonstrate that this growth rate is in fact a threshold by proving: If $\frac{1}{q}\binom{n}{k} \to \infty$, then $P(C\ \text{is MDS}) \to 0$. A matrix is ($\textit{contiguous}$) $\textit{super-regular}$ if all of its (contiguous) square submatrices are nonsingular. The above results imply that for any $k \times k$ matrix $A$ chosen uniformly at random over $\mathbb{F}_q$, the following hold: If $\frac{4^k/\sqrt{k}}{q} \to 0$, then $P(A \text{ is super-regular}) \to 1$. If $\frac{4^k/\sqrt{k}}{q}\to \infty$, then $P(A \text{ is super-regular}) \to 0$. We also obtain the following asymptotic probabilities for two variations of the above questions: If $\frac{1}{q}\binom{n}{k} \to λ\in (0,\infty)$ and $k/n\to 0$, then $P(C\ \text{is MDS}) \to e^{-λ}$. If $\frac{k^3/3}{q} \to λ\in [0,\infty]$, then $P(A \text{ is contiguous super-regular}) \to e^{-λ}$. The number of super-regular $3\times 3$ matrices is known to be a polynomial in $q$. We show that the number of contiguous super-regular $3\times 3$ matrices is also a polynomial. Finally, for $4\times 4$ matrices, we show that the number of super-regular matrices is not a polynomial, nor even a quasi-polynomial of period less than $7$, whereas our experimental evidence suggests that the number of contiguous super-regular matrices is a polynomial. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_20983 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Probability of super-regular matrices and MDS codes over finite fields Appuswamy, Rathinakumar Bazzani, Marco Congero, Spencer Connelly, Joseph Ekaireb, Matthew Zeger, Kenneth Information Theory Let $C$ be an $[n,k]$ linear code chosen uniformly at random over a finite field $\mathbb{F}_q$ of size $q$. The following asymptotic probability of $C$ being maximum distance separable (MDS) as $q,n,k\to\infty$ is known: If $\frac{1}{q}\binom{n}{k} \to 0$, then $P(C\ \text{is MDS}) \to 1$. We demonstrate that this growth rate is in fact a threshold by proving: If $\frac{1}{q}\binom{n}{k} \to \infty$, then $P(C\ \text{is MDS}) \to 0$. A matrix is ($\textit{contiguous}$) $\textit{super-regular}$ if all of its (contiguous) square submatrices are nonsingular. The above results imply that for any $k \times k$ matrix $A$ chosen uniformly at random over $\mathbb{F}_q$, the following hold: If $\frac{4^k/\sqrt{k}}{q} \to 0$, then $P(A \text{ is super-regular}) \to 1$. If $\frac{4^k/\sqrt{k}}{q}\to \infty$, then $P(A \text{ is super-regular}) \to 0$. We also obtain the following asymptotic probabilities for two variations of the above questions: If $\frac{1}{q}\binom{n}{k} \to λ\in (0,\infty)$ and $k/n\to 0$, then $P(C\ \text{is MDS}) \to e^{-λ}$. If $\frac{k^3/3}{q} \to λ\in [0,\infty]$, then $P(A \text{ is contiguous super-regular}) \to e^{-λ}$. The number of super-regular $3\times 3$ matrices is known to be a polynomial in $q$. We show that the number of contiguous super-regular $3\times 3$ matrices is also a polynomial. Finally, for $4\times 4$ matrices, we show that the number of super-regular matrices is not a polynomial, nor even a quasi-polynomial of period less than $7$, whereas our experimental evidence suggests that the number of contiguous super-regular matrices is a polynomial. |
| title | Probability of super-regular matrices and MDS codes over finite fields |
| topic | Information Theory |
| url | https://arxiv.org/abs/2603.20983 |