Kakeya-type sets in finite vector spaces

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 rq^{r-1}$ we have $|V\setminus K|=Θ(nq^{n-r+1})$. This improves previously known bounds $|V\setminus K|=Ω(q^{n-r+1})$ and $|V\setminus K|=O(n^2q^{n-r+1})$.

No reviews yet.

No comments yet.