REVIEW 3 major objections 5 minor 2 cited by
Reed-Solomon Codes Against Insertions and Deletions: Full-Length and Rate-$1/2$ Codes
T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read 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…
desk verdict 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. 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 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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [§3.2, Proposition 2 and Claim 2] 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.
- [§3.3, proof of Theorem 2] 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.
- [Preliminaries, Lemma 3] 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.
minor comments (5)
- [Table 1] 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.
- [Theorem 1 statement] 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.
- [Proof of Theorem 3] In the running-time analysis, the sentence 'since k=Θ(q^4)' should read 'since q=Θ(k^4)'.
- [After Proposition 1] 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.
- [Proof of Theorem 2] 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.
Circularity Check
No significant circularity: Theorem 1's counting argument rests on external algebraic lemmas and standard probabilistic bounds, not on self-referential definitions or fitted parameters.
full rationale
The paper's core claims (Theorems 1, 2, and 3) are derived from the definition of longest common subsequence, the half-Singleton bound (Theorem 4), Lemma 2 from [11], Lemma 3 from [30], and the Schwartz-Zippel lemma. None of these inputs is defined in terms of the paper's conclusions. Lemma 2 is a previously published, parameter-free algebraic necessary condition for an RS code to fail insdel correction; although reference [11] shares an author with the present paper (R. Con), the paper does not cite [11] for the target result itself or for any uniqueness or optimality claim. The counting argument in Proposition 2 uses Lemma 2 only as a black-box criterion and then bounds the number of orderings satisfying that criterion; this is ordinary derivation, not circularity. Likewise, Theorem 2 uses union bounds, the Schwartz-Zippel lemma, and a determinant-nonzero claim from [1], all external and with assumptions that do not include the target conclusion. Section 4 is a constructive inductive existence proof with a polynomial-time algorithm; there are no fitted parameters renamed as predictions. The suspected error in Claim 2 identified by the skeptic is a correctness concern: if the tail bound is indeed off by an exponential factor, then Theorem 1's proof is invalid as written, but an invalid bound does not make the derivation equivalent to its inputs. Under the circularity criteria, the paper is self-contained against external benchmarks and exhibits no self-referential reduction, so the appropriate score is 0.
Assumptions & free parameters
assumptions (6)
- domain assumption Lemma 2 from [11]: an RS code fails to correct n-ℓ insdel errors iff there exist increasing I,J of length ℓ with d_H(I,J) ≥ ℓ-k+1 and rank(V_{k,ℓ,I,J}(α)) < 2k-1.
- standard math Schwartz-Zippel lemma
- standard math Stirling's approximation
- domain assumption Half-Singleton bound (Theorem 4, [29])
- domain assumption Lemma 3 from [30, Lemma 4.10] for k=2 (AGL characterization)
- domain assumption Non-zero determinant of top (2k-1)x(2k-1) submatrix of V is a non-zero polynomial of degree < k^2 ([1, Prop 18])
Cite this review
Pith. "Pith review of Reed-Solomon Codes Against Insertions and Deletions: Full-Length and Rate-$1/2$ Codes." pith.science (2026). https://pith.science/paper/KMEAMYPV
@misc{pith2026250111371,
author = {Pith},
title = {Pith review of: Reed-Solomon Codes Against Insertions and Deletions: Full-Length and Rate-$1/2$ Codes},
year = {2026},
howpublished = {\url{https://pith.science/paper/KMEAMYPV}},
note = {Machine review of arXiv:2501.11371}
}
abstract
The performance of Reed--Solomon codes (RS codes, for short) in the presence of insertion and deletion errors has attracted growing attention in recent literature. In this work, we further study this intriguing mathematical problem, focusing on two regimes. First, we study the question of how well full-length RS codes perform against insertions and deletions. For 2-dimensional RS codes, we provide a complete characterization of codes that cannot correct even a single insertion or deletion. Furthermore, we prove that for sufficiently large field size~$q$, nearly all full-length $2$-dimensional RS codes can correct up to $(1 - \delta)q$ insertion and deletion errors for any $0 < \delta < 1$. Extending beyond the 2-dimensional case, we show that for any $k \ge 2$, there exists a full-length $k$-dimensional RS code capable of correcting $q / (10k)$ insertion and deletion errors, provided $q$ is large enough. Second, we focus on rate $1/2$ RS codes that can correct a single insertion or deletion error. We present a polynomial-time algorithm that constructs such codes over fields of size $q = \Theta(k^4)$. This result matches the existential bound given in \cite{con2023reed}.
Forward citations
Cited by 2 Pith papers
-
Linear List Decodable Edit-Correcting Codes with Rate Approaching $1$
For every small eta, explicit binary linear list-decodable codes correct an eta fraction of insertions and deletions with rate 1-O(eta^(1/4)) and polynomial-time encoding and decoding.
-
Decoding Insertions/Deletions via List Recovery
Any (ρ, 2ρn+1, L)-list-recoverable code is a (ρ, L)-list-decodable insdel code, yielding the first polynomial-time insdel decoder for [n,k] Reed-Solomon codes with k > 2.
Reference graph
Works this paper leans on
-
[11]
R. Con, Z. Guo, R. Li, and Z. Zhang, “Random Reed-Solomon codes achieve the half-singleton bound for insertions and deletions over linear-sized alphabets,”arXiv preprint arXiv:2407.07299, 2024
arXiv 2024
-
[1]
Reed Solomon codes against adversarial insertions and deletions,
R. Con, A. Shpilka, and I. Tamo, “Reed Solomon codes against adversarial insertions and deletions,” IEEE Transactions on Information Theory, vol. 69, no. 5, pp. 2991–3000, 2023
work page 2023
-
[2]
An overview of capacity results for synchronization channels,
M. Cheraghchi and J. Ribeiro, “An overview of capacity results for synchronization channels,”IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 3207–3232, 2020
work page 2020
-
[3]
Synchronization strings and codes for insertions and deletions - A survey,
B. Haeupler and A. Shahrasbi, “Synchronization strings and codes for insertions and deletions - A survey,”IEEE Trans. Inf. Theory, vol. 67, no. 6, pp. 3190–3206, 2021. [Online]. Available: https://doi.org/10.1109/TIT.2021.3056317
arXiv 2021
-
[4]
Traitor tracing for shortened and corrupted fingerprints,
R. Safavi-Naini and Y. Wang, “Traitor tracing for shortened and corrupted fingerprints,” inACM work- shop on Digital Rights Management. Springer, 2002, pp. 81–100
work page 2002
-
[5]
Deletion correcting using generalized Reed-Solomon codes,
Y. Wang, L. McAven, and R. Safavi-Naini, “Deletion correcting using generalized Reed-Solomon codes,” inCoding, Cryptography and Combinatorics. Springer, 2004, pp. 345–358. RS CODES AGAINST INSERTIONS AND DELETIONS: FULL-LENGTH AND RATE-1/2 CODES 19
work page 2004
-
[6]
Construction of deletion correcting codes using generalized Reed– Solomon codes and their subcodes,
D. Tonien and R. Safavi-Naini, “Construction of deletion correcting codes using generalized Reed– Solomon codes and their subcodes,”Designs, Codes and Cryptography, vol. 42, no. 2, pp. 227–237, 2007
work page 2007
-
[7]
T. D. Duc, S. Liu, I. Tjuawinata, and C. Xing, “Explicit constructions of two-dimensional Reed-Solomon codes in high insertion and deletion noise regime,”IEEE Transactions on Information Theory, vol. 67, no. 5, pp. 2808–2820, 2021
work page 2021
Show all 32 references
-
[8]
On 2-dimensional insertion-deletion Reed-Solomon codes with optimal as- ymptotic error-correcting capability,
S. Liu and I. Tjuawinata, “On 2-dimensional insertion-deletion Reed-Solomon codes with optimal as- ymptotic error-correcting capability,”Finite Fields and Their Applications, vol. 73, p. 101841, 2021
2021
-
[9]
Optimal two-dimensional Reed–Solomon codes correcting insertions and deletions,
R. Con, A. Shpilka, and I. Tamo, “Optimal two-dimensional Reed–Solomon codes correcting insertions and deletions,”IEEE Transactions on Information Theory, 2024
2024
-
[10]
Optimal RS codes and GRS codes against adversarial insertions and deletions and optimal constructions,
J. Liu, “Optimal RS codes and GRS codes against adversarial insertions and deletions and optimal constructions,”IEEE Transactions on Information Theory, 2024
2024
-
[12]
Binary codes capable of correcting deletions, insertions, and reversals,
V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals,” inSoviet physics doklady, vol. 10, 1966, pp. 707–710
1966
-
[13]
Codes which correct single asymmetric errors (in Russian),
R. Varshamov and G. Tenengolts, “Codes which correct single asymmetric errors (in Russian),”Au- tomatika i Telemkhanika, vol. 161, no. 3, pp. 288–292, 1965
1965
-
[14]
Codes correcting two deletions,
R. Gabrys and F. Sala, “Codes correcting two deletions,”IEEE Transactions on Information Theory, vol. 65, no. 2, pp. 965–974, 2018
2018
-
[15]
Two deletion correcting codes from indicator vectors,
J. Sima, N. Raviv, and J. Bruck, “Two deletion correcting codes from indicator vectors,”IEEE transac- tions on information theory, vol. 66, no. 4, pp. 2375–2391, 2019
2019
-
[16]
Efficient low-redundancy codes for correcting multiple deletions,
J. Brakensiek, V. Guruswami, and S. Zbarsky, “Efficient low-redundancy codes for correcting multiple deletions,”IEEE Transactions on Information Theory, vol. 64, no. 5, pp. 3403–3410, 2017
2017
-
[17]
On optimal k-deletion correcting codes,
J. Sima and J. Bruck, “On optimal k-deletion correcting codes,”IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 3360–3375, 2020
2020
-
[18]
Optimal codes for the q-ary deletion channel,
J. Sima, R. Gabrys, and J. Bruck, “Optimal codes for the q-ary deletion channel,” in2020 IEEE Inter- national Symposium on Information Theory (ISIT). IEEE, 2020, pp. 740–745
2020
-
[19]
Explicit two-deletion codes with redundancy matching the existential bound,
V. Guruswami and J. H ˚ astad, “Explicit two-deletion codes with redundancy matching the existential bound,”IEEE Transactions on Information Theory, vol. 67, no. 10, pp. 6384–6394, 2021
2021
-
[20]
Explicit construction of q-ary 2-deletion correcting codes with low redundancy,
S. Liu, I. Tjuawinata, and C. Xing, “Explicit construction of q-ary 2-deletion correcting codes with low redundancy,”IEEE Transactions on Information Theory, 2024
2024
-
[21]
Synchronization strings: Codes for insertions and deletions approaching the Singleton bound,
B. Haeupler and A. Shahrasbi, “Synchronization strings: Codes for insertions and deletions approaching the Singleton bound,”Journal of the ACM, vol. 68, no. 5, pp. 1–39, 2021
2021
-
[22]
Improved bounds for codes correcting insertions and deletions,
K. Yasunaga, “Improved bounds for codes correcting insertions and deletions,”Designs, Codes and Cryptography, pp. 1–12, 2024
2024
-
[23]
Bounds for deletion/insertion correcting codes,
V. I. Levenshtein, “Bounds for deletion/insertion correcting codes,” inProceedings IEEE International Symposium on Information Theory (ISIT). IEEE, 2002, p. 370
2002
-
[24]
On linear and cyclic codes for correcting deletions,
K. A. Abdel-Ghaffar, H. C. Ferreira, and L. Cheng, “On linear and cyclic codes for correcting deletions,” in2007 IEEE International Symposium on Information Theory (ISIT). IEEE, 2007, pp. 851–855
2007
-
[26]
Coordinate-ordering-free upper bounds for linear insertion-deletion codes,
H. Chen, “Coordinate-ordering-free upper bounds for linear insertion-deletion codes,”IEEE Transactions on Information Theory, vol. 68, no. 8, pp. 5126–5132, 2022
2022
-
[27]
Strict half-singleton bound, strict direct upper bound for linear insertion-deletion codes and optimal codes,
Q. Ji, D. Zheng, H. Chen, and X. Wang, “Strict half-singleton bound, strict direct upper bound for linear insertion-deletion codes and optimal codes,”IEEE Transactions on Information Theory, vol. 69, no. 5, pp. 2900–2910, 2023
2023
-
[28]
New dimension-independent upper bounds on linear insdel codes,
C. Xie, H. Chen, L. Qu, and L. Liu, “New dimension-independent upper bounds on linear insdel codes,” Advances in Mathematics of Communications, vol. 18, no. 6, pp. 1575–1589, 2024
2024
-
[29]
Efficient linear and affine codes for correcting insertions/deletions,
K. Cheng, V. Guruswami, B. Haeupler, and X. Li, “Efficient linear and affine codes for correcting insertions/deletions,”SIAM Journal on Discrete Mathematics, vol. 37, no. 2, pp. 748–778, 2023
2023
-
[30]
Bounds and constructions for insertion and deletion codes,
S. Liu and C. Xing, “Bounds and constructions for insertion and deletion codes,”IEEE Transactions on Information Theory, vol. 69, no. 2, pp. 928–940, 2023
2023
-
[31]
Mitzenmacher and E
M. Mitzenmacher and E. Upfal,Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. [Online]. Available: https://doi.org/10.1017/ CBO9780511813603
2005
-
[32]
Probabilistic algorithms for sparse polynomials,
R. Zippel, “Probabilistic algorithms for sparse polynomials,” inEUROSAM, 1979, pp. 216–226
1979
-
[33]
Fast probabilistic algorithms for verification of polynomial identities,
J. T. Schwartz, “Fast probabilistic algorithms for verification of polynomial identities,”J. ACM, vol. 27, no. 4, pp. 701–717, 1980. [Online]. Available: http://doi.acm.org/10.1145/322217.322225
1980
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.