A subspace-evasive set over a field F is a subset of Fn that has small intersection with any low-dimensional affine subspace of Fn. Interest in subspace evasive sets began in the work of Pudlák and Rödl (Quaderni di Matematica 2004). More recently, Guruswami (CCC 2011) showed that obtaining such sets over large fields can be used to construct capacity-achieving list-decodable codes with a constant list size.

Our results in this note are as follows:

1. We provide a construction of subspace-evasive sets in Fn of size F(1−)n that intersect any k-dimensional affine subspace of Fn in at most (2)k points. This slightly improves a recent construction of Dvir and Lovett (STOC 2012), who constructed similar sets, but with a bound of (k)k on the size of the intersection. Besides having a smaller intersection, our construction is more elementary. The construction is explicit when k and are constants. This is sufficient in order to explicitly construct the aforementioned list-decodable codes.

2. We show, using the Kövári-Sós-Turán Theorem, that for a certain range of the parameters