Source-linked AI summary
Sharp density bounds on the finite field Kakeya problem
Boris Bukh, Ting-Wei Chao
TL;DR
The paper asks how sharply one can lower-bound the density of finite-field Kakeya sets. It uses high-order polynomial vanishing, with conditions depending on the lines through each point, to improve the lower bound and close the factor-of-two gap in all dimensions.
Problem
The paper addresses the gap between known lower bounds for finite-field Kakeya sets and constructions attaining density 1/2^{n−1}.
Source: Our result · p. 2, Stronger result · p. 3Method
The proof uses polynomials vanishing to high order at Kakeya points, with vanishing conditions depending on the lines through each point.
Source: Proof outline · p. 3, Hasse derivatives and high-order… · p. 4Results
The lower bound improves by a factor of 2−1/q, closing the factor-of-two gap in all dimensions.
Source: Our result · p. 2Takeaways & Limitations
The resulting bound matches the known construction up to the stated lower-order gap discussion.
Source: Our result · p. 2, §4 · p. 8The discussion notes a remaining gap between the improved bound and known constructions in lower-order terms.
Source: §4 · p. 8
Abstract
from arXiv · showhide
A Kakeya set in $\mathbb{F}_q^n$ is a set containing a line in every direction. We show that every Kakeya set in $\mathbb{F}_q^n$ has density at least $1/2^{n-1}$, matching the construction by Dvir, Kopparty, Saraf and Sudan.
1 Introduction
The paper studies lower bounds for finite-field Kakeya sets, improving the known bound by a factor of 2−1/q and closing the factor-of-two gap in every dimension.
Kakeya sets in finite fields.
- Saraf and Sudan improved the lower-bound constant from 1/n! to c−n for some c ≈ 2.5 and presented a Kakeya-set construction of size 2−n+1q^n + O_n(q^n−1) [5].Source: Kakeya sets in finite fields · p. 1
- The only previously noted result breaching that gap was the three-dimensional bound |K| ≥ 0.2107q^3 of Lund, Saraf and Wolf [4].Source: Kakeya sets in finite fields · p. 1
Our result.
- The authors improve the lower bound by a factor of 2−1/q, closing the factor-of-two gap in all dimensions.Source: Our result · p. 2
Paper organization.
- The paper first presents a weaker dimension-three proof, then proves the general theorem and discusses the remaining gap to known constructions.Source: Paper organization · p. 2
2 Simple argument in dimension 3
The dimension-three argument uses polynomials vanishing to order two on a Kakeya set and shows that such a polynomial must be zero, yielding a size lower bound through codimension counting.
Simple argument in dimension 3
- Polynomials vanishing to order 2 at every point of a Kakeya set are forced to be the zero polynomial.Source: §2 · pp. 2–3
- For any point in F_q^3, order-two vanishing imposes four linear conditions, so vanishing on K has codimension at most 4|K|.Source: §2 · p. 2
- The proof restricts the polynomial to each Kakeya line, where order-two vanishing and a degree bound force the resulting univariate polynomial to vanish identically.Source: §2 · p. 3
- Writing the top homogeneous component as Q(x_1,x_2)=P_d(x_1,x_2,1), vanishing on F_q^2 and degree restrictions imply Q, and hence P_d, is zero, contradicting deg P=d.Source: §2 · p. 3
3 Proof of Theorem 1
The proof strengthens the target theorem by using direction-dependent high-order vanishing conditions on polynomials, together with Hasse derivatives and a dimension count. Restricting these polynomials to selected non-horizontal lines forces them to vanish identically, yielding the lower bound.
Stronger result.
- The proof establishes a result slightly stronger than Theorem 1 for sets containing lines in every non-horizontal direction.Non-horizontal directions use direction vectors whose last coordinate is 1.Source: Stronger result · p. 3
Proof outline.
- The argument uses anisotropic polynomial spaces, Hasse derivatives, and vanishing conditions that depend on the lines passing through each point.The exponent of x_n is less constrained, while line-dependent conditions provide the factor-of-two improvement.Source: Proof outline · p. 3, Hasse derivatives and high-order… · pp. 3–4
Hasse derivatives and high-order vanishing along lines.
- Hasse derivatives define multiplicity over finite fields and remain compatible with affine changes, while line multiplicity is defined through univariate restrictions.The generalized Schwartz–Zippel lemma states that a nonzero polynomial vanishing to order r everywhere has degree at least rq.Source: Hasse derivatives and high-order… · p. 4
- For each non-horizontal direction, one line is selected, and at every point the proof imposes vanishing to order (r,r′) along each selected line through that point.The parameter is set to r′ = (2−1/q)r, with r a multiple of q tending to infinity.Source: Hasse derivatives and high-order… · p. 4
- Restricting the derivatives to each selected line makes the resulting univariate polynomials vanish identically, forcing the top homogeneous component to vanish on every non-horizontal direction.The generalized Schwartz–Zippel lemma then yields a contradiction unless the original polynomial is zero.Source: Hasse derivatives and high-order… · p. 5
- The dimension argument separates low- and high-degree monomial conditions, bounds their codimensions, and combines the resulting estimates to obtain the desired lower bound.The final comparison uses dim V, the total line-point incidence count, and the limit r →∞.Source: Hasse derivatives and high-order… · pp. 5–7
4 Lower-order terms
For odd q, the sharp two-dimensional Kakeya bound is |K| ≥ q(q+1)/2, while higher-dimensional constructions are assembled inductively from lower-dimensional Kakeya sets and almost Kakeya sets.
4 Lower-order terms
- |K| ≥ q(q+1)/2 is the sharp bound for two-dimensional Kakeya sets when q is odd.This bound is attributed to Blokhuis and Mazzocca [1].Source: §4 · pp. 7–8
- Higher-dimensional constructions distinguish odd and even q, using almost Kakeya sets for odd q and a direct construction for even q.The odd-q construction is due to Dvir, whereas the even-q construction is due to Kopparty, Saraf, and Sudan.Source: §4 · p. 8
- The higher-dimensional almost Kakeya construction has an asymptotic expansion with lower-order terms, and the authors note that closing the resulting gap remains open.For large q, the quantity is given as 2^(−n+1)q^n(1 + (n−1)/q + O_n(q^−2)).Source: §4 · p. 8
- Horizontal directions can be handled more efficiently by adding a lower-dimensional Kakeya set instead of a horizontal hyperplane.An almost Kakeya set contains a line in every non-horizontal direction.Source: §4 · p. 8
- The inductive construction places an (n−1)-dimensional Kakeya set in a horizontal hyperplane and unions it with a translate of an almost Kakeya set.For any x ∈ F_q^n, the resulting union is a Kakeya set; the construction also considers random choices of x.Source: §4 · p. 8