Katz–Tao counting lemma (Lemma 2.1)
ProvedArithmeticKakeya.katz_tao_counting_lemmaadditive-combinatoricskakeya
Katz–Tao's counting lemma: if with for , then the number of tuples satisfying for all is at least . Stated in cross-multiplied integer form to avoid division. It lower-bounds the number of copies of a constructible graph inside a set .
Preamble
import Mathlib
Formal statement
namespace ArithmeticKakeya
theorem katz_tao_counting_lemma
(X : Type) [Fintype X] [DecidableEq X]
(k : ℕ) (Y : Fin k → Type) [∀ i, Fintype (Y i)] [∀ i, DecidableEq (Y i)]
(f : (i : Fin k) → X → Y i) (M : Fin k → ℕ)
(hM : ∀ i, Fintype.card (Y i) ≤ M i) :
Fintype.card X ^ (k + 1) ≤
Fintype.card { x : Fin (k + 1) → X // ∀ i : Fin k, f i (x i.castSucc) = f i (x i.succ) } *
Finset.univ.prod M := by sorry
end ArithmeticKakeyaSource
Katz–Tao, Math. Res. Lett. 6 (1999), Lemma 2.1; as stated in https://epoch.ai/frontiermath/open-problems/arithmetic-kakeya
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.