REVIEW 1 major objections 4 minor 4 cited by
New families of non-Reed-Solomon MDS codes
T0 review · 1 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read This paper constructs new families of maximum-distance-separable (MDS) codes that are provably not equivalent to Reed-Solomon codes, by evaluating monomial spans at point sets chosen to avoid small root sets.
desk verdict A genuinely useful framework and explicit non-RS MDS families with a real proof gap at the n=2k boundary that does not affect the headline long-length results. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The operating pair is (I,T): the exponent set I = {i_1 < ... < i_k} and the evaluation set T ⊆ \mathbb{F}_q with |T| = n ≥ 2k. The code is C(T,I) = ev_T(V_I), with V_I = span_{\mathbb{F}_q}{x^i : i ∈ I}. The MDS condition is equivalent to the avoidance statement T_k ∩ S = ∅, where S collects every k-subset of \mathbb{F}_q that is the zero set of some nonzero polynomial in V_I. Non-RS status is certified by the Schur square $C^{{⋆2}}$(T,I) = ev_T(span{x^i : i ∈ I+I}), relying on the fact that a generalized Reed-Solomon code of dimension k ≤ n/2 has Schur-square dimension 2k−1. The engine is Lemma II.1: |I+I| ≥ 2ℓ−1 with equality exactly for arithmetic progressions, so a non-arithmetic progression I gives |I+I| ≥ 2k.
What would settle it
Take k=4, I = {0,1,2,4}, and search over finite fields for an 8-element evaluation set T with no 4-subset summing to zero (which makes C(T,I) MDS) but with the total sum of all 8 elements equal to zero. If such a T exists, the Schur square loses the missing exponent 7 and has dimension at most 7 < 8, contradicting the blanket non-RS claim of Proposition III.1.
Extended reading notes
Core claim
The central claim is that non-Reed-Solomon MDS codes arise systematically from evaluation codes C(T,I) = ev_T(span{x^i : i ∈ I}) whenever two conditions hold: every nonzero polynomial in the span has at most k−1 roots in T (making the code MDS), and the Schur square $C^{{⋆2}}$(T,I) = ev_T(span{x^i : i ∈ I+I}) has dimension at least 2k (making it non-RS for k ≤ n/2). For any non-arithmetic-progression I of size k, the sumset I+I has size at least 2k by additive number theory, and the paper asserts this forces the Schur-square dimension above 2k. Existence of an admissible T follows from the counting inequality in Theorem IV.3, while explicit construction is given for I = {0,1,...,k−2,k} and its generalizations, where the MDS condition reduces to keeping all k-subset sums (respectively r-th elementary symmetric sums) of T nonzero.
Load-bearing premise
The non-RS conclusion leans on the unstated assumption that no nonzero polynomial built from the sumset monomials x^i with i ∈ I+I vanishes on all n evaluation points; this injectivity is guaranteed only when n exceeds the largest exponent in I+I, and the paper does not prove it in general.
Editorial extensions
If this is right
- For any non-arithmetic-progression I with 3 ≤ k ≤ n/2, an [n,k] non-RS MDS code exists over \mathbb{F}_q whenever \binom{q}{n} > \frac{q^k-1}{q-1}\binom{m_I}{k}\binom{q-k}{n-k}, permitting length n = O(q^{1/k} m_I).
- For I = {0,1,...,k−2,k}, explicit codes exist over prime fields with n < p/k + (k+1)/2, and over extension fields with n up to about (p/k)p^t, lengths that are not subject to the divisibility constraints of twisted or cyclic non-RS codes.
- For q = 2^m, known Roth-Lempel values R(k,q) imply q-ary [q/2+1,3] and [q/2,k] non-RS MDS codes for odd k with 5 ≤ k ≤ q/4.
- If a q-ary code with no codewords of weight k exists, then a q^r-ary [n,k] non-RS MDS code exists; this yields concrete instances from extended Hamming and BCH codes.
Reading between the lines
- The paper's non-RS certificate through the Schur square assumes the evaluation map on span{x^i : i ∈ I+I} is injective on T; that is automatic when n > max(I+I), but for n ≤ max(I+I) it is an unproven premise, and testing n=2k cases would show whether an extra hypothesis is needed.
- The zero-sum-free sets T used here are close cousins of cap sets and weak sum-free sets in additive combinatorics, so bounds from that literature could sharpen the trade-off between length n and field size q beyond the counting estimate.
- The parity-check transfer in Proposition V.4 suggests a general recipe: start from any code with a gap in its weight enumerator at weight k, embed its columns into a larger field, and obtain a non-RS MDS code; exploring other weight-gap codes could give new parameter ranges.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a general framework for constructing [n,k] MDS codes over F_q by evaluating a k-dimensional space of monomials V_I = span{x^i : i∈I} on an n-element set T. The MDS condition is reduced to the combinatorial requirement T_k ∩ S = ∅, where S is the set of k-subsets of F_q that are contained in the zero set of some nonzero polynomial in V_I. For non-arithmetic progression exponent sets I, the authors claim that the resulting codes are non-Reed-Solomon by showing that the Schur square has dimension at least 2k, using the lower bound |I+I| ≥ 2k. Existence is established via a counting argument under a binomial inequality. Explicit constructions are given for I = {0,1,...,k-2,k} and generalizations, reducing the problem to avoiding zero k-subset sums or zero elementary symmetric sums; these yield lengths up to about q/2 in several cases and O(q^{1/k}) in others.
Significance. The framework is appealing, and the conversion of the MDS condition to a zero-sum combinatorics problem is elegant and likely reusable. The paper is self-contained, with no fitted parameters and no reliance on results that incorporate the target codes. The counting argument is transparent, and the explicit constructions appear genuinely new, improving on known length ranges in several parameter regimes, especially for prime fields. However, the proof of the non-RS property contains a gap at the boundary n=2k because the claimed Schur-square dimension requires injectivity of the evaluation map on I+I, a condition that is not always satisfied. This affects part of the stated parameter range, so the main claims are not yet fully established.
major comments (1)
- [III, Proposition III.1] The assertion that C⋆2(T,I) has dimension at least 2k because |I+I| ≥ 2k is missing a proof of injectivity of the evaluation map ev_T on span{x^i : i∈I+I}. The dimension of the image is the rank of ev_T, which can be strictly smaller than |I+I| if a nonzero polynomial in that span vanishes on all of T. This happens, for instance, for I = {0,1,...,k-2,k} and n=2k: if T is a 2k-element set with ∑_{α∈T} α = 0, then P_T(x)=∏_{α∈T}(x-α) has no x^{2k-1} term and therefore lies in span{x^i : i∈I+I}, while ev_T(P_T)=0. The hypothesis T_k ∩ S = ∅, which for this I is equivalent to all k-subset sums being nonzero, does not exclude the possibility that the total sum of T is zero. Hence the non-RS conclusion is not established for n=2k, and the same gap propagates to Theorem IV.3, Theorem IV.5, Proposition V.1, Corollary V.2, and Theorems V.12, V.14, V.15, VI.3, and VI.4 whenever they allow n=2k. The authors should either add the condition n > max(I+I) so that injectivity is automatic, or provide a separate argument covering the boundary case n=2k.
minor comments (4)
- [V, Theorems V.12 and VI.3] In the definition α_i = 1 + ∑_{i=1}^{m-1} a_{i,j}ζ^j, the summation index should be j rather than i to avoid reusing the outer index; the same typo appears in several places.
- [References] Reference [13] is cited only as 'arxiv' without an arXiv identifier or publication details; please complete the bibliographic entry.
- [I, Remark I.6] The claim that the Schur square of the Roth-Lempel code has a significantly smaller minimum distance than the codes constructed here would benefit from a proof or a precise citation.
- [V, Proposition V.4] The symbol A_k is used both for the number of weight-k codewords and, in Section III, for a k-subset of F_q; consider renaming one of these to avoid ambiguity.
Circularity Check
No significant circularity: the framework and explicit constructions are self-contained against external standards; the flagged Schur-square dimension inference in Proposition III.1 is an omitted proof (correctness gap), not a circular reduction.
full rationale
The paper's central derivation chain is self-contained. It defines C(T,I) as an evaluation code on the monomial space V_I, obtains the MDS property from the zero-set condition T_k∩S=∅ (S collects k-subsets of F_q that are zero sets of nonzero polynomials in V_I), and obtains the non-RS property from Lemma II.2, which is proved inside the paper using the standard fact that the Schur square of a GRS code has dimension 2k−1. The one load-bearing inference that could look circular is in the proof of Proposition III.1: "If I is a non-arithmetic progression, then the set I+I has cardinality at least 2k by Lemma II.1. Hence, the Schur square C⋆2(T,I) has dimension at least 2k." This is not a circular reduction: the dimension of the Schur square is a computed quantity, not a hypothesis, and the inference tacitly assumes the evaluation map ev_T is injective on span{x^i : i∈I+I}. That injectivity is neither stated nor proved (for n=2k it can fail when the evaluation points sum to zero), so Proposition III.1 contains an omitted proof step—a correctness gap that weakens Theorem IV.3 and the n=2k cases of the explicit theorems—but it does not define the conclusion into the premise, nor fit a parameter and rename it a prediction. The paper is also non-circular in its external inputs: Lemma II.1 is Nathanson's standard sumset bound; the product Singleton bound criterion is attributed to Mirandola–Zémor; and the constructed codes are checked against independent external benchmarks (BCH codes, extended Hamming codes, codetables.de listings) that are not fitted to the target non-RS MDS codes. The only self-citation, [14] (a textbook co-authored by C. Xing), supplies standard coding-theory facts (parity-check column independence, BCH/Hamming code parameters) and is not load-bearing for the novel existence or construction claims. Overall, the derivation does not reduce to its own inputs by construction, so the circularity score is low.
Assumptions & free parameters
assumptions (3)
- standard math Singleton bound and the fact that the dual of an MDS code is MDS
- standard math Lemma II.1 from additive number theory: for a set I of ℓ integers, |I+I| ≥ 2ℓ-1, with equality iff I is an arithmetic progression
- standard math Product Singleton bound for Schur squares of MDS codes: dim(C*2) ≥ min{2k-1,n}
Cite this review
Pith. "Pith review of New families of non-Reed-Solomon MDS codes." pith.science (2026). https://pith.science/paper/EIJGI2JV
@misc{pith2026241114779,
author = {Pith},
title = {Pith review of: New families of non-Reed-Solomon MDS codes},
year = {2026},
howpublished = {\url{https://pith.science/paper/EIJGI2JV}},
note = {Machine review of arXiv:2411.14779}
}
abstract
MDS codes have garnered significant attention due to their wide applications in practice. To date, most known MDS codes are equivalent to Reed-Solomon codes. The construction of non-Reed-Solomon (non-RS) type MDS codes has emerged as an intriguing and important problem in both coding theory and finite geometry. Although some constructions of non-RS type MDS codes have been presented in the literature, the parameters of these MDS codes remain subject to strict constraints. In this paper, we introduce a general framework of constructing $[n,k]$ MDS codes using the idea of selecting a suitable set of evaluation polynomials and a set of evaluation points such that all nonzero polynomials have at most $k-1$ zeros in the evaluation set. Moreover, these MDS codes can be proved to be non-Reed-Solomon by computing their Schur squares. Furthermore, several explicit constructions of non-RS MDS codes are given by converting to combinatorial problems. As a result, new families of non-RS MDS codes with much more flexible lengths can be obtained and most of them are not covered by the known results.
Forward citations
Cited by 4 Pith papers
-
On subcodes of the generalized Reed-Solomon codes
It characterizes self-duality and near-MDS status for one-codimensional subcodes of generalized Reed-Solomon codes for all r, and determines the dual codes for r=1,2,k-1.
-
Row-Column Twisted Reed-Solomon codes
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.
-
Shelby: Decentralized Storage Designed to Serve
Shelby is a decentralized storage protocol design that targets Web2-grade read performance using Clay codes, micropayments, a dedicated network backbone, and an 'audit-the-auditor' scheme.
-
Some constructions of non-generalized Reed-Solomon MDS Codes
Necessary and sufficient conditions are given for two extended evaluation-code families to be non-GRS MDS codes, and o-monomials are characterized by nonvanishing complete symmetric functions.
Reference graph
Works this paper leans on
-
[1]
Ball, On large subsets of a finite vector space in which every subset of basis size is a basis, J
S. Ball, On large subsets of a finite vector space in which every subset of basis size is a basis, J. Eur. Math. Soc., vol. 14, pp. 733–748, 2012
work page 2012
- [2]
- [3]
- [4]
-
[5]
M. Blaum and R. M. Roth, On lowest density MDS codes , IEEE Trans. Inf. Theory, vol. 45, no. 1, pp. 46–59, Jan. 1999
work page 1999
-
[6]
Chen, Many non-Reed-Solomon type MDS codes from arbitrary genus a lgebraic curves, IEEE Trans
H. Chen, Many non-Reed-Solomon type MDS codes from arbitrary genus a lgebraic curves, IEEE Trans. Inf. Theory, vol. 70, no. 7, pp. 4856–4864, Jul. 2024
work page 2024
- [7]
-
[8]
H. Randriambololona, On Products and Powers of Linear Codes Under Component-wise Multiplication, in AGCT, 2015
work page 2015
Show all 25 references
-
[9]
J. I. Kokkala, D. S. Krotov and R. J. Patric, On the classification of MDS Codes , IEEE Trans. Inf. Theory, vol. 61, pp. 6485–6492, 2015
2015
-
[10]
S. H. Dau, W. Song, Z. Dong, and C. Y uen, Balanced sparsest generator matrices for MDS codes, 2013 IEEE International Symposium on Information Theory, Istanbul, Turkey, pp. 1889–1893, 2013
2013
-
[11]
S. H. Dau, W. Song, and C. Y uen, On the existence of MDS codes over small fields with constrain ed generator matrices, 2014 IEEE International Symposium on Information Theory, H onolulu, HI, USA, pp. 1787–1791, 2014
2014
-
[12]
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error -Correcting Codes, Amsterdam, The Netherlands: Elsevier, 1977. 18
1977
-
[13]
F. Li. Y . Chen, H. Chen and Y . Niu, Non-Reed-Solomon type cyclic MDS codes, arxiv
-
[14]
Lin and C
S. Lin and C. Xing, Coding Theory: A First Course, Cambri dge, U.K.: Cambridge Univ. Press, 2008
2008
-
[15]
Mirandola, and G
D. Mirandola, and G. Z´ emor, Critical pairs for the product Singleton bound, IEEE Trans. Inf. Theory, vol. 61, no. 9, pp. 4928–4937, Sep. 2015
2015
-
[16]
M. B. Nathanson, Additive Number Theory: Inverse Probl ems and the Geometry and Sumsets, Graduate Texts in Mathematics, vol. 165, Springer, 1996
1996
-
[17]
Huang, Q
D. Huang, Q. Y ue Y . Niu, X. Li, MDS or NMDS self-dual codes from twisted generalized Reed-S olomon codes, Des. Codes Cryptogr., vol. 89, no. 9, pp. 2195–2209, 2022
2022
-
[18]
Liu and S
H. Liu and S. Liu, Construction of MDS twisted Reed-Solomon codes and LCD MDS c odes, Des. Codes Cryptogr., vol. 89, no. 9, pp. 2051–2065, 2021
2021
-
[19]
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, May 1989
1989
-
[20]
Serge, Curve raizionali normali e k-archi negli spazi finiti, Ann
B. Serge, Curve raizionali normali e k-archi negli spazi finiti, Ann. Mat. Pura Appl., vol. 39, pp. 357–378, Dec. 1955
1955
-
[21]
Sheekey, A new family of linear maximum rank distance codes, Adv
J. Sheekey, A new family of linear maximum rank distance codes, Adv. Math. Commun., vol. 10, pp. 475–488, 2016
2016
-
[22]
J. Sui, X. Zhu and X. Shi, MDS and near-MDS codes via twisted Reed-Solomon codes , Des. Codes Cryptogr., vol. 90, pp. 1937–1958, 2022
1937
-
[23]
J. Sui, Q. Y ue, X. Li and D. Huang, MDS, near MDS or 2-MDS self-dual codes via twisted Reed-Solomon code, IEEE Trans. Inf. Theory, vol. 68, no. 12, pp. 7832–7841, Dec. 2022
2022
-
[24]
Y . Wu, Z. Heng, C. Li and C. Ding, More MDS codes of non-Reed-Solomon type , arXiv:2401.03391
-
[25]
Y . Wu, J.Y . Hyun, Y . Lee, New LCD MDS codes of non-Reed-Solomon type, IEEE Trans. Inf. Theory, vol. 67, no. 8, pp. 5069–5078, Aug. 2021
2021
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.