Kakeya-type sets in finite vector spaces

Swastik Kopparty, Vsevolod F. Lev, Shubhangi Saraf, Madhu Sudan

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

For a finite vector space V and a nonnegative integer r≥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⊆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≥rq r-1, we have |V\K|=Θ(nq n-r+1); this improves the previously known bounds |V\K|=Ω(q n-r+1) and |V\K|=O(n 2 q n-r+1).

Original languageEnglish (US)
Pages (from-to)337-355
Number of pages19
JournalJournal of Algebraic Combinatorics
Volume34
Issue number3
DOIs
StatePublished - Nov 1 2011

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Discrete Mathematics and Combinatorics

Keywords

  • Finite field
  • Kakeya problem
  • Kakeya set
  • Polynomial method

Cite this