List-Recovery of Random Linear Codes over Small Fields

For our first result, we consider $(\alpha ,\mathrm{\ell },L)$-list-recovery from erasures. Recall that the capacity in this case is

As mentioned before, [17] showed that there is a price to pay for linearity over fields of small characteristic. More precisely, they proved the following.

We show that this limitation disappears when considering a prime field size $q$. In this case, we can make the output list size $O_{\alpha ,\mathrm{\ell },q}(1/\epsilon )$.

While our focus is on the setting where $\alpha$ and $q$ are constants, we determine effective bounds on $C(\alpha ,\mathrm{\ell },q)$ even when $\alpha$ is a function of $n$, and $q$ is slightly super-constant.¹¹1For a concrete example, when $\mathrm{\ell }\le (1-\gamma )q$ for some constant $\gamma$, and $\alpha$ is bounded away from $1$, we can take $C(\alpha ,\mathrm{\ell },q)\le q^{O(\mathrm{\ell }\cdot \log q)}$ as long as $n\ge C(\alpha ,\mathrm{\ell },q)$. We refer the reader to Theorem 25 for the precise bound.

Next, we consider the case of list-recovery from errors, where we recall the capacity is

Here, contrary to what happens in the regime of large $q$-s, we do not observe any price to pay for linearity, at least in terms of the dependence on the gap-to-capacity $\epsilon$.

Again, we determine effective bounds on the numerator $C(\rho ,\mathrm{\ell },q)$, which can be found in Theorem 31.²²2Specifically, when $\rho$ is bounded away from both $0$ and $1-\mathrm{\ell }/q$, we can take $C(\rho ,\mathrm{\ell },q)\le q^{\mathrm{\ell }\cdot \mathrm{polylog}(q)}$. See Theorem 31 for the precise bound. For context, we recall that in the “large $q$ regime” (say, $q\gg {\mathrm{\ell }}^{1/\epsilon }$), such a result is provably impossible. Specifically, when $q$ is large, the list-recovery capacity is (essentially) the Singleton bound, namely, $R_{\mathrm{errors}}^{\ast }\approx 1-\rho$. It is known that at rate $1-\rho -\epsilon$, any linear code list-recoverable from errors must have $L\ge {\mathrm{\ell }}^{\mathrm{\Omega }(R/\epsilon )}$ [31]. That is, the dependence of $L$ on the gap-to-capacity must be exponential. But in our case, at least if $\rho ,\mathrm{\ell }$ and $q$ are held constant, the dependence of $L$ on $\epsilon$ is just $O(1/\epsilon )$.

We conclude this section with some remarks.

Firstly, observe that for a combinatorial rectangle $T_1\times \mathrm{\cdots }\times T_n$, if each of the sets $T_i$ is nontrivially mixing as a subset of ${𝔽}_q$ (take the $n=1$ case of the above definition), then $T_1\times \mathrm{\cdots }\times T_n$ is also nontrivially mixing (as a subset of ${𝔽}_q^n$). Hence, it suffices for us to consider whether or not subsets of ${𝔽}_q$ mix. It is here that the dependence on the field size shows up.

Recall from the earlier discussion that [17] established that random linear codes over ${𝔽}_{{\mathrm{\ell }}^t}$ (where $\mathrm{\ell }$ is a prime power) are with high probability not $(\alpha ,\mathrm{\ell },L)$-list-recoverable from erasures unless $L\ge {\mathrm{\ell }}^{\mathrm{\Omega }(1/\epsilon )}$. Indeed, it is easy to find a subset $T\subseteq {𝔽}_{{\mathrm{\ell }}^t}$ which is not $\delta$-mixing for any $\delta >0$: take $T={𝔽}_{\mathrm{\ell }}$ (or, more generally, any multiplicative coset $\gamma \cdot {𝔽}_{\mathrm{\ell }}$ for $\gamma \in {𝔽}_{{\mathrm{\ell }}^t}\setminus \{0\}$). Since ${𝔽}_{\mathrm{\ell }}$ is closed under addition, in particular we have that if $X$ and $X^{\prime }$ are sampled independently and uniformly from $T$ then $\mathrm{Pr}[X+X^{\prime }\in T]=1$, so $T$ is not $\delta$-mixing for any $\delta >0$.

What went wrong in this example? The fact that ${𝔽}_{{\mathrm{\ell }}^t}$ contains ${𝔽}_{\mathrm{\ell }}$ as a subfield means that ${𝔽}_{{\mathrm{\ell }}^t}$ contains non-trivial ${𝔽}_{\mathrm{\ell }}$-linear subspaces. Such subspaces naturally create “bad” input lists, and the argument of [17] establishes that indeed a random linear code is likely to contain many vectors from a combinatorial rectangle $T_1\times \mathrm{\cdots }\times T_n$ where at least a $(1-\alpha )$ fraction of the $T_i$’s are $1$-dimensional ${𝔽}_{\mathrm{\ell }}$-subspaces of ${𝔽}_{{\mathrm{\ell }}^t}$.

If we insist that $q$ be a prime, then ${𝔽}_q$ does not have any non-trivial subspaces. However, in this case ${𝔽}_q$ still contains some subsets with “additive structure;” for example, taking $\mathrm{\ell }$ to be odd here for simplicity, centered intervals⁴⁴4Or, more generally, arithmetic progressions. like $I=\{-\frac{\mathrm{\ell }-1}{2},-\frac{\mathrm{\ell }-1}{2}+1\mathrm{\dots },\frac{\mathrm{\ell }-1}{2}-1,\frac{\mathrm{\ell }-1}{2}\}\subseteq {𝔽}_q$ have the property that if one samples $X,X^{\prime }\sim I$ independently, then $\mathrm{Pr}[X+X^{\prime }\in I]\approx \frac{3}{4}+\frac{1}{4{\mathrm{\ell }}^2}$ assuming $\mathrm{\ell }\le 2q/3$. But note that this is still non-trivially bounded away from $1$! Remarkably, an argument of Lev [29] shows that this is the worst case over prime fields. More precisely, over all sets $T$ of size $\mathrm{\ell }$, to maximize $\mathrm{Pr}[\alpha X+\beta X^{\prime }\in \gamma +T]$ where $\alpha ,\beta ,\gamma \in {𝔽}_q$ with $\alpha ,\beta \ne 0$, one should choose $T=I$ (the centered interval of length $\mathrm{\ell }$), $\alpha =\beta =1$ and $\gamma =0$. In our technical section we give an effective bound on $\mathrm{Pr}[X+X^{\prime }\in I]$ for all , which allows us to argue that combinatorial rectangles $T_1\times \mathrm{\cdots }\times T_n$ in which at least a $1-\alpha$ fraction of the $T_i$’s have size at most $\mathrm{\ell }$ are nontrivially mixing, as desired.

We now wish to establish that list-recovery balls are nontrivially mixing. Notably, unlike in the case of erasures, the argument here is insensitive to the base field. Let $T=T_1\times \mathrm{\cdots }\times T_n$, where each $|T_i|\le \mathrm{\ell }$. Let $X,X^{\prime }\sim B_{\rho }(T)$; in this overview, we will sketch how one bounds $\mathrm{Pr}[X+X^{\prime }\in B_{\rho }(T)]$ (the argument easily generalizes to allow for multipliers $\alpha ,\beta \in {𝔽}_q\setminus \{0\}$ and a shift $y\in {𝔽}_q^n$).

Unlike in the case of combinatorial rectangles, it is not the case that $X=(X_1,\mathrm{\dots },X_n)$ and $X^{\prime }=(X_1^{\prime },\mathrm{\dots },X_n^{\prime })$ have independent coordinates. For example, conditioned on $X_1$ lying in $T_1$, then $X_2$ is less likely to lie in $T_2$. However, these correlations are relatively minor, and we can essentially “pretend” that both $X$ and $X^{\prime }$ are sampled as follows: for each $i\in [n]$, with probability $1-\rho$ set the $i$-th coordinate to a uniformly random element of $T_i$, and otherwise set it to a uniformly random element of ${𝔽}_q\setminus T_i$, and these choices are made independently for each $i\in [n]$.⁵⁵5In fact for technical reasons we have to consider $X_i$ lying in $T_i$ with probability $\omega$ for $\omega \le \rho$, and similarly $X_i^{\prime }$ lies in $T_i$ with probability ${\omega }^{\prime }\le \rho$. But by a concentration argument one can easily establish that $\omega$ and ${\omega }^{\prime }$ are with high probability very close to $\rho$. We remark that a similar trick is implicit in [12], and made explicit in the context of rank-metric codes by Guruswami and Resch [18].

This new distribution is much more amenable to analysis. In particular, letting $E_i$ be the indicator for the event $X_i+X_i^{\prime }\in T_i$, then $X+X^{\prime }\in B_{\rho }(T)$ iff ${\sum }_i{E}_i\ge (1-\rho )n$. Thus, if we can argue then a classic Chernoff-Hoeffding bound establishes $\mathrm{Pr}\left[{\sum }_i{E}_i\ge (1-\rho )n\right]$ is exponentially small, implying the desired $\delta$-mixing.

Bounding $\mathrm{Pr}[E_i=1]$ is the most novel part of the analysis, and is done in Lemma 26. Recall that $X_i,X_i^{\prime }\sim T_i$, and let also $Y_i,Y_i^{\prime }\sim {𝔽}_q\setminus T_i$. We have

As is standard, $\mathrm{Pr}[X_i+X_i^{\prime }=z_i]$ is proportional to $1_{T_i}\ast 1_{T_i}(z_i)$, the convolution of the indicator functions for $T_i$, and similarly $\mathrm{Pr}[X_i+Y_i^{\prime }=z_i]$ and $\mathrm{Pr}[Y_i+Y_i^{\prime }=z_i]$ are proportional to $1_{T_i}\ast 1_{{𝔽}_q\setminus T_i}(z_i)$ and $1_{{𝔽}_q\setminus T_i}\ast 1_{{𝔽}_q\setminus T_i}(z_i)$, respectively. Using the simple identity $1_{{𝔽}_q\setminus T_i}=1-1_{T_i}$, we can rewrite Equation 2 as

where $c$ is a constant which we show to be positive assuming $\rho \in (0,1-\mathrm{\ell }/q)$ (and indeed, if $\rho >1-\mathrm{\ell }/q$ then it could be negative). Upon giving a trivial upper bound $1_{T_i}\ast 1_{T_i}(z_i)$ (which corresponds to the case that $T_i$ does not mix at all, as we must do since we are making no assumptions on the field) and simplifying, we obtain the bound

To our satisfaction, we have that iff $\rho \in (0,1-\mathrm{\ell }/q)$, which is precisely the range of decoding radius at which we can hope for positive rate list-recovery from errors in the first place! Thus, we have that $\mathrm{Pr}\left[{\sum }_i{E}_i\ge (1-\rho )n\right]$ is exponentially small, establishing that list-recovery balls nontrivially mix.

We begin with the relevant definition.

We will also consider list-recovery from errors. The concept of a list-recovery ball – which generalizes that of a Hamming ball – will be useful.

We now state the relevant capacity theorem for list-recovery from erasures. The proofs of the two implications are standard: the possibility result follows from analyzing the performance of a plain random code, while the impossibility result follows from a counting argument.

We therefore say that the capacity for $(\alpha ,\mathrm{\ell },L)$-list-recovery from erasures is $1-\alpha -(1-\alpha ){\log }_q\mathrm{\ell }$. We will study what happens for codes of rate $1-(1-\alpha ){\log }_q\mathrm{\ell }-\alpha -\epsilon$ for some $\epsilon >0$, and determine the value of their output list-size $L$. We will be focused on the case where $q$ is held constant, and the gap-to-capacity $\epsilon$ tends to $0$.

We now define what it means for a code to be list-recoverable from errors.

We will need an estimate on the size of list-recovery balls. It makes use of the $(q,\mathrm{\ell })$-entropy function, defined as follows:

An operational interpretation of this quantity is as the base-$q$ entropy of a random variable which, with probability $1-x$, samples a uniformly random element from a set of size $\mathrm{\ell }$, and with probability $x$ samples a uniformly random element from the complement. Additionally, so long as it holds that . Note that if $\mathrm{\ell }=1$ one recovers the $q$-entropy function, which we denote as $h_q$ (i.e., if $\mathrm{\ell }$ is omitted from the subscript, then it is by default $1$).

We now state the relevant estimate.

This estimate drives the following capacity theorem.

Thus, we will concern ourselves with codes of rate $1-h_{q,\mathrm{\ell }}(\rho )-\epsilon$, and determine the output list size $L$ for $(\rho ,\mathrm{\ell },L)$-list-recovery from errors. And, as in the list-recovery from erasures case, we will hold $\rho ,\mathrm{\ell },q$ constants and consider the asymptotic behaviour of $L$ as the gap-to-capacity $\epsilon \to 0$.

We will also need the following lower bound on the difference $h_{q,\mathrm{\ell }}(\rho )-h_{q,\mathrm{\ell }}(\rho -\eta )$. See the full version of the paper [3] for the proof.