5
$\begingroup$

What is the minimum size of a subset $S \subseteq \mathbb{F}_p^n$ such that for all directions $a \in \mathbb{F}_p^n$, there is a line in direction $a$ that intersects $S$ in at least $C$ points?

If $C = p$ this is exactly the finite field Kakeya problem, and we know $|S| \ge C_n p^n$ by the proof of Dvir in On the size of Kakeya sets in finite fields. However, I am curious what bounds we can show if e.g. $C$ is much smaller than $p$, eg. $C = \log^{O(1)}(pn)$.

I believe by random sampling, one can show an upper bound of something like $\lvert S\rvert \le p^{(1-1/C)n}$, which is trivial for $C = \log^{O(1)}(pn)$. A lower bound of $\lvert S\rvert \ge p^{(n-1)/2}$ is also clear, because the points in $S$ determine at most $\lvert S\rvert^2$ lines.

Also, in Dvir's paper, he also handles the case where $C = p^{1-\epsilon}$, but I am asking for even much smaller values of $C$. So is the truth closer to $p^{n/2}$ or $p^n$?

Improve this question
$\endgroup$
1
  • $\begingroup$ The paper of Dvir gets a bound for any $C$ - the $C=p^{1-\epsilon}$ is just for getting a lower bound of size $p^{n (1-\epsilon)}$ - but it's of size a bit less than $C^n$, so it's worse than the points determine lines lower bound for $C < \sqrt{p}$. $\endgroup$
    – Will Sawin
    Commented May 4, 2022 at 23:06

1 Answer 1

Reset to default
9
$\begingroup$

As claimed in equation (2) of this recent paper

Dhar, Manik; Dvir, Zeev; Lund, Ben, Simple proofs for Furstenberg sets over finite fields, ZBL07471814 [arXiv].

one can get a lower bound of $2^{-n} C^n$ by adapting the arguments from

Bukh, Boris; Chao, Ting-Wei, Sharp density bounds on the finite field Kakeya problem, ZBL07471810. [arXiv]

For $C=p$ the bound is tight up to a factor of $2$. I don't know what to conjecture for other values of $C$.

EDIT: for $C=2$ I would imagine by the usual union bound argument that a random set of cardinality $p^{n/2} n^{10} \log^{10} p$ (say) should work to give a upper bound, though I haven't checked this carefully. So maybe the truth is something like $p^{n/2} C^{n/2}$ up to lower order terms?

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ Your guess at the end suggests that one can achieve $C=3$ with a set of size $p^{ n (1/2 +o(1))}$. Here's an argument that this might not be possible: If this occurs, then the probability that two random points in the set are colinear with a third point in the set is at least $p^{- o(n)}$. This should imply the set is highly additively structured. But highly additively structured sets are the least likely to contain two points on a line in an arbitrary direction. $\endgroup$
    – Will Sawin
    Commented May 5, 2022 at 1:27
  • 1
    $\begingroup$ Hmm, good point, my initial guess was too naive and there does seem to be some sort of discontinuity when going from $C=2$ to $C=3$. Probably one has to work harder at trying all kinds of constructions before arriving at a tentative prediction (but then again, there was no consensus on what to conjecture for cap sets until Dvir's breakthrough). $\endgroup$
    – Terry Tao
    Commented May 5, 2022 at 1:33
  • $\begingroup$ Thanks for the answers! And yes, as mentioned in the original post, random sampling (or other constructions) do achieve an upper bound of $p^{(1-1/C)n}$ up to polynomial factors in $p, n$, which is $p^{n/2}$ for $C = 2$. $\endgroup$
    – yangpliu
    Commented May 5, 2022 at 1:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .