Pith. sign in

REVIEW 8 minor 1 cited by

Some constructions of non-generalized Reed-Solomon MDS Codes

T0 review · 0 major / 8 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves exact, checkable conditions—nonzero elementary symmetric sums on every k-subset and (k−1)-subset of an evaluation set—under which two classes of extended codes are maximum distance separable (MDS), and shows that in the…

desk verdict Solid incremental contribution to the non-GRS MDS literature; the main determinant arguments check out, but two unproved statements and several typos should be fixed before this becomes a standard reference. read the letter →

arxiv 2506.04080 v2 pith:WZ45QAWJ submitted 2025-06-04 cs.IT math.IT

Kanat Abdukhalikov , Cunsheng Ding , Gyanendra K. Verma This is my paper
classification cs.ITmath.IT MSC 51E2105B2594B65
keywords MDScodegeneralizedReed-Solomonnon-GRSelementarysymmetricfunctionVandermondedeterminantparity-checkmatrixo-polynomialhyperoval
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper asks when certain linear codes built by deleting one or two powers from the usual Reed–Solomon evaluation matrix, then extending, remain maximum distance separable. It proves exact conditions: MDSness of the one-point extension $C_1$ is equivalent to the nonvanishing of elementary symmetric sums $\sigma_r$ on every $k$-subset and $\sigma_{r-1}$ on every $(k-1)$-subset of the evaluation points; the two-point extension $C_2$ adds a third condition labelled $(\#)$. In the range $6 \le 2k \le n$ any code meeting these conditions is not equivalent to a generalized Reed–Solomon code, so the construction yields optimal codes outside the GRS family. The same machinery gives parity-check matrices for the new codes and, for dimension $3$ over even fields, a new characterization of $o$-monomials in terms of complete symmetric functions.

What carries the argument

The load-bearing machinery is a pair of generalized Vandermonde determinant identities. Proposition 2.4 (cited from [22]) says that a Vandermonde matrix with one exponent row removed and a new row of exponent $n$ added has determinant equal to the Vandermonde product times the elementary symmetric sum $\sigma_r$; Lemma 2.5 (cited from [20]) says that replacing the top-degree row by exponent $h$ yields the Vandermonde product times the complete symmetric function $S_{h-n+1}$. These identities reduce every relevant $k\times k$ minor of $G_{r,k}$, $G_1$, and $G_2$ to a Vandermonde factor times an elementary or complete symmetric sum, turning the MDS condition that all minors be nonsingular into nonvanishing of those symmetric functions on all subsets of the evaluation set. Lemma 2.6, derived from [16], supplies the orthogonality identities used to verify the parity-check matrices.

What would settle it

A concrete disproof would be a single evaluation set and parameters $(n,k,r)$ for which every $k$-subset has $\sigma_r\neq 0$ and every $(k-1)$-subset has $\sigma_{r-1}\neq 0$, yet some $k\times k$ minor of $G_1$ is singular; Theorem 4.5 says this cannot happen, so a computer search over, say, all $6$-subsets of $\mathbb{F}_{17}$ would settle the necessity claim.

Watch

Extended reading notes

Core claim

The paper establishes necessary and sufficient conditions for two families of extended codes to be maximum distance separable, and proves that those MDS codes are non-GRS. The first family $C_1$, generated by appending a column $(0,0,\ldots,0,1)^T$ to the generator matrix of the code $C_{r,k}$ introduced in [12], is MDS if and only if every $k$-subset of the evaluation set has nonzero $r$-th elementary symmetric sum $\sigma_r$ and every $(k-1)$-subset has nonzero $\sigma_{r-1}$. The second family $C_2$, with two appended columns, is MDS if and only if the same two conditions hold together with a third condition $(\#)$ involving $\sigma_{r-2}$, the parameter $\delta$, and the sum of the selected evaluation points. The paper also derives parity-check matrices for both families and, via the connection between MDS codes and arcs in finite projective spaces for $k=3$ over even fields, characterizes monomial $o$-polynomials $x^h$ by the nonvanishing of the complete symmetric function $S_{h-2}$ on every triple of distinct field elements.

Load-bearing premise

The whole argument rests on the cited generalized Vandermonde determinant identities holding for every possible subset of evaluation points, including matrices where one exponent row is skipped; if that identity failed for even one subset, the claimed if-and-only-if MDS conditions would collapse.

Editorial extensions

If this is right

  • If the conditions of Theorem 4.5 are met with $6 \le 2k \le n$, the resulting $[n+1,k]$ code is guaranteed to be a non-GRS MDS code, so the construction yields codes that are optimal in distance and not equivalent to generalized Reed–Solomon codes.
  • The explicit parity-check matrices $H_1$ and $H_2$ give a concrete way to verify codewords and study the duals of these non-GRS MDS codes.
  • Corollary 4.10 gives the existence of $[n+1,k]$ non-GRS MDS codes over odd primes $p$ whenever $6 \le 2k \le n$ and $n \le p/k + (k+1)/2$.
  • Corollaries 4.11 and 4.12 convert the existence of a code with a certain weight-distribution property into the existence of a non-GRS MDS code, such as a $[12,5]$ non-GRS MDS code over $\mathbb{F}_{3^7}$ obtained from an $[11,4,6]$ code over $\mathbb{F}_3$.
  • Theorem 6.4 characterizes $o$-monomials: over $\mathbb{F}_{2^m}$, the polynomial $x^h$ is an $o$-polynomial if and only if $S_{h-2}$ is nonzero on every triple of distinct field elements.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: the same determinant pattern suggests that adding further extending columns would impose one additional elementary-symmetric nonvanishing condition per added column, with the cases $r=1$ and $r=2$ behaving as lower-order degenerations; the paper does not state this.
  • Inference: because the conditions in Theorem 4.5 are purely combinatorial conditions on the evaluation set, they give a cheap filter for searching large finite fields for new non-GRS MDS codes; the paper does not discuss search cost.
  • Inference: Theorem 6.4 turns the $o$-monomial question into a finite verification problem, namely checking $S_{h-2}\neq 0$ on triples, which could be implemented directly as a computational test for candidate exponents $h$; the paper only states the equivalence.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 8 minor

Summary. The paper studies two classes of extended codes built from the code family C_{r,k} introduced by Jin, Ma, Xing, and Zhou, and proves necessary and sufficient conditions for these codes to be MDS: Theorem 3.2 characterizes when C_{r,k} itself is MDS, Theorem 4.5 characterizes the one-point extension C_1 by the nonvanishing of two families of elementary symmetric sums, and Theorem 5.5 gives a three-condition plus an extra delta-condition characterization for the two-point extension C_2. The paper also gives parity-check matrices for these codes and, in Section 6, connects 3-dimensional MDS codes to o-polynomials, characterizing o-monomials x^h by nonvanishing of complete symmetric sums S_{h-2} on triples.

Significance. The central contribution is a clean, explicit equivalence between MDS-ness of these code families and nonvanishing of concrete symmetric polynomials in the evaluation points. The proofs are largely elementary determinant identities rather than black-box arguments, and the conditions are directly checkable; the examples are verified with MAGMA. I traced the applications of Proposition 2.4 and Lemma 2.5 in Theorems 3.2, 4.5, and 5.5, and the parameter shifts (r to r-1 or r-2 when passing to smaller square minors) are correct, so the main determinant-based concern does not land. The non-GRS label is inherited from the prior Schur-square result in [12], with the paper's own contribution being the MDS characterization and the transfer argument via Lemma 4.2. The main mathematical core is sound.

minor comments (8)
  1. [Section 4, Corollary 4.11] Corollary 4.11 is asserted without proof or citation; it is not an immediate consequence of the preceding theorems, so please either supply a proof or replace the statement by a precise reference to the source.
  2. [Section 5, Proposition 5.2] Proposition 5.2 has no proof; saying that the proof is similar to Theorem 5.1 is not enough because the last row entry delta-S_2 differs from the entry b in Theorem 5.1, so please include the orthogonality calculation or cite a reference where this exact matrix is derived.
  3. [Section 6, Theorem 6.4] Theorem 6.4 is stated for every positive integer h with gcd(h,q-1)=1, but the expression S_{h-2} is undefined for h=1; please add the hypothesis h >= 2, and either treat the case q=2, h=1 separately or exclude it, since for q>2 the polynomial x is not an o-polynomial.
  4. [Section 5, Proposition 5.6] In the first displayed condition of Proposition 5.6, the indices j_2,...,j_r do not exist when r=1; the condition should be the nonvanishing of the sum of the k selected evaluation points.
  5. [Sections 4 and 5] When Proposition 2.4 is applied to a (k-1)x(k-1) or (k-2)x(k-2) minor in Theorems 4.5 and 5.5, the parameter r is implicitly replaced by r-1 or r-2; stating this substitution explicitly would improve readability and prevent a common source of confusion.
  6. [Section 5, definition of G2] The displayed matrix G2 before Theorem 5.1 appears to assume r >= 2; for r=1 the matrix must be understood through the accompanying description of C_2, so please indicate this explicitly in the definition.
  7. [Throughout] There are several typographical errors: 'coloumn' in Section 2, 'deep whole' in Corollaries 4.15 and 5.9, and 'o-polinomial' in Section 6.
  8. [Section 5, Remark 5.3] The notation H_{n-k+2} in Remark 5.3 is not defined in the paper; please define the matrix from [29] or avoid the notation.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the central MDS derivations rest on external determinant identities and an external non-GRS base, with only independent self-cited lemmas.

full rationale

The derivation chain is self-contained rather than circular. Theorem 3.2 reduces every k-by-k minor of G_{r,k} to a Vandermonde determinant times the elementary symmetric sum sigma_r via Proposition 2.4, which is cited from Muir's external determinant treatise [22]; the necessity direction uses exactly the same identity, so its content is not presupposed. The non-GRS assertion is imported from Jin et al. [12], an external source, not from the present authors. The extension results Theorems 4.5 and 5.5 likewise apply Proposition 2.4 and Lemma 2.5 (from Marchi [20]) to the appended-column minors; the computations identify the relevant minor as a cofactor matrix of the same type, with parameters r-1 and r-2, and the r=1 and r=2 edge cases reduce to Vandermonde determinants. These are direct derivations, not renamings of the desired conclusion. The self-citations that appear are not circular loads: Lemma 4.2 from [27] (a paper co-authored by Ding) is used to transfer non-GRS from C_{r,k} to its extensions, but it is an elementary parameter-free statement whose contrapositive is true by puncturing a monomial-equivalent GRS code; the cited theorem does not assume the target result. Theorem 4.14 from [26] is used only to draw corollaries about covering radii and deep holes, and it is not used to establish the MDS or non-GRS conclusions. The unproved Corollary 4.11, the omitted proof of Proposition 5.2, and the compressed proofs of Theorems 4.7 and 5.7 are presentation gaps, not circular reductions. No fitted parameter is relabeled as a prediction, and no theorem's conclusion is equivalent to its hypotheses by construction.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central construction introduces no invented entities. One construction parameter, delta, is free but is not fitted to data; Theorem 5.5 identifies which delta values are allowed. The main unproved background is the standard Vandermonde determinant toolkit and the prior non-GRS result from [12]. The non-GRS conclusion for the extended codes is inherited rather than re-proved in this paper.

free parameters (1)
  • delta = any field element satisfying condition (#) in Theorem 5.5
    Construction parameter of the second extended code family; not fitted to data, but the MDS condition depends on it.
assumptions (4)
  • standard math Singleton bound and the MDS generator-matrix criterion (Lemma 2.3)
    Standard coding theory fact used throughout the paper to test MDS-ness via nonsingular minors.
  • standard math Vandermonde determinant identities (Proposition 2.4, Lemma 2.5, Lemma 2.6)
    Quoted from [22], [20], and [16]; load-bearing for every determinant computation in Sections 3 to 6.
  • domain assumption Theorem 6.3: a length q+2 code from an o-polynomial is MDS if and only if the polynomial is an o-polynomial
    Known finite-geometry result [11], used as a black box in the o-monomial characterization.
  • domain assumption The prior non-GRS result for C_{r,k} from [12, Proposition VI.1]
    The paper proves MDS necessity but inherits the non-GRS conclusion for C_{r,k} and for the extended codes through Lemma 4.2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Some constructions of non-generalized Reed-Solomon MDS Codes." pith.science (2026). https://pith.science/paper/WZ45QAWJ

@misc{pith2026250604080,
  author       = {Pith},
  title        = {Pith review of: Some constructions of non-generalized Reed-Solomon MDS Codes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WZ45QAWJ}},
  note         = {Machine review of arXiv:2506.04080}
}
read the original abstract

We investigate two classes of extended codes and provide necessary and sufficient conditions for these codes to be non-GRS MDS codes. We also determine the parity check matrices for these codes. Using the connection of MDS codes with arcs in finite projective spaces, we give a new characterization of o-monomials.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Row-Column Twisted Reed-Solomon codes

    cs.IT 2025-09 conditional novelty 5.0 of 10

    A new family of maximum-distance-separable codes, RCTRS, is built by applying row and column twists to Reed-Solomon codes and is claimed to be inequivalent to both RS and column-twisted RS codes.

Reference graph

Works this paper leans on

29 extracted references · 15 canonical work pages · cited by 1 Pith paper

  1. [15]

    Y. Li, Z. Sun, and S. Zhu. A family of linear codes that are either non-GRS MDS codes or NMDS codes.arXiv:2401.04360

    arXiv

  2. [29]

    Zhi and S

    Y. Zhi and S. Zhu. New MDS codes of non-GRS type and NMDS codes.Discrete Mathematics, 348:114436, 2025. 25

    work page 2025

  3. [12]

    L. Jin, L. Ma, C. Xing, and H. Zhou. New families of non-Reed-Solomon MDS codes.arXiv:2411.14779

    arXiv

  4. [1]

    Abdukhalikov

    K. Abdukhalikov. Bent functions and line ovals.Finite Fields Appl., 47:94–124, 2017

    work page 2017

  5. [2]

    Abdukhalikov

    K. Abdukhalikov. Hyperovals and bent functions.European J. Combin., 79:123– 139, 2019

    work page 2019

  6. [3]

    S. Ball. On large subsets of a finite vector space in which every subset of basis size is a basis.Journal of the European Mathematical Society, 14(3):733–748, 2012

    2012

  7. [4]

    S. Ball. Grassl–R¨ otteler cyclic and consta-cyclic MDS codes are generalised Reed–Solomon codes.Designs, Codes and Cryptography, 91(5):1685–1694, 2023

    work page 2023

  8. [5]

    Ball and M

    S. Ball and M. Lavrauw. Arcs in finite projective spaces.EMS Surveys in Mathematical Sciences, 6(1-2):133–172, 2019

    2019

Show all 29 references
  1. [6]

    Beelen, M

    P. Beelen, M. Bossert, S. Puchinger, and J. Rosenkilde. Structural properties of twisted Reed-Solomon codes with applications to cryptography. In2018 IEEE International Symposium on Information Theory (ISIT), pages 946–950, 2018

    2018

  2. [7]

    Beelen, S

    P. Beelen, S. Puchinger, and J. Rosenkilde. Twisted Reed–Solomon codes.IEEE Transactions on Information Theory, 68(5):3047–3061, May 2022

    2022

  3. [8]

    Beelen, S

    P. Beelen, S. Puchinger, and J. Rosenkilde n´ e Nielsen. Twisted Reed-Solomon codes. In2017 IEEE International Symposium on Information Theory (ISIT), pages 336–340, 2017

    2017

  4. [9]

    Caullery and K.-U

    F. Caullery and K.-U. Schmidt. On the classification of hyperovals.Adv. Math., 283:195–203, 2015

    2015

  5. [10]

    H. Chen. Many non-Reed-Solomon type MDS codes from arbitrary genus alge- braic curves.IEEE Transactions on Information Theory, 70:4856–4864, 2022

    2022

  6. [11]

    J. W. P. Hirschfeld.Projective geometries over finite fields. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York, second edition, 1998. 23

    1998

  7. [13]

    Kiss and T

    G. Kiss and T. Sz˝ onyi.Finite Geometries. Taylor & Francis CRC Press, 1 edition, 2023

    2023

  8. [14]

    Lavauzelle and J

    J. Lavauzelle and J. Renner. Cryptanalysis of a system based on twisted Reed–Solomon codes.Designs, Codes and Cryptography, 88:1285 – 1300, 2019

    2019

  9. [16]

    Li, L.-J

    Z. Li, L.-J. Xing, and X.-M. Wang. Quantum generalized Reed-Solomon codes: Unified framework for quantum maximum-distance-separable codes.Physic Re- view A, 77:012308, Jan 2008

    2008

  10. [17]

    S. Liu, H. Liu, and F. E. Oggier. Constructions of non-generalized Reed-Solomon MDS codes.arXiv:2412.08391

    arXiv

  11. [18]

    I. G. Macdonald.Symmetric Functions and Hall Polynomials. Oxford University Press, Oxford, 2nd edition, 1995

    1995

  12. [19]

    F. J. MacWilliams and N. J. A. Sloane.The Theory of Error-Correcting Codes. Elsevier, Amsterdam, The Netherlands, 1977

    1977

  13. [20]

    S. D. Marchi. Polynomials arising in factoring generalized vandermonde determi- nants: an algorithm for computing their coefficients.Mathematical and Computer Modelling, 34:271–281, 2001

    2001

  14. [21]

    Mirandola and G

    D. Mirandola and G. Z´ emor. Critical pairs for the product Singleton bound. IEEE Trans. Inform. Theory, 61(9):4928–4937, 2015

    2015

  15. [22]

    T. C. Muir.A Treatise on the Theory of Determinants. 1960

    1960

  16. [23]

    R. M. Roth and A. Lempel. A construction of non-Reed-Solomon type MDS codes.IEEE Transactions on Information Theory, 35:655–657, 1989

    1989

  17. [24]

    B. Segre. Curve razionali normali ek-archi negli spazi finiti.Annali di Matem- atica Pura ed Applicata, 39:357–378, December 1955

    1955

  18. [25]

    Seroussi and R

    G. Seroussi and R. M. Roth. On MDS extensions of generalized Reed-Solomon codes.IEEE Transactions on Information Theory, 32(3):349–354, 1986

    1986

  19. [26]

    Y. Wu, C. Ding, and T. Chen. When does the extended code of an MDS code remain MDS?IEEE Transactions on Information Theory, 71:263–272, 2025

    2025

  20. [27]

    Y. Wu, Z. Heng, C. Li, and C. Ding. More MDS codes of non-Reed-Solomon type.arXiv:2401.03391. 24

    arXiv

  21. [28]

    Y. Wu, J. Y. Hyun, and Y. Lee. New LCD MDS codes of non-Reed–Solomon type.IEEE Transactions on Information Theory, 67(8):5069–5078, Aug. 2021

    2021

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.