# Much weaker condition for Kakeya sets over finite fields

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$$?

• 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}$. Commented May 4, 2022 at 23:06

## 1 Answer

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?

• 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. Commented May 5, 2022 at 1:27
• 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). Commented May 5, 2022 at 1:33
• 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$. Commented May 5, 2022 at 1:44