{
  "abstract": "The sequence reconstruction problem for $q$-ary deletion channels, introduced by Levenshtein in 2001, concerns the minimum number of channels required to uniquely recover a transmitted sequence when each channel introduces exactly $t$ deletions. Combinatorially, it is equivalent to determining $N_q(n,d,t)$, the maximum intersection size of two $t$-deletion balls with centers at Levenshtein distance at least $d$, for $q$-ary sequences of length $n$ over the alphabet \\(Σ_q=\\{0,1,\\dots,q-1\\}\\). Levenshtein solved the uncoded case $N_q(n,1,t)$ for all $n\\ge t$; subsequently, Gabrys and Yaakobi determined $N_2(n,2,t)$, and Wang et al. extended the result to $N_3(n,2,t)$. In this paper, we study the problem for \\(q\\)-ary sequences under minimum Levenshtein distance \\(d=2\\) with channels that introduce exactly \\(t\\) deletions. We determine the exact value of \\(N_q(n,2,t)\\) for all \\(t\\ge 2, q\\geq 4\\), and for sufficiently large \\(n\\), and construct explicit pairs of sequences attaining the maximum intersection. Furthermore, for each $q\\ge3$, we characterize all extremal sequence pairs. In particular, if the intersection size matches the first two terms of \\(N_q(n,2,t)\\), then the two center sequences must contain, at the same positions, length-5 blocks of the forms \\((a,b,c,a,b)\\) and \\((b,a,c,b,a)\\) for some distinct \\(a,b,c\\inΣ_q\\); for \\(t\\ge q+2\\), the exact maximum \\(N_q(n,2,t)\\) is attained precisely by \\(2q!\\) unordered pairs of sequences with a specific block structure. Asymptotically, we prove that for \\(q\\ge 4\\) and \\(t\\ge 2\\), \\[ N_q(n,2,t)=\\frac{6}{(t-2)!}n^{t-2}-\\frac{3t+13}{(t-3)!}n^{t-3}+\\frac{3t^2+25t+64}{4(t-4)!}n^{t-4}+O(n^{t-5}). \\] Moreover, \\(N_q(n,2,t)\\) and \\(N_{q-1}(n,2,t)\\) share their first \\(q-1\\) terms, and for \\(t\\ge q\\) the coefficient of \\(n^{t-q}\\) in their difference is \\(\\frac{6t-6q+5}{(t-q)!}\\).",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.16837",
  "author_total": 3,
  "authors": [
    {
      "name": "Xiang Wang"
    },
    {
      "name": "Han Li"
    },
    {
      "name": "Fang-Wei Fu"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/14mx2g5ft5qcd.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.16837",
  "fulltext_url": null,
  "id": "14mx2g5ft5qcd",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.16837",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.IT"
    ],
    [
      "arxiv",
      "math.IT"
    ],
    [
      "openalex",
      "1702|Coding theory and cryptography"
    ]
  ],
  "openalex": "W7213393839",
  "pdf_url": "https://arxiv.org/pdf/2609.16837",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-15",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/14mx2g5ft5qcd.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:21:45Z",
      "native_id": "2609.16837",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.16837"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.IT",
      "subfield": "general"
    }
  ],
  "title": "On Sequence Reconstruction Problem for q-ary Deletion Channels",
  "title_text": "On Sequence Reconstruction Problem for q-ary Deletion Channels",
  "type": "preprint",
  "updated_at": "2026-10-30T12:21:45Z",
  "url": "https://research.draconitic.com/paper/14mx2g5ft5qcd",
  "venue": "arXiv",
  "versions": []
}