{"id":"273c8fd4-810c-49c7-9528-39a274d4faea","arxiv_id":"2507.04797","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"New q-ary codes correcting bursts or localized deletions achieve redundancy log n + (t-1) log log n + O(1) when t < 2q, improving on prior best constructions.","lead":"The paper constructs new deletion-correcting codes that recover lost symbols in bursts, using a balance condition on the differences between adjacent symbols. The codes use less extra redundancy than previous best constructions, but only for bursts shorter than twice the alphabet size.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem IV.1 and V.1 invoke Lemma III.3 with t2=0 (and with t2=1 for t'=t−1 in V.1), a parameter regime Lemma III.3 explicitly excludes; the final correction step inside the located window is therefore unsupported.","rationale":"I read the paper as making two related existence claims: q-ary (≤t)-burst-deletion-correcting codes and t-localized-deletion-correcting codes with redundancy log n+(t−1)log log n+O(1), under the stated constraints on q and t. The position-estimation machinery—strong-(ℓ,ϵ)-locally-balanced differential sequences, the VT-type and L1-weight constraints, and the good-triple analysis of Lemmas III.4 and IV.1—is presented in detail and appears coherent. The counting argument in Lemma III.2 gives the needed density of codewords, and the redundancy accounting is consistent. The load-bearing weakness is exactly the final correction step inside the located window. Both Theorem IV.1 and Theorem V.1 explicitly rely on Lemma III.3, but that lemma is stated only for t1≥t2≥2. The paper never proves a P-bounded deletion-only (t2=0) or deletion-with-one-survivor (t2=1) code with redundancy log P+O(1). This is not a matter of disagreement with prior work; it is an internal gap between the cited lemma and the parameters used. The gap is plausibly fixable—known single-deletion VT-type codes and the construction in [19] may generalize—but as written the proof does not supply the missing ingredient. The encoder section also states that the q-ary generalizations of [31] are 'direct' and omits their proofs; that is a secondary weakness, since the code-existence theorems do not depend on the encoder, but it reinforces the need for a careful patch. I therefore agree with the reader's conditional verdict and do not see a reason to change it.","tokens_in":27582,"tokens_out":8141,"duration_ms":89331,"concrete_test":"Independently derive a P-bounded t'-burst-deletion-correcting code over Σ_q with redundancy log P + O_{q,t}(1) without invoking Lemma III.3 at t2=0 or t2=1. For example, check whether the cited [19, Corollary 3] actually covers t2=0 or t2=1; if it does not, construct f_{P,t',0}: Σ_q^n → {0,1}^{log P + O(1)} directly, e.g. via a VT-type constraint localized to the window. If no such construction can be supplied, or if it requires more than log P + O(1) redundancy, the final correction steps in Theorems IV.1 and V.1 are unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central code-existence proofs depend on a final correction step inside a located window of length P. In Theorem IV.1, the code is defined using f_{P,t',0} for each 2≤t'≤t, where f_{P,t',0} is said to be 'the function in Lemma III.3'. In Theorem V.1, the code uses f_{P,t,t−t'}, which becomes f_{P,t,0} when t'=t and f_{P,t,1} when t'=t−1. However, Lemma III.3 is stated only for integers t1≥t2≥2, and Definition III.2 itself requires 1≤t2≤t1. Thus neither f_{P,t',0} nor f_{P,t,1} is provided by the cited lemma. A burst of t' consecutive deletions is naturally a (t',0)-burst-error, or a (t'+1,1)-burst-error in the differential sequence, so the t2≥2 result does not apply without an additional reduction or a separate P-bounded deletion-only code with redundancy log P+O(1). The assertion 'By Lemma III.3, the code is a P-bounded t'-burst-deletion correcting code' therefore does not follow from the stated results. This is a fixable but load-bearing gap: unless such a code is derived, Theorems IV.1 and V.1 lack support for their final correction step, and the announced redundancy log n+(t−1)log log n+O(1) is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes new q-ary codes correcting bursts of at most t deletions and t-localized deletions, achieving redundancy log n + (t−1) log log n + O(1) for q ≥ 2, t < q (or even q, t < 2q). The construction selects codewords whose differential sequences are strong-(ℓ,ε)-locally-balanced and satisfies a VT-type constraint and an L1-weight constraint. The error-correction algorithm first estimates error positions within a short window, then invokes a P-bounded (t1,t2)-burst-error correcting code on the located window. The paper also provides an efficient encoder mapping arbitrary length-(n−2) sequences to length-n sequences with strong locally balanced differential sequences. The main technical novelty is a simpler position-estimation code that also corrects a single deletion.","tokens_in":27929,"tokens_out":20170,"duration_ms":187665,"significance":"If the technical gaps identified below are resolved, the redundancy improvement is real and meaningful: it saves one log log n factor for all q with t<q and extends to even q up to t<2q, and the position-estimation method is conceptually simpler than prior array-based or dense-sequence methods. The efficient encoder for strong locally balanced differential sequences appears to be new. The paper is well-structured and contains detailed proof sketches for the main lemmas, with external results from [19] and [31] used as black boxes.","major_comments":[{"comment":"Theorems IV.1 and V.1 invoke the function f_{P,t1,t2} of Lemma III.3 with t2=0 (and in Theorem V.1 also with t2=1). Specifically, Theorem IV.1 uses f_{P,t',0} for 2≤t'≤t, and Theorem V.1 uses f_{P,t,t−t'} with t−t'=0 for t'=t and t−t'=1 for t'=t−1. However, Lemma III.3 is stated only for integers t1≥t2≥2, and Definition III.2 also requires 1≤t2≤t1. No derivation is given for the cases t2=0 or t2=1. Consequently, the assertion 'By Lemma III.3, the code is a P-bounded ... code' in the final correction step of both theorems is not supported by the quoted lemma. The authors need to either extend Lemma III.3 to cover t2=0 and t2=1, or provide an alternative P-bounded code for deletion-only and single-symbol-replacement errors inside the located window, together with a proof.","section":"Lemma III.3; Theorems IV.1 and V.1"},{"comment":"After Claim 2, the proof states that the substring y'_{[j−ℓ+1,j]} contains y'_{i_s−∑_{r=1}^{s-1} t_r} for all 1≤s≤k. This does not follow from Claim 2. Claim 2 only gives j−i1 < ℓ−t'+t1, which yields an upper bound on j and implies j−ℓ+1 < i1, but it gives no lower bound on j. To cover the starts of all deleted blocks, one needs j ≥ i_k−∑_{r=1}^{k−1} t_r, which can be as large as i1+t−t'. Since j is chosen as the first (largest) index from the right satisfying (28), the proof must show that some such index exists in that range. As written, the located window could end before the later deleted blocks, and the subsequent correction step would fail. Please provide an argument that the scanning procedure yields a window covering all block starts.","section":"Theorem V.1, Step 3"}],"minor_comments":[{"comment":"The upper endpoint of the interval in Definition III.1 is written as (q+1)/2 + ε, but Lemma III.2, Claim 1, and Section VI all use (q−1)/2 + ε. Please correct this typo for consistency.","section":"Definition III.1"},{"comment":"Propositions VI.1–VI.3 are stated without proofs, with the remark that they are direct q-ary generalizations of binary results. Since these propositions are central to the claimed encoder, please provide proofs or precise references to the q-ary versions.","section":"Section VI"},{"comment":"The existence of parameters a_{t'}, b, c for which the redundancy bound holds is asserted without the standard counting argument. A short pigeonhole argument would make the redundancy claim complete.","section":"Theorem IV.1"},{"comment":"There is a typo in 'the anaysis'; it should be 'the analysis'.","section":"Section VI-B"}],"recommendation":"major_revision","confidential_remarks":"The two gaps identified in the major comments are potentially fixable. If Lemma III.3 in [19] actually covers t2=0 and t2=1, the authors should quote the precise statement; otherwise a new lemma is needed. The second gap in Theorem V.1 may require reworking the window-locating argument. Given the otherwise careful structure, I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hey — quick read of Ye–Sun–Ge (arXiv:2507.04797). The headline: they have a genuinely new position-estimation method based on strong-locally-balanced differential sequences with a VT constraint and an L1-weight constraint. If the proof is patched, it shaves one log log n off the best known redundancy for (≤t)-burst-deletion and t-localized-deletion codes, but only for t < 2q (and even q when q ≤ t < 2q).\n\nWhat's actually new and good: the position-estimation code itself is simpler than prior constructions and, unlike earlier position-estimation codes, it also corrects a single deletion — that's exactly where the log log n saving comes from. The local-balance argument in Claims 1 and 2 is carefully developed and internally consistent on inspection. The redundancy accounting and the choice of good triples in Lemma III.4 are thorough. The efficient encoder into strong-locally-balanced differential sequences is new, though it leans on an unproved q-ary generalization of [31]; the authors state Propositions VI.1–VI.3 without proof and say they follow by direct generalization. That is likely true but needs a written justification.\n\nThe real soft spot is the one the stress-test flags: Theorem IV.1 and V.1 invoke Lemma III.3 with t2 = 0 (and t2 = 1 when t' = t−1), while Lemma III.3 is stated only for t1 ≥ t2 ≥ 2. A burst of t' deletions in the original sequence corresponds to a (t',0)-burst-error, or a (t'+1,1)-burst-error in the differential sequence, so the cited lemma does not cover the case needed for the final correction step. The paper gives no alternative derivation of a P-bounded deletion-only correcting code with redundancy log P + O(1). This is load-bearing: without it, Theorems IV.1 and V.1 do not establish the announced redundancy. But it looks fixable — existing machinery for (t, s)-burst errors should yield the required code, and the same authors' [19] is the natural source.\n\nThe citation pattern is fine: [19, Corollary 3] and [26] are used as black boxes, but they're real published theorems and there is no circularity. The t < 2q restriction is a genuine limitation, and the paper is honest about it.\n\nWho should read this: coding theorists working on deletion-correcting codes, especially burst and localized deletion models. It deserves a serious referee — not as-is, because the t2=0 gap must be patched and the encoder claims need proofs or explicit citations, but the core method is promising and the improvement is modest but real.","headline":"A genuinely new position-estimation scheme that improves redundancy for burst and localized deletions, but the main theorems currently rest on an unstated parameter regime of a cited lemma; fixable, but unsupported as written.","tokens_in":28497,"tokens_out":2425,"would_cite":false,"duration_ms":26692,"reading_group":"yes","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":"For any fixed alphabet size q and any burst length t < 2q (with q even in the upper range), there are q-ary codes correcting a burst of at most t deletions—and codes correcting a single t-localized deletion—with redundancy log n + (t-1)…","keywords":["burst-deletion correcting codes","localized-deletion correcting codes","position-estimation code","locally-balanced sequences","differential sequences","Varshamov-Tenengolts constraint","q-ary codes","redundancy bounds"],"falsifier":"Run a finite computer search for q=3, t=2, and small n, enumerating all codewords satisfying the constraints in Theorem IV.1 and testing whether any two have overlapping two-deletion-burst balls; a single intersection would refute the construction in that parameter range. A narrower check is to verify whether Lemma III.3 actually supplies the t2=0 case, since the final correction step in Theorem IV.1 (and Theorem V.1 at t′=t) depends on that unstated case.","tokens_in":27358,"feed_emoji":"🧬","tokens_out":8631,"duration_ms":89287,"temperature":0.7,"pith_summary":"Deletions that hit a sequence in one burst, or inside one short window, are hard because the receiver does not know where symbols vanished. This paper constructs codes that fix at most t such deletions while adding only about log n + (t-1) log log n + O(1) redundant symbols over an alphabet of size q, for any fixed q and any 2 ≤ t < 2q (with q even when t ≥ q). That improves the redundancy of previous constructions for both the burst-deletion and localized-deletion models, and it comes from a new position-estimation code: codewords are chosen so that a short checksum-driven invariant pinpoints the damaged window before correction begins. The paper also provides an efficient encoder that maps an arbitrary input into a codeword whose differential sequence is strong-(ℓ,ϵ)-locally-balanced, the property the whole construction relies on.","feed_headline":"Burst-deletion codes reach log n + (t−1) log log n redundancy","feed_subtitle":"New position-estimation scheme trims redundancy for both burst and localized deletions, for any alphabet with t < 2q.","key_machinery":"The machinery is the differential sequence ψ(x), defined by ψ(x)_i = (x_{i−1} − x_i) mod q with x_0 = x_{n+1} = 0; deleting one symbol simply merges two adjacent entries of ψ with a mod-q sum. The codes select codewords whose ψ is strong-(ℓ,ϵ)-locally-balanced—every substring of length at least ℓ has L1-weight near (q−1)/2 per symbol—and then impose the two checksum constraints on ψ. The locally-balanced condition makes the key gap equation (j − i)Δsum + σ(j) − σ(i) impossible when j − i ≥ ℓ, unless a 'good triple' (q,t,ϵ) with a certain integer s_{t′} exists; Lemma III.4 shows such triples exist exactly for t < q or even q with t < 2q. The final correction uses a P-bounded (t1,t2)-burst-error correcting code from Lemma III.3 to repair whatever remains in a window of length P = ℓ + t − 1.","core_discovery":"The central claim is Theorem IV.1 and Theorem V.1: for fixed q and t with 2 ≤ t < 2q (even q required in the upper range), there is a q-ary code correcting a burst of at most t deletions, and a q-ary code correcting a single t-localized deletion, both with redundancy log n + (t-1) log log n + O(1). The codes are intersections of four constraints: the differential sequence ψ(x) is strong-(ℓ,ϵ)-locally-balanced; for each possible burst length t′ a P-bounded code checksum is fixed; VT(ψ(x)) ≡ b (mod N); and Sum(ψ(x)) ≡ cq (mod (t+1)q). The VT and L1 constraints carry the position information that survives deletion, and the locally-balanced condition bounds how far wrong the position estimate can be—Claim 1 shows the estimated start satisfies j − i < ℓ, a window of length O(log n). Inside that window a P-bounded burst-error code finishes the correction. Because the same position-estimation code handles every burst length t′ and also corrects a single deletion on its own, the redundancy saves one log log n factor compared with approaches that split the alphabet or handle each burst length separately.","pith_inferences":["The t < 2q restriction is an artifact of the good-triple condition; extending past t ≥ 2q would need a different local-balance ratio or a different invariant, and nothing here suggests the log-log factor is removable in that range.","Because ψ is a bijection onto sequences with Sum ≡ 0 (mod q), the same position-estimation scheme may transfer to insertion or edit-burst models where differential sequences also merge or split locally.","The encoder's two-symbol overhead raises the natural question of whether one redundant symbol suffices; the counting in Lemma III.2 gives at least q^n/2 valid codewords, so the existential bound does not rule out a one-symbol encoder.","The good-triple characterization in Lemma III.4 is a self-contained design tool that could be reused for other constrained codes that require local balance on differential sequences."],"forward_implications":["For q-ary alphabets with t < q, the (≤t)-burst code achieves redundancy log n + (t−1) log log n + O(1), improving on the previous log n + 8 log log n + o(log log n) for general q.","For even q in the range q ≤ t < 2q, both the burst and localized codes achieve the same redundancy, and the localized code improves on the previous log n + 2t log log n + O(1).","The position-estimation code corrects a single deletion on its own and serves all burst lengths up to t with one set of constraints, so the redundancy does not accumulate an extra log log n per possible burst length.","The new encoder turns any length-(n−2) sequence into a length-n sequence whose differential sequence is strong-(ℓ,ϵ)-locally-balanced with two redundant symbols, running in O(n^C) time for a constant C depending on the chosen parameters.","The decoding algorithms run in O(n log n) time and locate the damaged window before applying the local correction step.","The redundancy gap to the log n + Ω(1) lower bound is narrowed but not closed; the paper leaves open whether the lower bound is asymptotically tight for general t and q."],"supporting_citations":[{"why":"Supplies the P-bounded (t1,t2)-burst-error correcting code f_{P,t1,t2} used to finish correction inside the located window, and is also the source of previous even-q constructions.","marker":"[19, Corollary 3]"},{"why":"Shows that deleting one symbol merges two adjacent entries of the differential sequence and provides the single-deletion correction algorithm that Lemma III.1 adapts to arbitrary modulus N.","marker":"[28, Theorem 3]"},{"why":"Origin of the strong-(ℓ,ϵ)-locally-balanced condition, whose L1-weight generalization Lemma III.2 proves is satisfied by many codewords.","marker":"[20, Claim 4]"},{"why":"The analogous VT-plus-strong-local-balance position-estimation code that works only for odd bursts, which this paper's differential-sequence version generalizes to a wider range of q and t.","marker":"[20, Lemma 9]"},{"why":"Provides the sliding-window constrained-code encoder used as Stage 1 to map an arbitrary input differential sequence into a locally-balanced sequence.","marker":"[31]"},{"why":"Records the VT-on-differential-sequence idea and the example showing that constraint alone cannot correct two deletions for q ≥ 3, motivating the added local-balance condition.","marker":"[22]"},{"why":"Supplies the previous best redundancy for general q, the baseline that the new burst-deletion code improves.","marker":"[13]"},{"why":"Provides the previous localized-deletion position-estimation code that locates errors within O((log n)^2), the baseline that the new localized code improves.","marker":"[25]"},{"why":"Introduces the binary encoder into strong-(ℓ,ϵ)-locally-balanced sequences that the new q-ary differential-sequence encoder generalizes.","marker":"[26, Section VI]"}],"fun_headline_variants":["Deletion-correction redundancy drops to log n + (t−1) log log n","New code corrects bursts and localized deletions with lower redundancy","Deletion codes: log n + (t−1) log log n redundancy achieved","Position-estimation code simplifies and improves deletion correction"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The decoding proof relies on a component that fixes purely deleted symbols inside a known short window, but the lemma it cites is stated only for mixed deletion-and-substitution errors, and the purely deletion case is not proved separately.","fun_headline_variants_meta":{"raw":{"variants":["Deletion-correction redundancy drops to log n + (t−1) log log n","New code corrects bursts and localized deletions with lower redundancy","Deletion codes: log n + (t−1) log log n redundancy achieved","Position-estimation code simplifies and improves deletion correction"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000825,"raw_usage":{"total_tokens":3757,"prompt_tokens":1243,"completion_tokens":2514,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":859,"completion_tokens_details":{"reasoning_tokens":2436}},"tokens_in":859,"tokens_out":2514,"duration_ms":20127,"temperature":1.0,"reasoning_tokens":2436,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:40:05.533236+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a finite computer search for q=3, t=2, and small n, enumerating all codewords satisfying the constraints in Theorem IV.1 and testing whether any two have overlapping two-deletion-burst balls; a single intersection would refute the construction in that parameter range. A narrower check is to verify whether Lemma III.3 actually supplies the t2=0 case, since the final correction step in Theorem IV.1 (and Theorem V.1 at t′=t) depends on that unstated case.","supporting_citations":[{"cited_title":"Efficient Design of Subblock Energy-Constrained Codes and Sliding Window-Constrained Codes,","cited_arxiv_id":null,"evidence_quote":"Provides the sliding-window constrained-code encoder used as Stage 1 to map an arbitrary input differential sequence into a locally-balanced sequence."},{"cited_title":"Non-binary Codes for Correcting a Burst of at Most t Deletions,","cited_arxiv_id":null,"evidence_quote":"Records the VT-on-differential-sequence idea and the example showing that constraint alone cannot correct two deletions for q ≥ 3, motivating the added local-balance condition."},{"cited_title":"Non-binary Two-Deletion Correcting Codes and Burst-Deletion Correcting Codes,","cited_arxiv_id":null,"evidence_quote":"Supplies the previous best redundancy for general q, the baseline that the new burst-deletion code improves."},{"cited_title":"Optimal Codes Correcting Localized Deletions,","cited_arxiv_id":null,"evidence_quote":"Provides the previous localized-deletion position-estimation code that locates errors within O((log n)^2), the baseline that the new localized code improves."}],"review_version":1}