Constructible graphs for arithmetic Kakeya
DefinitionArithmeticKakeya_gridadditive-combinatoricskakeya
The combinatorial substrate of the arithmetic Kakeya problem. grid d enumerates the vertices with . A ConstructibleGraph over a dilate set consists of dimensions and stage labellings on the prefix grid , where a non-zero label lies in (a zero label means no edge). The vertex count is and the edge count . edgeFn is the -valued function contributed by one labelled edge, sending its two endpoints to and all other vertices to . 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
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.