An exact coordinate change between AP parameters and simplex vertices
DefinitionGreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_APCorrespondencearithmetic-progressionscombinatoricsgreen-tao-port-8822hypergraph-regularity
For a simplex vector of length over , take the initial term to be its first coordinate moment and the common difference to be the negative coordinate sum. The remaining coordinates, at positions , are free.
The bundle supplies the tail sum and tail moment, the explicit reconstruction of the first two coordinates from and the free tail, and the resulting bijection
No division is needed in this coordinate change, so its definition does not require a prime or even a positive modulus.
Definition code
import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_Simplex
import Lean
import Mathlib.Algebra.BigOperators.Expect
import Mathlib.Algebra.Order.BigOperators.GroupWithZero.Finset
import Mathlib.Data.Fintype.Card
import Mathlib.Data.ZMod.Basic
import Mathlib.Tactic
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# The arithmetic-progression/simplex correspondence
For `k = r + 2`, the coordinate moment and the negative coordinate sum give
the initial term and common difference of the encoded cyclic progression.
The remaining `r` coordinates parametrize every fiber uniformly. An
explicit equivalence records this change of variables and transports the
normalized simplex average to the normalized arithmetic-progression count.
-/
namespace Wikipedia.SzemeredisTheorem
open scoped BigOperators
/-- Sum of the free coordinates in a fiber of the AP parameter map. -/
def simplexTailSum (r N : ℕ) (y : Fin r → ZMod N) : ZMod N :=
∑ i : Fin r, y i
/-- First moment of the free coordinates, using their actual positions
`2, ..., r + 1` in the full simplex vector. -/
def simplexTailMoment (r N : ℕ) (y : Fin r → ZMod N) : ZMod N :=
∑ i : Fin r, (i.succ.succ : ZMod N) * y i
/-- Reconstruct simplex coordinates from a cyclic initial term `a`, common
difference `d`, and the remaining `r` free coordinates. -/
def simplexCoordinatesOfAP (r N : ℕ) (a d : ZMod N)
(y : Fin r → ZMod N) : Fin (r + 2) → ZMod N :=
Fin.cases
(simplexTailMoment r N y - a - d - simplexTailSum r N y)
(Fin.cases (a - simplexTailMoment r N y) y)
@[simp]
theorem simplexCoordinatesOfAP_zero (r N : ℕ) (a d : ZMod N)
(y : Fin r → ZMod N) :
simplexCoordinatesOfAP r N a d y 0 =
simplexTailMoment r N y - a - d - simplexTailSum r N y :=
rfl
@[simp]
theorem simplexCoordinatesOfAP_one (r N : ℕ) (a d : ZMod N)
(y : Fin r → ZMod N) :
simplexCoordinatesOfAP r N a d y 1 =
a - simplexTailMoment r N y :=
rfl
@[simp]
theorem simplexCoordinatesOfAP_succ_succ (r N : ℕ)
(a d : ZMod N) (y : Fin r → ZMod N) (i : Fin r) :
simplexCoordinatesOfAP r N a d y i.succ.succ = y i :=
rfl
/-- Split the coordinate sum into the first two and the free tail. -/
theorem simplexCoordinateSum_decompose (r N : ℕ)
(x : Fin (r + 2) → ZMod N) :
simplexCoordinateSum (r + 2) N x =
x 0 + x 1 +
simplexTailSum r N (fun i => x i.succ.succ) := by
simp [simplexCoordinateSum, simplexTailSum, Fin.sum_univ_succ,
add_assoc]
/-- Split the coordinate moment into coordinate one and the free tail;
coordinate zero has coefficient zero. -/
theorem simplexCoordinateMoment_decompose (r N : ℕ)
(x : Fin (r + 2) → ZMod N) :
simplexCoordinateMoment (r + 2) N x =
x 1 + simplexTailMoment r N (fun i => x i.succ.succ) := by
simp [simplexCoordinateMoment, simplexTailMoment,
Fin.sum_univ_succ]
@[simp]
theorem simplexCoordinateSum_coordinatesOfAP (r N : ℕ)
(a d : ZMod N) (y : Fin r → ZMod N) :
simplexCoordinateSum (r + 2) N
(simplexCoordinatesOfAP r N a d y) = -d := by
rw [simplexCoordinateSum_decompose]
simp
ring
@[simp]
theorem simplexCoordinateMoment_coordinatesOfAP (r N : ℕ)
(a d : ZMod N) (y : Fin r → ZMod N) :
simplexCoordinateMoment (r + 2) N
(simplexCoordinatesOfAP r N a d y) = a := by
rw [simplexCoordinateMoment_decompose]
simp
/-- The exact coordinate change: AP parameters, together with `r` free
coordinates, are equivalent to simplex coordinates of length `r + 2`. -/
def simplexAPEquiv (r N : ℕ) :
(Fin (r + 2) → ZMod N) ≃
(ZMod N × ZMod N) × (Fin r → ZMod N) where
toFun x :=
((simplexCoordinateMoment (r + 2) N x,
-simplexCoordinateSum (r + 2) N x),
fun i => x i.succ.succ)
invFun y := simplexCoordinatesOfAP r N y.1.1 y.1.2 y.2
left_inv x := by
funext i
refine Fin.cases ?_ (fun i => Fin.cases ?_ (fun _ => rfl) i) i
· change
simplexCoordinatesOfAP r N
(simplexCoordinateMoment (r + 2) N x)
(-simplexCoordinateSum (r + 2) N x)
(fun i => x i.succ.succ) 0 =
x 0
rw [simplexCoordinatesOfAP_zero,
simplexCoordinateMoment_decompose,
simplexCoordinateSum_decompose]
ring
· change
simplexCoordinatesOfAP r N
(simplexCoordinateMoment (r + 2) N x)
(-simplexCoordinateSum (r + 2) N x)
(fun i => x i.succ.succ) 1 =
x 1
rw [simplexCoordinatesOfAP_one,
simplexCoordinateMoment_decompose]
ring
right_inv y := by
rcases y with ⟨⟨a, d⟩, tail⟩
apply Prod.ext
· apply Prod.ext
· change
simplexCoordinateMoment (r + 2) N
(simplexCoordinatesOfAP r N a d tail) =
a
exact simplexCoordinateMoment_coordinatesOfAP r N a d tail
· change
-simplexCoordinateSum (r + 2) N
(simplexCoordinatesOfAP r N a d tail) =
d
rw [simplexCoordinateSum_coordinatesOfAP]
simp
· funext i
change simplexCoordinatesOfAP r N a d tail i.succ.succ = tail i
exact simplexCoordinatesOfAP_succ_succ r N a d tail i
end Wikipedia.SzemeredisTheorem
/- Materialize compiler-generated declarations promised by this bundle. -/
run_meta do
for requiredName in #[
`Wikipedia.SzemeredisTheorem.simplexTailMoment.eq_1,
`Wikipedia.SzemeredisTheorem.simplexTailSum.eq_1
] do
let actualName ← Lean.realizeGlobalConstNoOverloadCore requiredName
unless actualName == requiredName do
throwError "Generated companion resolved to an unexpected name"
Source