Kakeya-type sets in finite vector spaces
Kakeya-type sets in finite vector spaces
复制标题
有限向量空间中的挂屋型集合
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
M. Sudan
中科院分区：
文献类型：
--
作者：
Swastik Kopparty;V. Lev;Shubhangi Saraf;M. Sudan
对于有限向量空间V和非负整数r≤dim V，我们估计V的子集的最小可能大小，该子集包含每个r维子空间的平移。特别地，我们证明了如果K <$V是具有此性质的最小子集，n表示V的维数，q是基础域的大小，则对于r有界且r<n≤rqr−1，我们有|V K| =Θ（nqn−r+1）;这改进了先前已知的边界|V K| =Ω（qn−r+1），|V K|时间复杂度为O（n2 qn −r+1）。
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≤rqr−1, we have |V∖K|=Θ(nqn−r+1); this improves the previously known bounds |V∖K|=Ω(qn−r+1) and |V∖K|=O(n2qn−r+1).