Asymptotically Optimal List Size of Random Linear Codes

Abstract

We prove that for every fixed prime power $q$, every $p\in (0,1-1/q)$, and every $\epsilon >0$ with $1-H_q(p)-\epsilon >0$, a random linear code over ${\mathbb{F}}_q$ of rate $1-H_q(p)-\epsilon$ is $(p,\lceil \frac{H_q(p)}{\epsilon }\rceil +O_{p,q}(1))\text{-list-decodable}$ with probability at least $1-q^{-\Omega (n)}$. Guruswami, Li, Mosheiff, Resch, Silas, and Wootters showed that, for sufficiently small $\epsilon$, random linear codes require list size at least $\lfloor \frac{H_q(p)}{\epsilon }+0.99\rfloor ,$ and conjectured that $\frac{H_q(p)}{\epsilon }(1+o(1))$ suffices as $\epsilon \to 0$. This conjecture was previously known for $q=2$, where the upper bound $H_2(p)/\epsilon +2$ was established. For $q>2$, however, the best known upper bound was $C_{p,q}/\epsilon$ for a constant $C_{p,q}$ depending on $p$ and $q$. Our result resolves the conjecture for every prime power $q$ and, in fact, establishes the sharper upper bound $\frac{H_q(p)}{\epsilon }+O_{p,q}(1)$.

12 pages