Kakeya-type sets in finite vector spaces

Abstract

For a finite vector space $V$ and a non-negative integer $r\le \dim V$ we estimate the smallest possible size of a subset of $V$, containing a translate of every $r$-dimensional subspace. In particular, we show that if $K\subset V$ is the smallest subset with this property, $n$ denotes the dimension of $V$, and $q$ is the size of the underlying field, then for $r$ bounded and $r<n\le r{q}^{r-1}$ we have $|V\setminus K|=\Theta (n{q}^{n-r+1})$. This improves previously known bounds $|V\setminus K|=\Omega (q^{n-r+1})$ and $|V\setminus K|=O(n^2{q}^{n-r+1})$.