A q-ary error-correcting code C \subseteq {1,2,...,q}^n is said to be
list decodable to radius \rho with list size L if every Hamming ball of radius \rho
contains at most L codewords of C. We prove that in order for a q-ary code to be
list-decodable up to radius (1-1/q)(1-\eps)n, we must have L = Omega(1/\eps^2).
Specifically, we prove that there exists a constant c_q>0 and a function f_q
such that for small enough \eps > 0, if C is list-decodable to radius
(1-1/q)(1-\eps)n with list size c_q/\eps^2, then C has at most f_q(\eps)
codewords, independent of n. This result is asymptotically tight (treating q as
a constant), since such codes with an exponential (in n) number of codewords are
known for list size L = O(1/\eps^2).
A result similar to ours is implicit in Blinovsky (1986) for the binary (q=2)
case. Our proof works for all alphabet sizes, and is technically and
conceptually simpler.