The list size of random linear codes at capacity

Abstract

Let $C\le {\mathbb{F}}_q^n$ be a uniformly random ${\mathbb{F}}_q$-linear code of rate $1-h_q(\rho )-\epsilon$, and let $L^{\ast }(C,\rho )$ be the least $L$ such that every Hamming ball of relative radius $\rho$ contains at most $L$ codewords of $C$. That $L^{\ast }={\Theta }_{q,\rho }(1/\epsilon )$ has been known since work of Guruswami, Håstad and Kopparty and of Guruswami and Narayanan. Guruswami, Li, Mosheiff, Resch, Silas and Wootters proved that the constant in front of $1/\epsilon$ is at least $h_q(\rho )$ for all $q$, along with an upper bound special to $q=2$ which narrowed $L^{\ast }$ to within three consecutive integers in that case. But for $q\ge 3$ no upper bound with the correct constant was known. We determine $L^{\ast }$ for every prime power $q$. Let $\zeta :=h_q(\rho )/\epsilon$. For every sufficiently small $\epsilon$, with probability $1-o(1)$ over the choice of $C$, $$L^{\ast }(C,\rho )=\lceil \zeta \rceil ,$$ unless the fractional part of $\zeta$ is at most $q^{-{\Omega }_{q,\rho }(\zeta )}$, in which case $L^{\ast }(C,\rho )$ is $\lfloor \zeta \rfloor$ or $\lfloor \zeta \rfloor +1$. By the threshold characterization of random linear codes due to Mosheiff, Resch, Ron-Zewi, Silas and Wootters, both bounds reduce to a two-sided estimate of a single quantity $V(q,L,\rho )$, where $1-V(q,L,\rho )$ is the threshold rate for $(\rho ,L)$-list-decodability. We prove for all large $L$: $$h_q(\rho )(1+1/L)-q^{-{\Omega }_{q,\rho }(L)}\le V(q,L,\rho )\le h_q(\rho )(1+1/L).$$ The upper bound rests on a new entropy inequality for sparse random vectors under pairwise non-proportional linear constraints, proved with the Erdős-Rado sunflower lemma. The lower bound is an exact analysis of the distribution introduced by Guruswami, Li, Mosheiff, Resch, Silas and Wootters.