Pith. sign in

REVIEW 3 major objections 3 minor 23 references

Reconstruction Codes for Deletions and Insertions: Connection, Distinction, and Construction

T0 review · 3 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that any code reconstructing from t insertions also reconstructs from t deletions, and that for many reads deletion codes need only constant redundancy while insertion codes require log-log redundancy.

desk verdict Strong, novel results with two fixable proof gaps; worth refereeing. read the letter →

arxiv 2508.14386 v1 pith:3QTDGTLB submitted 2025-08-20 cs.IT math.IT

Yubo Sun , Gennian Ge This is my paper · ORCID
classification cs.ITmath.IT MSC 94B6094B65
keywords reconstructioncodesdeletionballinsertionminimumredundancyruncountsequenceq-aryLevenshteindistance
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Reconstruction codes let a receiver recover a stored sequence from any N noisy copies, or reads, of it. This paper shows a one-way link between two error models: any code that works when the noise is t insertions also works when the noise is t deletions, so deletions never require more redundancy than insertions. In the regime where N grows like a fixed multiple of n^(t-1), the two models diverge: deletion codes can be built with only a constant number of extra symbols, while insertion codes provably need log-log n + O(1) extra symbols. The paper then constructs explicit q-ary codes for two deletions or two insertions with up to five reads, matching the best binary constructions up to small additive terms.

What carries the argument

The connection rests on an explicit injection from the intersection of two t-deletion balls into the intersection of their t-insertion balls (Theorem 1). The deletion result rests on a run-count bound (Lemma 8): two sequences with a given number of uninterrupted equal-symbol blocks share at most C(r(x)+t-3,t-1)+C(r(y)+t-3,t-1) common t-deletion results; restricting to low-run sequences yields a code of size at least q^(n-1), hence constant redundancy. The insertion result rests on a bound on insertion-ball intersections at fixed Levenshtein distance, and on a theorem equating (n,q,N;I_t)-reconstruction with (n,q,2;I_1)-reconstruction in the chosen parameter window, reducing the problem to a

What would settle it

Enumerate all pairs of binary strings of length 8 with at most 4 equal-symbol blocks and compute their common two-deletion results. If any pair shares more than 6 such results, the run-count bound (and with it the constant-redundancy deletion claim) is false. The questionable identity in the proof can also be checked directly with block counts 3 and one string length 3, where the claimed equality gives 2 on one side and 3 on the other.

Watch

Extended reading notes

Core claim

Any two sequences share no more common t-deletion results than common t-insertion results, so every (n,q,N;I_t)-reconstruction code is automatically an (n,q,N;D_t)-reconstruction code (Theorem 1). For t >= 2 and N of order n^(t-1), the deletion minimum redundancy is a constant, disproving a conjecture, while the insertion minimum redundancy is exactly log-log n + O(1) (Theorem 2). Explicit q-ary codes for two deletions/insertions with 2, 3, 4, and 5 reads achieve redundancies 3 log n + O(log-log n), 3 log n + O(1), 2 log n + O(log-log n), and log n + O(log-log n), respectively.

Load-bearing premise

The deletion results depend on a bound that limits how many common deleted versions two sequences can share, based on how many uninterrupted equal-symbol blocks they contain; the proof of that bound as printed contains a counting step that fails on small examples, so the bound is not fully established as stated.

Editorial extensions

If this is right

  • Upper bounds for insertion reconstruction codes transfer automatically to deletion reconstruction codes; Theorem 1 makes this a general principle rather than a coincidence.
  • The conjecture in [1] predicting log-log n redundancy for many-read deletion codes is false; the true redundancy in the studied regime is a constant, substantially lowering the anticipated cost.
  • The insertion bound in [2] for binary alphabets extends to all q-ary alphabets and all t >= 2.
  • The explicit codes for N=2,3,4,5 extend the binary constructions in [3] to q-ary alphabets, within O(log-log n) of the binary benchmarks.
  • Corollary 1 yields a deletion analogue of the insertion-ball intersection bound in [15], so intersection-size bounds for insertions imply comparable bounds for deletions at any Levenshtein distance.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper does not exploit the reverse transfer: every lower bound on deletion redundancy would immediately lower-bound insertion redundancy via Theorem 1; future work could use this to derive new insertion lower bounds.
  • The constant-redundancy deletion construction is achieved by a coarse run-count filter; using t-periodicity and other run-structure constraints might push the threshold N upward or reduce the constant.
  • Because the proof of Lemma 8 contains a counting step that fails on small examples, researchers building on the deletion result should first check whether the stated bound or a slightly weaker one is valid; the asymptotic theorem may stand either way.
  • The construction transfer from insertions to deletions means the new q-ary two-deletion codes inherit insertion-side constraints; direct deletion-specific designs could potentially improve the additive constants for small N.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper studies reconstruction codes for t-deletions and t-insertions over q-ary alphabets. Its main claims are: (i) a general inequality |D_t(x)∩D_t(y)| ≤ |I_t(x)∩I_t(y)|, so every insertion reconstruction code is also a deletion reconstruction code and ρ(n,q,N;D_t) ≤ ρ(n,q,N;I_t); (ii) for t≥2 and N=O(n^{t-1}), deletions and insertions behave differently—the deletion redundancy is O(1), disproving a conjecture of Chrisnata et al., while the insertion redundancy is log log n + O(1); and (iii) explicit constructions for two-deletion/two-insertion reconstruction codes for N=2,3,4,5 with redundancies 3 log n+O(log log n), 3 log n+O(1), 2 log n+O(log log n), and log n+O(log log n). The proofs use run-count estimates for deletion balls, insertion-ball recurrences, and extensions of earlier binary constructions to non-binary alphabets.

Significance. If the results hold, the paper makes a strong contribution: it establishes a clean general connection between deletion and insertion reconstruction codes, separates the two settings asymptotically at N=O(n^{t-1}), and extends the available construction toolbox to non-binary alphabets. The disproof of the Chrisnata et al. conjecture and the q-ary extension of Ye et al. are both of clear interest to the coding theory community. The central ideas are plausible and the asymptotic conclusions are likely recoverable. However, the paper as written contains load-bearing gaps in the deletion-bound lemma, in the insertion-case recursion for t=2, and in the application of the binary-to-ternary extension lemma. These issues are local and appear fixable, but they are not merely cosmetic.

major comments (3)
  1. [Section IV-B, Lemma 8] Lemma 8 is false as stated. Take q=2, n=10, t=4, x=0000 111 000, and y=000 1111 000. Both sequences have r(x)=r(y)=3 runs. D_4(x)∩D_4(y) consists of all common subsequences of length 6, namely 0^α 1^β 0^γ with α,β,γ≤3 and α+β+γ=6, giving 10 sequences. The lemma claims the intersection is at most C(3+4-3,3)+C(3+4-3,3)=4+4=8. The error is in the step marked (⋄): the Cauchy–Vandermonde evaluation is off by one; the correct sum evaluates to C(r+t-2,t-1), not C(r+t-3,t-1). Since Lemma 8 is the key bound in the proof of Theorem 3, the deletion half of Theorem 2 is not supported as written. The leading asymptotic survives if the bound is corrected to 2 C(r+t-2,t-1), because that still has the same leading term, but the lemma, its proof, and the threshold in Theorem 3 must be revised.
  2. [Section IV-C, Theorem 4 and Lemma 9] The quantity Δ_q(n,t) is defined using N_q^+(n,t-2,t-2,1) and I_q(n+1,t-3). For t=2, these terms are undefined (t-2=0 violates Lemma 6's hypothesis t≥k≥ℓ≥1, and t-3=-1 makes I_q meaningless). Yet Theorem 4 and Lemma 9 claim to cover t≥2. The base case n=t=2 in Lemma 9 also uses I_{t-3}=I_{-1}. Thus the insertion half of Theorem 2 is not proved for t=2 as written. The authors need either a separate treatment for t=2 or a reformulation that avoids negative parameters. This is load-bearing because Theorem 2 is a central claim.
  3. [Section V-B, Lemma 20] Lemma 20 applies Lemma 19 with a parameter mismatch. In the proof, x and y are in R_q(n,4,P) and ~{x} is a combination of at most five 4≤-periodic sequences, so |~{x}|≤5P. Lemma 19, however, is stated only for |~{x}|≤P. The error bound O(P^{14}) in Lemma 18 also becomes O((5P)^{14}) if the length parameter is 5P. The proof of Lemma 20 therefore does not follow from the cited lemma as stated. This affects the constructions for N=2,4,5. The issue is likely fixable by restating Lemma 19 with parameter 5P and correspondingly adjusting the codomain of ξ, but the current text needs correction.
minor comments (3)
  1. [Section IV-C, Lemma 9] In the proof of the case |u|=|v|=0, the summation index is written as ~b∈Σ_q\{d}~ in one line; it should be d'∈Σ_q\{d}. Also the notation S_a'^{d'} is used before its definition is clear.
  2. [Section V-A, Theorem 6] The proof of Theorem 6 relies on Claims 1 and 2, but Claim 2 only sketches the case |A_3|=|A_6|=1 and says the other cases are similar. Given the subtle differences noted in Remark 7, a fuller verification of the omitted cases would be helpful.
  3. [Section II-A] The definition of R(n,t,ℓ) as 'every t≤-periodic substring has length at most ℓ' is used later with parameters such as 4 and (P-1)/3. It would be clearer to state explicitly whether the bound applies to maximal periodic substrings or to all substrings, since this affects the proof of Lemma 20.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: central claims are derived from first principles or external published results; self-citations are to independent technical lemmas.

full rationale

The paper's main results are not circular. Theorem 1 proves |D_t(x)∩D_t(y)| ≤ |I_t(x)∩I_t(y)| via an explicit injective map φ, which is self-contained and does not presuppose the conclusion. The deletion part of Theorem 2 (Theorem 3) rests on Lemma 8, which uses Levenshtein's deletion-ball bound (Lemma 3) and a decomposition lemma from Chrisnata et al. (Lemma 4), both external to this paper; the subsequent covering-code lower bound relies on published results by Levenshtein and Lenz et al. The insertion part (Theorem 4 and Lemma 9) uses asymptotic intersection formulas from Sala et al. and a structural lemma from Abbasian et al., none of which are derived from the paper's own claims. Section V constructs codes using technical lemmas from the authors' prior works [3,10,12,8]. Although these are self-citations, they are not circular in the forbidden sense: each cited lemma is a parameter-free, stated-assumption tool (e.g., VT-syndrome properties, a hash-like function ξ for short differing middles, covering-code bounds) that does not include the target reconstruction-code result as an assumption. The paper's own contributions (distinction between deletion and insertion redundancy, non-binary constructions) are new and not merely restatements of these cited tools. A correctness concern exists in Lemma 8's step (⋄), where the claimed Cauchy–Vandermonde evaluation appears to be incorrectly applied (the example in the skeptical note shows the stated bound fails). This is a mathematical error, not circularity; it weakens the proof of Theorem 3 as written but does not constitute a derivation that reduces to its own input. Therefore, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters fitted to data and no newly postulated entities. The central claims rest on standard and cited lemmas; the main caveat is that some cited tools are the authors' own prior published results, but they are not circular in the sense of assuming the target theorems.

assumptions (5)
  • standard math Levenshtein ball-size formulas: |D_t(x)| <= C(r(x)+t-1,t) and |I_t(x)| = I_q(n,t) = (q-1)^t n^t/t! + O(n^{t-1})
    Quoted from [14] and used in the proofs of Theorem 3 and Theorem 4.
  • domain assumption Intersection-size formula N_q^+(n,t,k,ell) from Sala et al. [15]
    The insertion part of Theorem 2 and Lemma 9 depend on this exact asymptotic formula for intersections of insertion balls.
  • domain assumption Characterization of single-insertion ball intersections from Abbasian et al. [18]
    Lemma 7 classifies pairs x=u x~ v, y=u y~ v with |I_1(x) intersection I_1(y)|=1; this is a load-bearing input to Lemma 9.
  • domain assumption Existence of a binary hash function xi from [3, Theorem 5.6]
    Lemma 18 assumes a previously constructed hash function for binary two-insertion-disjointness; Lemma 19 and Lemma 20 extend it to q-ary sequences.
  • standard math Covering-code size bound and the lower bound |R_q(n,t,P)| >= q^n/2 from [8, Lemma 6.10]
    Used in Theorem 3 to show the run-constrained code has at most log q redundancy, and in Section V to compute construction sizes.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Reconstruction Codes for Deletions and Insertions: Connection, Distinction, and Construction." pith.science (2026). https://pith.science/paper/3QTDGTLB

@misc{pith2026250814386,
  author       = {Pith},
  title        = {Pith review of: Reconstruction Codes for Deletions and Insertions: Connection, Distinction, and Construction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3QTDGTLB}},
  note         = {Machine review of arXiv:2508.14386}
}
abstract

Let $\mathcal{B}(\cdot)$ be an error ball function. A set of $q$-ary sequences of length $n$ is referred to as an \emph{$(n,q,N;\mathcal{B})$-reconstruction code} if each sequence $\boldsymbol{x}$ within this set can be uniquely reconstructed from any $N$ distinct elements within its error ball $\mathcal{B}(\boldsymbol{x})$. The main objective in this area is to determine or establish bounds for the minimum redundancy of $(n,q,N;\mathcal{B})$-reconstruction codes, denoted by $\rho(n,q,N;\mathcal{B})$. In this paper, we investigate reconstruction codes where the error ball is either the \emph{$t$-deletion ball} $\mathcal{D}_t(\cdot)$ or the \emph{$t$-insertion ball} $\mathcal{I}_t(\cdot)$. Firstly, we establish a fundamental connection between reconstruction codes for deletions and insertions. For any positive integers $n,t,q,N$, any $(n,q,N;\mathcal{I}_t)$-reconstruction code is also an $(n,q,N;\mathcal{D}_t)$-reconstruction code. This leads to the inequality $\rho(n,q,N;\mathcal{D}_t)\leq \rho(n,q,N;\mathcal{I}_t)$. Then, we identify a significant distinction between reconstruction codes for deletions and insertions when $N=O(n^{t-1})$ and $t\geq 2$. For deletions, we prove that $\rho(n,q,\tfrac{2(q-1)^{t-1}}{q^{t-1}(t-1)!}n^{t-1}+O(n^{t-2});\mathcal{D}_t)=O(1)$, which disproves a conjecture posed in \cite{Chrisnata-22-IT}. For insertions, we show that $\rho(n,q,\tfrac{(q-1)^{t-1}}{(t-1)!}n^{t-1}+O(n^{t-2});\mathcal{I}_t)=\log\log n + O(1)$, which extends a key result from \cite{Ye-23-IT}. Finally, we construct $(n,q,N;\mathcal{B})$-reconstruction codes, where $\mathcal{B}\in \{\mathcal{D}_2,\mathcal{I}_2\}$, for $N \in \{2,3, 4, 5\}$ and establish respective upper bounds of $3\log n+O(\log\log n)$, $3\log n+O(1)$, $2\log n+O(\log\log n)$ and $\log n+O(\log\log n)$ on the minimum redundancy $\rho(n,q,N;\mathcal{B})$. This generalizes results previously established in \cite{Sun-23-IT}.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Correcting deletions with multiple reads,

    J. Chrisnata, H. M. Kiah, and E. Yaakobi, “Correcting deletions with multiple reads,” IEEE Transactions on Information Theory , vol. 68, no. 11, pp. 7141–7158, 2022

    work page 2022

  2. [2]

    Reconstruction of sequences distorted by two insertions,

    Z. Ye, X. Liu, X. Zhang, and G. Ge, “Reconstruction of sequences distorted by two insertions,” IEEE Transactions on Information Theory , vol. 69, no. 8, pp. 4977–4992, 2023

    work page 2023

  3. [3]

    Correcting two-deletion with a constant number of reads,

    Y . Sun and G. Ge, “Correcting two-deletion with a constant number of reads,” IEEE Transactions on Information Theory , vol. 69, no. 5, pp. 2969–2982, 2023

    work page 2023

  4. [4]

    Next-generation digital information storage in dna,

    G. M. Church, Y . Gao, and S. Kosuri, “Next-generation digital information storage in dna,” Science, vol. 337, no. 6102, pp. 1628–1628, 2012

    work page 2012

  5. [5]

    Towards practical, high-capacity, low-maintenance information storage in synthesized dna,

    N. Goldman, P. Bertone, S. Chen, C. Dessimoz, E. M. LeProust, B. Sipos, and E. Birney, “Towards practical, high-capacity, low-maintenance information storage in synthesized dna,” Nature, vol. 494, pp. 77–80, 2013

    work page 2013

  6. [6]

    Coding for racetrack memories,

    Y . M. Chee, H. M. Kiah, A. Vardy, V . K. Vu, and E. Yaakobi, “Coding for racetrack memories,” IEEE Transactions on Information Theory , vol. 64, no. 11, pp. 7094–7112, 2018

    work page 2018

  7. [7]

    Coding for sequence reconstruction for single edits,

    K. Cai, H. M. Kiah, T. T. Nguyen, and E. Yaakobi, “Coding for sequence reconstruction for single edits,” IEEE Transactions on Information Theory , vol. 68, no. 1, pp. 66–79, 2022

    work page 2022

  8. [8]

    Sequence reconstruction under single-burst-insertion/deletion/edit channel,

    Y . Sun, Y . Xi, and G. Ge, “Sequence reconstruction under single-burst-insertion/deletion/edit channel,”IEEE Transactions on Information Theory, vol. 69, no. 7, pp. 4466–4483, 2023

    work page 2023

Show all 23 references
  1. [9]

    Error-correcting codes for nanopore sequencing,

    A. Banerjee, Y . Yehezkeally, A. Wachter-Zeh, and E. Yaakobi, “Error-correcting codes for nanopore sequencing,” IEEE Transactions on Information Theory, vol. 70, no. 7, pp. 4956–4967, 2024

    2024

  2. [10]

    Bounds and constructions of ℓ-read codes under the hamming metric,

    Y . Sun and G. Ge, “Bounds and constructions of ℓ-read codes under the hamming metric,” IEEE Transactions on Information Theory , vol. 71, no. 8, pp. 5868–5883, 2025

    2025

  3. [11]

    Coding for synthesis defects,

    Z. Lu, H. M. Kiah, Y . Zhang, R. N. Grass, and E. Yaakobit, “Coding for synthesis defects,” in 2024 IEEE Information Theory Workshop (ITW), Shenzhen, China, Nov. 2024, pp. 621–626

    2024

  4. [12]

    Correcting errors through partitioning and burst-deletion correction,

    Y . Sun and G. Ge, “Correcting errors through partitioning and burst-deletion correction,” arXiv:2506.07609, 2025. [Online]. Available: https://doi.org/10.48550/arXiv:2506.07609

    2025 doi arXiv

  5. [13]

    Efficient reconstruction of sequences,

    V . I. Levenshtein, “Efficient reconstruction of sequences,” IEEE Transactions on Information Theory , vol. 47, no. 1, pp. 2–22, 2001

    2001

  6. [14]

    Efficient reconstruction of sequences from their subsequences or supersequences,

    ——, “Efficient reconstruction of sequences from their subsequences or supersequences,” Journal of Combinatorial Theory. Series A , vol. 93, no. 2, pp. 310–332, 2001

    2001

  7. [15]

    Exact reconstruction from insertions in synchronization codes,

    F. Sala, R. Gabrys, C. Schoeny, and L. Dolecek, “Exact reconstruction from insertions in synchronization codes,” IEEE Transactions on Information Theory, vol. 63, no. 4, pp. 2428–2445, 2017

    2017

  8. [16]

    Sequence reconstruction over the deletion channel,

    R. Gabrys and E. Yaakobi, “Sequence reconstruction over the deletion channel,” IEEE Transactions on Information Theory, vol. 64, no. 4, pp. 2924–2931, 2018

    2018

  9. [17]

    Sequence reconstruction problem for deletion channels: A complete asymptotic solution,

    V . L. P. Pham, K. Goyal, and H. M. Kiah, “Sequence reconstruction problem for deletion channels: A complete asymptotic solution,” Journal of Combinatorial Theory, Series A , vol. 211, p. 105980, 2025

    2025

  10. [18]

    On the size of error ball in single-deletion double-insertion channels,

    A. Abbasian, M. Mirmohseni, and M. N. Kenari, “On the size of error ball in single-deletion double-insertion channels,” IEEE Transactions on Molecular, Biological, and Multi-Scale Communications , vol. Early Access, 2025. [Online]. Available: https://doi.org/10.1109/TMBMC.2025.3590000

    2025

  11. [19]

    Binary codes capable of correcting deletions, insertions and reversals,

    V . I. Levenshtein, “Binary codes capable of correcting deletions, insertions and reversals,” Soviet Physics Doklady , vol. 10, no. 8, pp. 707–710, 1966

    1966

  12. [20]

    Logarithmically larger deletion codes of all distances,

    N. Alon, G. Bourla, B. Graham, X. He, and N. Kravitz, “Logarithmically larger deletion codes of all distances,” IEEE Transactions on Information Theory, vol. 70, no. 1, pp. 125–130, 2024

    2024

  13. [21]

    Jukna, Extremal Combinatorics with Applications in Computer Science , 2nd ed

    S. Jukna, Extremal Combinatorics with Applications in Computer Science , 2nd ed. Springer-Verlag Berlin Heidelberg, 2011

    2011

  14. [22]

    Bounds for deletion/insertion correcting codes,

    V . I. Levenshtein, “Bounds for deletion/insertion correcting codes,” in Proceedings IEEE International Symposium on Information Theory , Lausanne, Switzerland, Jun. 2002, pp. 370–

    2002

  15. [23]

    Covering codes using insertions or deletions,

    A. Lenz, C. Rashtchian, P. H. Siegel, and E. Yaakobi, “Covering codes using insertions or deletions,” IEEE Transactions on Information Theory , vol. 67, no. 6, pp. 3376–3388, 2021

    2021

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.