arxiv: 2605.12133 · v1 · submitted 2026-05-12 · 💻 cs.IT · math.IT

Recognition: no theorem link

A framework for constructing non-GRS MDS-NMDS codes from deep holes and its application

Yang Li , Zhenliang Lu , San Ling , Kwok-Yan Lam

Authors on Pith no claims yet

Pith reviewed 2026-05-13 04:00 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords non-GRS MDS-NMDS codesdeep holescovering radiusextended codesgeneralized Reed-Solomon codesMDS codesnear-MDS codesmonomial equivalence

0 comments

The pith

Starting from non-GRS MDS-NMDS codes whose covering radius equals n-k, a framework produces new non-GRS MDS-NMDS codes of length n+1 via deep-hole extensions.

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

The paper supplies a unified construction that takes any family of [n,k] non-GRS MDS or near-MDS codes achieving the largest possible covering radius and produces longer [n+1,k+1] members of the same class. The extension is realized by adjoining a coordinate at a deep hole; the resulting codes remain outside the monomial-equivalence class of generalized Reed-Solomon and extended GRS codes. The same procedure is rewritten in the language of the second kind of extended codes, which both recovers a recent theorem and lowers the computational effort required by earlier methods. When the framework is applied to extended subcodes of GRS codes, it yields three explicit new families together with a complete determination of their covering radii and two classes of deep holes.

Core claim

If a family of [n,k]_q non-GRS MDS-NMDS codes has covering radius exactly n-k, then adjoining a coordinate at any deep hole produces a family of [n+1,k+1]_q non-GRS MDS-NMDS codes. This construction is equivalent to forming the second kind of extended code, which recovers the main result of Wu-Ding-Chen, reduces the complexity of the Ma-Kai-Zhu approach, and reveals extra algebraic structure. The framework is instantiated on extended subcodes of GRS codes to obtain three new families and to characterize their deep holes.

What carries the argument

Deep-hole extension of codes that already attain covering radius n-k; equivalently, the second kind of extended code operation.

If this is right

Three new infinite families of non-GRS MDS-NMDS codes are obtained from extended subcodes of GRS codes.
The covering radius of those extended subcodes is completely determined and two classes of their deep holes are characterized.
The monomial equivalence of the constructed codes with Roth-Lempel codes is settled for the new families.
The second-kind reformulation gives a provably cheaper way to generate the same codes than the earlier Ma-Kai-Zhu procedure.

Where Pith is reading between the lines

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

Iterating the construction produces infinite ascending chains of non-GRS MDS-NMDS codes for any fixed alphabet size.
The extra structural properties uncovered may help decide monomial equivalence for other optimal code families.
Because the method works uniformly for both MDS and NMDS starting points, it offers a single route to enlarge tables of known non-GRS codes.
The deep-hole characterization for extended GRS subcodes may generalize to other Reed-Solomon-like constructions.

Load-bearing premise

The original codes must have covering radius exactly n-k so that the added coordinate truly corresponds to a deep hole.

What would settle it

Take a concrete small-field [n,k] non-GRS MDS-NMDS code known to have covering radius n-k, extend it at a deep hole, and check whether the resulting length-n+1 code is still non-GRS and meets the MDS or NMDS distance bound.

read the original abstract

Maximum distance separable (MDS) codes and near MDS (NMDS) codes are of particular interest in coding theory due to their optimal error-correcting capabilities and wide applications in communication, cryptography, and storage systems. A family of linear codes is called a family of non-GRS MDS-NMDS codes if for each $[n,k]_q$ code in the family, it is either an $[n,k,n-k+1]_q$ MDS code that is not monomially equivalent to any GRS code or extended GRS code, or an $[n,k,n-k]_q$ NMDS code. This paper develops a unified framework for constructing new families of non-GRS MDS-NMDS codes via deep holes. We show that, starting from a family of $[n,k]_q$ non-GRS MDS-NMDS codes with covering radius $n-k$, one can systematically obtain more $[n+1,k+1]_q$ non-GRS MDS-NMDS codes. The proposed framework is further reformulated in terms of the second kind of extended codes. This reformulation recovers a main result of Wu, Ding, and Chen (IEEE Trans. Inf. Theory, 71(1): 263-272, 2025), provides a provable reduction in the computational complexity compared with the approach of Ma, Kai, and Zhu (Finite Fields Appl., 114, 102844, 2026), and reveals additional structural properties of the resulting codes. As an application, we determine the covering radius and characterize two classes of deep holes of extended subcodes of GRS codes. By applying our framework, we obtain three new families of non-GRS MDS-NMDS codes and investigate the monomial equivalence between the resulting codes and Roth-Lempel codes.

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.

Desk Editor's Note private letter to a colleague

The paper gives a framework to extend non-GRS MDS-NMDS codes from deep holes, yielding three new families and a simpler recovery of prior work.

read the letter

The main point is that you can take a family of non-GRS MDS-NMDS codes with covering radius exactly n-k and extend them by one length using deep holes to produce new families of the same type. The authors do this and end up with three fresh families. They also characterize the covering radius and deep holes for extended subcodes of generalized Reed-Solomon codes. This approach recovers the main theorem from Wu, Ding, and Chen but with a clear drop in computational complexity compared to Ma, Kai, and Zhu. The reformulation using the second kind of extended codes helps show additional properties of the codes. Applying the framework to those GRS subcodes gives the new examples, and they check monomial equivalence against Roth-Lempel codes. The argument holds together. They prove that the extension preserves the MDS or NMDS distance and the non-equivalence to GRS or extended GRS codes. The starting point for the GRS subcodes is verified by computing the covering radius directly. One soft spot is the dependence on having initial codes with covering radius precisely n-k. While the paper supplies this for the cases it uses, finding such codes in other settings could require extra effort. The equivalence investigation is parameter-specific, so it works for the families presented but might not generalize easily. Readers working on MDS code constructions over finite fields will get the most out of this. It supplies explicit new families and a systematic way to generate more, which matters for applications in error correction and cryptography. The paper shows clear thinking on the topic and engages with the recent literature. It deserves a serious referee because the new families and the simplified recovery of prior work add real value. I recommend sending it to peer review.

Referee Report

0 major / 3 minor

Summary. The paper develops a unified framework for constructing families of non-GRS MDS-NMDS codes from deep holes. It proves that any family of [n,k]_q non-GRS MDS-NMDS codes with covering radius exactly n-k yields, via deep-hole extension, a new family of [n+1,k+1]_q non-GRS MDS-NMDS codes. The construction is reformulated using the second kind of extended codes; this recovers the main result of Wu-Ding-Chen, reduces computational complexity relative to Ma-Kai-Zhu, and exposes additional structural properties. As an application the authors determine the covering radius of extended subcodes of GRS codes, characterize two classes of their deep holes, produce three new explicit families of non-GRS MDS-NMDS codes, and compare them with Roth-Lempel codes under monomial equivalence.

Significance. If the preservation proofs hold, the work supplies a systematic, complexity-reducing method for generating optimal codes outside the GRS class, which is valuable for applications in communications, cryptography and storage. The recovery of a prior theorem, the explicit new families, and the structural insights on deep holes constitute concrete contributions to the catalog and theory of MDS/NMDS codes.

minor comments (3)

[§3.2] §3.2, after Definition 3.4: the statement that the extension preserves the non-GRS property is asserted to follow from the covering-radius hypothesis, but the argument would be clearer if the monomial-equivalence check were written out explicitly rather than referred to an earlier lemma.
[Table 1] Table 1 (new families): the parameter ranges for q and the explicit generator matrices are given, yet the table does not indicate the field sizes for which the non-equivalence to Roth-Lempel codes was verified computationally; adding this information would strengthen the claim.
[§5.1] §5.1, paragraph following Theorem 5.3: the complexity comparison with Ma-Kai-Zhu is stated in big-O terms; a short numerical example for a concrete (n,k,q) would make the reduction more tangible.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our manuscript, which correctly captures the unified framework for constructing non-GRS MDS-NMDS codes from deep holes, the recovery of the Wu-Ding-Chen result, the complexity reduction relative to Ma-Kai-Zhu, and the three new explicit families obtained as an application. We are pleased that the referee recognizes the potential value for applications in communications, cryptography, and storage. Since the report contains no specific major comments or requests for clarification, we have no individual points to address.

Circularity Check

0 steps flagged

No significant circularity; forward construction from assumed inputs

full rationale

The paper defines a framework that takes as given any family of [n,k]_q non-GRS MDS-NMDS codes possessing covering radius exactly n-k and proves that a deep-hole extension produces a new family of [n+1,k+1]_q non-GRS MDS-NMDS codes while preserving the required distance and non-equivalence properties. This is a standard constructive implication, not self-definitional: the input codes are external to the derivation and the output properties are established by direct proof rather than by re-labeling fitted parameters. The reformulation via second-kind extended codes is shown to recover the Wu-Ding-Chen result as a special case, which is presented as a consistency check rather than a load-bearing premise. The separate determination of covering radii for extended subcodes of GRS codes supplies independent content used to instantiate three new families. No self-citation chain, ansatz smuggling, or renaming of known results is required for the central claims.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based solely on the abstract, the work relies on standard coding theory concepts without introducing new free parameters or invented entities.

axioms (2)

standard math The Singleton bound holds for linear codes over finite fields, with MDS codes achieving equality.
Used to define MDS and NMDS codes.
domain assumption Covering radius and deep holes are standard, well-defined notions for linear codes.
Central to the extension framework.

pith-pipeline@v0.9.0 · 5640 in / 1207 out tokens · 92659 ms · 2026-05-13T04:00:44.055130+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

48 extracted references · 48 canonical work pages · 1 internal anchor

[1]

Some constructions of non-generalized Reed-Solomon MDS codes,

K. Abdukhalikov, C. Ding, and G. K. Verma, “Some constructions of non-generalized Reed-Solomon MDS codes,”Discrete Math., vol. 349, no. 10, 115202, 2026

work page 2026
[2]

Ball,Finite Geometry and Combinatorial Applications

S. Ball,Finite Geometry and Combinatorial Applications. Cambridge: Cambridge University Press, 2015

work page 2015
[3]

Structural properties of twisted Reed-Solomon codes with applications to cryptography,

P. Beelen, M. Bossert, S. Puchinger, and J. Rosenkilde, “Structural properties of twisted Reed-Solomon codes with applications to cryptography,” inProc. IEEE Int. Symp. Inf. Theory (ISIT), pp. 946–950, 2018

work page 2018
[4]

Twisted Reed–Solomon codes,

P. Beelen, S. Puchinger, and J. Rosenkilde, “Twisted Reed–Solomon codes,”IEEE Trans. Inf. Theory, vol. 68, no. 5, pp. 3047–3061, 2022

work page 2022
[5]

The Magma algebra system I: The user language,

W. Bosma, J. Cannon, and C. Playoust, “The Magma algebra system I: The user language,”J. Symb. Comput., vol. 24, no. 3–4, pp. 235–265, 1997

work page 1997
[6]

Permutation code: Optimal exact-repair of a single failed node in MDS code based distributed storage systems,

V . R. Cadambe, C. Huang, and J. Li, “Permutation code: Optimal exact-repair of a single failed node in MDS code based distributed storage systems,” inProc. IEEE Int. Symp. Inf. Theory (ISIT), pp. 1225–1229, 2011

work page 2011
[7]

Many non-Reed-Solomon type MDS codes from arbitrary genus algebraic curves,

H. Chen, “Many non-Reed-Solomon type MDS codes from arbitrary genus algebraic curves,”IEEE Trans. Inf. Theory, vol. 70, no. 7, pp. 4856–4864, 2024

work page 2024
[8]

On the structure of the Schur squares of twisted generalized Reed-Solomon codes and application to cryptanalysis,

A. Couvreur, R. Pratihar, N. Tanısalı, and I. Zappatore, “On the structure of the Schur squares of twisted generalized Reed-Solomon codes and application to cryptanalysis,” inProc. Int. Conf. Post-Quantum Cryptogr. (PQCrypto), pp. 3–34, 2025

work page 2025
[9]

On the covering radius of Reed-Solomon codes,

A. Dur, “On the covering radius of Reed-Solomon codes,”Discrete Math., vol. 126, pp. 99–105, 1994

work page 1994
[10]

On near-MDS codes,

S. Dodunekov and I. Landgev, “On near-MDS codes,”J. Geom., vol. 54, no. 1–2, pp. 30–43, 1995

work page 1995
[11]

Deep holes of twisted Reed-Solomon codes,

W. Fang, J. Xu, and R. Zhu, “Deep holes of twisted Reed-Solomon codes,”Finite Fields Appl., vol. 108, 102680, 2025

work page 2025
[12]

Algebraic quantum codes,

M. Grassl, “Algebraic quantum codes,” presented at the 12th Int. Workshop on Coding and Cryptography (WCC 2022). [Online]. Available: https://www.wcc2022.uni-rostock.de/storages/uni-rostock/Tagungen/WCC2022/Papers/GRASSL WCC2022 2022-03-08.pdf

work page 2022
[13]

Roth–Lempel NMDS codes of non-elliptic-curve type,

D. Han and C. Fan, “Roth–Lempel NMDS codes of non-elliptic-curve type,”IEEE Trans. Inf. Theory, vol. 69, no. 9, pp. 5670–5675, 2023

work page 2023
[14]

A tight upper bound for the maximal length of MDS elliptic codes,

D. Han and Y . Ren, “A tight upper bound for the maximal length of MDS elliptic codes,”IEEE Trans. Inf. Theory, vol. 69, no. 2, pp. 819–822, 2023

work page 2023
[15]

W. C. Huffman and V . Pless,Fundamentals of Error-Correcting Codes. Cambridge: Cambridge University Press, 2003

work page 2003
[16]

New families of non-Reed-Solomon MDS codes,

L. Jin, L. Ma, C. Xing, and H. Zhou, “New families of non-Reed-Solomon MDS codes,”IEEE Trans. Inf. Theory, vol. 72, no. 2, pp. 985-993, 2026

work page 2026
[17]

Deep holes and MDS extensions of Reed-Solomon codes,

K. Kaipa, “Deep holes and MDS extensions of Reed-Solomon codes,”IEEE Trans. Inf. Theory, vol. 63, no. 8, pp. 4940–4948, 2017

work page 2017
[18]

Deep holes in Reed-Solomon codes based on Dickson polynomials,

M. Keti and D. Wan, “Deep holes in Reed-Solomon codes based on Dickson polynomials,”Finite Fields Appl., vol. 40, pp. 110–125, 2016

work page 2016
[19]

The main conjecture for near-MDS codes,

I. Landjev and A. Rousseva, “The main conjecture for near-MDS codes,” inProc. 9th INt. Workshop on Coding Cryptogr. (WCC), pp. 1-8, 2015

work page 2015
[20]

Cryptanalysis of a system based on twisted Reed-Solomon codes,

J. Lavauzelle and J. Renner, “Cryptanalysis of a system based on twisted Reed-Solomon codes,”Des. Codes Cryptogr., vol. 88, no. 7, pp. 1285–1300, 2020

work page 2020
[21]

New MDS and self-dual generalized Roth-Lempel codes as well as their deep holes,

F. Li, R. Jiang, and Y . Liu, “New MDS and self-dual generalized Roth-Lempel codes as well as their deep holes,”Des. Codes Cryptogr., vol. 93, no. 11, pp. 5079–5096, 2025. 22

work page 2025
[22]

On the subset sum problem over finite fields,

J. Li and D. Wan, “On the subset sum problem over finite fields,”Finite Fields Appl., vol. 14, no. 4, pp. 911–929, 2008

work page 2008
[23]

Properties and decoding of twisted GRS codes and their extensions,

Y . Li, M. F. Ezerman, H. Lao, and S. Ling, “Properties and decoding of twisted GRS codes and their extensions,”arXiv preprint, 2025. [Online]. Available: https://arxiv.org/abs/2508.02382

work page arXiv 2025
[24]

A family of linear codes that are either non-GRS MDS codes or NMDS codes,

Y . Li, Z. Sun, and S. Zhu, “A family of linear codes that are either non-GRS MDS codes or NMDS codes,”IEEE Trans. Commun., vol. 73, no. 12, pp. 13073–13086, 2025

work page 2025
[25]

Covering radii and deep holes of two classes of extended twisted GRS codes and their applications,

Y . Li, S. Zhu, and Z. Sun, “Covering radii and deep holes of two classes of extended twisted GRS codes and their applications,”IEEE Trans. Inf. Theory, vol. 71, no. 5, pp. 3516–3530, 2025

work page 2025
[26]

Two new classes of Hermitian self-orthogonal non-GRS MDS codes and their applications,

G. Luo, X. Cao, M. F. Ezerman, and S. Ling, “Two new classes of Hermitian self-orthogonal non-GRS MDS codes and their applications,” Adv. Math. Commun., vol. 16, no. 4, pp. 921–933, 2022

work page 2022
[27]

On propagation rules for entanglement-assisted quantum codes,

G. Luo, L. Sok, M. F. Ezerman, and S. Ling, “On propagation rules for entanglement-assisted quantum codes,” inProc. 12th Int. Symp. Topics Coding (ISTC), Brest, France, 2023, pp. 1-5

work page 2023
[28]

The extended codes of NMDS codes,

Q. Ma, X. Kai, and S. Zhu, “The extended codes of NMDS codes,”Finite Fields Appl., vol. 114, 102844, 2026

work page 2026
[29]

The complexity of computing the covering radius of a code,

A. McLoughlin, “The complexity of computing the covering radius of a code,”IEEE Trans. Inf. Theory, vol. 30, no. 6, pp. 800–804, 1984

work page 1984
[30]

A study of deep holes in the first-order Reed-Muller codes,

M. Ozeki, “A study of deep holes in the first-order Reed-Muller codes,”Kyushu J. Math., vol. 66, no. 2, pp. 449–477, 2012

work page 2012
[31]

A construction of non-Reed-Solomon type MDS codes,

R. M. Roth and A. Lempel, “A construction of non-Reed-Solomon type MDS codes,”IEEE Trans. Inf. Theory, vol. 35, no. 3, pp. 655–657, 1989

work page 1989
[32]

Application of random relaying of partitioned MDS codeword block to persistent relay CSMA over random error channels,

K. Sakakibara and J. Taketsugu, “Application of random relaying of partitioned MDS codeword block to persistent relay CSMA over random error channels,” inProc. 5th Int. Congr. Ultra Modern Telecommun. Control Syst. Workshops (ICUMT), pp. 106–112, 2013

work page 2013
[33]

MDS codes, NMDS codes and their secret-sharing schemes,

D. E. Simos and Z. Varbanov, “MDS codes, NMDS codes and their secret-sharing schemes,” in18th Int. Conf. on Applications of Computer Algebra (ACA), Sofia, Bulgaria, 2012

work page 2012
[34]

The extended codes of a family of reversible MDS cyclic codes,

Z. Sun and C. Ding, “The extended codes of a family of reversible MDS cyclic codes,”IEEE Trans. Inf. Theory, vol. 70, no. 7, pp. 4808–4822, 2024

work page 2024
[35]

The extended codes of some linear codes,

Z. Sun, C. Ding, and T. Chen, “The extended codes of some linear codes,”Finite Fields Appl., vol. 96, 102401, 2024

work page 2024
[36]

The extended codes of projective two-weight codes,

Z. Sun, C. Ding, and T. Chen, “The extended codes of projective two-weight codes,”Discrete Math., vol. 347, no. 9, 114080, 2024

work page 2024
[37]

Binary informed source codes and index codes using certain near-MDS codes,

A. Thomas and B. Rajan, “Binary informed source codes and index codes using certain near-MDS codes,”IEEE Trans. Commun., vol. 66, no. 5, pp. 2181–2190, 2018

work page 2018
[38]

Onl-th NMDS codes,

H. Tong, W. Chen, and F. Yu, “Onl-th NMDS codes,”Chinese J. Electron., vol. 23, no. 3, pp. 454-457, 2014

work page 2014
[39]

When does the extended code of an MDS code remain MDS?

Y . Wu, C. Ding, and T. Chen, “When does the extended code of an MDS code remain MDS?”IEEE Trans. Inf. Theory, vol. 71, no. 1, pp. 263–272, 2025

work page 2025
[40]

More MDS codes of non-Reed-Solomon type,

Y . Wu, Z. Heng, C. Li, and C. Ding, “More MDS codes of non-Reed-Solomon type,”arXiv preprint, 2024. [Online]. Available: https://arxiv.org/pdf/2401.03391

work page arXiv 2024
[41]

Mutually disjoint Steiner systems from BCH codes,

Q. Yan and J. Zhou, “Mutually disjoint Steiner systems from BCH codes,”Des. Codes Cryptogr., vol. 92, no. 4, pp. 885–907, 2024

work page 2024
[42]

The weight distributions of three new classes of binary linear codes,

Y . Yong, “The weight distributions of three new classes of binary linear codes,”Cryptogr. Commun., vol. 17, no. 5, pp. 1627–1639, 2025

work page 2025
[43]

On deep holes of elliptic curve codes,

J. Zhang and D. Wan, “On deep holes of elliptic curve codes,”IEEE Trans. Inf. Theory, vol. 69, no. 7, pp. 4498–4506, 2023

work page 2023
[44]

Non-GRS type MDS and AMDS codes from extended TGRS codes

M. Zhang, S. Yang, and Y . Zheng, “Non-GRS type MDS and AMDS codes from extended TGRS codes,”arXiv preprint, 2026. [Online]. Available: https://arxiv.org/pdf/2604.05682

work page internal anchor Pith review Pith/arXiv arXiv 2026
[45]

A secret sharing scheme based on near-MDS codes,

Y . Zhou, F. Wang, Y . Xin, S. Luo, S. Qing, and Y . Yang, “A secret sharing scheme based on near-MDS codes,” inProc. IEEE Int. Conf. Netw. Inf. Dig. Control (IC-NIDC), pp. 833–836, 2009

work page 2009
[46]

The (+)-extended twisted generalized Reed-Solomon code,

C. Zhu and Q. Liao, “The (+)-extended twisted generalized Reed-Solomon code,”Discrete Math., vol. 347, no. 2, 113749, 2024

work page 2024
[47]

Efficient decoding of twisted GRS codes and Roth-Lempel codes,

R. Zhu and L. Jin, “Efficient decoding of twisted GRS codes and Roth-Lempel codes,”arXiv preprint, 2025. [Online]. Available: https://arxiv.org/pdf/2512.24217

work page arXiv 2025
[48]

On determining deep holes of generalized Reed-Solomon codes,

J. Zhuang, Q. Cheng, and J. Li, “On determining deep holes of generalized Reed-Solomon codes,”IEEE Trans. Inf. Theory, vol. 62, no. 1, pp. 199–207, 2016

work page 2016