pith. sign in

arxiv: 2603.20983 · v2 · submitted 2026-03-22 · 💻 cs.IT · math.IT

Probability of super-regular matrices and MDS codes over finite fields

Rathinakumar Appuswamy , Marco Bazzani , Spencer Congero , Joseph Connelly , Matthew Ekaireb , Kenneth Zeger This is my paper

Pith reviewed 2026-05-15 02:10 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords MDS codessuper-regular matricesfinite fieldsasymptotic probabilitythreshold phenomenalinear codesrandom matricesPoisson limit
0
0 comments X

The pith

Random [n,k] codes over F_q are MDS with probability tending to 1 or 0 according to whether binom(n,k)/q tends to 0 or infinity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the probability a uniformly random linear code over a finite field is maximum distance separable undergoes a sharp threshold. When binom(n,k)/q tends to zero under joint growth of the parameters, this probability tends to one. When the same ratio tends to infinity, the probability tends to zero. Parallel threshold statements are established for the event that a random square matrix is super-regular, using the growth rate 4^k over sqrt(k) times 1/q. The work also derives Poisson limits for the probabilities in intermediate regimes and determines when the exact count of such matrices is a polynomial in the field size.

Core claim

If (1/q) binom(n,k) tends to 0 then the probability that a random [n,k] code is MDS tends to 1; if it tends to infinity then the probability tends to 0. The same dichotomy holds for super-regularity of random k by k matrices with the quantity 4^k/sqrt(k)/q. When the ratio tends to a finite positive lambda and k/n tends to 0, the MDS probability tends to e^{-lambda}. When k^3/(3q) tends to lambda the contiguous-super-regular probability tends to e^{-lambda}. The number of super-regular 3 by 3 matrices is a polynomial in q, as is the number of contiguous super-regular 3 by 3 matrices; for 4 by 4 matrices the super-regular count is not a polynomial nor a quasi-polynomial of period less than 7.

What carries the argument

Uniform random selection of linear codes and matrices over F_q together with asymptotic enumeration of the events that all relevant square submatrices are nonsingular.

If this is right

  • When binom(n,k)/q tends to a positive finite constant lambda and k/n tends to 0, the MDS probability tends to e to the minus lambda.
  • When k cubed over 3q tends to a finite lambda, the probability a random matrix is contiguous super-regular tends to e to the minus lambda.
  • The exact count of super-regular 3 by 3 matrices is a polynomial in q, and the same holds for contiguous super-regular 3 by 3 matrices.
  • For 4 by 4 matrices the count of super-regular matrices is neither a polynomial nor a quasi-polynomial of period smaller than 7.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The threshold supplies a concrete regime in which random selection already produces MDS codes with overwhelming probability, suggesting that explicit constructions may only be needed below that regime.
  • The Poisson limits indicate that the number of non-MDS obstructions behaves like a Poisson random variable when the ratio is order 1, which may be useful for concentration bounds.
  • The distinction between super-regular and contiguous super-regular counts for 4 by 4 matrices hints that locality constraints on the minors change the algebraic dependence on q.

Load-bearing premise

The field size q and the code parameters n and k all tend to infinity simultaneously under the stated growth conditions on their ratios.

What would settle it

For a concrete sequence with binom(n,k)/q growing like log n, compute the exact fraction of MDS codes for successive values and check whether that fraction drops from near 1 to near 0.

Figures

Figures reproduced from arXiv: 2603.20983 by Joseph Connelly, Kenneth Zeger, Marco Bazzani, Matthew Ekaireb, Rathinakumar Appuswamy, Spencer Congero.

Figure 1
Figure 1. Figure 1: An example of a 5 ˆ 16 matrix A with two different 5 ˆ 5 submatrices (blue and red) that share two columns (split blue/red). Lemma 2.5. Let A be a random k ˆ n matrix over the field Fq and let B and B1 be distinct k ˆ k submatrices of A that share exactly j columns. Then, PpB and B 1 are singularq ď 2 q k`1´j ` 1 pq ´ 1q 2 . Proof. Let J be the event that the columns of A shared by both B and B1 are linear… view at source ↗
Figure 2
Figure 2. Figure 2: An example of a 9 ˆ 9 square matrix (black) A with a 4 ˆ 4 contiguous submatrix B anchored at p5, 7q formed by deleting from A all but its red columns and blue rows. The corner decomposition pB, u, v ¯ q of B is shown to the right in green. The following lemma is used in the proof of Lemma 3.3. Lemma 3.1. (e.g., [17, pp. 24-26]) If U is a nonsingular m ˆ m matrix, V is an m ˆ n matrix, W is an n ˆ m matrix… view at source ↗
Figure 3
Figure 3. Figure 3: Square contiguous submatrices anchored at [PITH_FULL_IMAGE:figures/full_fig_p024_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The matrix M shown when minpi, jq “ 6. For each m “ 2, . . . , minpi, jq, since vm “ B¯mpB¯´1 m vmq, if the first entry of B¯´1 m vm is 0, then vm is a linear combination of the right-most m ´ 2 columns of B¯m (or vm “ 0 in the case Sections: 1 2 3 4 5 6 References Page 24 of 49 [PITH_FULL_IMAGE:figures/full_fig_p025_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Plots of the probability of a random k ˆ k matrix over Fq being super-regular or contiguous super-regular. The red curves are e ´λ . The green curves are counts of 3 ˆ 3 matrices based on Theorem 4.4(a) for super-regular and (b) for contiguous super-regular. Each blue dot is the fraction of 1000 randomly selected k ˆ k matrices over Fq that were super-regular (where λ “ 1 q ` 2k k ˘ ) or contiguous super-r… view at source ↗
read the original abstract

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 \lambda \in (0,\infty)$ and $k/n\to 0$, then $P(C\ \text{is MDS}) \to e^{-\lambda}$. If $\frac{k^3/3}{q} \to \lambda \in [0,\infty]$, then $P(A \text{ is contiguous super-regular}) \to e^{-\lambda}$. 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper establishes sharp threshold results for the probability that a random [n,k] linear code over F_q is MDS: if (1/q) binom(n,k) -> 0 then P(MDS) -> 1, while if (1/q) binom(n,k) -> infinity then P(MDS) -> 0. It further derives a Poisson limit P(MDS) -> e^{-lambda} when the quantity tends to a finite lambda >0 and k/n ->0. Analogous thresholds and limits are proved for random k x k matrices being super-regular (threshold 4^k / sqrt(k) / q) and contiguous super-regular (threshold k^3/3 / q). The paper also proves that the number of contiguous super-regular 3x3 matrices over F_q is a polynomial in q, while the number of (non-contiguous) super-regular 4x4 matrices is neither a polynomial nor a quasi-polynomial of period less than 7.

Significance. If the results hold, they give precise asymptotic characterizations of MDS codes and super-regular matrices in the large-q regime, using direct combinatorial counting and moment methods. These thresholds are load-bearing for applications in coding theory and matrix-based constructions; the Poisson limits and small-case polynomiality statements are additional contributions that clarify the transition and counting behavior.

minor comments (2)
  1. [§3] §3, after Eq. (3): the transition from the first-moment upper bound to the second-moment argument for the divergence case could be expanded with an explicit reference to the deletion method or Paley-Zygmund inequality used to control dependence among singular submatrices.
  2. [§5] The statement that the number of super-regular 4x4 matrices is not a quasi-polynomial of period less than 7 relies on experimental evidence; a brief description of the computational method (e.g., the range of q tested and the period-search algorithm) would strengthen the claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. The summary accurately captures the main contributions on MDS thresholds, Poisson limits, and the polynomiality results for small super-regular matrices.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's core derivations consist of direct combinatorial enumeration of singular submatrices (for MDS codes) and contiguous square submatrices (for super-regular matrices), followed by standard first-moment arguments showing expected violations tend to infinity or to a constant, plus method-of-moments or Stein-Chen arguments for the Poisson limit under k/n -> 0. These steps rely on the uniform random model and the stated asymptotic growth conditions; they do not reduce any claimed prediction to a fitted input, self-definition, or load-bearing self-citation. The reference to a 'known' result is external prior work, and the new threshold and Poisson statements are obtained independently from the counting arguments. No ansatz smuggling, uniqueness theorems from the same authors, or renaming of known results occurs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard combinatorial properties of finite fields and uniform random selection; no free parameters are fitted and no new entities are postulated.

axioms (2)
  • domain assumption Uniform random selection of linear codes and matrices over finite fields
    Standard modeling assumption in random coding arguments, invoked throughout the probability statements.
  • domain assumption Asymptotic limits as q, n, k tend to infinity under the stated growth conditions
    The threshold and Poisson results are stated only in this regime.

pith-pipeline@v0.9.0 · 5758 in / 1372 out tokens · 36081 ms · 2026-05-15T02:10:02.095814+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages · 3 internal anchors

  1. [1]

    Akemann, J

    G. Akemann, J. Baik, and P. Di Francesco,The Oxford handbook of random matrix theory, Oxford University Press. 2011

    work page 2011

  2. [2]

    Superregular matrices over small finite fields

    P. Almeida and D. Napp, “Superregular matrices over small finite fields”, arXiv:2008.00215v1, August 2020

    work page arXiv 2008

  3. [3]

    A new class of superregular matrices and MDP convo- lutional codes

    P. Almeida, D. Napp, and R. Pinto, “A new class of superregular matrices and MDP convo- lutional codes”,Linear Algebra and its Applications, vol. 439, pp. 2145-2157, 2013

    work page 2013

  4. [4]

    Anderson, A

    G.W. Anderson, A. Guionnet, and O. Zeitouni,An introduction to random matrices, Cam- bridge University Press, 2010

    work page 2010

  5. [5]

    Two moments suffice for Poisson approximations: The Chen-Stein method

    R. Arratia, L. Goldstein, and L. Gordon, “Two moments suffice for Poisson approximations: The Chen-Stein method”,The Annals of Probability, vol. 17, no. 1, pp. 9–25, 1989

    work page 1989

  6. [6]

    Arratia, L

    R. Arratia, L. Goldstein, and L. Gordon, ”Poisson approximation and the Chen-Stein method”,Statistical Science, vol. 5, no. 4, pp. 403–434, 1990

    work page 1990

  7. [7]

    On the distribution of rank of a random matrix over a finite field

    C. Cooper, “On the distribution of rank of a random matrix over a finite field”,Random Structures and Algorithms, 17 (3-4), pp. 197–212, 2000

    work page 2000

  8. [8]

    Balanced sparsest generator matrices for MDS codes

    S. H. Dau, W. Song, Z. Dong, and C. Yuen. “Balanced sparsest generator matrices for MDS codes”,IEEE International Symposium on Information Theory (ISIT), pp. 1889—1893

    work page

  9. [9]

    (Also arXiv:1301.5108.v1)

    work page internal anchor Pith review Pith/arXiv arXiv

  10. [10]

    On the existence of MDS codes over small fields with constrained generator matrices

    S. H. Dau, W. Song, Z. Dong, and C. Yuen. “On the existence of MDS codes over small fields with constrained generator matrices”,IEEE International Symposium on Information Theory (ISIT), pp. 1787–1791, 2014

    work page 2014

  11. [11]

    The probability that a matrix is nilpotent

    N.J. Fine and I.N. Herstein, “The probability that a matrix is nilpotent”,Illinois Journal of Mathematics. vol. 2, pp. 499–504, 1958

    work page 1958

  12. [12]

    The eigenvalue distribution of a random unipotent matrix in its representation on lines

    J. Fulman, “The eigenvalue distribution of a random unipotent matrix in its representation on lines”,Journal of Algebra, vol. 228, pp. 497–511, 2000

    work page 2000

  13. [13]

    Random matrix theory over finite fields

    J. Fulman, “Random matrix theory over finite fields”,Bulletin (New Series) of the American Mathematical Society, vol. 39, pp. 51–85, 2002

    work page 2002

  14. [14]

    Hyperplane sections of Grassmannians and the number of MDS linear codes

    S.R. Ghorpade and G. Lachaud, “Hyperplane sections of Grassmannians and the number of MDS linear codes”,Finite Fields and Their Applications, vol. 7, pp. 468–506, 2001

    work page 2001

  15. [15]

    Strongly-MDS convolutional codes

    H. Gluesing-Luerssen, J. Rosenthal, and R. Smarandache, “Strongly-MDS convolutional codes”,IEEE Transactions on Information Theory, vol. 52, no. 2, February 2006, pp. 584– 598

    work page 2006

  16. [16]

    How random is the characteristic polynomial of a random ma- trix?

    J. Hansen and E. Schmutz, “How random is the characteristic polynomial of a random ma- trix?”,Mathematical Proceedings of the Cambridge Philosophical Society, vol. 114, pp. 507– 515, 1993

    work page 1993

  17. [17]

    The 1959 Annali di Matematica paper of Beniamino Segre and its legacy

    J. W. P. Hirschfeld, “The 1959 Annali di Matematica paper of Beniamino Segre and its legacy”,Journal of Geometry, June 2003. Sections: 1 2 3 4 5 6 ReferencesPage 47 of 49 Probability of super-regular matrices and MDS codes over finite fieldsMarch 20, 2026

    work page 1959

  18. [18]

    Horn and C

    R. Horn and C. Johnson,Matrix analysis, Second Edition, Cambridge University Press, New York, 2013

    work page 2013

  19. [19]

    An algorithm for counting arcs in higher-dimensional projective space

    K. Isham, “An algorithm for counting arcs in higher-dimensional projective space”,Finite Fields and Their Applications, vol. 80, pp. 102006, 2022

    work page 2022

  20. [20]

    A note on upper bounds for minimum distance codes

    D.D. Joshi, “A note on upper bounds for minimum distance codes”,Information and Control, vol. 1, no. 3, pp. 289–295, 1958

    work page 1958

  21. [21]

    Singularity probabilities for random matrices over finite fields

    J. Kahn and J. Koml ´os, “Singularity probabilities for random matrices over finite fields”, Combinatorics, Probability, and Computing, vol. 10, no. 2, pp. 137–157, 2001

    work page 2001

  22. [22]

    An asymptotic formula inqfor the number ofrn, ksq-ary MDS codes

    K. Kaipa, “An asymptotic formula inqfor the number ofrn, ksq-ary MDS codes”,IEEE Transactions on Information Theory, vol. 60, no. 11, pp. 7047–7057, November 2014

    work page 2014

  23. [23]

    Application of logical mathematics to information theory

    Y . Komamiya, “Application of logical mathematics to information theory”,Proceedings of the 3rd Japanese National Congress on Applied Mathematics, pp. 58–70, January 31, 1953 (in Japanese)

    work page 1953

  24. [24]

    On the determinant of random matrices

    J. Koml ´os, “On the determinant of random matrices”,Studia Scientiarum Mathematicarum Hungarica, vol. 3, pp. 387–399, 1968

    work page 1968

  25. [25]

    On the rank of matrices with random Boolean elements

    M. V . Kozlov, “On the rank of matrices with random Boolean elements”,Soviet Mathematics - Doklady, vol. 7, pp. 1048–1051, 1966

    work page 1966

  26. [26]

    Sparse MDS matrices over small fields: A proof of the GM-MDS conjecture

    S. Lovett, “Sparse MDS matrices over small fields: A proof of the GM-MDS conjecture”, SIAM Journal on Computing, vol. 50, no. 4, pp. 1248–1262, 2021

    work page 2021

  27. [27]

    F. J. MacWilliams and N.J.A. Sloane,The theory of error-correcting codes, North-Holland Publishing Company, 1977

    work page 1977

  28. [28]

    Singularity of Random Matrices over Finite Fields

    K. Maples, “Singularity of random matrices over finite fields”, arXiv.org/abs/1012.2372, De- cember 2010

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  29. [29]

    Convertible codes: New class of codes for efficient conver- sion of coded data in distributed storage

    F. Maturana and K. V . Rashmi, “Convertible codes: New class of codes for efficient conver- sion of coded data in distributed storage”,11th Innovations in Theoretical Computer Science Conference, Article No. 66, pp. 66:1 – 66:26, 2020

    work page 2020

  30. [30]

    Mehta,Random Matrices, Amsterdam: Elsevier/Academic Press

    M.L. Mehta,Random Matrices, Amsterdam: Elsevier/Academic Press. 2004

    work page 2004

  31. [31]

    Potters and J.-P

    M. Potters and J.-P. Bouchaud,A first course in random matrix theory: for physicists, engi- neers and data scientists, Cambridge University Press, 2020

    work page 2020

  32. [32]

    Roth,Introduction to coding theory, Cambridge University Press, 2006

    R. Roth,Introduction to coding theory, Cambridge University Press, 2006

    work page 2006

  33. [33]

    On MDS codes via Cauchy matrices

    R. M. Roth and A. Lempel, “On MDS codes via Cauchy matrices”,IEEE Transactions on Information Theory, vol. 35, no. 6, pp. 1314–1319, November 1989

    work page 1989

  34. [34]

    On generator matrices of MDS codes

    R. M. Roth and G. Seroussi, “On generator matrices of MDS codes”,IEEE Transactions on Information Theory, vol. 31, no. 6, pp. 826 – 830, November 1985

    work page 1985

  35. [35]

    On the rank of random matrices over finite fields

    D. Salmond, A. Grant, I. Grivell, and T. Chan, “On the rank of random matrices over finite fields”, https://arxiv.org/pdf/1404.3250, 2016. Sections: 1 2 3 4 5 6 ReferencesPage 48 of 49 Probability of super-regular matrices and MDS codes over finite fieldsMarch 20, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  36. [36]

    On the distribution of the entries of a fixed-rank random matrix over a finite field

    C. Sanna, “On the distribution of the entries of a fixed-rank random matrix over a finite field”, Finite Fields and Their Applications, vol. 93, 2024

    work page 2024

  37. [37]

    The order of a typical matrix with entries in a finite field

    E. Schmutz, “The order of a typical matrix with entries in a finite field”,Israel Journal of Mathematics, vol. 91, pp. 349–71. 1995

    work page 1995

  38. [38]

    Curve razionali normali ek–archi negli spazi finiti

    B. Segre, “Curve razionali normali ek–archi negli spazi finiti”,Annali di Matematica Pura Applicata, vol. 39, pp. 357–379, 1955

    work page 1955

  39. [39]

    Maximum distanceq-nary codes

    R.C. Singleton, “Maximum distanceq-nary codes”,IEEE Transactions on Information The- ory, vol. 10, no. 2, pp. 116–118, 1964

    work page 1964

  40. [40]

    Linear codes, strata of Grassmannians and the problems of Segre

    A. N. Skorobogatov, “Linear codes, strata of Grassmannians and the problems of Segre”, Coding theory and algebraic geometry, H. Stichtenoth and M. A. Tsfasman, Eds., Lecture Notes in Mathematics, vol. 1518, pp. 210–223, Springer-Verlag, Berlin, 1992

    work page 1992

  41. [41]

    Optimum linear codes with support-constrained generator matrices over small fields

    H. Yildiz and B. Hassibi, “Optimum linear codes with support-constrained generator matrices over small fields”,IEEE Transactions on Information Theory, vol. 65, no. 12, pp. 7868–7875, 2019. Sections: 1 2 3 4 5 6 ReferencesPage 49 of 49

    work page 2019