It has been known since [Zyablov and Pinsker 1982] that a random $q$-ary code of rate $1-H_q(\rho)-\eps$ (where $0<\rho<1-1/q$, $\eps>0$ and $H_q(\cdot)$ is the $q$-ary entropy function) with high probability is a $(\rho,1/\eps)$-list decodable code. (That is, every Hamming ball of radius at most $\rho n$ has at most $1/\eps$ codewords in it.) In this paper we prove the ``converse" result. In particular, we prove that for \emph{every} $0<\rho<1-1/q$, a random code of rate $1-H_q(\rho)-\eps$, with high probability, is not a $(\rho,L)$-list decodable code for any $L\le \frac{c}{\eps}$, where $c$ is a constant that depends only on $\rho$ and $q$. We also prove a similar lower bound for random linear codes.

Previously, such a tight lower bound on the list size was only known for the case when $\rho\ge 1-1/q-O(\sqrt{\eps})$ [Guruswami and Vadhan, 2005]. For binary codes a lower bound is known for all $0<\rho<1/2$, though the lower bound is asymptotically weaker than our bound [Blinovsky, 1986]. These results however are not subsumed by ours as they hold for arbitrary codes of rate $1-H_q(\rho)-\eps$.