{"id":"e772dcb9-a578-4447-a030-b3358f1b5484","arxiv_id":"2506.07609","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A partitioning theorem reduces t-deletion plus s-substitution correction to burst-deletion correction, yielding VT-based codes that match or slightly improve known redundancy bounds.","lead":"This paper introduces a partitioning method that turns overlapping deletion-and-substitution error balls into intersecting burst-deletion balls, then builds VT-syndrome codes from it. The framework unifies existing constructions and gives a slightly better q-ary code for one deletion plus one substitution.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma III.2's ℓ=t case is not proved as printed: the asserted inequality i_k ≥ j_{k+1} is impossible under i_1<j_1, and the block construction contains an empty interval and an ill-defined shift, leaving Theorem III.1's central reduction unverified pending a corrected proof.","rationale":"The paper's central mechanism is the reduction in Theorem III.1: overlapping t-deletion s-substitution balls can be partitioned into at most 2t+2s−1 equal-length subpairs with intersecting ≤t-burst-deletion balls. All Section IV code constructions (Theorems IV.20 and IV.23) invoke this theorem, and its deletion-only base is Lemma III.2. The reader is right to focus on this lemma. In the ℓ=t case the proof asserts i_k≥j_{k+1} after assuming i_1<j_1; this is impossible at k=1. The condition defining ℓ=t instead forces the opposite interleaving j_k≥i_{k+1}: for t=2, ℓ=t requires j_1≥i_2, and for general t the condition max{i_k,j_k}≥min{i_{k+1},j_{k+1}} propagates this. So the defect is in the core combinatorial relation, not in a minor bound. The block definition also contains an empty interval when p_k∈J and p_{k+1}∈I, and the shift t_k may be negative while being used as a lower index. These are concrete, locatable errors in the only proof of the lemma. Independently, the statement of Lemma III.2 is plausible, and small examples such as I={1,2}, J={3,4} for t=2 admit the claimed partition, so I would not reject the paper. The appropriate posture is conditional acceptance: the code-construction lemmas that assume the partition (Lemmas IV.19 and IV.22) are not independently verified, and the absence of a correct proof of Lemma III.2 means Theorem III.1 cannot yet be cited as a foundation. No data or reproducibility concerns apply, and the paper gives appropriate credit to prior VT-based constructions.","tokens_in":22572,"tokens_out":18022,"duration_ms":210307,"concrete_test":"Independently re-derive Lemma III.2's ℓ=t case for t=2 and t=3 using explicit interleavings, e.g., I={1,2}, J={3,4} for t=2 and I={1,2,4}, J={3,5,6} for t=3. Instantiate the printed block definition and the claimed equality x^(k)_{[t_k+1,n_k]}=y^(k)_{[1,n_k−t_k]}, testing both t_k=d_k and t_k=|d_k|; verify whether every block satisfies D_t(x^(k))∩D_t(y^(k))≠∅. Separately, exhaustively enumerate all binary x,y of length n≤10 with B_{t,0}(x)∩B_{t,0}(y)≠∅ for t≤3 and search over all partitions into at most 2t−1 equal-length blocks; if a counterexample exists, Theorem III.1 collapses, while if none exists, the gap is a proof-repair issue that can be resolved by rewriting Lemma III.2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Every construction in Section IV imports Theorem III.1, and Theorem III.1's deletion-only base is Lemma III.2. In the ℓ=t case of Lemma III.2's proof, the authors assume i_1<j_1 and then assert 'i_k ≥ j_{k+1}' for k∈[1,t−1]. This is false already for k=1, since i_1<j_1<j_2 gives i_1<j_2. The interleaving forced by ℓ=t is in the opposite direction: for t=2, ℓ=t requires j_1≥i_2, and the condition max{i_k,j_k} ≥ min{i_{k+1},j_{k+1}} propagates j_k≥i_{k+1}. So the error sits in the core combinatorial relation, not in a peripheral bound. The subsequent block definition is also under-specified: when p_k∈J and p_{k+1}∈I, it defines z^(k)=z[p_{k+1},p_{k+1}−1], which is the empty interval because p_{k+1}>p_k. The shift t_k is defined as min(|I∩[1,p_k]|−|J∩[1,p_k]|, n_k), which is negative whenever the prefix contains more J-deletions than I-deletions, yet it is used as the lower index in x^(k)_{[t_k+1,n_k]}; no orientation or absolute value is specified. Thus the claimed equality x^(k)_{[t_k+1,n_k]}=y^(k)_{[1,n_k−t_k]} is not demonstrated for the cases that actually occur. Since the authors provide no machine-checked proof and Lemma III.2 is the sole bridge from arbitrary t-deletion overlapping balls to burst-deletion balls, the central claim is not certifiable as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a partitioning technique intended to reduce the problem of correcting arbitrary t deletions with s substitutions to the simpler problem of correcting bursts of at most t deletions. The central claim, Theorem III.1, asserts that if two sequences have intersecting t-deletion s-substitution balls, then they can be partitioned into at most 2t+2s-1 sub-pairs whose ≤t-burst-deletion balls intersect. The proof relies on Lemma III.2 for the deletion-only case and Lemma III.3 for substitutions. Based on this framework, the authors construct VT-based codes for binary single- and two-deletion correction with multiple substitutions, and for q-ary single-deletion correction, with redundancy (s+1)(2s+1) log n + O(1) or (s+1)(2s+3) log n + O(1) bits. They also discuss limitations of existing approaches, propose t-good and t-valid sequence constraints for multiple deletions, and extend the partitioning to adjacent transpositions.","tokens_in":22957,"tokens_out":9374,"duration_ms":102140,"significance":"If Theorem III.1 is proven, the partitioning framework is a valuable unifying tool: it offers a systematic reduction from general deletion-substitution correction to burst-deletion correction, gives concise alternative proofs of several known constructions, and yields at least one improved redundancy result (q-ary single-deletion single-substitution codes with 6 log n + O(1) bits vs. the previous 7 log n + o(log n)). The redundancy calculations via the pigeonhole principle are explicit and check out. However, the proof of the central Lemma III.2 is not valid as printed: the ℓ=t case contains a reversed inequality, a malformed empty interval, and an ill-defined shift. Because every code construction in Sections IV and V imports Theorem III.1, the current manuscript does not yet establish its main claims. The paper does not provide machine-checked proofs, so the correctness depends entirely on repairing this lemma.","major_comments":[{"comment":"The proof asserts that assuming i_1 < j_1, it follows that i_k ≥ j_{k+1} for k∈[1,t−1]. This is false; for k=1 it would give i_1 ≥ j_2, contradicting i_1 < j_1 < j_2. The interleaving forced by the definition of ℓ (max(i_k,j_k) ≥ min(i_{k+1},j_{k+1}) for k<ℓ) gives the opposite type of relation, e.g., j_k ≥ i_{k+1} under the stated assumption. In addition, the block definition for p_k∈J and p_{k+1}∈I defines z^(k) = z[p_{k+1}, p_{k+1}−1], which is an empty interval, and t_k = min(|I∩[1,p_k]|−|J∩[1,p_k]|, n_k) can be negative while used as a lower index in x^(k)_{[t_k+1,n_k]}. These issues invalidate the proof of the ℓ=t case as written. Since Lemma III.2 is the sole basis for Theorem III.1, and all code constructions import Theorem III.1, this gap must be repaired before the paper's central claims can be accepted.","section":"§III, Lemma III.2 (ℓ=t case)"},{"comment":"The decoder for the code C is asserted rather than derived. The proof states that R_{2s+2}(F_b(F_b(x))) 'can be easily verified' to be recoverable from the corresponding block, and that F_b(x) can then be recovered by applying Theorem IV.20 via brute force, but no decoding algorithm or correctness proof is supplied. In particular, it is not shown that the deletion patterns in the three blocks (the data part, the syndrome part, and the repeated-syndrome part) can be handled independently, nor that the repetition code can be decoded when corrupted by deletions. The claimed O(n^{s+2}) decoding complexity is therefore not established. Please provide a complete decoding procedure and a proof of its correctness.","section":"§IV-D, Theorem IV.27"}],"minor_comments":[{"comment":"The term 'd(y)_dx' in Equation (7) is undefined; it should presumably be 'd(y)_{p_x}'.","section":"§IV-B2, Lemma IV.16, Eq. (7)"},{"comment":"The proof refers to 'm_k' in the product ∏_{k=0}^{2s}(m_k+1), but m_k is not defined; it should be n_k.","section":"§IV-C2, Theorem IV.23 proof"},{"comment":"The notation R_{2s+2}(·) is used without a formal definition; it should be stated that this is the (2s+2)-fold repetition code on the binary representation of the syndrome of the syndrome.","section":"§IV-D, Definition IV.26 and Theorem IV.27"},{"comment":"The ordering relation 'p_1 ≺ p_2 ≺ ... ≺ p_{2t}' for the sorted multi-set I∪J is not formally defined; please clarify how ties between i_k and j_k are broken.","section":"§III, Lemma III.2 proof"},{"comment":"The displayed identity 'Σ_{i=p_1}^{p_2+1} d(x)_i = Σ_{i=p_1}^{p_1+1} d(x)_i = q' is missing the summand d(x)_i in the first expression; it should read 'Σ_{i=p_1}^{p_2+1} d(x)_i = Σ_{i=p_1}^{p_1+1} d(x)_i = q' or similar.","section":"§V-B, Lemma V.8 proof"}],"recommendation":"major_revision","confidential_remarks":"The central lemma appears plausible and the framework is promising, but the submitted version contains a clear technical error in the proof of Lemma III.2 that cannot be ignored. I recommend asking the authors to supply a fully corrected proof of the ℓ=t case, with explicit block definitions and a well-defined shift, and to provide a detailed decoder for Theorem IV.27. If these are fixed, the paper could be a solid contribution to the deletion-correction literature."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper deserves a serious referee, but not a clean acceptance as posted. The core new idea, Theorem III.1, is genuinely useful: overlapping t-deletion s-substitution balls can be split into at most 2t+2s−1 equal-length subpairs whose burst-deletion balls intersect, and that reduction is what makes the VT constructions fall out cleanly. That is more than repackaging; it gives a structural explanation for why identity and differential VT syndromes behave differently, and it yields a small real improvement: a q-ary single-deletion single-substitution code with 6 log n redundancy versus the previous 7 log n baseline.\n\nThe paper also does honest work with the literature. The re-derivations of Levenshtein, Smagloy-Song, Nguyen, and Pi-Zhang are not dressed up as new, and the comparisons are benchmarks rather than circular inputs. There is no invented data or fitted parameters.\n\nThe soft spot is exactly where the stress-test note points. Lemma III.2, the deletion-only base of everything, is not proved as printed. In the ℓ=t case the authors assume i_1<j_1 and then assert i_k ≥ j_{k+1}; that is false already at k=1. The interleaving that actually follows from the definition of ℓ goes the other way. Then the block construction defines z^(k)=z[p_{k+1},p_{k+1}−1] as an empty interval in one case, and t_k can be negative while being used as a lower index without orientation. So the claimed equality x^(k)=y^(k) is not demonstrated for the cases that occur. Since Theorem III.1 and every Section IV construction import Lemma III.2, the central claim is not certifiable as written. This is a load-bearing flaw, but it looks repairable: the intended interleaving and block boundaries are recoverable from the surrounding argument, and the rest of the framework is coherent. The repetition-code decoder in Theorem IV.27 is asserted rather than derived; that is a smaller issue, and probably fixable.\n\nWho gets value: coding theorists working on VT-based deletion/substitution codes. The framework will be useful once Lemma III.2 is repaired. My recommendation: send it to peer review, but make the referee focus on Lemma III.2 before anything else; treat acceptance as conditional on a corrected proof. I would not cite the paper until that proof is out.","headline":"A genuinely useful partitioning framework for deletion-substitution correction, but the proof of its load-bearing lemma has printed errors that need fixing before the results are certifiable.","tokens_in":23455,"tokens_out":2882,"would_cite":false,"duration_ms":35919,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B60","94B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two sequences with overlapping t-deletion s-substitution balls can be cut into at most 2t+2s−1 subpairs whose burst-deletion balls intersect, reducing general deletion correction to burst-deletion correction.","keywords":["deletion-correcting codes","substitution-correcting codes","burst-deletion correction","Varshamov-Tenengolts syndromes","accumulative differential sequences","partitioning technique","redundancy bounds","DNA data storage"],"falsifier":"Fix t = 2, s = 0 and exhaustively check all binary pairs x, y of length n ≤ 20 with B_{2,0}(x) ∩ B_{2,0}(y) ≠ ∅: does every such pair admit a partition into at most 3 equal-length subpairs whose 2-burst-deletion balls intersect? The first pair that fails disproves Lemma III.2 and Theorem III.1; if none fails, the obstruction is only the printed proof's index relation, which would then need a corrected ordering.","tokens_in":22384,"feed_emoji":"✂️","tokens_out":15643,"duration_ms":149633,"temperature":0.7,"pith_summary":"The paper aims to prove that correcting t arbitrary deletions together with s substitutions can be reduced to correcting bursts of at most t deletions — a much easier error type for which good codes already exist. Its engine is a partitioning theorem: whenever two equal-length sequences have overlapping t-deletion s-substitution balls, both can be cut into at most 2t+2s−1 equal-length subpairs whose ≤t-burst-deletion balls intersect, so any burst-deletion-correcting construction built on Varshamov-Tenengolts (VT) weighted checksums extends to the full deletion-plus-substitution problem. On this foundation the paper builds binary codes for one deletion, and for two deletions, plus any number of substitutions, and q-ary codes for one deletion plus substitutions; the q-ary one-deletion one-substitution code uses 6 log n + O(1) redundancy bits, improving on the previous 7 log n + o(log n). The same framework explains why earlier VT-based methods stall exactly at two deletions in binary and one deletion in non-binary alphabets, and it extends at no extra cost to adjacent transpositions, the other main error type in DNA-storage channels.","feed_headline":"Partitioning turns scattered deletions into burst corrections","feed_subtitle":"A splitting rule lets burst-deletion code methods correct t deletions plus s substitutions.","key_machinery":"The machinery has three parts. First, the partition theorem (Theorem III.1) and its engine Lemma III.2, which interleaves the deleted positions of two sequences into a sorted list and cuts both sequences at those positions; each resulting block has equal length in both sequences and overlapping burst-deletion balls. Second, the sign-preserving number σ(z), the least number of substrings into which an integer sequence z splits with all non-zero entries in each substring sharing a sign, together with Lemma IV.4: an integer sequence whose VT syndromes VT_k(z) = Σ i^k z_i vanish for k = 0, …, σ(z)−1 is the all-zero sequence. Third, the two transforms that make burst deletions benign: the accumulative sequence f(x) (prefix sums of the symbols) and the accumulative differential sequence g(x) (prefix sums of the differences x_i − x_{i−1} mod q, i.e., the run string in binary). Lemmas IV.14 through IV.17 guarantee that after a burst deletion the difference of the transformed sequences is sign-constant, which is exactly what the sign-preserving number and the VT criterion need.","core_discovery":"The paper's central claim is Theorem III.1: for any t ≥ 1 and s ≥ 0, if two equal-length sequences x and y have intersecting t-deletion s-substitution balls, then both sequences admit a partition into the same number m ≤ 2t+2s−1 of equal-length blocks such that the ≤t-burst-deletion balls of each block pair intersect. The proof isolates the deletion-only case as an interleaving argument about the two deletion-position sets (Lemma III.2), then adds substitutions one at a time (Lemma III.3). The payoff is that every existing scheme for correcting bursts of at most t deletions becomes a scheme for t arbitrary deletions plus s substitutions: the paper realizes this with VT syndromes on accumulative sequences, producing binary single-deletion codes at (s+1)(2s+1) log n + O(1) bits, and on accumulative differential sequences, producing q-ary single-deletion codes at the same redundancy and binary two-deletion codes at (s+2)(2s+3) log n + O(1) bits, with the q-ary s=1 case (6 log n + O(1)) beating the previous 7 log n + o(log n) barrier.","pith_inferences":["The paper leaves implicit that the same partition-plus-commutativity recipe should extend the adjacent-transposition result to non-binary alphabets, provided a non-binary analogue of the transposition-commutativity fact exists; testing that extension is a direct next step.","Because the number of subpairs 2t+2s−1 directly sets the redundancy exponent, any sharper partition count for special cases (for instance the deletion-only case s = 0) would immediately lower the code redundancy; a computer search over small alphabets could hunt for pairs requiring fewer blocks than the general bound.","The t-valid construction of Section V-B is existence-only, since the authors note that valid sequences are too scarce to give practical redundancy; finding an efficient encoder that maps arbitrary q-ary strings into the valid class would convert it into a usable code — the analogue of the marker techniques that already exist for binary t-good sequences.","The sign-alternating counterexamples in Remarks IV.15 and IV.18 point to a general criterion the paper does not state: a VT construction on a given transform succeeds for a deletion pattern precisely when the transformed difference stays sign-constant on every block of the partition; formulating and testing that criterion could predict which error classes a transform can handle before constructing"],"forward_implications":["Any pair of sequences with overlapping t-deletion s-substitution balls splits into at most 2t+2s−1 equal-length subpairs with intersecting ≤t-burst-deletion balls (Theorem III.1), so burst-deletion correction is the only primitive needed for the general problem.","Binary single-deletion s-substitution codes achieve (s+1)(2s+1) log n + O(1) redundancy, matching the known bounds of the corresponding VT constructions with a shorter proof (Theorem IV.20).","Binary two-deletion s-substitution codes achieve (s+2)(2s+3) log n + O(1) redundancy, and q-ary single-deletion s-substitution codes achieve (s+1)(2s+1) log n + O(1); at s = 1 the q-ary bound is 6 log n + O(1), improving on the 7 log n + o(log n) syndrome-compression constructions (Theorems IV.23, Remark IV.24).","Because deletions, substitutions, and adjacent transpositions commute in binary alphabets, the same binary codes correct t deletions with s substitutions and adjacent transpositions at no extra redundancy (Theorem A.1).","The failure patterns in Remarks IV.15 and IV.18 explain the known barriers for VT methods — two deletions in binary and one deletion in non-binary for original sequences, three deletions in binary and two in non-binary for differential sequences — and the t-good and t-valid constructions (Theorems V.3 and V.9) remove those barriers at the price of redundancy."],"supporting_citations":[{"why":"Supplies the identity-function VT construction for a single deletion that the paper's accumulative-sequence code reproduces at s = 0.","marker":"[7]"},{"why":"Supplies the differential-function construction for a burst of at most two deletions that the accumulative-differential constructions generalize.","marker":"[8]"},{"why":"The single-deletion single-substitution code whose redundancy the paper's construction matches at s = 1 with a simpler proof.","marker":"[23]"},{"why":"The systematic multi-deletion multi-substitution code whose redundancy the paper matches for s ≥ 1, again with a simpler proof.","marker":"[21]"},{"why":"The q-ary differential VT codes for one deletion that the paper's q-ary construction generalizes to s substitutions.","marker":"[11]"},{"why":"The binary run-string codes for two deletions plus substitutions that the paper's binary two-deletion code coincides with at s = 1 and reproves more concisely.","marker":"[13]"},{"why":"The t-deletion codes built from VT syndromes on sequences with spaced ones, which the paper revisits as its t-good construction.","marker":"[15]"},{"why":"The commutativity of deletions and adjacent transpositions in binary alphabets, which the appendix relies on to extend the partition argument.","marker":"[6]"}],"fun_headline_variants":["Partition Trick Converts Scattered Deletions to Burst Errors","Burst-Deletion Codes Repurposed via Partitioning for Mixed Errors","Split Sequences to Turn Deletions and Substitutions into Burst Correctable","Partitioning Lifts Burst-Deletion Codes to Handle Substitutions Too"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole framework rests on a technical lemma about how two sets of deleted positions interleave; as printed, the lemma's proof asserts an ordering relation that contradicts the increasing order of those positions and defines one block as an empty interval, so unless that lemma can be repaired, the partitioning theorem and every code construction built on it lose their foundation.","fun_headline_variants_meta":{"raw":{"variants":["Partition Trick Converts Scattered Deletions to Burst Errors","Burst-Deletion Codes Repurposed via Partitioning for Mixed Errors","Split Sequences to Turn Deletions and Substitutions into Burst Correctable","Partitioning Lifts Burst-Deletion Codes to Handle Substitutions Too"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000331,"raw_usage":{"total_tokens":1845,"prompt_tokens":948,"completion_tokens":897,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":564,"completion_tokens_details":{"reasoning_tokens":816}},"tokens_in":564,"tokens_out":897,"duration_ms":10037,"temperature":1.0,"reasoning_tokens":816,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:31:17.882796+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix t = 2, s = 0 and exhaustively check all binary pairs x, y of length n ≤ 20 with B_{2,0}(x) ∩ B_{2,0}(y) ≠ ∅: does every such pair admit a partition into at most 3 equal-length subpairs whose 2-burst-deletion balls intersect? The first pair that fails disproves Lemma III.2 and Theorem III.1; if none fails, the obstruction is only the printed proof's index relation, which would then need a corrected ordering.","supporting_citations":[{"cited_title":"Asymptotically optimum binary code with correction for losses of one or two adjacent bits,","cited_arxiv_id":null,"evidence_quote":"Supplies the differential-function construction for a burst of at most two deletions that the accumulative-differential constructions generalize."},{"cited_title":"Systematic codes correcting multiple-deletion and multiple-substitution errors,","cited_arxiv_id":null,"evidence_quote":"The systematic multi-deletion multi-substitution code whose redundancy the paper matches for s ≥ 1, again with a simpler proof."},{"cited_title":"A new version ofq-ary Varshamov-Tenengolts codes with more efficient encoders: the differential VT codes and the differential shifted VT codes,","cited_arxiv_id":null,"evidence_quote":"The q-ary differential VT codes for one deletion that the paper's q-ary construction generalizes to s substitutions."},{"cited_title":"On optimalk-deletion correcting codes,","cited_arxiv_id":null,"evidence_quote":"The t-deletion codes built from VT syndromes on sequences with spaced ones, which the paper revisits as its t-good construction."},{"cited_title":"Codes in the Damerau distance for deletion and adjacent transposition correction,","cited_arxiv_id":null,"evidence_quote":"The commutativity of deletions and adjacent transpositions in binary alphabets, which the appendix relies on to extend the partition argument."}],"review_version":1}