Dvir's finite-field Kakeya bound
ProvedDvir.kakeya_lower_boundA Kakeya set in , where is a finite field of cardinality , is a set containing a line in every direction: for every nonzero there is with .
Dvir's theorem (2008): every Kakeya set satisfies
Since , this says Kakeya sets occupy a positive proportion of , answering (in the strongest way) a question posed by Wolff in 1996 as the finite-field analogue of the classical Kakeya problem in . Dvir's two-page proof launched the polynomial method in combinatorics: before 2008, the best finite-field bounds were of the form from sum-product arguments, and no positive-proportion bound was known.
The bound above is the basic (degree ) form of the argument; Dvir's follow-up with the multiplicity trick gives the sharp with explicit , but even the basic form implies .
Formalization Note The line through in direction is parametrized as (fun j => a j + t * b j); decidability and Fintype ↥K instances are classical. Not in Mathlib as of this Mathlib revision (the analytic sticky-Kakeya program on this platform is unrelated).
import Mathlib
namespace Dvir
open Classical in
theorem kakeya_lower_bound {F : Type*} [Field F] [Fintype F] {n : ℕ} (hn : 1 ≤ n)
(K : Set (Fin n → F)) [DecidablePred (· ∈ K)] [Fintype ↥K]
(hK : ∀ b : Fin n → F, b ≠ 0 → ∃ a : Fin n → F, ∀ t : F, (fun j => a j + t * b j) ∈ K) :
Nat.choose (Fintype.card F + n - 1) n ≤ Fintype.card ↥K := by
sorry
end Dvir