{"id":"9cb03958-3ff5-4c8a-8c44-66af2514a507","arxiv_id":"2411.14779","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New framework and explicit constructions yield non-Reed-Solomon MDS codes with lengths up to roughly q/k, far more flexible than earlier O(q^{1/k}) bounds.","lead":"This paper builds a general framework for constructing maximum distance separable (MDS) codes that are not equivalent to Reed-Solomon codes, by choosing polynomial spaces and evaluation points carefully. It gives explicit new families of such codes with more flexible lengths than previous constructions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition III.1 infers dim(C⋆2)≥2k from |I+I|≥2k without proving injectivity of the evaluation map; for n=2k the kernel can be nonzero, so the non-RS conclusion is not established.","rationale":"The reader's weakest_assumption correctly identifies the missing injectivity argument. This is the single most load-bearing point because the non-RS claim for the general framework depends entirely on the Schur square dimension being at least 2k. The explicit constructions in Sections V and VI inherit the same gap whenever n=2k: they verify the MDS condition via k-subset sums but never verify that the Schur square evaluation map is injective. A concrete failure mode exists in principle: for I={0,...,k-2,k} and n=2k, the monic polynomial vanishing on T has degree 2k and its x^{2k-1} coefficient is the negative of the sum of T; when that sum is zero, the polynomial belongs to span{x^i: i∈I+I} and lies in the kernel. The MDS condition (T_k∩S=∅) is compatible with total sum zero, since for this I it only forbids zero k-subset sums. I did not find an independent flaw in the counting arguments in Section IV or in the n>2k explicit cases; those appear sound, and adding the hypothesis n>max(I+I) or proving full rank would fix the gap. Hence the CONDITIONAL verdict is appropriate; the concern does not change the reader's recommendation.","tokens_in":17445,"tokens_out":15643,"duration_ms":149411,"concrete_test":"For q=2^5, k=3, I={0,1,3}, enumerate the 16 elements of the form 1+u with u in a 4-dimensional F_2-subspace U of F_32. Select a 6-element subset T with ∑_{u∈T} u=0 (possible since U has dimension 4) and verify that every 3-subset of T has nonzero sum (automatic from constant coefficient 1). Compute the rank of the 6×6 matrix with rows (1, α, α², α³, α⁴, α⁶) for α∈T. If the rank is below 6, the evaluation map on span{x^i : i∈I+I} has a kernel, and Proposition III.1's inference from |I+I|≥2k to dim C⋆2≥2k is invalid. Conversely, if the rank is always 6, the gap is not realized by this family; a more general search over all T satisfying T_k∩S=∅ with n=2k would still be needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is in the proof of Proposition III.1: once the MDS property is established, the proof asserts that for a non-arithmetic progression I, Lemma II.1 gives |I+I|≥2k, and therefore the Schur square C⋆2(T,I)=ev_T(span{x^i : i∈I+I}) has dimension at least 2k. The dimension of the image is the rank of the evaluation map, not |I+I|; the map can have a nontrivial kernel. Injectivity is automatic only when n>max(I+I), which is not stated. For n=2k and I={0,1,...,k-2,k}, we have I+I={0,1,...,2k-2,2k}, so max(I+I)=2k. If T is a 2k-element set with ∑_{α∈T} α=0, then P_T(x)=∏_{α∈T}(x-α) has no x^{2k-1} term, lies in span{x^i : i∈I+I}, and vanishes on T, forcing dim C⋆2≤2k-1. The hypothesis T_k∩S=∅ does not prevent this: for this I it is equivalent to all k-subset sums of T being nonzero, which can hold while the total sum is zero. Hence Proposition III.1's non-RS conclusion, and therefore Theorem IV.3 and the n=2k cases of the explicit constructions, rest on an unproven rank assumption. The codes may still be non-RS, but the proof as written does not establish it.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17758,"tokens_out":11211,"duration_ms":105878,"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":[{"comment":"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.","section":"III, Proposition III.1"}],"minor_comments":[{"comment":"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.","section":"V, Theorems V.12 and VI.3"},{"comment":"Reference [13] is cited only as 'arxiv' without an arXiv identifier or publication details; please complete the bibliographic entry.","section":"References"},{"comment":"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.","section":"I, Remark I.6"},{"comment":"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.","section":"V, Proposition V.4"}],"recommendation":"major_revision","confidential_remarks":"To the editor: The main gap is real but localized. The authors should be asked to either strengthen Proposition III.1 by requiring n > max(I+I) or to treat the case n=2k separately. If the boundary case can be handled, the paper would be publishable. The novelty relative to [6] and [2] appears adequate, and the paper is generally well organized and self-contained."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper delivers what it advertises: a clean general framework for building non-RS MDS codes by choosing a monomial set I and an evaluation set T, plus explicit families with lengths linear in q for prime fields and flexible lengths beyond twisted RS or Roth-Lempel. The weight-numerator reduction (Proposition V.4) is the genuinely new idea, and it earns its keep: BCH and Hamming codes give concrete codes with n > 2k in the interesting range. The counting argument for existence is straightforward and self-contained; no fitted parameters, no circularity. The citation pattern looks fine.\n\nThe soft spot is real, and the stress-test hits it precisely. In Proposition III.1, from |I+I| ≥ 2k the paper concludes dim(C⋆2) ≥ 2k without proving that the evaluation map on span{x^i : i∈I+I} is injective. That is only automatic when n > max(I+I). For I = {0,1,…,k−2,k}, max(I+I)=2k, so when n=2k the map can have a kernel: if the sum of all elements of T is zero, the polynomial P_T(x) = ∏(x−α) lies in the span and vanishes on T, forcing dim(C⋆2) ≤ 2k−1. The hypothesis T_k∩S=∅ excludes k-subset sums being zero but does not exclude the total sum being zero. So the proof of non-RS-ness for the n=2k cases, and for the general existence theorem when the inequality admits n=2k, is incomplete as written. This is a proof gap, not a counterexample; the codes may well be non-RS, but the argument does not show it.\n\nImportantly, the gap is confined to the boundary n=2k. For n ≥ 2k+1, n > max(I+I), so the evaluation map is injective and the Schur square argument is sound. The headline results — lengths linear in q from Corollary V.2 for large n, and the Hamming/BCH examples — all have n > 2k, so they stand. The flaw affects the borderline cases and the full generality of Theorems IV.3.\n\nThe paper is worth a serious referee. The framework is useful, the explicit families are new, and the gap is likely fixable by stating the injectivity condition or treating n=2k separately. I would accept it for peer review, ask the authors to fix the boundary case, and cite the n>2k results in my own work while waiting for the general statement to be repaired.","headline":"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.","tokens_in":18296,"tokens_out":7817,"would_cite":true,"duration_ms":125220,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B05","94B27","11B13","11T71"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["MDS codes","non-Reed-Solomon codes","Schur squares","polynomial evaluation codes","arithmetic progressions","finite fields","zero-sum-free sets"],"falsifier":"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.","tokens_in":17232,"feed_emoji":"🧮","tokens_out":15937,"duration_ms":146454,"temperature":0.7,"pith_summary":"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.","feed_headline":"Non-RS MDS codes from a monomial-avoidance trick","feed_subtitle":"Avoiding k-term zero-sums yields MDS codes that escape Reed-Solomon equivalence, with more flexible lengths.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies Lemma II.1, the sumset bound |I+I| ≥ 2ℓ−1 with equality only for arithmetic progressions, which drives the Schur-square dimension claim.","marker":"[16]"},{"why":"Introduces twisted Reed-Solomon codes and states the fact that MDS codes with k<3 or n−k<3 are RS, motivating the 3 ≤ k ≤ n/2 range.","marker":"[2]"},{"why":"Gives earlier non-RS MDS codes from algebraic curves with length O(q^{1/k}); the present paper compares and in some ranges improves the length.","marker":"[6]"},{"why":"Provides the Roth-Lempel non-RS MDS construction and the values of R(k,q) used to get length q/2 codes in Theorems V.14.","marker":"[19]"},{"why":"Supplies the coding-theory background (BCH codes, extended Hamming codes, parity-check matrices) behind the weight-numerator construction and the explicit examples.","marker":"[14]"},{"why":"Gives the lower bound on Schur squares of MDS codes and the context for using Schur products as a tool.","marker":"[8]"},{"why":"Constructs cyclic non-RS MDS codes, used as a comparison point for length restrictions n | (q−1).","marker":"[13]"}],"fun_headline_variants":["Non-RS MDS from Schur-square condition","Sumset trick yields non-RS MDS","New non-RS MDS with flexible lengths","Schur squares for non-RS MDS"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Non-RS MDS from Schur-square condition","Sumset trick yields non-RS MDS","New non-RS MDS with flexible lengths","Schur squares for non-RS MDS"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001064,"raw_usage":{"total_tokens":4469,"prompt_tokens":963,"completion_tokens":3506,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":579,"completion_tokens_details":{"reasoning_tokens":3446}},"tokens_in":579,"tokens_out":3506,"duration_ms":23898,"temperature":1.0,"reasoning_tokens":3446,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:57:36.207594+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies Lemma II.1, the sumset bound |I+I| ≥ 2ℓ−1 with equality only for arithmetic progressions, which drives the Schur-square dimension claim."},{"cited_title":"Beelen, S","cited_arxiv_id":null,"evidence_quote":"Introduces twisted Reed-Solomon codes and states the fact that MDS codes with k<3 or n−k<3 are RS, motivating the 3 ≤ k ≤ n/2 range."},{"cited_title":"Chen, Many non-Reed-Solomon type MDS codes from arbitrary genus a lgebraic curves, IEEE Trans","cited_arxiv_id":null,"evidence_quote":"Gives earlier non-RS MDS codes from algebraic curves with length O(q^{1/k}); the present paper compares and in some ranges improves the length."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Roth-Lempel non-RS MDS construction and the values of R(k,q) used to get length q/2 codes in Theorems V.14."},{"cited_title":"Lin and C","cited_arxiv_id":null,"evidence_quote":"Supplies the coding-theory background (BCH codes, extended Hamming codes, parity-check matrices) behind the weight-numerator construction and the explicit examples."},{"cited_title":"Randriambololona, On Products and Powers of Linear Codes Under Component-wise Multiplication, in AGCT, 2015","cited_arxiv_id":null,"evidence_quote":"Gives the lower bound on Schur squares of MDS codes and the context for using Schur products as a tool."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Constructs cyclic non-RS MDS codes, used as a comparison point for length restrictions n | (q−1)."}],"review_version":1}