Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Constructible graphs for arithmetic Kakeya

Definition
ArithmeticKakeya_grid

by LG · Nov 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

additive-combinatoricskakeya

The combinatorial substrate of the arithmetic Kakeya problem. grid d enumerates the vertices [e1,…,ek][e_1,\dots,e_k][e1​,…,ek​] with 1≤ei≤di1\le e_i\le d_i1≤ei​≤di​. A ConstructibleGraph over a dilate set X⊂Z2X\subset\mathbb Z^2X⊂Z2 consists of dimensions d1,…,dkd_1,\dots,d_kd1​,…,dk​ and stage labellings fif_ifi​ on the prefix grid d1×⋯×(di−1)d_1\times\cdots\times(d_i-1)d1​×⋯×(di​−1), where a non-zero label lies in XXX (a zero label means no edge). The vertex count is n(G)=d1⋯dkn(G)=d_1\cdots d_kn(G)=d1​⋯dk​ and the edge count m(G)=∑i(#non-zero fi) di+1⋯dkm(G)=\sum_i(\#\text{non-zero }f_i)\,d_{i+1}\cdots d_km(G)=∑i​(#non-zero fi​)di+1​⋯dk​. edgeFn is the Z2\mathbb Z^2Z2-valued function contributed by one labelled edge, sending its two endpoints to ±x\pm\mathbf{x}±x and all other vertices to 000. These are the definitions of the source's Verifiable Set-up.

Definition code
import Mathlib

namespace ArithmeticKakeya

open Finset

/-- `grid d` enumerates the vertices of `d_1 × ⋯ × d_k`: all lists `[e_1,…,e_k]`
with `1 ≤ e_i ≤ d_i`, each exactly once. -/
def grid : List ℕ → List (List ℕ)
  | [] => [[]]
  | d :: ds => (List.range' 1 d).foldr (fun a acc => (grid ds).map (fun t => a :: t) ++ acc) []

/-- The prefix domain of stage `i` (0-indexed): `d.take i ++ [d[i] − 1]`. -/
def domainDims (d : List ℕ) (i : Fin d.length) : List ℕ :=
  d.take i.val ++ [d.get i - 1]

/-- An `X`-constructible graph. A non-zero label `f i e` is allowed only on the prefix
domain `domainDims dims i` and must then lie in `X`; a zero value means "no edge". -/
structure ConstructibleGraph (X : Finset (ℤ × ℤ)) where
  dims : List ℕ
  f : (i : Fin dims.length) → List ℕ → ℤ × ℤ
  f_support : ∀ (i : Fin dims.length) (e : List ℕ),
    f i e ≠ (0, 0) → e ∈ grid (domainDims dims i) ∧ f i e ∈ X

/-- The number of vertices `n(G) = d_1 ⋯ d_k`. -/
def n {X : Finset (ℤ × ℤ)} (G : ConstructibleGraph X) : ℕ := G.dims.prod

/-- The number of edges `m(G) = Σ_i (# non-zero entries of f_i) · d_{i+1} ⋯ d_k`. -/
def m {X : Finset (ℤ × ℤ)} (G : ConstructibleGraph X) : ℕ :=
  Finset.sum Finset.univ (fun i : Fin G.dims.length =>
    ((grid (domainDims G.dims i)).filter (fun e => decide (G.f i e ≠ (0, 0)))).length *
      (G.dims.drop (i.val + 1)).prod)

/-- The edge function for stage `i`, prefix `a`, suffix `c`: sends `a ++ c` to `f i a`,
`(a with last coordinate +1) ++ c` to its negation, and all other vertices to `(0,0)`. -/
def edgeFn {X : Finset (ℤ × ℤ)} (G : ConstructibleGraph X)
    (i : Fin G.dims.length) (a c : List ℕ) : List ℕ → ℤ × ℤ :=
  let x := G.f i a
  let e₁ := a ++ c
  let e₂ := a.dropLast ++ [a.getLastD 0 + 1] ++ c
  fun g => if g = e₁ then x else if g = e₂ then -x else (0, 0)

end ArithmeticKakeya
Source
https://epoch.ai/frontiermath/open-problems/arithmetic-kakeya (Verifiable Set-up / Introduction)
Human review
  • Endorsed by Shuze Chen · Nov 17, 2026

    Confirmed by the moderator at approval.

  • Endorsed by LG · Nov 17, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me