{"id":"eaae676e-ef2c-41f0-a319-0ab3842110d0","arxiv_id":"2501.11371","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Full-length 2D Reed-Solomon codes: almost all orderings correct a linear fraction of insdel errors, and rate-1/2 codes correcting a single insdel error exist over fields of size Θ(k^4).","lead":"This paper studies how Reed-Solomon codes behave when symbols are inserted into or deleted from codewords, rather than just corrupted. It shows that for two-dimensional full-length codes, almost all orderings of the field elements yield codes that can correct a linear fraction of such errors, and gives a fast construction of rate-1/2 codes over small fields.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 2's upper bound is off by an exponential factor: as printed, the bad-ordering fraction is not small, so Theorem 1's proof is invalid without a correction.","rationale":"After reading the paper in good faith, the strongest claim is Theorem 1. The proof's stochastic counting is the most load-bearing step. The reader's weakest_assumption was Lemma 2 from [11], a black-box algebraic criterion; that is a legitimate concern, but the paper's own Claim 2 has a concrete algebraic error that is more immediate and falsifiable. The displayed upper bound for the bad-orderings tail is wrong by an exponential factor because the factor (q-1)q^{s-delta q-1} * prod(q-i) is Theta(q^{2(s-delta q)}) while the proof bounds it by q^{s-delta q+2}. Numerically, for q=100, delta=0.5, the s=q term alone is about 3e93, far above the claimed about 2.5e7. This is not merely cosmetic: it invalidates the proof of Theorem 1 as written. However, the proof of Claim 1 in Proposition 2 suggests the intended count is q(q-1) * prod(q-i), without the extra q^{s-l-1}, so the error is very likely a fixable typo rather than a false conclusion. Theorem 2 and Theorem 3 do not depend on this step. The reader correctly recommended CONDITIONAL; our analysis strengthens the need for that condition by showing that the typo in Proposition 2 propagates into the core estimate of Theorem 1. We therefore see no reason to move the verdict: it stays CONDITIONAL, with the concrete check above needed to confirm the corrected bound.","tokens_in":22741,"tokens_out":29594,"duration_ms":245798,"concrete_test":"Recompute Claim 2's left-hand side at q=100, delta=0.5, s=q using the printed formula: verify it exceeds q^2(4e^2/(delta^2 q))^{delta q}. Then redo the same tail bound with the corrected count from Claim 1, q(q-1) * prod_{i=0}^{s-delta q-1}(q-i) (no extra q^{s-delta q-1}), and check whether the bound q^2(4e^2/(delta^2 q))^{delta q} still holds; if it does, the flaw is a fixable typo, otherwise Theorem 1's proof is unsound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1 rests on Claim 2, which bounds the fraction of 'bad' orderings. As printed, Claim 2 is false. The displayed tail sum contains the factor (q-1)q^{s-delta q-1} * prod_{i=0}^{s-delta q-1}(q-i), but the proof replaces this with q^{s-delta q+2}. For t = s - delta q >= 3, that factor is (q-1)q^{t-1} * q(q-1)...(q-t+1), which is Theta(q^{2t}), not q^{t+2}. For example, at q=100, delta=0.5, the s=q term alone is about 3e93, while the claimed bound q^2(4e^2/(delta^2 q))^{delta q} is about 2.5e7. So the inequality in Claim 2 fails by many orders of magnitude. The root cause is a propagated typo: Proposition 2's display has an extra q^{s-l-1} relative to the proof's own count in Claim 1, which is q(q-1) * prod_{i=0}^{s-l-1}(q-i). With the extra factor removed, the exponent in Claim 2 should be q^{s-delta q+1}, and the conclusion likely holds. But as written, Theorem 1 is unproven.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Reed–Solomon codes against insertion and deletion errors in two regimes. For full-length RS codes (n=q), it characterizes all orderings of F_q for which the 2-dimensional code fails to correct a single insdel error; proves that for large q, a (1-ε) fraction of all orderings yield RS_{q,2} codes correcting (1-δ)q insdel errors; and proves, by a probabilistic argument, the existence of a full-length RS_{q,k} code correcting q/(10k) insdel errors. In the second part, the paper gives an induction-based polynomial-time construction of rate-1/2 RS codes correcting a single insdel error over fields of size q=O(k^4), matching the existential bound of Con–Shpilka–Tamo. The authors explicitly note that the lower bound in Proposition 1 is loose because potential equivalences are overcounted, and they leave explicit constructions for the random-ordering result as an open problem.","tokens_in":22984,"tokens_out":23150,"duration_ms":207536,"significance":"If the results stand, they are substantial: Theorem 1 would show that a uniformly random full-length 2-dimensional RS code corrects a linear number of insdel errors with high probability, a regime not previously established; Theorem 3 provides the first polynomial-time construction of rate-1/2 RS codes matching the existential field-size bound. The paper builds on previously published algebraic criteria (Lemma 2, Schwartz–Zippel, the half-Singleton bound) rather than introducing circular definitions, and the counting strategy is natural. However, the printed proofs contain several load-bearing display inconsistencies in the central estimates; these are readily fixable, but until corrected the theorems are not fully supported as written.","major_comments":[{"comment":"The displayed sum in Proposition 2 contains the factor q^{s-ℓ-1}, whereas the counting proof (in particular, the paragraph after Claim 1 establishing the bound (q-s)!·q·(q-1)·∏(q-i)) yields the factor q·(q-1) instead. This is not merely cosmetic: in Claim 2 the printed inequality (q-1)q^{s-δq-1}∏_{i=0}^{s-δq-1}(q-i) ≤ q^{s-δq+2} is false. Writing t=s-δq, the left-hand side has degree 2t in q while the right-hand side has degree t+2; for t≥3 the inequality fails by a factor q^{t-2}. For example, at q=100, δ=1/2, s=q, the printed summand is enormously larger than the claimed upper bound q^2(4e^2/(δ^2 q))^{δq}. Since Theorem 1's proof relies on Claim 2, the printed proof does not establish the theorem. Replacing the displayed q^{s-ℓ-1} by q, matching Claim 1, makes Claim 2's estimate valid and the proof goes through.","section":"§3.2, Proposition 2 and Claim 2"},{"comment":"The proof defines ℓ=q-q/(16k) in its first sentence, but the subsequent estimate (k^2/q)^{ℓ/(4k)} (q choose ℓ)^2 ≤ (k^2/q)^{q/(5k)} (eq/(q/(10k)))^{q/(5k)} requires ℓ=q-q/(10k), as the text itself states: 'which implies that ℓ=q-q/(10k)'. With the printed value ℓ=q-q/(16k), the compensation (q choose ℓ)=(q choose q/(10k)) used to obtain (10ek)^{q/(5k)} is unavailable, and the displayed bound does not follow. The proof is repaired by defining ℓ=q-q/(10k) from the start; for k≥2 this still gives ℓ/(4k)>q/(5k), so the subsequent chain of inequalities is valid.","section":"§3.3, proof of Theorem 2"},{"comment":"The statement of Lemma 3 has an off-by-two error. The condition on the right, f_{a,b}(α_I)≠α_J for all increasing I,J∈[n]^ℓ with d_H(I,J)≥ℓ-1, rules out common subsequences of length ℓ; hence it gives LCS≤ℓ-1 and therefore ED(C)≥2n-2ℓ+2, not ED(C)=2n-2ℓ. The later use in Lemma 6, where n=4 and ℓ=3 is used to obtain the optimal distance 4, is consistent with the corrected statement 'insdel distance at least 2n-2ℓ+2' (with equality implied by the half-Singleton bound in that application). The lemma statement should be corrected, or the notion of 'insdel distance' used there should be clarified.","section":"Preliminaries, Lemma 3"}],"minor_comments":[{"comment":"The entries for q=5 and q=7 do not match the lower bound of Proposition 1: the proposition gives at least 1/6 ≈ 0.167 for q=5 and at least 115/120 ≈ 0.958 for q=7, while the table reports 0.333 and 0.967. Since the text says the table evaluates the bound in Proposition 1, either the table reports exact proportions from a stronger analysis or the values should be corrected.","section":"Table 1"},{"comment":"The theorem states 'Let ε, δ > 0' but the meaningful range is 0<δ<1; for δ≥1 the expression (1-δ)q is non-positive and the statement is not what the proof addresses.","section":"Theorem 1 statement"},{"comment":"In the running-time analysis, the sentence 'since k=Θ(q^4)' should read 'since q=Θ(k^4)'.","section":"Proof of Theorem 3"},{"comment":"The note that the lower bound may overcount bad equivalence classes is correct and appropriately caveats the bound; however, the table should be labeled consistently as either the lower bound or an exact count.","section":"After Proposition 1"},{"comment":"The phrase 'agree on at most k-1 coordinates' is used without relating it to Lemma 2's condition d_H(I,J)≥ℓ-k+1; relating the two explicitly would improve readability and avoid confusion with Hamming agreements of the index sequences.","section":"Proof of Theorem 2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is promising and the main results appear correct after straightforward corrections of the displayed estimates. The referee's main concern is that the printed versions of Proposition 2/Claim 2 and of Theorem 2's ℓ parameter are internally inconsistent and load-bearing; both are local fixes, but the authors should be asked to correct them and to re-verify the resulting constants. No concerns about novelty or attribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth your time. This paper makes two genuine advances: it fully characterizes the bad orderings for full-length 2-dimensional RS codes, and it gives a polynomial-time construction of rate-1/2 RS codes correcting a single insdel error over q = Θ(k^4), matching the existential bound. Theorem 1's almost-all result for linear insdel errors is the kind of clean statement that moves the subfield forward. The inductive counting in Section 4 is clever, and the paper is honest about what it does not do (no explicit good ordering for full-length codes, no extension below rate 1/2).\n\nThe stress-test note about Claim 2 is correct as far as the printed text goes: the displayed sum in Proposition 2 contains q^{s-ℓ-1}, while the proof's own count is q(q-1) times the same product. With that extra factor, the Claim 2 inequality indeed fails for s-ℓ ≥ 3, so the written proof of Theorem 1 is invalid. But this is a propagated typo, not a structural gap. Replace the display with the proof's q(q-1) factor and Claim 2's bound q^{s-δq+2} follows from the same Stirling estimate. I read this as a minor-revision fix, not a fatal flaw.\n\nOther soft spots are also minor. Table 1's proportions for q=5 and q=7 are inconsistent with Proposition 1's formula. Theorem 2's claim that the number of disjoint submatrices m is at least ℓ/4k is justified in three sentences and deserves a real proof or reference. And Theorem 3's proof says \"since k = Θ(q^4)\" when it means q = Θ(k^4); the running-time claim still works because q is polynomial in k, but the sentence is wrong. The paper leans on Lemma 2 from the co-authored preprint [11] as a black box; that lemma is the algebraic foundation for Theorems 1 and 2, so the results are conditional on it, but nothing here suggests the lemma is shaky.\n\nBottom line: the central contributions hold up, and the errors are presentation-level. This deserves a serious referee and, after the typos and the terse m ≥ ℓ/4k step are cleaned up, publication. I would cite it and bring it to our reading group.","headline":"Solid insdel-RS paper: the k=2 characterization and the rate-1/2 construction are real progress, and the scary Claim 2 issue is a fixable typo, not a broken proof.","tokens_in":23555,"tokens_out":7518,"would_cite":true,"duration_ms":63336,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B35","94B65","11T71"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that full-length Reed–Solomon codes, whose evaluation points can be freely permuted, are almost always highly resistant to insertions and deletions: nearly every 2-dimensional code corrects a linear number of such errors…","keywords":["Reed–Solomon codes","insertions and deletions","insdel errors","full-length codes","half-Singleton bound","rate-1/2 codes","evaluation orderings","rank criterion"],"falsifier":"For a small prime power q (say 7, 8, and 9), exhaustively enumerate all q! orderings and test which ones make RS_{q,2}(α) fail to correct a single deletion; if any failing ordering is not affinely equivalent to (0,1,θ,…,$θ^{{q−2}}$), its reverse, or (0,1,…,q−1) with q prime, the complete characterization of Lemma 4 is wrong. For the linear-fraction claim, compute the exact proportion of orderings that fail to correct (1−δ)q errors for the largest q one can enumerate and compare with the exponential decay bound $q^{2}$($4e^{2}$/($δ^{2}$ q))^{δ q} asserted in Claim 2.","tokens_in":22506,"feed_emoji":"🧬","tokens_out":13478,"duration_ms":111097,"temperature":0.7,"pith_summary":"This paper asks whether Reed–Solomon (RS) codes, the standard algebraic codes for correcting substitutions, can also withstand insertions and deletions (insdel errors), where symbols are lost or injected and word length changes. The answer it defends is strongly positive when the code is full-length: for dimension 2, it completely lists the 'bad' orderings of the field that fail to correct even a single insdel error, and proves that for large fields almost all orderings yield codes correcting (1−δ)q insdel errors for any fixed δ>0. For arbitrary dimension k it proves that a full-length RS code correcting q/(10k) insdel errors exists once q is large enough. In the rate-1/2 regime it gives a polynomial-time algorithm constructing [2k,k]_q RS codes over fields of size q=O($k^{4}$) that correct a single insdel error, matching the best existential field-size bound known.","feed_headline":"Almost every 2-D Reed-Solomon code defeats insertions/deletions","feed_subtitle":"Ordering the field is the trick: 2-D RS codes correct a linear number of insertions/deletions; rate-1/2 codes are poly-time constructible.","key_machinery":"The load-bearing object is the evaluation matrix V_{k,ℓ,I,J}(X), whose rows pair the monomials 1,X,…,$X^{{k−1}}$ evaluated at two increasing index sequences I,J of length ℓ. Lemma 2 (quoted from the companion paper [11]) says that if RS_{n,k}(α) cannot correct n−ℓ insdel errors, then some such matrix with d_H(I,J) ≥ ℓ−k+1 has rank below 2k−1. All of the paper's counting and existence statements flow from this reduction: Theorem 1 counts orderings for which every relevant V_{2,ℓ,I,J}(α) has full rank; Theorem 2 constructs disjoint families of (2k−1)×(2k−1) submatrices so that singularities become independent Schwartz–Zippel events; and the rate-1/2 induction of Theorem 3 rules out, for each pair of new evaluation points, the at most 5(k−1)^2 algebraic configurations in which two normalized polynomials agree on a long common subsequence.","core_discovery":"The paper's central claim is that the insdel performance of a full-length Reed–Solomon code is governed almost entirely by the ordering of the evaluation points, and that almost every ordering is good. Concretely, every permutation α of F_q that makes RS_{q,2}(α) unable to correct a single deletion is affinely equivalent to one of three explicitly listed sequences — a cyclic subgroup orbit, its reversal, or the natural ordering (0,1,…,q−1) when q is prime. For any 0<δ<1, the fraction of orderings for which the code fails to correct (1−δ)q insdel errors drops exponentially in q, so at least 1−ε of all full-length 2-dimensional RS codes correct any linear number of insdel errors once q exceeds a threshold depending on δ and ε. For general k, a probabilistic argument using disjoint-variable submatrices and Schwartz–Zippel shows that some ordering of F_q yields an RS_{q,k} code correcting q/(10k) errors whenever q ≥ $e^{{6k}}$·($10ek^{3}$). Finally, the paper constructs optimal rate-1/2 codes: the smallest field for a [4,2] RS code correcting a single insdel error is F_7, and induction on the dimension yields a deterministic polynomial-time construction of [2k,k]_q codes with q=O($k^{4}$) that meet the half-Singleton bound.","pith_inferences":["The rank-criterion method should transfer to generalized RS codes and to shortened or subcodes: the same V_{k,ℓ,I,J} matrices appear whenever evaluation points are chosen, so the counting technique likely gives 'almost all' statements for those families too.","The O(k^4) field size in Theorem 3 is an artifact of the induction's worst-case counting; for small k the true minimal field size can be computed exactly (e.g., q=7 for k=2), and a data-driven guess is that the exponent drops below 4 for larger k.","Explicitly constructing the good orderings promised by Theorem 1 is left open; derandomizing the Schwartz–Zippel/union-bound proof (e.g., via small-biased sets or pseudorandom permutations) is a natural next step.","The three bad-order classes of Lemma 4 are all orbits of a cyclic subgroup of AGL(1,q) — the natural ordering is but one instance — suggesting that insdel resilience is tied to the affine geometry of the field, a connection worth making precise."],"forward_implications":["A uniformly random full-length 2-dimensional RS code over a large field corrects any linear number of insdel errors with overwhelming probability.","For every dimension k, full-length RS codes exist that correct q/(10k) insdel errors, so the ordering of F_q is never the bottleneck for linear resilience when q is large.","Rate-1/2 RS codes meeting the half-Singleton bound exist over fields of size O(k^4) and can be constructed in polynomial time, demystifying the existential bounds of [1].","Because insdel correction depends so strongly on the ordering, the evaluation vector itself becomes a design tool: rearranging the same field elements can change a code from correcting nothing to correcting a linear fraction of errors."],"supporting_citations":[{"why":"Supplies Lemma 2, the rank-deficiency criterion that reduces insdel correction to the rank of V_{k,ℓ,I,J}(α); the counting and probabilistic arguments of Sections 3.2–3.3 rely on it.","marker":"[11]"},{"why":"Gives the existential O((n/(2k−1))^{2k^2}) field-size bound that Theorem 3 matches, and Proposition 18, the non-zero determinant used inside the proof of Theorem 2.","marker":"[1]"},{"why":"Provides Lemma 3 (and Lemma 4.10) characterizing when a 2-dimensional RS code reaches insdel distance 2n−2ℓ, used in the single-insdel characterization and in verifying the [4,2] base case.","marker":"[30]"},{"why":"States the half-Singleton bound (Theorem 4) that fixes the rate-1/2 target and defines what optimality means in Section 4.","marker":"[29]"},{"why":"Pioneered deletion-correcting generalized RS codes and the induction-based approach that Section 4 refines for proper RS codes.","marker":"[5]"},{"why":"Shows the Ω(n^3) field-size lower bound for [n,2] codes correcting n−3 deletions, which frames why the q=7 base case is extremal.","marker":"[9]"}],"fun_headline_variants":["Almost all 2-D RS codes fix linear indels","Field order makes RS codes insdel-resilient","Poly-time rate-1/2 RS codes for single indel","2-D RS: almost every ordering corrects indels","RS codes: random ordering beats indels"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the lemma, taken as a black box from a companion paper, that a code which fails to correct n−ℓ insdel errors must contain two index sequences I,J for which the evaluation matrix V_{k,ℓ,I,J}(α) drops rank; if that implication were false, the 'almost all orderings' claim for dimension 2 and the existence results for general k would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Almost all 2-D RS codes fix linear indels","Field order makes RS codes insdel-resilient","Poly-time rate-1/2 RS codes for single indel","2-D RS: almost every ordering corrects indels","RS codes: random ordering beats indels"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001686,"raw_usage":{"total_tokens":6761,"prompt_tokens":1104,"completion_tokens":5657,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":720,"completion_tokens_details":{"reasoning_tokens":5579}},"tokens_in":720,"tokens_out":5657,"duration_ms":38056,"temperature":1.0,"reasoning_tokens":5579,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:23:28.221376+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a small prime power q (say 7, 8, and 9), exhaustively enumerate all q! orderings and test which ones make RS_{q,2}(α) fail to correct a single deletion; if any failing ordering is not affinely equivalent to (0,1,θ,…,$θ^{{q−2}}$), its reverse, or (0,1,…,q−1) with q prime, the complete characterization of Lemma 4 is wrong. For the linear-fraction claim, compute the exact proportion of orderings that fail to correct (1−δ)q errors for the largest q one can enumerate and compare with the exponential decay bound $q^{2}$($4e^{2}$/($δ^{2}$ q))^{δ q} asserted in Claim 2.","supporting_citations":[{"cited_title":"Reed Solomon codes against adversarial insertions and deletions,","cited_arxiv_id":null,"evidence_quote":"Gives the existential O((n/(2k−1))^{2k^2}) field-size bound that Theorem 3 matches, and Proposition 18, the non-zero determinant used inside the proof of Theorem 2."},{"cited_title":"Bounds and constructions for insertion and deletion codes,","cited_arxiv_id":null,"evidence_quote":"Provides Lemma 3 (and Lemma 4.10) characterizing when a 2-dimensional RS code reaches insdel distance 2n−2ℓ, used in the single-insdel characterization and in verifying the [4,2] base case."},{"cited_title":"Efficient linear and affine codes for correcting insertions/deletions,","cited_arxiv_id":null,"evidence_quote":"States the half-Singleton bound (Theorem 4) that fixes the rate-1/2 target and defines what optimality means in Section 4."},{"cited_title":"Deletion correcting using generalized Reed-Solomon codes,","cited_arxiv_id":null,"evidence_quote":"Pioneered deletion-correcting generalized RS codes and the induction-based approach that Section 4 refines for proper RS codes."},{"cited_title":"Optimal two-dimensional Reed–Solomon codes correcting insertions and deletions,","cited_arxiv_id":null,"evidence_quote":"Shows the Ω(n^3) field-size lower bound for [n,2] codes correcting n−3 deletions, which frames why the q=7 base case is extremal."}],"review_version":1}