# Tight Bounds on List-Decodable and List-Recoverable
Zero-Rate Codes

Nicolas Resch University of Amsterdam. Email<EMAIL_ADDRESS>Chen Yuan
Shanghai Jiao Tong University. Email<EMAIL_ADDRESS>Yihan Zhang
Institute of Science and Technology Austria. Email<EMAIL_ADDRESS>
###### Abstract

In this work, we consider the list-decodability and list-recoverability of
codes in the _zero-rate regime_. Briefly, a code
${\mathcal{C}}\subseteq[q]^{n}$ is $(p,\ell,L)$-list-recoverable if for all
tuples of input lists $(Y_{1},\dots,Y_{n})$ with each $Y_{i}\subseteq[q]$ and
$|Y_{i}|=\ell$ the number of codewords $c\in{\mathcal{C}}$ such that
$c_{i}\notin Y_{i}$ for at most $pn$ choices of $i\in[n]$ is less than $L$;
list-decoding is the special case of $\ell=1$. In recent work by Resch, Yuan
and Zhang (ICALP 2023) the zero-rate threshold for list-recovery was
determined for all parameters: that is, the work explicitly computes
$p_{*}:=p_{*}(q,\ell,L)$ with the property that for all $\varepsilon>0$ (a)
there exist infinite families positive-rate $(p_{*}-\varepsilon,\ell,L)$-list-
recoverable codes, and (b) any $(p_{*}+\varepsilon,\ell,L)$-list-recoverable
code has rate $0$. In fact, in the latter case the code has _constant_ size,
independent on $n$. However, the constant size in their work is quite large in
$1/\varepsilon$, at least
$|{\mathcal{C}}|\geq(\frac{1}{\varepsilon})^{O(q^{L})}$.

Our contribution in this work is to show that for all choices of $q,\ell$ and
$L$ with $q\geq 3$, any $(p_{*}+\varepsilon,\ell,L)$-list-recoverable code
must have size $O_{q,\ell,L}(1/\varepsilon)$, and furthermore this upper bound
is complemented by a matching lower bound $\Omega_{q,\ell,L}(1/\varepsilon)$.
This greatly generalizes work by Alon, Bukh and Polyanskiy (IEEE Trans. Inf.
Theory 2018) which focused only on the case of binary alphabet (and thus
necessarily only list-decoding). We remark that we can in fact recover the
same result for $q=2$ and even $L$, as obtained by Alon, Bukh and Polyanskiy:
we thus strictly generalize their work.

Our main technical contribution is to (a) properly define a linear programming
relaxation of the list-recovery condition over large alphabets; and (b) to
demonstrate that a certain function defined on a $q$-ary probability simplex
is maximized by the uniform distribution. This represents the core challenge
in generalizing to larger $q$ (as a $2$-ary simplex can be naturally
identified with a one-dimensional interval). We can subsequently re-utilize
certain Schur convexity and convexity properties established for a related
function by Resch, Yuan and Zhang along with ideas of Alon, Bukh and
Polyanskiy.

###### Contents

  1. 1 Introduction
    1. 1.1 Our results.
    2. 1.2 Technical Overview
    3. 1.3 Organization
  2. 2 Preliminaries
    1. 2.1 List-Decoding
    2. 2.2 List-Recovery
    3. 2.3 Types of Vector Tuples
  3. 3 Zero-Rate List-Decoding
    1. 3.1 Linear Programming Relaxation
    2. 3.2 Properties of $f(P,\omega)$
    3. 3.3 Abundance of Random-Like $L$-tuples
    4. 3.4 Putting Everything Together
  4. 4 Zero-Rate List-Recovery
    1. 4.1 Linear Programming Relaxation
    2. 4.2 Properties of $f_{\ell}(P,\omega)$
    3. 4.3 Abundance of Random-Like $L$-tuples
    4. 4.4 Putting Everything Together
  5. 5 Code Construction
  6. 6 Conclusion
  7. A Auxiliary lemmas

##  1 Introduction

Given an error-correcting code $\mathcal{C}\subseteq[q]^{n}$, a fundamental
requirement is that the codewords are sufficiently well-spread in order to
guarantee some non-trivial correctability properties. This is typically
enforced by requiring that the minimum distance of the code
$d=\min\\{d_{\mathrm{H}}(\boldsymbol{c},\boldsymbol{c}^{\prime}):\boldsymbol{c}\neq\boldsymbol{c}^{\prime}\in\mathcal{C}\\}$,
where $d_{\mathrm{H}}(\cdot,\cdot)$ denotes the Hamming distance (i.e. the
number of coordinates on which two strings differ). Note that minimum distance
$d$ is equivalent to the following “packing” property: if we put a ball of
radius $r:=\lfloor d/2\rfloor$ around any point $\boldsymbol{z}\in[q]^{n}$ –
i.e. we consider the Hamming ball
$\mathcal{B}_{\mathrm{H}}(\boldsymbol{y},r):=\\{\boldsymbol{x}\in[q]^{n}:d_{\mathrm{H}}(\boldsymbol{x},\boldsymbol{y})\leq
r\\}$ – then all these balls contain at most 1 codeword from $\mathcal{C}$.

This latter viewpoint can easily be generalized to obtain _list-decodability_
, where we now require that such Hamming balls do not capture “too many”
codewords. That is, for $p\in[0,1]$ and $L\in{\mathbb{N}}$ a code is called
$(p,L)$_-list-decodable_ if every Hamming ball of radius $pn$ contains less
than $L$ codewords from $\mathcal{C}$. In notation: for all
${\boldsymbol{y}}\in[q]^{n}$,
$|\mathcal{B}_{\mathrm{H}}({\boldsymbol{y}},pn)|\leq L-1$.111Typically the
upper bound is $L$, rather than $L-1$. However, for “impossibility” arguments
this parametrization is more common, as it leads to less cumbersome
computations. This notion was already introduced in the 50’s by Elias and
Wozencraft [Eli57, Woz58, Eli91] but has in the past 20 years seen quite a bit
of attention due to its connections to other parts of theoretical computer
science [GL89, BFNW93, Lip90, KM93, Jac97, STV01].

One can push this generalization further to obtain _list-recoverability_.
Here, we consider a tuple of input lists
${\boldsymbol{Y}}=(Y_{1},\dots,Y_{n})$, where each $Y_{i}\subseteq[q]$ has
size at most $\ell$ (for some $\ell\in{\mathbb{N}}$). The requirement is that
the number of codewords that “disagree” with ${\boldsymbol{Y}}$ in at most
$pn$ coordinates is at most $L-1$. More formally, if for all
${\boldsymbol{Y}}=(Y_{1},\dots,Y_{n})$ the number of codewords
${\boldsymbol{c}}\in{\mathcal{C}}$ such that $|\\{i\in[n]:c_{i}\notin
Y_{i}\\}|\leq pn$ is at most $L-1$, the code is called $(p,\ell,L)$_-list-
recoverable_. Note that $(p,L)$-list-decodability is nothing other than
$(p,1,L)$-list-recoverability. Initially, list-recoverability was abstracted
as a useful stepping stone towards list-decoding concatenated codes. However,
in recent years this notion has found many connections to other parts of
computer, e.g. in cryptography [HIOS15, HLR21], randomness extraction [GUV09],
hardness amplification [DMOZ20], group testing [INR10, NPR11], streaming
algorithms [DW22], and beyond.

#### Rate versus noise-resilience.

Having fixed a desired “error-tolerance” as determined by the parameters
$p,\ell$ and $L$ we would also like the code $\mathcal{C}$ to be as large as
possible: intuitively, this implies that the code contains the minimal amount
of redundancy possible. A fundamental question in coding theory is to
understand the achievable tradeoffs between the rate
$R:=\frac{\log_{q}|\mathcal{C}|}{n}$ and some “error-resilience” property of
the code, e.g., minimum distance, list-decodability, or list-recoverability.

This question in full generality is wide open. Even for the special case of
$q=2$ and $L=2$ (i.e. determining the optimal tradeoff between rate and
distance for binary codes) is unclear: on the possibility side we have the
Gilbert-Varshamov bound [Gil52, Var57] showing $R\geq 1-H_{2}(p/2)$ is
achievable (here, $H_{2}(x)=-x\log_{2}x-(1-x)\log_{2}(1-x)$ is the binary
entropy function), while bounds of Elias and Bassalygo [Bas65] and the linear
programming bound [WMR74, MRRW77, Del73] give incomparable and non-tight upper
bounds. None of these bounds have been substantially improved in at least 40
years. The situation is even more complicated for larger $q$: for $q=49$ (and
larger prime powers) the celebrated algebraic geometry codes of Tsafsman,
Vladut and Zink [TVZ82] provide explicit codes of higher rate in certain
regimes than those promised by the Gilbert-Varshamov bound.

When one relaxes the question to allow an asymptotically growing list size $L$
then we do have a satisfactory answer: the answer is provided by the list-
decoding/-recovery theorem, which states that for all $\varepsilon>0$ there
exist $(p,\ell,O(1/\varepsilon))$-list-recoverable codes of rate
$1-H_{q,\ell}(p)$ where

$H_{q,\ell}(x):=p\log_{q}\left(\frac{q-\ell}{p}\right)+(1-p)\log_{q}\left(\frac{\ell}{1-p}\right)$

is $(q,\ell)$-ary entropy function [Res20].222Note that setting $\ell=1$
recovers the standard $q$-ary entropy function, which itself reduces to the
binary entropy function upon setting $q=2$. On the other hand, any code of
rate $R\geq 1-h_{q,\ell}(p)$ fails to be $(p,\ell,L)$-list-recoverable unless
$L\geq q^{\Omega(\varepsilon n)}$. However, this does not provide very
meaningful bounds if one is interested in, say, $(p,2,5)$-list-recoverable
codes.

#### Positive versus zero-rate regimes.

Thus far, we have implicitly been discussing the _positive-rate regime_.
However, one can also ask questions about the behaviour of codes in the _zero-
rate regime_. For context, recent work by Resch, Yuan and Zhang [RYZ22]
computed the zero-rate threshold for list-recovery: that is, for all alphabet
sizes $q\geq 2$, input list sizes $\ell$ and output list size $L$, they
determine the value $p_{*}(q,\ell,L)$ such that (a) for all
$p<p_{*}(q,\ell,L)$ there exist infinite families of positive rate
$(p,\ell,L)$-list-recoverable codes over the alphabet $[q]$, and (b) for all
$p>p_{*}(q,\ell,L)$ there does not exist such an infinite family.

Having now delineated the “positive rate” and the “zero-rate” regimes
depending on how $p$ compares to $p_{*}(q,\ell,L)$, in this work we study the
zero-rate regime for list-recoverable codes for all alphabet sizes $q$. In
[RYZ22], it is shown that $(p,\ell,L)$-list-recoverable codes
${\mathcal{C}}\subseteq[q]^{n}$ with $p=p_{*}(q,\ell,L)+\varepsilon$ have
constant size (that is, independent of the block length $n$); however, this
constant is massive in the parameters due to the use of a Ramsey-theoretic
bound. In particular, the dependence on $\varepsilon$ is at least
$(1/\varepsilon)^{2q^{L}}$, and this is additionally multiplied by a tower of
2’s of height roughly $L$.

To the best of our knowledge, prior work on this question focuses exclusively
on the $q=2$ case. For example, in the case of $L=2$ (i.e., unique-decoding)
we have $p_{*}(2,1,2)=1/4$, and work by Levenshtein shows A particularly
relevant prior work is due to Alon, Bukh and Polyanskiy [ABP18]. Herein the
authors consider this question for the special case of $q=2$ (and thus,
necessarily, only for list-decoding). In particular, they show that when $L$
is even if $p=p_{*}(2,1,L)+\varepsilon$ then such a $(p,L)$-list-decodable
code ${\mathcal{C}}\subseteq[2]^{n}$ has size at most $O_{L}(1/\varepsilon)$,
and moreover provide a construction of such a code with size
$\Omega_{L}(1/\varepsilon)$.333Note that for the special case of $q=2$, the
zero-rate threshold for list-decoding had already been established by
Blinovsky [Bli86]. They observe some interesting behaviour in the case of odd
$L$; in particular, the maximum size of a $(p_{*}(2,1,3)+\varepsilon,3)$-list-
decodable code is $\Theta(1/\varepsilon^{3/2})$.444This argument in fact shows
a flaw in an earlier claimed proof of Blinovsky that claimed such codes have
size $O_{L}(1/\varepsilon)$ for all $L\in{\mathbb{N}}$.

Our motivations for this investigation are three-fold. Firstly, the zero-rate
regime offers combinatorial challenges and interesting behaviours that we
uncover in this work. Secondly, many codes that find applications in other
areas of theoretical computer in fact have subconstant rate. Lastly, the zero-
rate regime appears much more tractable than the positive rate regime –
indeed, we can obtain tight upper and lower bounds on the size of a code, as
we will soon see. It would be interesting to determine to what extent such
techniques could be useful for understanding the positive rate regime as well.

###  1.1 Our results.

Our main result in this work is a tight bound on the size of a
$(p,\ell,L)$-list-recoverable code over an alphabet of size $q\geq 3$ when
$p>p_{*}(q,\ell,L)$. The main technical challenge is to compute the following
upper bound on the size of such a code.

######  Theorem 1 (Informal Version of Theorem 25).

Let $q,\ell,L\in{\mathbb{N}}$ with $q\geq 3$. $\ell<q$ and $L>\ell$ be fixed
constants. Let $\varepsilon>0$ and put $p=p_{*}(q,\ell,L)+\varepsilon$.
Suppose ${\mathcal{C}}\subseteq[q]^{n}$ is $(p,\ell,L)$-list-recoverable. Then
$|{\mathcal{C}}|\leq O_{q,\ell,L}(1/\varepsilon)$.

We complement the above negative result with the following code construction,
showing the upper bound is tight.

######  Theorem 2 (Informal Version of Theorem 26).

Let $q,\ell,L\in{\mathbb{N}}$ with $q\geq 3$ and $\ell<q$ be fixed constants.
Let $\varepsilon>0$ and put $p=p_{*}(q,\ell,L)+\varepsilon$. There exists a
$(p,\ell,L)$-list-recoverable code ${\mathcal{C}}\subseteq[q]^{n}$ such that
$|{\mathcal{C}}|\geq\Omega_{q,\ell,L}(1/\varepsilon)$.

We emphasize that in the above theorems the implied constants may depend on
$q,\ell$ and $L$.

Note that our results explicitly _exclude_ the case of $q=2$. As [ABP18]
prove, the binary alphabet behaves in subtle ways: the bound on the code size
depends on the parity of $L$. Intriguingly, our work demonstrates that such
behaviour does not arise over larger alphabets.

###  1.2 Technical Overview

#### The double-counting argument.

Since our focus is on zero-rate list-decodable/-recoverable codes, it helps to
first review the proof of the zero-rate threshold $p_{*}(q,\ell,L)$. A lower
bound can be easily obtained by a random construction that attains a positive
rate for any $p\leq p_{*}(q,\ell,L)-\varepsilon$. For the upper bound, let us
first consider the list-decoding case, i.e., $\ell=1$. The proof in [Bli05,
Bli08, RYZ22], at a high-level, proceeds via a double-counting argument.555A
characterization of $p_{*}(q,1,L)$ was announced in [Bli05, Bli08] whose proof
was flawed. The work [RYZ22] filled in the gaps therein and characterized
$p_{*}(q,\ell,L)$ for general $\ell$. For any $(p,\ell,L)$-list-decodable code
${\mathcal{C}}\subset[q]^{n}$, the proof aims to upper and lower bound the
_radius_ of a list averaged over the choice of the list from ${\mathcal{C}}$:

$\displaystyle\frac{1}{M^{L}}\sum_{({\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L})\in{\mathcal{C}}^{L}}\operatorname{rad}_{\mathrm{H}}({\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L}).$
(1)

Comparing the bounds produces an upper bound on $|{\mathcal{C}}|$. Here
$\operatorname{rad}_{\mathrm{H}}(\cdot)$, known as the Chebyshev radius of a
list, is the relative radius of the smallest Hamming ball containing all
codewords in the list. A lower bound on Equation 1 essentially follows from
list-decodability of ${\mathcal{C}}$. Indeed, each term (corresponding to
lists consisting of distinct codewords) is lower bounded by $p$, otherwise a
list that fits into a ball of radius at most $np$ is found, violating list-
decodability of ${\mathcal{C}}$. Therefore Equation 1 is at least $p-o(1)$,
where $o(1)$ is to account for lists with not-all-distinct codewords.

On the other hand, it is much more tricky to upper bound Equation 1 as, in
general, $\operatorname{rad}_{\mathrm{H}}$ admits no analytically closed form
and can only be computed by solving a min-max problem. Previous proofs [RYZ22]
then first extracts a subcode ${\mathcal{C}}^{\prime}$ with highly-regular
list structures via the hypergraph Ramsey’s theorem. This allows one to assert
that all lists have essentially the same radius and all codewords in each list
have essentially the same distance to the center of the list. As a result, the
min-max expression is “linearized” and Equation 1 can be upper bounded when
restricted to ${\mathcal{C}}^{\prime}$. The downside is that the Ramsey
reduction step is rather lossy for code size.

#### Weighted average radius.

The effect of the Ramsey reduction, put formally, is to enforce the _average
radius_ :

$\displaystyle\overline{\operatorname{rad}}_{\mathrm{H}}({\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L})$
$\displaystyle\coloneqq\frac{1}{n}\min_{{\boldsymbol{r}}\in\\{0,1\\}^{n}}\frac{1}{L}\sum_{i=1}^{L}d_{\mathrm{H}}({\boldsymbol{c}}_{i},{\boldsymbol{r}})$
(2)

of every list in the subcode to be approximately equal. To extract the
regularity structures in lists without resorting to extremal bounds from
Ramsey theory, [ABP18] introduced the notion of _weighted average radius_
which “linearizes” the Chebyshev radius in a _weighted_ manner:

$\displaystyle\overline{\operatorname{rad}}_{\omega}({\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L})$
$\displaystyle\coloneqq\frac{1}{n}\min_{{\boldsymbol{r}}\in\\{0,1\\}^{n}}\sum_{i=1}^{L}\omega(i)d_{\mathrm{H}}({\boldsymbol{c}}_{i},{\boldsymbol{r}})$

where $\omega$ is a distribution on $L$ elements. For any weighting $\omega$,
$\overline{\operatorname{rad}}_{\omega}$ of lists from the code forms a suite
of succinct statistics of the list distribution. It turns out
$\overline{\operatorname{rad}}_{U_{L}}=\overline{\operatorname{rad}}$ (where
$U_{L}$ denotes the uniform distribution on $[L]$) is maximal under all
$\omega$. Recall that the double-counting argument suggests that in an optimal
zero-rate code, the behaviour of the ensemble average of $\operatorname{rad}$
is essentially captured by that of $\overline{\operatorname{rad}}$. In
particular, list-decodability ensures that $\overline{\operatorname{rad}}$ of
_most_ lists should be large. However, not too many lists in an optimal code
are expected to have large $\overline{\operatorname{rad}}_{\omega}$ for any
$\omega\neq U_{L}$. [ABP18] then managed to quantify the gap between
$\overline{\operatorname{rad}}=\overline{\operatorname{rad}}_{U_{L}}$ and
$\overline{\operatorname{rad}}_{\omega}$ (with $\omega\neq U_{L}$), which
yields improved (and sometimes optimal) size-radius trade-off of zero-rate
codes.

#### Generalization to $q$-ary list-decoding.

Our major technical contribution is in extrapolating the above ideas to list-
recovery. The challenge lies particularly in defining a proper notion of
weighted average radius and proving its properties. Our definition relies
crucially on an embedding $\varphi$ from $[q]$ to the simplex in
${\mathbb{R}}^{q}$ and relaxes the center ${\boldsymbol{r}}$ of the list to be
a fractional vector. Specifically, denoting by $\Delta$ the simplex in
${\mathbb{R}}^{q}$ and
$\partial\Delta=\\{{\boldsymbol{e}}_{1},\cdots,{\boldsymbol{e}}_{q}\\}$ its
vertices (i.e., the standard basis of ${\mathbb{R}}^{q}$), we let the
embedding $\varphi$ map each symbol $x\in[q]$ to the one-hot vector
${\boldsymbol{e}}_{x}\in\partial\Delta$. Denoting by
${\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L}\in(\partial\Delta)^{n}$ the
(element-wise) images of a list
${\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L}\in[q]^{n}$, we define the
_weighted average radius_ of
${\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L}$ as:

$\displaystyle\overline{\operatorname{rad}}_{\omega}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})$
$\displaystyle=\frac{1}{n}\min_{{\boldsymbol{y}}\in\Delta^{n}}\frac{1}{2}\mathop{\mathbb{E}}_{i\sim\omega}\left[\left\|{\boldsymbol{x}}_{i}-{\boldsymbol{y}}\right\|_{1}\right],$
(3)

where $\omega$ is any distribution on $[L]$.

The notriviality and significance of the above notion, especially the
embedding used therein, is three-fold.

  * •

First, as the weighting $\omega$ varies,
$\overline{\operatorname{rad}}_{\omega}$ serves as a bridge between the
standard average radius in Equation 2 and the Chebyshev radius. Indeed,
$\omega=U_{L}$ recovers the former, and the maximum
$\overline{\operatorname{rad}}_{\omega}$ over $\omega$ recovers the latter.
However, we caution that the second statement does not hold without the
embedding since the Hamming distance between $q$-ary symbols per se is not and
cannot be interpolated by a convex function, which makes the minimax theorem
inapplicable. Fortunately, our embedding affinely extend the $q$-ary Hamming
distance to the simplex therefore brings back the applicability of the minimax
theorem and connects $\max_{\omega}\overline{\operatorname{rad}}_{\omega}$ to
$\operatorname{rad}$.

  * •

Second, our definition in Equation 3 allows ${\boldsymbol{y}}$ to take any
value on the simplex, instead of only its vertices, i.e., the image of $[q]$
under $\varphi$. Though embedding naively to the hypercube $[0,1]^{q}$ seems
convenient, upon solving the expression with fractional ${\boldsymbol{y}}$ one
does not necessarily obtain a notion that is guaranteed to closely approximate
the original version with integral ${\boldsymbol{y}}$. In contrast, using
linear programming duality, we show that our embedding yields relaxed notion
of radius which closely approximates the actual Chebyshev radius. Indeed, upon
rounding the fractional center ${\boldsymbol{y}}$ and taking its pre-image
under $\varphi$, our results guarantee that the resulting radius must have
negligible difference from the Chebyshev radius. Precisely speaking, we want
to find a vector ${\boldsymbol{y}}=(y(i,j))_{[n]\times[q]}\in\Delta$ close to
the $L$ images of the codewords
${\boldsymbol{x}}_{1},\ldots,{\boldsymbol{x}}_{L}$ by linear programming.
Meanwhile, we want ${\boldsymbol{y}}(i):=(y(i,1),\ldots,y(i,q))$ to belong to
$\partial\Delta$ so that we can find a preimage of ${\boldsymbol{y}}(i)$ in
$[q]$. Since ${\boldsymbol{y}}(i)\in\Delta$, the components in
${\boldsymbol{y}}(i)$ are subject to $\sum_{j=1}^{q}y(i,j)=1$. This implies
that at least one component of ${\boldsymbol{y}}(i)$ is nonzero. The basic
feasible solution in Proposition 27 guarantees that there exists a feasible
solution such that most of $y(i,j)$ are $0$. Combining with the fact
$\sum_{j=1}^{q}y(i,j)=1$ forces $(y(i,1),\ldots,y(i,q))\in\partial\Delta$ for
almost all $i\in[n]$. Thus, we obtain a negligible loss in the conversion
between Hamming distance and Euclidean distance.

  * •

Finally, under the embedding $\varphi$, the weighted average radius
$\overline{\operatorname{rad}}_{\omega}$ still retains the appealing feature
that the minimization can be analytically solved, therefore giving rise to an
explicit expression (see Equation 37) which greatly facilitates our analysis.

We then show, via techniques deviating from those in [ABP18], three key
properties that are required by the subsequent arguments.

  1. 1.

For any fixed distribution $P$, if entries of codewords in the list are
generated i.i.d. using $P$, then

$f(P,\omega)\coloneqq\mathop{\mathbb{E}}_{(X_{1},\cdots,X_{L})\sim P^{\otimes
L}}\left[1-\max_{x\in[q]}\sum_{\begin{subarray}{c}i\in[L]\\\
X_{i}=x\end{subarray}}\omega(i)\right]$

is maximized when $\omega=U_{L}$. Moreover, the equality holds if and only if
$\omega=U_{L}$ for $q\geq 3$ and any $L$. Our approach is different from
[ABP18] as we can not explicitly represent function $f(P,\omega)$.

  2. 2.

Furthermore, if entries of codewords in the list are generated i.i.d. using a
certain $P$, then $f(P,U_{L})$ is upper bounded by $f(P_{q,p},U_{L})$ with
$P_{q,p}=(\frac{1-p}{q},\ldots,\frac{1-p}{q},p)$ and $p=\max_{i\in[q]}P(i)$.
This follows from the Schur convexity property proved in [RYZ22].

  3. 3.

Finally, denoting by $P_{i}$ the distribution of the $i$-th components of
codewords in code ${\mathcal{C}}$, Schur convexity promises
$f(P_{i},U_{L})\leq f(P_{q,p_{i}},U_{L})$. In [RYZ22], it is proved that
$f(P_{q,p},U_{L})$ is convex for $p\in[1/q,1]$. Thus, we can conclude that

$\frac{1}{n}\sum_{i\in[n]}f(P_{i},U_{L})\leq f(P_{q,p},U_{L})$

with $p=\frac{1}{n}\sum_{i\in[n]}p_{i}$.

The remaining part of our proof is similar to [ABP18]. We show that a code
${\mathcal{C}}$ either has radius

$\operatorname{rad}({\mathcal{C}})=\frac{1}{n}\min_{{\boldsymbol{x}}\in[q]^{n}}\max_{{\boldsymbol{c}}\in{\mathcal{C}}}d_{\mathrm{H}}({\boldsymbol{c}},{\boldsymbol{x}})\leq
1-\frac{1}{q}-\delta$

or most of $L$-tuples with distinct codewords in ${\mathcal{C}}$ are
distributed close to uniform,. For the former case, we use the convexity
property to show that the list-decodability of ${\mathcal{C}}$ can not exceed
$f(U_{q},U_{L})=p_{*}(q,L)$ by much. For the latter case, since most of
$L$-tuples of distinct codewords in ${\mathcal{C}}^{L}$ looks uniformly at
random, we can show that the list-decodablilty of ${\mathcal{C}}$ is very
close to that of random codes which is $f(U_{q},U_{L})$.

#### Generalization to list-recovery.

For list-recovery, i.e., $\ell>1$, we find an embedding $\varphi_{\ell}$ that
maps each element in $[q]$ to a superposition of $\ell$ vertices of the
simplex in ${\mathbb{R}}^{q}$, i.e., we map the element in $[q]$ to a vector
space $[0,1]^{{\mathcal{X}}}$ where ${\mathcal{X}}=\binom{[q]}{\ell}$ is the
collection of all $\ell$-subsets in $[q]$. Concretely, we define
$\varphi_{\ell}(i):=\sum_{A\in{\mathcal{X}},i\in A}{\boldsymbol{e}}_{A}$ where
$({\boldsymbol{e}}_{A})_{A\in{\mathcal{X}}}$ is a standard basis of
${\mathbb{R}}^{{\mathcal{X}}}$. The intuition behind this map is that if $i\in
X$, we have
$\left\|\varphi_{\ell}(i)-{\boldsymbol{e}}_{X}\right\|_{1}=\binom{q}{\ell}-1$
and otherwise
$\left\|\varphi_{\ell}(i)-{\boldsymbol{e}}_{X}\right\|_{1}=\binom{q}{\ell}+1$.
Similar to the list decoding, given $L$ codewords in $[q]^{n}$, we obtain $L$
vectors ${\boldsymbol{x}}_{1},\ldots,{\boldsymbol{x}}_{L}$ under the map
$\varphi_{\ell}$. Our goal is to find a vector
${\boldsymbol{y}}=(y(i,A))_{[n]\times{\mathcal{X}}}$ close to these $L$
vectors subject to the constraint that $\sum_{A\in{\mathcal{X}}}y(i,A)=1$ for
any $i\in[n]$. This constraint combined with the basic feasible solution
argument in Proposition 27 forces that for almost all $i\in[n]$,
$(y(i,A))_{A\in{\mathcal{X}}}$ is of the form ${\boldsymbol{e}}_{X}$. For such
$i$, we can find an $\ell$-subset $X\in{\mathcal{X}}$ preserving the distance,
i.e.,

$d_{\mathrm{LR}}(i,X)=\mathds{1}{\left\\{i\notin
X\right\\}}=\frac{1}{2}\left(\left\|\varphi_{\ell}(i)-{\boldsymbol{e}}_{X}\right\|_{1}-\binom{q}{\ell}+1\right).$

Besides the linear programming relaxation, further adjustments for the proof
of properties analogous to Items 1, 2 and 3 above are required.

#### Code construction.

As alluded to before, a code that saturates the optimal size-radius trade-off
should essentially saturate both the upper and lower bounds on the quantity

$\displaystyle\frac{1}{M^{L}}\sum_{({\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L})\in{\mathcal{C}}^{L}}\overline{\operatorname{rad}}_{\mathrm{H}}({\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L})$

considered in the double-counting argument. Indeed, our impossibility result
implies that any optimal zero-rate code must contain a large fraction of
random-like $L$-tuples $({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})$,
i.e., for every ${\boldsymbol{u}}\in[q]^{L}$

$\sum_{i=1}^{n}\mathds{1}{\left\\{({\boldsymbol{c}}_{1}(i),\ldots,{\boldsymbol{c}}_{L}(i))={\boldsymbol{u}}\right\\}}\approx\frac{n}{q^{L}}$
(4)

where
${\boldsymbol{c}}_{j}=({\boldsymbol{c}}_{j}(1),\ldots,{\boldsymbol{c}}_{j}(n))\in[q]^{n}$.
To match such an impossibility result, an optimal construction should contain
as many such $L$-tuples as possible. A simplex-like code then becomes a
natural candidate. This is a natural extension of the construction in [ABP18]
to larger alphabet. An $M\times n$ codebook ${\mathcal{C}}$ consisting of $M$
codewords each of length $n$ is constructed by putting as columns all possible
distinct length-$M$ vectors that contains identical numbers of $1,2,\cdots,q$.
It is not hard to see by symmetry that (4) becomes equality for every
$L$-tuple with distinct codewords in ${\mathcal{C}}$. Thus, ${\mathcal{C}}$ is
the most regular code.

We also remark that, unlike for positive-rate codes, the prototypical random
construction (with expurgation) does not lead to favorable size-radius trade-
off since the deviation of random sampling is comparatively too large in the
zero-rate regime. In contrast, the simplex code is deterministically regular
and has no deviation.

###  1.3 Organization

The remainder is organized as follows. First, Section 2 provides the necessary
notations and definitions, together with some preliminary results which will
be useful in the subsequent arguments. Sections 3.1, 3.2, 3.3 and 3.4 contain
our argument establishing Theorem 1 for list-decoding (i.e. the case
$\ell=1$); in Section 4 we elucidate the changes that need to be made to
establish the theorem for general $\ell$. Next, Section 5 provides the code
construction establishing Theorem 2. We lastly summarize our contribution in
Section 6 and state open problems.

##  2 Preliminaries

Firstly, for convenience of the reader we begin by summarizing the notation
that we use. This is particularly relevent as we will often be in situations
where we need multiple indexes for, e.g., lists of vectors where each
coordinate lies in a probability simplex, so the reader is encouraged to refer
to this table whenever it is unclear what is intended.

English letter in boldface |  $[q]^{n}$-valued vector
---|---
Greek letter in boldface |  $\Delta([q])$-valued vector
$\Delta:=\Delta([q])$ | Simplex in $[0,1]^{q}$, i,e., $\Delta=\\{(x_{1},\ldots,x_{q})\in[0,1]^{q}:\sum_{i=1}^{q}x_{i}=1\\}$
$\partial\Delta$ | Set of vertices of $\Delta$
${\boldsymbol{e}}_{x}\in\partial\Delta$ | The image of $x\in[q]$ under $\varphi$, i.e., the $x$-th vertex of $\Delta$
${\boldsymbol{c}}_{i}\in[q]^{n}$ | The $i$-th codeword in a list
${\boldsymbol{x}}_{i}\in\Delta^{n}$ | Image of ${\boldsymbol{c}}_{i}$ under $\varphi$ (applied component-wise)
${\boldsymbol{y}}\in\Delta^{n}$ | Relaxed center of a list
${\boldsymbol{x}}(j)\in\partial\Delta,{\boldsymbol{y}}(j)\in\Delta$ | The $j$-th block (of length $q$) in ${\boldsymbol{x}}\in(\partial\Delta)^{n},{\boldsymbol{y}}\in\Delta^{n}$, respectively
$x(j,k)\in\\{0,1\\},y(j,k)\in[0,1]$ | The $(j,k)$-th element of ${\boldsymbol{x}}\in(\partial\Delta)^{n},{\boldsymbol{y}}\in\Delta^{n}$, respectively
$\operatorname{rad}_{\mathrm{H}}$ | (Standard) Chebyshev radius
$\operatorname{rad}$ | Relaxed Chebyshev radius
$\overline{\operatorname{rad}}$ | Average radius
$\overline{\operatorname{rad}}_{\omega}$ | Average radius weighted by $\omega\in\Delta([L])$
$f(P,\omega)$ | Expected average radius (weighted by $\omega$) of $P$-distributed symbols
$(X_{1},\cdots,X_{L})\sim P^{\otimes L}$ | A list of i.i.d. $P$-distributed symbols
$U_{k}$ | Uniform distribution on $[k]$
Table 1: Notation for list-decoding.

For a finite set $S$ and an integer $0\leq k\leq|S|$, we denote
$\binom{S}{k}\coloneqq\left\\{T\subset S:|T|=k\right\\}$. Let
$[q]=\\{1,\ldots,q\\}$.

###  2.1 List-Decoding

Fix $q\in{\mathbb{Z}}_{\geq 3}$ and $L\in{\mathbb{Z}}_{\geq 2}$. Let
$d_{\mathrm{H}}({\boldsymbol{c}},{\boldsymbol{r}})$ denote the _Hamming
distance_ between ${\boldsymbol{c}},{\boldsymbol{r}}\in[q]^{n}$, i.e., the
number of coordinates on which the strings differ. For $t\in[0,n]$, let
$\mathcal{B}_{\mathrm{H}}({\boldsymbol{y}},t):=\\{{\boldsymbol{c}}\in[q]^{n}:d_{\mathrm{H}}({\boldsymbol{c}},{\boldsymbol{y}})\leq
t\\}$ denote the _Hamming ball_ centered around ${\boldsymbol{y}}$ of radius
$\left\lfloor t\right\rfloor$.

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

Let $p\in[0,1]$. A code ${\mathcal{C}}\subseteq[q]^{n}$ is _$(p,L)_{q}$ -list-
decodable_ if for any ${\boldsymbol{y}}\in[q]^{n}$,

$\displaystyle\left|{\mathcal{C}}\cap\mathcal{B}_{\mathrm{H}}({\boldsymbol{y}},np)\right|$
$\displaystyle\leq L-1.$

In [RYZ22] the zero-rate regime for list-decoding was derived, which is the
supremum over $p\in[0,1]$ for which $(p-\varepsilon,L)_{q}$-list-decodable
codes of positive rate exist for all $\varepsilon>0$. This value was shown to
be

$\displaystyle
p_{*}(q,L)=1-\frac{1}{L}\mathop{\mathbb{E}}_{(X_{1},\cdots,X_{L})\sim
U_{q}^{\otimes L}}\left[\mathsf{pl}(X_{1},\cdots,X_{L})\right],$ (5)

where the function $\mathsf{pl}$ outputs the number of times the most popular
symbol appears. In [RYZ22] it is shown that $(p_{*}(q,L)+\varepsilon,L)$-list-
decodable codes have size $O_{\varepsilon,q,L}(1)$, i.e., some constant
independent of $n$. Our target in this work is to show that the correct
dependence on $\varepsilon$ is $O_{q,L}(1/\varepsilon)$, except for the case
of $q=2$ with odd $L$.

A “dual” definition of list-decodability is proffered by the Chebyshev radius.

######  Definition 2 (Chebyshev radius).

The _Chebyshev radius_ of a list of distinct vectors
${\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L}\in[q]^{n}$ is defined as

$\displaystyle\operatorname{rad}_{\mathrm{H}}({\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L})$
$\displaystyle\coloneqq\frac{1}{n}\min_{{\boldsymbol{r}}\in[q]^{n}}\max_{i\in[L]}d_{\mathrm{H}}({\boldsymbol{c}}_{i},{\boldsymbol{r}}).$

Observe that a code ${\mathcal{C}}\subseteq[q]^{n}$ is $(p,L)$-list-decodable
if and only if

$\displaystyle\min\\{\operatorname{rad}_{\mathrm{H}}(\boldsymbol{c}_{1},\dots,\boldsymbol{c}_{L}):\boldsymbol{c}_{1},\dots,\boldsymbol{c}_{L}\in{\mathcal{C}}\text{
distinct}\\}>p\ .$ (6)

In particular, to show a code fails to be list-decodable, it suffices to upper
bound the Chebyshev radius of $L$ distinct codewords.

Recall that our main target is an upper bound on the size of list-
decodable/-recoverable codes (in the zero-rate regime). A natural approach is
to derive from Equation 6 the desired bound on the code; however, this
quantity is quite difficult to work with directly. We therefore work with a
_relaxed_ version, which we now introduce.

We require the following definitions. Let us embed $[q]^{n}$ into the simplex
$\Delta([q])$ via the following map $\varphi$:

$\displaystyle\begin{array}[]{rclc}\varphi\colon&[q]&\to&\Delta([q])\\\
&x&\mapsto&{\boldsymbol{e}}_{x}\end{array}$ (9)

where ${\boldsymbol{e}}_{x}$ is the $q$-dimensional vector with a $1$ in the
$x$-th location and $0$ everywhere else. Denote by $\Delta=\Delta([q])$ the
simplex and
$\partial\Delta=\\{{\boldsymbol{e}}_{1},\cdots,{\boldsymbol{e}}_{q}\\}$ its
vertices. For ${\boldsymbol{\chi}}={\boldsymbol{e}}_{x}\in\partial\Delta$ and
${\boldsymbol{\eta}}\in\Delta$, let

$\displaystyle d({\boldsymbol{\chi}},{\boldsymbol{\eta}})$
$\displaystyle:=\frac{1}{2}\left\|{\boldsymbol{\chi}}-{\boldsymbol{\eta}}\right\|_{1}=\frac{1}{2}\left(1-{\boldsymbol{\eta}}(x)+\sum_{x^{\prime}\in[q]\setminus\\{x\\}}{\boldsymbol{\eta}}(x^{\prime})\right).$
(10)

Note that if ${\boldsymbol{\eta}}={\boldsymbol{e}}_{y}\in\partial\Delta$, then

$\displaystyle d({\boldsymbol{\chi}},{\boldsymbol{\eta}})$
$\displaystyle=d_{\mathrm{H}}(x,y).$

From now on we will only work with $\Delta^{n}$-valued vectors and will still
denote such length-$qn$ vectors by boldface letters, abusing the notation. For
${\boldsymbol{y}}\in\Delta^{n}$, we use $y(j,k)\in[0,1]$ to denote its
$(j,k)$-th element and use
${\boldsymbol{y}}(j)=(y(j,1),\ldots,y(j,q))\in\Delta$ to denote its $j$-th
block of size $q$. For ${\boldsymbol{c}}\in[q]^{n}$, we use
${\boldsymbol{c}}(j)\in[q]$ to denote its $j$-th element.

For ${\boldsymbol{x}}\in(\partial\Delta)^{n}$ and
${\boldsymbol{y}}\in\Delta^{n}$, the definition of $d(\cdot,\cdot)$ can be
extended to length-$qn$ vectors in the natural way. Specifically,

$\displaystyle d({\boldsymbol{x}},{\boldsymbol{y}})$
$\displaystyle=\sum_{j=1}^{n}d({\boldsymbol{x}}(j),{\boldsymbol{y}}(j)).$ (11)

We may now define the _relaxed Chebyshev radius_.

######  Definition 3.

The _relaxed Chebyshev radius_ of a list of distinct vectors
${\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L}\in(\partial\Delta)^{n}$ is

$\displaystyle\operatorname{rad}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})$
$\displaystyle\coloneqq\frac{1}{n}\min_{{\boldsymbol{y}}\in\Delta^{n}}\max_{i\in[L]}d({\boldsymbol{x}}_{i},{\boldsymbol{y}}).$
(12)

Observe that

$\displaystyle\operatorname{rad}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})$
$\displaystyle\leq\operatorname{rad}_{\mathrm{H}}({\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L}).$
(13)

where $\varphi({\boldsymbol{c}}_{i})={\boldsymbol{x}}_{i}$ (here we extend the
definition of $\varphi$ to length-$n$ inputs in a similar way as in Equation
11). This justifies the “relaxation” terminology.

As a last piece of terminology, we define the radius of a code.

######  Definition 4.

For any code ${\mathcal{C}}\in[q]^{n}$, we define the _Chebyshev radius_ of
${\mathcal{C}}$ as

$\operatorname{rad}({\mathcal{C}})=\frac{1}{n}\min_{{\boldsymbol{x}}\in[q]^{n}}\max_{{\boldsymbol{c}}\in{\mathcal{C}}}d_{\mathrm{H}}({\boldsymbol{c}},{\boldsymbol{x}}).$

###  2.2 List-Recovery

${\mathcal{X}}=\binom{[q]}{\ell}$ | collection of $\ell$-subsets in $[q]$.
---|---
English capital letter $A$ | a $\ell$-subset in ${\mathcal{X}}$
English capital letter in bold ${\boldsymbol{Y}}$ |  ${\mathcal{X}}$-valued vector
${\mathcal{X}}_{i}=\\{A\in{\mathcal{X}}:i\in A\\}$ | collection of $\ell$-subsets containing in $[q]$ that contains element $i$.
$\Delta_{\ell}=\Delta_{\ell}({\mathcal{X}})$ | Simplex in $[0,1]^{{\mathcal{X}}}$, i,e., $\Delta_{\ell}=\\{(x_{A})_{A\in{\mathcal{X}}}\in[0,1]^{\mathcal{X}}:\sum_{A\in{\mathcal{X}}}x_{A}=1\\}$
${\boldsymbol{e}}_{A}$ | the $A$-th vertex of $\Delta_{\ell}$
${\boldsymbol{e}}_{i}=\sum_{A\in{\mathcal{X}}_{i}}{\boldsymbol{e}}_{A}$ | the image of $i\in[q]$ under $\varphi_{\ell}$
$\partial\Delta_{\ell}=\\{{\boldsymbol{e}}_{1},\ldots,{\boldsymbol{e}}_{q}\\}$ | The image of elements in $[q]$ under $\varphi_{\ell}$
${\boldsymbol{c}}_{i}\in[q]^{n}$ | The $i$-th codeword in a list
${\boldsymbol{x}}_{i}\in\Delta_{\ell}^{n}$ | Image of ${\boldsymbol{c}}_{i}$ under $\varphi$ (applied component-wise)
${\boldsymbol{y}}\in\Delta_{\ell}^{n}$ | Relaxed center of a list
${\boldsymbol{x}}(j)\in\partial\Delta_{\ell},{\boldsymbol{y}}(j)\in\Delta_{\ell}$ | The $j$-th block (of length $\binom{q}{\ell}$) in ${\boldsymbol{x}}\in(\partial\Delta_{\ell})^{n},{\boldsymbol{y}}\in\Delta_{\ell}^{n}$, respectively
${\boldsymbol{x}}(j,A)\in\\{0,1\\},{\boldsymbol{y}}(j,A)\in[0,1]$ | The $(j,A)$-th element of ${\boldsymbol{x}}\in(\partial\Delta_{\ell})^{n},{\boldsymbol{y}}\in\Delta_{\ell}^{n}$, respectively
$\operatorname{rad}_{\ell}$ | (Standard) $\ell$ radius
$\operatorname{rad}$ | Relaxed $\ell$-radius
$\overline{\operatorname{rad}}$ | Average $\ell$-radius
$\overline{\operatorname{rad}}_{\omega,\ell}$ | Average $\ell$-radius weighted by $\omega\in\Delta([L])$
$f_{\ell}(P,\omega)$ | Expected average $\ell$-radius (weighted by $\omega$) of $P$-distributed symbols
$(X_{1},\cdots,X_{L})\sim P^{\otimes L}$ | A list of i.i.d. $P$-distributed symbols
$U_{k}$ | Uniform distribution on $[k]$
Table 2: Notation for list-recovery.

We now provide the necessary modifications to the above definitions to the
setting of list-recovery. Let ${\mathcal{X}}=\binom{[q]}{\ell}$ be the
collection of all $\ell$-subsets in $[q]$ and
${\mathcal{X}}_{i}=\\{A\in{\mathcal{X}}:i\in A\\}$. Define
$\Delta_{\ell}=\\{(x_{A})_{A\in{\mathcal{X}}}\in[0,1]^{\mathcal{X}}:\sum_{A\in{\mathcal{X}}}x_{A}=1\\}$.
Let $({\boldsymbol{e}}_{A})_{A\in{\mathcal{X}}}$ is a standard basis of
${\mathbb{R}}^{{\mathcal{X}}}$. Let
${\boldsymbol{e}}_{i}=\sum_{A\in{\mathcal{X}}_{i}}{\boldsymbol{e}}_{A}$ and
$\partial\Delta=\\{{\boldsymbol{e}}_{1},\ldots,{\boldsymbol{e}}_{q}\\}$. Let
$\varphi_{\ell}:[q]\rightarrow\partial\Delta_{\ell}$ be defined as
$\varphi_{\ell}(i)={\boldsymbol{e}}_{i}$. Below, we define the list-recovery
distance between a vector in $[q]^{n}$ and an $n$-tuple of $\ell$-subsets
${\boldsymbol{Y}}\in{\mathcal{X}}^{n}$. If $\ell=1$, this list-recovery
distance recovers the classic Hamming distance, viewing ${\boldsymbol{Y}}$
naturally as a vector in $[q]^{n}$.

######  Definition 5 (List-recovery distance).

Given a vector ${\boldsymbol{x}}\in[q]^{n}$ and a tuple of sets
${\boldsymbol{Y}}=(Y_{1},\dots,Y_{n})\in{\mathcal{X}}^{n}$ for $1\leq\ell\leq
q-1$, we define

$\displaystyle d_{\mathrm{LR}}({\boldsymbol{x}},{\boldsymbol{Y}})$
$\displaystyle\coloneqq\sum_{i=1}^{n}\mathds{1}{\left\\{x_{i}\notin
Y_{i}\right\\}}\ .$

######  Definition 6 (List-recoverability).

A code ${\mathcal{C}}\subset[q]^{n}$ is said to be _$(p,\ell,L)$ -list-
recoverable_ if for every ${\boldsymbol{Y}}\in\binom{[q]}{\ell}^{n}$,
$\left|{\mathcal{C}}\cap\mathcal{B}_{\mathrm{LR}}({\boldsymbol{Y}},np)\right|<L$
where

$\mathcal{B}_{\mathrm{LR}}({\boldsymbol{Y}},np)=\\{{\boldsymbol{c}}\in[q]^{n}:d_{\mathrm{LR}}({\boldsymbol{c}},{\boldsymbol{Y}})\leq
np\\}.$

The zero-rate regime for list-recoverability was also derived in [RYZ22]:

$\displaystyle
p_{*}(q,\ell,L)=1-\frac{1}{L}\mathop{\mathbb{E}}_{(X_{1},\cdots,X_{L})\sim
U_{q}^{\otimes L}}\left[\mathsf{pl}_{\ell}(X_{1},\cdots,X_{L})\right]\ ,$ (14)

where
$\mathsf{pl}_{\ell}(x_{1},\dots,x_{L})=\max_{\Sigma\subseteq[q]:|\Sigma|=\ell}|\\{i\in[L]:x_{i}\in\Sigma\\}|$
is the top-$\ell$ plurality value, i.e., the number of times the $\ell$ most
popular symbols appear.

######  Definition 7 ($\ell$-radius).

The _$\ell$ -radius_ of an $L$-set of vectors
${\boldsymbol{c}}_{1},\dots,{\boldsymbol{c}}_{L}\in[q]^{n}$ is defined as the
radius of the smallest list-recovery ball containing the set
$\\{{\boldsymbol{c}}_{1},\dots,{\boldsymbol{c}}_{L}\\}$:

$\displaystyle\operatorname{rad}_{\ell}({\boldsymbol{c}}_{1},\dots,{\boldsymbol{c}}_{L})$
$\displaystyle\coloneqq\frac{1}{n}\min_{{\boldsymbol{Y}}\in{\mathcal{X}}^{n}}\max_{i\in[L]}d_{\mathrm{LR}}({\boldsymbol{c}}_{i},{\boldsymbol{Y}}).$
(15)

In analogy to the list-decoding case, we define the $\ell$-radius of
${\mathcal{C}}$.

######  Definition 8.

For any code ${\mathcal{C}}\in[q]^{n}$, we define the _$\ell$ -radius_ of
${\mathcal{C}}$ as

$\operatorname{rad}_{\ell}({\mathcal{C}})=\frac{1}{n}\min_{{\boldsymbol{Y}}\in{\mathcal{X}}^{n}}\max_{{\boldsymbol{c}}\in{\mathcal{C}}}d_{\mathrm{LR}}({\boldsymbol{c}},{\boldsymbol{Y}}).$

We embed $[q]$ into Euclidean space $[0,1]^{{\mathcal{X}}}$,

$\displaystyle\begin{array}[]{rclc}\varphi_{\ell}\colon&[q]&\to&[0,1]^{{\mathcal{X}}}\\\
&i&\mapsto&{\boldsymbol{e}}_{i}:=\sum_{A\in{\mathcal{X}}_{i}}{\boldsymbol{e}}_{A}.\end{array}$
(18)

Define
$\partial\Delta_{\ell}=\\{{\boldsymbol{e}}_{1},\ldots,{\boldsymbol{e}}_{q}\\}$.
For ${\boldsymbol{\chi}}={\boldsymbol{e}}_{i}\in\partial\Delta_{\ell}$ and
${\boldsymbol{\eta}}\in\Delta_{\ell}$, let

$\displaystyle d({\boldsymbol{\chi}},{\boldsymbol{\eta}})$
$\displaystyle=\frac{1}{2}\left(\left\|{\boldsymbol{\chi}}-{\boldsymbol{\eta}}\right\|_{1}-\binom{q-1}{\ell-1}+1\right)$
$\displaystyle=\frac{1}{2}\left(\sum_{A\in{\mathcal{X}}_{i}}(1-{\boldsymbol{\eta}}(A))+\sum_{A^{\prime}\in{\mathcal{X}}\setminus{\mathcal{X}}_{i}}{\boldsymbol{\eta}}(A^{\prime})-\binom{q-1}{\ell-1}+1\right).$
(19)

We abuse the notation $d({\boldsymbol{\chi}},{\boldsymbol{\eta}})$ as
${\boldsymbol{\chi}},{\boldsymbol{\eta}}$ are vectors of length
$|{\mathcal{X}}|$. Note that if ${\boldsymbol{\eta}}={\boldsymbol{e}}_{A}$ for
some $A\in{\mathcal{X}}$, then

$\displaystyle d({\boldsymbol{\chi}},{\boldsymbol{\eta}})$
$\displaystyle=d_{\mathrm{LR}}(i,A)\in\\{0,1\\}.$

Define the _relaxed $\ell$-radius_ of a list of distinct vectors
${\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L}\in(\partial\Delta_{\ell})^{n}$
as:

$\displaystyle\operatorname{rad}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})$
$\displaystyle\coloneqq\frac{1}{n}\min_{{\boldsymbol{y}}\in\Delta_{\ell}^{n}}\max_{i\in[L]}d({\boldsymbol{x}}_{i},{\boldsymbol{y}}).$

Obviously,

$\displaystyle\operatorname{rad}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})$
$\displaystyle\leq\operatorname{rad}_{\ell}({\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L}).$

where ${\boldsymbol{x}}_{i}=\varphi_{\ell}({\boldsymbol{c}}_{i})$.

###  2.3 Types of Vector Tuples

The last concept that we need is the type of a tuple of vectors. Informally,
one takes a tuple of vectors
$({\boldsymbol{c}}_{1},\dots,{\boldsymbol{c}}_{L})\in([q]^{n})^{L}$, views it
as a $L\times n$ matrix, and then computes the fraction of columns that take
on a certain value ${\boldsymbol{u}}\in[q]^{L}$ for each
${\boldsymbol{u}}\in[q]^{L}$. In other words, the type of is the distribution
on $[q]^{L}$ induced by randomly sampling a column from this matrix.

######  Definition 9 (Type).

Let $q,L\in{\mathbb{N}}$, let
$({\boldsymbol{c}}_{1},\dots,{\boldsymbol{c}}_{L})\in([q]^{n})^{L}$ be a tuple
of vectors, and let ${\boldsymbol{u}}\in[q]^{L}$ be a vector. The _type_ of
$({\boldsymbol{c}}_{1},\dots,{\boldsymbol{c}}_{L})$ is

$\mathsf{type}({\boldsymbol{c}}_{1},\dots,{\boldsymbol{c}}_{L})\coloneqq(\mathsf{type}_{\boldsymbol{u}}({\boldsymbol{c}}_{1},\dots,{\boldsymbol{c}}_{L}))_{{\boldsymbol{u}}\in[q]^{L}}$

where

$\mathsf{type}_{\boldsymbol{u}}({\boldsymbol{c}}_{1},\dots,{\boldsymbol{c}}_{L})\coloneqq\frac{1}{n}\sum_{i=1}^{n}\mathds{1}{\left\\{({\boldsymbol{c}}_{1}(i),\dots,{\boldsymbol{c}}_{L}(i))={\boldsymbol{u}}\right\\}}\
.$

##  3 Zero-Rate List-Decoding

###  3.1 Linear Programming Relaxation

We have shown in Equation 13 that $\operatorname{rad}$ is smaller than
$\operatorname{rad}_{\mathrm{H}}$. Conversely, Lemma 3 below establishes that
$\operatorname{rad}$ and $\operatorname{rad}_{\mathrm{H}}$ do not differ much.
That is, for any list, if a center ${\boldsymbol{y}}\in\Delta^{n}$ achieves a
relaxed radius $t$, then there must exist ${\boldsymbol{r}}\in[q]^{n}$
attaining approximately the same $t$ for sufficiently large $n$.

######  Lemma 3 ($\operatorname{rad}$ is close to
$\operatorname{rad}_{\mathrm{H}}$).

Let ${\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L}\in[q]^{n}$. Denote by
${\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L}\in(\partial\Delta)^{n}$ the
images of ${\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L}$ under the
embedding $\varphi$. Then

$\displaystyle\operatorname{rad}_{\mathrm{H}}({\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L})$
$\displaystyle\leq\operatorname{rad}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})+\frac{L}{n}.$

###### Proof.

Suppose
$\operatorname{rad}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})=t$. Then
there exists ${\boldsymbol{y}}\in\Delta^{n}$ such that for every $i\in[L]$,

$\displaystyle d({\boldsymbol{x}}_{i},{\boldsymbol{y}})$
$\displaystyle=\frac{1}{2}\sum_{j=1}^{n}\left(1-y(j,c_{i}(j))+\sum_{x\in[q]\setminus\\{c_{i}(j)\\}}y(j,x)\right)\leq
t,$

where the first equality is by Equations 10 and 11. That is, the following
polytope is nonempty:

$\left\\{{\boldsymbol{y}}\in\Delta^{n}:\forall
i\in[L],\;d({\boldsymbol{x}}_{i},{\boldsymbol{y}})\leq t\right\\}\\\
=\left\\{(y(j,k))_{(j,k)\in[n]\times[q]}:\begin{array}[]{l}\forall(j,k)\in[n]\times[q],\,y(j,k)\geq
0,\\\ \forall j\in[n],\,\sum_{k=1}^{q}y(j,k)=1,\\\ \forall
i\in[L],\,\frac{1}{2}\sum_{j=1}^{n}\left(1-y(j,{\boldsymbol{c}}_{i}(j))+\sum_{x\in[q]\setminus\\{{\boldsymbol{c}}_{i}(j)\\}}y(j,x)\right)\leq
t\end{array}\right\\}.$ (20)

Equivalently, the following linear program (LP) is feasible:

$\displaystyle\begin{array}[]{cl}\max\limits_{(y(j,k))_{(j,k)\in[n]\times[q]}}&0\\\
\mathrm{s.t.}&\forall(j,k)\in[n]\times[q],\,y(j,k)\geq 0,\\\ &\forall
j\in[n],\,\sum_{k=1}^{q}y(j,k)=1,\\\ &\forall
i\in[L],\,\frac{1}{2}\sum_{j=1}^{n}\left(1-y(j,{\boldsymbol{c}}_{i}(j))+\sum_{x\in[q]\setminus\\{{\boldsymbol{c}}_{i}(j)\\}}y(j,x)\right)\leq
t.\end{array}$ (25)

Since the equality
$\left\langle{\boldsymbol{a}},{\boldsymbol{y}}\right\rangle\leq b$ is
equivalent to the equality
$\left\langle{\boldsymbol{a}},{\boldsymbol{y}}\right\rangle+z=b,z\geq 0$, the
above LP can be written in equational form:

$\displaystyle\begin{array}[]{cl}\max\limits_{(y(j,k))_{(j,k)\in[n]\times[q]},(z(i))_{i\in[L]}}&0\\\
\mathrm{s.t.}&\forall(j,k)\in[n]\times[q],\,y(j,k)\geq 0,\\\ &\forall
i\in[L],\,z(i)\geq 0,\\\ &\forall j\in[n],\,\sum\limits_{k=1}^{q}y(j,k)=1,\\\
&\forall
i\in[L],\,\frac{1}{2}\sum\limits_{j=1}^{n}\left(1-y(j,{\boldsymbol{c}}_{i}(j))+\sum\limits_{x\in[q]\setminus\\{{\boldsymbol{c}}_{i}(j)\\}}y(j,x)\right)+z(i)\leq
t,\end{array}$ (31)

or more compactly in matrix form:

$\displaystyle\begin{array}[]{cl}\max\limits_{{\boldsymbol{y}}\in{\mathbb{R}}^{nq},{\boldsymbol{z}}\in{\mathbb{R}}^{L}}&0\\\
\mathrm{s.t.}&\begin{bmatrix}A&I_{L}\\\
B&0\end{bmatrix}\begin{bmatrix}{\boldsymbol{y}}\\\
{\boldsymbol{z}}\end{bmatrix}=\begin{bmatrix}t\boldsymbol{1}_{L}\\\
\boldsymbol{1}_{n}\end{bmatrix},\\\
&{\boldsymbol{y}},{\boldsymbol{z}}\geq\boldsymbol{0}.\end{array}$ (35)

Here $A\in{\mathbb{R}}^{L\times(nq)}$ and $B\in{\mathbb{R}}^{n\times(nq)}$
encode respectively the fourth and third constraints in Equation 31, and
$I_{L}\in{\mathbb{R}}^{L\times L},\boldsymbol{1}_{L}\in{\mathbb{R}}^{L}$
denote respectively the $L\times L$ identity matrix and the all-one vector of
length $L$. It is clear that

$\displaystyle\operatorname{rk}\left(\begin{bmatrix}A&I_{L}\\\
B&0\end{bmatrix}\right)$ $\displaystyle\leq n+L.$

This implies that there exists a feasible solution
${\boldsymbol{y}},{\boldsymbol{z}}$ that has at most $n+L$ nonzeros and thus
${\boldsymbol{y}}=(y(j,k))_{(j,k)\in[n]\times[q]}$ has at most $n+L$ nonzeros.
Indeed, such solutions are known as the _basic feasible solutions_ ; see
Proposition 27. Note that for every block $j\in[n]$, $\sum_{k=1}^{q}y(j,k)=1$.
This implies that $y(j,1),\ldots,y(j,q)$ cannot be simultaneously $0$.
Moreover, if $q-1$ out of them are $0$, the remaining one is forced to be $1$.
Since there are $n$ blocks in total, by the pigeonhole principle, there are at
least $n-L$ choices of $j\in[n]$ such that
${\boldsymbol{y}}(j)=(y(j,1),\ldots,y(j,q))\in\partial\Delta$. Without loss of
generality, we assume that these $n-L$ indices are $1,\ldots,n-L$. Let
${\boldsymbol{r}}\in[q]^{n}$ be such that
$\varphi({\boldsymbol{r}}(j))={\boldsymbol{y}}(j)$ for $j=1,\ldots,n-L$ and
$r(j)$ is any value in $[q]$ for $j=n-L+1,\ldots,n$. Since
$d({\boldsymbol{x}}_{i}(j),{\boldsymbol{y}}(j))\in[0,1]$ and
$d_{\mathrm{H}}({\boldsymbol{c}}_{i}(j),{\boldsymbol{r}}(j))\in\\{0,1\\}$, the
difference between $d({\boldsymbol{x}}_{i},{\boldsymbol{y}})$ and
$d_{\mathrm{H}}({\boldsymbol{c}}_{i},{\boldsymbol{r}})$ is at most $L$. The
proof is completed. ∎

We further relax $\operatorname{rad}$ by defining the _weighted average
radius_. For
${\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L}\in(\partial\Delta)^{n}$ and
$\omega\in\Delta([L])$, let

$\displaystyle\overline{\operatorname{rad}}_{\omega}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})$
$\displaystyle\coloneqq\frac{1}{n}\min_{{\boldsymbol{y}}\in\Delta^{n}}\mathop{\mathbb{E}}_{i\sim\omega}\left[d({\boldsymbol{x}}_{i},{\boldsymbol{y}})\right]=\frac{1}{n}\min_{{\boldsymbol{y}}\in\Delta^{n}}\sum_{i\in[L]}\omega(i)d({\boldsymbol{x}}_{i},{\boldsymbol{y}}).$

In words, weighted average radius is obtained by replacing the maximization
over $i\in[L]$ in the definition of relaxed radius (see Equation 12) with an
average with respect to a distribution $\omega$.

Since the objective of the minimization is separable, one can minimize over
each $y(j)$ individually and obtain an alternative expression. Suppose
${\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L}\in(\partial\Delta)^{n}$ are
the images of ${\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L}\in[q]^{n}$
under the embedding $\varphi$. Then

$\displaystyle\overline{\operatorname{rad}}_{\omega}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})$
$\displaystyle=\frac{1}{n}\min_{{\boldsymbol{y}}\in\Delta^{n}}\sum_{i\in[L]}\omega(i)d({\boldsymbol{x}}_{i},{\boldsymbol{y}})$
$\displaystyle=\frac{1}{2n}\min_{({\boldsymbol{y}}_{1},\cdots,{\boldsymbol{y}}_{n})\in\Delta^{n}}\sum_{i\in[L]}\omega(i)\sum_{j=1}^{n}\left(1-{\boldsymbol{y}}_{j}({\boldsymbol{c}}_{i}(j))+\sum_{x\in[q]\setminus\\{{\boldsymbol{c}}_{i}(j)\\}}{\boldsymbol{y}}_{j}(x)\right)$
$\displaystyle=\frac{1}{2n}\min_{({\boldsymbol{y}}_{1},\cdots,{\boldsymbol{y}}_{n})\in\Delta^{n}}\sum_{j=1}^{n}\left[\sum_{i\in[L]}\omega(i)\left(1-{\boldsymbol{y}}_{j}({\boldsymbol{c}}_{i}(j))+\sum_{x\in[q]\setminus\\{{\boldsymbol{c}}_{i}(j)\\}}{\boldsymbol{y}}_{j}(x)\right)\right]$
$\displaystyle=\frac{1}{2n}\sum_{j=1}^{n}\min_{{\boldsymbol{y}}_{j}\in\Delta}\left[\sum_{i\in[L]}\omega(i)\left(1-2{\boldsymbol{y}}_{j}({\boldsymbol{c}}_{i}(j))+\sum_{x\in[q]}{\boldsymbol{y}}_{j}(x)\right)\right]$
(36)
$\displaystyle=\frac{1}{2n}\sum_{j=1}^{n}\min_{{\boldsymbol{y}}_{j}\in\Delta}\left[\sum_{i\in[L]}\omega(i)\left(2-2{\boldsymbol{y}}_{j}({\boldsymbol{c}}_{i}(j))\right)\right]$
$\displaystyle=\frac{1}{n}\sum_{j=1}^{n}\min_{{\boldsymbol{y}}_{j}\in\Delta}\left[1-\sum_{i\in[L]}\omega(i){\boldsymbol{y}}_{j}({\boldsymbol{c}}_{i}(j))\right]$
$\displaystyle=1-\frac{1}{n}\sum_{j=1}^{n}\max_{{\boldsymbol{y}}_{j}\in\Delta}\left[\sum_{i\in[L]}\omega(i){\boldsymbol{y}}_{j}({\boldsymbol{c}}_{i}(j))\right]$
$\displaystyle=1-\frac{1}{n}\sum_{j=1}^{n}\max_{x\in[q]}\sum_{\begin{subarray}{c}i\in[L]\\\
{\boldsymbol{c}}_{i}(j)=x\end{subarray}}\omega(i).$ (37)

Equation 36 holds since the objective in brackets only depends on
${\boldsymbol{y}}_{j}$, not on other
$({\boldsymbol{y}}_{j^{\prime}})_{j^{\prime}\in[n]\setminus\\{j\\}}$. To see
Equation 37, we note that a maximizer ${\boldsymbol{y}}^{*}\in\Delta$ to the
following problem

$\displaystyle\max_{{\boldsymbol{y}}\in\Delta}\sum_{i\in[L]}\omega(i)y(x_{i}),$

where $\omega\in\Delta([L])$ and $(x_{1},\cdots,x_{L})\in[q]^{L}$ are fixed,
is given by ${\boldsymbol{y}}^{*}={\boldsymbol{e}}_{x^{*}}$ where
$x^{*}\in[q]$ satisfies

$\displaystyle x^{*}$
$\displaystyle\in\operatorname*{argmax}_{x\in[q]}\sum_{i\in[L]}\omega(i)\mathds{1}{\left\\{x_{i}=x\right\\}}.$

Obviously, by definition, for any
${\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L}\in(\partial\Delta)^{n}$ and
$\omega\in\Delta([L])$,

$\displaystyle\overline{\operatorname{rad}}_{\omega}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})$
$\displaystyle\leq\operatorname{rad}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L}).$

In fact, the following lemma shows that $\operatorname{rad}$ is equal to the
maximum $\overline{\operatorname{rad}}_{\omega}$ over $\omega$.

######  Lemma 4 ($\operatorname{rad}$ equals maximum
$\overline{\operatorname{rad}}_{\omega}$).

For any
${\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L}\in(\partial\Delta)^{n}$,

$\displaystyle\operatorname{rad}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})$
$\displaystyle=\max_{\omega\in\Delta([L])}\overline{\operatorname{rad}}_{\omega}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L}).$

###### Proof.

Note that

$\displaystyle\operatorname{rad}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})$
$\displaystyle\coloneqq\frac{1}{n}\min_{{\boldsymbol{y}}\in\Delta^{n}}\max_{i\in[L]}d({\boldsymbol{x}}_{i},{\boldsymbol{y}})=\frac{1}{n}\min_{{\boldsymbol{y}}\in\Delta^{n}}\max_{\omega\in\Delta([L])}\sum_{i\in[L]}\omega(i)d({\boldsymbol{x}}_{i},{\boldsymbol{y}}),$

since the inner maximum is anyway achieved by a singleton distribution. Note
also that the objective function

$\displaystyle\sum_{i\in[L]}\omega(i)d({\boldsymbol{x}}_{i},{\boldsymbol{y}})$
$\displaystyle=\frac{1}{2}\sum_{i\in[L]}\omega(i)\sum_{j=1}^{n}\left(1-y(j,{\boldsymbol{c}}_{i}(j))+\sum_{x\in[q]\setminus\\{{\boldsymbol{c}}_{i}(j)\\}}y(j,x)\right)$

is affine in $\omega$ and linear in ${\boldsymbol{y}}$. Therefore, von
Neumann’s minimax theorem allows us to interchange $\min$ and $\max$ and
obtain

$\displaystyle\operatorname{rad}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})$
$\displaystyle=\frac{1}{n}\max_{\omega\in\Delta([L])}\min_{{\boldsymbol{y}}\in\Delta^{n}}\sum_{i\in[L]}\omega(i)d({\boldsymbol{x}}_{i},{\boldsymbol{y}})=\max_{\omega\in\Delta([L])}\overline{\operatorname{rad}}_{\omega}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L}),$

as claimed by the lemma. ∎

In fact, we can say something stronger: it is not necessary to maximize over
the entire (uncountable) probability simplex $\Delta([L])$. Instead, we can
extract a finite subset $\Omega_{L}\subset\Delta([L])$ and maximize over this
set to recover $\operatorname{rad}$. The following lemma is analogous to
[ABP18, Lemma 6].

######  Lemma 5 ($\operatorname{rad}$ is achieved by finitely many $\omega$).

For every $L$, there exists a finite set of probability measures
$\Omega_{L}\subseteq\Delta([L])$ such that

$\operatorname{rad}({\boldsymbol{x}}_{1},\ldots,{\boldsymbol{x}}_{L})=\max_{\omega\in\Omega_{L}}\overline{\operatorname{rad}}_{\omega}({\boldsymbol{x}}_{1},\ldots,{\boldsymbol{x}}_{L}).$

for all
${\boldsymbol{x}}_{1},\ldots,{\boldsymbol{x}}_{L}\in\partial\Delta^{n}$.

###### Proof.

The idea is to view the computation of
$\max_{\omega\in\Omega_{L}}\overline{\operatorname{rad}}_{\omega}({\boldsymbol{x}}_{1},\dots,{\boldsymbol{x}}_{L})$
as finding the maximum among some finite set of linear program maxima over
some convex polytopes, and then to take $\Omega_{L}$ to be the set of vertices
of the defined convex polytopes.

First, we define the convex polytopes based on a ($q$-ary version of a)
signature. For each $\omega\in\Delta([L])$, we define a _signature_ for
$\omega$ which is a function $S_{\omega}:[q]^{L}\rightarrow[q]$ such that

$S_{\omega}({\boldsymbol{u}})\in\operatorname*{argmax}_{x\in[q]}\sum_{i:{\boldsymbol{u}}(i)=x}\omega(i)$

for ${\boldsymbol{u}}\in[q]^{L}$. Define further the $q$ halfspaces
$H_{{\boldsymbol{u}},x}:=\\{\omega\in\Delta([L]):\sum_{i:{\boldsymbol{u}}(i)=x}\omega(i)\geq
1/q\\}$ for $x\in[q]$. Observe that if $S({\boldsymbol{u}})=x$ where $S$ is a
signature for $\omega$ then $\omega\in H_{{\boldsymbol{u}},x}$. Thus, by
ranging over the choices for ${\boldsymbol{u}}\in[q]^{L}$ and $x\in[q]$ we
obtain $q^{L+1}$ halfspaces that partition the $(L-1)$-dimensional space
$\Delta([L])$ into at most $\sum_{j\leq L-1}\binom{q^{L+1}}{j}$ regions.

For each possible signature $S:[q]^{L}\to[q]$, let
$\Omega_{S}=\\{\omega\in\Delta([L])\colon S\text{ is a signature for
}\omega\\}$, and note that $\Omega_{S}$ is a convex polytope. Indeed, it is an
intersection over ${\boldsymbol{u}}\in[q]^{L}$ of the convex polytopes

$\displaystyle\left\\{\omega\in\Delta([L])\colon\exists\text{ signature
}\right.$ $\displaystyle\left.S_{\omega}\text{ for }\omega\text{ s.t.
}S_{\omega}({\boldsymbol{u}})=S({\boldsymbol{u}})\right\\}$
$\displaystyle=\bigcap_{y\in[q]\setminus
S({\boldsymbol{u}})}\left\\{\omega\in\Delta([L])\colon\sum_{i:{\boldsymbol{u}}(i)=S({\boldsymbol{u}})}\omega(i)\geq\sum_{i:{\boldsymbol{u}}(i)=y}\omega(i)\right\\}$

where $S_{\omega}$ is a signature for $\omega$. Now, to maximize

$\overline{\operatorname{rad}}_{\omega}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})=\frac{1}{n}\min_{{\boldsymbol{y}}\in\Delta^{n}}\sum_{i\in[L]}\omega(i)d({\boldsymbol{x}}_{i},{\boldsymbol{y}})$

over $\omega\in\Omega_{L}$, consider the set
$T_{\boldsymbol{u}}=\\{i\in[n]:({\boldsymbol{x}}_{1}(i),\ldots,{\boldsymbol{x}}_{L}(i))={\boldsymbol{u}}\\}$
for ${\boldsymbol{u}}\in[q]^{L}$ and let
$a_{{\boldsymbol{u}}}=\frac{|T_{\boldsymbol{u}}|}{n}$. We claim it suffices to
find the maximum of the following linear function:

$\displaystyle\sum_{{\boldsymbol{u}}\in[q]^{L}}a_{{\boldsymbol{u}}}y_{{\boldsymbol{u}}},\quad\text{s.t.}\quad
y_{{\boldsymbol{u}}}=\sum_{i:{\boldsymbol{u}}(i)=S({\boldsymbol{u}})}\omega(i)$
(38)

over all $\omega\in\Omega_{S}$. Indeed, by Equation 37, we have

$\overline{\operatorname{rad}}_{\omega}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})=1-\frac{1}{n}\sum_{j=1}^{n}\max_{x\in[q]}\sum_{\begin{subarray}{c}i\in[L]\\\
c_{i}(j)=x\end{subarray}}\omega(i).$

This implies that a maximizer only depends on the index set
$T_{\boldsymbol{u}}$, and furthermore that its value is determined by the
$a_{{\boldsymbol{u}}}$’s as in Equation 38.

We can thus take the union of all vertex sets of all polytopes $\Omega_{S}$
for all signatures $S$. Multiplying this by the $O_{q,L}(1)$ regions defined
by all the halfspaces $H_{{\boldsymbol{u}},x}$ we obtain a finite set of
vertices, as desired. ∎

###  3.2 Properties of $f(P,\omega)$

Now, we consider the expected weighted average radius of a sequence of i.i.d.
symbols. Specifically, for $P\in\Delta([q])$ and $\omega\in\Delta([L])$, let

$\displaystyle f(P,\omega)$
$\displaystyle\coloneqq\mathop{\mathbb{E}}_{(X_{1},\cdots,X_{L})\sim
P^{\otimes
L}}\left[\overline{\operatorname{rad}}_{\omega}({\boldsymbol{e}}_{X_{1}},\cdots,{\boldsymbol{e}}_{X_{L}})\right].$

[ABP18] studies $f(P,\omega)$ for $q=2$ and even $L$. In this case, one can
take advantage of the fact that $P\in\Delta([2])$ may be parametrized by a
single real number, and thereby yield a fairly simple expression for
$f(P,\omega)$.

Nonetheless, in this subsection, we will show that all properties of
$f(P,\omega)$ in [ABP18] holding for $q=2$ and even $L$ can be generalized to
any $q\geq 3$ and any $L$. Let us first provide a more explicit expression for
$f(P,\omega)$ using Equation 37:

$\displaystyle f(P,\omega)$
$\displaystyle\coloneqq\mathop{\mathbb{E}}_{(X_{1},\cdots,X_{L})\sim
P^{\otimes L}}\left[1-\max_{x\in[q]}\sum_{\begin{subarray}{c}i\in[L]\\\
X_{i}=x\end{subarray}}\omega(i)\right]$
$\displaystyle=1-\sum_{(x_{1},\cdots,x_{L})\in[q]^{L}}\left(\prod_{i=1}^{L}P(x_{i})\right)\max_{x\in[q]}\sum_{i\in[L]}\omega(i)\mathds{1}{\left\\{x_{i}=x\right\\}}.$

We define the shorhand notation

$\displaystyle\mathrm{max}_{\omega}(x_{1},\cdots,x_{L})$
$\displaystyle\coloneqq\max_{x\in[q]}\sum_{\begin{subarray}{c}i\in[L]\\\
x_{i}=x\end{subarray}}\omega(i)$ (39)

for any $\omega\in\Delta([L])$ and $(x_{1},\dots,x_{L})\in[q]^{L}$.

The first property that we would like to establish is that $f(P,\omega)$ only
increases if $\omega$ is replaced by $U_{L}$, and furthermore that the maximum
is uniquely obtained at $U_{L}$ if $P(x)>0$ for all $x\in[q]$. In order to do
this, we will regularly “average-out” coordinates of $\omega$ and then show
that the function value increases (or at least, does not decrease). To be
introduce some terminology, for $S\subseteq[L]$ we say that
$\overline{\omega}$ is obtained from $\omega$ by _averaging-out_ the subset
$S$ of coordinates if $\overline{\omega}$ is defined as

$\overline{\omega}(i)=\begin{cases}\frac{\sum_{j\in S}\omega(j)}{|S|}&i\in
S\\\ \omega(i)&i\notin S\end{cases}\ .$

The following lemma gives a simple criterion for establishing that, if
$\overline{\omega}$ is obtained from $\omega$ by averaging two coordinates,
then $f(P,\overline{\omega})\leq f(P,\omega)$, and it furthermore gives a
criterion for the inequality to be strict. The main thrust of the proof of
Lemma 7 is thus to show that this criterion is always satisfied.

######  Lemma 6.

Let $P\in\Delta([q])$ and $\omega\in\Delta([L])$. Suppose
$\omega(L-1)\neq\omega(L)$ and that $\overline{\omega}\in\Delta([L])$ is
obtained by averaging-out the last two coordinates of $\omega$. Suppose that
for all $(x_{1},\dots,x_{L})\in[q]^{L}$ we have

$\displaystyle\frac{1}{2}\left(\mathrm{max}_{\omega}(x_{1},\cdots,x_{L-1},x_{L})+\mathrm{max}_{\omega}(x_{1},\cdots,x_{L},x_{L-1})\right)$
$\displaystyle\geq\mathrm{max}_{\overline{\omega}}(x_{1},\cdots,x_{L-1},x_{L}).$
(40)

Then $f(P,\overline{\omega})\geq f(P,\omega)$.

Furthermore, suppose that additionally there exists
$(x_{1},\dots,x_{L})\in[q]^{L}$ with $\prod_{i=1}^{L}P(x_{i})>0$ such that the
inequality in Equation 40 is strict. Then
$f(P,\overline{\omega})>f(P,\omega)$.

###### Proof.

Define $\omega^{\prime}\in\Delta([L])$ as

$\displaystyle\omega^{\prime}(i)$
$\displaystyle=\begin{cases}\omega(i),&i\in[L]\setminus\\{L-1,L\\}\\\
\omega(L),&i=L-1\\\ \omega(L-1),&i=L\end{cases}.$

That is, $\omega^{\prime}$ is obtained by swapping the last two components of
$\omega$. By symmetry, we have $f(P,\omega)=f(P,\omega^{\prime})$ and so

$\displaystyle f(P,\omega)$
$\displaystyle=\frac{1}{2}(f(P,\omega)+f(P,\omega^{\prime}))$
$\displaystyle=\frac{1}{2}\left(1-\sum_{(x_{1},\cdots,x_{L})\in[q]^{L}}\left(\prod_{i=1}^{L}P(x_{i})\right)\mathrm{max}_{\omega}(x_{1},\ldots,x_{L-1},x_{L})\right.$
$\displaystyle\quad\quad\quad\left.+1-\sum_{(x_{1},\cdots,x_{L})\in[q]^{L}}\left(\prod_{i=1}^{L}P(x_{i})\right)\mathrm{max}_{\omega^{\prime}}(x_{1},\ldots,x_{L-1},x_{L})\right)$
$\displaystyle=1-\sum_{(x_{1},\cdots,x_{L})\in[q]^{L}}\left(\prod_{i=1}^{L}P(x_{i})\right)\frac{1}{2}\left(\mathrm{max}_{\omega}(x_{1},\ldots,x_{L-1},x_{L})+\mathrm{max}_{\omega}(x_{1},\ldots,x_{L},x_{L-1}))\right)$
$\displaystyle\leq
1-\sum_{(x_{1},\cdots,x_{L})\in[q]^{L}}\left(\prod_{i=1}^{L}P(x_{i})\right)\mathrm{max}_{\overline{\omega}}(x_{1},\ldots,x_{L-1},x_{L})$
$\displaystyle=f(P,\overline{\omega})\ ,$

where the inequality follows from Equation 40. From the above sequence of
inequalities, it is also clear that if additionally there exists
$(x_{1},\dots,x_{L})\in[q]^{L}$ with $\prod_{i=1}^{L}P(x_{i})>0$ for which the
inequality in Equation 40 is strict, then
$f(P,\overline{\omega})>f(P,\omega)$. ∎

We now establish that the function value cannot decrease if $\omega$ is
replaced by $U_{L}$.

######  Lemma 7.

For any $P\in\Delta([q])$ and $\omega\in\Delta([L])$, $f(P,\omega)\leq
f(P,U_{L})$.

###### Proof.

Fix any $(x_{1},\cdots,x_{L})\in[q]^{L}$. Let $\omega\in\Delta([L])$ be non-
uniform. Without loss of generality, assume $\omega(L-1)\neq\omega(L)$. Let
$\overline{\omega}\in\Delta([L])$ be obtained by uniformizing the last two
components of $\omega$, i.e.,

$\displaystyle\overline{\omega}(i)$
$\displaystyle=\begin{cases}\omega(i),&i\in[L]\setminus\\{L-1,L\\}\\\
\frac{1}{2}(\omega(L-1)+\omega(L)),&i\in\\{L-1,L\\}\end{cases}.$

We claim $f(P,\overline{\omega})\geq f(P,\omega)$. By Lemma 6, we just need to
establish Equation 40.

Equation 40 trivially holds if $x_{L-1}=x_{L}$. We therefore assume below
$x_{L-1}\neq x_{L}$. Let $x_{L-1}=a$ and $x_{L}=b$. Let

$\omega^{(a)}=\sum_{\begin{subarray}{c}i\in[L-2]\\\
x_{i}=a\end{subarray}}\omega(i),\qquad\omega^{(b)}=\sum_{\begin{subarray}{c}i\in[L-2]\\\
x_{i}=b\end{subarray}}\omega(i)\ .$

Then, we have

$\sum_{\begin{subarray}{c}i\in[L]\\\
x_{i}=a\end{subarray}}\overline{\omega}(i)=\omega^{(a)}+\frac{1}{2}(\omega(L-1)+\omega(L)),\qquad\sum_{\begin{subarray}{c}i\in[L]\\\
x_{i}=b\end{subarray}}\overline{\omega}(i)=\omega^{(b)}+\frac{1}{2}(\omega(L-1)+\omega(L)).$

We first assume that there exists $c\notin\\{a,b\\}$ such that

$\mathrm{max}_{\overline{\omega}}(x_{1},\cdots,x_{L})=\sum_{\begin{subarray}{c}i\in[L]\\\
x_{i}=c\end{subarray}}\overline{\omega}(i)=\sum_{\begin{subarray}{c}i\in[L]\\\
x_{i}=c\end{subarray}}{\omega}(i)$

where the second equality follows since the set $\\{i\in[q]:x_{i}=c\\}$ does
not contain $L-1,L$. Equation 40 therefore holds as

$\mathrm{max}_{{\omega}}(x_{1},\cdots,x_{L-1},x_{L})\geq\sum_{\begin{subarray}{c}i\in[L]\\\
x_{i}=c\end{subarray}}{\omega}(i),\qquad\mathrm{max}_{\omega}(x_{1},\cdots,x_{L},x_{L-1})\geq\sum_{\begin{subarray}{c}i\in[L]\\\
x_{i}=c\end{subarray}}{\omega}(i).$

We proceed to the case that

$\mathrm{max}_{\overline{\omega}}(x_{1},\cdots,x_{L})=\max\left\\{\frac{1}{2}(\omega(L-1)+\omega(L))+\omega^{(a)},\frac{1}{2}(\omega(L-1)+\omega(L))+\omega^{(b)}\right\\}.$

Equation 40 holds as

$\mathrm{max}_{\omega}(x_{1},\cdots,x_{L-1},x_{L})\geq\max\left\\{\omega^{(a)}+\omega(L-1),\omega^{(b)}+\omega(L)\right\\}$

and

$\mathrm{max}_{{\omega}}(x_{1},\cdots,x_{L},x_{L-1})\geq\max\left\\{\omega^{(a)}+\omega(L),\omega^{(b)}+\omega(L-1)\right\\}.$

Thus, Lemma 6 implies $f(P,\overline{\omega})\geq f(P,\omega)$, as desired.

We can then continue averaging components of $\omega$ and in this way obtain a
sequence $(\omega_{i})_{i\in{\mathbb{N}}}$ of distributions with
$\omega_{1}=\omega$. This sequence converges in $\ell_{\infty}$-norm to the
uniform distribution $U_{L}$ and satisfies $f(P,\omega_{i+1})\geq
f(P,\omega_{i})$ for all $i\in{\mathbb{N}}$. Observing that $\omega\mapsto
f(P,\omega)$ is a continuous function – the term
$\max_{x\in[q]}\sum_{i\in[L]}\omega(i)\mathds{1}{\left\\{x_{i}=x\right\\}}$ is
a maximum over linear functions of $\omega$, hence linear, implying that
$f(P,\cdot)$ is a linear combination of continuous functions – it follows that
$f(P,U_{L})=\lim_{i\to\infty}f(P,\omega_{i})$, and in particular that
$f(P,U_{L})\geq f(P,\omega_{1})=f(P,\omega)$, as desired. ∎

We now strengthen the conclusion of Lemma 7 by showing that for all $q\geq 3$
and $L\geq 2$ the function $\omega\mapsto f(P,\omega)$ is _uniquely_ maximized
by the setting $\omega=U_{L}$, except for degenerate cases where $P(x)=0$ for
some $x\in[q]$.

Before stating and proving this fact, we note that the proof of Lemma 7 in
fact shows that we can average out any subset of coordinates of $\omega$ and
only increase the value of $f(P,\omega)$. We formalize this fact in the
following lemma, which will be useful in the following arguments.

######  Lemma 8.

Let $P\in\Delta([q])$, $\omega\in\Delta([L])$ and $S\subseteq[L]$. Let
$\overline{\omega}$ be obtained from $\omega$ by averaging-out the subset $S$
of coordinates. Then $f(P,\overline{\omega})\geq f(P,\omega)$.

######  Theorem 9.

Let $q\geq 3$, $L\geq 2$ and let $P\in\Delta([q])$ be such that $P(x)>0$ 666In
fact, our proof only apply with $P=U_{q}$ which clearly satisfies the
condition. for all $x\in[q]$. Then for all $\omega\in\Delta([L])$,
$f(P,\omega)\leq f(P,U_{L})$ with equality if and only if $\omega=U_{L}$.

###### Proof.

The inequality was already established in Lemma 7, so we focus on showing
$\omega=U_{L}$ when $f(P,\omega)=f(P,U_{L})$. As $q\geq 3$, let $a,b$ and $c$
denote $3$ distinct elements of $[q]$. Let $\omega\neq U_{L}$ and suppose for
a contradiction that $f(P,\omega)$ is a maximum of the function $\omega\mapsto
f(P,\omega)$. The proof proceeds via a number of cases.

  1. 1.

$L$ is even. Without loss of generality, $\omega(L-1)<\omega(L)$. If $L\geq
4$, let $\omega^{\prime}$ be obtained from $\omega$ by averaging-out the first
$L-2$ coordinates; by Lemma 8, $f(P,\omega^{\prime})\geq f(P,\omega)$. If
$L=2$, set $\omega^{\prime}=\omega$.

If $L\geq 4$, since $2|(L-2)$, we can set $x_{1}=\dots=x_{L/2-1}=a$ and
$x_{L/2}=\dots=x_{L-2}=b$. Set further $x_{L-1}=a$ and $x_{L}=b$. We observe
that for this $(x_{1},\dots,x_{L})\in[q]^{L}$ and $\overline{\omega}$ obtained
from $\omega^{\prime}$ by averaging-out the last two coordinates, Equation 40
strictly holds. Indeed,

$\mathrm{max}_{\omega^{\prime}}(x_{1},\ldots,x_{L-1},x_{L})+\mathrm{max}_{\omega^{\prime}}(x_{1},\ldots,x_{L},x_{L-1})=2\sum_{j=1}^{(L-2)/2}\omega(i)+2\omega(L)$

and

$2\mathrm{max}_{\overline{\omega}}(x_{1},\ldots,x_{L-1},x_{L})=2\sum_{j=1}^{(L-2)/2}\omega(i)+\omega(L-1)+\omega(L).$

Thus Lemma 6 implies $f(P,\overline{\omega})>f(P,\omega^{\prime})\geq
f(P,\omega)$, a contradiction.

  2. 2.

$L$ is odd and at least three components of $\omega$ take distinct values, or
the components in $\omega$ only take two different values and at least two of
them take the minimum value. Without loss of generality
$\omega(L-2)\leq\omega(L-1)<\omega(L)$. If $L\geq 5$, let $\omega^{\prime}$ be
obtained from $\omega$ by averaging-out the first $L-3$ coordinates; by Lemma
8, $f(P,\omega^{\prime})\geq f(P,\omega)$. If $L=3$, set
$\omega^{\prime}=\omega$.

Since $2|(L-3)$, if $L\geq 5$, we set $x_{1}=\dots=x_{(L-1)/2-1}=a$ and
$x_{(L-1)/2}=\dots=x_{L-3}=b$. Let $x_{L-2}=c$, $x_{L-1}=a$ and $x_{L}=b$. We
observe that for this $(x_{1},\dots,x_{L})\in[q]^{L}$ and $\overline{\omega}$
obtained from $\omega^{\prime}$ by averaging-out the last two coordinates,
Equation 40 strictly holds. Indeed, since $\omega(L-2)<\omega(L)$ we have

$\mathrm{max}_{\omega^{\prime}}(x_{1},\ldots,x_{L-1},x_{L})+\mathrm{max}_{\omega^{\prime}}(x_{1},\ldots,x_{L},x_{L-1})=2\sum_{j=1}^{(L-2)/2}\omega(i)+2\omega(L)$

and

$2\mathrm{max}_{\overline{\omega}}(x_{1},\ldots,x_{L-1},x_{L})=2\sum_{j=1}^{(L-3)/2}\omega(i)+\omega(L-1)+\omega(L).$

Thus Lemma 6 implies $f(P,\overline{\omega})>f(P,\omega^{\prime})\geq
f(P,\omega)$, a contradiction.

  3. 3.

$L$ is odd and only one component takes the minimum value. That is,
$\omega(1)=\omega(2)=\cdots=\omega(L-1)<\omega(L)$. Let $\omega^{\prime}$ be
obtained from $\omega^{\prime}$ by averaging-out the subset $\\{L-1,L_{2}\\}$.
Then $f(P,\omega^{\prime})\geq f(P,\omega)$ by Lemma 8 and moreover
$\omega^{\prime}$ is such that at least two coordinates take on the minimum
value, as
$\omega^{\prime}(1)=\cdots=\omega^{\prime}(L-2)>\omega^{\prime}(L-1)=\omega^{\prime}(L)$.
The argument from the previous case can now be applied to derive a
contradiction.

∎

Thus, except for degenerate choices for $P\in\Delta([q])$, it follows that the
function $\omega\mapsto f(P,\omega)$ is maximized by the choice of
$\omega=U_{L}$. The next step is to determine the distribution
$P\in\Delta([q])$ maximizing $P\mapsto f(P,U_{L})$. At this point, we can rely
on a main result of [RYZ22]: upon observing that the function $P\mapsto
1-f(P,U_{L})$ is the same as the function $f_{q,L}(P)$ defined in [RYZ22,
Equation (17)]. It is shown therein that $f_{q,L}(P)$ is _strictly Schur
convex_ , which in particular means that $f_{q,L}(P)$ has a unique minimum at
$P=U_{q}$. That is, $f(P,U_{L})$ has a unique maximum at $P=U_{q}$.

The (strict) Schur convexity also implies the following: if
$p=\max_{x\in[q]}P(x)$, then $f_{q,L}(P)\geq f_{q,L}(P_{q,p})$ where

$\displaystyle
P_{q,p}(x)=\begin{cases}\frac{1-p}{q-1}&x\in\\{1,2,\dots,q-1\\}\\\
p&x=q\end{cases}\ .$ (41)

That is, we can conclude that $f(P,U_{L})\leq f(P_{q,p},U_{L})$. We
encapsulate these facts in the following proposition.

######  Proposition 10 (Theorem 1,2 [RYZ22]).

Let $q\geq 2$, $L\geq q$ and $P\in\Delta([q])$. Suppose
$p=\max_{x\in[q]}P(x)$. Then $f(P,U_{L})\leq f(P_{q,p},U_{L})$. Furthermore,
$f(P_{q,p},U_{L})\leq f(U_{q},U_{L})$ is monotone decreasing for $p\geq 1/q$.
Lastly, $f(P_{q,p},U_{L})$ is concave for $p\in[1/q,1]$, i.e.,
$\frac{1}{n}\sum_{i=1}^{n}f(P_{q,p_{i}},U_{L})\leq f(P_{q,p},U_{L})$ with
$p=\frac{1}{n}\sum_{i=1}^{n}p_{i}$.

A further fact that we have from [RYZ22] is that

$p_{*}(q,L)=f(U_{q},U_{L})\ .$

In fact, this was taken as the definition of $p_{*}(q,L)$. To end this
subsection, we prove the following theorem by utilizing the concavity of
$f(P_{q,p},U_{L})$.

######  Theorem 11.

Assume $\operatorname{rad}_{\mathrm{H}}({\mathcal{C}})\leq p$, then we have

$\mathop{\mathbb{E}}_{({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{C}}^{L}}\left[\operatorname{rad}_{\omega}(\varphi({\boldsymbol{c}}_{1}),\ldots,\varphi({\boldsymbol{c}}_{L}))\right]\leq
f(P_{q,p},U_{L}).$

###### Proof.

Let ${\boldsymbol{y}}$ be the center attaining
$\operatorname{rad}_{\mathrm{H}}({\mathcal{C}})$. Without loss of generality,
we can assume ${\boldsymbol{y}}$ is a all zero vector. Let $P_{i}$ be the
distribution of symbols in the $i$-th index of ${\mathcal{C}}$, i.e.,
$P_{i}(j)=\Pr[{\boldsymbol{c}}(i)=j]$ with the distribution taken over
${\boldsymbol{c}}\in{\mathcal{C}}$. Let $p_{i}=\max_{x\in[q]}P_{i}(x)$ and
$p^{\prime}=\frac{1}{n}\sum_{i=1}^{n}p_{i}$. Clearly, $p_{i}\geq 1/q$. Then,
we have

$\displaystyle\mathop{\mathbb{E}}_{({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{C}}^{L}}\left[\operatorname{rad}_{\omega}(\varphi({\boldsymbol{c}}_{1}),\ldots,\varphi({\boldsymbol{c}}_{L}))\right]=\frac{1}{n}\sum_{i=1}^{n}f(P_{i},\omega)$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}f(P_{i},U_{L})\leq\frac{1}{n}\sum_{i=1}^{n}f(P_{q,p_{i}},U_{L})\leq
f(P_{q,p^{\prime}},U_{L})\leq f(P_{q,p},U_{L}).$

The first inequality is due to Lemma 7 and the second and third inequalities
are due to Proposition 10. The last inequality is due to
$\operatorname{rad}_{\mathrm{H}}({\mathcal{C}})\leq p$ and the center
${\boldsymbol{y}}$ is all zero vector. The proof is completed. ∎

###  3.3 Abundance of Random-Like $L$-tuples

Recall the notations

$\operatorname{rad}({\mathcal{C}})=\frac{1}{n}\min_{{\boldsymbol{y}}\in[q]^{n}}\max_{{\boldsymbol{c}}\in{\mathcal{C}}}d_{\mathrm{H}}({\boldsymbol{c}},{\boldsymbol{y}})$

and

$\mathsf{type}_{\boldsymbol{u}}({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})=\frac{1}{n}\sum_{i=1}^{n}\mathbb{1}\\{({\boldsymbol{c}}_{1}(i),\ldots,{\boldsymbol{c}}_{L}(i))={\boldsymbol{u}}\\}$

where
${\boldsymbol{c}}_{i}=({\boldsymbol{c}}_{i}(1),\ldots,{\boldsymbol{c}}_{i}(n))\in[q]^{n}$
and ${\boldsymbol{u}}\in[q]^{L}$. In this subsection, we prove a code
${\mathcal{C}}\subseteq[q]^{n}$ either contains a large subcode
${\mathcal{C}}^{\prime}\subseteq{\mathcal{C}}$ with radius
$\operatorname{rad}({\mathcal{C}}^{\prime})\leq 1-\frac{1}{q}-\varepsilon$, or
most of its $L$-tuples are of type close to the uniform distribution (for all
${\boldsymbol{u}}\in[q]^{L})$.

We first show that for any projection $\pi_{A}$ with $|A|\geq\mu n$ (for some
parameter $\mu\in[0,1]$), the projection $\pi_{A}({\mathcal{C}})$ almost
preserves the radius $\operatorname{rad}({\mathcal{C}})$ with small loss.
Then, if
$\operatorname{rad}({\mathcal{C}}^{\prime})>1-\frac{1}{q}-\varepsilon$ for any
subcode ${\mathcal{C}}^{\prime}$ with large size, we find a codeword
${\boldsymbol{c}}_{1}$ in ${\mathcal{C}}$ whose symbols’ distribution is close
to the uniform. In fact, most codewords in ${\mathcal{C}}$ satisfies this
requirement. Let $A_{i}$ be the index set of ${\boldsymbol{c}}_{1}$ taking
value $i$. We apply $\pi_{A_{i}}$ to ${\mathcal{C}}$ and claim that
$\pi_{A_{i}}({\mathcal{C}})$ preserves the radius. Thus, we can find a
codeword ${\boldsymbol{c}}_{2}$ such that for every $i\in[q]$, the symbol’s
distribution of $\pi_{A_{i}}({\boldsymbol{c}}_{2})$ is close to uniform.
Moreover, most of codewords in ${\mathcal{C}}$ satisfy this requirement. The
proof is the completed by induction.

######  Lemma 12.

Let $\pi_{A}:[q]^{n}\rightarrow[q]^{A}$ be the projection on a set $A$ of size
$m$. Suppose ${\mathcal{C}}\subseteq[q]^{n}$ is a code of size $qs$ satisfying
$\operatorname{rad}_{\mathrm{H}}(\pi_{A}({\mathcal{C}}))\leq
1-\frac{1}{q}-\varepsilon$. Then, there exists a subcode
${\mathcal{C}}^{\prime}\subseteq{\mathcal{C}}$ of size at least $s$ such that
$\operatorname{rad}_{\mathrm{H}}({\mathcal{C}}^{\prime})\leq
1-\frac{1}{q}-\frac{m}{n}\varepsilon$.

###### Proof.

Let $\pi_{\bar{A}}$ be the projection on the remaining $n-m$ coordinates. By
the pigeonhole principle, there exists a subcode ${\mathcal{C}}^{\prime}$ of
size at least $\frac{|{\mathcal{C}}|}{q}$ such that for any codeword
${\boldsymbol{c}}^{\prime}\in{\mathcal{C}}^{\prime}$, the most frequent symbol
of $\pi_{\bar{A}}({\boldsymbol{c}}^{\prime})$ is the same. Without loss of
generality, we assume this majority symbol is $0$. Let
${\boldsymbol{y}}\in[q]^{A}$ be the center attaining
$\operatorname{rad}_{\mathrm{H}}(\pi_{A}({\mathcal{C}}))$. Define
${\boldsymbol{z}}\in[q]^{n}$ to be ${\boldsymbol{y}}$ on $A$ and $0$
elsewhere, i.e.

$z_{i}=\begin{cases}y_{i}&i\in A\\\ 0&i\notin A\end{cases}.$

For any codeword ${\boldsymbol{c}}^{\prime}\in{\mathcal{C}}^{\prime}$, we have

$\displaystyle d_{\mathrm{H}}({\boldsymbol{c}}^{\prime},{\boldsymbol{z}})$
$\displaystyle=d_{\mathrm{H}}(\pi_{A}({\boldsymbol{c}}^{\prime}),{\boldsymbol{y}})+d_{\mathrm{H}}(\pi_{\bar{A}}({\boldsymbol{c}}^{\prime}),{\boldsymbol{y}}^{\prime})\leq
m\left(1-\frac{1}{q}-\varepsilon\right)+(n-m)\left(1-\frac{1}{q}\right)$
$\displaystyle\leq n\left(1-\frac{1}{q}\right)-m\varepsilon.$

Thus, $\operatorname{rad}_{\mathrm{H}}({\mathcal{C}}^{\prime})\leq
1-\frac{1}{q}-\frac{m}{n}\varepsilon$, as claimed. ∎

######  Theorem 13.

Let $L$ be fixed. For every $\varepsilon>0$, there exists a $\delta>0$ with
the following property. If $s$ is a natural number, there exist constants
$M_{0}=M_{0}(s)$ and $c(s)$ such that for any code
${\mathcal{C}}\subseteq[q]^{n}$ with size $M\geq M_{0}$, at least one of the
following must hold:

  1. 1.

There exists ${\mathcal{C}}^{\prime}\subseteq{\mathcal{C}}$ such that
$|{\mathcal{C}}^{\prime}|\geq s$ and
$\operatorname{rad}_{\mathrm{H}}({\mathcal{C}}^{\prime})\leq
1-\frac{1}{q}-\delta$.

  2. 2.

There exist at least $M^{L}-c(s)M^{L-1}$ many $L$-tuples of distinct codewords
$({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})$ in ${\mathcal{C}}$ such
that for all ${\boldsymbol{u}}\in[q]^{L}$ we have

$|\mathsf{type}_{\boldsymbol{u}}({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})-q^{-L}|\leq\varepsilon$

and thus

$|\overline{\operatorname{rad}}_{\omega}(\varphi({\boldsymbol{c}}_{1}),\cdots,\varphi({\boldsymbol{c}}_{L}))-f(U_{q},\omega)|\leq
q^{L}\varepsilon.$

###### Proof.

Let $\varepsilon$ satisfy
$\left|\left(\frac{1}{q}-(q-1)\delta_{0}\right)^{L}-q^{-L}\right|\leq\varepsilon$
and $\mu=\left(\frac{1}{q}-(q-1)\delta_{0}\right)^{L}$,
$\delta=\mu\delta_{0}$. Set $M_{0}(s)=q^{L+1}s$. We assume that the first
statement does not hold and our goal is to show that the second statement must
hold. Since the first statement does not hold, for any
${\boldsymbol{y}}\in[q]^{n}$, there exists a codeword
${\boldsymbol{c}}\in{\mathcal{C}}$ with
$d_{\mathrm{H}}({\boldsymbol{c}},{\boldsymbol{y}})>n\left(1-\frac{\ell}{q}-\delta\right)$.
For each ${\boldsymbol{c}}\in{\mathcal{C}}$, let
$\lambda_{\boldsymbol{c}}\in{\mathcal{X}}$ be the most frequent symbol of
${\boldsymbol{c}}$. By the pigeonhole principle, we can find a subcode
${\mathcal{C}}^{\prime}\subseteq{\mathcal{C}}$ of size at least $\frac{M}{q}$
such that $\lambda_{\boldsymbol{c}}$ for
${\boldsymbol{c}}\in{\mathcal{C}}^{\prime}$ are the same $\lambda$. Let
$\lambda\cdot\mathbf{1}=(\lambda,\lambda,\ldots,\lambda)\in[q]^{n}$. It is
clear that
$\operatorname{rad}({\mathcal{C}}^{\prime})\leq\frac{1}{n}\max_{{\boldsymbol{c}}\in{\mathcal{C}}^{\prime}}d_{\mathrm{H}}({\boldsymbol{c}},\lambda\cdot\mathbf{1}).$
As $M>qs$, this implies
$d_{\mathrm{H}}({\boldsymbol{c}}_{1},\lambda\cdot\mathbf{1})>\left(1-\frac{1}{q}-\delta\right)n$
for some ${\boldsymbol{c}}_{1}\in{\mathcal{C}}^{\prime}$. (In fact, there
exist at least $M-qs$ such ${\boldsymbol{c}}_{1}$ as we can remove
${\boldsymbol{c}}_{1}$ from ${\mathcal{C}}^{\prime}$ and obtain the same
conclusion.) Note that necessarily
$d_{\mathrm{H}}({\boldsymbol{c}}_{1},\lambda\cdot\mathbf{1})\leq\left(1-\frac{1}{q}\right)n$
(otherwise $\lambda$ would not be the element agreeing the most with
${\boldsymbol{c}}_{1}$). Let $A_{x}=\\{i\in[n]:c_{1}(i)=x\\}$ for $x\in[q]$.
This implies

$\frac{|A_{x}|}{n}\in\left[\frac{1}{q}-(q-1)\delta,\frac{1}{q}+\delta\right]\subseteq\left[\frac{1}{q}-(q-1)\delta_{0},\frac{1}{q}+\delta_{0}\right],$

as
$\max_{x\in[q]}\frac{|A_{x}|}{n}\in\left[\frac{1}{q},\frac{1}{q}+\delta\right]$
and
$\min_{x\in[q]}\frac{|A_{x}|}{n}\in\left[\frac{1}{q}-(q-1)\delta,\frac{1}{q}\right]$.

Now we fix ${\boldsymbol{c}}_{1}$ and its index set $A_{1},\ldots,A_{q}$ and
let ${\mathcal{C}}^{\prime}={\mathcal{C}}\setminus\\{{\boldsymbol{c}}_{1}\\}$.
We consider the punctured code $\pi_{A_{1}}({\mathcal{C}})$. According to
Lemma 12, there exists a subcode
${\mathcal{C}}^{\prime\prime}\subseteq{\mathcal{C}}$ of size at most $qs-1$
with $\operatorname{rad}_{\ell}(\pi_{A_{1}}({\mathcal{C}}^{\prime\prime}))\leq
1-\frac{\ell}{q}-\delta_{0}$. Therefore, the same argument as above shows that
there exists at least $M-2qs$ codewords ${\boldsymbol{c}}_{2}\in{\mathcal{C}}$
such that the symbol distribution of $\pi_{A_{1}}({\boldsymbol{c}}_{2})$ is
close to uniform, i.e., $|\\{i\in
A_{1}:{\boldsymbol{c}}_{2}(i)=x\\}|/|A_{1}|\in\left[\frac{1}{q}-(q-\ell)\delta_{0},\frac{1}{q}+\delta_{0}\right]$
for each $x\in[q]$. Then, we apply this argument with sets
$A_{2},\ldots,A_{q}$ sequentially and conclude that there exists at least
$M-2q^{2}s-1$ codewords ${\boldsymbol{c}}_{2}\in{\mathcal{C}}$ (excluding
${\boldsymbol{c}}_{1}$) such that the symbol distribution of each
$\pi_{A_{x}}({\boldsymbol{c}}_{2})$ is close to uniform.

We next partition $[n]$ into $q^{2}$ sets
$A_{xy}=\\{i\in[n]:{\boldsymbol{c}}_{1}(i)=x,{\boldsymbol{c}}_{2}(j)=y\\}$ for
$x,y\in[q]$ according to the value of ${\boldsymbol{c}}_{1}$ and
${\boldsymbol{c}}_{2}$. This gives
$\frac{|A_{xy}|}{n}\in\left[\left(\frac{1}{q}-(q-1)\delta_{0}\right)^{2},\left(\frac{1}{q}+\delta_{0}\right)^{2}\right]$.
One can continue this process and construct $L$-tuples
${\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L}$ for which necessarily

$\displaystyle\forall{\boldsymbol{u}}\in[q]^{L},~{}~{}~{}|\mathsf{type}_{\boldsymbol{u}}({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})-q^{-L}|\in\left[\left(\frac{1}{q}-(q-1)\delta_{0}\right)^{L},\left(\frac{1}{q}+\delta_{0}\right)^{L}\right]$
(42)

In general, there are more than

$N_{1}=\prod_{i=0}^{L-1}(M-j-2q^{i+1}s)$

$L$-tuples $({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})$ satisfying
Equation 42. This implies $N_{1}\geq M^{L}-cM^{L-1}$ where $c$ only depends on
$q$ and $L$. The proof is completed.

∎

###  3.4 Putting Everything Together

The argument follows the same line of reasoning as [ABP18]. We provide the
proof for completeness. Define
$\rho_{L}({\mathcal{C}})=\min\operatorname{rad}(\varphi({\boldsymbol{c}}_{1}),\ldots,\varphi({\boldsymbol{c}}_{L}))$
with minimum taken over all $L$-tuples
$({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{C}}^{L}$ with
distinct elements, where we recall that $\operatorname{rad}$ denotes the
_relaxed_ Chebyshev radius (Definition 3).

######  Theorem 14.

Let $L\geq 2$ and $q\geq 3$. If ${\mathcal{C}}\subseteq[q]^{n}$ is
$(p_{*}(q,L)+\varepsilon,L)$-list-decodable, then
$|{\mathcal{C}}|=O_{q,L}(\frac{1}{\varepsilon})$.

###### Proof.

Shorthand $\tau_{L}=p_{*}(q,L)$ and $\tau_{p,L}=f(P_{q,p},U_{L})$ with
$P_{q,p}$ defined in Proposition 10. Note that $\tau_{p,L}<\tau_{L}$ if
$p>1/q$.

Our first step is to obtain a subcode
${\mathcal{C}}_{1}\subseteq{\mathcal{C}}$ with
$\rho({\mathcal{C}}_{1})\geq\tau_{L}+\varepsilon$. By the list-decodability
assumption on ${\mathcal{C}}$, for any $L$-tuple
$({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{C}}^{L}$ with
distinct elements, we have
$\operatorname{rad}_{\mathrm{H}}({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\geq\tau_{L}+\varepsilon$.
To apply Lemma 3, we want this Hamming metric radius slightly larger. To do
this, we find a subcode ${\mathcal{C}}_{1}\subseteq{\mathcal{C}}$ such that
all codewords in ${\mathcal{C}}_{1}$ have the same prefix of length $rL$ where
$r=\lfloor 1/(\tau_{L}+\varepsilon)\rfloor$. By the pigeonhole principle,
$|{\mathcal{C}}_{1}|\geq q^{-rL}|{\mathcal{C}}|$. Removing these $rL$ indices
we obtain a code ${\mathcal{C}}_{2}$ for which, for all
$({\boldsymbol{c}}_{1},\dots,{\boldsymbol{c}}_{L})\in{\mathcal{C}}_{2}^{L}$
with distinct elements, we have

$\operatorname{rad}_{\mathrm{H}}({\boldsymbol{c}}_{1},\dots,{\boldsymbol{c}}_{L})\geq\frac{n}{n-rL}(\tau_{L}+\varepsilon)\geq\left(1+\frac{rL}{n}\right)\tau_{L}+\varepsilon\geq\tau_{L}+\varepsilon+\frac{L}{n}\
.$

Applying Lemma 3, we find that
$\rho_{L}({\mathcal{C}}_{2})\geq\tau_{L}+\varepsilon$ or equivalently
$\operatorname{rad}({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\geq\tau_{L}+\varepsilon$
for any $L$-tuple $({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})$ with
distinct elements. We divide our discussion into two cases.

  * •

Suppose $\operatorname{rad}_{\mathrm{H}}({\mathcal{C}}_{2})\leq
1-\frac{1}{q}-\delta$ for some constant $\delta>0$. Let $p=\frac{1}{q}+\delta$
and ${\boldsymbol{y}}$ the center attaining
$\operatorname{rad}_{\mathrm{H}}({\mathcal{C}}_{2})$. By ordering the elements
of ${\mathcal{C}}$ arbitrarily, we may identify ordered $L$-element tuples of
${\mathcal{C}}^{L}$ with distinct elements with $L$-element subsets of
${\mathcal{C}}$. For every such ordered $L$-tuple
$({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})$, there is a weight
$\omega\in\Omega_{L}$ that solves

$\operatorname{rad}(\varphi({\boldsymbol{c}}_{1}),\ldots,\varphi({\boldsymbol{c}}_{L}))=\max_{\omega\in\Omega_{L}}\overline{\operatorname{rad}}_{\omega}(\varphi({\boldsymbol{c}}_{1}),\cdots,\varphi({\boldsymbol{c}}_{L})).$

Each solution $\omega$ gives a coloring of $L$-element subsets of
${\mathcal{C}}_{2}$: we assign color $\omega$ to the $L$-element subset if
$\omega$ is a maximizer (breaking ties arbitrarily). As this coloring has at
most $|\Omega_{L}|$ colors and Lemma 5 promises $|\Omega_{L}|=O_{q,L}(1)$ (in
particular, it’s finite), by the hypergraph version of Ramsey’s theorem
[GRS91, Theorem 2] it follows that if ${\mathcal{C}}_{2}$ is large enough,
there is a monochromatic subset ${\mathcal{C}}_{3}\subseteq{\mathcal{C}}_{2}$
of size exceeding $L^{2}/(\tau_{L}-\tau_{p,L})$.

On the other hand, let ${\mathcal{T}}$ be the set of all ordered $L$-tuples of
distinct codewords in ${\mathcal{C}}_{3}$. If
$({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})$ is an $L$-tuple selected
uniformly at random in ${\mathcal{C}}_{3}^{L}$, then
$\Pr[({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\notin{\mathcal{T}}]\leq\frac{\binom{L}{2}}{|{\mathcal{C}}_{3}|}<\tau_{L}-\tau_{p,L}$.
Since $\operatorname{rad}_{\mathrm{H}}({\mathcal{C}}_{3})\leq 1-p$, by Theorem
11 and Proposition 10, we have

$\displaystyle\tau_{p,L}$
$\displaystyle\geq\mathop{\mathbb{E}}_{({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{C}}_{3}^{L}}\left[\overline{\operatorname{rad}}_{\omega}(\varphi({\boldsymbol{c}}_{1}),\cdots,\varphi({\boldsymbol{c}}_{L}))\right]$
$\displaystyle\geq\Pr[({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{T}}]\mathop{\mathbb{E}}_{({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{T}}}\left[\overline{\operatorname{rad}}_{\omega}(\varphi({\boldsymbol{c}}_{1}),\cdots,\varphi({\boldsymbol{c}}_{L}))\right].$

This implies there exists an $L$-tuple of distinct codewords
${\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L}$ in ${\mathcal{C}}_{3}$ such
that

$(1-\tau_{L}+\tau_{p,L})\overline{\operatorname{rad}}_{\omega}(\varphi({\boldsymbol{c}}_{1}),\cdots,\varphi({\boldsymbol{c}}_{L}))<\tau_{p,L}.$

It follows that

$\overline{\operatorname{rad}}_{\omega}(\varphi({\boldsymbol{c}}_{1}),\cdots,\varphi({\boldsymbol{c}}_{L}))<\tau_{p,L}+\tau_{L}-\tau_{p,L}=\tau_{L}$

as
$\overline{\operatorname{rad}}_{\omega}(\varphi({\boldsymbol{c}}_{1}),\cdots,\varphi({\boldsymbol{c}}_{L}))\leq
1$. Contradiction.

  * •

Otherwise, let ${\mathcal{H}}$ be the collection of all $L$-tuples
$({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})$ in
${\mathcal{C}}_{2}^{L}$ such that

$\overline{\operatorname{rad}}_{\omega}(\varphi({\boldsymbol{c}}_{1}),\cdots,\varphi({\boldsymbol{c}}_{L}))>\tau_{L}$

for some $\omega\neq U_{L}$. Let
$\varepsilon_{0}=q^{-L}\min\\{\tau_{L}-f(U_{q},\omega):\omega\in\Omega_{L}\\}$;
since $\omega\mapsto f(U_{q},\omega)$ is uniquely maximized by $U_{L}$
(Theorem 9) and $\Omega_{L}$ is finite (Lemma 5), $\varepsilon_{0}>0$. By
Theorem 13 applied with $\varepsilon=\varepsilon_{0}$, there exist at least
$|{\mathcal{C}}_{2}|^{L}-c|{\mathcal{C}}_{2}|^{L-1}$ many $L$-tuples of
distinct codewords ${\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L}$ in $C$
such that

$\overline{\operatorname{rad}}_{\omega}(\varphi({\boldsymbol{c}}_{1}),\cdots,\varphi({\boldsymbol{c}}_{L}))\leq
f(U_{q},\omega)+q^{L}\varepsilon_{0}\leq\tau_{L}.$

Thus, $|{\mathcal{H}}|\leq c|{\mathcal{C}}_{2}|^{L-1}$ where $c$ depends only
on $q$ and $L$. Let $({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})$ be a
random $L$-tuple in ${\mathcal{C}}_{2}^{L}$. The probability that
$({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})$ are $L$ distinct
codewords is at least
$1-\frac{\binom{L}{2}}{|{\mathcal{C}}_{2}|}=O(\frac{1}{|{\mathcal{C}}_{2}|})$.
The probability that
$({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{H}}$ is at
most $O(\frac{1}{|{\mathcal{C}}_{2}|})$. This implies
$\Pr[({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{T}}\setminus{\mathcal{H}}]\geq
1-O(\frac{1}{|{\mathcal{C}}_{2}|})$. Thus,

$\displaystyle\tau_{L}$ $\displaystyle\geq$
$\displaystyle\mathop{\mathbb{E}}_{({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{C}}_{2}^{L}}\left[\overline{\operatorname{rad}}_{U_{L}}(\varphi({\boldsymbol{c}}_{1}),\cdots,\varphi({\boldsymbol{c}}_{L}))\right]$
$\displaystyle\geq$
$\displaystyle\Pr[({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{T}}\setminus{\mathcal{H}}]\mathop{\mathbb{E}}_{({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{T}}\setminus{\mathcal{H}}}\left[\overline{\operatorname{rad}}_{U_{L}}(\varphi({\boldsymbol{c}}_{1}),\cdots,\varphi({\boldsymbol{c}}_{L}))\right]$
$\displaystyle\geq$
$\displaystyle\left(1-O\left(\frac{1}{|{\mathcal{C}}_{2}|}\right)\right)\mathop{\mathbb{E}}_{({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{T}}\setminus{\mathcal{H}}}\left[\overline{\operatorname{rad}}_{U_{L}}(\varphi({\boldsymbol{c}}_{1}),\cdots,\varphi({\boldsymbol{c}}_{L}))\right]\
.$

On the other hand, for any
$({\boldsymbol{c}}_{1},\dots,{\boldsymbol{c}}_{L})\in{\mathcal{T}}\setminus{\mathcal{H}}$,

$\overline{\operatorname{rad}}_{U_{L}}(\varphi({\boldsymbol{c}}_{1}),\cdots,\varphi({\boldsymbol{c}}_{L}))\geq\rho({\mathcal{C}}_{2})\geq\tau_{L}+\varepsilon.$

This implies that $|{\mathcal{C}}_{2}|\leq O_{q,L}(\frac{1}{\varepsilon})$ and
thus also $|{\mathcal{C}}|\leq O_{q,L}(\frac{1}{\varepsilon})$. ∎

##  4 Zero-Rate List-Recovery

In this section, we show how our results on list-decoding can naturally be
extended to list-recovery. As many of the ideas are the same, we mostly focus
upon indicating the changes that need to be made for this more general
setting.

###  4.1 Linear Programming Relaxation

First, we can similarly prove that $\operatorname{rad}$ is close to
$\operatorname{rad}_{\ell}$ by designing a linear programming relaxation.

######  Lemma 15 ($\operatorname{rad}$ is close to
$\operatorname{rad}_{\ell}$).

Let ${\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L}\in[q]^{n}$. Denote by
${\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L}\in(\partial\Delta_{\ell})^{n}$
the images of ${\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L}$ under the
embedding $\varphi_{\ell}$. Then

$\displaystyle\operatorname{rad}_{\ell}({\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L})$
$\displaystyle\leq\operatorname{rad}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})+\frac{L}{n}.$

###### Proof.

Suppose
$n\cdot\operatorname{rad}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})=t$.
Then there exists ${\boldsymbol{y}}\in\Delta_{\ell}^{n}$ such that for every
$i\in[L]$,

$d({\boldsymbol{x}}_{i},{\boldsymbol{y}})\leq t,$

That is, the following polytope is nonempty:

$\left\\{{\boldsymbol{y}}\in\Delta^{n}:\forall
i\in[L],\;d({\boldsymbol{x}}_{i},{\boldsymbol{y}})\leq t\right\\}\\\
=\left\\{(y(j,A))_{(j,A)\in[n]\times{\mathcal{X}}}:\begin{array}[]{l}\forall(j,k)\in[n]\times{\mathcal{X}},\,y(j,A)\geq
0,\\\ \forall j\in[n],\,\sum_{A\in{\mathcal{X}}}y(j,A)=1,\\\ \forall
i\in[L],\,\frac{1}{2}\sum_{j=1}^{n}\left(\sum_{A\in{\mathcal{X}}_{{\boldsymbol{c}}_{i}(j)}}(1-y(j,A))+\sum_{A\in{\mathcal{X}}\setminus{\mathcal{X}}_{{\boldsymbol{c}}_{i}(j)}}y(j,A)-\binom{q-1}{\ell-1}+1\right)\leq
t\end{array}\right\\}.$ (43)

Equivalently, the following linear program (LP) is feasible:

$\displaystyle\begin{array}[]{cl}\max\limits_{(y(j,A))_{(j,A)\in[n]\times{\mathcal{X}}}}&0\\\
\mathrm{s.t.}&\forall(j,A)\in[n]\times{\mathcal{X}},\,y(j,A)\geq 0,\\\
&\forall j\in[n],\,\sum_{A\in{\mathcal{X}}}y(j,A)=1,\\\ &\forall
i\in[L],\,\frac{1}{2}\sum_{j=1}^{n}\left(\sum_{A\in{\mathcal{X}}_{{\boldsymbol{c}}_{i}(j)}}(1-y(j,A))+\sum_{A\in{\mathcal{X}}\setminus{\mathcal{X}}_{{\boldsymbol{c}}_{j}(j)}}y(j,A)-\binom{q-1}{\ell-1}+1\right)\leq
t.\end{array}$ (48)

Similar to the list decoding case, our LP can be written as

$\displaystyle\begin{array}[]{cl}\max\limits_{{\boldsymbol{y}}\in{\mathbb{R}}^{\binom{q}{\ell}n},{\boldsymbol{z}}\in{\mathbb{R}}^{L}}&0\\\
\mathrm{s.t.}&\begin{bmatrix}A&I_{L}\\\
B&0\end{bmatrix}\begin{bmatrix}{\boldsymbol{y}}\\\
{\boldsymbol{z}}\end{bmatrix}=\begin{bmatrix}t\boldsymbol{1}_{L}\\\
\boldsymbol{1}_{n}\end{bmatrix},\\\
&{\boldsymbol{y}},{\boldsymbol{z}}\geq\boldsymbol{0}.\end{array}$ (52)

where $A$ is an $L\times\binom{q}{\ell}n$ matrix and $B$ is an
$n\times\binom{q}{\ell}n$ matrix encoding the third and second constraints in
the LP problem. By Proposition 27, there exists a basic feasible solution
${\boldsymbol{y}},{\boldsymbol{z}}$ with at most $n+L$ nonzero components and
thus ${\boldsymbol{y}}=(y(j,A))_{(j,A)\in[n]\times{\mathcal{X}}}$ has at most
$n+L$ nonzeros. Since $\sum_{A\in{\mathcal{X}}}y(j,T)=1$, at least one of
$y(j,T),T\in{\mathcal{X}}$ are nonzero. This implies that there are at least
$n-L$ choices for $j\in[n]$ such that
$(y(j,T))_{T\in{\mathcal{X}}}={\boldsymbol{e}}_{S}$ for some
$S\in{\mathcal{X}}$. We proceed to construct the set
${\boldsymbol{Y}}=(Y_{1},\ldots,Y_{n})\in{\mathcal{X}}^{n}$. If
${\boldsymbol{y}}_{j}={\boldsymbol{e}}_{S}$, we set $Y_{j}=S$. Since there are
at least $n-L$ indices $j$ with ${\boldsymbol{y}}_{j}={\boldsymbol{e}}_{S}$
for some $S\in{\mathcal{X}}$, we have at most $L$ $Y_{j}$ yet to be determined
which are set to be any $\ell$-subsets in ${\mathcal{X}}$. By construction,
the difference between
$d_{\mathrm{LR}}({\boldsymbol{c}}_{i},{\boldsymbol{Y}})$ and
$d({\boldsymbol{x}}_{i},{\boldsymbol{y}})$ is at most $L$. The proof is
completed. ∎

We further relax rad by defining the weighted average $\ell$-radius. For
${\boldsymbol{x}}_{1},\ldots,{\boldsymbol{x}}_{L}\in(\partial\Delta_{\ell})^{n}$
and $\omega\in\Delta([L])$, let

$\displaystyle\overline{\operatorname{rad}}_{\omega,\ell}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})$
$\displaystyle\coloneqq\frac{1}{n}\min_{{\boldsymbol{y}}\in\Delta_{\ell}^{n}}\mathop{\mathbb{E}}_{i\sim\omega}\left[d({\boldsymbol{x}}_{i},{\boldsymbol{y}})\right]=\frac{1}{n}\min_{{\boldsymbol{y}}\in\Delta_{\ell}^{n}}\sum_{i\in[L]}\omega(i)d({\boldsymbol{x}}_{i},{\boldsymbol{y}}).$

We can minimize each component of ${\boldsymbol{y}}(A)$ so as to obtain the
minimization of the above function. Suppose
${\boldsymbol{x}}_{1},\ldots,{\boldsymbol{x}}_{L}\in(\partial\Delta_{\ell})^{n}$
are the images of ${\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L}\in[q]^{n}$
under the embedding $\varphi_{\ell}$. Then,

$\displaystyle\overline{\operatorname{rad}}_{\omega,\ell}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})=\frac{1}{n}\min_{{\boldsymbol{y}}\in\Delta_{\ell}^{n}}\sum_{i\in[L]}\omega(i)d({\boldsymbol{x}}_{i},{\boldsymbol{y}})$
$\displaystyle=\frac{1}{2n}\min_{{\boldsymbol{y}}\in\Delta_{\ell}^{n}}\sum_{i\in[L]}\omega(i)\sum_{j=1}^{n}\left(\sum_{A\in{\mathcal{X}}_{{\boldsymbol{c}}_{i}(j)}}(1-{\boldsymbol{y}}_{j}(A))+\sum_{A^{\prime}\in{\mathcal{X}}\setminus{\mathcal{X}}_{{\boldsymbol{c}}_{i}(j)}}{\boldsymbol{y}}_{j}(A^{\prime})-\binom{q-1}{\ell-1}+1\right)$
$\displaystyle=\frac{1}{2n}\min_{({\boldsymbol{y}}_{1},\ldots,{\boldsymbol{y}}_{n})\in\Delta_{\ell}^{n}}\sum_{j=1}^{n}\left[\sum_{i\in[L]}\omega(i)\bigg{(}\sum_{A\in{\mathcal{X}}_{{\boldsymbol{c}}_{i}(j)}}(1-{\boldsymbol{y}}_{j}(A))+\sum_{A^{\prime}\in{\mathcal{X}}\setminus{\mathcal{X}}_{{\boldsymbol{c}}_{i}(j)}}{\boldsymbol{y}}_{j}(A^{\prime})-\binom{q-1}{\ell-1}+1\bigg{)}\right]$
$\displaystyle=\frac{1}{2n}\sum_{j=1}^{n}\min_{{\boldsymbol{y}}_{j}\in\Delta_{\ell}}\left[\sum_{i\in[L]}\omega(i)(2-2\sum_{A\in{\mathcal{X}}_{{\boldsymbol{c}}_{i}(j)}}{\boldsymbol{y}}_{j}(A))\right]$
$\displaystyle=\frac{1}{n}\sum_{j=1}^{n}\min_{{\boldsymbol{y}}_{j}\in\Delta_{\ell}}\left[1-\sum_{i\in[L]}\omega(i)\sum_{A\in{\mathcal{X}}_{{\boldsymbol{c}}_{i}(j)}}{\boldsymbol{y}}_{j}(A)\right]$
$\displaystyle=1-\frac{1}{n}\sum_{j=1}^{n}\max_{{\boldsymbol{y}}_{j}\in\Delta_{\ell}}\left[\sum_{i\in[L]}\omega(i)\sum_{A\in{\mathcal{X}}_{{\boldsymbol{c}}_{i}(j)}}{\boldsymbol{y}}_{j}(A)\right]$
$\displaystyle=1-\frac{1}{n}\sum_{j=1}^{n}\max_{A\in{\mathcal{X}}}\sum_{\begin{subarray}{c}i\in[L]\\\
{\boldsymbol{c}}_{i}(j)\in A\end{subarray}}\omega(i).$ (53)

Equation 53 is due to the fact that the maximizer ${\boldsymbol{y}}^{*}$ to
the following problem

$\max_{{\boldsymbol{y}}\in\Delta_{\ell}}\sum_{i\in[L]}\omega(i)\sum_{A\in{\mathcal{X}}_{x_{i}}}{\boldsymbol{y}}(A)=\max_{{\boldsymbol{y}}\in\Delta_{\ell}}\sum_{A\in{\mathcal{X}}}{\boldsymbol{y}}(A)\sum_{\begin{subarray}{c}i\in[L]\\\
x_{i}\in A\end{subarray}}\omega(i).$

is obtained from a set $A\in{\mathcal{X}}$ that maximizes
$\sum_{\begin{subarray}{c}i\in[L],x_{i}\in A\end{subarray}}\omega(i)$ and
setting ${\boldsymbol{y}}^{*}={\boldsymbol{e}}_{A}$.

Clearly

$\overline{\operatorname{rad}}_{\omega,\ell}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})\leq\operatorname{rad}({\boldsymbol{x}}_{1},\ldots,{\boldsymbol{x}}_{L}).$

Similarly, we can prove that rad is equal to the maximum
$\overline{\operatorname{rad}}_{\omega,\ell}$ over $\omega$.

######  Lemma 16 ($\operatorname{rad}$ equals maximum
$\overline{\operatorname{rad}}_{\omega}$).

For any
${\boldsymbol{x}}_{1},\ldots,{\boldsymbol{x}}_{L}\in(\partial\Delta_{\ell})^{n}$,

$\operatorname{rad}({\boldsymbol{x}}_{1},\ldots,{\boldsymbol{x}}_{L})=\max_{\omega\in\Delta([L])}\overline{\operatorname{rad}}_{\omega,\ell}({\boldsymbol{x}}_{1},\ldots,{\boldsymbol{x}}_{L}).$

###### Proof.

The proof is exactly the same as in Lemma 7. We observe that

$\displaystyle\operatorname{rad}({\boldsymbol{x}}_{1},\cdots,{\boldsymbol{x}}_{L})$
$\displaystyle\coloneqq\frac{1}{n}\min_{{\boldsymbol{y}}\in\Delta_{\ell}^{n}}\max_{i\in[L]}d({\boldsymbol{x}}_{i},{\boldsymbol{y}})=\frac{1}{n}\min_{{\boldsymbol{y}}\in\Delta_{\ell}^{n}}\max_{\omega\in\Delta([L])}\sum_{i\in[L]}\omega(i)d({\boldsymbol{x}}_{i},{\boldsymbol{y}}),$

Then, we apply von Neumann’s minimax theorem to interchange min and max. ∎

######  Lemma 17 ($\operatorname{rad}$ is achieved by finitely many $\omega$).

For every $L$ and $\ell$, there exists a finite set of probability measure
$\Omega_{\ell,L}\subseteq\Delta([L])$ such that

$\operatorname{rad}({\boldsymbol{x}}_{1},\ldots,{\boldsymbol{x}}_{L})=\max_{\omega\in\Omega_{L}}\overline{\operatorname{rad}}_{\omega,\ell}({\boldsymbol{x}}_{1},\ldots,{\boldsymbol{x}}_{L}).$

for all
${\boldsymbol{x}}_{1},\ldots,{\boldsymbol{x}}_{L}\in\partial\Delta_{\ell}^{n}$.

###### Proof.

The proof is very similar to Lemma 5 except that our signatures are now maps
$[q]^{L}\to\binom{[q]}{\ell}$ which yields $\binom{q}{\ell}q^{L}$ hyperplanes
$H_{A,{\boldsymbol{u}}}=\\{\omega\in\Delta([L])\colon\sum_{i:{\boldsymbol{u}}(i)\in
A}\omega(i)\geq 1/\binom{q}{\ell}\\}$ for each $A\in\binom{[q]}{\ell}$ and
${\boldsymbol{u}}\in[q]^{L}$. Similarly, to see that the sets
$\Omega_{S}=\\{\omega\in\Delta([L])\colon S\text{ is a signature for
}\omega\\}$ for $S:[q]^{L}\to\binom{[q]}{\ell}$ are indeed convex polytopes
one must simply note that it is an intersection over
${\boldsymbol{u}}\in[q]^{L}$ of the convex polytopes

$\displaystyle\left\\{\omega\in\Delta([L])\colon\exists\text{ signature
}\right.$ $\displaystyle\left.S_{\omega}\text{ for }\omega\text{ s.t.
}S_{\omega}({\boldsymbol{u}})=S({\boldsymbol{u}})\right\\}$
$\displaystyle=\bigcap_{B\in\binom{[q]}{\ell}\setminus
S({\boldsymbol{u}})}\left\\{\omega\in\Delta([L])\colon\sum_{i:{\boldsymbol{u}}(i)\in
S({\boldsymbol{u}})}\omega(i)\geq\sum_{i:{\boldsymbol{u}}(i)\in
B}\omega(i)\right\\}\ .$

Lastly, the argument now uses Equation 53 in order to view the optimization as
a linear program. ∎

###  4.2 Properties of $f_{\ell}(P,\omega)$

We consider the expected weighted average $\ell$-radius of a sequence of
i.i.d. symbols. Let

$\displaystyle f_{\ell}(P,\omega)$
$\displaystyle\coloneqq\mathop{\mathbb{E}}_{(X_{1},\cdots,X_{L})\sim
P^{\otimes
L}}\left[\overline{\operatorname{rad}}_{\omega,\ell}({\boldsymbol{e}}_{X_{1}},\cdots,{\boldsymbol{e}}_{X_{L}})\right].$

where $P$ is a probability distribution over $[q]$. Using Equation 53, we have

$\displaystyle f_{\ell}(P,\omega)$
$\displaystyle=\mathop{\mathbb{E}}_{(X_{1},\cdots,X_{L})\sim P^{\otimes
L}}\left[1-\max_{A\in{\mathcal{X}}}\sum_{\begin{subarray}{c}i\in[L]\\\
X_{i}\in A\end{subarray}}\omega(i)\right]$
$\displaystyle=1-\sum_{(x_{1},\ldots,x_{L})\in[q]^{L}}\bigg{(}\prod_{i=1}^{L}P(x_{i})\bigg{)}\max_{A\in{\mathcal{X}}}\sum_{i\in[L]}\omega(i)\mathds{1}{\left\\{x_{i}\in
A\right\\}}.$ (54)

We define the shorthand notation

$\mathrm{max}_{\omega,\ell}(x_{1},\ldots,x_{L}):=\max_{A\in{\mathcal{X}}}\sum_{\begin{subarray}{c}i\in[L]\\\
x_{i}\in
A\end{subarray}}\omega(i),\qquad\mathrm{argmax}_{\omega,\ell}(x_{1},\ldots,x_{L}):=\operatorname*{argmax}_{A\in{\mathcal{X}}}\sum_{\begin{subarray}{c}i\in[L]\\\
x_{i}\in A\end{subarray}}\omega(i).$

for any $\omega\in\Delta([L])$ and $(x_{1},\ldots,x_{L})\in[q]^{L}$.

We again begin by establishing that $f_{\ell}(P,\omega)$ cannot decrease if
$\omega$ is replaced by $U_{L}$, in analogy to Lemma 7.

First, we give a criterion for increase, which is analogous to Lemma 6. The
proof is completely analogous to the previous proof and is therefore omitted.

######  Lemma 18.

Let $P\in\Delta([q])$ and $\omega\in\Delta([L])$. Suppose
$\omega(L-1)\neq\omega(L)$ and that $\overline{\omega}\in\Delta([L])$ is
obtained by averaging-out the last two coordinates of $\omega$. Suppose that
for all $(x_{1},\dots,x_{L})\in[q]^{L}$ we have

$\displaystyle\frac{1}{2}\left(\mathrm{max}_{\omega,\ell}(x_{1},\cdots,x_{L-1},x_{L})+\mathrm{max}_{\omega,\ell}(x_{1},\cdots,x_{L},x_{L-1})\right)$
$\displaystyle\geq\mathrm{max}_{\overline{\omega},\ell}(x_{1},\cdots,x_{L-1},x_{L}).$
(55)

Then $f(P,\overline{\omega})\geq f(P,\omega)$.

Furthermore, suppose that additionally there exists
$(x_{1},\dots,x_{L})\in[q]^{L}$ with $\prod_{i=1}^{L}P(x_{i})>0$ such that the
inequality in Equation 55 is strict. Then
$f(P,\overline{\omega})>f(P,\omega)$.

######  Lemma 19.

Let $\ell\geq 2$ and $q\geq 3$ with $\ell\leq q$. For any distribution $P$ and
$\omega\in\Delta([L])$, $f_{\ell}(P,\omega)\leq f_{\ell}(P,U_{L})$.

###### Proof.

Fix any $(x_{1},\cdots,x_{L})\in[q]^{L}$. Let $\omega\in\Delta([L])$ be non-
uniform. Without loss of generality, assume $\omega(L-1)\neq\omega(L)$ and let
$\overline{\omega}$ be obtained from $\omega$ by averaging-out the last two
coordinates. We will show Equation 55 holds, which suffices by Lemma 18.

Equation 55 clearly holds if $x_{L-1}=x_{L}$. We now assume $x_{L}=a$ and
$x_{L-1}=b$ with $a\neq b$. Let

$\omega^{(a)}=\sum_{\begin{subarray}{c}i\in[L-2]\\\
x_{i}=a\end{subarray}}\omega(i),\qquad\omega^{(b)}=\sum_{\begin{subarray}{c}i\in[L-2]\\\
x_{i}=a\end{subarray}}\omega(i)\ .$

Let $T=\mathrm{argmax}_{\overline{\omega},\ell}(x_{1},\ldots,x_{L})$. If
$x_{L-1},x_{L}\in T$, then Equation 55 holds trivially. Otherwise, we assume
at least one of them is not in $T$. Without loss of generality, we first
assume that $a\in T$ and $b\notin T$. This implies that
$\sum_{x_{i}=a}\overline{\omega}(i)\geq\sum_{x_{i}=b}\overline{\omega}(i)$ and
$\omega^{(a)}\geq\omega^{(b)}$. In this case, we have

$2\mathrm{max}_{\overline{\omega},\ell}(x_{1},\ldots,x_{L})=2\sum_{x_{i}\in
T\setminus\\{a\\}}\omega(i)+2\omega^{(a)}+\omega(L-1)+\omega(L).$

On the other hand,

$\mathrm{max}_{\omega,\ell}(x_{1},\ldots,x_{L-1},x_{L})\geq\sum_{x_{i}\in
T\setminus\\{a\\}}\omega(i)+\omega^{(a)}+\omega(L),$

and

$\mathrm{max}_{\omega,\ell}(x_{1},\ldots,x_{L},x_{L-1})\geq\sum_{x_{i}\in
T\setminus\\{a\\}}\omega(i)+\omega^{(a)}+\omega(L-1).$

Thus Equation 55 holds. It remains to consider the case both $a,b$ are not in
$T$. In this case, we observe that

$\mathrm{max}_{\omega,\ell}(x_{1},\ldots,x_{L-1},x_{L})\geq\sum_{x_{i}\in
T}\omega(i)=\sum_{x_{i}\in
T}\overline{\omega}(i)=\mathrm{max}_{\overline{\omega},\ell}(x_{1},\ldots,x_{L})$

and

$\mathrm{max}_{\omega,\ell}(x_{1},\ldots,x_{L},x_{L-1})\geq\sum_{x_{i}\in
T}\omega(i)=\sum_{x_{i}\in
T}\overline{\omega}(i)=\mathrm{max}_{\overline{\omega},\ell}(x_{1},\ldots,x_{L}).$

Thus Equation 55 always holds. ∎

######  Theorem 20.

Let $q>\ell\geq 2$, $L>\ell$ and $\omega\in\Delta([L])$. Assume $P(x)>0$ for
all $x\in[q]$.777This theorem is only applied with $P=U_{q}$ which clearly
satisfies this condition. Then $f_{\ell}(P,\omega)=f_{\ell}(P,U_{L})$ if and
only if $\omega=U_{L}$.

###### Proof.

To prove this claim, by Lemma 18 it suffices to show that for any non-uniform
$\omega\in\Delta([L])$ there exists a $(x_{1},\ldots,x_{L})\in[q]^{L}$, such
that Equation 55 strictly holds. Since $L>\ell\geq 2$, assume $L=\ell+a\geq 3$
with $a\geq 1$.

Suppose there exist two components $\omega(L),\omega(L-1)$ achieving the
minimum $\min_{i\in[L]}\omega(i)$. Let $\omega(j)$ be the maximum
$\max_{i\in[L]}\omega(i)$, which is necessarily strictly larger than
$\omega(L-1)$ and $\omega(L)$ (otherwise $\omega=U_{L}$). Let
$\omega^{\prime}$ be obtained from $\omega$ by averaging-out the coordinates
$L-1$ and $j$. Lemma 16 promises $f_{\ell}(P,\omega)\leq
f_{\ell}(P,\omega^{\prime})$. Clearly,
$\omega^{\prime}(L-1)>\overline{\omega}(L)$. We can continue this process
until there is only one component achieving the minimum of $\omega$ (note that
we will never obtain the uniform distribution, as it will always hold that
$\omega(L)<1/q$).

We may now assume $\omega(L)$ is smaller than any other component of $\omega$.
Let $x_{1}=x_{2}=\cdots=x_{a}=1$ and $x_{a+i}=i+1$ for $i=1,\ldots,\ell$. This
can be done as $q>\ell\geq 2$. It is clear that

$\mathrm{max}_{\omega,\ell}(x_{1},\cdots,x_{L-1},x_{L})=\sum_{i=1}^{L-1}\omega(i),\qquad\mathrm{max}_{\omega,\ell}(x_{1},\cdots,x_{L},x_{L-1})=\sum_{i=1}^{L-1}\omega(i).$

Let $\overline{\omega}\in\Delta([L])$ be obtained from $\omega$ by averaging-
out the last two coordinates. Then

$2\mathrm{max}_{\overline{\omega},\ell}(x_{1},\cdots,x_{L-1},x_{L})=2\sum_{i=1}^{L-2}\omega(i)+\omega(L-1)+\omega(L).$

As $\omega(L)<\omega(L-1)$, Equation 55 strictly holds. By Lemma 18, the proof
is completed. ∎

Now, we turn to maximizing the other derived function $P\mapsto
f_{\ell}(P,U_{L})$. The function $f_{\ell}(P,U_{L})$ is the same as the
function $1-f_{q,L,\ell}(P)$ from [RYZ22] where

$\displaystyle f_{q,L,\ell}(P)$
$\displaystyle\coloneqq\mathop{\mathbb{E}}_{(X_{1},\cdots,X_{L})\sim
P^{\otimes L}}\left[\mathsf{pl}_{\ell}(X_{1},\cdots,X_{L})\right].$

As before, we can rely on certain Schur convexity and convexity results from
[RYZ22].

######  Proposition 21 (Theorem 8, 9 [RYZ22]).

For any $q>\ell\geq 2$ and $L>\ell$, $f_{\ell}(P,U_{L})\leq
f_{\ell}(P_{q,\ell,p},U_{L})$ where $p=\max_{A\in{\mathcal{X}}}\sum_{i\in
A}P(i)$ and

$\displaystyle P_{q,\ell,p}(i)$
$\displaystyle=\begin{cases}\frac{1-p}{q-\ell},&1\leq i\leq q-\ell\\\
\frac{p}{\ell},&q-\ell+1\leq i\leq q\end{cases}.$ (56)

$f_{\ell}(P_{q,\ell,p},U_{L})\leq f_{\ell}(U_{q},U_{L})$ is monotone
decreasing for $p\geq\ell/q$. Moreover $f_{\ell}(P_{q,\ell,p},U_{L})$ is
concave for $p\in[0,1]$, i.e.,
$\frac{1}{n}\sum_{i=1}^{n}f_{\ell}(P_{q,\ell,p_{i}},U_{L})\leq
f_{\ell}(P_{q,\ell,p},U_{L})$ with
$p^{\prime}=\frac{1}{n}\sum_{i=1}^{n}p_{i}$.

As a corollory of the above we can prove the following.

######  Theorem 22.

Assume $\operatorname{rad}_{\ell}({\mathcal{C}})\leq p$, then we have

$\mathop{\mathbb{E}}_{({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{C}}^{L}}\left[\operatorname{rad}_{\omega,\ell}(\varphi_{\ell}({\boldsymbol{c}}_{1}),\ldots,\varphi_{\ell}({\boldsymbol{c}}_{L}))\right]\leq
f(P_{q,\ell,p},U_{L}).$

###### Proof.

Let ${\boldsymbol{Y}}$ be the center attaining
$\operatorname{rad}_{\ell}({\mathcal{C}})$. Without loss of generality, we
assume
${\boldsymbol{Y}}=(\\{q-\ell+1,\ldots,q\\},\ldots,\\{q-\ell+1,\ldots,q\\})$.
Let $P_{i}$ be the distribution of symbols in the $i$-th index of
${\mathcal{C}}$, i.e., $P_{i}(j)=\Pr[{\boldsymbol{c}}(i)=j]$ where
${\boldsymbol{c}}\in{\mathcal{C}}$ is a random codeword distributed uniformly
at random. Let $p_{i}=\max_{A\in{\mathcal{X}}}\sum_{j\in A}P_{i}(j)$ and
$p^{\prime}=\frac{1}{n}\sum_{i=1}^{n}p_{i}$. Then, we have

$\displaystyle\mathop{\mathbb{E}}_{({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{C}}^{L}}\left[\operatorname{rad}_{\omega,\ell}(\varphi_{\ell}({\boldsymbol{c}}_{1}),\ldots,\varphi_{\ell}({\boldsymbol{c}}_{L}))\right]=\frac{1}{n}\sum_{i=1}^{n}f_{\ell}(P_{i},\omega)$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}f_{\ell}(P_{i},U_{L})\leq\frac{1}{n}\sum_{i=1}^{n}f_{\ell}(P_{q,\ell,p_{i}},U_{L})\leq
f_{\ell}(P_{q,\ell,p^{\prime}},U_{L})\leq f(P_{q,\ell,p},U_{L}).$

The first inequality is due to Lemma 16 and the second and third inequalities
are due to Proposition 21. The last inequality is due to
$\operatorname{rad}_{\ell}({\mathcal{C}})\leq p$ and the form of the center
${\boldsymbol{Y}}$. The proof is completed. ∎

###  4.3 Abundance of Random-Like $L$-tuples

Recall
$\operatorname{rad}_{\ell}({\mathcal{C}})=\frac{1}{n}\min_{{\boldsymbol{Y}}\in{\mathcal{X}}^{n}}\max_{{\boldsymbol{c}}\in{\mathcal{C}}}d_{\mathrm{LR}}({\boldsymbol{c}},{\boldsymbol{Y}})$.
The goal now is to show that, unless ${\mathcal{C}}$ has a large biased
subcode, most $L$-tuples in ${\mathcal{C}}$ have a random-like type. The proof
is quite similar to the list-decoding case; we present here for completeness.

######  Lemma 23.

Let $\pi_{A}:[q]^{n}\rightarrow[q]^{A}$ be the projection on a set $A$ of size
$m$. Suppose ${\mathcal{C}}\subseteq[q]^{n}$ is a code of size
$\binom{q}{\ell}s$ satisfying
$\operatorname{rad}_{\ell}(\pi_{A}({\mathcal{C}}))\leq
1-\frac{\ell}{q}-\varepsilon$. Then, there exists a subcode
${\mathcal{C}}^{\prime}\subseteq{\mathcal{C}}$ of size at least $s$ such that
$\operatorname{rad}_{\ell}({\mathcal{C}}^{\prime})\leq
1-\frac{\ell}{q}-\frac{m}{n}\varepsilon$.

###### Proof.

The proof is similar as in Lemma 12. Let $\pi_{\bar{A}}$ be the projection on
the remaining $n-m$ indices. By the pigeonhole principle, there exist a
subcode ${\mathcal{C}}^{\prime}$ of size at least
$\frac{|{\mathcal{C}}|}{\binom{q}{\ell}}$ such that the $\ell$ most frequent
symbols of $\pi_{\bar{A}}({\boldsymbol{c}}^{\prime})$ is the same. Let $T$ be
this set and we have
$d_{\mathrm{LR}}(\pi_{\bar{A}}({\boldsymbol{c}}^{\prime}),{\boldsymbol{T}})\leq
1-\frac{\ell}{q}$ with
${\boldsymbol{T}}=(T,T,\ldots,T)\in{\mathcal{X}}^{\bar{A}}$. Let
${\boldsymbol{Y}}\in{\mathcal{X}}^{A}$ be the center attaining
$\operatorname{rad}_{\ell}(\pi_{A}({\mathcal{C}}))$. Define ${\boldsymbol{Z}}$
as
$\pi_{A}({\boldsymbol{Z}})={\boldsymbol{T}},\pi_{\bar{A}}({\boldsymbol{Z}})={\boldsymbol{Y}}$
and for any codeword ${\boldsymbol{c}}^{\prime}\in{\mathcal{C}}^{\prime}$, we
have

$\displaystyle d_{\mathrm{LR}}({\boldsymbol{c}}^{\prime},{\boldsymbol{Z}})$
$\displaystyle=d_{\mathrm{LR}}(\pi_{A}({\boldsymbol{c}}),{\boldsymbol{Y}})+d_{\mathrm{LR}}(\pi_{\bar{A}}({\boldsymbol{c}}^{\prime}),{\boldsymbol{T}})$
$\displaystyle\leq
m\left(1-\frac{\ell}{q}-\varepsilon\right)+(n-m)\left(1-\frac{\ell}{q}\right)\leq
n\left(1-\frac{\ell}{q}\right)-m\varepsilon.\qed$

######  Theorem 24.

Let $q,L,\ell$ be fixed. For every $\varepsilon>0$, there exists a $\delta>0$
with the following property. If $s$ is a natural number, there exist constants
$M_{0}=M_{0}(s)$ and $c(s)$ such that for any code
${\mathcal{C}}\subseteq[q]^{n}$ with size $M\geq M_{0}$, one of the following
two alternatives must hold:

  1. 1.

There exists ${\mathcal{C}}^{\prime}\subseteq{\mathcal{C}}$ such that
$|{\mathcal{C}}^{\prime}|\geq s$ and
$\operatorname{rad}_{\ell}({\mathcal{C}}^{\prime})\leq
1-\frac{\ell}{q}-\delta$.

  2. 2.

There exists at least $M^{L}-c(s)M^{L-1}$ many $L$ tuples of distinct
codewords ${\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L}$ in $C$ such that
for all ${\boldsymbol{u}}\in[q]^{L}$

$|\mathsf{type}_{\boldsymbol{u}}({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})-q^{-L}|\leq\varepsilon$

and so we have

$|\overline{\operatorname{rad}}_{\omega,\ell}(\varphi_{\ell}({\boldsymbol{c}}_{1}),\cdots,\varphi_{\ell}({\boldsymbol{c}}_{L}))-f_{\ell}(U_{q},\omega)|\leq
q^{L}\varepsilon\ .$

###### Proof.

Set $h=\binom{q}{\ell}$. Let $\varepsilon$ satisfy
$\left|\left(\frac{1}{q}-(q-\ell)\delta_{0}\right)^{L}-q^{-L}\right|\leq\varepsilon$
and $\mu=\left(\frac{1}{q}-(q-\ell)\delta_{0}\right)^{L}$,
$\delta=\mu\delta_{0}$. Set $M_{0}(s)=q^{L}hs$. We assume that the first
statement does not hold and our goal is to show that the second statement must
hold. Since the first statement does not hold, for any
${\boldsymbol{Y}}\in{\mathcal{X}}^{n}$, there exists a codeword
${\boldsymbol{c}}\in{\mathcal{C}}$ with
$d_{\mathrm{LR}}({\boldsymbol{c}},{\boldsymbol{Y}})>n\left(1-\frac{\ell}{q}-\delta\right)$.
For each ${\boldsymbol{c}}\in{\mathcal{C}}$, let
$T_{\boldsymbol{c}}\in{\mathcal{X}}$ be the collection of the $\ell$ most
frequent symbols. By the pigeonhole principle, we can find a subcode
${\mathcal{C}}^{\prime}\subseteq{\mathcal{C}}$ of size at least $\frac{M}{h}$
such that $T_{\boldsymbol{c}}$ for ${\boldsymbol{c}}\in{\mathcal{C}}^{\prime}$
are the same $T$. Let ${\boldsymbol{T}}=(T,T,\ldots,T)\in{\mathcal{X}}^{n}$ It
is clear that
$\operatorname{rad}_{\ell}({\mathcal{C}}^{\prime})\leq\frac{1}{n}\max_{{\boldsymbol{c}}\in{\mathcal{C}}^{\prime}}d_{\mathrm{LR}}({\boldsymbol{c}},{\boldsymbol{T}}).$
As $M>hs$, this implies
$d_{\mathrm{LR}}({\boldsymbol{c}}_{1},{\boldsymbol{T}})>\left(1-\frac{\ell}{q}-\delta\right)n$
for some ${\boldsymbol{c}}_{1}\in{\mathcal{C}}^{\prime}$. (In fact, there
exist at least $M-hs$ such ${\boldsymbol{c}}_{1}$ as we can remove
${\boldsymbol{c}}_{1}$ from ${\mathcal{C}}^{\prime}$ and obtain the same
conclusion.) Note that necessarily
$d_{\mathrm{LR}}({\boldsymbol{c}}_{1},{\boldsymbol{T}})\leq\left(1-\frac{\ell}{q}\right)n$
(otherwise $T$ would not be the $\ell$-element subset agreeing the most with
${\boldsymbol{c}}_{1}$). Let $A_{x}=\\{i\in[n]:{\boldsymbol{c}}_{1}(i)=x\\}$
for $x\in[q]$. This implies

$\frac{|A_{x}|}{n}\in\left[\frac{1}{q}-(q-\ell)\delta,\frac{1}{q}+\delta\right]\subseteq\left[\frac{1}{q}-(q-\ell)\delta_{0},\frac{1}{q}+\delta_{0}\right],$

as
$\max_{x\in[q]}\frac{|A_{x}|}{n}\in\left[\frac{1}{q},\frac{1}{q}+\delta\right]$
and
$\min_{x\in[q]}\frac{|A_{x}|}{n}\in\left[\frac{1}{q}-(q-\ell)\delta,\frac{1}{q}\right]$.

Now we fix ${\boldsymbol{c}}_{1}$ and its index set $A_{1},\ldots,A_{q}$ and
let ${\mathcal{C}}^{\prime}={\mathcal{C}}\setminus\\{{\boldsymbol{c}}_{1}\\}$.
We consider the punctured code $\pi_{A_{1}}({\mathcal{C}})$. According to
Lemma 23, there exists a subcode
${\mathcal{C}}^{\prime\prime}\subseteq{\mathcal{C}}$ of size at most $hs-1$
with $\operatorname{rad}_{\ell}(\pi_{A_{1}}({\mathcal{C}}^{\prime\prime}))\leq
1-\frac{\ell}{q}-\delta_{0}$. Therefore, the same argument as above shows that
there exists at least $M-2hs$ codewords ${\boldsymbol{c}}_{2}\in{\mathcal{C}}$
such that the symbol distribution of $\pi_{A_{1}}({\boldsymbol{c}}_{2})$ is
close to uniform, i.e., $|\\{i\in
A_{1}:{\boldsymbol{c}}_{2}(i)=x\\}|/|A_{1}|\in\left[\frac{1}{q}-(q-\ell)\delta_{0},\frac{1}{q}+\delta_{0}\right]$
for each $x\in[q]$. Then, we apply this argument with sets
$A_{2},\ldots,A_{q}$ sequentially and conclude that there exists at least
$M-2qhs-1$ (excluding ${\boldsymbol{c}}_{1}$) codewords
${\boldsymbol{c}}_{2}\in{\mathcal{C}}$ such that the symbol distribution of
each $\pi_{A_{x}}({\boldsymbol{c}}_{2})$ is close to uniform.

We next partition $[n]$ into $q^{2}$ sets
$A_{xy}=\\{i\in[n]:{\boldsymbol{c}}_{1}(i)=x,{\boldsymbol{c}}_{2}(j)=y\\}$ for
$x,y\in[q]$ according to the value of ${\boldsymbol{c}}_{1}$ and
${\boldsymbol{c}}_{2}$. This gives
$\frac{|A_{xy}|}{n}\in\left[\left(\frac{1}{q}-(q-\ell)\delta_{0}\right)^{2},\left(\frac{1}{q}+\delta_{0}\right)^{2}\right]$.
One can continue this process and construct $L$-tuples
${\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L}$ for which necessarily

$\displaystyle\forall{\boldsymbol{u}}\in[q]^{L},~{}~{}~{}|\mathsf{type}_{\boldsymbol{u}}({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})-q^{-L}|\in\left[\left(\frac{1}{q}-(q-\ell)\delta_{0}\right)^{L},\left(\frac{1}{q}+\delta_{0}\right)^{L}\right]$
(57)

In general, there are more than

$N_{1}=\prod_{i=0}^{L-1}(M-j-2q^{i}hs)$

$L$-tuples $({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})$ satisfying
Equation 57. This implies $N_{1}\geq M^{L}-cM^{L-1}$ where $c$ only depends on
$q$, $\ell$ and $L$. The proof is completed. ∎

###  4.4 Putting Everything Together

The proof is quite similar to the list-decoding case. We provide the proof for
completeness. Define
$\rho_{\ell}({\mathcal{C}})=\min\operatorname{rad}_{\ell}(\varphi_{\ell}({\boldsymbol{c}}_{1}),\ldots,\varphi_{\ell}({\boldsymbol{c}}_{L}))$
with minimum taken over all $L$-tuples
$({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in C^{L}$ with distinct
codewords.

######  Theorem 25.

Let $L\geq 2$ and $q,L>\ell\geq 2$. If ${\mathcal{C}}\subseteq[q]^{n}$ is
$(p_{*}(q,\ell,L)+\varepsilon,\ell,L)$-list recoverable, then
$|{\mathcal{C}}|=O_{q,\ell,L}(\frac{1}{\varepsilon})$.

###### Proof.

To simplify our notation, let $\tau_{\ell,L}=p_{*}(q,\ell,L)$ and
$\tau_{x,\ell,L}=f_{\ell}(P_{q,\ell,x},U_{L})$ with $P_{q,\ell,x}$ defined in
Proposition 21. Similar to the list-decoding case, by defining
${\mathcal{C}}_{1}$ to be the set of all ${\boldsymbol{c}}\in{\mathcal{C}}$
whose first $rL$ coordinates are some given string in $[q]^{rL}$ for
$r=\lfloor 1/(\tau_{L}+\varepsilon)\rfloor$, we can obtain a code
${\mathcal{C}}_{2}\subseteq[q]^{n-rL}$ of size at least
$q^{-rL}|{\mathcal{C}}|$ whose $\ell$-radius is at least
$\tau_{\ell,L}+\varepsilon+\frac{L}{n}$. Applying Lemma 15, we thus have a
subcode ${\mathcal{C}}_{2}\subseteq{\mathcal{C}}$ with
$\rho_{\ell}({\mathcal{C}}_{2})\geq\tau_{\ell,L}+\varepsilon$. We divide our
discussion into two cases.

  * •

$\operatorname{rad}_{\ell}({\mathcal{C}}_{2})\leq 1-\frac{\ell}{q}-\delta$ for
some constant $\delta>0$. Let $p=\frac{\ell}{q}+\delta$. For every
$({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{C}}_{1}^{L}$,
there exists a weight $\omega\in\Omega_{\ell,L}$ that solves

$\operatorname{rad}(\varphi_{\ell}({\boldsymbol{c}}_{1}),\ldots,\varphi_{\ell}({\boldsymbol{c}}_{L}))=\max_{\omega\in\Omega_{\ell,L}}\overline{\operatorname{rad}}_{\omega,\ell}(\varphi_{\ell}({\boldsymbol{c}}_{1}),\cdots,\varphi_{\ell}({\boldsymbol{c}}_{L})).$

Each solution $\omega$ gives a coloring of $L$-element subsets of
${\mathcal{C}}_{2}$. By Lemma 17, there are a finite number of $\omega$ in
$\Omega_{\ell,L}$. The hypergraph version of Ramesy’s theorem [GRS91, Theorem
2] implies that there exists a monochromatic subset
${\mathcal{C}}_{3}\subseteq{\mathcal{C}}_{2}$ exceeding
$\frac{L^{2}}{\tau_{\ell,L}-\tau_{p,\ell,L}}$.

On the other hand, let ${\mathcal{T}}$ be the set of all $L$-tuples with
distinct codewords in ${\mathcal{C}}_{3}$. Let
$({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})$ be an $L$-tuple selected
uniformly at random in ${\mathcal{C}}_{3}^{L}$. Then

$\Pr[({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\notin{\mathcal{T}}]\leq\frac{\binom{L}{2}}{|C_{3}|}<\tau_{\ell,L}-\tau_{p,\ell,L}.$

Since $\operatorname{rad}_{\ell}({\mathcal{C}})\leq 1-\frac{\ell}{q}-\delta$,
by Lemma 16 and Proposition 21, we have

$\displaystyle\tau_{p,\ell,L}$ $\displaystyle\geq$
$\displaystyle\mathop{\mathbb{E}}_{({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{C}}_{3}^{L}}\left[\overline{\operatorname{rad}}_{\omega,\ell}(\varphi_{\ell}({\boldsymbol{c}}_{1}),\cdots,\varphi_{\ell}({\boldsymbol{c}}_{L}))\right]$
$\displaystyle\geq$
$\displaystyle\Pr[({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{T}}]\mathop{\mathbb{E}}_{({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{T}}}\left[\overline{\operatorname{rad}}_{\omega,\ell}(\varphi_{\ell}({\boldsymbol{c}}_{1}),\cdots,\varphi_{\ell}({\boldsymbol{c}}_{L}))\right].$

This implies that there exists an $L$-tuple of distinct codewords
${\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L}$ in ${\mathcal{C}}_{3}$ such
that

$(1-\tau_{\ell,L}+\tau_{p,\ell,L})\overline{\operatorname{rad}}_{\omega,\ell}(\varphi_{\ell}({\boldsymbol{c}}_{1}),\cdots,\varphi_{\ell}({\boldsymbol{c}}_{L}))<\tau_{p,\ell,L}.$

It follows that

$\overline{\operatorname{rad}}_{\omega,\ell}(\varphi_{\ell}({\boldsymbol{c}}_{1}),\cdots,\varphi_{\ell}({\boldsymbol{c}}_{L}))<\tau_{p,\ell,L}+\tau_{\ell,L}-\tau_{p,\ell,L}=\tau_{\ell,L}$

contradicting the assumption that
$\rho_{L}({\mathcal{C}}_{2})\geq\tau_{\ell,L}+\varepsilon$.

  * •

Otherwise, let ${\mathcal{H}}$ be the collection of all $L$-tuples
$({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})$ in
${\mathcal{C}}_{2}^{L}$ such that
$\overline{\operatorname{rad}}_{\omega,\ell}(\varphi_{\ell}({\boldsymbol{c}}_{1}),\cdots,\varphi_{\ell}({\boldsymbol{c}}_{L}))>\tau_{\ell,L}$
for some $\omega\neq U_{L}$. Let
$\varepsilon_{0}=q^{-L}\min\\{\tau_{\ell,L}-f_{\ell}(U_{q},\omega):\omega\in\Omega_{\ell,L}\\}$;
Theorem 20 and Lemma 17 guarantee $\varepsilon_{0}>0$. By Theorem 24, there
exists at least $|{\mathcal{C}}_{2}|^{L}-c|{\mathcal{C}}_{2}|^{L-1}$ many
$L$-tuples of distinct codewords
${\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L}$ in ${\mathcal{C}}_{2}$ such
that

$\overline{\operatorname{rad}}_{\omega,\ell}(\varphi_{\ell}({\boldsymbol{c}}_{1}),\cdots,\varphi({\boldsymbol{c}}_{L}))\leq
f_{\ell}(U_{q},\omega)+q^{L}\varepsilon_{0}\leq\tau_{\ell,L}.$

Thus, $|{\mathcal{H}}|\leq c|{\mathcal{C}}_{2}|^{L-1}$ where $c$ only depends
on $q,\ell,L$. Let $({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})$ be a
random $L$-tuple in ${\mathcal{C}}_{2}^{L}$. Similarly, we can show
$\Pr[({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{T}}\setminus{\mathcal{H}}]\geq
1-O(\frac{1}{|{\mathcal{C}}_{2}|})$ where the constant in $O$ only depends on
$q,\ell,L$ and

$\displaystyle\tau_{\ell,L}\geq\left(1-O\left(\frac{1}{|{\mathcal{C}}_{2}|}\right)\right)\mathop{\mathbb{E}}_{({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{T}}\setminus{\mathcal{H}}}\left[\overline{\operatorname{rad}}_{U_{L},\ell}(\varphi_{\ell}({\boldsymbol{c}}_{1}),\cdots,\varphi_{\ell}({\boldsymbol{c}}_{L}))\right]$

On the other hand,

$\overline{\operatorname{rad}}_{U_{L},\ell}(\varphi_{\ell}({\boldsymbol{c}}_{1}),\cdots,\varphi_{\ell}({\boldsymbol{c}}_{L}))\geq\rho_{\ell}({\mathcal{C}}_{1})\geq\tau_{\ell,L}+\varepsilon.$

for
$({\boldsymbol{c}}_{1},\ldots,{\boldsymbol{c}}_{L})\in{\mathcal{T}}\setminus{\mathcal{H}}$.
This implies that $|{\mathcal{C}}_{2}|\leq
O_{q,\ell,L}(\frac{1}{\varepsilon})$ and thus $|{\mathcal{C}}|\leq
O_{q,\ell,L}(\frac{1}{\varepsilon})$.

∎

##  5 Code Construction

In this section, we present a simple simplex-like code construction and show
that it attains the optimal size-radius trade-off by analyzing its list-
decoding and -recovery radius.

Our construction will be identical for list-decoding and -recovery and
therefore we will directly analyze its list-recovery radius. Before presenting
the construction and its analysis, let us define the average radius
$\overline{\operatorname{rad}}_{\ell}$. This is a standard notion that
“linearizes” the Chebyshev radius $\operatorname{rad}$ and often finds its use
in the analysis of list-recoverable codes in the literature. The definition
reads as follows: for any
${\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L}\in[q]^{n}$,

$\displaystyle\overline{\operatorname{rad}}_{\ell}({\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L})$
$\displaystyle\coloneqq\frac{1}{L}\min_{{\boldsymbol{Y}}\in{\mathcal{X}}^{n}}\sum_{i=1}^{L}d_{\mathrm{LR}}({\boldsymbol{c}}_{i},{\boldsymbol{Y}}).$

It is well-known and easy to verify (by, e.g., following the derivations
leading to Equation 37) that the above minimization admits the following
explicit solution:

$\displaystyle\overline{\operatorname{rad}}_{\ell}({\boldsymbol{c}}_{1},\cdots,{\boldsymbol{c}}_{L})$
$\displaystyle\coloneqq\sum_{j=1}^{n}\left(1-\frac{1}{L}\mathsf{pl}_{\ell}({\boldsymbol{c}}_{1}(j),\cdots,{\boldsymbol{c}}_{L}(j))\right),$
(58)

Equation 58 should be interpreted as the average distance from each
${\boldsymbol{c}}_{i}$ to the “centroid”
${\boldsymbol{Y}}^{*}\in{\mathcal{X}}^{n}$ of the list defined as888If there
are multiple maximizers, take an arbitrary one and the value of
$\overline{\operatorname{rad}}_{\ell}$ remains the same.

$\displaystyle{\boldsymbol{Y}}^{*}(j)$
$\displaystyle\coloneqq\operatorname*{argmax}_{A\in{\mathcal{X}}}\sum_{i=1}^{L}\mathds{1}{\left\\{{\boldsymbol{c}}_{i}(j)\in
A\right\\}}.$

for each $j\in[n]$.

Finally, for integers $q\geq 1$ and $L\geq 0$, denote by

$\displaystyle{\mathcal{A}}_{q,L}$