AP hypergraphs, degenerate simplices, and the uniform removal predicate
DefinitionGreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_APRemovalarithmetic-progressionscombinatoricsgreen-tao-port-8822hypergraph-regularity
A finite cyclic set defines an unweighted AP-simplex hypergraph by requiring each AP edge-form value to lie in . A constant progression is represented by a point of and a free tail in the AP/simplex coordinate equivalence. Given a simplex cover, a witnessing deleted colour can be chosen for each such degenerate simplex and encoded in a fixed finite set of coloured deletion slots.
The uniform cyclic partite-removal predicate says that, for every , there is a independent of the positive modulus such that any corresponding hypergraph with normalized simplex count below has a simplex cover of normalized deletion cost at most . The predicate records the exact combinatorial input used by the AP counting argument.
Definition code
import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_APCorrespondence
import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_Removal
import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Szemeredi_Weighted
import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Transference_APCut
import Lean
import Mathlib.Algebra.BigOperators.Expect
import Mathlib.Algebra.BigOperators.Fin
import Mathlib.Algebra.Order.BigOperators.Expect
import Mathlib.Algebra.Order.BigOperators.GroupWithZero.Finset
import Mathlib.Data.Fin.Tuple.Basic
import Mathlib.Data.Finset.Max
import Mathlib.Data.Fintype.Card
import Mathlib.Data.Int.Lemmas
import Mathlib.Data.ZMod.Basic
import Mathlib.Data.ZMod.Units
import Mathlib.Order.Partition.Finpartition
import Mathlib.RingTheory.Int.Basic
import Mathlib.Tactic
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# From partite simplex removal to dense arithmetic progressions
For a finite set `A ⊆ ZMod N`, its arithmetic-progression hypergraph has
one edge of colour `j` whenever the `j`th AP form belongs to `A`. The
degenerate progressions of common difference zero give a large,
edge-disjoint family of labelled simplices. Consequently every simplex
cover has normalized deletion cost at least `mean (1_A) / k`.
This is the elementary half of the standard deduction of dense
Szemerédi from the partite simplex-removal lemma.
-/
namespace Wikipedia.SzemeredisTheorem
open scoped BigOperators
/-- The unweighted partite hypergraph cut out by membership of each AP form
in `A`. -/
def apSetHypergraph (k N : ℕ) (A : Finset (ZMod N)) :
SimplexHypergraph (fun _ : Fin k => ZMod N) where
edge j x := apSimplexForm k N j x ∈ A
@[simp]
theorem apSetHypergraph_edge
(k N : ℕ) (A : Finset (ZMod N))
(j : Fin k)
(x : DeletedVector (fun _ : Fin k => ZMod N) j) :
(apSetHypergraph k N A).edge j x ↔
apSimplexForm k N j x ∈ A :=
Iff.rfl
/-- Parameters for degenerate AP simplices: a member of `A` and the free
tail in the AP/simplex coordinate equivalence. -/
abbrev DiagonalAPParameter
(r N : ℕ) (A : Finset (ZMod N)) :=
↥A × (Fin r → ZMod N)
/-- The labelled simplex corresponding to the constant progression with
value `a`. -/
def diagonalAPSimplex
(r N : ℕ) (A : Finset (ZMod N))
(p : DiagonalAPParameter r N A) :
Fin (r + 2) → ZMod N :=
simplexCoordinatesOfAP r N p.1.1 0 p.2
@[simp]
theorem simplexCoordinateSum_diagonalAPSimplex
(r N : ℕ) (A : Finset (ZMod N))
(p : DiagonalAPParameter r N A) :
simplexCoordinateSum (r + 2) N
(diagonalAPSimplex r N A p) = 0 := by
simp [diagonalAPSimplex]
@[simp]
theorem simplexCoordinateMoment_diagonalAPSimplex
(r N : ℕ) (A : Finset (ZMod N))
(p : DiagonalAPParameter r N A) :
simplexCoordinateMoment (r + 2) N
(diagonalAPSimplex r N A p) = p.1.1 := by
simp [diagonalAPSimplex]
/-- Every edge form on a degenerate AP simplex is the same member of `A`. -/
@[simp]
theorem apSimplexForm_diagonalAPSimplex
(r N : ℕ) (A : Finset (ZMod N))
(p : DiagonalAPParameter r N A)
(j : Fin (r + 2)) :
apSimplexForm (r + 2) N j
(deleteCoordinate (diagonalAPSimplex r N A p) j) =
p.1.1 := by
rw [apSimplexForm_deleteCoordinate,
simplexCoordinateMoment_diagonalAPSimplex,
simplexCoordinateSum_diagonalAPSimplex]
simp
/-- Every degenerate AP parameter gives an actual labelled simplex of the
AP-set hypergraph. -/
theorem diagonalAPSimplex_mem_simplexFinset
(r N : ℕ) [NeZero N] (A : Finset (ZMod N))
(p : DiagonalAPParameter r N A) :
diagonalAPSimplex r N A p ∈
(apSetHypergraph (r + 2) N A).simplexFinset := by
let : ∀ _ : Fin (r + 2), Fintype (ZMod N) :=
fun _ => inferInstance
rw [SimplexHypergraph.mem_simplexFinset]
intro j
rw [apSetHypergraph_edge,
apSimplexForm_diagonalAPSimplex]
exact p.1.2
/-- Present a dependent deleted-coordinate vector by the canonical
`Fin n` list of its remaining coordinates. -/
noncomputable def deletedVectorToFinTuple
{G : Type*} {n : ℕ} (j : Fin (n + 1))
(x : DeletedVector (fun _ : Fin (n + 1) => G) j) :
Fin n → G :=
fun t => x (finSuccAboveEquiv j t)
namespace SimplexHypergraph
/-- All deleted coloured faces, embedded into one fixed finite type by the
canonical ordering of each deleted coordinate space. -/
noncomputable def deletionSlotFinset
{G : Type*} [Fintype G] [DecidableEq G] {n : ℕ}
(deleted :
DeletionFamily (fun _ : Fin (n + 1) => G)) :
Finset (Fin (n + 1) × (Fin n → G)) := by
classical
exact Finset.univ.biUnion fun j =>
(deleted j).image fun x =>
(j, deletedVectorToFinTuple j x)
end SimplexHypergraph
/-- Choose one deleted colour witnessing that a cover meets a given
degenerate arithmetic-progression simplex. -/
noncomputable def diagonalCoverColor
(r N : ℕ) [NeZero N] (A : Finset (ZMod N))
(deleted :
SimplexHypergraph.DeletionFamily
(fun _ : Fin (r + 2) => ZMod N))
(hcover :
(apSetHypergraph (r + 2) N A).IsSimplexCover deleted)
(p : DiagonalAPParameter r N A) :
Fin (r + 2) :=
Classical.choose
(hcover (diagonalAPSimplex r N A p)
(diagonalAPSimplex_mem_simplexFinset r N A p))
/-- Encode the face selected by a cover in a fixed finite disjoint union of
coloured deletion slots. -/
noncomputable def diagonalCoveredSlot
(r N : ℕ) [NeZero N] (A : Finset (ZMod N))
(deleted :
SimplexHypergraph.DeletionFamily
(fun _ : Fin (r + 2) => ZMod N))
(hcover :
(apSetHypergraph (r + 2) N A).IsSimplexCover deleted)
(p : DiagonalAPParameter r N A) :
Fin (r + 2) × (Fin (r + 1) → ZMod N) :=
let j := diagonalCoverColor r N A deleted hcover p
(j, deletedVectorToFinTuple j
(deleteCoordinate (diagonalAPSimplex r N A p) j))
/-- Uniform partite simplex removal on cyclic vertex classes of a fixed
number of colours. The constant is independent of the modulus. This is the
precise deep combinatorial input still required from the hypergraph
regularity/removal development. -/
def HasUniformCyclicPartiteSimplexRemoval (k : ℕ) : Prop :=
∀ ε : ℝ, 0 < ε →
∃ c : ℝ, 0 < c ∧
∀ (N : ℕ) [NeZero N],
∀ H :
SimplexHypergraph (fun _ : Fin k => ZMod N),
H.toWeighted.simplexCount < c →
∃ deleted :
SimplexHypergraph.DeletionFamily
(fun _ : Fin k => ZMod N),
H.IsSimplexCover deleted ∧
SimplexHypergraph.normalizedDeletionCost
deleted ≤ ε
end Wikipedia.SzemeredisTheorem
/- Materialize compiler-generated declarations promised by this bundle. -/
run_meta do
for requiredName in #[
`Wikipedia.SzemeredisTheorem.diagonalAPSimplex.eq_1
] do
let actualName ← Lean.realizeGlobalConstNoOverloadCore requiredName
unless actualName == requiredName do
throwError "Generated companion resolved to an unexpected name"
Source