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.