On Sequence Reconstruction Problem for q-ary Deletion Channels

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 ${\mathrm{\Sigma }}_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\ge 4$, and for sufficiently large $n$, and construct explicit pairs of sequences attaining the maximum intersection. Furthermore, for each $q\ge 3$, 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 {\mathrm{\Sigma }}_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})\mathrm{.}$$ 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)!}$.