AG Codes Have No List-Decoding Friends: Approaching the Generalized Singleton Bound Requires Exponential Alphabets

A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rate R codes are not list-decodable using list-size L beyond an error fraction L / L +1 (1- R ) (the Singleton bound being the case of L = 1, i.e., unique decoding). We prove that in order to approach this bound for any fixed L > 1, one needs exponential alphabets. Specifically, for every L > 1 and R ∈ (0, 1), if a rate R code can be list-of- L decoded up to error fraction L / L +1 (1 - R - ε), then its alphabet must have size at least exp(Ω L,R (1/ε)). This is in sharp contrast to the situation for unique decoding where certain families of rate R algebraic-geometry (AG) codes over an alphabet of size O (1/ε 2 ) are unique-decodable up to error fraction (1 - R - ε)/2. Our bounds hold even for subconstant ε ≥ 1/ n , implying that any code exactly achieving the L -th generalized Singleton bound requires alphabet size 2 ΩL,R(n) . Previously this was only known only for L = 2 under the additional assumptions that the code is both linear and MDS. Our lower bound is tight up to constant factors in the exponent—with high probability random codes (or, as shown recently, even random linear codes) over exp( OL (1/ε))-sized alphabets, can be list-of- L decoded up to error fraction L / L +1 (1- R - ε).