# The Levenshtein’s Sequence Reconstruction Problem and the Length of the
List††thanks: This paper was presented in part at the $2022$ IEEE
International Symposium on Information Theory (ISIT2022) (see [1]). ††thanks:
The authors were funded in part by the Academy of Finland grant 338797 and the
third author was funded by the Finnish Cultural Foundation.

Ville Junnila, Tero Laihonen and Tuomo Lehtilä The authors are currently with
the Department of Mathematics and Statistics, University of Turku, Turku
FI-20014, Finland (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>tualeh@utu.fi).Much
of the work of the third author was done when he was in Univ Lyon, Université
Claude Bernard, CNRS, LIRIS - UMR 5205, F69622, France.

###### Abstract

In the paper, the Levenshtein’s sequence reconstruction problem is considered
in the case where at most $t$ substitution errors occur in each of the $N$
channels and the decoder outputs a list of length $\mathcal{L}$. Moreover, it
is assumed that the transmitted words are chosen from an $e$-error-correcting
code $C\ (\subseteq\\{0,1\\}^{n})$. Previously, when $t=e+\ell$ and the length
$n$ of the transmitted word is large enough, the numbers of required channels
are determined for $\mathcal{L}=1,2\text{ and }\ell+1$. Here we determine the
exact number of channels in the cases $\mathcal{L}=3,4,\ldots,\ell$.
Furthermore, with the aid of covering codes, we also consider the list sizes
in the cases where the length $n$ is rather small (improving previously known
results). After that we study how much we can decrease the number of required
channels when we use list-decoding codes. Finally, the majority algorithm is
discussed for decoding in a probabilistic set-up; in particular, we show that
with high probability a decoder based on it is verifiably successful, i.e.,
the output word of the decoder can be verified to be the transmitted one.

Keywords: Information Retrieval, Levenshtein’s Sequence Recontruction, List
Decoding, Majority Algorithm, Sauer-Shelah Lemma, Substitution Errors.

##  1 Introduction

In this paper, the Levenshtein’s _sequence reconstruction problem_ , which was
introduced in [2], is studied when the errors are substitution errors. For
many related sequence reconstruction problems (concerning, for instance,
deletion and insertion errors) consult, for example, [2, 3, 4, 5, 6, 7, 8].
Originally, the motivation for the sequence reconstruction problem came from
biology and chemistry where the familiar redundancy method of error correction
is not suitable. The sequence reconstruction problem has come back to the
focus, since it was recently pointed out that this problem is highly relevant
to information retrieval in advanced storage technologies where the stored
information is either a single copy, which is read many times, or the stored
information has several copies [5, 9]. This problem (see [5]) is especially
applicable to DNA data storage systems (see [10, 11, 12, 13]) where DNA
strands provide numerous erroneous copies of the information and the goal is
to recover the information using these copies.

Let us denote the set $\\{1,2,\dots,n\\}$ by $[1,n].$ Denote by $\mathbb{F}$
the finite field of two elements, and denote the binary Hamming space by
$\mathbb{F}^{n}$. The _support_ of the word $\mathbf{x}=x_{1}\dots
x_{n}\in\mathbb{F}^{n}$ is defined via $\textrm{supp}(\mathbf{x})=\\{i\mid
x_{i}\neq 0\\}.$ Let us denote the all-zero word $\mathbf{0}=00\dots
0\in\mathbb{F}^{n}$ and by $\mathbf{e}_{i}\in\mathbb{F}^{n}$ a word with $1$
in the $i$th coordinate and zeros elsewhere. The _Hamming weight_
$w(\mathbf{x})$ of $\mathbf{x}\in\mathbb{F}^{n}$ is
$|\textrm{supp}(\mathbf{x})|$. The _Hamming distance_ is defined as
$d(\mathbf{x},\mathbf{y})=w(\mathbf{x}+\mathbf{y})$ for
$\mathbf{x},\mathbf{y}\in\mathbb{F}^{n}$. Let us denote the _Hamming ball_ of
radius $t$ centered at $\mathbf{x}\in\mathbb{F}^{n}$ by
$B_{t}(\mathbf{x})=\\{\mathbf{y}\in\mathbb{F}^{n}\mid
d(\mathbf{x},\mathbf{y})\leq t\\}$ and its cardinality by
$V(n,t)=\sum_{i=0}^{t}\binom{n}{i}$. A nonempty subset of $\mathbb{F}^{n}$ is
called a _code_ and its elements are called _codewords_. The _minimum
distance_ of a code $C\subseteq\mathbb{F}^{n}$ is defined as
$d_{\textrm{min}}(C)=\min_{\mathbf{c}_{1},\mathbf{c}_{2}\in
C,\mathbf{c}_{1}\neq\mathbf{c}_{2}}d(\mathbf{c}_{1},\mathbf{c}_{2}).$
Consequently, the code $C$ has the error-correcting capability
$e=e(C)=\lfloor(d_{\textrm{min}}(C)-1)/2\rfloor.$

Next we consider the sequence reconstruction problem. For the rest of the
paper, let $C\subseteq\mathbb{F}^{n}$ be any $e$-error-correcting code. A
codeword $\mathbf{x}\in C$ is transmitted through $N$ channels where, in each
of them, at most $t$ substitution errors can occur. In the sequence
reconstruction problem, our aim is to reconstruct $\mathbf{x}$ based on the
$N$ distinct outputs $Y=\\{\mathbf{y}_{1},\dots,\mathbf{y}_{N}\\}$ from the
channels (see Fig. 1).

Figure 1: The Levenshtein’s sequence reconstruction.

It is assumed that $t>e(C)$ (if $t\leq e(C),$ then only one channel is enough
to reconstruct $\mathbf{x}$). For $\ell\geq 1$, let us denote

$t=e(C)+\ell=e+\ell$

for the rest of paper. The situation where we obtain sometimes a short list of
possibilities for $\mathbf{x}$ instead of always recovering $\mathbf{x}$
uniquely, is considered in [14, 15]. Based on the set $Y$ and the code $C$,
the list decoder (see Fig. 1) $\mathcal{D}$ gives an estimation
$T_{\mathcal{D}}=T_{\mathcal{D}}(Y)=\\{\mathbf{x}_{1},\dots,\mathbf{x}_{|T_{\mathcal{D}}|}\\}$
on the sequence $\mathbf{x}$ which we try to reconstruct. We denote by
$\mathcal{L_{D}}$ the maximum cardinality of the list $T_{\mathcal{D}}(Y)$
over all possible sets $Y$ of output words. The decoder is said to be
_successful_ if $\mathbf{x}\in T_{\mathcal{D}}$. In this paper, we focus on
the smallest possible value of $\mathcal{L_{D}}$ over all successful decoders
$\mathcal{D}$, in other words, on $\mathcal{L}=\min_{\mathcal{D}\text{ is
successful}}\\{\mathcal{L_{D}}\\}$. Let us denote

$T=T(Y)=C\cap\left(\bigcap_{\mathbf{y}\in Y}B_{t}(\mathbf{y})\right).$

Consequently,

$\mathcal{L}=\max\\{|T(Y)|\mid Y\text{ is a set of }N\text{ output words}\\}.$

The value $\mathcal{L}$ depends on $e,\ell,n$ and $N$. Obviously, one would
like to have as small $\mathcal{L}$ as possible. Observe that we consider the
worst case scenario of the output channels regarding $\mathcal{L}$. In such a
situation, the channels are sometimes called adversarial; for example, see
[16]. The problem of minimizing $\mathcal{L}$ is studied, for example, in [14,
15, 17, 18, 19, 20]. Also a probabilistic versions of this problem have been
studied (often under the name trace reconstruction) for example in [21, 22].
In this paper, we mainly consider the relation between $N$ and $\mathcal{L}$
for various $n$ after we fix two parameters $\ell$ and $e$ (while letting $C$
be any $e$-error-correcting code). The sequence reconstruction problem is also
closely related (see [17]) to _information retrieval in associative memory_
introduced by Yaakobi and Bruck [14, 15].

The structure of the paper is as follows. In Section 2, we recall some of the
known results. In particular, it is pointed out that if we have at least
(resp. less than) $V(n,\ell-1)+1$ channels, then the list size is constant
with respect to $n$ (resp. there are $e$-error-correcting codes with list size
depending on $n$). In Section 3, we give the complete correspondence between
the list size and the number of channels when we have more than
$V(n,\ell-1)+1$ channels and $n$ is large enough. It is sometimes enough to
increase the number of channels only by a constant amount in order to decrease
the list size (see Corollary 13). Section 4 focuses on improving the bounds on
the list size when $n$ is not restricted and we obtain strictly more channels
than $V(n,\ell-1)+1$. Section 5 is devoted to list size when we have _less_
than $V(n,\ell-1)+1$ channels. The final section deals with the reconstruction
with the aid of a majority algorithm on the coordinates among the output words
in $Y$.

##  2 Known results

In this section we present some known results on how the two values $N$ and
$\mathcal{L}$ are linked. The basic idea on estimating $\mathcal{L}$ is the
following: we analyse the maximum number of output words ($N$) we can fit in
the intersection of $\mathcal{L}$ $t$-radius balls centered at codewords. As
expected, the length $\mathcal{L}$ of the outputted list strongly depends on
the number of channels.

Previously, in [2] and [14], the problem has been considered for
$\mathcal{L}=1$ and $\mathcal{L}=2$, respectively. Moreover, in [23], the
exact number of channels $N$ required to have $\mathcal{L}$ constant on $n$
has been presented, see Theorems 4 and 5. Following theorem gives an exact
number of channels required to have $\mathcal{L}=1$.

######  Theorem 1 ([2]).

We have $\mathcal{L}\leq 1$ if

$N\geq\sum_{i=0}^{\ell-1}\binom{n-2e-1}{i}\sum^{t-i}_{k=e+1+i-\ell}\binom{2e+1}{k}+1.$

######  Theorem 2 ([14]).

If
$N\geq\sum_{i_{1},i_{2},i_{3},i_{4}}\binom{n-\lceil\frac{3d}{2}\rceil}{i_{1}}\binom{\lceil\frac{d}{2}\rceil}{i_{2}}\binom{\lceil\frac{d}{2}\rceil}{i_{3}}\binom{\lfloor\frac{d}{2}\rfloor}{i_{4}}+1$
for

  * •

$0\leq i_{1}\leq t-\lceil\frac{d}{2}\rceil$,

  * •

$i_{1}+\lfloor\frac{d}{2}\rfloor-t\leq i_{4}\leq t-\lceil\frac{d}{2}\rceil-
i_{1}$,

  * •

$2\lceil\frac{d}{2}\rceil-t+i_{1}\leq i_{3}\leq t-(i_{1}+i_{4})$ and

  * •

$\max\\{i_{1}-i_{3}-i_{4}+\lceil\frac{3d}{2}\rceil-t,i_{1}+i_{3}+i_{4}+\lceil\frac{d}{2}\rceil-t\\}\leq
i_{2}\leq t-(i_{1}+i_{4}+\lceil\frac{d}{2}\rceil-i_{3})$,

then $\mathcal{L}\leq 2$ for any code $C$ with minimum distance $d$.

The next result is a a reformulation of a result by Yaakobi and Bruck [14,
Algorithm 18] proven in [23].

######  Theorem 3.

Let $n\geq 2\ell-1$ and $C$ be an $e$-error-correcting code in
$\mathbb{F}^{n}$. If $N\geq V(n,\ell-1)+1$, then we have

$\mathcal{L}\leq\binom{2\ell}{\ell}.$

The bound in Theorem 3 can be improved to $2^{\ell}$ which has been shown to
be tight in [23].

######  Theorem 4 (Theorem $7$, [23]).

Let $n\geq\ell$ and $C$ be an $e$-error-correcting code in $\mathbb{F}^{n}$.
If $t=e+\ell$ and $N\geq V(n,\ell-1)+1$, then we have

$\mathcal{L}\leq 2^{\ell}.$

Besides the $2^{\ell}$ part, also the value $V(n,\ell-1)+1$ for the number of
channels is tight, that is, if the value for $N$ is less, then list size
$\mathcal{L}$ can be linear with respect to $n$.

######  Theorem 5 (Theorem $10$, [23]).

If $N\leq V(n,\ell-1)$, then there exists an $e$-error-correcting code such
that $\mathcal{L}\geq\lfloor n/(e+1)\rfloor$.

Let us denote for the rest of the paper

$\displaystyle
n(e,\ell,b)=(\ell-1)^{2}\left(b-e+(e+1)\left(b-3e-2e^{2}+eb+\binom{b-2e-1}{2}\right)\right)+\ell-2.$

Although the bound for $\mathcal{L}$ in Theorem 4 cannot be improved in
general, we can improve it, when $n$ is large, to $\ell+1$.

######  Theorem 6 (Theorem $20$, [23]).

Let $n\geq n(e,\ell,b)$, $b=\max\\{3t,4e+4\\}$, $|Y|=N\geq V(n,\ell-1)+1$ and
$C$ be an $e$-error-correcting code. Then we have

$\mathcal{L}\leq\ell+1.$

Moreover, the bound $\ell+1$ is tight.

######  Theorem 7 (Theorem $9$, [23]).

There exists an $e$-error-correcting code $C\subseteq\mathbb{F}_{2}^{n}$ such
that $\mathcal{L}\geq\ell+1$ if $n\geq\ell+\ell e+e$ and the number of
channels satisfies $N\leq V(n,\ell-1)+1$.

Finally, in [14, Theorem $6$], the authors have given exact number of channels
required to have $\mathcal{L}\leq 2$. All in all, $N$ is known precisely only
for these three values when $\mathcal{L}$ is constant on $n$. In the following
section, we give the missing values for $N$.

##  3 List size with more channels

In this section, we give exact bounds for the number of channels $N=N_{h}+1$
(when $n$ is large) which is required for satisfying $\mathcal{L}<h$ for every
constant value $h$. Previously, $N_{h}$ was known only for three values
$h=2,3,\ell+2$. To achieve this, we need to introduce two technical lemmas
from [23].

In the following lemma, when $n$ is large, it is shown that if any three
codewords in $T(Y)$ differ within some subset of coordinates $\overline{D}$ of
constant size $b$, then there exists an output word $\mathbf{y}$ which differs
from these codewords in at least $\ell-1$ coordinate positions outside of
$\overline{D}$. Notice that $\textrm{supp}(\mathbf{w}+\mathbf{z})$ gives the
set of coordinates in which $\mathbf{w}$ and $\mathbf{z}$ differ.

######  Lemma 8 (Lemma $18$, [23]).

Let $b\geq 3t$ be an integer with $t=e+\ell$ and $C_{1}$ be an $e$-error-
correcting code. Assume that $n\geq n(e,\ell,b)$, $|Y|=N\geq V(n,\ell-1)+1$,
$|T(Y)|\geq 3$ and $\mathbf{c}_{0},\mathbf{c}_{1},\mathbf{c}_{2}\in T(Y)$. If
now $\overline{D}\subseteq[1,n]$ is a set such that $|\overline{D}|=b$ and

$\textrm{supp}(\mathbf{c}_{0}+\mathbf{c}_{1})\cup\textrm{supp}(\mathbf{c}_{0}+\mathbf{c}_{2})\cup\textrm{supp}(\mathbf{c}_{1}+\mathbf{c}_{2})\subseteq\overline{D}\text{,}$

then for any word $\mathbf{w}\in\mathbb{F}^{n}$ we have
$\textrm{supp}(\mathbf{w}+\mathbf{c}_{0})\setminus\overline{D}=\textrm{supp}(\mathbf{w}+\mathbf{c}_{1})\setminus\overline{D}=\textrm{supp}(\mathbf{w}+\mathbf{c}_{2})\setminus\overline{D}$
and there exists an output word $\mathbf{y}\in Y$ such that

$|\textrm{supp}(\mathbf{y}+\mathbf{c}_{0})\setminus\overline{D}|\geq\ell-1.$

The following lemma shows that the distance between any codewords in $T(Y)$ is
either $2e+1$ or $2e+2$.

######  Lemma 9 (Lemma $19$, [23]).

Let $n\geq n(e,\ell,3t)$, $|Y|=N\geq V(n,\ell-1)+1$, $C$ be an $e$-error-
correcting code and $|T(Y)|\geq 3$. Then we have
$d(\mathbf{c}_{1},\mathbf{c}_{2})\leq 2e+2$ for any two
$\mathbf{c}_{1},\mathbf{c}_{2}\in T(Y)$.

We denote by $N^{\prime}(n,\ell,e,h)$ the maximum number of $t$-error channels
such that there exists a set of output words $Y\subseteq\mathbb{F}^{n}$
satisfying $|Y|=N^{\prime}(n,\ell,e,h)$ and $|T(Y)|\geq h$ for some $e$-error
correcting code $C$. By Theorems 5 and 6, $N^{\prime}(n,\ell,e,h)=V(n,\ell-1)$
for all $\ell+2\leq h\leq\lfloor n/(e+1)\rfloor$ when $n$ is large enough.
Hence, when we use notation $N(n,\ell,e,h)$, we assume that $h$ is the
smallest integer for which
$N^{\prime}(n,\ell,e,h)=N^{\prime}(n,\ell,e,h^{\prime})$. When the exact
formulation is not necessary for clarity, we denote $N(n,\ell,e,h)=N_{h}$.
Observe that, if $N\geq N_{h}+1$, then $\mathcal{L}<h$ for all $e$-error-
correcting codes. In particular, the difference between
$N^{\prime}(n,\ell,e,h)$ and $N(n,\ell,e,h)$ is that $N^{\prime}(n,\ell,e,h)$
exists for each value of $h$ but may give the same values for different
choices of $h$ while $N(n,\ell,e,h)$ does not exist for every choice of $h$
but each value it attains is unique.

We need the following two technical notations in the next theorem. Let us have
$N_{h}$ channels, then

$\displaystyle W_{w}=$ $\displaystyle\left\\{(i_{1},\dots,i_{h})\mid\text{for
each }j:\right.$ $\displaystyle\left.i_{j}\in\mathbb{N},e+1\geq
i_{j}\geq\frac{w+1-\ell}{2}\text{ and }w\geq\sum_{j=1}^{h}i_{j}\right\\}$

and

$\displaystyle W^{\prime}_{w}=$
$\displaystyle\left\\{(i_{1},\dots,i_{h})\mid\text{each
}i_{j}\in\mathbb{N},e\geq i_{1}\geq\frac{w-\ell}{2}\text{ and for }\right.$
$\displaystyle\left.j\geq 2:e+1\geq i_{j}\geq\frac{w+1-\ell}{2}\text{ and
}w\geq\sum_{j=1}^{h}i_{j}\right\\}.$

In the following theorem, we give the maximum number of channels $N_{h}$ which
gives list size $\mathcal{L}=h$ for some $e$-error-correcting code and if
$N>N_{h}$, then $\mathcal{L}<h$ for all $e$-error-correcting codes.

######  Theorem 10.

Let $n\geq n(e,\ell,b)$, $b\geq\max\\{3t,4e+4\\}$, $\ell\geq 2$, $3\leq
h\leq\ell+1$. Then

$\displaystyle N(n,\ell,e,h)=N_{h}=V(n,\ell-1)+$
$\displaystyle\max\left\\{\sum_{w\geq\ell}\sum_{(i_{1},\dots,i_{h})\in
W_{w}}\binom{n-h(e+1)}{w-\sum_{j=1}^{h}i_{j}}\prod_{j=1}^{h}\binom{e+1}{i_{j}},\right.$
$\displaystyle\left.\sum_{w\geq\ell}\sum_{(i_{1},\dots,i_{h})\in
W^{\prime}_{w}}\binom{n+1-h(e+1)}{w-\sum_{j=1}^{h}i_{j}}\binom{e}{i_{1}}\prod_{j=2}^{h}\binom{e+1}{i_{j}}\right\\}.$

###### Proof.

Let us have $N=N(n,\ell,e,h)$, $n\geq n(e,\ell,b)$, $b\geq\max\\{3t,4e+4\\}$,
$\ell\geq 2$ and $3\leq h\leq\ell+1$. Moreover, let $C$ be such an $e$-error-
correcting code, that it maximizes $\mathcal{L}$ (we have $\mathcal{L}=h$)
when $N=N(n,\ell,e,h)$. Furthermore, let $Y$ be a set of outputs such that
$|T(Y)|=\mathcal{L}=h$ and let us denote
$T(Y)=\\{\mathbf{c}_{1},\dots,\mathbf{c}_{h}\\}$.

By Theorem 5, we have $N\geq V(n,\ell-1)+1$. Since $C$ is an $e$-error-
correcting code and by Lemma 9, we have
$d(\mathbf{c}_{i},\mathbf{c}_{j})\in\\{2e+1,2e+2\\}$ for each $i\neq j$. Since
we are considering binary Hamming space and $h\geq 3$, all pairwise distances
cannot be $2e+1$. Let us assume without loss of generality that
$d(\mathbf{c}_{1},\mathbf{c}_{2})=2e+2$ and let us then translate the Hamming
space so that $\mathbf{c}_{1}=\mathbf{0}$. Now $w(\mathbf{c}_{2})=2e+2$ and
$w(\mathbf{c}_{3})\in\\{2e+1,2e+2\\}$. Moreover,
$|\textrm{supp}(\mathbf{c}_{2})\cap\textrm{supp}(\mathbf{c}_{3})|=e+1$. Let
$\overline{D}$ be any subset of $[1,n]$ satisfying
$\textrm{supp}(\mathbf{c}_{1}+\mathbf{c}_{2})\cup\textrm{supp}(\mathbf{c}_{1}+\mathbf{c}_{3})\cup\textrm{supp}(\mathbf{c}_{2}+\mathbf{c}_{3})\subseteq\overline{D}$
and $|\overline{D}|=b$. Observe that
$\textrm{supp}(\mathbf{c}_{1})\setminus\overline{D}=\textrm{supp}(\mathbf{c}_{2})\setminus\overline{D}=\textrm{supp}(\mathbf{c}_{3})\setminus\overline{D}=\emptyset$.

By Lemma 8, there exists an output word $\mathbf{y}\in Y$ such that
$|\textrm{supp}(\mathbf{c}_{1}+\mathbf{y})\setminus\overline{D}|\geq\ell-1$.
Since $d(\mathbf{y},\mathbf{c}_{2})\leq t$, we have
$|\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}_{2})|\geq e+1$.
Moreover, since $d(\mathbf{y},\mathbf{c}_{1})\leq t$, we have
$w(\mathbf{y})\leq t$ and hence,
$|\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}_{2})|=e+1$. Thus,
$\textrm{supp}(\mathbf{y})=(\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}_{2}))\cup(\textrm{supp}(\mathbf{y})\setminus\overline{D})$
and
$\textrm{supp}(\mathbf{y})\cap(\textrm{supp}(\mathbf{c}_{3})\setminus\textrm{supp}(\mathbf{c}_{2}))=\emptyset$.
Hence,
$\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}_{3})\subseteq\textrm{supp}(\mathbf{c}_{2})$
and moreover,
$\textrm{supp}(\mathbf{y})\cap(\textrm{supp}(\mathbf{c}_{2})\setminus\textrm{supp}(\mathbf{c}_{3}))=\emptyset$
as otherwise $d(\mathbf{y},\mathbf{c}_{3})\geq(\ell-1+1)+(2e+1-e)=t+1>t$ (a
contradiction). Together these give that
$\textrm{supp}(\mathbf{y})\cap\overline{D}=\textrm{supp}(\mathbf{c}_{2})\cap\textrm{supp}(\mathbf{c}_{3})$.
Notice that for each $i\in[4,h]$ we may choose $\overline{D}$ in such a way
that also $\textrm{supp}(\mathbf{c}_{i})\subseteq\overline{D}$ since
$|\overline{D}|=b\geq 4e+4$. Thus, there exists an output word
$\mathbf{y}^{\prime}\in Y$ such that
$|\textrm{supp}(\mathbf{c}_{1}+\mathbf{y}^{\prime})\setminus\overline{D}|\geq\ell-1$.
Therefore, as above,
$\textrm{supp}(\mathbf{y}^{\prime})\cap\overline{D}=\textrm{supp}(\mathbf{c}_{2})\cap\textrm{supp}(\mathbf{c}_{i})$
and
$\textrm{supp}(\mathbf{y}^{\prime})\cap\overline{D}=\textrm{supp}(\mathbf{c}_{2})\cap\textrm{supp}(\mathbf{c}_{3})$
implying
$\textrm{supp}(\mathbf{c}_{2})\cap\textrm{supp}(\mathbf{c}_{i})=\textrm{supp}(\mathbf{c}_{2})\cap\textrm{supp}(\mathbf{c}_{3})$.
Finally, translate the Hamming space so that the word $\mathbf{z}$ with
$\textrm{supp}(\mathbf{z})=\textrm{supp}(\mathbf{c}_{2})\cap\textrm{supp}(\mathbf{c}_{3})$
becomes $\mathbf{z}=\mathbf{0}$. Then we have
$w(\mathbf{c}_{i})\in\\{e,e+1\\}$ (for $i\in[1,h]$) and
$\textrm{supp}(\mathbf{c}_{i})\cap\textrm{supp}(\mathbf{c}_{j})=\emptyset$ for
each $i\neq j$ since $d(\mathbf{c}_{i},\mathbf{c}_{j})\in\\{2e+1,2e+2\\}$.
Moreover, at most one of $\mathbf{c}_{i}$ can have weight $e$ by the minimum
distance of $C$.

Let us then count the number of words in
$\bigcap_{i=1}^{h}B_{t}(\mathbf{c}_{i})$. Observe that if
$|Y|>|\bigcap_{i=1}^{h}B_{t}(\mathbf{c}_{i})|$, then we cannot have $h$
codewords in $T(Y)$ but if $|Y|=|\bigcap_{i=1}^{h}B_{t}(\mathbf{c}_{i})|$,
then we can have $h$ codewords in $T(Y)$. Clearly, each word $\mathbf{y}$ with
$w(\mathbf{y})\leq\ell-1$ belongs to the intersection contributing
$V(n,\ell-1)$ words to it. Assume then that $w(\mathbf{y})=w\geq\ell$. As
$d(\mathbf{y},\mathbf{c}_{j})\leq t$ for all $j\in[1,h]$, we have
$w(\mathbf{y})+w(\mathbf{c}_{j})-2|\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}_{j})|\leq
t$. Denote
$i_{j}=|\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}_{j})|$. Assume
first that $w(\mathbf{c}_{j})=e+1$ for all $j$. Then $\mathbf{y}\in
B_{t}(\mathbf{c}_{j})$ if and only if we have $w+e+1-2i_{j}\leq t$. Hence,
$e+1\geq i_{j}\geq(w+1-\ell)/2$. Moreover, $\sum_{j=1}^{h}i_{j}\leq w$ since
$w(\mathbf{y})=w$ and
$\textrm{supp}(\mathbf{c}_{j_{1}})\cap\textrm{supp}(\mathbf{c}_{j_{2}})=\emptyset$
for each $j_{1}\neq j_{2}$. In other words,
$\mathbf{y}\in\bigcap_{i=1}^{h}B_{t}(\mathbf{c}_{i})$ if and only if
$(i_{1},\dots,i_{h})\in W_{w}$. Hence, there exist
$\sum_{(i_{1},\dots,i_{h})\in
W_{w}}\binom{n-h(e+1)}{w-\sum_{j=1}i_{j}}\prod_{i_{j}=1}^{h}\binom{e+1}{i_{j}}$
words of weight $w\geq\ell$ in $\bigcap_{i=1}^{h}B_{t}(\mathbf{c}_{i})$.

In the case where $w(\mathbf{c}_{k})=e$ for some $k$, say $k=1$, we have
$e\geq i_{1}\geq(w-\ell)/2$. Thus,
$\mathbf{y}\in\bigcap_{i=1}^{h}B_{t}(\mathbf{c}_{i})$ if and only if
$(i_{1},\dots,i_{h})\in W_{w}^{\prime}$. Hence, there exist
$\sum_{(i_{1},\dots,i_{h})\in
W_{w}^{\prime}}\binom{n+1-h(e+1)}{w-\sum_{j=1}i_{j}}\binom{e}{i_{1}}\cdot$
$\prod_{i_{j}=2}^{h}\binom{e+1}{i_{j}}$ words of weight $w\geq\ell$ in
$\bigcap_{i=1}^{h}B_{t}(\mathbf{c}_{i})$. Together these give the claim.∎

Observe by the proof that the bounds given in Theorem 10 are tight. Notice
that geometrically the output sets giving maximal list size are more
complicated than, for example, in Theorem 5 (where a ball of volume
$V(n,\ell-1)$ is essential). If we increase $N$ by one, then $\mathcal{L}$
decreases by one since we cannot place the output word within the intersection
of $t$-balls centered at codewords in $T(Y)$. Another observation is that
although the sums do not include an upper bound for $w$, there is one. Namely
the definition, for $W_{w}$, gives that $w\leq 2e+\ell+1$ and for
$W_{w}^{\prime}$ that $w\leq 2e+\ell$.

In the following theorem, we improve the previous result by showing that the
two binomial sums within the $\max$ are actually equal.

######  Theorem 11.

Let $n\geq n(e,\ell,b)$, $b\geq\max\\{3t,4e+4\\}$, $\ell\geq 2$, $3\leq
h\leq\ell+1$. Then

$\displaystyle N(n,\ell,e,h)-V(n,\ell-1)$
$\displaystyle=\sum_{w\geq\ell}\sum_{(i_{1},\dots,i_{h})\in
W_{w}}\binom{n-h(e+1)}{w-\sum_{j=1}^{h}i_{j}}\prod_{j=1}^{h}\binom{e+1}{i_{j}}$
$\displaystyle=\sum_{w\geq\ell}\sum_{(i_{1},\dots,i_{h})\in
W^{\prime}_{w}}\binom{n+1-h(e+1)}{w-\sum_{j=1}^{h}i_{j}}\binom{e}{i_{1}}\prod_{j=2}^{h}\binom{e+1}{i_{j}}.$

###### Proof.

Observe that the claim follows from Theorem 10 if we can prove that the two
binomial sums in the claim are equal. For that, we will be considering subsums

$\displaystyle S_{a}=$
$\displaystyle\sum_{w=\ell+2a}^{\ell+2a+1}\sum_{(i_{1},\dots,i_{h})\in
W_{w}}\left(\binom{n-h(e+1)}{w-\sum_{j=1}^{h}i_{j}}\prod_{j=1}^{h}\binom{e+1}{i_{j}}\right)$
(1)

and

$\displaystyle S^{\prime}_{a}=$
$\displaystyle\sum_{w=\ell+2a}^{\ell+2a+1}\sum_{(i_{1},\dots,i_{h})\in
W^{\prime}_{w}}\left(\binom{n+1-h(e+1)}{w-\sum_{j=1}^{h}i_{j}}\binom{e}{i_{1}}\prod_{j=2}^{h}\binom{e+1}{i_{j}}\right).$
(2)

We claim that $S_{a}=S^{\prime}_{a}$ for each non-negative integer $a$. When
$w=\ell+2a$ we have

$\displaystyle W_{\ell+2a}=\left\\{(i_{1},\dots,i_{h})\mid\text{for each
}j:i_{j}\in\mathbb{N},e+1\geq i_{j}\geq a+1\text{ and
}\ell+2a\geq\sum_{j=1}^{h}i_{j}\right\\}$

and

$\displaystyle W^{\prime}_{\ell+2a}=\left\\{(i_{1},\dots,i_{h})\mid\text{each
}i_{j}\in\mathbb{N},e\geq i_{1}\geq a\text{ and for }\right.$
$\displaystyle\left.j\geq 2:e+1\geq i_{j}\geq a+1\text{ and
}\ell+2a\geq\sum_{j=1}^{h}i_{j}\right\\}.$

Moreover, for $w=\ell+2a+1$ we have

$\displaystyle W_{\ell+2a+1}=\left\\{(i_{1},\dots,i_{h})\mid\text{for each
}j:i_{j}\in\mathbb{N},e+1\geq i_{j}\geq a+1\text{ and
}\ell+2a+1\geq\sum_{j=1}^{h}i_{j}\right\\}$

and

$\displaystyle
W^{\prime}_{\ell+2a+1}=\left\\{(i_{1},\dots,i_{h})\mid\text{each
}i_{j}\in\mathbb{N},e\geq i_{1}\geq a+1\text{ and for }\right.$
$\displaystyle\left.j\geq 2:e+1\geq i_{j}\geq a+1\text{ and
}\ell+2a+1\geq\sum_{j=1}^{h}i_{j}\right\\}.$

Assume now that the codewords $\mathbf{c}_{i}\in T(Y)$ are arranged as in the
proof of Theorem 10, that is, each codeword has weight of $e$ or $e+1$. Hence,
their supports do not intersect. Recall that we have at most one codeword with
weight $e$ and if that word exists, then we are using set $W^{\prime}_{w}$ in
our binomial sum. For further rearranging of the Hamming space, we assume that
if each word has weight $e+1$, then
$\textrm{supp}(\mathbf{c}_{i})=[(e+1)(i-1)+1,(e+1)i]$ and if there exists a
word with weight $e$, it is denoted by $\mathbf{c}^{\prime}_{1}$ (replacing
$\mathbf{c}_{1}$) and we have
$\textrm{supp}(\mathbf{c}^{\prime}_{1})=[2,e+1]$.

Recall that $w$ describes the weight of a word
$\mathbf{y}_{i}\in\bigcap_{\mathbf{c}\in T(Y)}B_{t}(\mathbf{c})$ in the proof
of Theorem 10 within the notations $W_{w}$ and $W^{\prime}_{w}$. When
$w(\mathbf{y}_{i})=w=2a+\ell$ and we are considering case $S_{a}$, then
$|\textrm{supp}(\mathbf{y}_{i})\cap\textrm{supp}(\mathbf{c}_{j})|=i_{j}\geq
a+1$. Let us denote by $Y_{2a}$, $Y_{2a+1}$, $Y^{\prime}_{2a}$ and
$Y^{\prime}_{2a+1}$ the sets of output words contributing to the sums $S_{a}$
and $S^{\prime}_{a}$, respectively, where $Y_{w}$ (resp. $Y^{\prime}_{w}$)
contains output words of weight $w+\ell$. Let us denote by $D=[h(e+1)+1,n]$.

We will construct the proof by first showing that $Y_{2a}\subseteq
Y^{\prime}_{2a}$, then that $Y^{\prime}_{2a+1}\subseteq Y_{2a+1}$ and finally
that $|Y^{\prime}_{2a}\setminus Y_{2a}|=|Y_{2a+1}\setminus
Y^{\prime}_{2a+1}|$. Together, these imply that $S_{a}=S_{a}^{\prime}$.

Assume that $\mathbf{y}\in Y_{2a}$. Thus, $w(\mathbf{y})=\ell+2a$ and
$|\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}_{i})|\geq a+1$ for
each $i\in[1,h]$. Hence,
$e\geq|\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}^{\prime}_{1})|\geq
a$ since
$\textrm{supp}(\mathbf{c}_{1})=\textrm{supp}(\mathbf{c}^{\prime}_{1})\cup\\{1\\}$.
Hence, $\mathbf{y}\in Y^{\prime}_{2a}$.

Assume then that $\mathbf{y}\in Y^{\prime}_{2a+1}$. Thus,
$w(\mathbf{y})=\ell+2a+1$ and
$|\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}_{i})|\geq a+1$ for
each $i\in[2,h]$ and
$|\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}^{\prime}_{1})|\geq
a+1$. Hence, $|\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}_{1})|\geq
a+1$ and $\mathbf{y}\in Y_{2a+1}$. Therefore, $Y_{2a}\subseteq
Y^{\prime}_{2a}$ and $Y^{\prime}_{2a+1}\subseteq Y_{2a+1}$.

Let us now consider output word $\mathbf{y}^{\prime}\in
Y^{\prime}_{2a}\setminus Y_{2a}$. We again have
$w(\mathbf{y}^{\prime})=\ell+2a$,
$|\textrm{supp}(\mathbf{y}^{\prime})\cap\textrm{supp}(\mathbf{c}_{j})|=i_{j}\geq
a+1$ for each $j\in[2,h]$. However,
$|\textrm{supp}(\mathbf{y}^{\prime})\cap\textrm{supp}(\mathbf{c}_{1})|=a=|\textrm{supp}(\mathbf{y}^{\prime})\cap\textrm{supp}(\mathbf{c}^{\prime}_{1})|$.
Observe that now especially
$\textrm{supp}(\mathbf{y}^{\prime})\cap\\{1\\}=\emptyset$. Thus,
$\mathbf{y}^{\prime}+\mathbf{e}_{1}\in Y_{2a+1}$. Let us denote
$i_{D}=|\textrm{supp}(\mathbf{y}^{\prime})\cap D|$. We have
$i_{D}=w(\mathbf{y}^{\prime})-a-\sum_{j=2}^{h}i_{j}=\ell+a-\sum_{j=2}^{h}i_{j}$.
Consider then output word $\mathbf{y}\in Y_{2a+1}\setminus Y^{\prime}_{2a+1}$.
We again have $w(\mathbf{y})=\ell+2a+1$,
$|\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}_{j})|=i_{j}\geq a+1$
for each $j\in[1,h]$. However,
$|\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}^{\prime}_{1})|=a$; in
particular, we have $1\in\textrm{supp}(\mathbf{y})$. Indeed, if
$1\not\in\textrm{supp}(\mathbf{y})$, then $\mathbf{y}\not\in Y_{2a+1}$ and if
$|\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}^{\prime}_{1})|\geq
a+1$, then $\mathbf{y}\in Y^{\prime}_{2a+1}$. Thus,
$\mathbf{y}+\mathbf{e}_{1}\in Y^{\prime}_{2a}$. Moreover, we have
$i_{D}=|\textrm{supp}(\mathbf{y}^{\prime})\cap
D|=w(\mathbf{y})-a-1-\sum_{j=2}^{h}i_{j}=\ell+a-\sum_{j=2}^{h}i_{j}$.
Therefore, for each output word $\mathbf{y}^{\prime}\in
Y^{\prime}_{2a}\setminus Y_{2a}$, we have
$\mathbf{y}^{\prime}+\mathbf{e}_{1}\in Y_{2a+1}\setminus Y^{\prime}_{2a+1}$
and for each output word $\mathbf{y}\in Y_{2a+1}\setminus Y^{\prime}_{2a+1}$,
we have $\mathbf{y}+\mathbf{e}_{1}\in Y^{\prime}_{2a}\setminus Y_{2a}$. Thus,
$|Y^{\prime}_{2a}\setminus Y_{2a}|=|Y_{2a+1}\setminus Y^{\prime}_{2a+1}|$.

Now, we have $S_{a}=S^{\prime}_{a}$ and the claim follows. ∎

In the following theorem, we show that $N_{h}$ exists and is unique for each
value $h\in[3,\ell+1]$ when $n$ is large. As we have seen previously, this
does not hold when $h\geq\ell+2$.

######  Theorem 12.

Let $n\geq n(e,\ell,b)$, $b\geq\max\\{3t,4e+4\\}$, $\ell\geq 2$, $3\leq
h\leq\ell$, then $N^{\prime}(n,\ell,e,h)>N^{\prime}(n,\ell,e,h+1)$ for each
$h$ and thus, each $N_{h}$ exists and attains unique value.

###### Proof.

Since $N^{\prime}(n,\ell,e,h+1)$ denotes the maximum value for
$|\bigcap_{i=1}^{h+1}B_{t}(\mathbf{c}_{i})|$ over all sets
$T(Y)=\\{\mathbf{c}_{1},\dots,\mathbf{c}_{h+1}\\}$, we clearly have
$N^{\prime}(n,\ell,e,h)\geq N^{\prime}(n,\ell,e,h+1)$. As we have seen in the
previous theorems, the maximum value for $N^{\prime}(n,\ell,e,h+1)$ is
attained when the codewords in
$T(Y)=\\{\mathbf{c}_{1},\dots,\mathbf{c}_{h+1}\\}$ have supports
$\textrm{supp}(\mathbf{c}_{i})=[(i-1)(e+1)+1,i(e+1)]$. We show that when we
choose $h$ of these codewords, then we can fit more words in the intersection
of their $t$-balls. We clearly have
$\bigcap_{i=1}^{h+1}B_{t}(\mathbf{c}_{i})\subseteq\bigcap_{i=1}^{h}B_{t}(\mathbf{c}_{i})$.
In the following, we show that there exists a word
$\mathbf{y}\in\bigcap_{i=1}^{h}B_{t}(\mathbf{c}_{i})\setminus\bigcap_{i=1}^{h+1}B_{t}(\mathbf{c}_{i})$
and hence,
$|\bigcap_{i=1}^{h}B_{t}(\mathbf{c}_{i})|>|\bigcap_{i=1}^{h+1}B_{t}(\mathbf{c}_{i})|$.

Let $w(\mathbf{y})=\ell+1$,
$|\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}_{i})|=1$ for
$i\in[1,h]$,
$\textrm{supp}(\mathbf{y})\cap\textrm{supp}(\mathbf{c}_{h+1})=\emptyset$ and
$|\textrm{supp}(\mathbf{y})\cap[(h+1)(e+1)+1,n]|=\ell+1-h$. We have
$d(\mathbf{y},\mathbf{c}_{i})=\ell+1+e+1-2=t$ for $i\in[1,h]$ but
$d(\mathbf{y},\mathbf{c}_{h+1})=\ell+1+e+1=t+2$. Thus, the claim follows. ∎

Using Theorem 11, we can improve the bound $\mathcal{L}\leq\ell+1$ of Theorem
6 just by adding a constant number $(e+1)^{\ell+1}$ of channels.

######  Corollary 13.

Let $n\geq n(e,\ell,b)$, $b\geq\max\\{3t,4e+4\\}$ and $\ell\geq 3$. If $N\geq
V(n,\ell-1)+(e+1)^{\ell+1}+1$, then $\mathcal{L}\leq\ell$.

###### Proof.

We calculate the value $N_{h}$ with $h=\ell+1$ of Theorem 11. For this
purpose, we consider the set $W_{w}$ with $w\geq\ell$. We get that $i_{j}\geq
1$ for each $j\in[1,h]$ and thus, $w\geq\ell+1$. On the other hand,
$w\leq\ell+1$. Indeed, if $w\geq\ell+2$, then
$w\geq\sum_{j=1}^{h}i_{j}\geq\sum_{j=1}^{\ell+1}i_{j}\geq(\ell+1)(w+1-\ell)/2=(\ell-1)(w+1-\ell)/2+w-(\ell-1)>w$
(a contradiction). Therefore, as $w=\ell+1$ and $i_{j}\geq 1$ for each $j$, we
have $W_{w}=\\{(1,1,...,1)\\}$. Thus, the sum corresponding to $W_{w}$ in
Theorem 11 gives $V(n,\ell-1)+(e+1)^{\ell+1}$. Hence, if $N\geq
N_{\ell+1}+1=V(n,\ell-1)+(e+1)^{\ell+1}+1$, then $\mathcal{L}\leq\ell$. ∎

In the following corollary, we present the asymptotic behaviour of $N_{h}$ on
$n$. Notice that Corollary 13 considers the case $h=\ell+1$ and Corollary 14
cases $3\leq h\leq\ell$.

######  Corollary 14.

Let $\ell\geq h\geq 3$, $n\geq n(e,\ell,b)$ and $b\geq\max\\{3t,4e+4\\}$. If
$N\geq N_{h}+1$, then $\mathcal{L}\leq h-1$, where

$\displaystyle N_{h}\in
V(n,\ell-1)+\binom{n-h(e+1)}{\ell+1-h}(e+1)^{h}+\Theta(n^{\ell-h}).$

###### Proof.

Let $n\geq n(e,\ell,b)$, $b\geq\max\\{3t,4e+4\\}$, $\ell\geq h\geq 3$, and $e$
and $\ell$ be fixed. By Theorem 11, we have
$N_{h}=V(n,\ell-1)+\sum_{w\geq\ell}\sum_{(i_{1},\dots,i_{h})\in
W_{w}}\binom{n-h(e+1)}{w-\sum_{j=1}^{h}i_{j}}\prod_{j=1}^{h}\binom{e+1}{i_{j}}$.

When we inspect the set $W_{w}$ closer, we notice that in
$\binom{n-h(e+1)}{w-\sum_{j=1}^{h}i_{j}}$ term $w-\sum_{j=1}^{h}i_{j}$ attains
its maximum value when $w-\sum_{j=1}^{h}i_{j}$ is as large as possible since
$w\leq 2e+\ell+1$ (recall that $e$ and $\ell$ are constants with respect to
$n$). This occurs exactly when $i_{j}=\lceil(w+1-\ell)/2\rceil$ for each $j$
and $\lceil(w+1-\ell)/2\rceil$ is as small as possible. In particular, when
$w\in\\{\ell,\ell+1\\}$, we have $\lceil(w+1-\ell)/2\rceil=1$ and when
$w=\ell+1+a$ for some integer $a\geq 1$, we have
$\lceil(w+1-\ell)/2\rceil=1+\lceil a/2\rceil$. Moreover, when $w=\ell$, we
have $w-\sum_{j=1}^{h}i_{j}\leq\ell-h$. When $w=\ell+1$, we have
$w-\sum_{j=1}^{h}i_{j}\leq\ell+1-h$ and when $w=\ell+1+a$, we have
$w-\sum_{j=1}^{h}i_{j}\leq\ell+1+a-h(1+\lceil a/2\rceil)$. Since $h\geq 3$ and
$a\geq 1$, we have $\ell+1+a-h(1+\lceil a/2\rceil)\leq\ell+1-h-\lceil
a/2\rceil\leq\ell-h$. Thus, we may concentrate on the case with $w=\ell+1$.

Furthermore, as $w=\ell+1$ and $i_{j}=1$ for each $j=1,2,\ldots,h$, we have
$\prod_{j=1}^{h}\binom{e+1}{i_{j}}=(e+1)^{h}$. Recall that $e$ is constant on
$n$. Hence, for large $n$, it is enough to consider the binomial coefficient
$\binom{n-h(e+1)}{\ell+1-h}$. Moreover, the second largest binomial
coefficient is $\binom{n-h(e+1)}{\ell-h}$ and we have
$\binom{n-h(e+1)}{t}\in\Theta(n^{t})$, when $n$ is large. Therefore, we have
$N_{h}\in
V(n,\ell-1)+\binom{n-h(e+1)}{\ell+1-h}(e+1)^{h}+\Theta(n^{\ell-h})$.∎

In Theorem 2, a tight bound for the number of channels to certainly attain the
list size $\mathcal{L}\leq 2$ is presented when code $C$ has minimum distance
$d$. Observe, that when we choose $h=3$ in Theorem 11, we attain the number of
channels required to have $\mathcal{L}\leq 2$. The bound of Theorem 2 by
Yaakobi and Bruck looks quite different from the bound in Theorem 11. However,
Theorem 2 can be obtained as a corollary from Theorem 11 as shown in Corollary
15. The new presentation in Corollary 15 somewhat simplifies the inequalities
for the indices compared to Theorem 2.

######  Corollary 15.

Let $n\geq n(e,\ell,b)$, $b\geq\max\\{3t,4e+4\\}$ and $\ell\geq 2$. If

$N\geq
N^{\prime}=\sum_{i_{1},i_{2},i_{3},i_{4}}\binom{n-3e-3}{i_{1}}\binom{e+1}{i_{2}}\binom{e+1}{i_{3}}\binom{e+1}{i_{4}}+1$

for

  * •

$0\leq i_{1}\leq\ell-1$,

  * •

$0\leq i_{4}\leq\ell-1-i_{1}$,

  * •

$0\leq i_{3}\leq\ell-1-i_{1}$ and

  * •

$i_{1}+i_{3}+i_{4}-(\ell-1)\leq i_{2}\leq\ell-1-i_{1}-|i_{4}-i_{3}|$,

then $\mathcal{L}\leq 2$ for any $e$-error-correcting code $C$ and value
$N^{\prime}$ is equal to the lower bound obtained in Theorem 2.

###### Proof.

We first show that the formulation of the bound follows from Theorem 11 when
$h=3$. This gives the minimum number of channels $N$ required to have
$\mathcal{L}\leq 2$. In particular, we have

$\displaystyle N_{3}=$ $\displaystyle
V(n,\ell-1)+\sum_{w\geq\ell}\sum_{(i_{2},i_{3},i_{4})\in
W_{w}}\binom{n-3e-3}{w-i_{2}-i_{3}-i_{4}}\binom{e+1}{i_{2}}\binom{e+1}{i_{3}}\binom{e+1}{i_{4}}.$

We have renamed the indices for convenience (the index $i_{1}$ will be saved
for later use in the proof). Moreover, we have
$W_{w}=\\{(i_{2},i_{3},i_{4})\mid(w+1-\ell)/2\leq i_{j}\leq e+1,w\geq
i_{2}+i_{3}+i_{4}\\}$. Earlier, we have used $W_{w}$ only with the assumption
that $w\geq\ell$. However, we may allow here that $w<\ell$. Hence, we may have
some binomial coefficients with $i_{j}<0$ for some $j$. In these cases (and
when $i_{j}>e+1$), we use the common convention that the binomial coefficient
attains the value $0$. Observe that $N_{3}=\sum_{w\geq
0}\sum_{(i_{2},i_{3},i_{4})\in
W_{w}}\binom{n-3e-3}{w-i_{2}-i_{3}-i_{4}}\binom{e+1}{i_{2}}\binom{e+1}{i_{3}}\binom{e+1}{i_{4}}$.
Indeed, since $W_{w}=\\{(i_{2},i_{3},i_{4})\mid 0\leq i_{j}\leq e+1,w\geq
i_{2}+i_{3}+i_{4}\\}$, we have
$\sum_{w=0}^{\ell-1}\sum_{(i_{2},i_{3},i_{4})\in
W_{w}}\binom{n-3e-3}{w-i_{2}-i_{3}-i_{4}}\binom{e+1}{i_{2}}\binom{e+1}{i_{3}}\binom{e+1}{i_{4}}=\sum_{w=0}^{\ell-1}\sum_{i_{2}=0}^{e+1}\sum_{i_{3}=0}^{e+1}\sum_{i_{4}=0}^{e+1}\binom{n-3e-3}{w-i_{2}-i_{3}-i_{4}}\binom{e+1}{i_{2}}\binom{e+1}{i_{3}}\binom{e+1}{i_{4}}=V(n,\ell-1)$
due to binomial identity
$\sum_{p=0}^{s}\binom{m-s}{k-p}\binom{s}{p}=\binom{m}{k}.$

Let us denote by $i_{1}=w-i_{2}-i_{3}-i_{4}$. We now get that $2i_{2}\geq
2(w+1-\ell)/2=i_{1}+i_{2}+i_{3}+i_{4}-\ell+1$ and similar inequalities for
$i_{3}$ and $i_{4}$. Since we do not have to take into account lower bound
$i_{1}\geq 0$ (cases with $i_{1}<0$ increase binomial sum by $0$) or the cases
with $i_{j}>e+1$ for $j\in\\{2,3,4\\}$, we can consider following system of
inequalities:

$\displaystyle i_{2}\geq$ $\displaystyle i_{1}+i_{3}+i_{4}-\ell+1$ (3)
$\displaystyle i_{3}\geq$ $\displaystyle i_{1}+i_{2}+i_{4}-\ell+1$ (4)
$\displaystyle i_{4}\geq$ $\displaystyle i_{1}+i_{2}+i_{3}-\ell+1.$ (5)

Our goal is to show that this system of inequalities is equivalent with the
following system of inequalities:

$\displaystyle i_{4}$ $\displaystyle\leq\ell-1-i_{1},$ (6) $\displaystyle
i_{3}$ $\displaystyle\leq\ell-1-i_{1},$ (7) $\displaystyle
i_{1}+i_{3}+i_{4}-(\ell-1)\leq i_{2}$
$\displaystyle\leq\ell-1-i_{1}-|i_{4}-i_{3}|.$ (8)

Let us first show that the second system of inequalities follows from the
first system of inequalities.

Inequality (6) follows from

$i_{4}=w-i_{1}-i_{2}-i_{3}\leq w-i_{1}-2(w-\ell+1)/2=\ell-1-i_{1}.$

We obtain Inequality (7) in similar manner. Moreover, from Inequalities (4)
and (5) we obtain $i_{2}\leq\ell-1-i_{1}-i_{4}+i_{3}$ and
$i_{2}\leq\ell-1-i_{1}-i_{3}+i_{4}$, respectively. Together, these imply

$i_{2}\leq\ell-1-i_{1}-|i_{4}-i_{3}|.$

Finally, the lower bound inequality in (8) follows directly from (3).

Let us then show that the first system of inequalities follows from the second
one. First of all, Inequality (3) follows immediately from Inequality (8).
Assume first that $i_{4}\geq i_{3}$. Then the upper bound of Inequality (8) is
$i_{2}\leq\ell-1-i_{1}-i_{4}+i_{3}$. This implies Inequality (4) and
inequality (5) since

$i_{4}\geq i_{3}\geq i_{1}+i_{2}+i_{4}-\ell+1\geq i_{1}+i_{2}+i_{3}-\ell+1.$

The case with $i_{3}\geq i_{4}$ is similar.

Finally, we may add lower bounds $i_{j}\geq 0$ for all $j\in\\{1,2,3,4\\}$ due
to binomial coefficient context. Similarly we notice that if $i_{1}\geq\ell$,
then $i_{4}<0$. Thus, we may also add upper bound $i_{1}\leq\ell-1$. Hence,
the first part of the claim follows.

Let us then derive the bound of Theorem 2 by Yaakobi and Bruck from this new
lower bound. The case with $d=2e+1$ is included in Appendix and we consider
here only the case with $d=2e+2$. When we have $d=2e+2$, Theorem 2 can be
presented in the following way: If
$N\geq\sum_{h_{1},h_{2},h_{3},h_{4}}\binom{n-3e-3}{h_{1}}\binom{e+1}{h_{2}}\binom{e+1}{h_{3}}\binom{e+1}{h_{4}}+1$
for

  * •

$0\leq h_{1}\leq\ell-1$,

  * •

$h_{1}-(\ell-1)\leq h_{4}\leq\ell-1-h_{1}$,

  * •

$e+2-\ell+h_{1}\leq h_{3}\leq t-(h_{1}+h_{4})$ and

  * •

$\max\\{h_{1}-h_{3}-h_{4}+2e+3-\ell,h_{1}+h_{3}+h_{4}-\ell+1\\}\leq
h_{2}\leq\ell-1-(h_{1}+h_{4}-h_{3})$,

then $\mathcal{L}\leq 2$ for any $e$-error-correcting code $C$ (with minimum
distance $d=2e+2$). Next, we modify the presentation we got for $N_{3}$ into
the formulation above.

Let us denote by $i^{\prime}_{2}=e+1-i_{2}$ and by $i^{\prime}_{3}=e+1-i_{3}$.
Observe that $\binom{e+1}{i^{\prime}_{j}}=\binom{e+1}{i_{j}}$ for
$j\in\\{2,3\\}$. We can replace lower bound $i_{4}\geq 0$ by $i_{4}\geq
i_{1}-(\ell-1)$ since $i_{4}\geq 0\geq i_{1}-\ell+1$ and
$\binom{e+1}{i_{4}}=0$ when $i_{4}<0$. Moreover, we have $0\leq
i_{3}\leq\ell-1-i_{1}$. Hence, $e+1\geq i^{\prime}_{3}\geq e+2-\ell+i_{1}$.
Notice that the upper bound of $i^{\prime}_{3}$ can be replaced by
$t-(i_{1}+i_{4})$ since $t-(i_{1}+i_{4})\geq e+1$ as $i_{1}+i_{4}\leq\ell-1$
and $\binom{e+1}{i^{\prime}_{3}}=0$ when $i^{\prime}_{3}>e+1$.

For $i_{2}$ we have $i_{1}+i_{3}+i_{4}-(\ell-1)\leq
i_{2}\leq\ell-1-i_{1}-|i_{4}-i_{3}|$ and hence,
$\ell-1-(i_{1}+i_{4}-i^{\prime}_{3})\geq
i^{\prime}_{2}\geq-\ell+e+2+i_{1}+|i_{4}-i_{3}|=e+2-\ell+i_{1}+|i_{4}+i^{\prime}_{3}-e-1|=\max\\{i_{1}-i^{\prime}_{3}-i_{4}+2e+3-\ell,i_{1}+i^{\prime}_{3}+i_{4}-\ell+1\\}$.
By comparing these inequalities with the bounds used in Theorem 2, we notice
that they are identical. The case with $d=2e+1$ is similar and is included in
Appendix. Hence, we get the claim.∎

##  4 New Bounds with the aid of Covering Codes

Notice that although we have the bound $\mathcal{L}\leq\ell+1$ when $n$ is
rather large (see Theorem 6), for smaller lengths of the codes our best bound
is still $\mathcal{L}\leq 2^{\ell}$ (see Theorem 4) when the number of
channels satisfies $N\geq V(n,\ell-1)+1$. Although this bound is attained in
some cases (see [23]) and thus cannot be improved in general, we can try to
get a smaller list size $\mathcal{L}$ when we increase the number of channels
as we have seen Theorem 10. In this section, we utilize covering codes when we
increase the number of channels. A code $C\subseteq\mathbb{F}^{n}$ is an
$R$-_covering code_ if for every word $\mathbf{x}\in\mathbb{F}^{n}$ there
exists a codeword $\mathbf{c}\in C$ such that $d(\mathbf{x},\mathbf{c})\leq
R$. For an excellent source on results concerning covering codes, see [24].
Let us denote by $k[n,R]$ the smallest possible dimension of a _linear_
$R$-covering code of length $n$.

Let us next present the well-known Sauer-Shelah lemma (see [25, 26]). Let
$\mathcal{F}$ be a family of subsets of $[1,n]$, where $n$ is a positive
integer. We say that a subset $S$ of $[1,n]$ is _shattered_ by $\mathcal{F}$
if for any subset $E\subseteq S$ there exists a set $F\in\mathcal{F}$ such
that $F\cap S=E$. The Sauer-Shelah lemma states that if
$|\mathcal{F}|>\sum_{i=0}^{k-1}\binom{n}{i}$, then $\mathcal{F}$ shatters a
subset of size (at least) $k$. Since the subsets of $[1,n]$ can naturally be
interpreted as words of $\mathbb{F}^{n}$, the Sauer-Shelah lemma can be
reformulated as follows. Notice that $\sum_{i=0}^{k-1}\binom{n}{i}=V(n,k-1)$.

######  Theorem 16 ([25, 26]).

If $Y\subseteq\mathbb{F}^{n}$ is a set containing at least $V(n,k-1)+1$ words,
then there exists a set $S$ of $k$ coordinates such that for any word
$\mathbf{w}\in\mathbb{F}^{n}$ with $\textrm{supp}(\mathbf{w})\subseteq S$
there exists a word $\mathbf{s}\in Y$ satisfying
$\textrm{supp}(\mathbf{w})=\textrm{supp}(\mathbf{s})\cap S$. Here we say that
the set $S$ of coordinates is _shattered_ by $Y$.

Observe that each Hamming ball of radius $e$ contains at most one codeword of
$C$. Thus, if the intersection of the balls of radius $t$ centered at the
output words of $Y$ can be covered by $k$ balls of radius $e$, then we have
$|T(Y)|\leq k$. This approach is formulated in the following lemma.

######  Lemma 17 ([23]).

Let $C\subseteq\mathbb{F}^{n}$ be an $e$-error-correcting code. If for any set
of output words $Y=\\{\mathbf{y}_{1},\ldots,\mathbf{y}_{N}\\}$ we have

$T(Y)\subseteq\bigcup_{i=1}^{k}B_{e}(\beta_{i})$

for some words $\beta_{i}\in\mathbb{F}^{n}$ ($i=1,\ldots,k$), then
$\mathcal{L}\leq k.$

Notice that Lemma 17 also gives a decoding algorithm. Indeed, if the words
$\beta_{i}$ are known, then there is at most one codeword in each
$B_{e}(\beta_{i})$, we can use the decoding algorithm of $C$ on $\beta_{i}$
and the codeword can be added to the list $T$.

######  Theorem 18.

Let $C$ be an $e$-error-correcting code. If the number of channels satisfies
$N\geq V(n,\ell+2R-1)-2^{\ell+2R-k[\ell+2R,R]}+2$, then

$\mathcal{L}\leq 2^{k[\ell+2R,R]}.$

###### Proof.

Let $\mathbf{x}$ be the input word. We have
$|Y|\geq(V(n,\ell+2R-1)+1)-(2^{\ell+2R-k[\ell+2R,R]}-1)$. Next we show that
with this number of outputs we can guarantee that there exists a set $S$ of
$\ell+2R$ coordinates such that within these coordinates of $S$ a subset
$Y^{\prime}\subseteq Y$ contains a linear $R$-covering code of length
$\ell+2R$. Due to Theorem 16, we know that if we had more output words,
namely, $|Y|\geq V(n,\ell+2R-1)+1$, then we would have a set $S$ of
coordinates such that a subset $Y^{\prime\prime}\subseteq Y$ contains all the
$2^{\ell+2R}$ words of length $\ell+2R$ among these coordinates of $S$. Let
$D$ be a linear $R$-covering code in $\mathbb{F}^{\ell+2R}$ with
$\dim(D)=k[\ell+2R,R].$ Notice that any coset $\mathbf{u}+D$,
$\mathbf{u}\in\mathbb{F}^{\ell+2R}$, of the linear code $D$ is also an
$R$-covering code, and there are $2^{\ell+2R-\dim(D)}$ distinct cosets.
Therefore, the set $Y^{\prime\prime}$ can miss any $2^{\ell+2R-\dim(D)}-1$
words of $\mathbb{F}^{\ell+2R}$ and still the remaining subset contains at
least one $R$-covering code of length $\ell+2R$. Consequently, it follows that
$Y^{\prime}$ contains an $R$-covering code of size $2^{k[\ell+2R,R]}$ because
$Y^{\prime}$ can be obtained from $Y^{\prime\prime}$ by removing some
$2^{\ell+2R-\dim(D)}-1$ words.

Now let $\mathbf{s}\in\mathbb{F}^{n}$ be a word such that
$\textrm{supp}(\mathbf{s})=S$ and
$Y_{1}=\\{\mathbf{y}_{1},\dots,\mathbf{y}_{2^{k[\ell+2R,R]}}\\}\subseteq
Y^{\prime}$ the subset of output words corresponding to the $R$-covering code.
Denote $\beta_{i}=\mathbf{s}+\mathbf{y}_{i}$ for $i=1,\dots,2^{k[\ell+2R,R]}$.
Since the words in set $Y_{1}$ form, among the coordinates corresponding to
$S$, an $R$-covering code of length $\ell+2R$, we know that there exists
$\mathbf{y}_{j}$, $j\in\\{1,\dots,2^{k[\ell+2R,R]}\\}$, such that the words
$\mathbf{y}_{j}$ and $\mathbf{x}+\mathbf{s}$ differ in at most $R$ places
among the coordinates of $S$. Consequently, as
$d(\mathbf{x},\mathbf{y}_{j})\leq t$, the words $\mathbf{x}$ and
$\beta_{j}=\mathbf{y}_{j}+\mathbf{s}$ have distance at most $t-(\ell+R)+R=e$
from one another. Therefore, by Lemma 17, we get that $\mathcal{L}\leq
2^{k[\ell+2R,R]}.$ ∎

Note that if $\ell=5$ and $N\geq V(n,4)+1$, then, by Theorem 4, we have
$\mathcal{L}\leq 2^{5}=32.$ If we have $N\geq V(n,6)-6$, then (using as the
linear $1$-covering code $D$ the Hamming code of length 7), we obtain by the
previous result, that $\mathcal{L}\leq 16.$

##  5 List size with less channels

By the following theorem (of [23]), it is clear that if we have _less_ than
$V(n,\ell-1)+1$ channels, then the list size cannot in general be constant for
$e$-error-correcting codes of length $n$.

######  Theorem 19.

[23] Let $V(n,\ell-p-1)+1\leq N\leq V(n,\ell-p)$ where $0\leq p\leq\ell-1$.
Moreover, let $C\subseteq\mathbb{F}^{n}$ be such an $e$-error-correcting code
that $\mathcal{L}$ is maximal. Then we have

$\mathcal{L}=\Theta(n^{p}).$

Due to this result, in order to have a smaller list size, let us concentrate
on certain $e$-error-correcting codes, namely, those with at most $M$
codewords within any ball of radius $e+a$, for some $a>0$.

######  Theorem 20.

Let $N\geq V(n,\ell-a-1)+1$ where $0\leq a\leq\ell-1$. Let $C$ be an
$e$-error-correcting code such that $|B_{e+a}(\mathbf{u})\cap C|\leq M$ for
every $\mathbf{u}\in\mathbb{F}^{n}$. Consequently,

$\mathcal{L}\leq 2^{\ell-a}M.$

###### Proof.

Assume that we received the set $Y$ of output words from the channels. Due to
the number of channels, we know, by Theorem 16, that there exists a subset
$Y^{\prime}\subseteq Y$ of size $|Y^{\prime}|=2^{\ell-a}$ such that these
words have in some $\ell-a$ coordinates, denote this set of coordinates by
$S$, all possible words of length $\ell-a$. Suppose $\mathbf{x}$ is the input
word and denote
$Y^{\prime}=\\{\mathbf{y}_{1},\dots,\mathbf{y}_{2^{\ell-a}}\\}.$ Let
$\beta_{i}=\mathbf{y}_{i}+\mathbf{s}$, $i=1,\dots,2^{\ell-a}$ where
$\textrm{supp}(\mathbf{s})=S$. It is easy to check that $\mathbf{x}$ has
distance at most $e+a$ from one of the $\beta_{i}$’s. Since there are at most
$2^{\ell-a}$ $\beta_{i}$’s and there are at most $M$ codewords within distance
$e+a$ from each of them, we obtain the bound $\mathcal{L}\leq 2^{\ell-a}M.$ ∎

The previous result is useful when our $e$-error-correcting code is a code for
traditional list-decoding, see [27]. For number of channels being less than
$V(n,\ell-1)+1$, it also gives, for every $e$-error-correcting code with
suitable $a$, small exponent for $n$ compared to Theorem 19 (see Corollary
21(ii) below), or even constant bounds (see Corollary 21(i)). The following
corollary follows straightforwardly from applying the results in [27, Theorem
3.2] to Theorem 20. Let us denote

$r(n,e,M)=\frac{n}{2}\left(1-\sqrt{1-\frac{M-1}{M}\frac{2(2e+1)}{n}}\right)$

and

$r(n,e)=\frac{n}{2}\left(1-\sqrt{1-\frac{2(2e+1)}{n}}\right).$

######  Corollary 21.

Let $C$ be an $e$-error-correcting code, $t=e+\ell$, an integer $M\geq 1$ and
$2e+1<n/2$. We have

  * (i)

Let $N\geq V(n,\ell-r(n,e,M)+e-1)+1$ where $0\leq r(n,e,M)-e\leq\ell-1$ and
$r(n,e,M)\geq 1$. Consequently,

$\mathcal{L}\leq 2^{t-r(n,e,M)}M.$

  * (ii)

Let $N\geq V(n,\ell-r(n,e)+e)+1$ where $1\leq r(n,e)-e\leq\ell$ and
$r(n,e)\geq 2$. Consequently,

$\mathcal{L}\leq 2^{t-r(n,e)+1}n.$

In what follows, we continue our study of the list size for codes with
$|B_{e+a}(\mathbf{u})\cap C|\leq M$ for every $\mathbf{u}\in\mathbb{F}^{n}$.
First, we introduce two technical lemmas. Lemma 22 can be seen as a
reformulation of [23, Lemma $13$] for lesser number of channels and Lemma 23
as a reformulation of Lemma 9.

######  Lemma 22.

Let $N\geq V(n,\ell-a-1)+1$, $\ell-1\geq a\geq 1$ and
$n\geq(\ell-a-1)^{2}2^{b}+\ell-a-2$. Then for any codeword $\mathbf{c}\in
T(Y)$ and any set $\overline{D}\subseteq[1,n]$ with cardinality
$|\overline{D}|=b$ there exists an output word $\mathbf{y}\in Y$ such that
$|\textrm{supp}(\mathbf{y}+\mathbf{c})\setminus\overline{D}|\geq\ell-a-1$.

###### Proof.

Let us assume without loss of generality that $\mathbf{c}=\mathbf{0}$. Thus,
$w(\mathbf{y})\leq t$ for each $\mathbf{y}\in Y$. Let us count the number of
binary words of weight at most $t$ which have
$|\textrm{supp}(\mathbf{y})\setminus\overline{D}|<\ell-a-1$. There are at most

$\displaystyle\sum_{j=0}^{\ell-a-2}\sum_{i=0}^{\min\\{b,t-j\\}}\binom{b}{i}\binom{n-b}{j}$
$\displaystyle\leq$ $\displaystyle(\ell-a-1)2^{b}\binom{n}{\ell-a-2}$
$\displaystyle=$
$\displaystyle(\ell-a-1)2^{b}\frac{\ell-a-1}{n-\ell+a+2}\binom{n}{\ell-a-1}$
$\displaystyle\leq$ $\displaystyle\binom{n}{\ell-a-1}$

such words, which is strictly less than $N$ and hence, the claim holds. ∎

######  Lemma 23.

Let $N\geq V(n,\ell-a-1)+1$, $\ell-1\geq a\geq 1$, $b=2t$,
$n\geq(\ell-a-1)^{2}2^{b}+\ell-a-2$ and $\mathcal{L}\geq 2$. Then for any two
codewords $\mathbf{c}_{1}$ and $\mathbf{c}_{2}$ in $T(Y)$ holds

$2e+1\leq d(\mathbf{c}_{1},\mathbf{c}_{2})\leq 2e+2a+2.$

###### Proof.

Let us assume without loss of generality that $\mathbf{c}_{1}=\mathbf{0}$.
Notice that $w(\mathbf{c}_{2})\leq 2t$. Choose
$\overline{D}=\textrm{supp}(\mathbf{c}_{2})$. Now, by Lemma 22, there exists
an output word $\mathbf{y}\in Y$ such that
$|\textrm{supp}(\mathbf{y})\setminus\overline{D}|\geq\ell-a-1$. Since
$d(\mathbf{c}_{2},\mathbf{y})\leq t$ and $w(\mathbf{y})\leq t$, we have
$t\geq\ell-a-1+(w(\mathbf{c}_{2})-(t-(\ell-a-1)))=\ell-2a-2-e+w(\mathbf{c}_{2})$
and hence, $w(\mathbf{c}_{2})\leq 2e+2a+2$. Therefore,
$d(\mathbf{c}_{1},\mathbf{c}_{2})\leq 2e+2a+2$. Since we consider an
$e$-error-correcting code, the lower bound follows. ∎

Together with the two previous lemmas, we can now prove an upper bound for
$\mathcal{L}$, depending on the maximum number $M$ of codewords in an
$(e+a)$-radius ball.

######  Theorem 24.

Let $N\geq V(n,\ell-a-1)+1$, $\ell-1\geq a\geq 1$,
$b=\left\lceil(2e+2a+2)^{\mathbbm{e}\cdot(e+a+1)!}\right\rceil$,
$n\geq(\ell-a-1)^{2}2^{b}+\ell-a-2$. Moreover, let $C$ be such an $e$-error-
correcting code that there are at most $M$ codewords in any $(e+a)$-radius
ball. Then

$\mathcal{L}\leq\max\\{(t+1)M,b/(2e+2a+2)\\}.$

###### Proof.

Let us denote
$T(Y)=\\{\mathbf{c}_{1},\mathbf{c}_{2},\dots,\mathbf{c}_{\mathcal{L}}\\}$. If
$\mathcal{L}\leq b/(2e+2a+2)$, then the claim follows. Assume now that
$\mathcal{L}>b/(2e+2a+2)$. Assume then, without loss of generality, that
$\mathbf{c}_{1}=\mathbf{0}$. By Lemma 23, we have $w(\mathbf{c}_{i})\leq
2e+2a+2$ for each $i\in[1,\mathcal{L}]$.

Let $Z$ be a subset of $\mathbb{F}^{n}$. We say that
$\mathbf{w}\in\mathbb{F}^{n}$ is a _central word_ with respect to $Z$ if
$d(\mathbf{w},\mathbf{z})\leq e+a+1$ for all $\mathbf{z}\in Z$. Moreover, the
set of all central words with respect to $Z$ is denoted by $W_{Z}$. In what
follows, we first show a useful observation stating that if a subset
$C_{S}\subseteq T(Y)$ is such that $\mathbf{0}\in C_{S}$ and $|C_{S}|\leq
b/(2e+2a+2)$, then there exists a word $\mathbf{w}\in\mathbb{F}^{n}$ such that
$w(\mathbf{w})\leq e+a+1$ and $d(\mathbf{w},\mathbf{c})\leq e+a+1$ for any
$\mathbf{c}\in C_{S}$, i.e., $\mathbf{w}\in W_{C_{S}}\neq\emptyset$. Since
$w(\mathbf{c})\leq 2e+2a+2$ for any $\mathbf{c}\in C_{S}$, we have

$\left|\bigcup_{\mathbf{c}\in
C_{S}}\textrm{supp}(\mathbf{c})\right|\leq(2e+2a+2)\cdot\frac{b}{2e+2a+2}=b\text{.}$

Therefore, by Lemma 22, there exists an output word $\mathbf{y}\in Y$ such
that

$|\textrm{supp}(\mathbf{y})\setminus\bigcup_{\mathbf{c}\in
C_{S}}\textrm{supp}(\mathbf{c})|\geq\ell-1-a\text{.}$

Let then $\mathbf{w}\in\mathbb{F}^{n}$ be such that

$\textrm{supp}(\mathbf{w})=\textrm{supp}(\mathbf{y})\cap\bigcup_{\mathbf{c}\in
C_{S}}\textrm{supp}(\mathbf{c})\text{.}$

Now, as $d(\mathbf{y},\mathbf{c})\leq t=e+\ell$ for any $\mathbf{c}\in C_{S}$,
we have $d(\mathbf{w},\mathbf{c})\leq e+a+1$. Moreover, $w(\mathbf{w})\leq
e+a+1$ since $\mathbf{0}\in C_{S}$.

In what follows, we show using an iterative approach that there exists a
central word $\mathbf{w}\in\mathbb{F}^{n}$ with respect to $T(Y)$. We begin
the iterative process by considering a subset
$C_{0}=\\{\mathbf{c}_{1},\mathbf{c}_{2}\\}\subseteq T(Y)$ such that
$\mathbf{c}_{1}=\mathbf{0}$ and $w(\mathbf{c}_{2})=e+a+1+p_{1}$ with $1\leq
p_{1}\leq e+a+1$. Indeed, we may assume that such a codeword $\mathbf{c}_{2}$
exists since otherwise we are immediately done due to $\mathbf{w}=\mathbf{0}$
being the searched central word. Observe that the weight of a central word
$\mathbf{w}\in W_{C_{0}}$ satisfies $p_{1}\leq w(\mathbf{w})\leq e+a+1$. In
particular, there are exactly $\binom{e+a+1+p_{1}}{p_{1}}$ central words
$\mathbf{w}\in W_{C_{0}}$ of weight $p_{1}$. For each such central word
$\mathbf{w}$, we may assume that there exists a codeword $\mathbf{c}\in T(Y)$
such that $d(\mathbf{w},\mathbf{c})>e+a+1$ as otherwise $\mathbf{w}\in
W_{T(Y)}$ and we are done. Now we form a new code $C_{1}$ by adding such a
codeword $\mathbf{c}$ for each $\mathbf{w}\in W_{C_{0}}$ with
$w(\mathbf{w})=p_{1}$. The number of added codewords is at most

$\binom{e+a+1+p_{1}}{p_{1}}\leq(2e+2a+2)^{p_{1}}-1\text{.}$

Therefore, we have $|C_{1}|\leq(2e+2a+2)^{p_{1}}+1$. Notice that there are no
central words in $W_{C_{1}}$ of weight at most $p_{1}$. Furthermore, by the
previous observation for $W_{C_{S}}$, $W_{C_{1}}$ is nonempty as
$|C_{1}|\leq(2e+2a+2)^{p_{1}}+1\leq b/(2e+2a+2)$.

Assume that $p_{2}>p_{1}$ is now the smallest weight of a central word in
$W_{C_{1}}$. Let $\mathbf{w}$ be a central word with respect to $C_{1}$ of
weight $p_{2}$. The support of $\mathbf{w}$ is a subset of
$\bigcup_{\mathbf{c}\in C_{1}}\textrm{supp}(\mathbf{c})$ since otherwise there
exists a central word $\mathbf{w}^{\prime}\in W_{C_{1}}$ with
$w(\mathbf{w}^{\prime})<w(\mathbf{w})$ (a contradiction). Therefore, as
($\mathbf{c}_{1}=\mathbf{0}\in C_{1}$ implies) $\left|\bigcup_{\mathbf{c}\in
C_{1}}\textrm{supp}(\mathbf{c})\right|\leq(2e+2a+2)(2e+2a+2)^{p_{1}}$, the
number of central words of weight $p_{2}$ in $W_{C_{1}}$ is at most

$\displaystyle\binom{(2e+2a+2)(2e+2a+2)^{p_{1}}}{p_{2}}$ $\displaystyle=$
$\displaystyle\binom{(2e+2a+2)^{p_{1}+1}}{p_{2}}$ $\displaystyle\leq$
$\displaystyle\frac{(2e+2a+2)^{p_{1}p_{2}+p_{2}}}{2}\text{.}$

Again, for each central word $\mathbf{w}\in W_{C_{1}}$ of weight $p_{2}$,
there exists a codeword $\mathbf{c}\in T(Y)$ such that
$d(\mathbf{w},\mathbf{c})>e+a+1$. Now we form a new code $C_{2}$ by adding
such a codeword $\mathbf{c}$ for each $\mathbf{w}\in W_{C_{1}}$ with
$w(\mathbf{w})=p_{2}$. Thus, we have
$|C_{2}|\leq(2e+2a+2)^{p_{1}}+1+(2e+2a+2)^{p_{1}p_{2}+p_{2}}/2\leq(2e+2a+2)^{p_{1}p_{2}+p_{2}}/2+(2e+2a+2)^{p_{1}p_{2}+p_{2}}/2=(2e+2a+2)^{p_{1}p_{2}+p_{2}}$.

The process can be iteratively continued by forming a new code $C_{i}$ based
on the previous code $C_{i-1}$, until we have reached $p_{i}=e+a+1$ or we have
already found a central word with respect to $T(Y)$. In what follows, the
iterative process is explained in more detail:

  * •

Assume that $p_{i}>p_{i-1}$ is the smallest weight of a central word in
$W_{C_{i-1}}$.

  * •

Assume that $|C_{i-1}|\leq(2e+2a+2)^{\sum_{h=1}^{i-1}\prod_{k=h}^{i-1}p_{k}}$.
By the observation above for $W_{C_{S}}$, this implies that $W_{C_{i-1}}$ is
nonempty as $|C_{i-1}|\leq b/(2e+2a+2)$ (see also Equation (10)). Furthermore,
we have $|\bigcup_{\mathbf{c}\in
C_{i-1}}\textrm{supp}(\mathbf{c})|\leq(2e+2a+2)|C_{i-1}|=(2e+2a+2)^{(\sum_{h=1}^{i-1}\prod_{k=h}^{i-1}p_{k})+1}$.

  * •

Let $\mathbf{w}\in W_{C_{i-1}}$ be of weight $p_{i}$. As previously, the
support of $\mathbf{w}$ is a subset of $\bigcup_{\mathbf{c}\in
C_{i-1}}\textrm{supp}(\mathbf{c})$ since otherwise there exists a central word
$\mathbf{w}^{\prime}\in W_{C_{i-1}}$ with
$w(\mathbf{w}^{\prime})<w(\mathbf{w})$ (a contradiction). Therefore, as
$|\bigcup_{\mathbf{c}\in
C_{i-1}}\textrm{supp}(\mathbf{c})|\leq(2e+2a+2)|C_{i-1}|=(2e+2a+2)^{(\sum_{h=1}^{i-1}\prod_{k=h}^{i-1}p_{k})+1}$,
the number of central words in $W_{C_{i-1}}$ of weight $p_{i}$ is at most
$\binom{(2e+2a+2)^{(\sum_{h=1}^{i-1}\prod_{k=h}^{i-1}p_{k})+1}}{p_{i}}$.

  * •

Again, for each central word $\mathbf{w}\in W_{C_{i-1}}$ of weight $p_{i}$,
there exists a codeword $\mathbf{c}\in T(Y)$ such that
$d(\mathbf{w},\mathbf{c})>e+a+1$. Now we form a new code $C_{i}$ by adding
such a codeword $\mathbf{c}$ for each $\mathbf{w}\in W_{C_{i-1}}$ with
$w(\mathbf{w})=p_{i}$. Thus, we have

$\displaystyle|C_{i}|\leq$
$\displaystyle(2e+2a+2)^{\sum_{h=1}^{i-1}\prod_{k=h}^{i-1}p_{k}}+\binom{(2e+2a+2)^{1+(\sum_{h=1}^{i-1}\prod_{k=h}^{i-1}p_{k})}}{p_{i}}$
$\displaystyle\leq$
$\displaystyle(2e+2a+2)^{\sum_{h=1}^{i}\prod_{k=h}^{i}p_{k}}/2+(2e+2a+2)^{\sum_{h=1}^{i}\prod_{k=h}^{i}p_{k}}/2$
(9) $\displaystyle=$
$\displaystyle(2e+2a+2)^{\sum_{h=1}^{i}\prod_{k=h}^{i}p_{k}}.$

Notice that since $1\leq p_{1}<p_{2}<\cdots<p_{i}\leq e+a+1$, we reach
$p_{j}=e+a+1$ at some point (or the central word $\mathbf{w}$ with respect to
$T(Y)$ has already been found in an earlier step). By (• ‣ 5), we have

$\begin{split}|C_{j}|&\leq(2e+2a+2)^{\sum_{h=1}^{j}\prod_{k=h}^{j}p_{k}}\\\
&\leq(2e+2a+2)^{\sum_{h=1}^{e+a+1}\prod_{k=h}^{e+a+1}k}\\\
&=(2e+2a+2)^{\sum_{h=0}^{e+a}(e+a+1)!/h!}\\\
&\leq(2e+2a+2)^{\mathbbm{e}\cdot(e+a+1)!-1}\\\
&\leq\frac{b}{2e+2a+2}\end{split}$ (10)

since $\sum_{h=0}^{e+a+1}1/h!<\sum_{h=0}^{\infty}1/h!=\mathbbm{e}$. Therefore,
by the previous observation, $W_{C_{j}}$ is nonempty. Thus, in conclusion,
there exists a central word $\mathbf{w}\in\mathbb{F}^{n}$ with respect to
$T(Y)$.

Let us now translate the Hamming space so that $\mathbf{w}=\mathbf{0}$ and
thus, $T(Y)\subseteq B_{e+a+1}(\mathbf{0})$. In other words, we have
$w(\mathbf{c}_{i})\leq e+a+1$ for each $i$. Recall that we have $N\geq
V(n,\ell-a-1)+1$. Thus, there exists a word $\mathbf{y}\in Y$ such that
$w(\mathbf{y})\geq\ell-a$. Moreover, since $d(\mathbf{c}_{i},\mathbf{y})\leq
t$ for each $i$, we have $w(\mathbf{y})\leq t+e+a+1$. The proof now divides
into the following three cases depending on the weight of $w(\mathbf{y})$.

(i) Assume first that $\ell-a\leq w(\mathbf{y})\leq t$. Now the support of
each $\mathbf{c}_{i}\in T(Y)$ of weight $e+a+1$ intersects with
$\textrm{supp}(\mathbf{y})$ since otherwise
$d(\mathbf{y},\mathbf{c}_{i})\geq(e+a+1)+(\ell-a)=t+1$ (a contradiction).
Hence,

$T(Y)\subseteq
B_{e+a}(\mathbf{0})\cup\bigcup_{i\in\textrm{supp}(\mathbf{y})}B_{e+a}(\mathbf{e}_{i})\text{.}$

(ii) Assume then that $t\leq w(\mathbf{y})\leq t+e+a$. Let $\mathbf{y}_{s}$ be
a word such that
$\textrm{supp}(\mathbf{y}_{s})\subseteq\textrm{supp}(\mathbf{y})$ and
$w(\mathbf{y}_{s})=t$. Now the support of each $\mathbf{c}_{i}\in T(Y)$ of
weight $e+a+1$ intersects with $\textrm{supp}(\mathbf{y}_{s})$ since otherwise
$d(\mathbf{y},\mathbf{c}_{i})\geq t+1$ (a contradiction). Hence,

$T(Y)\subseteq
B_{e+a}(\mathbf{0})\cup\bigcup_{i\in\textrm{supp}(\mathbf{y}_{s})}B_{e+a}(\mathbf{e}_{i})\text{.}$

(iii) Assume finally that $w(\mathbf{y})=t+e+a+1$. Then we have
$w(\mathbf{c}_{i})=e+a+1$ for any $\mathbf{c}_{i}\in T(Y)$ as
$d(\mathbf{y},\mathbf{c}_{i})\leq t$. Let $\mathbf{y}_{s}$ be a word such that
$\textrm{supp}(\mathbf{y}_{s})\subseteq\textrm{supp}(\mathbf{y})$ and
$w(\mathbf{y}_{s})=t+1$. Again the support of each $\mathbf{c}_{i}\in T(Y)$ of
weight $e+a+1$ intersects with $\textrm{supp}(\mathbf{y}_{s})$. Observing that
$w(\mathbf{c}_{i})=e+a+1$ for any $\mathbf{c}_{i}\in T(Y)$ as
$d(\mathbf{y},\mathbf{c}_{i})\leq t$, we have

$T(Y)\subseteq\bigcup_{i\in\textrm{supp}(\mathbf{y}_{s})}B_{e+a}(\mathbf{e}_{i})\text{.}$

Based on the cases (i)–(iii), the set of codewords $T(Y)$ is always contained
in a union of $t+1$ balls of radius $e+a$. Thus, as each ball of radius $e+a$
has at most $M$ codewords, we obtain that $\mathcal{L}\leq(t+1)M$. ∎

##  6 Decoding with majority algorithm

In this section, we focus on decoding the transmitted word
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})\in C$ based on the set $Y$ of the
output words using a majority algorithm. For the rest of the section, we
assume that each word of $B_{t}(\mathbf{x})$ is outputted from a channel with
equal probability. Here we actually allow — unlike elsewhere in the paper —
some of the output words $\mathbf{y}_{i}$ to be equal. Probabilistic set-up
has been studied for different error types, for example, in [21, 22]. Our
approach differs from these articles in that we have given an upper limit for
the possible number of errors in any single channel. This allows us to have a
verifiability property in Theorem 28 unlike, for example, in [21, 22]. With
the verifiability property we mean that although we cannot be certain whether
we can deduce the transmitted word correctly before looking at the output
words, we can sometimes deduce the transmitted word with complete certainty
after seeing the output words. In other words, some output word sets have
properties which allow us to know the transmitted word with certainty.

First we describe the (well-known) majority algorithm using similar
terminology and notation as in [14]. The coordinates of the output words
$\mathbf{y}_{j}\in Y$ are denoted by
$\mathbf{y}_{j}=(y_{j,1},y_{j,2},\ldots,y_{j,n})$. Furthermore, the number of
zeros and ones in the $i$th coordinates of the output words are respectively
denoted by

$m_{i,0}=|\\{j\in\\{1,2,\ldots,N\\}\mid y_{j,i}=0\\}|$

and $m_{i,1}=N-m_{i,0}$. Based on $Y$, the _majority algorithm_ outputs the
word $\mathbf{z}_{Y}=\mathbf{z}=(z_{1},z_{2},\ldots,z_{n})\in\mathbb{F}^{n}$,
where

$z_{i}=\begin{cases}0&\text{ if }m_{i,0}>m_{i,1}\\\ ?&\text{ if
}m_{i,0}=m_{i,1}\\\ 1&\text{ if }m_{i,0}<m_{i,1}\text{.}\end{cases}$

In other words, for each coordinate of $\mathbf{z}$, we choose $?$, $0$ or $1$
based on whether the numbers of $0$s and $1$s are equal or which ones occur
more frequently. Observe that the coordinate $z_{i}$ outputted by the majority
algorithm is equal to $x_{i}$ if and only if at most $\lceil N/2\rceil-1$
errors occur in the $i$th coordinates of $Y$. Observe that the complexity of
the majority algorithm is $\Theta(Nn)$ and since reading all the output words
takes $\Theta(Nn)$ time, majority algorithm has optimal time complexity.

In [14, Example 1], it is shown that the majority algorithm does not always
output the correct transmitted word $\mathbf{x}$ when the number of channels
$N$ is equal to the value in Theorem 1 even though we take the $e$-error-
correction capability of $C$ into account. In [7], a modification of the
majority algorithm is presented for decoding and it is shown that if the
number of channels satisfies the bound of Theorem 1, then the output word of
the algorithm belongs to $B_{e}(\mathbf{x})$ and can be uniquely decoded to
$\mathbf{x}$. In what follows, we demonstrate that _with high probability_ the
word $\mathbf{z}$ is within distance $e$ from $\mathbf{x}$ with significantly
smaller number of channels (than in [7]). For example, the Monte Carlo
simulations for the values $t=5$ and $n=28$ are illustrated in Table 1.

For this purpose, we first consider a variant of the so called _multiple
birthday problem_ ; the multiple birthday problem has been studied, for
example, in [28] and [29]. Here we assume that $s$, $q$, $n$ and $t$ are
integers satisfying $2\leq s\leq q$ and $0\leq t\leq n$. A _throw_ consists of
placing $t$ balls randomly into $n$ buckets in such a way that each ball lands
in a different bucket and each subset of the buckets of size $t$ for a throw
has an equal probability. Denote then by $C_{t}(n,q,s)$ the event that after
$q$ throws, at least one bucket contains at least $s$ balls. Observe that if
$t=1$, then we are actually considering the multiple birthday problem;
furthermore, if ($t=1$ and) $s=2$, then the case is the (regular) birthday
problem. Furthermore, by $Pr[C_{t}(n,q,s)]$ we denote the probability that
there exist at least $s$ balls in a bucket. In the following theorem, we
present (based on $Pr[C_{t}(n,q,s)]$) a lower bound on the probability that
the output $\mathbf{z}$ of the majority algorithm is equal to $\mathbf{x}$.

######  Theorem 25.

Let $\mathbf{x}$ be the transmitted codeword of $C\subseteq\mathbb{F}^{n}$ and
$N$ the number of channels. The probability that the output $\mathbf{z}$ of
the majority algorithm is equal to $\mathbf{x}$ is at least

$1-Pr[C_{t}(n,N,\lceil N/2\rceil)]\text{.}$

###### Proof.

Let $P_{1}$ denote the probability that a coordinate of the outputs $Y$
contains at least $\lceil N/2\rceil$ errors when _at most_ $t$ errors occur in
each channel and $P_{2}$ the probability that a coordinate of the outputs $Y$
contains at least $\lceil N/2\rceil$ errors when _exactly_ $t$ errors occur in
each channel. It is immediate that $P_{1}\leq P_{2}$. Observe that the outputs
$Y$ of the $N$ channels in the case of the probability $P_{2}$ can be
represented as the above described variant of the multiple birthday problem as
follows: an output $\mathbf{y}_{i}\in Y$ with exactly $t$ errors can be
considered as a throw of $t$ balls to $n$ buckets, and there are $N$ throws in
total. Therefore, $P_{2}=Pr[C_{t}(n,N,\lceil N/2\rceil)]$ and the claim
follows. ∎

In order to obtain a lower bound on the probability $1-Pr[C_{t}(n,N,\lceil
N/2\rceil)]$, we require an upper bound on $Pr[C_{t}(n,N,\lceil N/2\rceil)]$.
In the following lemma, we present such an upper bound loosely based on a
recursive idea introduced in [28] for computing the exact probability of the
multiple birthday problem.

######  Lemma 26.

Let $s$, $q$, $n$ and $t$ be integers satisfying $2\leq s\leq q$ and $0\leq
t\leq n$. (i) Now the probability $Pr[C_{t}(n,q,s)]$ is at most

$\frac{t^{s}}{n^{s-1}}\sum_{i=s}^{q}\left(\binom{i-1}{s-1}\left(\frac{n-t}{n}\right)^{i-s}\left(1-Pr[C_{t-1}(n-1,i-1,s)]\right)\right)\text{,}$

where $Pr[C_{0}(n,q,s)]=0$ and $Pr[C_{t}(n,q,s)]=0$ if $q<s$. (ii)
Furthermore, we obtain that

$Pr[C_{t}(n,q,s)]\leq\frac{t^{s}}{n^{s-1}}\binom{q}{s}\text{.}$

###### Proof.

(i) Observe first that we clearly have $Pr[C_{0}(n,q,s)]=0$. Let then $i$ be
an integer such that $s\leq i\leq q$. Denote by $C_{t}(n,q,s,i)$ the event
that after the $i$th throw of $t$ balls there exist first time at least $s$
balls in a bucket; notice that after the $i$th throw it is possible that $s$
balls appear in multiple buckets. Using this notation, we have

$Pr[C_{t}(n,q,s)]=\sum_{i=s}^{q}Pr[C_{t}(n,q,s,i)]\text{.}$ (11)

The probability $Pr[C_{t}(n,q,s,i)]$ can be calculated based on the following
facts:

  * (i)

Let $B$ be one of the buckets that first attains $s$ balls. Clearly, the
bucket $B$ can be chosen in $n$ ways.

  * (ii)

The $s-1$ throws placing balls into $B$ before the $i$th throw can be chosen
from the previous $i-1$ throws in $\binom{i-1}{s-1}$ ways.

  * (iii)

As the probability that a ball of a single throw lands into $B$ is
$\binom{n-1}{t-1}/\binom{n}{t}$, the probability of the event that the $s$
selected throws put balls into $B$ is equal to

$\left(\frac{\binom{n-1}{t-1}}{\binom{n}{t}}\right)^{s}=\left(\frac{t}{n}\right)^{s}\text{.}$

  * (iv)

As the probability that no ball of a single throw lands into $B$ is
$\binom{n-1}{t}/\binom{n}{t}$, the probability of the event that no other
throw (than the $s$ selected ones) puts a ball into $B$ is equal to

$\left(\frac{\binom{n-1}{t}}{\binom{n}{t}}\right)^{i-s}=\left(\frac{n-t}{n}\right)^{i-s}\text{.}$

  * (v)

Finally, let $B^{\prime}$ denote the set of $n-1$ buckets other than $B$ and
$P_{i}$ denote the probability that no bucket in $B^{\prime}$ contains at
least $s$ balls after the first $i-1$ throws with the conditional assumption
that the events of (iii) and (iv) occur. Observe that if a ball of a throw
lands into $B$, then the throw puts $t-1$ balls into the buckets of
$B^{\prime}$, and otherwise $t$ balls land into $B^{\prime}$.

Thus, in conclusion, we have

$Pr[C_{t}(n,q,s,i)]=n\cdot\binom{i-1}{s-1}\cdot\left(\frac{t}{n}\right)^{s}\cdot\left(\frac{n-t}{n}\right)^{i-s}\cdot
P_{i}\text{.}$

Therefore, by (11), we obtain that $Pr[C_{t}(n,q,s)]$ is equal to

$\frac{t^{s}}{n^{s-1}}\sum_{i=s}^{q}\left(P_{i}\cdot\binom{i-1}{s-1}\left(\frac{n-t}{n}\right)^{i-s}\right)\text{.}$

Finally, notice that $P_{i}$ is equal to the probability that no bucket in
$B^{\prime}$ contains at least $s$ balls after $s-1$ throws with $t-1$ balls
and $i-s$ throws with $t$ balls have been performed in the buckets of
$B^{\prime}$ (corresponding to the events of (iii) and (iv), respectively).
Therefore, we obtain that that $P_{i}\leq 1-Pr[C_{t-1}(n-1,i-1,s)]$ since at
least $t-1$ balls are thrown $i-1$ times into the $n-1$ buckets of
$B^{\prime}$ (by the observation in (v)). Hence, the claim immediately
follows.

(ii) For the second upper bound, we first notice that by the so called _hockey
stick identity_ for the binomial coefficients, we have

$\sum_{i=s}^{q}\binom{i-1}{s-1}=\binom{q}{s}\text{.}$

Therefore, as $(n-t)/n\leq 1$ and the probability $P_{i}\leq 1$, the second
claim immediately follows. ∎

In the following theorem, the upper bound (ii) of the previous lemma is
applied to estimate the probability in Theorem 25. Observe that according to
the second claim of the theorem, the probability that the majority algorithm
outputs the transmitted word is as close to one as required when the rather
weak condition $n>2t\cdot\mathbbm{e}$, where $\mathbbm{e}$ is the Napier’s
constant, is satisfied and $N$ is large enough.

######  Theorem 27.

Let $C$ be an $e$-error-correcting code and $\mathbf{x}$ the transmitted word
of $C$. The probability that the output $\mathbf{z}$ of the majority algorithm
is equal to the transmitted word $\mathbf{x}$ is at least

$1-\frac{t^{\lceil N/2\rceil}}{n^{\lceil N/2\rceil-1}}\binom{N}{\lceil
N/2\rceil}\text{.}$

Furthermore, if $n>2t\cdot\mathbbm{e}$, then

$\lim_{N\to\infty}\left(1-Pr[C_{t}(n,N,\lceil N/2\rceil)]\right)=1\text{.}$

###### Proof.

The first claim follows immediately by applying Theorem 25 and Lemma 26.
Assuming $m$ and $r$ are integers such that $1\leq r\leq m$, we have the
following well-known upper bound on the binomial coefficient:

$\binom{m}{r}<\left(\frac{m\cdot\mathbbm{e}}{r}\right)^{r}\text{.}$

Applying this upper bound, we obtain that

$\begin{split}Pr[C_{t}(n,N,\lceil N/2\rceil)]&\leq\frac{t^{\lceil
N/2\rceil}}{n^{\lceil N/2\rceil-1}}\binom{N}{\lceil N/2\rceil}\\\
&<\frac{t^{\lceil N/2\rceil}}{n^{\lceil
N/2\rceil-1}}\left(\frac{N\cdot\mathbbm{e}}{\lceil N/2\rceil}\right)^{\lceil
N/2\rceil}\\\ &\leq
2t\cdot\mathbbm{e}\left(\frac{2t\cdot\mathbbm{e}}{n}\right)^{\lceil
N/2\rceil-1}\to 0\text{.}\end{split}$

as $N\to\infty$ since $n>2t\cdot\mathbbm{e}$. Thus, the second claim follows.
∎

Table 1: The lower bound of Theorem 25 together with Lemma 26 and Theorem 27 as well as the Monte Carlo approximations with $100000$ samples of the probability that $\mathbf{z}=\mathbf{x}$ when $n=28$, $t=5$ and $N=11,21,31,41,101$. $N$ | Theorem 25 and Lemma 26 | Theorem 27 | Simulation
---|---|---|---
11 | $0.8199$ | $0.5806$ | $0.8615$
21 | $0.9901$ | $0.9419$ | $0.9929$
31 | $0.9994$ | $0.9910$ | $0.9997$
41 | $0.9997$ | $0.9985$ | $1.000$
101 | $1.000$ | $1.000$ | $1.000$

In Table 1, we illustrate the various approaches to approximate the
probability that the output $\mathbf{z}$ of the majority algorithm is equal to
the transmitted word $\mathbf{x}$ when $t=5$ and $n=28$ (satisfying the
condition of Theorem 27): the lower bound on the probabilities of Theorem 25
together with Lemma 26 and Theorem 27 as well as the Monte Carlo simulations
with $100000$ samples. Observe that the majority algorithm outputs
$\mathbf{z}=\mathbf{x}$ with high probability for significantly smaller number
$N$ of channels compared to Theorem 1, for which the required number of
channels is $41709$ when $e=0$, $t=5$ and $n=28$; here $e=0$ is chosen in
order to meet the requirement $\mathbf{z}=\mathbf{x}$.

Above, we saw that it is highly probable that the majority algorithm works
correctly with significantly smaller number of channels compared to the one
given in Theorem 1, which was required in the algorithm presented in [7]. In
what follows, we take another approach on the majority algorithm and show that
if a certain criteria (see Theorem 28) is met for the outputs $Y$, then we can
verify that the output $\mathbf{z}$ of the majority algorithm belongs to
$B_{e}(\mathbf{x})$. For this purpose, notice first that the total number of
errors occurring in the $i$th coordinates of the outputs $Y$ is at least
$m_{i}=\min\\{m_{i,0},m_{i,1}\\}$. On the other hand, there happens at most
$t$ errors in each channel and, hence, the total number of errors in the
channels is at most $tN$. Thus, we obtain that

$\sum_{i=1}^{n}m_{i}\leq tN\text{.}$ (12)

Furthermore, if $\mathbf{x}=\mathbf{z}$, then the number of errors is exactly
$\sum_{i=1}^{n}m_{i}$. In addition, if $\mathbf{x}\neq\mathbf{z}$, then for
each coordinate $i$ in which the words differ,
$\max\\{m_{i,0},m_{i,1}\\}=N-m_{i}$ is contributed to the sum of errors
(instead of $m_{i}$). The following theorem is based on the idea that even the
modified sum (in the left hand side of (13)) has to satisfy Inequality (12).

######  Theorem 28.

Let $C$ be an $e$-error-correcting code, $m^{\prime}_{i}$ be the integers
$m_{i}$ ordered in such a way that $m^{\prime}_{1}\geq
m^{\prime}_{2}\geq\cdots\geq m^{\prime}_{n}$ and $\mathbf{z}$ be the output
word of the majority algorithm. We have $d(\mathbf{x},\mathbf{z})\leq k$ if
$k$ is a positive integer such that

$\sum_{i=1}^{k+1}(N-m^{\prime}_{i})+\sum_{i=k+2}^{n}m^{\prime}_{i}>tN\text{.}$
(13)

###### Proof.

Let $k$ be a positive integer satisfying (13). Suppose to the contrary that
$d(\mathbf{x},\mathbf{z})\geq k+1$. This implies that for at least $k+1$
coordinates $i$, the number of errors is $\max\\{m_{i,0},m_{i,1}\\}=N-m_{i}$.
Therefore, by the ordering of $m^{\prime}_{i}$, the number of errors is at
least

$\sum_{i=1}^{k+1}(N-m^{\prime}_{i})+\sum_{i=k+2}^{n}m^{\prime}_{i}\
(>tN)\text{.}$

Thus, due to (13), we have a contradiction with the maximum number of errors
being $tN$ and the claim follows. ∎

Observe that (13) allows us to estimate the accuracy of $\mathbf{z}$. In
particular, if $k\leq e$, then $d(\mathbf{x},\mathbf{z})\leq k\leq e$ and the
word $\mathbf{z}$ can be decoded to $\mathbf{x}$ as $C$ is an $e$-error-
correcting code. Furthermore, if $k>e$, then $\mathbf{x}\in C\cap
B_{k}(\mathbf{z})$ and the decoding algorithm outputs a list of words
containing $\mathbf{x}$. Moreover, the size of the list is at most
$\max_{\mathbf{u}\in\mathbb{F}^{n}}|C\cap B_{k}(\mathbf{u})|$, which is
closely related to the traditional list decoding (see [27]). In conclusion,
the theorem gives us a condition guaranteeing that the transmitted word can be
decoded uniquely or with certain accuracy.

Table 2: The Monte Carlo approximations with $100000$ samples of the probability for $e$ satisfying the condition of Theorem 28 when $n=24$, $t=7$, $e=2,3,4$ and $N=11,21,31,41$. $N\backslash e$ | $2$ | $3$ | $4$
---|---|---|---
11 | $0.068$ | $0.260$ | $0.587$
21 | $0.369$ | $0.790$ | $0.972$
31 | $0.701$ | $0.971$ | $0.999$
41 | $0.887$ | $0.997$ | $0.999$

The probability, that in Theorem 28 there exists a certain $k$ satisfying
(13), can be analysed analytically as shown below, but first we approximate it
using Monte Carlo simulations. In Table 2, the probability is approximated
using $100000$ samples for $n=24$, $t=7$, $e=2,3,4$ and varying number of
channels $N$; here we choose $k=e$ and we strive for the exact transmitted
word $\mathbf{x}$. From the table, we can notice that as the number of
channels increases it becomes very likely that Inequality (13) is satisfied
and that the majority algorithm together with the $e$-error-correction
capability of $C$ verifiably outputs the transmitted word $\mathbf{x}$.

In what follows, we further study analytically the probability that for a set
$Y$ of outputs there exists an integer $k$ satisfying the conditions of
Theorem 28. For this purpose, let $C_{t}^{\prime}(n,q,s)$ denote the event
that after $q$ random throws of $t$ balls, each of the $n$ buckets contains at
most $s$ balls. Furthermore, regarding the number of errors occurring in the
channels (in total), let $Er(r)$ denote the event that at least $r$ errors
happen in the outputs $Y$ in total. Moreover, let $p(N)$ denote the parity of
$N$, i.e., $p(N)=1$ if $N$ is odd, and otherwise $p(N)=0$. Now we are ready to
formulate the following theorem.

######  Theorem 29.

Let $C$ be an $e$-error-correcting code and $\alpha$ be a positive integer
smaller than $\lceil N/2\rceil$. The probability that a positive integer $k$
satisfies (13) is at least

$Pr[C_{t}^{\prime}(n,N,\lceil N/2\rceil-\alpha)\cap
Er(tN-(k+1)(2\alpha-p(N))+1)]\text{.}$

###### Proof.

Assume that (i) at most $\lceil N/2\rceil-\alpha$ errors occur in each
coordinate of the outputs $Y$ and that (ii) at least
$tN-(k+1)(2\alpha-p(N))+1$ errors occur in the channels in total (when at most
$t$ errors occur in each channel). Now the difference
$(N-m_{i})-m_{i}=N-2m_{i}$ gives the number of additional errors occurring in
a coordinate in the case that $\max\\{m_{i,0},m_{i,1}\\}=N-m_{i}$ errors
happen instead of $m_{i}=\min\\{m_{i,0},m_{i,1}\\}$ errors. The difference
$(N-m_{i})-m_{i}$ can be estimated based on the parity of $N$ as follows:

  * •

If $N$ is even, then $N-2m_{i}\geq N-2(\lceil
N/2\rceil-\alpha)=2\alpha=2\alpha-p(N)$.

  * •

If $N$ is odd, then $N-2m_{i}\geq N-2(\lceil
N/2\rceil-\alpha)=2\alpha-1=2\alpha-p(N)$.

In conclusion, we have $N-2m_{i}\geq 2\alpha-p(N)$. Therefore, using the
notation of Theorem 28, we have

$\begin{split}&\quad\sum_{i=1}^{k+1}(N-m^{\prime}_{i})+\sum_{i=k+2}^{n}m^{\prime}_{i}\\\
&\geq\sum_{i=1}^{n}m^{\prime}_{i}+(k+1)(2\alpha-p(N))>tN\end{split}$

since $\sum_{i=1}^{n}m^{\prime}_{i}\geq tN-(k+1)(2\alpha-2p(N))+1$ by the
assumption (ii). Thus, the integer $k$ satisfies the condition of Theorem 28.

In order to estimate the probability of the events of the assumptions (i) and
(ii) occurring simultaneously, we denote by $A$ the event that at most $\lceil
N/2\rceil-\alpha$ errors occur in each coordinate of the outputs $Y$ when at
most $t$ errors happen in each channel. Clearly, since the event
$C_{t}^{\prime}(n,N,\lceil N/2\rceil-\alpha)$ can be interpreted as the
outputs $Y$ of the channels as in Theorem 25, we have
$C_{t}^{\prime}(n,N,\lceil N/2\rceil-\alpha)\subseteq A$. Hence, the
probability of the events of the assumptions (i) and (ii) occurring
simultaneously is at least $Pr[A\cap Er(tN-(k+1)(2\alpha-p(N))+1)]\geq
Pr[C_{t}^{\prime}(n,N,\lceil N/2\rceil-\alpha)\cap
Er(tN-(k+1)(2\alpha-p(N))+1)]$ and the claim follows. ∎

Observe that if $A$ and $B$ are events (independent or dependent), then the
probability of the event $A\cap B$ can be estimated as follows by the
inclusion-exclusion principle:

$Pr[A\cap B]=Pr[A]+Pr[B]-Pr[A\cup B]\geq Pr[A]+Pr[B]-1\text{.}$

Applying this lower bound to Theorem 29, the following corollary is
immediately obtained.

######  Corollary 30.

Let $C$ be an $e$-error-correcting code and $\alpha$ be a positive integer.
The probability that a positive integer $k$ satisfies (13) is at least
$Pr[C_{t}^{\prime}(n,N,\lceil
N/2\rceil-\alpha)]+Pr[Er(tN-(k+1)(2\alpha-p(N))+1)]-1$.

In what follows, we discuss how the value $\alpha$ in the previous corollary
should be chosen in order for the lower bound to be as close to $1$ as
desired. Consider first the approximation of the probability
$Pr[Er(tN-(k+1)(2\alpha-p(N))+1)]$. Let $X$ be a categorical random variable
representing the number of errors occurring in a channel. Hence, for
$r=0,1,\ldots,t$, the probability

$Pr[X=r]=p_{r}=\frac{\binom{n}{r}}{\sum_{i=0}^{t}\binom{n}{i}}\text{.}$

The expected value of the distribution corresponding to $X$ is

$\mu=E(X)=\sum_{r=0}^{t}rp_{r}$

and the variance is

$\sigma^{2}=Var(X)=E(X^{2})-\mu^{2}=\sum_{r=0}^{t}r^{2}p_{r}-\mu^{2}\text{.}$

Let

$S_{N}=X_{1}+X_{2}+\cdots+X_{N}$

be the sum of independent and identically distributed random variables $X_{i}$
each equal to $X$. Clearly, we have
$Pr[Er(tN-(k+1)(2\alpha-p(N))+1)]=Pr[S_{N}\geq tN-(k+1)(2\alpha-p(N))+1]$. By
the Central Limit Theorem (for example, see [30, Section 5.4]), the sum
$S_{N}$ can be approximated (for large enough values of $N$) by the normal
distribution $\mathcal{N}(\mu N,\sigma\sqrt{N})$, where $\mu N$ and
$\sigma\sqrt{N}$ are the expected value and the standard deviation of $S_{N}$,
respectively. A usual approach on the normal distribution is to use the
following concept of _confidence intervals_. For a positive integer $h$, the
probability

$Pr[\mu N-h\cdot\sigma\sqrt{N}\leq S_{N}\leq\mu N+h\cdot\sigma\sqrt{N}]$

rapidly approaches one as $h$ increases; even for $h=4$ the probability is
approximately $0.999937$. Straightforwardly, we obtain that
$tN-(k+1)(2\alpha-p(N))+1\leq\mu N-h\cdot\sigma\sqrt{N}$ if and only if

$\alpha\geq\frac{(t-\mu)N+h\cdot\sigma\sqrt{N}+1+p(N)(k+1)}{2(k+1)}(>0)\text{.}$

Now we have $Pr[S_{N}\geq tN-(k+1)(2\alpha-p(N))+1]\geq Pr[\mu
N-h\cdot\sigma\sqrt{N}\leq S_{N}\leq\mu N+h\cdot\sigma\sqrt{N}]$.

In order to estimate the lower bound of Corollary 30 for some fixed $n$, $e$
and $t$, we first choose a suitable positive integer $h$ such that the
previous lower bound of $Pr[S_{N}\geq tN-(k+1)(2\alpha-p(N))+1]$ is as large
as desired. Then, according to the following lemma, we have a lower bound on
the probability $Pr[C^{\prime}(n,tN,\lceil N/2\rceil-\alpha)]$, which
approaches $1$ as the number $N$ of channels tends to infinity. Hence, for
carefully chosen $h$, $\alpha$ and $N$, the probability discussed in Corollary
30 gets as close to $1$ as desired. Furthermore, notice that the proof of the
lemma is based on similar ideas as the one of Theorem 27.

######  Lemma 31.

Let $h$ and $k$ be (fixed) positive integers and
$\alpha=\lceil((t-\mu)N+h\cdot\sigma\sqrt{N}+1+p(N)(k+1))/(2(k+1))\rceil$.
Then the probability $Pr[C_{t}^{\prime}(n,N,\lceil N/2\rceil-\alpha)]$ is at
least

$1-\frac{t^{\lceil N/2\rceil-\alpha+1}}{n^{\lceil
N/2\rceil-\alpha}}\binom{N}{\lceil N/2\rceil-\alpha+1}\text{.}$

Furthermore, denoting $A=(k-(t-\mu))/(k+1)$, we obtain that if $t-\mu<k$ and
$n>2t\cdot\mathbbm{e}/A$, then

$\lim_{N\to\infty}Pr[C_{t}^{\prime}(n,N,\lceil N/2\rceil-\alpha)]=1\text{.}$

###### Proof.

The lower bound on $Pr[C_{t}^{\prime}(n,N,\lceil
N/2\rceil-\alpha)]=1-Pr[C_{t}(n,N,\lceil N/2\rceil-\alpha+1)]$ immediately
follows by Lemma 26(ii) and hence, the first claim follows. Assume then that
$t-\mu<k$ and $n>2t\cdot\mathbbm{e}/A$. For the limit of second claim, observe
first that $h\cdot\sigma\sqrt{N}+1+p(N)(k+1)\leq N$ when $N$ is large enough
since $k$ is a (fixed) constant. Therefore, by straightforward calculations,
we have

$\alpha\leq\frac{(t-\mu+1)N}{2(k+1)}+1\text{.}$ (14)

This further implies that

$1-\frac{2(\alpha-1)}{N}\geq
1-\frac{t-\mu+1}{k+1}=\frac{k-(t-\mu)}{k+1}=A\text{.}$

Applying this inequality, for large enough $N$, we have

$\begin{split}&\quad Pr[C_{t}^{\prime}(n,N,\lceil N/2\rceil-\alpha)]\\\
&>1-\frac{t^{\lceil N/2\rceil-\alpha+1}}{n^{\lceil
N/2\rceil-\alpha}}\left(\frac{N\cdot\mathbbm{e}}{N/2-\alpha+1}\right)^{\lceil
N/2\rceil-\alpha+1}\\\
&=1-2t\mathbbm{e}\left(\frac{2t\mathbbm{e}}{n}\right)^{\lceil
N/2\rceil-\alpha}\left(\frac{1}{1-\frac{2(\alpha-1)}{N}}\right)^{\lceil
N/2\rceil-\alpha+1}\\\ &\geq
1-2t\mathbbm{e}\left(\frac{2t\mathbbm{e}}{n}\right)^{\lceil
N/2\rceil-\alpha}\left(\frac{1}{A}\right)^{\lceil N/2\rceil-\alpha+1}\\\
&=1-\frac{2t\mathbbm{e}}{A}\left(\frac{2t\mathbbm{e}}{An}\right)^{\lceil
N/2\rceil-\alpha}\text{.}\end{split}$

Now the probability

$Pr[C_{t}^{\prime}(n,N,\lceil
N/2\rceil-\alpha)]>1-\frac{2t\mathbbm{e}}{A}\left(\frac{2t\mathbbm{e}}{An}\right)^{\lceil
N/2\rceil-\alpha}$

and the lower bound approaches one as $N$ tends to infinity since
$n>2t\cdot\mathbbm{e}/A$ and $\lceil N/2\rceil-\alpha\to\infty$ due to
Inequality (14) and the assumption $t-\mu<k$. Thus, the second claim follows.
∎

Notice that the condition $t-\mu<k$ of the lemma is rather undemanding for our
purposes. Observe that the lemma is usually applied for $k=e$ as then the
output $\mathbf{z}$ of the majority algorithm can be uniquely decoded to the
transmitted word $\mathbf{x}$ according to Theorem 28. In this case, the
condition can be formulated as $\ell<\mu$. Moreover, we trivially have
$\mu>tp_{t}=t\binom{n}{t}/V(n,t)$. Furthermore, we have the estimation

$\binom{n}{t-a}\leq\frac{t^{a}}{\prod_{i=1}^{a}n-t+i}\binom{n}{t}\leq\frac{t^{a}}{(n-t+1)^{a}}\binom{n}{t}.$

Thus, if $n\geq t^{2}+t-1$, we obtain

$\mu>\frac{t}{\sum_{i=0}^{t}\frac{t^{i}}{(n-t+1)^{i}}}\geq\frac{t}{\sum_{i=0}^{t}\frac{1}{t^{i}}}>\frac{t}{\sum_{i=0}^{\infty}\frac{1}{t^{i}}}=t-1\text{,}$

where the assumption $n\geq t^{2}+t-1$ is used in the second inequality.
Furthermore, we have $t-1\geq\ell$ when $e\geq 1$. Therefore, as $\mu>t-1$, it
is actually enough for the requirement $\ell<\mu$ that $t-1\geq\ell$. In other
words, condition $t-\mu<e$ is satisfied when $n\geq t^{2}+t-1$ and $e\geq 1$.
Moreover, even this quite meagre condition for $n$ is more than we actually
need due to rather crude estimates; for example, the condition $t-\mu<e$ is
met for the values $n=10$, $e=1$ and $t=5$ (as well as for all $n>10$ for the
same choices of $e$ and $t$).

As explained before the previous lemma, we can get the lower bound of
Corollary 30 as close to $1$ as desired for carefully chosen $h$, $\alpha$ and
$N$ by combining Lemma 31 with the discussions on the probability
$Pr[Er(tN-(k+1)(2\alpha-p(N))+1)]=Pr[S_{N}\geq tN-(k+1)(2\alpha-p(N))+1]$. For
example, if $n=62$, $t=7$, $(k=)\ e=2$ and $h=3$, then the conditions of Lemma
31 are satisfied and the lower bound of Corollary 30 is approximately $0.997$
when $N=41$.

## References

  * [1] V. Junnila, T. Laihonen, and T. Lehtilä, “On the list size in the Levenshtein’s sequence reconstruction problem,” in _2022 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2022, pp. 510–515.
  * [2] V. I. Levenshtein, “Efficient reconstruction of sequences,” _IEEE Trans. Inform. Theory_ , vol. 47, no. 1, pp. 2–22, 2001.
  * [3] V. Levenshtein, E. Konstantinova, E. Konstantinov, and S. Molodtsov, “Reconstruction of a graph from 2-vicinities of its vertices,” _Discrete Appl. Math._ , vol. 156, pp. 1399–1406, 2008.
  * [4] R. Gabrys and E. Yaakobi, “Sequence reconstruction over the deletion channel,” _IEEE Trans. Inform. Theory_ , vol. 64, no. 4, pp. 2924–2931, 2018\.
  * [5] M. Horovitz and E. Yaakobi, “Reconstruction of sequences over non-identical channels,” _IEEE Trans. Inform. Theory_ , vol. 65, no. 2, pp. 1267–1286, 2018.
  * [6] M. Abu-Sini and E. Yaakobi, “On list decoding of insertions and deletions under the reconstruction model,” in _Proceedings of 2021 IEEE International Symposium on Information Theory_ , 2021, pp. 1706–1711.
  * [7] ——, “On Levenshtein’s reconstruction problem under insertions, deletions, and substitutions,” _IEEE Trans. Inform. Theory_ , vol. 67, no. 11, pp. 7132–7158, 2021.
  * [8] V. I. Levenshtein, “Efficient reconstruction of sequences from their subsequences or supersequences,” _Journal of Combinatorial Theory, Series A_ , vol. 93, no. 2, pp. 310–332, 2001.
  * [9] E. Yaakobi, J. Bruck, and P. H. Siegel, “Constructions and decoding of cyclic codes over $b$-symbol read channels,” _IEEE Trans. Inform. Theory_ , vol. 62, no. 4, pp. 1541–1551, 2016.
  * [10] J. Bornholt, R. Lopez, D. M. Carmean, L. Ceze, G. Seelig, and K. Strauss, “A DNA-based archival storage system,” _ACM SIGARCH Computer Architecture News_ , vol. 44, no. 2, pp. 637–649, 2016.
  * [11] G. M. Church, Y. Gao, and S. Kosuri, “Next-generation digital information storage in DNA,” _Science_ , vol. 337, no. 6102, pp. 1628–1628, 2012.
  * [12] R. N. Grass, R. Heckel, M. Puddu, D. Paunescu, and W. J. Stark, “Robust chemical preservation of digital information on DNA in silica with error-correcting codes,” _Angew. Chem. Int. Edit._ , vol. 54, no. 8, pp. 2552–2555, 2015.
  * [13] S. H. T. Yazdi, H. M. Kiah, E. Garcia-Ruiz, J. Ma, H. Zhao, and O. Milenkovic, “DNA-based storage: Trends and methods,” _IEEE Transactions on Molecular, Biological and Multi-Scale Communications_ , vol. 1, no. 3, pp. 230–248, 2015.
  * [14] E. Yaakobi and J. Bruck, “On the uncertainty of information retrieval in associative memories,” _IEEE Trans. Inform. Theory_ , vol. 65, no. 4, pp. 2155–2165, 2018.
  * [15] ——, “On the uncertainty of information retrieval in associative memories,” in _Proceedings of 2012 IEEE International Symposium on Information Theory_ , 2012, pp. 106–110.
  * [16] M. Cheraghchi, R. Gabrys, O. Milenkovic, and J. Ribeiro, “Coded trace reconstruction,” _IEEE Transactions on Information Theory_ , vol. 66, no. 10, pp. 6084–6103, 2020.
  * [17] V. Junnila and T. Laihonen, “Information retrieval with varying number of input clues,” _IEEE Trans. Inform. Theory_ , vol. 62, no. 2, pp. 625–638, 2016.
  * [18] ——, “Codes for information retrieval with small uncertainty,” _IEEE Trans. Inform. Theory_ , vol. 60, no. 2, pp. 976–985, 2014.
  * [19] T. Laihonen and T. Lehtilä, “Improved codes for list decoding in the Levenshtein’s channel and information retrieval,” in _Proceedings of 2017 IEEE International Symposium on Information Theory_ , 2017, pp. 2643–2647.
  * [20] T. Laihonen, “On t-revealing codes in binary Hamming spaces,” _Information and Computation_ , vol. 268, 2019.
  * [21] T. Batu, S. Kannan, S. Khanna, and A. McGregor, “Reconstructing strings from random traces,” in _Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms_ , 2004, pp. 910–918.
  * [22] K. Viswanathan and R. Swaminathan, “Improved string reconstruction over insertion-deletion channels,” in _Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms_ , 2008, pp. 399–408.
  * [23] V. Junnila, T. Laihonen, and T. Lehtilä, “On Levenshtein’s channel and list size in information retrieval,” _IEEE Trans. Inform. Theory_ , vol. 67, no. 6, pp. 3322–3341, 2020.
  * [24] G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein, _Covering codes_ , ser. North-Holland Mathematical Library. Amsterdam: North-Holland Publishing Co., 1997, vol. 54.
  * [25] N. Sauer, “On the density of families of sets,” _J. Comb. Theory A_ , vol. 13, no. 1, pp. 145–147, 1972.
  * [26] S. Shelah, “A combinatorial problem; stability and order for models and theories in infinitary languages,” _Pac. J. Math._ , vol. 41, no. 1, pp. 247–261, 1972.
  * [27] V. Guruswami, _List decoding of error-correcting codes_. ProQuest LLC, Ann Arbor, MI, 2001, thesis (Ph.D.)–Massachusetts Institute of Technology. [Online]. Available: http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:0803408
  * [28] K. Suzuki, D. Tonien, K. Kurosawa, and K. Toyota, “Birthday paradox for multi-collisions,” in _Information Security and Cryptology – ICISC 2006_ , M. S. Rhee and B. Lee, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 29–40.
  * [29] M. Kounavis, S. Deutsch, D. Durham, and S. Komijani, “Non-recursive computation of the probability of more than two people having the same birthday,” in _2017 IEEE Symposium on Computers and Communications (ISCC)_ , 2017, pp. 1263–1270.
  * [30] H. Tijms, _Understanding probability_ , 3rd ed. Cambridge: Cambridge University Press, 2012.

## Appendix

###### Proof of Corollary 15..

Let us now consider the proof of Corollary 15 in the case where $d=2e+1$. The
proof is quite similar to the case with $d=2e+2$. Although the first half of
the proof in Corollary 15 works for $d=2e+1$, we start from the beginning
since using set $W^{\prime}_{w}$ instead of $W_{w}$ is better suited for our
goal.

First we study the second binomial sum in the claim of Theorem 11 when $h=3$.
Then we show that it gives equivalent result with Theorem 15 when $d=2e+1$.
Since the binomial sum in Equation (2) is equivalent with the binomial sum in
Equation (1), the claim follows.

Let us now consider the value we get for $N_{3}$ in the second binomial sum of
Theorem 11 when $h=3$. We have

$\displaystyle N_{3}=$ $\displaystyle
V(n,\ell-1)+\sum_{w\geq\ell}\sum_{(i_{2},i_{3},i_{4})\in
W^{\prime}_{w}}\binom{n-3e-2}{w-i_{2}-i_{3}-i_{4}}\binom{e+1}{i_{2}}\binom{e+1}{i_{3}}\binom{e}{i_{4}}.$

In what follows, we have renamed the indices for convenience in such a way
that $i_{4}$ corresponds to $i_{1}$ of Theorem 11 (the index $i_{1}$ will be
saved for later use in the proof). Moreover, we have
$W^{\prime}_{w}=\\{(i_{2},i_{3},i_{4})\mid\text{for
}j\in[2,3]:(w+1-\ell)/2\leq i_{j}\leq e+1\text{ and }(w-\ell)/2\leq i_{4}\leq
e,w\geq i_{2}+i_{3}+i_{4}\\}$. Again, if we have some binomial coefficients
with $i_{j}<0$ for some $j$, then we use the common convention that the
binomial coefficient attains the value $0$. Then, as in the case $d=2e+2$, we
obtain that $N_{3}=\sum_{w\geq 0}\sum_{(i_{2},i_{3},i_{4})\in
W^{\prime}_{w}}\binom{n-3e-2}{w-i_{2}-i_{3}-i_{4}}\binom{e+1}{i_{2}}\binom{e+1}{i_{3}}\binom{e}{i_{4}}$.

Let us denote by $i_{1}=w-i_{2}-i_{3}-i_{4}$. We again get that $2i_{2}\geq
i_{1}+i_{2}+i_{3}+i_{4}-\ell+1$ and similar inequality for $i_{3}$. Moreover,
for $i_{4}$, we have $2i_{4}\geq i_{1}+i_{2}+i_{3}+i_{4}-\ell$. Since we do
not have to take into account lower bound $i_{1}\geq 0$ (cases with $i_{1}<0$
increase binomial sum by $0$) or the cases with $i_{j}>e+1$ for
$j\in\\{2,3,4\\}$, we can consider following system of inequalities:

$\displaystyle i_{2}\geq$ $\displaystyle i_{1}+i_{3}+i_{4}-\ell+1$ (15)
$\displaystyle i_{3}\geq$ $\displaystyle i_{1}+i_{2}+i_{4}-\ell+1$ (16)
$\displaystyle i_{4}\geq$ $\displaystyle i_{1}+i_{2}+i_{3}-\ell.$ (17)

Our goal is to show that this system of inequalities is equivalent with the
following system of inequalities:

$\displaystyle i_{4}$ $\displaystyle\leq\ell-1-i_{1},$ (18) $\displaystyle
i_{3}$ $\displaystyle\leq\ell-1-i_{1},$ (19) $\displaystyle
i_{1}+i_{3}+i_{4}-(\ell-1)\leq i_{2}$
$\displaystyle\leq\ell-1/2-i_{1}-|i_{4}-i_{3}+1/2|.$ (20)

Let us first show that the second system of inequalities follows from the
first system of inequalities.

Inequality (18) follows from

$i_{4}=w-i_{1}-i_{2}-i_{3}\leq w-i_{1}-2(w-\ell+1)/2=\ell-1-i_{1}.$

We obtain Inequality (19) in similar manner. Indeed,

$i_{3}=w-i_{1}-i_{2}-i_{4}\leq w-i_{1}-(w-\ell+1)/2-(w-\ell)/2=\ell-1/2-i_{1}$

and the upper bound follows from the fact that $i_{3}$ is an integer.
Moreover, from Inequalities (16) and (17) we obtain
$i_{2}\leq\ell-1/2-i_{1}-i_{4}-1/2+i_{3}$ and
$i_{2}\leq\ell-1/2-i_{1}-i_{3}+i_{4}+1/2$, respectively. Together, these imply

$i_{2}\leq\ell-1/2-i_{1}-|i_{4}+1/2-i_{3}|.$

Finally, the lower bound inequality in (20) follows directly from (15).

Let us then show that the first system of inequalities follows from the second
one. First of all, Inequality (15) follows immediately from Inequality (20).
Assume first that $i_{4}+1/2>i_{3}$. Then the upper bound of Inequality (20)
is $i_{2}\leq\ell-1-i_{1}-i_{4}+i_{3}$. This implies Inequality (16) and
inequality (17) since

$i_{4}\geq i_{3}\geq i_{1}+i_{2}+i_{4}-\ell+1\geq i_{1}+i_{2}+i_{3}-\ell+1.$

Notice that we cannot attain the lower bound in Inequality (17) in this case.

When $i_{3}>i_{4}+1/2$, then the upper bound of Inequality (20) is
$i_{2}\leq\ell-i_{1}-i_{3}+i_{4}$. In this case $i_{4}\geq
i_{1}+i_{2}+i_{3}-\ell$ and since $i_{3}>i_{4}$, both lower bounds, (16) and
(17), follow.

Finally, we may add lower bounds $i_{j}\geq 0$ for all $j\in\\{1,2,3,4\\}$ due
to binomial coefficient context. Similarly we notice that if $i_{1}\geq\ell$,
then $i_{3}<0$. Thus, we may also add upper bound $i_{1}\leq\ell-1$. Now, we
are ready to compare this bound with the bound of Theorem 2 by Yaakobi and
Bruck.

When we have $d=2e+1$, Theorem 2 can be presented in the following way: Let

$N\geq\sum_{h_{1},h_{2},h_{3},h_{4}}\binom{n-3e-2}{h_{1}}\binom{e+1}{h_{2}}\binom{e+1}{h_{3}}\binom{e}{h_{4}}+1$
for

  * •

$0\leq h_{1}\leq\ell-1$,

  * •

$h_{1}-\ell\leq h_{4}\leq\ell-1-h_{1}$,

  * •

$e+2-\ell+h_{1}\leq h_{3}\leq t-(h_{1}+h_{4})$ and

  * •

$\max\\{h_{1}-h_{3}-h_{4}+2e+2-\ell,h_{1}+h_{3}+h_{4}-\ell+1\\}\leq
h_{2}\leq\ell-1-(h_{1}+h_{4}-h_{3})$,

then $\mathcal{L}\leq 2$ for any $e$-error-correcting code $C$. Next, we
modify the presentation we got for $N_{3}$ into the formulation above.

Let us denote by $i^{\prime}_{2}=e+1-i_{2}$ and by $i^{\prime}_{3}=e+1-i_{3}$.
Observe that $\binom{e+1}{i^{\prime}_{j}}=\binom{e+1}{i_{j}}$ for
$j\in\\{2,3\\}$. Notice that we have $i_{4}\geq 0\geq i_{1}-\ell$ and
$\binom{e+1}{i_{4}}=0$ when $i_{4}<0$. Hence, we may just replace this lower
bound by $i_{1}-\ell$. Moreover, we have $0\leq i_{3}\leq\ell-1-i_{1}$. Hence,
$e+1\geq i^{\prime}_{3}\geq i_{1}+e+2-\ell$. Notice that $t-(i_{1}+i_{4})\geq
e+1$ since $i_{1}+i_{4}\leq\ell-1$ by Inequality (18), and
$\binom{e+1}{i^{\prime}_{3}}=0$ when $i^{\prime}_{3}>e+1$.

For $i_{2}$ we have $i_{1}+i_{3}+i_{4}-(\ell-1)\leq
i_{2}\leq\ell-1/2-i_{1}-|i_{4}+1/2-i_{3}|$ and hence,
$\ell-1-(i_{1}+i_{4}-i^{\prime}_{3})\geq
i^{\prime}_{2}\geq-\ell+e+3/2+i_{1}+|i_{4}+1/2-i_{3}|=e+3/2-\ell+i_{1}+|i_{4}+i^{\prime}_{3}-e-1/2|=\max\\{i_{1}-i^{\prime}_{3}-i_{4}+2e+2-\ell,i_{1}+i^{\prime}_{3}+i_{4}-\ell+1\\}$.
Hence, we get the claim. ∎