# Codes for the Z-channel

Nikita Polyanskii Nikita Polyanskii is with the IOTA Foundation. Email:
<EMAIL_ADDRESS>His research was conducted in part during October
2020 - December 2021 with the Technical University of Munich and the Skolkovo
Institute of Science and Technology. His work was supported by the German
Research Foundation (Deutsche Forschungsgemeinschaft, DFG) under Grant No.
WA3907/1-1 and the Russian Foundation for Basic Research (RFBR) under Grant
No. 20-01-00559 Yihan Zhang Yihan Zhang is with the Institute of Science and
Technology Austria. Email<EMAIL_ADDRESS>Supported by funding from
the European Union’s Horizon 2020 research and innovation programme under
grant agreement No 682203-ERC-[Inf-Speed-Tradeoff].

###### Abstract

This paper is a collection of results on combinatorial properties of codes for
the _Z-channel_. A Z-channel with error fraction $\tau$ takes as input a
length-$n$ binary codeword and injects in an adversarial manner $n\tau$
_asymmetric_ errors, i.e., errors that only zero out bits but do not flip
$0$’s to $1$’s. It is known that the largest $(L-1)$-list-decodable code for
the Z-channel with error fraction $\tau$ has exponential (in $n$) size if
$\tau$ is less than a critical value that we call the _Plotkin point_ and has
constant size if $\tau$ is larger than the threshold. The $(L-1)$-list-
decoding Plotkin point is known to be $L^{-\frac{1}{L-1}}-L^{-\frac{L}{L-1}}$,
which equals $1/4$ for unique-decoding with $L-1=1$. In this paper, we derive
various results for the size of the largest codes above and below the list-
decoding Plotkin point. In particular, we show that the largest $(L-1)$-list-
decodable code $\varepsilon$-above the Plotkin point has size
$\Theta_{L}(\varepsilon^{-3/2})$ for any $L-1\geq 1$. We also devise upper and
lower bounds on the exponential size of codes below the list-decoding Plotkin
point.

###### Contents

  1. 1 Introduction
  2. 2 Overview of our results and techniques
  3. 3 Preliminaries
  4. 4 Uniquely-decodable codes above the Plotkin point
    1. 4.1 Upper bound
    2. 4.2 Construction
  5. 5 List-decodable codes above the Plotkin point
    1. 5.1 List-decoding radius
    2. 5.2 List-decoding Plotkin point
    3. 5.3 Upper bound for constant-weight codes
    4. 5.4 Construction of constant-weight codes
    5. 5.5 Upper bound for approximate constant-weight codes
    6. 5.6 Upper bound for general codes
    7. 5.7 Construction of general codes
  6. 6 List-decodable codes below the Plotkin point
    1. 6.1 Upper bound on $(L-1)$-list-decoding capacity
    2. 6.2 Lower bound on $(L-1)$-list-decoding capacity
    3. 6.3 List-decoding capacity
  7. 7 Capacity of stochastic Z-channels
  8. 8 Open problems

##  1 Introduction

In coding theory, the Z-channel is used to model some asymmetric data storage
and transmission systems. In this binary-input binary-output channel, the
symbol $0$ is always transmitted correctly, whereas the transmitted symbol $1$
can be received as $0$.

In this paper, we consider the combinatorial setting where the encoder
transmits $n$ symbols, and the maximum number of errors inflicted by an
adversary is proportional to $n$. For a given word
$\boldsymbol{x}\in\\{0,1\\}^{n}$, we define the Z-ball centered at
$\boldsymbol{x}$ with radius $\tau n$ as a set of all possible words that can
be transmitted over the Z-channel with at most $\tau n$ errors such that
$\boldsymbol{x}$ is received. Given $\tau$ and $n$, the main goal for
$(L-1)$-list-decoding is to construct a code
$\mathcal{C}\subseteq\\{0,1\\}^{n}$ such that for any
$\boldsymbol{x}\in\\{0,1\\}^{n}$, the Z-ball centered at $\boldsymbol{x}$
contains at most $L-1$ codewords from $\mathcal{C}$. For $L=2$, we say that
$\mathcal{C}$ is a uniquely-decodable code tolerating a fraction $\tau$ of
(asymmetric) errors. For $L\geq 3$, $\mathcal{C}$ is referred to as an
$(L-1)$-list-decodable code for the Z-channel with list-decoding radius
$\tau$. Finding fundamental limits of error-correcting codes is one of the
major problems in coding theory. Uniquely-decodable codes for asymmetric
errors have been a subject for extensive studies in the numerous papers
[Bas65, Bor83, KF59, Var65, Klo81a, Klø81b, FLX03, BC93, ZF19]. Up to our best
knowledge, there are only two papers [LLP22, ZBJ20] in the literature that
discuss properties of list-decodable codes for the Z-channel.

First, we recall some results concerning the unique-decoding case. It is known
[Bas65, Bor83] that the rate of optimal codes tolerating a fraction $\tau$ of
asymmetric errors is asymptotically equal to the rate of optimal codes
correcting a fraction $\tau$ of symmetric errors 111Hereafter, errors are
called symmetric if any transmitted symbol from the alphabet $\\{0,1\\}$ can
be bit-flipped.. Hence there exist exponential-sized uniquely-decodable codes
for any fraction of errors $\tau<1/4$. The Plotkin bound [Plo60] says that the
size of a code capable of correcting a fraction $\tau=1/4+\varepsilon$ of
symmetric errors is bounded above by $1+1/(4\varepsilon)$. One might ask a
similar question for asymmetric errors. Specifically, can we bound the size of
a code $\mathcal{C}\subseteq\\{0,1\\}^{n}$ tolerating a fraction
$\tau=1/4+\varepsilon$ of asymmetric errors using a function that depends only
on $\varepsilon$? The paper [Bor83] claims that such a bound exists only for
$\varepsilon>1/12$. We disprove this statement and provide an order-optimal
uniquely-decodable code of size $\Theta(\varepsilon^{-3/2})$ as
$\varepsilon\to 0$. From the results of [Lev61, ABP18, Plo60], it follows that
the maximal size of a code tolerating a fraction $1/4+\varepsilon$ of
symmetric errors is $(4\varepsilon)^{-1}(1+o(1))$ as $\varepsilon\to 0$.

Much less is known about list-decodable codes for the Z-channel. By [LLP22,
ZBJ20], exponential-sized (or positive-rate) $(L-1)$-list-decodable codes with
list-decoding radius $\tau$ exist only for $\tau<\tau_{L}$, where
$\tau_{L}=w_{\max}-w_{\max}^{L}$ and $w_{\max}$ equals $L^{-\frac{1}{L-1}}$.
We call $\tau_{L}$ the _$(L-1)$ -list-decoding Plotkin point_. We extend the
above results from unique-decoding to list-decoding and obtain the same
characterization $\Theta_{L}(\varepsilon^{-3/2})$ for list-decodable codes
with arbitrary list size $L-1$ correcting $\tau_{L}+\varepsilon$ fraction of
asymmetric errors. The same question for symmetric errors was also studied
before. In a recent work [ABP18], the results in [Lev61, Plo60] for unique-
decoding were generalized to list-decoding with any _odd_ list size that is at
least one and the optimal code size was shown to be
$\Theta_{L}(\varepsilon^{-1})$. For _even_ list size, the problem seems
significantly more difficult and [ABP18] showed that the optimal code size is
$\Theta_{L}(\varepsilon^{-3/2})$ for list size three.

##  2 Overview of our results and techniques

This paper is a collection of results on combinatorial properties of codes for
the Z-channel with adversarial errors. The most technically challenging part
of our results has to do with obtaining the order-optimal size of codes that
correct a fraction of asymmetric errors _$\varepsilon$ -above_ the Plotkin
point. We start with the unique-decoding case and show in Sec. 4 that the
optimal size of codes which correct $1/4+\varepsilon$ fraction of asymmetric
errors is exactly $\Theta(\varepsilon^{-3/2})$. This follows from an upper
bound (Theorem 4 in Sec. 4.1) and a matching construction (Theorem 5 in Sec.
4.2). We then generalize these results to list-decoding for any list size at
least one. We show in Sec. 5.3-5.7 that the same bound
$\Theta_{L}(\varepsilon^{-3/2})$ is also optimal for list-decodable codes
which correct $\tau_{L}+\varepsilon$ fraction of asymmetric errors, where
$\tau_{L}$ is the list-decoding Plotkin point. See Sec. 5.1 and 5.2 for
definitions and properties of the list-decoding radius and list-decoding
Plotkin point.

We briefly explain below the ideas behind our results on “post-Plotkin” codes.

  1. 1.

(Upper bound for (approximate) constant-weight codes.) For _constant-weight_
codes (i.e., a code in which all codewords have the same Hamming weight), it
follows from a standard double-counting argument that the size of any code
$\varepsilon$-above the Plotkin point (i.e., $1/4$) is at most
$O_{L}(\varepsilon^{-1})$. For unique-decoding, this is known by [Plo60]; for
list-decoding, this follows from [LLP22] (see Theorem 6 in Sec. 5.3).
Furthermore, these results can be extended to _approximate constant-weight_
codes (i.e., a code in which all codewords have _approximately_ the same
Hamming weight). This can be done by either repeating the double-counting
argument with additional care of the deviation in weights or carefully
augmenting the codewords in such a way that the augmented codewords all have
the same weight. See Theorem 8 and 9 in Sec. 5.5 for details.

  2. 2.

(Upper bound for general codes.) For _general_ codes in which codewords can
have any weight between $0$ and $n$, given the above results, it is tempting
to partition $\\{0,1\\}^{n}$ into $\varepsilon^{-1}$ slices each of weight
between $nw$ and $n(w+\varepsilon)$ for some $w\in[0,1]$. The subcode in each
slice is therefore approximate constant-weight and has size at most
$O_{L}(\varepsilon^{-1})$. In total, we get an upper bound
$O_{L}(\varepsilon^{-2})$ on the size of the whole code. However, this bound
turns out to be suboptimal! We improve it by partitioning the space in a more
delicate way. The width of the slice is wider for weights far from the
critical weight $w_{\max}=L^{-\frac{1}{L-1}}$ and is thinner for weights close
to $w_{\max}$. In particular, we choose the width to be $\varepsilon^{1/2}$ on
average for
$w\in[0,w_{\max}-\Omega_{L}(\varepsilon^{1/2})]\cup[w_{\max}+\Omega_{L}(\varepsilon^{1/2}),1]$
and we choose it to be $\varepsilon$ for
$w\in[w_{\max}-O_{L}(\varepsilon^{1/2}),w_{\max}+O_{L}(\varepsilon^{1/2})]$,
while keeping the subcode in each slice having size $O_{L}(\varepsilon^{-1})$.
In total, there are at most
$O_{L}(1/\varepsilon^{1/2})=O_{L}(\varepsilon^{-1/2})$ slices for small and
large weights (i.e., weights far from $w_{\max}$) and at most
$O_{L}(\varepsilon^{1/2}/\varepsilon)=O_{L}(\varepsilon^{-1/2})$ slices for
moderate weights (i.e., weights close to $w_{\max}$). This gives an improved
upper bound
$O_{L}(\varepsilon^{-1/2}\varepsilon^{-1})=O_{L}(\varepsilon^{-3/2})$ on the
size of the whole code. The rigorous analyses for $L=2$ and $L>2$ are
presented in the proofs of Theorem 4 in Sec. 4.1 and Theorem 10 in Sec. 5.6,
respectively.

  3. 3.

(Construction of constant-weight codes.) In Sec. 5.4, we analyze a code formed
by rows of a matrix whose columns are all possible constant-weight words. In
Theorem 7, such a balanced code is shown to be $\varepsilon$-above the list-
decoding Plotkin point and have order-optimal size
$\Omega_{L}(\varepsilon^{-1})$. This code generalizes a construction proposed
in [ABP18] in the context of list-decodable codes for symmetric errors and has
a similar flavour as weak-flip codes discussed in [LMC18].

  4. 4.

(Construction of general codes.) We note that purely random post-Plotkin code
constructions do not have large size. However, we show how to use randomness
in order to build a code $\varepsilon$-above the Plotkin point of size
$\Omega_{L}(\varepsilon^{-3/2})$. The non-uniform partition used in the proof
of the converse bound suggests a matching construction. We reuse the constant-
weight construction in Theorem 7 in a consistent way with the non-uniform
partition. Specifically, we first build $\Theta_{L}(\varepsilon^{-1/2})$
constant-weight codes such that the $i$th code has size
$\Theta_{L}(\varepsilon^{-1})$ and contains codewords with relative weight
$w_{\max}-i\varepsilon$. The asymmetry property of the Z-channel comes to play
when we apply $\Theta_{L}(\varepsilon^{-1/2})$ independent random permutations
on the set of coordinates within each code and consider the union of all these
codes. For $L=2$, we carefully analyze the unique-decoding radius of the
resulting construction in the proof of Theorem 5 in Sec. 4.2. For $L>2$, we
investigate the list-decoding radius of our construction in the proof of
Theorem 12.

In Sec. 6.1 and 6.2, we study codes for the Z-channel _below_ the list-
decoding Plotkin point and obtain upper and lower bounds on the list-decoding
capacity. The upper bound in Theorem 15 follows the classical idea of Elias
and Bassalygo [Bas65]. Specifically, the space is multicovered by special
balls and the size of all balls is carefully adjusted such that each of them
contains a constant number of codewords only. The lower bound in Theorem 17
uses the standard random coding with expurgation technique. The question of
obtaining the exact list-decoding capacity for arbitrary list sizes is
difficult and our upper and lower bounds do not match. However, we manage to
derive the list-decoding capacity for asymptotically large list sizes in
Theorem 20 in Sec. 6.3.

Sec. 7 contains discussion on the capacity of Z-channels with _stochastic_
errors. This is a direct consequence of the seminal channel coding theorem by
Shannon [Sha48].

We end the paper with open questions in Sec. 8.

##  3 Preliminaries

The set $\\{i,i+1,\ldots,j\\}$ for some integers $i$ and $j$ with $i\leq j$
will be denoted as $[i,j]$. The set $[1,j]$ is shortly denoted as $[j]$. By
slight abuse of notation, we write $[w_{1},w_{2}]$ to denote the interval of
real numbers between $w_{1}$ and $w_{2}$. A vector of length $n$ is denoted by
bold lowercase letters, such as $\boldsymbol{x}$, and the $i$th entry of the
vector $\boldsymbol{x}$ is referred to as $x_{i}$. The all-zero vector, whose
length will be clear from the context, is written as $\boldsymbol{0}$. Define
the asymmetric function $\Delta(\boldsymbol{x},\boldsymbol{y})$ to be the
number of positions $i\in[n]$ such that $x_{i}=1$ and $y_{i}=0$. The Hamming
distance between $\boldsymbol{x},\boldsymbol{y}\in\\{0,1\\}^{n}$ is then
$d_{H}(\boldsymbol{x},\boldsymbol{y}):=\Delta(\boldsymbol{x},\boldsymbol{y})+\Delta(\boldsymbol{y},\boldsymbol{x})$.
The (Hamming) weight of $\boldsymbol{x}\in\\{0,1\\}^{n}$ is
$\textrm{wt}(\boldsymbol{x}):=d_{H}(\boldsymbol{x},\boldsymbol{0})$; the
relative weight is $\textrm{wt}(\boldsymbol{x})/n$. The _Z-distance_ between
$\boldsymbol{x},\boldsymbol{y}\in\\{0,1\\}^{n}$ is defined as
$d_{Z}(\boldsymbol{x},\boldsymbol{y})\coloneqq\max(\Delta(\boldsymbol{x},\boldsymbol{y}),\Delta(\boldsymbol{y},\boldsymbol{x}))$.
Note that the Hamming distance and the Z-distance are related by the following
identity:
$d_{Z}(\boldsymbol{x},\boldsymbol{y})=\frac{1}{2}(d_{H}(\boldsymbol{x},\boldsymbol{y})+|\textrm{wt}(\boldsymbol{x})-\textrm{wt}(\boldsymbol{y})|)$.
By this relation, we see that $d_{Z}(\cdot,\cdot)$ is indeed a distance, and
it equals $d_{H}(\cdot,\cdot)/2$ if the Hamming weights of $\boldsymbol{x}$
and $\boldsymbol{y}$ are the same. Define the Z-ball and the H-ball centered
at $\boldsymbol{x}\in\\{0,1\\}^{n}$ with radius $t$ as follows

$\displaystyle B^{\text{Z}}_{t}(\boldsymbol{x})$
$\displaystyle\coloneqq\\{\boldsymbol{y}\in\\{0,1\\}^{n}:\
\Delta(\boldsymbol{x},\boldsymbol{y})=0,\
\Delta(\boldsymbol{y},\boldsymbol{x})\leq t\\},$ $\displaystyle
B^{\text{H}}_{t}(\boldsymbol{x})$
$\displaystyle\coloneqq\\{\boldsymbol{y}\in\\{0,1\\}^{n}:\
d_{H}(\boldsymbol{x},\boldsymbol{y})\leq t\\}.$

Similarly, define the _Z-sphere_ and the _H-sphere_ centered at
$\boldsymbol{x}\in\\{0,1\\}^{n}$ with radius $t$ as follows

$\displaystyle S^{\mathrm{Z}}_{t}(\boldsymbol{x})$
$\displaystyle\coloneqq\\{\boldsymbol{y}\in\\{0,1\\}^{n}:\
\Delta(\boldsymbol{x},\boldsymbol{y})=0,\
\Delta(\boldsymbol{y},\boldsymbol{x})=t\\},$ $\displaystyle
S^{\mathrm{H}}_{t}(\boldsymbol{x})$
$\displaystyle\coloneqq\\{\boldsymbol{y}\in\\{0,1\\}^{n}:\
d_{H}(\boldsymbol{x},\boldsymbol{y})=t\\}.$

A code $\mathcal{C}\subseteq\\{0,1\\}^{n}$ is an arbitrary subset of binary
vector of the same length $n$. The size of a code $\mathcal{C}$ is denoted as
$|\mathcal{C}|$. The _rate_ of $\mathcal{C}$ is defined as
$R(\mathcal{C})\coloneqq\frac{1}{n}\log|\mathcal{C}|$. A code
$\mathcal{C}\subseteq\\{0,1\\}^{n}$ is called $w$-constant-weight if the
weight of all codewords $\boldsymbol{x}\in\mathcal{C}$ is
$\textrm{wt}(\boldsymbol{x})=nw$.

######  Definition 1 (Uniquely-decodable code).

We say that a code $\mathcal{C}\subseteq\\{0,1\\}^{n}$ corrects $t$ asymmetric
(symmetric) errors if for any $\boldsymbol{x}\in\\{0,1\\}^{n}$ the respective
Z-ball (H-ball) centered at $\boldsymbol{x}$ with radius $t$ contains at most
one codeword from $\mathcal{C}$, i.e., it holds that
$|B^{\text{Z}}_{t}(\boldsymbol{x})\cap\mathcal{C}|\leq 1$
($|B^{\text{H}}_{t}(\boldsymbol{x})\cap\mathcal{C}|\leq 1$).

Note that a code $\mathcal{C}$ corrects $t$ asymmetric errors if and only if
for any two distinct codewords $\boldsymbol{x},\boldsymbol{y}\in\mathcal{C}$,
it holds that $d_{Z}(\boldsymbol{x},\boldsymbol{y})>t$. A code
$\mathcal{C}\subseteq\\{0,1\\}^{n}$ is said to correct a fraction $\tau$ of
asymmetric (symmetric) errors if it corrects $t$ asymmetric (symmetric) errors
for $t=\lceil\tau n\rceil$.

In the following statement, we first recall a (trivial) observation from
[Var65].

######  Lemma 1.

Let a code $\mathcal{C}\subseteq\\{0,1\\}^{n}$ be $w$-constant-weight. Then
$\mathcal{C}$ corrects $t$ asymmetric errors if and only if it corrects $t$
symmetric errors which is in turn satisfied if and only if the minimum
distance of $\mathcal{C}$ is larger than $2t$.

We state two classical coding theory results, which were proved in [Plo60] and
[Bas65] respectively.

######  Lemma 2.

Let $\mathcal{C}\subseteq\\{0,1\\}^{n}$ be a code that corrects $t$, $t>n/4$,
symmetric errors. Then its size is bounded above as follows

$|\mathcal{C}|\leq 2\left\lfloor\frac{2t+2}{4t+3-n}\right\rfloor.$

######  Lemma 3.

Let a code $\mathcal{C}\subseteq\\{0,1\\}^{n}$ be $w$-constant-weight and
correct $t$ symmetric errors. If the inequality $t+1\leq
w\leq(n-\sqrt{n^{2}-4tn})/2$ is fulfilled, then the size of $\mathcal{C}$ is
bounded above as follows

$|\mathcal{C}|\leq\left\lfloor\frac{tn}{w^{2}-(w-t)n}\right\rfloor.$

We introduce below the concept of list-decodable codes.

######  Definition 2 (List-decodable code).

Let $L$ be a positive integer at least $2$. A code
$\mathcal{C}\subseteq\\{0,1\\}^{n}$ is said to be $(L-1)$-list-decodable with
list-decoding radius $\tau$ if for any $\boldsymbol{x}\in\\{0,1\\}^{n}$ the
respective Z-ball (H-ball) centered at $\boldsymbol{x}$ with radius
$t:=\lceil\tau n\rceil$ contains at most $L-1$ codewords from $\mathcal{C}$,
i.e., it holds that $|B^{\text{Z}}_{t}(\boldsymbol{x})\cap\mathcal{C}|\leq
L-1$ ($|B^{\text{H}}_{t}(\boldsymbol{x})\cap\mathcal{C}|\leq L-1$).

At last, we need the definition of the binary entropy function
$H(x)\coloneqq-x\log x-(1-x)\log(1-x)$ for any $x\in[0,1]$.

##  4 Uniquely-decodable codes above the Plotkin point

In this section, we obtain upper and lower bounds on the size of an optimal
code capable of correcting a fraction $\tau=\frac{1}{4}+\varepsilon$ of
asymmetric errors.

###  4.1 Upper bound

In the following statement, we derive an upper bound on the size of a code
capable of correcting a large fraction of asymmetric errors. The idea of the
proof is to partition a code into $O(\varepsilon^{-1/2})$ subcodes with
approximate constant weight. By lengthening codewords within each subcode, we
obtain constant-weight codes correcting a large fraction of symmetric errors
and show that their size can be bounded by $O(\varepsilon^{-1})$.

######  Theorem 4.

Let $n>36$ be an integer and $\mathcal{C}\subseteq\\{0,1\\}^{n}$ be a code
correcting a fraction $\tau=\frac{1}{4}+\varepsilon$ of asymmetric errors for
some real number $0<\varepsilon<1/12-3/n$. Then the size of the code can be
bounded as follows

$|\mathcal{C}|\leq\frac{1+7/n+2\sqrt{\varepsilon}+4\varepsilon+16\sqrt{\varepsilon}/n}{\varepsilon^{3/2}}+10.$

###### Proof.

Without loss of generality, we assume that the number of codewords of weight
at most $n/2$ is at least as the number of codewords of weight at least $n/2$.
Otherwise, we can consider the code that is obtained by replacing $0$ by $1$
and $1$ by $0$ in all codewords of the original code because the Z-distance
$d_{Z}(\boldsymbol{x},\boldsymbol{y})=\max(\Delta(\boldsymbol{x},\boldsymbol{y}),\Delta(\boldsymbol{y},\boldsymbol{x}))$
is not changed after such swapping. For a non-negative integer $i$, define
$\rho_{i}:=\frac{i}{2i+1}$. Define the subcode

$\mathcal{A}_{i}:=\\{\boldsymbol{x}\in\mathcal{C}:\
\lfloor\rho_{i}n\rfloor<\textrm{wt}(\boldsymbol{x})\leq\lfloor\rho_{i+1}n\rfloor\\}.$

Extend all codewords of $\mathcal{A}_{i}$ by adding
$\lfloor\rho_{i+1}n\rfloor-\lfloor\rho_{i}n\rfloor-1$ extra positions such
that all codewords have weight $\lfloor\rho_{i+1}n\rfloor$. Note that this can
be done in different ways. From Lemma 1 it follows that the obtained code
$\mathcal{A}_{i}^{\prime}\subseteq\\{0,1\\}^{n+\lfloor\rho_{i+1}n\rfloor-\lfloor\rho_{i}n\rfloor-1}$
contains codewords of weight $\lfloor\rho_{i+1}n\rfloor$ and corrects
$\lceil(1/4+\varepsilon)n\rceil$ symmetric errors. For $\varepsilon<1/12-3/n$,
the condition of Lemma 3 is fulfilled. Thus, we obtain that

$\displaystyle|\mathcal{A}_{i}|=|\mathcal{A}_{i}^{\prime}|$
$\displaystyle\leq\frac{\lceil(1/4+\varepsilon)n\rceil(n+\lfloor\rho_{i+1}n\rfloor-\lfloor\rho_{i}n\rfloor-1)}{\lfloor\rho_{i+1}n\rfloor^{2}-(\lfloor\rho_{i+1}n\rfloor-\lceil(1/4+\varepsilon)n\rceil)(n+\lfloor\rho_{i+1}n\rfloor-\lfloor\rho_{i}n\rfloor-1)}$
$\displaystyle\leq\frac{(1/4+\varepsilon+1/n)(1+\rho_{i+1}-\rho_{i})}{\rho_{i+1}^{2}-(\rho_{i+1}-1/4-\varepsilon)(1+\rho_{i+1}-\rho_{i})}.$

In the last inequality, we make use of the fact that $w^{2}-(w-t)n$ is a
monotonically decreasing function in $w$ for $w\leq(n-\sqrt{n^{2}-4tn})/2$.
Observe that $\rho_{i+1}^{2}-(\rho_{i+1}-1/4)(1+\rho_{i+1}-\rho_{i})=0$ since
$\rho_{i}=\frac{i}{2i+1}$. Thus, $|\mathcal{A}_{i}^{\prime}|\leq
1+(1/4+1/n)\varepsilon^{-1}$.

Let $i_{0}:=\lfloor 1/(2\sqrt{\varepsilon})\rfloor$ and, thus,
$\rho_{i_{0}}\geq\frac{1-2\sqrt{\varepsilon}}{2+2\sqrt{\varepsilon}}$. For a
non-negative integer $j$, consider the subcode

$\mathcal{B}_{j}:=\\{\boldsymbol{x}\in\mathcal{C}:\
\lfloor\rho_{i_{0}}n\rfloor+j\lceil 2\varepsilon
n\rceil<\textrm{wt}(\boldsymbol{x})\leq\lfloor\rho_{i_{0}}n\rfloor+(j+1)\lceil
2\varepsilon n\rceil\\}.$

We extend all codewords of $\mathcal{B}_{j}$ by adding $\lceil 2\varepsilon
n\rceil$ extra positions such that all obtained codewords have the same
weight. We get the code $\mathcal{B}_{j}^{\prime}\subseteq\\{0,1\\}^{n+\lceil
2\varepsilon n\rceil}$ which contains codewords of weight
$\lfloor\rho_{i_{0}}n\rfloor+(j+1)\lceil 2\varepsilon n\rceil$ and corrects
$\lceil(1/4+\varepsilon)n\rceil$ symmetric errors. By Lemma 2, we estimate

$|\mathcal{B}_{j}|=|\mathcal{B}_{j}^{\prime}|\leq\frac{n+4\varepsilon
n+8}{n+4\varepsilon n+3-n-2\varepsilon
n-1}\leq(1/2+4/n+2\varepsilon)\varepsilon^{-1}.$

Each codeword of $\mathcal{C}$, having weight within the interval $[1,n/2]$,
is included in $\mathcal{A}_{i}$ with some $i\in[0,i_{0}-1]$ or
$\mathcal{B}_{j}$ with some $j\in[0,j_{0}-1]$ if $j_{0}:=\lfloor
3/(4\sqrt{\varepsilon})+2\rfloor$. Indeed,

$\frac{n/2-\lfloor\rho_{i_{0}}n\rfloor}{\lceil 2\varepsilon
n\rceil}\leq\frac{n/2-\frac{1-2\sqrt{\varepsilon}}{2+2\sqrt{\varepsilon}}n}{2\varepsilon
n}+1\leq\left\lfloor\frac{3}{4\sqrt{\varepsilon}}+2\right\rfloor.$

Since the number of codewords with weight from the interval $[1,n/2]$ is not
less than the number of codewords of weight from the interval $[n/2,n-1]$, it
holds

$\displaystyle|\mathcal{C}|$ $\displaystyle\leq
2\left(\sum_{i=0}^{i_{0}-1}|\mathcal{A}_{i}|+\sum_{j=0}^{j_{0}-1}|\mathcal{B}_{j}|\right)+2$
$\displaystyle\leq\frac{1}{\varepsilon^{3/2}}(\varepsilon+1/4+1/n+3/4+6/n+3\varepsilon+2\sqrt{\varepsilon}+16\sqrt{\varepsilon}/n+8\varepsilon^{3/2})+2$
$\displaystyle=\frac{1+7/n+4\varepsilon+2\sqrt{\varepsilon}+16\sqrt{\varepsilon}/n}{\varepsilon^{3/2}}+10.\qed$

###  4.2 Construction

In the following statement, we prove that there exists a code of size
$\Omega(\varepsilon^{-3/2})$ and length $\exp(\Theta(\varepsilon^{-3/2}))$
capable of correcting a fraction $1/4+\varepsilon$ of asymmetric errors. We
use the intuition from the proof of Theorem 4. First, we build
$O(\varepsilon^{-1/2})$ codes such that the $j$th code is a uniquely-decodable
code containing codewords with the relative weight $\frac{1}{2}-j\varepsilon$.
We borrow an idea for such code with $j=0$ from [ABP18], where the authors
constructed list-decodable codes for symmetric errors. By performing simple
repetition, we construct longer codes of the same size while the error-
correction capability of all those codes remains unchanged. Applying a random
permutation on the set of coordinates within each code, we guarantee that two
codewords from different codes have a large asymmetric distance with
overwhelming probability.

######  Theorem 5.

There exists a code of length $\exp(O(\varepsilon^{-3/2}))$, capable of
correcting a fraction $\tau=\frac{1}{4}+\varepsilon$ of asymmetric errors.
Furthermore, its size is at least
$\frac{3\sqrt{3}}{128}\varepsilon^{-3/2}(1+o(1))$ as $\varepsilon\to 0$.

###### Proof.

Consider the positive integer $m:=\lfloor 3/(32\varepsilon)\rfloor$ and define
the real number $c:=2^{-3/2}$. For every $j\in\\{-\lfloor
c\sqrt{m}\rfloor,\ldots,\lfloor c\sqrt{m}\rfloor\\}$, denote
$n_{j}:=\binom{2m}{m-j}$. Consider a binary matrix $A_{j}$ of size $2m\times
n_{j}$, whose columns are all possible binary vectors of length $2m$ and
weight $m-j$. For two distinct rows $\boldsymbol{x}$ and $\boldsymbol{y}$ of
matrix $A_{j}$, we compute the number of positions in which the rows are
different:

$\Delta(\boldsymbol{x},\boldsymbol{y})=\Delta(\boldsymbol{y},\boldsymbol{x})=\binom{2m-2}{m-j-1}.$

This means that a code, whose codewords are rows of $A_{j}$, corrects a
fraction $\tau_{j}$ of asymmetric errors, where

$\tau_{j}:=\frac{\binom{2m-2}{m-j-1}-1}{\binom{2m}{m-j}}=\frac{(m-j)(m+j)}{2m(2m-1)}-\frac{1}{\binom{2m}{m-j}}=\frac{1}{4}+\frac{m/2-j^{2}}{4m^{2}-2m}-\frac{1}{\binom{2m}{m-j}}.$

Let us show that for small enough $\varepsilon$, it holds that
$\tau_{j}\geq\frac{1}{4}+\varepsilon$. We have

$\displaystyle\frac{m/2-j^{2}}{4m^{2}-2m}-\frac{1}{\binom{2m}{m-j}}$
$\displaystyle\geq\frac{m/2-c^{2}m}{4m^{2}-2m}-\frac{1}{\binom{2m}{m-\lfloor
c\sqrt{m}\rfloor}}$
$\displaystyle=\frac{3}{32m-16}-\frac{1}{\binom{2m}{m-\lfloor
c\sqrt{m}\rfloor}}$
$\displaystyle=\frac{3}{32m}+\frac{3}{2m(32m-16)}-\frac{1}{\binom{2m}{m-\lfloor
c\sqrt{m}\rfloor}}$ $\displaystyle\geq\varepsilon.$

To show the last inequality, we used that $m=\lfloor
3/(32\varepsilon)\rfloor$, $c=2^{-3/2}$ and the fact that for sufficiently
large $m$ (small $\varepsilon$), it holds

$\frac{3}{64m^{2}}>\frac{1}{\binom{2m}{m-\lfloor c\sqrt{m}\rfloor}}.$

For a positive integer $z$, consider a matrix $A_{j}^{(z)}$ of size $2m\times
zn_{j}$ which is composed of $z$ copies of the matrix $A_{j}$. We write copies
of $A_{j}$ to the right, i.e., $A_{j}^{(z)}=(A_{j},A_{j},\ldots,A_{j})$. By
$\tilde{A}_{j}^{(z)}$ denote a matrix obtained from $A_{j}^{(z)}$ by a random
permutation of its columns. This permutation is taken uniformly at random from
the set of all permutations. Note that a code whose codewords are rows of
$\tilde{A}_{j}^{(z)}$ corrects the same fraction of errors as the original
code obtained from $A_{j}$. Define integers

$z_{j}:=\prod_{\begin{subarray}{c}i=-\lfloor c\sqrt{m}\rfloor,\\\ i\neq
j\end{subarray}}^{\lfloor c\sqrt{m}\rfloor}\binom{2m}{m-i},\quad
N:=\prod_{\begin{subarray}{c}i=-\lfloor
c\sqrt{m}\rfloor\end{subarray}}^{\lfloor
c\sqrt{m}\rfloor}\binom{2m}{m-i},\quad M:=2m(2\lfloor c\sqrt{m}\rfloor+1).$

Consider a matrix $A$ of size $M\times N$ containing $\tilde{A}_{j}^{(z_{j})}$
as a submatrix for all $j\in\\{-\lfloor c\sqrt{m}\rfloor,\ldots,\lfloor
c\sqrt{m}\rfloor\\}$. We assume that matrices $\tilde{A}_{j}^{(z_{j})}$ are
written one below the other using the ascending order of parameter $j$. For
$\varepsilon\to 0$, we estimate the number of rows $M$ and the number of
columns $N$ in $A$ as follows

$M=\frac{3\sqrt{3}}{128\varepsilon\sqrt{\varepsilon}}(1+o(1)),\quad
N=\exp(\Theta(\varepsilon^{-3/2})).$

Let us show that for two distinct rows $\tilde{\boldsymbol{x}}$ and
$\tilde{\boldsymbol{y}}$ in $A$, the value
$d_{Z}(\tilde{\boldsymbol{x}},\tilde{\boldsymbol{y}})$ is large enough with
overwhelming probability. The latter ensures that the code obtained from $A$
can correct the required fraction of asymmetric errors. More formally, let
$\tilde{\boldsymbol{x}}$ and $\tilde{\boldsymbol{y}}$ be rows from
$\tilde{A}_{j}^{(z_{j})}$ and $\tilde{A}_{i}^{(z_{i})}$, where $j<i$. Clearly,
$\textrm{wt}(\tilde{\boldsymbol{x}})=\frac{m-j}{2m}N>\frac{m-i}{2m}N=\textrm{wt}(\tilde{\boldsymbol{y}})$
and
$d_{Z}(\tilde{\boldsymbol{x}},\tilde{\boldsymbol{y}})=\Delta(\tilde{\boldsymbol{x}},\tilde{\boldsymbol{y}})$.
The probability distribution for the random variable
$\Delta(\tilde{\boldsymbol{x}},\tilde{\boldsymbol{y}})$ is given by

$\Pr\\{\Delta(\tilde{\boldsymbol{x}},\tilde{\boldsymbol{y}})=t\\}=\begin{cases}\frac{\binom{\textrm{wt}(\tilde{\boldsymbol{x}})}{t}\binom{N-\textrm{wt}(\tilde{\boldsymbol{x}})}{\textrm{wt}(\tilde{\boldsymbol{y}})-\textrm{wt}(\tilde{\boldsymbol{x}})+t}}{\binom{N}{\textrm{wt}(\tilde{\boldsymbol{y}})}},\quad&\text{for
}t\in\left\\{\textrm{wt}(\tilde{\boldsymbol{x}})-\textrm{wt}(\tilde{\boldsymbol{y}}),\ldots,\min\left(\textrm{wt}(\tilde{\boldsymbol{x}}),N-\textrm{wt}(\tilde{\boldsymbol{y}})\right)\right\\},\\\
0,\quad&\text{otherwise.}\end{cases}$

We estimate the probability of the event that
$\Delta(\tilde{\boldsymbol{x}},\tilde{\boldsymbol{y}})$ is small as follows

$\Pr\left\\{\Delta(\tilde{\boldsymbol{x}},\tilde{\boldsymbol{y}})\leq
N\left(\frac{1}{4}+\varepsilon\right)\right\\}\leq
N\max\limits_{t\in[0,\lfloor
N(\frac{1}{4}+\varepsilon)\rfloor]}\Pr\left\\{\Delta(\tilde{\boldsymbol{x}},\tilde{\boldsymbol{y}})=t\right\\}.$
(1)

Let an integer $t$ be equal to $\alpha N$ for some real number
$\alpha\in\left[\frac{i-j}{2m},\ \min(\frac{m-j}{2m},\frac{m+i}{2m})\right]$.
Note that $N$ and $m$ are functions of $\varepsilon$. Define the function

$g_{i,j}(\alpha,\varepsilon):=\frac{1}{N}\log\left(\Pr\left\\{\Delta(\tilde{\boldsymbol{x}},\tilde{\boldsymbol{y}})=t\right\\}\right).$

For arbitrary integers $u$ and $v$ so that $u>v\geq 1$, the binomial
coefficient $\binom{u}{v}$ satisfies

$\sqrt{\frac{u}{8v(u-v)}}2^{uH(v/u)}\leq\binom{u}{v}\leq 2^{uH(v/u)}.$

Thus, for $\alpha\in\left(\frac{i-j}{2m},\
\min(\frac{m-j}{2m},\frac{m+i}{2m})\right)$, it holds that

$\displaystyle g_{i,j}(\alpha,\varepsilon)$
$\displaystyle\leq\frac{m-j}{2m}H\left(\frac{2\alpha
m}{m-j}\right)+\frac{m+j}{2m}H\left(\frac{j-i+2\alpha
m}{m+j}\right)-H\left(\frac{m-i}{2m}\right)-\frac{\log\left(\frac{m^{2}}{2(m-i)(m+i)N}\right)}{2N}$
$\displaystyle\leq r_{i,j}(\alpha,\varepsilon)+\delta(\varepsilon),$

where functions $r_{i,j}(\alpha,\varepsilon)$ and $\delta_{i,j}(\varepsilon)$
are defined as follows

$r_{i,j}(\alpha,\varepsilon):=\frac{m-j}{2m}H\left(\frac{2\alpha
m}{m-j}\right)+\frac{m+j}{2m}H\left(\frac{j-i+2\alpha
m}{m+j}\right)-H\left(\frac{m-i}{2m}\right),\quad\delta(\varepsilon):=\frac{\log(2N)}{2N}.$

Using the relation $\frac{\partial H(x)}{\partial x}=\log(\frac{1-x}{x})$, we
compute the derivative of $r_{i,j}(\alpha,\varepsilon)$:

$q_{i,j}(\alpha,\varepsilon):=\frac{\partial
r_{i,j}(\alpha,\varepsilon)}{\partial\alpha}=\log\left(\frac{m-j-2\alpha
m}{2\alpha m}\right)+\log\left(\frac{m+i-2\alpha m}{j-i+2\alpha m}\right).$

Let $\alpha_{i,j}=\alpha_{i,j}(\varepsilon):=\frac{(m-j)(m+i)}{4m^{2}}$.
Clearly, the function $q_{i,j}(\alpha,\varepsilon)$ is positive for
$\alpha<\alpha_{i,j}$, and the function $r_{i,j}(\alpha,\varepsilon)\leq 0$
for all required $\alpha$. Furthermore, $r_{i,j}(\alpha_{i,j},\varepsilon)=0$.
Since $m=\lfloor 3/(32\varepsilon)\rfloor$ and $-\lfloor c\sqrt{m}\rfloor\leq
j<i\leq\lfloor c\sqrt{m}\rfloor$, we obtain that
$\alpha_{i,j}(\varepsilon)-\left(\frac{1}{4}+\varepsilon\right)>0$ and

$\alpha_{i,j}(\varepsilon)-\left(\frac{1}{4}+\varepsilon\right)=\frac{(m-j)(m+i)}{4m^{2}}-\left(\frac{1}{4}+\varepsilon\right)=\frac{(i-j)m-ij-4\varepsilon
m^{2}}{4m^{2}}.$

Since the derivative of $r_{i,j}(\alpha,\varepsilon)$ is positive for
$\alpha\leq 1/4+\varepsilon$, we get that

$\sup_{\frac{i-j}{2m}<\alpha\leq\frac{1}{4}+\varepsilon}g_{i,j}(\alpha,\varepsilon)\leq
r_{i,j}(1/4+\varepsilon,\varepsilon)+\delta(\varepsilon).$ (2)

Observe that we have the partial sum of the Taylor series with the remainder
in Lagrange’s form

$r_{i,j}(\alpha_{i,j},\varepsilon)=r_{i,j}(1/4+\varepsilon,\varepsilon)+(\alpha_{i,j}-1/4-\varepsilon)q_{i,j}(1/4+\varepsilon,\varepsilon)+(\alpha_{i,j}-1/4-\varepsilon)^{2}\frac{\sigma_{i,j}(\theta,\varepsilon)}{2},$
(3)

where $\sigma_{i,j}(\alpha,\varepsilon):=\frac{\partial
q_{i,j}(\alpha,\varepsilon)}{\partial\alpha}$ and $\theta$ is some point
within the interval $[1/4+\varepsilon,\alpha_{i,j}]$. Let us show that the
function $\sigma_{i,j}(\alpha,\varepsilon)$ in the interval
$(1/4+\varepsilon,\alpha_{i,j})$ can be bounded below

$\frac{\sigma_{i,j}(\alpha,\varepsilon)}{\log e}=\frac{j-m}{\alpha(m-j-2\alpha
m)}-\frac{2m(m+j)}{(j-i+2\alpha m)(m+i-2\alpha m)}.$

For $\varepsilon\to 0$, $m=\Theta(\varepsilon^{-1})$. Thus,
$\sigma_{i,j}(\theta,\varepsilon)=-16\log e(1+o(1))$ as $\varepsilon\to 0$.
Indeed, it holds that

$\lim_{\varepsilon\to
0}\sup_{1/4+\varepsilon<\alpha<\alpha_{i,j}}\sigma_{i,j}(\alpha,\varepsilon)=-16\log
e,\quad\lim_{\varepsilon\to
0}\inf_{1/4+\varepsilon<\alpha<\alpha_{i,j}}\sigma_{i,j}(\alpha,\varepsilon)=-16\log
e.$

Now we estimate $q_{i,j}(1/4+\varepsilon,\varepsilon)$ as $\varepsilon\to 0$

$\displaystyle q_{i,j}(1/4+\varepsilon,\varepsilon)$
$\displaystyle=\log\left(1+\frac{mi-4\varepsilon m^{2}-jm-
ji}{(m/2+2\varepsilon m)(m/2+j-i+2\varepsilon m)}\right)$ $\displaystyle=4\log
e\frac{m(i-j)-4\varepsilon m^{2}-ji}{m^{2}}(1+o(1)).$

Recall that $r_{i,j}(\alpha_{i,j},\varepsilon)=0$. Combining the above bounds
with (3), we get

$\displaystyle r_{i,j}(1/4+\varepsilon,\varepsilon)$
$\displaystyle=-\left(\alpha_{i,j}-\frac{1}{4}-\varepsilon\right)\left(\frac{m(i-j)-4\varepsilon
m^{2}-ji}{m^{2}}(4\log e-2\log e)\right)(1+o(1))$
$\displaystyle\leq-\lambda\varepsilon^{2}+o(\varepsilon^{2})$

for some constant $\lambda>0$ and $\varepsilon\to 0$. Using this inequality,
the bound $\delta(\varepsilon)=o(\varepsilon^{2})$ and the inequality (2), we
estimate the LHS of (1) as follows

$\Pr\left\\{\Delta(\tilde{\boldsymbol{x}},\tilde{\boldsymbol{y}})\leq
N\left(\frac{1}{4}+\varepsilon\right)\right\\}\leq
N2^{-\lambda\varepsilon^{2}N+o(\varepsilon^{2}N)}=o(1),$

since $\varepsilon^{2}N=\exp(\Omega(\varepsilon^{-3/2}))$. The probability of
the event that
$\max\left(\Delta(\tilde{\boldsymbol{x}},\tilde{\boldsymbol{y}}),\Delta(\tilde{\boldsymbol{y}},\tilde{\boldsymbol{x}})\right)\leq
N(\frac{1}{4}+\varepsilon)$ for some distinct rows
$\tilde{\boldsymbol{x}},\tilde{\boldsymbol{y}}$ in matrix $A$ can be bounded
above as follows

$\binom{M}{2}\max_{\begin{subarray}{c}\tilde{\boldsymbol{x}},\tilde{\boldsymbol{y}}\in
A\\\
\tilde{\boldsymbol{x}}\neq\tilde{\boldsymbol{y}}\end{subarray}}\Pr\left\\{\max\left(\Delta(\tilde{\boldsymbol{x}},\tilde{\boldsymbol{y}}),\Delta(\tilde{\boldsymbol{y}},\tilde{\boldsymbol{x}})\right)\leq
N\left(\frac{1}{4}+\varepsilon\right)\right\\}=o(1).$

It follows that for $\varepsilon\to 0$, with overwhelming probability, the
code composed of rows of matrix $A$ can correct a fraction
$\tau=\frac{1}{4}+\varepsilon$ of asymmetric errors. ∎

##  5 List-decodable codes above the Plotkin point

###  5.1 List-decoding radius

Fix $L\in\mathbb{Z}_{\geq 2}$. For an $L$-list
$\mathcal{L}\coloneqq\\{\boldsymbol{x}_{1},\cdots,\boldsymbol{x}_{L}\\}\in\binom{\\{0,1\\}^{n}}{L}$
of distinct vectors, define its _Chebyshev radius_ w.r.t. Z-distance as

$\displaystyle\mathrm{rad}(\mathcal{L})$
$\displaystyle\coloneqq\min_{\boldsymbol{y}\in\\{0,1\\}^{n}}\max_{i\in[L]}d_{Z}(\boldsymbol{x}_{i},\boldsymbol{y}).$
(4)

Let $\mathcal{C}\subseteq\\{0,1\\}^{n}$ be an arbitrary code for the
Z-channel. The _$(L-1)$ -list-decoding radius_ $\tau_{L}(\mathcal{C})$ of
$\mathcal{C}$ is defined as

$\displaystyle\tau_{L}(\mathcal{C})$
$\displaystyle\coloneqq\min_{\mathcal{L}\in\binom{\mathcal{C}}{L}}\mathrm{rad}(\mathcal{L}).$

It is easy to see that the minimum in the definition of
$\mathrm{rad}(\mathcal{L})$ can be achieved by the following vector
$\boldsymbol{y}_{\mathcal{L}}=(y_{1},\cdots,y_{n})\in\\{0,1\\}^{n}$:

$\displaystyle y_{i}$
$\displaystyle=\begin{cases}1,&x_{1,i}=\cdots=x_{L,i}=1\\\
0,&\mathrm{otherwise}\end{cases},$ (5)

for each $i\in[n]$. Here $x_{j,i}$ denotes the $i$th entry of
$\boldsymbol{x}_{j}$. Observe that since
$\mathrm{supp}(\boldsymbol{y}_{\mathcal{L}})\subseteq\mathrm{supp}(\boldsymbol{x}_{i})$
for all $i\in[L]$, we have
$d_{Z}(\boldsymbol{x}_{i},\boldsymbol{y}_{\mathcal{L}})=|\mathrm{supp}(\boldsymbol{x}_{i})|-|\mathrm{supp}(\boldsymbol{y}_{\mathcal{L}})|=\textrm{wt}(\boldsymbol{x}_{i})-\textrm{wt}(\boldsymbol{y}_{\mathcal{L}})$.
Therefore

$\displaystyle\mathrm{rad}(\mathcal{L})\coloneqq$
$\displaystyle\max_{i\in[L]}\textrm{wt}(\boldsymbol{x}_{i})-\textrm{wt}(\boldsymbol{y}_{\mathcal{L}})=\max_{i\in[L]}\textrm{wt}(\boldsymbol{x}_{i})-\left|\bigcap_{i\in[L]}\mathrm{supp}(\boldsymbol{x}_{i})\right|.$

Furthermore, if all $\boldsymbol{x}_{i}$’s have the same weight $w$, then

$\displaystyle\mathrm{rad}(\mathcal{L})$
$\displaystyle=nw-\left|\bigcap_{i\in[L]}\mathrm{supp}(\boldsymbol{x}_{i})\right|.$
(6)

For a constant-weight code $\mathcal{C}$ of weight $w$, we have

$\displaystyle\tau_{L}(\mathcal{C})=nw-\max_{\mathcal{L}\in\binom{\mathcal{C}}{L}}\left|\bigcap_{\boldsymbol{x}\in\mathcal{L}}\mathrm{supp}(\boldsymbol{x})\right|.$

It is not hard to see that $\mathcal{C}\subseteq\\{0,1\\}^{n}$ is
$(L-1)$-list-decodable with list-decoding radius $\tau$ if and only if
$\tau_{L}(\mathcal{C})>n\tau$. The _$(L-1)$ -list-decoding capacity_ of a
Z-channel with input weight $w$ and fraction of asymmetric errors $\tau$ is
defined as

$\displaystyle C_{L-1}(w,\tau)$
$\displaystyle\coloneqq\limsup_{n\to\infty}\max_{\begin{subarray}{c}\mathcal{C}_{n}\subset
B^{\mathrm{Z}}_{nw}(\boldsymbol{0})\\\
\tau_{L}(\mathcal{C}_{n})>n\tau\end{subarray}}R(\mathcal{C}_{n}).$

The _$(L-1)$ -list-decoding radius_ of a Z-channel with input weight $w$ and
rate $R$ is defined as

$\displaystyle\tau_{L}(w,R)$
$\displaystyle\coloneqq\limsup_{n\to\infty}\max_{\begin{subarray}{c}\mathcal{C}_{n}\subset
B^{\mathrm{Z}}_{nw}(\boldsymbol{0})\\\ R(\mathcal{C}_{n})\geq
R\end{subarray}}\tau_{L}(\mathcal{C}_{n}).$

###  5.2 List-decoding Plotkin point

Let $\tau_{L}(w)\coloneqq w-w^{L}$ and $\tau_{L}\coloneqq\max\limits_{0\leq
w\leq 1}\tau_{L}(w)$. With slight abuse of notation, we write $w_{\max}$ to
denote the argument of $w$ that attains the maximum of $\tau_{L}(w)$. It is
not hard to check that $\tau_{L}(w)$ is concave in $w$ and the maximizer
$w_{\max}$ equals $L^{-\frac{1}{L-1}}$. Therefore
$\tau_{L}=L^{-\frac{1}{L-1}}-L^{-\frac{L}{L-1}}=(1-L^{-1})L^{-\frac{1}{L-1}}=(L-1)L^{-\frac{L}{L-1}}$.

Note that $w_{\max}$ is increasing in $L$. The minimum value of $w_{\max}$
over all $L\in\mathbb{Z}_{\geq 2}$ is $1/2$ when $L=2$ and
$w_{\max}\xrightarrow{L\to\infty}1$.

Note that $\tau_{L}$ is increasing $L$ and attains its minimum value $1/4$ at
$L=2$. Furthermore, $\tau_{L}\xrightarrow{L\to\infty}1$.

###  5.3 Upper bound for constant-weight codes

Fix $w\in(0,1)$. Consider an arbitrary code $\mathcal{C}$ of constant-weight
$w$ for the Z-channel with noise level $\tau=\tau_{L}(w)+\varepsilon$. Let
$M\coloneqq|\mathcal{C}|$. It was shown in [LLP22] via a double-counting
argument that

$\displaystyle\frac{M^{L}}{M(M-1)\cdots(M-L+1)}$
$\displaystyle\geq\frac{\tau}{\tau_{L}(w)}.$ (7)

Rearranging terms, we get

$\displaystyle(M(M-1)\cdots(M-L+1))(\tau_{L}(w)+\varepsilon)$
$\displaystyle\leq M^{L}\tau_{L}(w)$ $\displaystyle\implies$
$\displaystyle(M(M-1)\cdots(M-L+1))\varepsilon$
$\displaystyle\leq(M^{L}-M(M-1)\cdots(M-L+1))\tau_{L}(w)$
$\displaystyle\implies$
$\displaystyle\frac{M(M-1)\cdots(M-L+1)}{M^{L}-M(M-1)\cdots(M-L+1)}$
$\displaystyle\leq\frac{\tau_{L}(w)}{\varepsilon}.$

Applying Taylor expansion to the LHS of the above inequality, we get

$\displaystyle\frac{M}{\binom{L}{2}}-O_{L}(1)$
$\displaystyle\leq\frac{\tau_{L}(w)}{\varepsilon}$ $\displaystyle\implies$
$\displaystyle M$ $\displaystyle\leq\frac{C_{L,w}}{\varepsilon}+O_{L}(1),$

where $C_{L,w}\coloneqq\tau_{L}(w)\binom{L}{2}=(w-w^{L})\binom{L}{2}$.

We have therefore proved the following theorem.

######  Theorem 6.

Any $w$-constant-weight list-decodable code $\mathcal{C}$ for the Z-channel
with list-decoding radius $w-w^{L}+\varepsilon$ has size at most
$\frac{C_{L,w}}{\varepsilon}+O_{L}(1)$ where
$C_{L,w}\coloneqq(w-w^{L})\binom{L}{2}$.

###  5.4 Construction of constant-weight codes

In this section, we construct codes of constant-weight $w$ whose list-decoding
radius is $\varepsilon$-_above_ the list-decoding Plotkin point $\tau_{L}(w)$
for Z-channels. The code we construct has size $\Theta(1/\varepsilon)$, which
is optimal by the upper bound in the preceding section. Our construction is
inspired by [ABP18].

We prove the following theorem.

######  Theorem 7.

There exists a $w$-constant-weight $(L-1)$-list-decodable code $\mathcal{C}$
for the Z-channel with list-decoding radius $w-w^{L}-\varepsilon$ of size at
least $\frac{c_{L,w}}{\varepsilon}+o_{L,w}(1)$ where
$c_{L,w}=(1-w)w^{L-1}\binom{L}{2}$.

###### Proof.

Fix the weight $w$, $0<w<1$. Let $m$ be a sufficiently large integer. Since
$m$ is sufficiently large, we may assume that $m/w$ is an integer. Let
$M\coloneqq m/w$ and $n\coloneqq\binom{m/w}{m}$. Our construction of
$\mathcal{C}$ can be viewed as an $M\times n$ matrix, each row of which is a
codeword denoted by $\boldsymbol{x}_{i}$ ($1\leq i\leq M$). The code
$\mathcal{C}$ consists of all possible length-$(m/w)$ vectors of Hamming
weight $m$ as its _columns_.222Note that there are $\binom{m/w}{m}=n$ such
columns in total.

To examine $(L-1)$-list-decodability of $\mathcal{C}$, we compute the
$(L-1)$-list-decoding radius $\tau_{L}(\mathcal{C})$ of $\mathcal{C}$. By
symmetry, the Chebyshev radius $\mathrm{rad}(\mathcal{L})$ of any $L$-list
$\mathcal{L}\in\binom{\mathcal{C}}{L}$ of codewords does not depend on the
choice of $\mathcal{L}$. Therefore,
$\tau_{L}(\mathcal{C})=\mathbf{E}_{\mathcal{L}}\\{\mathrm{rad}(\mathcal{L})\\}$
where the expectation is over $\mathcal{L}$ uniformly chosen from
$\binom{\mathcal{C}}{L}$. We now compute the latter quantity.

$\displaystyle\mathbf{E}_{\mathcal{L}}\\{\mathrm{rad}(\mathcal{L})\\}$
$\displaystyle=nw-\mathbf{E}_{\mathcal{L}}\left\\{\left|\bigcap_{\boldsymbol{x}\in\mathcal{L}}\mathrm{supp}(\boldsymbol{x})\right|\right\\}$
$\displaystyle=nw-\mathbf{E}_{\mathcal{L}}\left\\{\sum_{i\in[n]}\mathds{1}\\{\forall\boldsymbol{x}\in\mathcal{L},\;x_{i}=1\\}\right\\}$
$\displaystyle=nw-\sum_{i\in[n]}\Pr_{\mathcal{L}}\\{\forall\boldsymbol{x}\in\mathcal{L},\;x_{i}=1\\}$
$\displaystyle=nw-n\frac{\binom{m}{L}}{\binom{m/w}{L}}.$

The last equality follows since the probability in the summation can be viewed
as the probability that one gets $L$ ones when sampling without replacement
$L$ bits from a length-$(m/w)$ vector of weight $m$.

Taking the Taylor expansion of the above expression at $m\to\infty$, we get

$\displaystyle\tau_{L}(\mathcal{C})=\mathbf{E}_{\mathcal{L}}\\{\mathrm{rad}(\mathcal{L})\\}=n\left(w-w^{L}+(1-w)w^{L}\binom{L}{2}m^{-1}+O_{L,w}(m^{-2})\right).$

Recall that we want $\mathcal{C}$ to be $\varepsilon$-above the Plotkin point,
i.e., $\tau_{L}(\mathcal{C})\geq
n(\tau_{L}(w)+\varepsilon)=n(w-w^{L}+\varepsilon)$. This is satisfied as long
as

$\displaystyle\varepsilon$
$\displaystyle\leq(1-w)w^{L}\binom{L}{2}m^{-1}+O_{L,w}(m^{-2})$
$\displaystyle\impliedby$ $\displaystyle\varepsilon$
$\displaystyle\leq(1-w)w^{L-1}\binom{L}{2}M^{-1}+O_{L,w}(M^{-2})$
$\displaystyle\impliedby$ $\displaystyle M$
$\displaystyle\leq\frac{c_{L,w}}{\varepsilon}+o_{L,w}(1),$

where $c_{L,w}\coloneqq(1-w)w^{L-1}\binom{L}{2}$. This finishes the proof. ∎

###  5.5 Upper bound for approximate constant-weight codes

The proof in Sec. 5.3 can be modified to work for _approximate_ constant-
weight codes.

######  Theorem 8.

Let $\mathcal{C}$ be an arbitrary $(L-1)$-list-decodable code for the
Z-channel with list-decoding radius $\tau=w-w^{L}+\varepsilon$. Suppose that
every codeword in $\mathcal{C}$ has weight in $[nw(1-\delta),nw(1+\delta)]$
for some $\delta\in[0,\tau/(2w))$. Then $M\coloneqq|\mathcal{C}|$ satisfies
the following relation:

$\displaystyle\frac{M^{L}}{M(M-1)\cdots(M-L+1)}$
$\displaystyle\geq\frac{\tau-2w\delta}{w(1+\delta)-(w(1-\delta))^{L}}.$

######  Remark 1.

If $\delta=0$, the above theorem recovers Theorem 6.

###### Proof.

To derive an upper bound on $M$, we follow a double-counting argument commonly
used in coding theory. We bound from both sides the following quantity:

$\displaystyle\sum_{\mathcal{L}\in[M]^{L}}\sum_{j\in\mathcal{L}}d_{Z}(\boldsymbol{x}_{j},\boldsymbol{y}_{\mathcal{L}}),$
(8)

where $\boldsymbol{y}_{\mathcal{L}}$ is defined in Eqn. (5).

We first give a lower bound on Eqn. (8). We drop all terms in Eqn. (8) with an
$\mathcal{L}$ whose elements are not all distinct. For any $\mathcal{L}$ whose
elements are all distinct, by list-decodability,

$\displaystyle\max_{j\in\mathcal{L}}d_{Z}(\boldsymbol{x}_{j},\boldsymbol{y}_{\mathcal{L}})=\max_{j\in\mathcal{L}}\textrm{wt}(\boldsymbol{x}_{j})-\textrm{wt}(\boldsymbol{y}_{\mathcal{L}})>n\tau.$

Since $\mathcal{C}$ is approximate constant-weight, we have
$|\textrm{wt}(\boldsymbol{x}_{i})-\textrm{wt}(\boldsymbol{x}_{j})|\leq
2nw\delta$ for any $i\neq j$. Therefore, Eqn. (8) is at least
$M(M-1)\cdots(M-L+1)(n\tau+(L-1)(n\tau-2nw\delta))$.

We then give an upper bound on Eqn (8).

$\displaystyle\sum_{(i_{1},\cdots,i_{L})\in[M]^{L}}\sum_{j\in[L]}d_{Z}(\boldsymbol{x}_{i_{j}},\boldsymbol{y}_{\mathcal{L}})$
$\displaystyle=\sum_{(i_{1},\cdots,i_{L})\in[M]^{L}}\sum_{j\in[L]}(\textrm{wt}(\boldsymbol{x}_{i_{j}})-\textrm{wt}(\boldsymbol{y}_{\mathcal{L}}))$
$\displaystyle=\sum_{(i_{1},\cdots,i_{L})\in[M]^{L}}\sum_{j\in[L]}\left(\textrm{wt}(\boldsymbol{x}_{i_{j}})-\sum_{k\in[n]}\mathds{1}\left\\{x_{i_{1},k}=1\right\\}\cdots\mathds{1}\left\\{x_{i_{L},k}=1\right\\}\right)$
$\displaystyle\leq
M^{L}Lnw(1+\delta)-\sum_{j\in[L]}\sum_{k\in[n]}\prod_{\ell\in[L]}\left(\sum_{i_{\ell}\in[M]}\mathds{1}\left\\{x_{i_{\ell},k}=1\right\\}\right)$
$\displaystyle=M^{L}Lnw(1+\delta)-L\sum_{k\in[n]}S_{k}^{L},$

where
$S_{k}\coloneqq\sum\limits_{i\in[M]}\mathds{1}\left\\{x_{i,k}=1\right\\}$
denotes the weight of the $k$th _column_ of $\mathcal{C}\in\\{0,1\\}^{M\times
n}$. By the norm comparison inequality $\|\boldsymbol{x}\|_{p}\leq
n^{1/p-1/q}\|\boldsymbol{x}\|_{q}$ for any $\boldsymbol{x}\in\mathbb{R}^{n}$
and $0<p<q$, we have

$\displaystyle\sum_{k\in[n]}S_{k}^{L}$ $\displaystyle\geq
n^{1-L}\left(\sum_{k\in[n]}S_{k}\right)^{L}\geq
n^{1-L}(Mnw(1-\delta))^{L}=n(Mw(1-\delta))^{L}.$

Therefore, Eqn. (8) is upper bounded by
$M^{L}Lnw(1+\delta)-nL(Mw(1-\delta))^{L}$.

Finally, putting the lower and upper bounds together, we get

$\displaystyle M(M-1)\cdots(M-L+1)(n\tau+(L-1)(n\tau-2nw\delta))$
$\displaystyle\leq M^{L}Lnw(1+\delta)-nL(Mw(1-\delta))^{L}$
$\displaystyle\implies$ $\displaystyle M(M-1)\cdots(M-L+1)(L\tau-L\cdot
2w\delta)$ $\displaystyle\leq M^{L}Lw(1+\delta)-LM^{L}(w(1-\delta))^{L}$
$\displaystyle\implies$ $\displaystyle M(M-1)\cdots(M-L+1)(\tau-2w\delta)$
$\displaystyle\leq M^{L}(w(1+\delta)-(w(1-\delta))^{L})$
$\displaystyle\implies$ $\displaystyle\frac{M^{L}}{M(M-1)\cdots(M-L+1)}$
$\displaystyle\geq\frac{\tau-2w\delta}{w(1+\delta)-(w(1-\delta))^{L}}.\qed$
(9)

In fact, one can apply a similar trick as that used in the proof of Theorem 4
and obtain a cheaper version of Theorem 8.

######  Theorem 9.

Let $\mathcal{C}$ be an $(L-1)$-list-decodable code for the Z-channel with
list-decoding radius $\tau>\tau_{L}$. Suppose that every codeword in
$\mathcal{C}$ has weight between $nw_{1}$ and $nw_{2}$ for some $0\leq
w_{1}\leq w_{2}\leq 1$. Then

$\displaystyle|\mathcal{C}|$
$\displaystyle\leq\frac{L-1}{1-\left(\frac{w_{2}/(1+w_{2}-w_{1})-w_{2}^{L}/(1+w_{2}-w_{1})^{L}}{\tau/(1+w_{2}-w_{1})}\right)^{\frac{1}{L-1}}}.$

###### Proof.

The proof follows by augmenting the code $\mathcal{C}$ to reduce it from
approximate constant-weight to exact constant-weight.

Let $\mathcal{C}$ be as described in the theorem statement. One can append
$(w_{2}-w_{1})n$ coordinates to each codeword in $\mathcal{C}$ in such a way
that all codewords of length $(1+w_{2}-w_{1})n$ have weight exactly $w_{2}n$.
Note that the _relative_ weight of each codeword is now
$\frac{w_{2}}{1+w_{2}-w_{1}}$. Moreover, the augmented code is $(L-1)$-list-
decodable with _relative_ list-decoding radius $\frac{\tau}{1+w_{2}-w_{1}}$.

We now recall the upper bound for $w$-constant-weight code given by Eqn. (7):

$\displaystyle\frac{M^{L}}{M(M-1)\cdots(M-L+1)}$
$\displaystyle\geq\frac{\tau}{w-w^{L}}$ $\displaystyle\implies$
$\displaystyle(M-L+1)^{L-1}\tau$ $\displaystyle\leq M^{L-1}(w-w^{L})$
$\displaystyle\implies$ $\displaystyle M$
$\displaystyle\leq\frac{L-1}{1-\left(\frac{w-w^{L}}{\tau}\right)^{\frac{1}{L-1}}}.$

Normalizing the parameters by $\frac{1}{1+w_{2}-w_{1}}$, we get the desired
bound. ∎

In the following statement, we estimate the size of a code $\varepsilon$-above
the list-decoding Plotkin point if all codewords are of weight
$\varepsilon$-close to each other.

######  Corollary 1.

Let $\mathcal{C}$ be an $(L-1)$-list-decodable code for the Z-channel with
list-decoding radius $\tau=\tau_{L}+\varepsilon$. Suppose that the relative
weight of all codewords is in the range $[w_{1},w_{2}]$, where
$w_{2}-w_{1}\leq\phi_{L}\varepsilon$ with $\phi_{L}$ being a positive real
number so that $\phi_{L}\leq\frac{1-\tau_{L}}{2\tau_{L}}$. Then
$|\mathcal{C}|\leq\frac{(L-1)^{2}}{\varepsilon}$ for small enough
$\varepsilon$.

###### Proof.

By Theorem 9 we get that

$|\mathcal{C}|\leq\frac{L-1}{1-\left(\frac{w_{2}/(1+w_{2}-w_{1})-w_{2}^{L}/(1+w_{2}-w_{1})^{L}}{\tau/(1+w_{2}-w_{1})}\right)^{\frac{1}{L-1}}}.$

After simple manipulation, it remains to show that

$w_{2}-\frac{w_{2}^{L}}{(1+\varepsilon\phi_{L})^{L-1}}\leq\left(1-\frac{\varepsilon}{L-1}\right)^{L-1}(\tau_{L}+\varepsilon).$

The LHS of the above inequality achieves its maximum at
$w_{2}=\frac{1+\varepsilon\phi_{L}}{L^{1/(L-1)}}$. Thus, after simplification,
we get a stronger sufficient condition

$(1+\varepsilon\phi_{L})\tau_{L}\leq(1-\varepsilon)(\tau_{L}+\varepsilon)$

or

$\phi_{L}\leq\frac{(1-\tau_{L})\varepsilon-\varepsilon^{2}}{\varepsilon\tau_{L}}.$

The latter holds for sufficiently small $\varepsilon$, and the corollary
follows. ∎

######  Remark 2.

Readers who are familiar with the literature may have noticed that unlike
results for symmetric errors [Bli86, ABP18], to prove Theorem 8, we did not
use Ramsey-theoretic machinery to first extract a subcode which is
(approximately) “equidistant”. The benefit of the Ramsey reduction is that the
Chebyshev radius of the subcode turns out to be (approximately) the same as
another stronger notion of radius called “average radius”. The average radius
is analytically much easier to deal with since unlike the Chebyshev radius, it
does not involve a minimax expression. However, the drawback is that the size
of the subcode is much smaller than the original one. The optimal size of
post-Plotkin codes for symmetric errors remains open.

The reason why in Theorem 8 we did not need Ramsey reduction while still
managed to obtain the optimal bound on the code sizes is as follows. For
asymmetric errors, the Chebyshev radius of (approximate) constant-weight codes
admits an explicit expression since the Chebyshev center (i.e., the minimizer
$\boldsymbol{y}$ in Eqn. (4)) can be easily identified with Eqn. (5). Note,
however, that in the symmetric case there is no simple formula for the
Chebyshev center.

###  5.6 Upper bound for general codes

For $L\geq 2$ and $\varepsilon>0$, denote the maximal size of a list-decodable
code for the Z-channel with $(L-1)$-list-decoding radius
$\tau_{L}+\varepsilon$ by $M_{L}(\varepsilon)$. From Corollary 1 one can
immediately see that $M_{L}(\varepsilon)=O_{L}(\varepsilon^{-2})$. However, it
is possible to improve this bound. In principle, we will follow the same
approach as in the proof of Theorem 4. For simplicity of arguments, we assume
that some numbers that are introduced in the discussion in this and next
subsections are integers since this will not affect the main conclusion.

######  Theorem 10.

For $L\geq 2$, it holds that $M_{L}(\varepsilon)=O_{L}(\varepsilon^{-3/2})$ as
$\varepsilon\to 0$.

######  Remark 3.

A suboptimal upper bound $O_{L}(\varepsilon^{-2})$ was presented in the first
version of [LLP20]. The authors of the current manuscript then managed to
improve this bound to the optimal order $O_{L}(\varepsilon^{-3/2})$. During
the finalization of the current manuscript, the first author updated the other
manuscript [LLP22] and presented the improved bound
$O_{L}(\varepsilon^{-3/2})$ there. However, the latter bound was first
obtained by the authors of the current manuscript.

###### Proof.

Let $\mathcal{C}$ be an $(L-1)$-list-decodable code of length $n$ with
$(L-1)$-list-decoding radius $\tau(\mathcal{C})=\tau_{L}+\varepsilon$ for some
$\varepsilon>0$. Recall that $w_{\max}$ is the argument achieving the maximum
of the function $w-w^{L}$ and $\tau_{L}=w_{\max}-w_{\max}^{L}$. Consider all
codewords whose Hamming weight is between $w_{1}n$ and $w_{2}n$ with
$w_{1}<w_{2}$.

Small weight $w_{1}=w_{\max}-\Omega_{L}(\sqrt{\varepsilon})$: In the
following, we analyze the case when
$w_{1}=w_{\max}-\Omega_{L}(\sqrt{\varepsilon})$, where $w_{\max}$ is the
maximizer of $w-w^{L}$, i.e. $w_{\max}$ satisfies $1-Lw_{\max}^{L-1}=0$. In
our analysis, we assume that $w_{1}$ is fixed and $\Delta:=w_{2}-w_{1}>0$ is
to be specified. By Theorem 9, the number of codewords of these weights is at
most

$\frac{L-1}{1-\left(\frac{w_{2}/(1+w_{2}-w_{1})-w_{2}^{L}/(1+w_{2}-w_{1})^{L}}{\tau(\mathcal{C})/(1+w_{2}-w_{1})}\right)^{\frac{1}{L-1}}}.$

This quantity is at most $\frac{L-1}{\varepsilon}$ if $\Delta=\Delta(w_{1})$
satisfies

$w_{2}-w_{2}(w_{2}/(1+\Delta))^{L-1}\leq\tau(\mathcal{C})(1-\varepsilon)^{L-1}.$
(10)

Recall that
$\tau(\mathcal{C})=\tau_{L}+\varepsilon=w_{\max}-w_{\max}^{L}+\varepsilon$.
For any $\gamma>0$, there exists a sufficiently small $\varepsilon>0$ such
that the RHS of inequality (10) is lower bounded as follows

$\displaystyle\tau(\mathcal{C})(1-\varepsilon)^{L-1}$
$\displaystyle\geq(w_{\max}-w_{\max}^{L}+\varepsilon)\left(1-(L-1)\varepsilon\right)$
(11) $\displaystyle\geq
w_{\max}-w_{\max}^{L}+\varepsilon\left(1-\gamma-(L-1)(w_{\max}-w_{\max}^{L})\right).$

Define $C_{L}$ to be $1-\gamma-(L-1)(w_{\max}-w_{\max}^{L})$. Clearly, for
$2\leq L\leq 3$ and sufficiently small $\gamma$, $C_{L}>0$, whereas for $L>3$,
$C_{L}<0$. Note that $(w_{1}+\Delta)(1+\Delta)^{-1}\geq w_{1}$. Now we
elaborate the LHS of (10):

$\displaystyle w_{2}-w_{2}(w_{2}/(1+\Delta))^{L-1}\leq$ $\displaystyle
w_{2}-w_{1}((w_{1}+\Delta)(1+\Delta)^{-1})^{L-1}$ (12) $\displaystyle\leq$
$\displaystyle w_{2}-w_{1}^{L}.$

Given (10)-(12), we conclude that it is sufficient to take $w_{2}$ such that
it satisfies

$w_{2}\leq w_{\max}-w_{\max}^{L}+w_{1}^{L}+C_{L}\varepsilon.$ (13)

Consider the iterative process

$x_{i}:=w_{\max}-w_{\max}^{L}+x_{i-1}^{L}+C_{L}\varepsilon$

with starting point $x_{1}=0$. We shall prove by induction that $x_{i}\geq
w_{\max}-\frac{D_{L}}{i}$ for all $i\in[1,\varepsilon^{-1/2}]$ and some
absolute constant $D_{L}\geq 0$. The base case $i=1$ holds true if $D_{L}\geq
w_{\max}$. Now assume that the inductive hypothesis is true for some $i>1$.
Recall the Bernoulli inequality $(1-y)^{s}\geq 1-sy$ for any real $y\leq 1$
and $s\geq 1$. Then we obtain

$\displaystyle x_{i+1}$ $\displaystyle\geq
w_{\max}-w_{\max}^{L}+w_{\max}^{L}\left(1-\frac{D_{L}}{iw_{\max}}\right)^{L}+C_{L}\varepsilon$
$\displaystyle\geq
w_{\max}-w_{\max}^{L}+w_{\max}^{L}\left(1-\frac{2D_{L}}{iw_{\max}}+\frac{D_{L}^{2}}{i^{2}w_{\max}^{2}}\right)^{L/2}+C_{L}\varepsilon$
$\displaystyle\geq
w_{\max}-w_{\max}^{L}+w_{\max}^{L}\left(1-\frac{LD_{L}}{iw_{\max}}+\frac{LD_{L}^{2}}{2i^{2}w_{\max}^{2}}\right)+C_{L}\varepsilon$
$\displaystyle\geq
w_{\max}-\frac{D_{L}}{i+1}-\frac{D_{L}}{i(i+1)}+\frac{D_{L}^{2}}{2w_{\max}i^{2}}+C_{L}\varepsilon.$

Note that for $D_{L}\geq\max(4w_{\max},|C_{L}|)$ and
$i\leq\varepsilon^{-1/2}$, the sum of the last three terms is non-negative and
the inductive hypothesis follows.

Define the subcode $\mathcal{C}^{\prime}\subseteq\mathcal{C}$ that includes
all codewords of $\mathcal{C}$ with the Hamming weight within the range
$[0,n(w_{\max}-D_{L}\varepsilon^{1/2})]$. The above arguments imply that the
size of $\mathcal{C}^{\prime}$ is $O_{L}(\varepsilon^{-3/2})$.

Large weight $w_{1}=w_{\max}+\Omega_{L}(\sqrt{\varepsilon})$: Consider the
iterative process

$x_{i}:=w_{\max}-w_{\max}^{L}+x_{i+1}^{L}+C_{L}\varepsilon$

with starting point $x_{1}=w_{\max}+E_{L}\varepsilon^{1/2}$, where an absolute
constant $E_{L}$ is to be specified. We shall prove by induction that
$x_{i}\geq w_{\max}+\frac{E_{L}}{\varepsilon^{-1/2}+1-i}$ for all
$i\in[1,\varepsilon^{-1/2}]$. The base case $i=1$ holds true. Assume the
hypothesis is true for some $i>1$. Then we obtain

$\displaystyle x_{i+1}$ $\displaystyle\geq
w_{\max}-w_{\max}^{L}+\left(w_{\max}+\frac{E_{L}}{\varepsilon^{-1/2}+1-i}\right)^{L}+C_{L}\varepsilon$
$\displaystyle=w_{\max}-w_{\max}^{L}+w_{\max}^{L}\left(1+\frac{2E_{L}}{w_{\max}(\varepsilon^{-1/2}+1-i)}+\frac{E_{L}^{2}}{w_{\max}^{2}(\varepsilon^{-1/2}+1-i)^{2}}\right)^{L/2}+C_{L}\varepsilon$
$\displaystyle\geq
w_{\max}+\frac{E_{L}}{\varepsilon^{-1/2}+1-i}+\frac{E_{L}^{2}}{2w_{\max}(\varepsilon^{-1/2}+1-i)^{2}}+C_{L}\varepsilon$
$\displaystyle=w_{\max}+\frac{E_{L}}{\varepsilon^{-1/2}-i}+\frac{E_{L}}{(\varepsilon^{-1/2}+1-i)(\varepsilon^{-1/2}-i)}+\frac{E_{L}^{2}}{2w_{\max}(\varepsilon^{-1/2}+1-i)^{2}}+C_{L}\varepsilon.$

Observe that the sum of the last three terms is non-negative for
$E_{L}\geq\max\left\\{8w_{\max},|C_{L}|/2\right\\}$.

Define the subcode $\mathcal{C}^{\prime\prime}\subseteq\mathcal{C}$ that
includes all codewords of $\mathcal{C}$ with the Hamming weight within the
range $[n(w_{\max}+D_{L}\varepsilon^{1/2}),n]$. The above arguments imply that
the size of $\mathcal{C}^{\prime\prime}$ is $O_{L}(\varepsilon^{-3/2})$.

Moderate weight $|w_{1}-w_{\max}|=O_{L}(\sqrt{\varepsilon})$: By Corollary 1
we can partition the set of codewords with weight
$[n(w_{\max}-D_{L}\varepsilon^{1/2}),n(w_{\max}+E_{L}\varepsilon^{1/2})]$ into
$O_{L}(\varepsilon^{-1/2})$ subcodes such that each of them has size
$O_{L}(\varepsilon^{-1})$.

Summing up the above discussion, we conclude that the size of $\mathcal{C}$
can be bounded as $O_{L}(\varepsilon^{-3/2})$ as $\varepsilon\to 0$. ∎

###  5.7 Construction of general codes

In this section we construct $(L-1)$-list-decodable codes of size
$\Omega_{L}(\varepsilon^{-3/2})$ and length $\exp(\Theta(\varepsilon^{-3/2}))$
whose list-decoding radius is $\tau_{L}+\varepsilon$. First we prove an
auxiliary technical lemma.

######  Lemma 11.

Let $\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{L}$ be binary vectors of length
$N$ such that the Hamming weight of these vectors is $w_{1}N,\ldots,w_{L}N$
with $0\leq w_{1}\leq\ldots\leq w_{L}\leq 1$. Define
$\tilde{\boldsymbol{x}}_{1},\ldots,\tilde{\boldsymbol{x}}_{L}$ to be random
vectors obtained from $\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{L}$ by
applying independent random permutations over the set of coordinates (each of
the $N!$ permutations is equally likely to appear). Let $\tilde{W}N$ denote
the number of coordinates $i\in[N]$ such that
$\tilde{x}_{1,i}=\tilde{x}_{2,i}=\ldots=\tilde{x}_{L,i}=1$, i.e., random
variable $\tilde{W}$ is defined as the fraction of coordinates where all
vectors $\tilde{\boldsymbol{x}}_{1},\ldots,\tilde{\boldsymbol{x}}_{L}$ are
ones. Then for any $\gamma>0$ it holds that

$\Pr\left\\{\tilde{W}\geq\gamma+\prod_{i=1}^{L}w_{i}\right\\}\leq(L+1)\exp(-N\gamma^{2}2^{-2L+1}).$

###### Proof.

Fix a real number $\delta$ such that $0<\delta<\gamma/(2^{L}-1)$. Let
$\overline{\boldsymbol{x}}_{i}$ be a random binary vector such that each
coordinate of $\overline{\boldsymbol{x}}_{i}$ is an independent random
variable which has Bernoulli distribution with parameter
$\overline{w}_{i}:=w_{i}+\delta$. We note that the random vectors
$\overline{\boldsymbol{x}}_{i}$ and $\tilde{\boldsymbol{x}}_{i}$ can be
equivalently defined (in terms of distributions) using the following three
steps:

  1. 1.

sample an independent binomial random variable $\xi_{i}$ with parameters
$\mathsf{Bin}(N,\overline{w}_{i})$ and set $\eta_{i}$ to be constant $w_{i}N$;

  2. 2.

define $\boldsymbol{y}_{i}$ and $\boldsymbol{z}_{i}$ to be the binary vectors
whose first $\xi_{i}$ and, respectively, $\eta_{i}$ coordinates are ones and
the remaining coordinates are zeros;

  3. 3.

apply an independent random permutation $\pi_{i}$, defined over the set of
coordinates $[N]$, to $\boldsymbol{y}_{i}$ and $\boldsymbol{z}_{i}$.

Let $\overline{W}N$ denote the number of coordinates $i\in[N]$ such that
$\overline{x}_{1,i}=\ldots=\overline{x}_{L,i}=1$, i.e., $\overline{W}$ is the
fraction of coordinates where all vectors
$\overline{\boldsymbol{x}}_{1},\ldots,\overline{\boldsymbol{x}}_{L}$. Clearly,
$\overline{W}N$ has a Binomial distribution with parameters $N$ and
$\prod_{i=1}^{L}\overline{w}_{i}$. Let $A_{i}$ denote the event that
$\xi_{i}\geq w_{i}$. Clearly, $\tilde{W}$ is stochastically dominated by the
random variable $\overline{W}$ conditioned on events $A_{1},\ldots,A_{L}$. By
Hoeffding’s inequality, we obtain

$\Pr\\{A_{i}\\}\geq 1-\exp(-2\delta^{2}N)$

and, hence,

$\Pr\\{A_{1}\cap\ldots\cap A_{L}\\}\geq 1-L\exp(-2\delta^{2}N).$ (14)

Then

$\displaystyle\Pr\left\\{\tilde{W}\geq\gamma+\prod_{i=1}^{L}w_{i}\right\\}$
$\displaystyle\leq$
$\displaystyle\Pr\left\\{\overline{W}\geq\gamma+\prod_{i=1}^{L}w_{i}\,|\,A_{1},\ldots,A_{L}\right\\}$
$\displaystyle\leq$
$\displaystyle\frac{\Pr\left\\{\overline{W}\geq\gamma+\prod_{i=1}^{L}w_{i}\right\\}}{\Pr\left\\{A_{1}\cap\ldots\cap
A_{L}\right\\}}$ $\displaystyle\leq$ $\displaystyle
1-\Pr\left\\{A_{1}\cap\ldots\cap
A_{L}\right\\}+\Pr\left\\{\mathsf{Bin}(N,w^{\prime})\geq
N\left(\gamma+\prod_{i=1}^{L}w_{i}\right)\right\\},$ (15)

where $w^{\prime}:=\prod_{i=1}^{L}\overline{w}_{i}$. One can easily prove by
induction on $L$ that $w^{\prime}\leq\prod_{i=1}^{L}w_{i}+(2^{L}-1)\delta$. By
Hoeffding’s inequality, we get

$\Pr\left\\{\mathsf{Bin}(N,w^{\prime})\geq
N\left(\gamma+\prod_{i=1}^{L}w_{i}\right)\right\\}\leq\exp\left(-2(\gamma-(2^{L}-1)\delta)^{2}N\right).$

By combining the latter inequality with inequalities (14)-(15), we obtain

$\Pr\left\\{\tilde{W}\geq\gamma+\prod_{i=1}^{L}w_{i}\right\\}\leq
L\exp(-2\delta^{2}N)+\exp\left(-2(\gamma-(2^{L}-1)\delta)^{2}N\right).$

After choosing $\delta$ that satisfies the equality
$\delta=\gamma-(2^{L}-1)\delta$, i.e., $\delta=\gamma/2^{L}$, we derive the
required statement. ∎

Now we are ready to present the main statement concerning the existence of
list-decodable codes. In principle, we follow the same arguments as used in
the case of uniquely-decodable codes. The suggested construction is order-
optimal by the upper bound for general codes.

######  Theorem 12.

There exists an $(L-1)$-list-decodable code code of length
$\exp(O_{L}(\varepsilon^{-3/2}))$ whose list-decoding radius is
$\tau_{L}+\varepsilon$. Furthermore, its size is
$\Omega_{L}(\varepsilon^{-3/2})$ as $\varepsilon\to 0$.

###### Proof.

Recall that $w_{\max}$ is the argument attaining the maximum of the function
$\tau_{L}(w)=w-w^{L}$, i.e., $w_{\max}$ satisfies
$w_{\max^{L-1}}=\frac{1}{L}$. Consider the positive integer
$m:=1/\varepsilon$. Define $J$ to be the set of consecutive integers between
$-\sqrt{(w_{\max}-w_{\max}^{2})m/2}$ and $\sqrt{(w_{\max}-w_{\max}^{2})m/2}$.
For every $j\in J$, denote $n_{j}:=\binom{m}{w_{\max}m-j}$. Consider a binary
matrix $A_{j}$ of size $m\times n_{j}$, whose columns are all possible binary
vectors of length $m$ and weight $wm-j$. By Theorem 7, we get that the code
formed by rows of matrix $A_{j}$ is a $w_{j}$-constant-weight $(L-1)$-list-
decodable code with the list-decoding radius $\tau_{j,L}$, where

$\tau_{j,L}=w_{j}-w_{j}^{L}+(1-w_{j})w_{j}^{L-1}\binom{L}{2}m^{-1}+O_{L}(m^{-2}),\quad
w_{j}=\frac{mw_{\max}-j}{m}.$

Clearly, we have

$\displaystyle\min\\{\tau_{j,L}:j\in J\\}$ $\displaystyle=$ $\displaystyle
w_{\max}-w_{\max}^{L}+\min_{j\in
J}\left(\frac{jLw_{\max}^{L-1}}{m}-\frac{j}{m}-\frac{j^{2}\binom{L}{2}w_{\max}^{L-2}}{m^{2}}\right)+(1-w_{\max})w_{\max}^{L-1}\binom{L}{2}m^{-1}+o_{L}(m^{-1})$
$\displaystyle=$ $\displaystyle
w_{\max}-w_{\max}^{L}+(1-w_{\max})\frac{L-1}{4m}+o_{L}(m^{-1})$
$\displaystyle=$ $\displaystyle\tau_{L}+\Omega_{L}(\varepsilon).$ (16)

For a positive integer $z$, consider a matrix $A_{j}^{(z)}$ of size $2m\times
zn_{j}$ that is composed of $z$ copies of the matrix $A_{j}$. We write copies
of $A_{j}$ to the right, i.e., $A_{j}^{(z)}=(A_{j},A_{j},\ldots,A_{j})$. By
$\tilde{A}_{j}^{(z)}$ denote a matrix obtained from $A_{j}^{(z)}$ by a random
permutation of its columns. This permutation is taken uniformly at random from
the set of all permutations. Note that the list-decoding radius of the code
formed by $\tilde{A}_{j}^{(z)}$ is the same as for the code given by $A_{j}$.
Define integers

$z_{j}:=\prod_{\begin{subarray}{c}i\in
J\setminus\\{j\\}\end{subarray}}\binom{m}{w_{\max}m-j},\quad
N:=\prod_{\begin{subarray}{c}i\in J\end{subarray}}\binom{m}{w_{\max}m-j},\quad
M:=m|J|.$

Consider a random matrix $\tilde{A}$ of size $M\times N$ containing
$\tilde{A}_{j}^{(z_{j})}$ as a submatrix for all $j\in J$. We assume that the
matrices $\tilde{A}_{j}^{(z_{j})}$ are written one below the other using the
ascending order of parameter $j$. Let $\mathcal{C}$ denote a code formed by
rows of $\tilde{A}$. For $\varepsilon\to 0$, we estimate the number of rows
$M$ and the number of columns $N$ in $\tilde{A}$ as follows

$M=\Theta_{L}(\varepsilon^{-3/2}),\quad
N=\exp(\Theta_{L}(\varepsilon^{-3/2})).$

We claim that with high probability, $\mathcal{C}$ is an $(L-1)$-list-
decodable code with the list-decoding radius
$\tau_{L}+\Omega_{L}(\varepsilon)$. In the remainder of the proof, we prove
this claim.

Let us take $L$ distinct codewords
$\mathcal{L}=\\{\tilde{\boldsymbol{x}}_{1},\ldots,\tilde{\boldsymbol{x}}_{L}\\}$
from $\mathcal{C}$ such that $L_{1}$ codewords
$\mathcal{L}_{1}=\\{\tilde{\boldsymbol{x}}_{1},\ldots,\tilde{\boldsymbol{x}}_{L_{1}}\\}$
are rows from $\tilde{A}^{(z_{j_{1}})}_{j_{1}}$, $L_{2}$ codewords
$\mathcal{L}_{2}=\\{\tilde{\boldsymbol{x}}_{L_{1}+1},\ldots,\tilde{\boldsymbol{x}}_{L_{1}+L_{2}}\\}$
are rows from $\tilde{A}^{(z_{j_{2}})}_{j_{2}}$, $\dots$, $L_{k}$ codewords
$\mathcal{L}_{k}=\\{\tilde{\boldsymbol{x}}_{L_{1}+\ldots+L_{k-1}+1},\ldots,\tilde{\boldsymbol{x}}_{L_{1}+\ldots+L_{k}}\\}$
are rows from $\tilde{A}^{(z_{j_{k}})}_{j_{k}}$ with
$j_{1}<j_{2}<\ldots<j_{k}$. We shall prove that the Chabyshev radius for
$\mathcal{L}$ is at least $\tau_{L}+\Omega_{L}(\varepsilon)$. If $k=1$, then
the statement follows from (16). Hereafter, assume that $k\geq 2$. For
$i\in[k]$, the Hamming weight of codewords in $\mathcal{L}_{i}$ is
$Nw_{j_{i}}$, and the number of positions where all codewords in
$\mathcal{L}_{i}$ are ones is $Nw^{\prime}_{i}$ with
$w^{\prime}_{i}:=w_{j_{i}}-\tau_{j_{i},L_{i}}$. Let $\tilde{W}N$ denote the
number of coordinates $i\in[N]$ such that
$\tilde{x}_{1,i}=\ldots=\tilde{x}_{L,i}=1$. By applying Lemma 11, we get that
for any $\gamma>0$

$\Pr\left\\{\tilde{W}\geq\gamma+\prod_{i=1}^{k}w_{i}^{\prime}\right\\}\leq(k+1)\exp(-N\gamma^{2}2^{-2k+1}).$

Since $j_{1}$ is the smallest integer in the set $\\{j_{1},\ldots,j_{k}\\}$,
$\tilde{\boldsymbol{x}}_{1}$ has the lowest Hamming weight $Nw_{j_{1}}$ in the
set $\mathcal{L}$. Therefore, the Chebyshev radius for $\mathcal{L}$ satisfies
$\mathrm{rad}(\mathcal{L})=Nw_{j_{1}}-N\tilde{W}$ and hence

$\Pr\left\\{\mathrm{rad}(\mathcal{L})\leq
N\left(w_{j_{1}}-\gamma-\prod_{i=1}^{k}w^{\prime}_{i}\right)\right\\}\leq(k+1)\exp(-N\gamma^{2}2^{-2k+1}).$

The number of $L$-size subcodes of $\mathcal{C}$ is
$\binom{M}{L}=O_{L}(\varepsilon^{-3L/2})$. By the union bound, the
$(L-1)$-list-decoding radius $\tau_{L}(\mathcal{C})$ is at least

$N\min_{\begin{subarray}{c}1\leq k\leq L\\\ j_{1},\ldots,j_{k}\in J\\\
j_{1}<\ldots<j_{k}\\\ L_{1},\ldots,L_{k}\geq 1\\\
L_{1}+\ldots+L_{k}=L\end{subarray}}\left(w_{j_{1}}-\gamma-\prod_{i=1}^{k}w^{\prime}_{i}\right)$

with probability at least

$1-\binom{M}{L}(k+1)\exp(-N\gamma^{2}2^{-2k+1})=1-O_{L}(\varepsilon^{-3L/2}\exp(-N\gamma^{2}2^{-2L+1})),$

where $N=\exp(\Theta_{L}(\varepsilon^{-3/2}))$. Therefore, it remains to show
that

$w_{j_{1}}-\gamma-\prod_{i=1}^{k}w^{\prime}_{i}=\tau_{L}+\Omega_{L}(\varepsilon)$

for all admissible $j_{1},\ldots,j_{k}$, $L_{1},\ldots,L_{k}$, small enough
$\gamma$ and large enough $m$ (and consequently large $N=N(m)$). Recall that
$w_{j_{i}}=w_{\max}-j_{i}/m$,
$w_{i}^{\prime}=w_{j_{i}}-\tau_{j_{i},L_{i}}=w_{j_{i}}^{L_{i}}-(1-w_{j_{i}})w_{j_{i}}^{L_{i}-1}\binom{L_{i}}{2}m^{-1}+O_{L}(m^{-2})$
and $m=1/\varepsilon$. Thus, it holds that

$\displaystyle w_{i}^{\prime}$
$\displaystyle=(w_{\max}-j_{i}\varepsilon)^{L_{i}}-(1-w_{\max}+j_{i}\varepsilon)(w_{\max}-j_{i}\varepsilon)^{L_{i}-1}\binom{L_{i}}{2}\varepsilon+o_{L}(\varepsilon)$
$\displaystyle=w_{\max}^{L_{i}}-L_{i}j_{i}w_{\max}\varepsilon-(1-w_{\max})w_{\max}^{L_{i}-1}\binom{L_{i}}{2}\varepsilon+o_{L}(\varepsilon)$
$\displaystyle\leq w_{\max}^{L_{i}}-j_{i}L_{i}\varepsilon+o_{L}(\varepsilon).$

Recall that $\tau_{L}=w_{\max}-w_{\max}^{L}$ and $L_{1}+\ldots+L_{k}=L$. Then
we obtain

$\displaystyle w_{j_{1}}-\prod_{i=1}^{k}w^{\prime}_{i}$ $\displaystyle\geq$
$\displaystyle
w_{\max}-j_{1}\varepsilon-\prod_{i=1}^{k}\left(w_{\max}^{L_{i}}-j_{i}L_{i}\varepsilon+o_{L}(\varepsilon)\right)$
$\displaystyle=$
$\displaystyle\tau_{L}+\varepsilon\left(-j_{1}+\sum_{i=1}^{k}\frac{w_{\max}^{L}}{w_{\max}^{L_{i}}}j_{i}L_{i}\right)+o_{L}(\varepsilon)$
$\displaystyle\overset{(a)}{\geq}$
$\displaystyle\tau_{L}+\varepsilon\left(-j_{1}+\frac{1}{L}\sum_{i=1}^{k}j_{i}L_{i}\right)+o_{L}(\varepsilon)$
$\displaystyle\overset{(b)}{=}$
$\displaystyle\tau_{L}+\Omega_{L}(\varepsilon),$

where $(a)$ follows from the fact $L_{i}\geq 1$ and
$w_{\max}^{L-1}=\frac{1}{L}$, $(b)$ is implied by the fact that
$L_{1}+\ldots+L_{k}=L$, $j_{i}$’s are integers and $j_{1}<j_{2}<\ldots<j_{k}$
with $k\geq 2$. ∎

##  6 List-decodable codes below the Plotkin point

In the following two subsections, we will bound $(L-1)$-list-decoding capacity
$C_{L-1}(w,\tau)$ for $\tau<w-w^{L}$. We note that for such a purpose, it
suffices to consider constant-weight codes. This is because for any general
code $\mathcal{C}$ of size $M$, one can find a constant-weight subcode
$\mathcal{C}^{\prime}\subseteq\mathcal{C}$ of size at least $M/(n+1)$. The
rate of $\mathcal{C}$ and $\mathcal{C}^{\prime}$ is asymptotically (in $n$)
the same.

Since the analyses involve applications of the method of types, we need to
first introduce the notion of _types_ of a tuple of vectors. Let
$\mathcal{P}(\Sigma)$ denote the set of distributions supported on a finite
set $\Sigma$.

######  Definition 3 (Type).

Let $\Sigma_{1},\cdots,\Sigma_{k}$ be finite alphabets. Let
$(\boldsymbol{x}_{1},\cdots,\boldsymbol{x}_{k})\in\Sigma_{1}^{n}\times\cdots\times\Sigma_{k}^{n}$.
The _joint type_
$T_{\boldsymbol{x}_{1},\cdots,\boldsymbol{x}_{k}}\in\mathbb{R}^{|\Sigma_{1}|\times\cdots\times|\Sigma_{k}|}$
of $\boldsymbol{x}_{1},\cdots,\boldsymbol{x}_{k}$ is defined as their
empirical distribution (a.k.a. histogram), i.e., for any
$(x_{1},\cdots,x_{k})\in\Sigma_{1}\times\cdots\times\Sigma_{k}$,

$\displaystyle
T_{\boldsymbol{x}_{1},\cdots,\boldsymbol{x}_{k}}(x_{1},\cdots,x_{k})$
$\displaystyle\coloneqq\frac{1}{n}\left|\left\\{i\in[n]:\boldsymbol{x}_{1,i}=x_{1},\cdots,\boldsymbol{x}_{k,i}=x_{k}\right\\}\right|.$

Sanov’s theorem determines the large deviation exponent of the type of an
i.i.d. vector.

######  Theorem 13 (Sanov [San58]).

Let $\mathcal{Q}\subset\mathcal{P}(\Sigma)$ be a subset of distributions on a
finite set $\Sigma$ such that it is equal to the closure of its interior. Let
$\boldsymbol{x}\in\Sigma^{n}$ be distributed according to $P^{\otimes n}$ for
some $P\in\mathcal{P}(\Sigma)$. Then

$\displaystyle\lim_{n\to\infty}\frac{1}{n}\log\Pr\\{T_{\boldsymbol{x}}\in\mathcal{Q}\\}$
$\displaystyle=-\inf_{Q\in\mathcal{Q}}D(Q\|P),$

where $D(Q\|P)$ denotes the Kullback–Leibler divergence between $Q$ and $P$
defined as

$\displaystyle D(Q\|P)$
$\displaystyle\coloneqq\sum_{x\in\Sigma}Q(x)\log\frac{Q(x)}{P(x)}.$

###  6.1 Upper bound on $(L-1)$-list-decoding capacity

In this section, we derive an upper bound on the size of any list-decodable
code for the Z-channel. At a high level, the proof follows the idea of Elias
and Bassalygo [Bas65]. The idea is to _cover_ the space where the code is
living using Hamming balls333In fact, it is more convenient for us to consider
sets that are slightly more structured than Hamming balls which will be
specified in the proceeding proof.. The radius of the balls is carefully
chosen so that there can only be a _constant_ number of codewords in the each
ball satisfying the list-decodability condition. Then the total number of
codewords is bounded by the covering number times a constant. We flesh out the
detail below.

We first present a covering lemma that will be useful in the proof of the
upper bound.

######  Lemma 14.

Let $w,v\in(0,1)$ and $\max(0,w+v-1)\leq a\leq\min(w,v)$. Define

$\displaystyle I(w,v,a)$
$\displaystyle\coloneqq(1-w-v+a)\log\frac{1-w-v+a}{(1-w)(1-v)}+(v-a)\log\frac{v-a}{(1-w)v}+(w-a)\log\frac{w-a}{w(1-v)}+a\log\frac{a}{wv}.$

to be the mutual information of the joint distribution
$P_{U,X}\coloneqq\begin{bmatrix}1-w-v+a&v-a\\\ w-a&a\end{bmatrix}$.444Note
that the marginal $P_{X}$ of $P_{U,X}$ is $\mathsf{Ber}(w)$ and the marginal
$P_{U}$ of $P_{U,X}$ is $\mathsf{Ber}(v)$. Then for any $\varepsilon>0$, there
exists a covering $\mathcal{D}\subset S_{nv}^{\mathrm{H}}(\boldsymbol{0})$ of
$S^{\mathrm{H}}_{nw}(\boldsymbol{0})$ satisfying: for any $\boldsymbol{x}\in
S^{\mathrm{H}}_{nw}(\boldsymbol{0})$, there is a
$\boldsymbol{u}\in\mathcal{D}$ such that
$T_{\boldsymbol{u},\boldsymbol{x}}=P_{U,X}$. Furthermore, the size of
$\mathcal{D}$ is at most $2^{n(I(w,v,a)+\varepsilon)}$.

###### Proof.

We will show that with high probability a random subset $\mathcal{D}$ of
$S^{\mathrm{H}}_{nv}(\boldsymbol{0})$ is a covering of
$S^{\mathrm{H}}_{nw}(\boldsymbol{0})$. Indeed, we sample $M\coloneqq
2^{n(I(w,v,a)+\varepsilon)}$ vectors uniformly at random from all weight-$nv$
vectors and call such a set $\mathcal{D}$. The probability that some sequence
$\boldsymbol{x}$ in $S^{\mathrm{H}}_{nw}(\boldsymbol{0})$ is not covered by
any vector in $\mathcal{D}$ can be bounded as follows:

$\displaystyle\Pr\\{\exists\boldsymbol{x}\in
S^{\mathrm{H}}_{nw}(\boldsymbol{0}),\;\forall\boldsymbol{u}\in\mathcal{D},\;T_{\boldsymbol{u},\boldsymbol{x}}\neq
P_{U,X}\\}$ $\displaystyle\leq\sum_{\boldsymbol{x}\in
S^{\mathrm{H}}_{nw}(\boldsymbol{0})}\prod_{\boldsymbol{u}\in\mathcal{D}}(1-\Pr\\{T_{\boldsymbol{u},\boldsymbol{x}}=P_{U,X}\\})$
$\displaystyle=\sum_{\boldsymbol{x}\in
S^{\mathrm{H}}_{nw}(\boldsymbol{0})}\prod_{\boldsymbol{u}\in\mathcal{D}}\left(1-\frac{\binom{n(1-w)}{n(v-a)}\binom{nw}{na}}{\binom{n}{nv}}\right)$
$\displaystyle=\binom{n}{nw}\left(1-2^{n(1-w)H\left(\frac{v-a}{1-w}\right)+nwH\left(\frac{a}{w}\right)-nH(v)+o(n)}\right)^{M}$
$\displaystyle\leq
2^{nH(w)}\left(1-2^{nI(w,v,a)+o(n)}\right)^{2^{nI(w,v,a)}2^{n\varepsilon}}$
$\displaystyle\xrightarrow{n\to\infty}2^{nH(w)}e^{-2^{n\varepsilon}}$ (17)
$\displaystyle=e^{-2^{n\varepsilon}+O_{L}(n)}.$

In Eqn. (17), we used the fact $\lim\limits_{n\to\infty}(1-1/n)^{n}=1/e$.
Therefore, with probability at least $1-e^{-2^{\Omega(n)}}$, $\mathcal{D}$ is
a covering of $S^{\mathrm{H}}_{nw}(\boldsymbol{0})$ w.r.t. $P_{U,X}$. This
finishes the proof of the lemma. ∎

We are now ready to prove the upper bound which reads as follows.

######  Theorem 15.

Fix $0<w<1$. Let $\mathcal{C}$ be a $w$-constant-weight list-decodable code
for the Z-channel of length $n$ with list-decoding radius $\tau$. Then for
$n\to\infty$

$\displaystyle R(\mathcal{C})$
$\displaystyle\leq\min_{\begin{subarray}{c}0\leq v\leq 1,\;\max(0,w+v-1)\leq
a\leq\min(w,v)\\\
(1-v)\left[\frac{w-a}{1-v}-\left(\frac{w-a}{1-v}\right)^{L}\right]+v\left[\frac{a}{v}-\left(\frac{a}{v}\right)^{L}\right]\leq\tau\end{subarray}}I(w,v,a)+o(1),$

where $I(w,v,a)$ was defined in Lemma 14.

###### Proof.

By Lemma 14, for any list-decodable code $\mathcal{C}$ with constant-weight
$nw$, one can find a weight-$nv$ covering $\mathcal{D}$ w.r.t. a joint
distribution $P_{U,X}$ as specified in Lemma 14, where the parameters $v$ and
$a$ are to be optimized later and $\mathcal{D}$ satisfies the properties given
by the lemma.

For each $\boldsymbol{u}\in S^{\mathrm{H}}_{nv}(\boldsymbol{0})$, define the
following _jointly typical set_ $A(\boldsymbol{u},P_{U,X})$ w.r.t. the joint
distribution $P_{U,X}$:

$\displaystyle A(\boldsymbol{u},P_{U,X})$
$\displaystyle\coloneqq\left\\{\boldsymbol{x}\in
S^{\mathrm{H}}_{nw}(\boldsymbol{0}):T_{\boldsymbol{u},\boldsymbol{x}}=P_{U,X}\right\\}.$
(18)

By the covering property of $\mathcal{D}$, we have

$\displaystyle S^{\mathrm{H}}_{nw}(\boldsymbol{0})$
$\displaystyle=\bigcup_{\boldsymbol{u}\in\mathcal{D}}A(\boldsymbol{u},P_{U,X})$
$\displaystyle\implies$ $\displaystyle
S^{\mathrm{H}}_{nw}(\boldsymbol{0})\cap\mathcal{C}$
$\displaystyle=\left(\bigcup_{\boldsymbol{u}\in\mathcal{D}}A(\boldsymbol{u},P_{U,X})\right)\cap\mathcal{C}$
$\displaystyle\implies$ $\displaystyle\mathcal{C}$
$\displaystyle=\bigcup_{\boldsymbol{u}\in\mathcal{D}}(A(\boldsymbol{u},P_{U,X})\cap\mathcal{C})$
$\displaystyle\implies$ $\displaystyle|\mathcal{C}|$
$\displaystyle\leq\sum_{\boldsymbol{u}\in\mathcal{D}}|A(\boldsymbol{u},P_{U,X})\cap\mathcal{C}|.$

For each $\boldsymbol{u}\in\mathcal{D}$, define
$\mathcal{C}_{\boldsymbol{u}}\coloneqq
A(\boldsymbol{u},P_{U,X})\cap\mathcal{C}$. By Markov’s inequality, there must
be a $\boldsymbol{u}^{*}\in\mathcal{D}$ such that
$|\mathcal{C}_{\boldsymbol{u}^{*}}|\geq|\mathcal{C}|/|\mathcal{D}|$. We
further define the punctured subcodes of $\mathcal{C}_{\boldsymbol{u}^{*}}$
w.r.t. $\boldsymbol{u}^{*}$. For $u\in\\{0,1\\}$, let
$\mathcal{C}_{\boldsymbol{u}^{*},u}\coloneqq\\{(x_{i})_{i\in[n],u^{*}_{i}=u}:\boldsymbol{x}\in\mathcal{C}\\}$
be the subcode obtained by restricting codewords in $\mathcal{C}$ to the
coordinates $i$’s where $u^{*}_{i}=u$. Note that
$\mathcal{C}_{\boldsymbol{u}^{*},1}\in\\{0,1\\}^{nv}$ and
$\mathcal{C}_{\boldsymbol{u}^{*},0}\in\\{0,1\\}^{n(1-v)}$.

The punctured subcodes $\mathcal{C}_{\boldsymbol{u}^{*},0}$ and
$\mathcal{C}_{\boldsymbol{u}^{*},1}$ enjoy the following property. For
$u\in\\{0,1\\}$, all codewords in $\mathcal{C}_{\boldsymbol{u}^{*},u}$ have
the same type $P_{X|U=u}$. That is, every codeword in
$\mathcal{C}_{\boldsymbol{u}^{*},0}$ has weight $w-a$ and every codeword in
$\mathcal{C}_{\boldsymbol{u}^{*},1}$ has weight $a$. Clearly,
$|\mathcal{C}_{\boldsymbol{u}^{*}}|\leq|\mathcal{C}_{\boldsymbol{u}^{*},0}|\cdot|\mathcal{C}_{\boldsymbol{u}^{*},1}|$.

Suppose that there are $n\tau_{0}$ errors in the locations $i$’s such that
$u^{*}_{i}=0$ and there are $n\tau_{1}$ errors in the locations $j$’s such
that $u^{*}_{j}=1$. The parameters $\tau_{0}$ and $\tau_{1}$ satisfy
$\tau_{0}+\tau_{1}\leq\tau$. As long as the following two conditions are
satisfied,

$\displaystyle\frac{\tau_{0}}{1-v}$
$\displaystyle>\frac{w-a}{1-v}-\left(\frac{w-a}{1-v}\right)^{L},\quad\frac{\tau_{1}}{v}>\frac{a}{v}-\left(\frac{a}{v}\right)^{L},$

both $|\mathcal{C}_{\boldsymbol{u}^{*},0}|$ and
$|\mathcal{C}_{\boldsymbol{u}^{*},1}|$ are at most a constant (independent of
$n$) by Theorem 6. Specifically, if

$\displaystyle\frac{\tau_{0}}{1-v}=\frac{w-a}{1-v}-\left(\frac{w-a}{1-v}\right)^{L}+\varepsilon,\quad\frac{\tau_{1}}{v}=\frac{a}{v}-\left(\frac{a}{v}\right)^{L}+\varepsilon,$

then

$\displaystyle|\mathcal{C}_{\boldsymbol{u}^{*},0}|$
$\displaystyle\leq\frac{C_{0}}{\varepsilon}+O_{L}(1),\quad|\mathcal{C}_{\boldsymbol{u}^{*},1}|\leq\frac{C_{1}}{\varepsilon}+O_{L}(1),$

where

$\displaystyle C_{0}$
$\displaystyle\coloneqq\left[\frac{w-a}{1-v}-\left(\frac{w-a}{1-v}\right)^{L}\right]\binom{L}{2},\quad
C_{1}\coloneqq\left[\frac{a}{v}-\left(\frac{a}{v}\right)^{L}\right]\binom{L}{2}.$

Therefore

$\displaystyle|\mathcal{C}|$
$\displaystyle\leq|\mathcal{C}_{\boldsymbol{u}^{*}}|\cdot|\mathcal{D}|\leq|\mathcal{C}_{\boldsymbol{u}^{*},0}|\cdot|\mathcal{C}_{\boldsymbol{u}^{*},1}|\cdot|\mathcal{D}|\leq\left(\frac{C_{0}}{\varepsilon}+O_{L}(1)\right)\cdot\left(\frac{C_{1}}{\varepsilon}+O_{L}(1)\right)\cdot
2^{n(I(w,v,a)+\varepsilon)},$

and $R(\mathcal{C})\leq I(w,v,a)+\varepsilon+o(1)$. Taking $\varepsilon\to 0$
finishes the proof. ∎

Though not used in the proof of Theorem 15, the upper bound on the size of a
covering given in Lemma 14 is actually tight (on the exponential scale). Such
a converse follows from a simple sphere-covering-type argument as below.

######  Lemma 16.

Let $I(w,v,a)$ and $P_{U,X}$ be as defined in Lemma 14. Then any covering
$\mathcal{D}\subset S_{nv}^{\mathrm{H}}(\boldsymbol{0})$ of
$S_{nw}^{\mathrm{H}}(\boldsymbol{0})$ satisfying the property in Lemma 14 has
size at least $2^{nI(w,v,a)-o(n)}$.

###### Proof.

For any $\boldsymbol{u}\in S_{nv}^{\mathrm{H}}(\boldsymbol{0})$, we first
compute the size of $A(\boldsymbol{u},P_{U,X})$ defined in Eqn. (18).

$\displaystyle|A(\boldsymbol{u},P_{U,X})|$
$\displaystyle=\binom{n(1-v)}{n(w-a)}\binom{nv}{na}\leq
2^{n\left[(1-v)H\left(\frac{w-a}{1-v}\right)+vH\left(\frac{a}{v}\right)\right]}.$

Now, by the covering property of $\mathcal{D}$, we have

$\displaystyle S_{nw}^{\mathrm{H}}(\boldsymbol{0})$
$\displaystyle=\bigcup_{\boldsymbol{u}\in\mathcal{D}}A(\boldsymbol{u},P_{U,X})$
$\displaystyle\implies$ $\displaystyle|S_{nw}^{\mathrm{H}}(\boldsymbol{0})|$
$\displaystyle\leq\sum_{\boldsymbol{u}\in\mathcal{D}}|A(\boldsymbol{u},P_{U,X})|$
$\displaystyle\implies$ $\displaystyle 2^{nH(w)-o(n)}$
$\displaystyle\leq|\mathcal{D}|2^{n\left[(1-v)H\left(\frac{w-a}{1-v}\right)+vH\left(\frac{a}{v}\right)\right]}$
$\displaystyle\implies$ $\displaystyle|\mathcal{D}|$ $\displaystyle\geq
2^{n\left[H(w)-(1-v)H\left(\frac{w-a}{1-v}\right)-vH\left(\frac{a}{v}\right)\right]-o(n)}=2^{nI(w,v,a)-o(n)}.\qed$
(19)

###  6.2 Lower bound on $(L-1)$-list-decoding capacity

In this section, our goal is to construct an $(L-1)$-list-decodable code
$\mathcal{C}\subset\\{0,1\\}^{n}$ for a Z-channel with noise level $\tau$. We
would like to obtain a lower bound on the rate $R(\mathcal{C})$ that can be
achieved by such a $\mathcal{C}$.

Before deriving the bound, we first introduce a set of distributions that will
play an important role in the proceeding analysis. For any $w\in[0,1]$ and
$\tau\in[0,w]$, define the following set of distributions:

$\displaystyle\mathcal{K}(w,\tau)$
$\displaystyle\coloneqq\left\\{P_{X_{1},\cdots,X_{L}}\in\mathcal{P}(\\{0,1\\}^{L}):\begin{array}[]{l}\forall
i\in[L],\;P_{X_{i}}(1)=w\\\
w-P_{X_{1},\cdots,X_{L}}(1,\cdots,1)\leq\tau\end{array}\right\\}.$ (22)

In words, $\mathcal{K}(w,\tau)$ is the collection of distributions
$P_{X_{1},\cdots,X_{L}}$ on length-$L$ binary strings satisfying: $(i)$ each
of its marginal $P_{X_{i}}$ (for $1\leq i\leq L$) is $\mathsf{Ber}(w)$; $(ii)$
the probability mass $P_{X_{1},\cdots,X_{L}}(1,\cdots,1)$ on the all-one
string is at least $w-\tau$.

We now describe our construction and analyze it. Our approach follows the
standard random coding with expurgation technique. We sample a codebook
$\mathcal{C}\in\\{0,1\\}^{M\times n}$ each entry of which is i.i.d. according
to $\mathsf{Ber}(w)$.

First, we claim that in expectation a $1/\mathrm{poly}(n)$ fraction of the
codewords have weight exactly $nw$. To see this, note that for any
$\boldsymbol{x}\in\mathcal{C}$,

$\displaystyle\Pr\\{\textrm{wt}(\boldsymbol{x})=nw\\}$
$\displaystyle=\binom{n}{nw}w^{nw}(1-w)^{n(1-w)}$
$\displaystyle=\frac{\sqrt{2\pi n}(n/e)^{n}}{\sqrt{2\pi
nw}(nw/e)^{nw}\sqrt{2\pi(1-w)}(n(1-w)/e)^{n(1-w)}}(1-O_{L}(n^{-1}))w^{nw}(1-w)^{n(1-w)}$
$\displaystyle=\frac{1}{\sqrt{2\pi nw(1-w)}}(1-O_{L}(n^{-1})),$

where the second step is by Stirling’s approximation $n!=\sqrt{2\pi
n}(n/e)^{n}(1+O_{L}(n^{-1}))$. Therefore,

$\displaystyle\mathbf{E}|\\{\boldsymbol{x}\in\mathcal{C}:\textrm{wt}(\boldsymbol{x})=nw\\}|$
$\displaystyle=\frac{M}{\sqrt{2\pi nw(1-w)}}(1-O_{L}(n^{-1})).$

Second, we compute the expected number of _bad_ $L$-lists, i.e., those
$L$-lists whose list-decoding radius is at most $n\tau$. For any list
$\mathcal{L}\in\binom{\mathcal{C}}{L}$ of codewords all of weight $nw$, it is
clear that $\mathrm{rad}(\mathcal{L})\leq n\tau$ (where
$\mathrm{rad}(\mathcal{L})$ was defined in Eqn. (6)) if and only if the joint
type $T_{\mathcal{L}}$ of $\mathcal{L}$ is in $\mathcal{K}(w,\tau)$. By
Sanov’s theorem (Theorem 13),

$\displaystyle-\frac{1}{n}\log\Pr\\{\mathrm{rad}(\mathcal{L})\leq n\tau\\}$
$\displaystyle=-\frac{1}{n}\log\Pr\\{T_{\mathcal{L}}\in\mathcal{K}(w,\tau)\\}$
$\displaystyle\xrightarrow{n\to\infty}\min_{P_{X_{1},\cdots,X_{L}}\in\mathcal{K}(w,\tau)}D\left(P_{X_{1},\cdots,X_{L}}\middle\|\mathsf{Ber}^{\otimes
L}(w)\right)\eqqcolon E(w,\tau).$

Therefore, for sufficiently large $n$, we have

$\displaystyle\mathbf{E}\left|\left\\{\mathcal{L}\in\binom{\mathcal{C}}{L}:\mathrm{rad}(\mathcal{L})\leq
n\tau\right\\}\right|$ $\displaystyle=\binom{M}{L}2^{-nE(w,\tau)(1-o(1))}.$

Finally, we expurgate all codewords whose weights are not exactly $nw$; we
also expurgate one codeword from each of the _bad_ $L$-lists $\mathcal{L}$,
i.e., those $\mathcal{L}$ such that $\mathrm{rad}(\mathcal{L})\leq n\tau$. If

$\displaystyle\binom{M}{L}2^{-nE(w,\tau)(1-o(1))}$
$\displaystyle\leq\frac{M}{2\sqrt{2\pi nw(1-w)}}(1-O_{L}(n^{-1}))$
$\displaystyle\impliedby$ $\displaystyle M^{L}2^{-nE(w,\tau)(1-o(1))}$
$\displaystyle\leq\frac{M}{2\sqrt{2\pi nw(1-w)}}(1-O_{L}(n^{-1}))$
$\displaystyle\impliedby$ $\displaystyle RL-E(w,\tau)(1-o(1))$
$\displaystyle\leq R(1-o(1))$ $\displaystyle\impliedby$ $\displaystyle R$
$\displaystyle\leq\frac{E(w,\tau)}{L-1}(1-o(1)),$

then after expurgation, we are left with at least $\frac{M}{2\sqrt{2\pi
nw(1-w)}}(1-O(n^{-1}))$ codewords which form an $(L-1)$-list-decodable code
$\mathcal{C}^{\prime}\subset\mathcal{C}$. Note that the rate
$R(\mathcal{C}^{\prime})$ is asymptotically equal to $R(\mathcal{C})$.

Therefore, we have proved the following theorem.

######  Theorem 17.

There exist $w$-constant-weight $(L-1)$-list-decodable codes for the Z-channel
with list-decoding radius $\tau<\tau_{L}(w)$ of rate at least

$\displaystyle\frac{1}{L-1}\min_{P_{X_{1},\cdots,X_{L}}\in\mathcal{K}(w,\tau)}D\left(P_{X_{1},\cdots,X_{L}}\middle\|\mathsf{Ber}^{\otimes
L}(w)\right),$

where $\mathcal{K}(w,\tau)$ was defined in Eqn. 22.

###  6.3 List-decoding capacity

Obtaining the exact $(L-1)$-list-decoding capacity for the Z-channel is a
difficult question and we are only able to derive nonmatching upper and lower
bounds in Sec. 6.1 and 6.2 respectively. Nevertheless, we can compute the
list-decoding capacity $C_{L-1}(w,\tau)$ when $L$ is sufficiently large.
Specifically, we determine the limit $\lim\limits_{L\to\infty}C_{L-1}(w,\tau)$
using the following two lemmas. The proofs below follow the outline that one
uses to prove the standard list-decoding capacity theorem for symmetric
errors.

Define

$\displaystyle C_{\mathrm{LD}}(w,\tau)$
$\displaystyle\coloneqq-(1-w+\tau)\log(1-w+\tau)+\tau\log\tau-w\log w.$ (23)

Note that for any fixed $w$, $C_{\mathrm{LD}}(w,\tau)$ is convex and
decreasing in $\tau$. It attains its maximum value $H(w)$ at $\tau=0$ and
attains its minimum value $0$ at $\tau=w$. Furthermore,
$C_{\mathrm{LD}}(w,\tau)$ is concave in $w$ and attains its maximum value at
$w=\frac{1+\tau}{2}$ for any fixed $\tau$. The corresponding maximum value is
$C_{\mathrm{LD}}(\tau)\coloneqq-(1+\tau)\log\frac{1+\tau}{2}+\tau\log\tau$
which is in turn convex and decreasing with maximum value $1$ at $\tau=0$ and
minimum value $0$ at $\tau=1$.

######  Lemma 18 (Upper bound).

For any $\delta\in(0,1)$, any $w$-constant-weight code of rate
$C_{\mathrm{LD}}(w,\tau)+\delta$ for the Z-channel with error fraction $\tau$
is not $(L-1)$-list-decodable for any $L<2^{n\delta+o(n)}$.

###### Proof.

Let $\mathcal{C}$ be any $w$-constant-weight code of rate
$C_{\mathrm{LD}}(w,\tau)+\delta$. To show non-list-decodability, we need to
exhibit a _bad_ center $\boldsymbol{y}$ such that the Z-ball around
$\boldsymbol{y}$ of radius $n\tau$ contains at least $2^{n\delta+o(n)}$
codewords from $\mathcal{C}$. Indeed, we will show that a random
$\boldsymbol{y}$ has such a property. Specifically, let $\boldsymbol{y}$ be
uniformly distributed among all vectors of weight $n(w-p)$. We compute the
expected number of codewords in $B^{\mathrm{Z}}_{n\tau}(\boldsymbol{y})$.

$\displaystyle\mathbf{E}|B^{\mathrm{Z}}_{n\tau}(\boldsymbol{y})\cap\mathcal{C}|$
$\displaystyle=\sum_{\boldsymbol{x}\in\mathcal{C}}\Pr\\{B^{\mathrm{Z}}_{n\tau}(\boldsymbol{y})\ni\boldsymbol{x}\\}$
$\displaystyle=\sum_{\boldsymbol{x}\in\mathcal{C}}\Pr\\{\mathrm{supp}(\boldsymbol{y})\subseteq\mathrm{supp}(\boldsymbol{x})\\}$
$\displaystyle=\sum_{\boldsymbol{x}\in\mathcal{C}}\frac{\binom{nw}{n(w-p)}}{\binom{n}{n(w-p)}}$
$\displaystyle=2^{nC_{\mathrm{LD}}(w,\tau)+n\delta}2^{n\left(wH\left(\frac{w-p}{w}\right)-H(w-p)\right)+o(n)}$
$\displaystyle=2^{n\delta+o(n)}.$

This finishes the proof. ∎

######  Lemma 19 (Construction).

For any $\delta\in(0,1)$ and any $L>1/\delta$, there exist $(L-1)$-list-
decodable codes for the Z-channel with error fraction $\tau$ of rate
$C_{\mathrm{LD}}(w,\tau)-\delta$.

###### Proof.

First note that if $\tau\geq w$, the capacity is trivially zero under any
constant list size since the channel can zero out all bits in any codeword and
the list size has to be as large as the code size. In the proof we therefore
assume $\tau<w$.

Let $\mathcal{C}\subset\\{0,1\\}^{n}$ be a collection of $M\coloneqq 2^{nR}$
(where $R=C_{\mathrm{LD}}(w,\tau)-\delta$) random vectors
$\boldsymbol{x}_{1},\cdots,\boldsymbol{x}_{M}$ each of which is i.i.d. chosen
from the set of all weight-$nw$ binary vectors. If a codeword
$\boldsymbol{x}\in\mathcal{C}$ is input to the channel, the weight of the
output vector $\boldsymbol{y}\in\\{0,1\\}^{n}$ is in the range
$[n(w-\tau),nw]$. A vector $\boldsymbol{y}\in\\{0,1\\}^{n}$ of weight in
$[n(w-\tau),nw]$ can result from $\boldsymbol{x}\in\mathcal{C}$ through the
channel if and only if
$\mathrm{supp}(\boldsymbol{y})\subset\mathrm{supp}(\boldsymbol{x})$. We
compute the probability that this happens to a random codeword
$\boldsymbol{x}\in\mathcal{C}$. For any fixed $\boldsymbol{y}\in\\{0,1\\}^{n}$
of weight $nu$ where $u\in[w-\tau,w]$, we have

$\displaystyle\Pr\\{\mathrm{supp}(\boldsymbol{y})\subseteq\mathrm{supp}(\boldsymbol{x})\\}$
$\displaystyle=\frac{\binom{n(1-u)}{n(w-u)}}{\binom{n}{nw}}\leq
2^{n(1-u)H\left(\frac{w-u}{1-u}\right)-nH(w)+o(n)}.$

Therefore, the probability that such a random code $\mathcal{C}$ is not
$(L-1)$-list-decodable is:

$\displaystyle\Pr\\{\mathcal{C}\text{ is not $(L-1)$-list-decodable}\\}$
$\displaystyle\leq\Pr\left\\{\exists\\{i_{1},\cdots,i_{L}\\}\in\binom{[M]}{L},\;\exists\boldsymbol{y}\in\\{0,1\\}^{n},\;\mathrm{s.t.}\;\textrm{wt}(\boldsymbol{y})\in[n(w-\tau),nw];\;\forall
j\in[L],\;\mathrm{supp}(\boldsymbol{y})\subseteq\mathrm{supp}(\boldsymbol{x}_{i_{j}})\right\\}$
$\displaystyle\leq\binom{M}{L}2^{n}\max_{w-\tau\leq u\leq
w}\left(2^{n(1-u)H\left(\frac{w-u}{1-u}\right)-nH(w)+o(n)}\right)^{L}$
$\displaystyle\leq\max_{w-\tau\leq u\leq
w}2^{nRL+n+nL\left[(1-u)H\left(\frac{w-u}{1-u}\right)-H(w)+o(1)\right]}$
$\displaystyle\leq
2^{n\left[RL+1+L\left((1-w+\tau)H\left(\frac{\tau}{1-w+\tau}\right)-H(w)+o(1)\right)\right]}.$
(24)

The last inequality follows since the function
$f_{w}(u)\coloneqq(1-u)H\left(\frac{w-u}{1-u}\right)$ has the following
property. For any fixed $w$, $f_{w}(u)$ is concave and decreasing in
$u\in[0,w]$, and therefore in the domain $u\in[w-\tau,w]$ it attains its
maximum at $u=w-\tau$.

By elementary algebraic manipulation, we have

$\displaystyle(1-w+\tau)H\left(\frac{\tau}{1-w+\tau}\right)-H(w)=-C_{\mathrm{LD}}(w,\tau).$

Recall $R=C_{\mathrm{LD}}(w,\tau)-\delta$. Then the exponent (normalized by
$n^{-1}$) of the RHS of the inequality (24) equals

$\displaystyle(C_{\mathrm{LD}}(w,\tau)-\delta)L+1-C_{\mathrm{LD}}(w,\tau)L+o(1)=-\delta
L+1+o(1),$

which is negative if $L>1/\delta+o(1)$. That is, the probability that
$\mathcal{C}$ is $(L-1)$-list-decodable is at least $1-2^{-\Omega(n)}$ for any
$L>1/\delta+o(1)$. ∎

Lemma 18 and 19 imply the following characterization.

######  Theorem 20 (List-decoding capacity).

The $(L-1)$-list-decoding capacity of the Z-channel with error fraction $\tau$
under input constraint $w$ is given by
$\lim\limits_{L\to\infty}C_{L-1}(w,\tau)=C_{\mathrm{LD}}(w,\tau)$ as defined
in Eqn. (23).

##  7 Capacity of stochastic Z-channels

In all other sections of this paper, we considered Z-channels with
_adversarial_ errors. In this section, we derive the capacity of _stochastic_
Z-channels from Shannon’s seminal channel coding theorem.

To this end, we first state Shannon’s theorem for general discrete memoryless
channels (DMCs). Let $\mathcal{X}$ and $\mathcal{Y}$ be two finite sets
denoting the input and output alphabets of the channel. A DMC is a stochastic
matrix $W_{Y|X}$ that maps a distribution over $\mathcal{X}$ to a distribution
over $\mathcal{Y}$. When the channel is used $n$ times with an input sequence
$\boldsymbol{x}\in\mathcal{X}^{n}$, the output sequence
$\boldsymbol{y}\in\mathcal{Y}^{n}$ follows a product law:

$\displaystyle\Pr\\{\boldsymbol{y}=(b_{1},\cdots,b_{n})|\boldsymbol{x}=(a_{1},\cdots,a_{n})\\}$
$\displaystyle=\prod_{i=1}^{n}W_{Y|X}(b_{i}|a_{i}),$

for any $(a_{1},\cdots,a_{n})\in\mathcal{X}^{n}$ and
$(b_{1},\cdots,b_{n})\in\mathcal{Y}^{n}$.

The DMC is said to be equipped with input constraints
$\mathcal{Q}\subset\mathcal{P}(\mathcal{X})$ if the type $T_{\boldsymbol{x}}$
of any input sequence $\boldsymbol{x}\in\mathcal{C}$ is required to belong to
$\mathcal{Q}$.

######  Theorem 21 (Channel coding theorem [Sha48]).

The capacity $C(W_{Y|X})$ of a DMC
$W_{Y|X}\in\mathcal{P}(\mathcal{Y}|\mathcal{X})$ with input constraints
$\mathcal{Q}$ is given by

$\displaystyle C(W_{Y|X})$ $\displaystyle=\max_{P_{X}\in\mathcal{Q}}I(X;Y),$
(25)

where the mutual information is evaluated w.r.t. the joint law $P_{X}W_{Y|X}$.

A discrete memoryless Z-channel is defined as follows. Both the input and
output alphabets are binary: $\mathcal{X}=\mathcal{Y}=\\{0,1\\}$. The channel
transition law is parameterized by the zeroing-out probability $\tau$, i.e.,
$W^{\mathrm{Z}}_{Y|X}(0|0)=1,W^{\mathrm{Z}}_{Y|X}(0|1)=\tau$. The input
constraint is such that all input sequences should have Hamming weight at most
$nw$ for some $w\in[0,1]$. It is easy to evaluate Eqn. (25) which yields
$C(W^{\mathrm{Z}}_{Y|X})=C(w,\tau)=H(w(1-\tau))-wH(\tau)$.

We note that for any fixed $w\in[0,1]$, $C(w,\tau)$ is convex and decreasing
in $\tau$. It attains its maximum value $H(w)$ at $\tau=0$ and attains its
minimum value $0$ at $\tau=1$.

We also note that $C(w,\tau)$ is concave in $w$ for any fixed $\tau$. The
maximizing $w$ is given by

$\displaystyle w_{\max}$
$\displaystyle\coloneqq\left(1-\tau+\tau^{-\frac{\tau}{1-\tau}}\right)^{-1},$

and the corresponding capacity $C(\tau)\coloneqq
H(w_{\max}(1-\tau))-w_{\max}H(\tau)$ is convex and decreasing with maximum
value $1$ at $\tau=0$ and minimum value $0$ at $\tau=1$.

For symmetric (a.k.a. bitflip) errors and erasures, it happens that the
capacity of binary symmetric channels and binary erasure channels coincide
with the respective list-decoding capacity (under adversarial errors).
Comparing the expressions of $C(w,\tau)$ and $C_{\mathrm{LD}}(w,\tau)$, we see
that this is no longer true for Z-channels.

##  8 Open problems

  1. 1.

For codes correcting symmetric (a.k.a. bitflip) errors, the Elias–Bassalygo
bound can be improved using Delsarte’s linear program [MRRW77]. We do not know
how to derive a linear programming-type bound for Z-channels. As far as we
know, the linear programming framework, in its most general form, assumes that
the ambient space that the code lives in (which is $\\{0,1\\}^{n}$ for general
codes and $S_{nw}^{\mathrm{H}}(\boldsymbol{0})$ for $w$-constant-weight codes)
can be defined as an _association scheme_. We do not see how to do so under
the Z-metric $d_{Z}(\cdot,\cdot)$ since the volume of the intersection of two
Z-spheres is not invariant under shifts.

  2. 2.

The largest code size is exponential in $n$ if the fraction of asymmetric
errors the list-decodable code can correct is less than the Plotkin point
$\tau_{L}$ and we gave bounds on the exponent in Sec. 6.1 and 6.2; whereas it
is $\Theta_{L}(\varepsilon^{-3/2})$ if the fraction of errors is
$\varepsilon$-above $\tau_{L}$. There is one missing case which we did not
solve, that is, what is the largest code size with error fraction being
_exactly_ $\tau_{L}$? We conjecture that in this case the answer is
$\Theta_{L}(n^{3/2})$. Note that the answer to the same question for symmetric
errors is $2n$ proved by a geometric argument.

## References

  * [ABP18] Noga Alon, Boris Bukh, and Yury Polyanskiy.  List-decodable zero-rate codes.  IEEE Transactions on Information Theory, 65(3):1657–1667, 2018\.
  * [Bas65] Leonid Alexandrovich Bassalygo.  New upper bounds for error correcting codes.  Problemy Peredachi Informatsii, 1(4):41–44, 1965.
  * [BC93] Bella Bose and Steve Cunningham.  Asymmetric error correcting codes.  In Sequences II, pages 24–35. Springer, 1993.
  * [Bli86] Volodia M Blinovsky.  Bounds for codes in the case of list decoding of finite volume.  Problems of Information Transmission, 22(1):7–19, 1986.
  * [Bor83] J Borden.  A low-rate bound for asymmetric error-correcting codes (corresp.).  IEEE Transactions on Information Theory, 29(4):600–602, 1983.
  * [FLX03] Fang-Wei Fu, San Ling, and Chaoping Xing.  New lower bounds and constructions for binary codes correcting asymmetric errors.  IEEE Transactions on Information Theory, 49(12):3294–3299, 2003\.
  * [KF59] Wan Kim and C Freiman.  Single error-correcting codes for asymmetric binary channels.  IRE Transactions on Information Theory, 5(2):62–66, 1959.
  * [Klo81a] T Klove.  Upper bounds on codes correcting asymmetric errors (corresp.).  IEEE Transactions on Information Theory, 27(1):128–131, 1981.
  * [Klø81b] Torleiv Kløve.  Error correcting codes for the asymmetric channel.  Department of Pure Mathematics, University of Bergen, 1981.
  * [Lev61] VI Levenshtein.  Application of hadamard matrices on coding problem.  Problems of Cybernetica, 5:123–136, 1961.
  * [LLP20] Alexey Lebedev, Vladimir Lebedev, and Nikita Polyanskii.  Two-stage coding over the z-channel.  arXiv, 2020.
  * [LLP22] Alexey Lebedev, Vladimir Lebedev, and Nikita Polyanskii.  Two-stage coding over the Z-channel.  to appear in IEEE Transactions on Information Theory, 2022.
  * [LMC18] Hsuan-Yin Lin, Stefan M Moser, and Po-Ning Chen.  Weak flip codes and their optimality on the binary erasure channel.  IEEE Transactions on Information Theory, 64(7):5191–5218, 2018\.
  * [MRRW77] Robert McEliece, Eugene Rodemich, Howard Rumsey, and Lloyd Welch.  New upper bounds on the rate of a code via the delsarte-macwilliams inequalities.  IEEE Transactions on Information Theory, 23(2):157–166, 1977.
  * [Plo60] Morris Plotkin.  Binary codes with specified minimum distance.  IRE Transactions on Information Theory, 6(4):445–450, 1960.
  * [San58] Ivan N Sanov.  On the probability of large deviations of random variables.  United States Air Force, Office of Scientific Research, 1958.
  * [Sha48] Claude E Shannon.  A mathematical theory of communication.  The Bell system technical journal, 27(3):379–423, 1948.
  * [Var65] Rom Rubenovich Varshamov.  On the theory of asymmetric codes.  In Doklady Akademii Nauk, volume 164, pages 757–760. Russian Academy of Sciences, 1965.
  * [ZBJ20] Yihan Zhang, Amitalok J Budkuley, and Sidharth Jaggi.  Generalized list decoding.  In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [ZF19] Jun Zhang and Fang-Wei Fu.  A construction of vh-sequences and its application to binary asymmetric error-correcting codes.  Finite Fields and Their Applications, 55:216–230, 2019.