Query complexity of sampling and small geometric partitions

Abstract

In this paper we study the following problem: Discrete partitioning problem (DPP): Let ${\mathbb{F}}_q{P}^n$ denote the $n$-dimensional finite projective space over ${\mathbb{F}}_q$. For positive integer $k\le n$, let $\{A^i{\}}_{i=1}^N$ be a partition of $({\mathbb{F}}_q{P}^n{)}^k$ such that (1) for all $i\le N$, $A^i={\prod }_{j=1}^k{A}_j^i$ (partition into product sets), (2) for all $i\le N$, there is a $(k-1)$-dimensional subspace $L^i\subseteq {\mathbb{F}}_q{P}^n$ such that $A^i\subseteq (L^i{)}^k$. What is the minimum value of $N$ as a function of $q,n,k$? We will be mainly interested in the case $k=n$.

References in corpus (1)

• On the size of Kakeya sets in finite fields