Pith. sign in

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 →

arxiv 2411.14779 v1 pith:EIJGI2JV submitted 2024-11-22 cs.IT math.IT

classification cs.ITmath.IT MSC 94B0594B2711B1311T71
keywords MDScodesnon-Reed-SolomonSchursquarespolynomialevaluationarithmeticprogressionsfinitefieldszero-sum-freesets
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's aim is to produce MDS codes—codes meeting the Singleton bound on error correction—that are not equivalent to Reed-Solomon codes, a rare and actively sought class. The construction evaluates a k-dimensional space of polynomials spanned by monomials x^i for i in a fixed set I at n field points T; the code is MDS precisely when no nonzero polynomial in that space has k roots inside T. The authors show by counting that for sufficiently large fields such a T always exists for any non-arithmetic-progression I, and they prove the resulting code is non-RS by showing its Schur square has dimension at least 2k. Explicit point sets are then given for specific I, converting the avoidance condition into combinatorial requirements such as 'no k-subset of T sums to zero,' which yields code lengths more flexible than earlier non-RS MDS constructions.

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.

Watch

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

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

  • 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.
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

1 major / 4 minor

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)
  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)
  1. [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.
  2. [References] Reference [13] is cited only as 'arxiv' without an arXiv identifier or publication details; please complete the bibliographic entry.
  3. [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.
  4. [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

0 steps flagged · score 1.0 of 10

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 0 free parameters · 3 assumptions · 0 invented entities

No free parameters are fitted to data; the constructions are explicit and the only inputs are the field and the chosen exponent set I. The paper relies on standard results: the Singleton bound, the product Singleton bound for Schur squares of MDS codes, and the additive combinatorics lemma |I+I| ≥ 2|I|-1 with equality only for arithmetic progressions. These are stated in the preliminaries. No new entities are postulated.

assumptions (3)
  • standard math Singleton bound and the fact that the dual of an MDS code is MDS
    Used throughout to identify MDS codes (Section II-A).
  • 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
    Used in Proposition III.1 to lower-bound the Schur square exponent set size.
  • standard math Product Singleton bound for Schur squares of MDS codes: dim(C*2) ≥ min{2k-1,n}
    Used in Section II-C to motivate the non-RS criterion and to guarantee the Schur square dimension is at least 2k-1.

how reviews work

0 comments
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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

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

  1. On subcodes of the generalized Reed-Solomon codes

    cs.IT 2025-07 conditional novelty 6.0 of 10

    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.

  2. 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.

  3. Shelby: Decentralized Storage Designed to Serve

    cs.DC 2025-06 conditional novelty 5.0 of 10

    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.

  4. Some constructions of non-generalized Reed-Solomon MDS Codes

    cs.IT 2025-06 conditional novelty 5.0 of 10

    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

25 extracted references · 24 canonical work pages · cited by 4 Pith papers

  1. [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

  2. [2]

    Beelen, S

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

  3. [3]

    Beelen, M

    P . Beelen, M. Bossert, S. Puchinger and J. Rosenkilde n´ e Nielsen, Structural properties of twisted Reed-Solomon codes with applications to code-based cryptography, 2018 IEEE International Symposium on Information Theory (ISIT), V ail, CO, USA, pp. 946–950, 2018

  4. [4]

    Beelen, S

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

  5. [5]

    Blaum and R

    M. Blaum and R. M. Roth, On lowest density MDS codes , IEEE Trans. Inf. Theory, vol. 45, no. 1, pp. 46–59, Jan. 1999

  6. [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

  7. [7]

    Cramer, I

    R. Cramer, I. B. Damgrd, and J. B. Nielsen, Secure Multipa rty Computation and Secret Sharing, Cambridge University Press, 2015

  8. [8]

    Randriambololona, On Products and Powers of Linear Codes Under Component-wise Multiplication, in AGCT, 2015

    H. Randriambololona, On Products and Powers of Linear Codes Under Component-wise Multiplication, in AGCT, 2015

Show all 25 references
  1. [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

  2. [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

  3. [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

  4. [12]

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

  5. [13]

    F. Li. Y . Chen, H. Chen and Y . Niu, Non-Reed-Solomon type cyclic MDS codes, arxiv

  6. [14]

    Lin and C

    S. Lin and C. Xing, Coding Theory: A First Course, Cambri dge, U.K.: Cambridge Univ. Press, 2008

  7. [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

  8. [16]

    M. B. Nathanson, Additive Number Theory: Inverse Probl ems and the Geometry and Sumsets, Graduate Texts in Mathematics, vol. 165, Springer, 1996

  9. [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

  10. [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

  11. [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

  12. [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

  13. [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

  14. [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

  15. [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

  16. [24]

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

  17. [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

Pith tools

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