{"id":"ffab5594-d14f-445d-a916-eab521b2461e","arxiv_id":"2505.04232","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For binary reconstruction codes correcting one deletion and one substitution, redundancy 0, 1, 2, log log n+3, log n+1, and 3 log n+4 suffice when the number of reads N is 4n−8, 3n−4, 2n+9, n+21, 31, and 7, respectively.","lead":"This paper designs families of binary codes for reconstructing a stored word when each of several noisy reads suffers one deletion and one substitution. It achieves the smallest known redundancy for several read counts, including zero redundancy when many reads are available.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.8's proof of the 'bad ≤ 6' bound (used for the N=7 code) does not guarantee 24 distinct good sequences for every pair; Theorem 4.8 may be unsupported.","rationale":"The reader's verdict was CONDITIONAL because Section V's case analysis could be incomplete. My stress-test identifies a specific subclaim of that analysis—Lemma 3.8's bound of at most 6 'bad' sequences—which is load-bearing for the most striking headline result, the (n,7)-reconstruction code with redundancy 3 log n + 4. The written proof of this subclaim is incomplete: the lower bound of 24 good sequences is asserted by listing sequences that may not be distinct and may not all occur for every pair, so the implication total ≤ 30 ⇒ bad ≤ 6 is not justified as written. This does not by itself establish a counterexample; the recommended test is an exhaustive check for small n. If the test passes, the concern is a proof gap rather than a mathematical error, so the existing CONDITIONAL verdict remains appropriate. I differ from the reader only in emphasis: the more serious unverified point is the bad-sequence count, not the overall |B|≤30 bounds or the Remark 2.8 size bound.","tokens_in":40146,"tokens_out":20731,"duration_ms":193245,"concrete_test":"Exhaustively enumerate all pairs of binary strings x,y of length n≤10 with dH(x,y)≥3 and |D(x,y)|=|S(x,y)|=0; for each pair compute B(x,y) and classify every z∈B(x,y) as good or bad according to Definition 3.7 by checking all representations z=x(i,î)=y(j,ĵ). Verify that the maximum of |B(x,y)| is ≤30 and the maximum number of bad sequences is ≤6. A counterexample would falsify Lemma 3.8 and hence Theorem 4.8; if the maxima hold, the concern reduces to a missing proof rather than a mathematical error.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4.8 constructs an (n,7;B)-reconstruction code from the list-decodable code CL by combining Lemma 2.6 with the second part of Lemma 3.8: among the ≤30 sequences in B(x,y) when d=s=0, at most 6 are 'bad'. This bad-sequence bound is the least secure step in the paper. The proof of Lemma 3.8 bounds |B(x,y)| by summing worst-case estimates over five index ranges (6+6+2+2+14=30) and then asserts that 24 good sequences exist, providing a list. However, the listed sequences are not proved to be distinct, nor are they shown to belong to B(x,y) for every pair (x,y) satisfying the hypotheses. For instance, if u is far in Hamming distance from every single-deletion of αv, the branch producing auβb, auβb, aw(1)βb, aw(2)βb may contribute nothing, and no compensation argument is given to show the total shrinks correspondingly. Since the N=7 result depends exactly on 'bad ≤ 6', a missed or duplicate good sequence could allow more than 6 bad sequences and invalidate Theorem 4.8.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies binary reconstruction codes for the single-deletion single-substitution channel. It defines B(x) as the set of length-(n-1) sequences obtainable from x by one deletion followed by one substitution, and calls C an (n,N;B)-reconstruction code when |B(x)∩B(y)| < N for every distinct x,y in C. The main results, summarized in Table I, give codes with redundancy 0, 1, 2, log log n + 3, log n + 1, and 3 log n + 4 for N = 4n−8, 3n−4, 2n+9, n+21, 31, and 7, respectively. The proofs decompose |B(x,y)| according to the sizes of the single-deletion and single-substitution intersections, bound the pieces by exhaustive case analysis in Section V, and combine those bounds with existing code constructions (VT codes, list-decodable codes, and single-deletion reconstruction codes).","tokens_in":40382,"tokens_out":6933,"duration_ms":65325,"significance":"If the case analysis and the size estimates are correct, the paper provides a coherent low-redundancy hierarchy for reconstruction codes under one deletion and one substitution, covering linear, logarithmic, and constant N. The decomposition of B(x,y) into S, D, and a residual piece is natural, and the explicit code constructions are a useful contribution. The N=7 result obtained from list-decodable codes is particularly interesting. The paper is generally readable and the main proof strategy is well matched to the problem. However, two load-bearing steps are not fully supported as written: the unproved size bound in Remark 2.8, which feeds the redundancy claim in Theorem 4.6, and the distinctness/membership claims for the 24 good sequences in Lemma 3.8, on which Theorem 4.8 rests. These need to be repaired before the main claims can be considered established.","major_comments":[{"comment":"The bound |R(n,P)| ≥ 3·2^{n−2} for P ≥ log n + 3 is asserted by saying that an argument similar to [25, Lemma 2] applies, but no proof is given. This bound is load-bearing: Theorem 4.6 uses it together with Lemma 4.4 to obtain |R(n,P)∩Cr| ≥ 2^{n−2} and then derives the log log n + 3 redundancy. Since [25, Lemma 2] is not stated in the paper and the reduction to run-length constraints on ψ(x) is only sketched, the derivation should be written out or replaced by a precise citation with a proof.","section":"Remark 2.8"},{"comment":"The proof of the 'bad ≤ 6' assertion claims that 24 good sequences exist and lists them, but it does not prove that the listed strings are pairwise distinct, nor does it prove for each listed string that it belongs to B(x,y) for every pair (x,y) satisfying the hypotheses. The listing appears to contain repeated expressions (for example aαu(1)βb appears twice in the displayed set), and in several branches the proof only says 'in the worst case' without showing that the claimed sequences exist in all cases. Since Theorem 4.8 depends exactly on the bound of at most 6 bad sequences, this step must be made rigorous: either prove that at least 24 distinct good sequences lie in B(x,y), or provide a different argument for the bad-sequence bound.","section":"Section V.F, Lemma 3.8"},{"comment":"The displayed lower bound on |C_{n+21}| is garbled: the expression '2n−2 / 2 (1/2 log log n+4)' is not well-formed and does not transparently yield the stated redundancy. The intended pigeonhole calculation should be written cleanly, for example |C_{n+21}| ≥ |R(n,P)∩Cr| / (2(1+P/2)), leading to the stated log log n + O(1) redundancy. In the same proof, the case (d,s) = (0,2) cites Lemma 3.4, but the correct reference is Lemma 3.5.","section":"Theorem 4.6"}],"minor_comments":[{"comment":"The list of N values says '4n−8, 3n−4, 2n+8, n+21, and 31', but the table and theorems use N = 2n+9 and also include N = 7; the list should be corrected.","section":"Section IV, first paragraph"},{"comment":"The proof states red(C7) ≤ log 3n + 4, which should read 3 log n + 4, consistent with the abstract and with the code-size calculation |C7| ≥ 2^n/(4·2n·2n^2).","section":"Theorem 4.8 proof"},{"comment":"The symbol r is used both for the number of runs r(x) and for the redundancy red(C), and in the proof of Theorem 4.6 the redundancy is written as r(C_{n+21}). This is confusing and should be renamed, e.g., red(C_{n+21}).","section":"Theorem 4.6 proof"},{"comment":"In the first paragraph of the proof, the notation 'u, u ∈ Σ^*' should presumably be 'u, v ∈ Σ^*'; the two middle strings of the two centers should be named distinctly.","section":"Lemma 3.8, proof"},{"comment":"The proof of Claim 5.14 uses the phrase 'by Lemma 2.13' in several places where the intended statement is the bound on the number of deletions of one sequence within Hamming distance one of another, which is Lemma 2.14. Lemma 2.13 alone does not directly give those 'at most three' statements.","section":"Section V.C, Claim 5.14"},{"comment":"The remark says 'Among them, we choose C3n−4 as the single-deletion reconstruction code defined in Lemma 2.7', but the code in Theorem 4.2 is the inversion-constrained code, not literally the code C_P(a1,a2) from Lemma 2.7. The relationship should be clarified.","section":"Remark 4.3"}],"recommendation":"major_revision","confidential_remarks":"The paper overlaps with the concurrent work [34], which the authors disclose. The main concern is not novelty but rigor: the unproved bound in Remark 2.8 and the unverified distinctness/membership in Lemma 3.8 are both load-bearing. I would like the revision to contain a complete proof of the size bound for R(n,P) and a careful rewrite of the final counting step in Lemma 3.8, including explicit distinctness arguments and a check that every listed good sequence is indeed in B(x,y)."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The paper genuinely improves on concurrent work by Song et al.: redundancy 0 vs 1 for N=4n−8, and N=31 vs 41 for redundancy log n+1, plus new intermediate trade-offs. The six-case decomposition of the overlap B(x,y) according to (d,s) is a real technical contribution, and the proofs of Lemmas 3.2–3.6 are detailed and mostly persuasive. But the weakest spot is exactly the one the stress-test names. Lemma 3.8 claims that when d=s=0, at most six of the ≤30 sequences in B(x,y) are 'bad'. The proof establishes the 30 as a sum of worst-case union sizes, which is fine for an upper bound, but then asserts a list of 24 good sequences without proving they are distinct, that they all lie in B(x,y), or that the earlier branches actually produce them when the relevant Hamming distances exceed 1. If u is far from every single-deletion of αv, the branch that is supposed to contribute auβb, auβb, aw(1)βb, aw(2)βb may contribute nothing, and no compensation argument is given. That is a load-bearing gap: Theorem 4.8 (N=7) depends exactly on 'bad ≤ 6'. The total bound |B|≤30 may still be salvageable, but the second part of Lemma 3.8 is not proved as written.\n\nTwo smaller issues. Remark 2.8 asserts |R(n,P)| ≥ 3·2^{n−2} by analogy to [25, Lemma 2] without a proof, and that bound feeds the redundancy calculation in Theorem 4.6. The statement and derivation of |C_{n+21}| there are also garbled (the formula in the proof does not parse, and 'r(Cn+21)' should be 'red(Cn+21)'). These are presentation problems, likely fixable.\n\nOn circularity: none. The case analysis is standalone and the code constructions use pigeonhole arguments on established code sizes. No fitted parameters, no self-reference in the load-bearing steps.\n\nWho this is for: coding theorists working on reconstruction codes, and people applying error balls to DNA storage or racetrack memory. The main constructions for N=4n−8, 3n−4, 2n+9, and n+21 look like a genuine advance, provided Lemmas 3.2–3.6 survive a careful pass. The N=7 result should not be cited until the bad-sequence bound is fixed. I would send it to a serious referee: the paper has enough substance and novelty to merit the time, and the gap is a concrete, checkable one. My own verdict is conditional, leaning positive.","headline":"Strong new bounds for deletion-substitution reconstruction codes, with a real but localized gap in the N=7 result that needs a rigorous proof of the bad-sequence bound.","tokens_in":40965,"tokens_out":4225,"would_cite":true,"duration_ms":37728,"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":"The paper proves that binary reconstruction codes for one deletion plus one substitution exist at six redundancy levels, from zero redundancy at 4n−8 reads down to 3 log n+4 redundancy at seven reads.","keywords":["reconstruction codes","single-deletion single-substitution","error correction","deletion channel","substitution channel","redundancy","VT syndrome","binary codes"],"falsifier":"Enumerate all pairs of binary sequences of length $n$ for small $n$ (starting at $n=5$) and compute $|\\mathcal{B}(x)\\cap\\mathcal{B}(y)|$ directly; if any pair violates the claimed bound for its $(d,s)$ case, the corresponding lemma is false. In particular, test the equality cases of Lemma 3.2, such as $x=a\\alpha\\alpha b$ and $y=a\\overline{\\alpha}\\,\\overline{\\alpha} b$ with $r(a)=0$, $r(b)=n-2$, against the claimed $4n-9$ cap.","tokens_in":39932,"feed_emoji":"🧬","tokens_out":14533,"duration_ms":117443,"temperature":0.7,"pith_summary":"This paper asks how many distinct outputs of a channel that deletes one symbol and then substitutes one symbol are enough to identify a binary codeword uniquely, and what coding overhead is needed. It proves that codes with redundancy $0$, $1$, $2$, $\\log\\log n+3$, $\\log n+1$, and $3\\log n+4$ exist when the decoder receives $N=4n-8$, $3n-4$, $2n+9$, $n+21$, $31$, and $7$ distinct ball elements, respectively. The proof route is a bound on the intersection of two single-deletion single-substitution balls, showing the intersection is at most $(d+s)n+O(1)$ with $(d,s)\\in\\{0,1,2\\}\\times\\{0,2\\}$, followed by exact case constants. These low-redundancy trade-offs matter for settings such as DNA storage, where the same word is read multiple times.","feed_headline":"Seven reads recover words hit by one deletion and one substitution","feed_subtitle":"New bounds on error-ball intersections yield codes whose redundancy ranges from 0 to 3 log n + 4.","key_machinery":"The central object is the single-deletion single-substitution ball $\\mathcal{B}(x)$, the set of all length-$(n-1)$ sequences obtained from $x$ by deleting one position and substituting one position. The proof machinery is a decomposition of $\\mathcal{B}(x)\\cap\\mathcal{B}(y)$ into $\\mathcal{S}=\\bigcup_{z\\in D(x,y)} S(z)$, $\\mathcal{D}=\\bigcup_{z\\in S(x,y)} D(z)$, and a residual set $\\mathcal{B}$, combined with inclusion-exclusion; the residual is shown to be $O(1)$ by run-structure counts in Tables II to IV. The code constructions then add mild constraints such as inversion-number parity, run-count caps, and VT syndrome or list-size-two constraints, each chosen to rule out the high-intersection cases characterized in Lemmas 3.2 to 3.8.","core_discovery":"In the paper's own terms, the central claim is that for any two distinct binary strings $x$ and $y$ of length $n$, the intersection of their single-deletion single-substitution balls is bounded by a linear function determined by the pair $(d,s)=(|D(x,y)|,|S(x,y)|)$, and the six possible pairs give bounds $4n-9$, $3n-5$, $3n-7$, $2n+8$, $2n+4$, $n+20$, and $30$ for the appropriate cases. These constants are what make the code constructions in Theorems 4.1 to 4.8 work: the full space is an $(n,4n-8;\\mathcal{B})$-reconstruction code, the inversion-parity code is $(n,3n-4;\\mathcal{B})$, the run-limited parity code is $(n,2n+9;\\mathcal{B})$, the shifted run-limited code is $(n,n+21;\\mathcal{B})$, and the VT and list-decodable codes give $N=31$ and $N=7$. The statement is constructive: each code is explicit, and the listed $N$ values are exact thresholds for the reconstruction guarantee.","pith_inferences":["If the residual bounds in Lemmas 3.2 to 3.8 are tight only at extreme run distributions, typical codewords may require fewer reads than the worst-case $N$, so a probabilistic version could lower redundancy for practical DNA-storage read counts.","The same $\\mathcal{S}$–$\\mathcal{D}$–residual decomposition could be applied to $q$-ary alphabets or to compound edit channels such as two deletions plus one substitution, where analogous case tables might yield similar low-redundancy reconstruction codes.","The $N=7$ result suggests that list-decodability with list size two is essentially a constant-read reconstruction property for this channel, so other list-decodable codes may directly give reconstruction codes for other constant $N$."],"forward_implications":["No redundancy is required to reconstruct a codeword from $N=4n-8$ distinct single-deletion single-substitution ball elements.","One extra bit of redundancy lowers the required reads to $N=3n-4$, and a second bit lowers it to $N=2n+9$.","Restricting to sequences with few runs gives $N=n+21$ at only $\\log\\log n+3$ redundancy.","Classical VT codes are already $(n,31;\\mathcal{B})$-reconstruction codes, and the list-size-two list-decodable code of [33] is an $(n,7;\\mathcal{B})$-reconstruction code."],"supporting_citations":[{"why":"Supplies the VT-code construction that corrects one deletion or substitution and is used for the N=31 code.","marker":"[14]"},{"why":"Gives |S(x,y)| in {0,2}, the substitution-ball intersection bound used throughout the case analysis.","marker":"[15]"},{"why":"Gives |D(x,y)| in {0,1,2} and the structural forms of words with nontrivial deletion-ball intersection.","marker":"[6]"},{"why":"Supplies the single-deletion reconstruction code used in the N=n+21 construction.","marker":"[4]"},{"why":"Supplies the list-size-two list-decodable code used to obtain the N=7 reconstruction code.","marker":"[33]"},{"why":"Provides the argument for the size bound on R(n,P) that fixes the redundancy in Theorem 4.6.","marker":"[25, Lemma 2]"},{"why":"Gives the run-count bound used for the two-bit and log-log-n redundancy codes.","marker":"[17, Theorem 2]"},{"why":"Establishes that the order of deletion and substitution does not change the result, justifying the ball definition.","marker":"[31]"},{"why":"Supplies the lemma relating deletions from runs to Hamming distances, used in the counting claims.","marker":"[1, Lemma 5]"}],"fun_headline_variants":["Zero redundancy code for double-error balls at N=4n-8","Six thresholds map N to redundancy from 0 to 3 log n","Seven reads enough: explicit codes beat one-error redundancy","Ball intersection bounds yield exact N for reconstruction"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the exhaustive case analysis in Section V is complete: if any intersection term was missed in the run-count tables, or if the unproved bound on $|R(n,P)|$ fails, the code constructions can no longer be guaranteed.","fun_headline_variants_meta":{"raw":{"variants":["Zero redundancy code for double-error balls at N=4n-8","Six thresholds map N to redundancy from 0 to 3 log n","Seven reads enough: explicit codes beat one-error redundancy","Ball intersection bounds yield exact N for reconstruction"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000391,"raw_usage":{"total_tokens":2104,"prompt_tokens":1039,"completion_tokens":1065,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":655,"completion_tokens_details":{"reasoning_tokens":996}},"tokens_in":655,"tokens_out":1065,"duration_ms":11290,"temperature":1.0,"reasoning_tokens":996,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:34:50.715713+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all pairs of binary sequences of length $n$ for small $n$ (starting at $n=5$) and compute $|\\mathcal{B}(x)\\cap\\mathcal{B}(y)|$ directly; if any pair violates the claimed bound for its $(d,s)$ case, the corresponding lemma is false. In particular, test the equality cases of Lemma 3.2, such as $x=a\\alpha\\alpha b$ and $y=a\\overline{\\alpha}\\,\\overline{\\alpha} b$ with $r(a)=0$, $r(b)=n-2$, against the claimed $4n-9$ cap.","supporting_citations":[{"cited_title":"Efficient reconstruction of sequen ces,","cited_arxiv_id":null,"evidence_quote":"Gives |S(x,y)| in {0,2}, the substitution-ball intersection bound used throughout the case analysis."},{"cited_title":"Correcting del etions with multiple reads,","cited_arxiv_id":null,"evidence_quote":"Gives |D(x,y)| in {0,1,2} and the structural forms of words with nontrivial deletion-ball intersection."},{"cited_title":"Coding fo r sequence reconstruction for single edits,","cited_arxiv_id":null,"evidence_quote":"Supplies the single-deletion reconstruction code used in the N=n+21 construction."},{"cited_title":"List-decodable codes for single-deletion single-substitution with list-size t wo,","cited_arxiv_id":null,"evidence_quote":"Supplies the list-size-two list-decodable code used to obtain the N=7 reconstruction code."},{"cited_title":"Single-deletion single-substitution correcting codes,","cited_arxiv_id":null,"evidence_quote":"Establishes that the order of deletion and substitution does not change the result, justifying the ball definition."}],"review_version":1}