Finite face partitions, refinements, and pullbacks
DefinitionGreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_FacePartitionarithmetic-progressionscombinatoricsgreen-tao-port-8822hypergraph-regularity
A face partition is a finite partition of the whole finite face space. Its complexity is its number of genuine atoms, and a representative may be chosen from each nonempty atom.
The indiscrete partition has one ambient cell when the space is nonempty. Common refinement is supplied for two partitions and for a finite family, with the empty family giving the indiscrete partition. A finite family of cuts generates the partition whose atoms have the same membership bits for every cut. A map pulls a target partition back by declaring two points equivalent when their images lie in the same target atom. The underlying partition order runs from finer to coarser.
Definition code
import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_ConditionalAverage
import Lean
import Mathlib.Algebra.BigOperators.Expect
import Mathlib.Algebra.Order.BigOperators.Expect
import Mathlib.Data.Fintype.Card
import Mathlib.Order.Partition.Finpartition
import Mathlib.Tactic
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Finite face partitions
The finite regularity argument uses partitions of finite face spaces. This
file fixes the refinement convention, packages common refinements and
partitions generated by cuts, and constructs pullbacks along maps of finite
types.
Mathlib orders `Finpartition` by refinement: `P ≤ Q` means that `P` is finer
than `Q`. Consequently the lattice infimum is the common refinement.
-/
namespace Wikipedia.SzemeredisTheorem
/-- A partition of all elements of a finite face space. -/
abbrev FacePartition (Ω : Type*) [Fintype Ω] [DecidableEq Ω] :=
Finpartition (Finset.univ : Finset Ω)
namespace FacePartition
variable {Ω : Type*} [Fintype Ω] [DecidableEq Ω]
/-- Refinement shrinks the atom containing every point. -/
theorem part_subset_of_le {P Q : FacePartition Ω}
(h : P ≤ Q) (x : Ω) :
P.part x ⊆ Q.part x := by
obtain ⟨s, hs, hsub⟩ :=
h (P.part_mem.2 (Finset.mem_univ x))
have hxs : x ∈ s :=
hsub (P.mem_part (Finset.mem_univ x))
rw [Q.part_eq_of_mem hs hxs]
exact hsub
/-- Pointwise atom inclusion characterizes the refinement order. -/
theorem le_iff_part_subset {P Q : FacePartition Ω} :
P ≤ Q ↔ ∀ x, P.part x ⊆ Q.part x := by
constructor
· exact fun h x => part_subset_of_le h x
· intro h s hs
obtain ⟨x, hx⟩ := P.nonempty_of_mem_parts hs
refine ⟨Q.part x, Q.part_mem.2 (Finset.mem_univ x), ?_⟩
rw [← P.part_eq_of_mem hs hx]
exact h x
/-- The indiscrete face partition. -/
def indiscrete : FacePartition Ω :=
⊤
@[simp]
theorem part_indiscrete (x : Ω) :
(indiscrete : FacePartition Ω).part x = Finset.univ := by
change (⊤ : FacePartition Ω).part x = Finset.univ
have hmem :
(⊤ : FacePartition Ω).part x ∈
(⊤ : FacePartition Ω).parts :=
(⊤ : FacePartition Ω).part_mem.2 (Finset.mem_univ x)
exact Finset.mem_singleton.mp
(Finpartition.parts_top_subset
(Finset.univ : Finset Ω) hmem)
/-- Partition complexity measured by the number of atoms. -/
def complexity (P : FacePartition Ω) : ℕ :=
P.parts.card
/-- A canonical representative of a partition atom. -/
noncomputable def representative
(P : FacePartition Ω) (a : P.parts) : Ω :=
Classical.choose (P.nonempty_of_mem_parts a.2)
/-- The common refinement of two face partitions. This is an infimum
because the `Finpartition` order points from finer to coarser partitions. -/
def join (P Q : FacePartition Ω) : FacePartition Ω :=
P ⊓ Q
theorem join_le_left (P Q : FacePartition Ω) :
join P Q ≤ P :=
inf_le_left
theorem join_le_right (P Q : FacePartition Ω) :
join P Q ≤ Q :=
inf_le_right
theorem le_join_iff {P Q R : FacePartition Ω} :
R ≤ join P Q ↔ R ≤ P ∧ R ≤ Q :=
le_inf_iff
@[simp]
theorem part_join (P Q : FacePartition Ω) (x : Ω) :
(join P Q).part x = P.part x ∩ Q.part x := by
apply Finpartition.part_eq_of_mem
· rw [join, Finpartition.parts_inf]
apply Finset.mem_erase.mpr
constructor
· exact Finset.nonempty_iff_ne_empty.mp ⟨x, by simp⟩
· apply Finset.mem_image.mpr
refine ⟨(P.part x, Q.part x), ?_, rfl⟩
simp
· simp
/-- A binary common refinement has at most the product of the two atom
counts. -/
theorem complexity_join_le (P Q : FacePartition Ω) :
complexity (join P Q) ≤ complexity P * complexity Q := by
change (P ⊓ Q).parts.card ≤ P.parts.card * Q.parts.card
calc
(P ⊓ Q).parts.card =
(((P.parts ×ˢ Q.parts).image
(fun st => st.1 ⊓ st.2)).erase ⊥).card :=
congrArg Finset.card (Finpartition.parts_inf P Q)
_ ≤
((P.parts ×ˢ Q.parts).image
(fun st => st.1 ⊓ st.2)).card :=
Finset.card_le_card (Finset.erase_subset _ _)
_ ≤ (P.parts ×ˢ Q.parts).card :=
Finset.card_image_le
_ = P.parts.card * Q.parts.card :=
Finset.card_product P.parts Q.parts
/-! ## Finite common refinements -/
/-- The common refinement of a finite family of face partitions. The empty
family gives the indiscrete partition. -/
def joinFinset {ι : Type*} [DecidableEq ι]
(s : Finset ι) (P : ι → FacePartition Ω) :
FacePartition Ω :=
s.inf P
@[simp]
theorem joinFinset_empty {ι : Type*} [DecidableEq ι]
(P : ι → FacePartition Ω) :
joinFinset ∅ P = indiscrete :=
rfl
@[simp]
theorem joinFinset_insert {ι : Type*} [DecidableEq ι]
(a : ι) (s : Finset ι) (P : ι → FacePartition Ω) :
joinFinset (insert a s) P =
join (P a) (joinFinset s P) := by
simp [joinFinset, join]
/-- A finite common refinement refines each partition in the family. -/
theorem joinFinset_le_of_mem {ι : Type*} [DecidableEq ι]
{s : Finset ι} (P : ι → FacePartition Ω)
{i : ι} (hi : i ∈ s) :
joinFinset s P ≤ P i :=
Finset.inf_le hi
/-- The universal property of a finite common refinement. -/
theorem le_joinFinset_iff {ι : Type*} [DecidableEq ι]
{s : Finset ι} {P : ι → FacePartition Ω}
{Q : FacePartition Ω} :
Q ≤ joinFinset s P ↔ ∀ i ∈ s, Q ≤ P i :=
Finset.le_inf_iff
/-- Two points lie in the same atom of a finite common refinement exactly
when they lie in the same atom of every constituent partition. -/
theorem mem_part_joinFinset_iff {ι : Type*} [DecidableEq ι]
(s : Finset ι) (P : ι → FacePartition Ω)
(x y : Ω) :
y ∈ (joinFinset s P).part x ↔
∀ i ∈ s, y ∈ (P i).part x := by
classical
induction s using Finset.induction with
| empty =>
rw [joinFinset_empty]
simp
| @insert a s ha ih =>
simp only [joinFinset_insert, part_join,
Finset.mem_inter, Finset.mem_insert, forall_eq_or_imp,
ih]
/-- The partition generated by a finite family of cuts. Two points lie in
the same atom exactly when every cut gives them the same membership bit. -/
def generatedBy (F : Finset (Finset Ω)) : FacePartition Ω :=
Finpartition.atomise Finset.univ F
/-- The generator-membership signature is the exact atom relation for
`generatedBy`. -/
@[simp]
theorem mem_part_generatedBy_iff (F : Finset (Finset Ω))
(x y : Ω) :
y ∈ (generatedBy F).part x ↔
∀ s ∈ F, (x ∈ s ↔ y ∈ s) := by
classical
let P : FacePartition Ω := generatedBy F
have hp : P.part x ∈ P.parts :=
P.part_mem.2 (Finset.mem_univ x)
have hpAtom :
P.part x ∈
(Finpartition.atomise
(Finset.univ : Finset Ω) F).parts := by
change
(Finpartition.atomise
(Finset.univ : Finset Ω) F).part x ∈
(Finpartition.atomise
(Finset.univ : Finset Ω) F).parts at hp
exact hp
obtain ⟨_, Q, hQ, hpart⟩ :=
Finpartition.mem_atomise.mp hpAtom
have hmem := Finset.ext_iff.mp hpart
have hx : x ∈ P.part x :=
P.mem_part (Finset.mem_univ x)
have hxAtom := (hmem x).2 hx
simp only [Finset.mem_filter] at hxAtom
constructor
· intro hy s hs
have hyAtom := (hmem y).2 hy
simp only [Finset.mem_filter] at hyAtom
exact (hxAtom.2 s hs).symm.trans (hyAtom.2 s hs)
· intro hsignature
apply (hmem y).1
simp only [Finset.mem_filter]
refine ⟨Finset.mem_univ y, ?_⟩
intro s hs
exact (hxAtom.2 s hs).trans (hsignature s hs)
/-- Adding generators refines the generated partition. -/
theorem generatedBy_antitone {F G : Finset (Finset Ω)}
(hFG : F ⊆ G) :
generatedBy G ≤ generatedBy F := by
rw [le_iff_part_subset]
intro x y hy
rw [mem_part_generatedBy_iff] at hy ⊢
intro s hs
exact hy s (hFG hs)
/-- A partition generated by `m` cuts has at most `2^m` atoms. -/
theorem complexity_generatedBy_le (F : Finset (Finset Ω)) :
complexity (generatedBy F) ≤ 2 ^ F.card := by
exact Finpartition.card_atomise_le
/-- The same-atom relation transported along a map. -/
def pullbackSetoid {Λ : Type*} [Fintype Λ] [DecidableEq Λ]
(f : Ω → Λ) (Q : FacePartition Λ) : Setoid Ω where
r x y := Q.part (f x) = Q.part (f y)
iseqv := {
refl := fun _ => rfl
symm := fun h => h.symm
trans := fun h₁ h₂ => h₁.trans h₂ }
instance instDecidableRelPullbackSetoid {Λ : Type*}
[Fintype Λ] [DecidableEq Λ]
(f : Ω → Λ) (Q : FacePartition Λ) :
DecidableRel (pullbackSetoid f Q) := by
intro x y
change Decidable (Q.part (f x) = Q.part (f y))
infer_instance
/-- Pull a partition back along a map of finite face spaces. -/
def pullback {Λ : Type*} [Fintype Λ] [DecidableEq Λ]
(f : Ω → Λ) (Q : FacePartition Λ) : FacePartition Ω :=
Finpartition.ofSetoid (pullbackSetoid f Q)
@[simp]
theorem mem_part_pullback_iff {Λ : Type*}
[Fintype Λ] [DecidableEq Λ]
(f : Ω → Λ) (Q : FacePartition Λ) (x y : Ω) :
y ∈ (pullback f Q).part x ↔
Q.part (f x) = Q.part (f y) := by
change
y ∈
(Finpartition.ofSetoid
(pullbackSetoid f Q)).part x ↔
Q.part (f x) = Q.part (f y)
rw [Finpartition.mem_part_ofSetoid_iff_rel]
rfl
/-- Membership in a pullback atom is exactly membership of the image in
the target atom. -/
theorem mem_part_pullback_iff_image_mem {Λ : Type*}
[Fintype Λ] [DecidableEq Λ]
(f : Ω → Λ) (Q : FacePartition Λ) (x y : Ω) :
y ∈ (pullback f Q).part x ↔
f y ∈ Q.part (f x) := by
rw [mem_part_pullback_iff]
constructor
· intro h
exact
(Q.mem_part_iff_part_eq_part
(Finset.mem_univ (f y))
(Finset.mem_univ (f x))).2 h.symm
· intro h
exact
((Q.mem_part_iff_part_eq_part
(Finset.mem_univ (f y))
(Finset.mem_univ (f x))).1 h).symm
/-- Pullback preserves refinement. -/
theorem pullback_mono {Λ : Type*}
[Fintype Λ] [DecidableEq Λ]
(f : Ω → Λ) {P Q : FacePartition Λ}
(h : P ≤ Q) :
pullback f P ≤ pullback f Q := by
rw [le_iff_part_subset]
intro x y hy
rw [mem_part_pullback_iff_image_mem] at hy ⊢
exact part_subset_of_le h (f x) hy
end FacePartition
end Wikipedia.SzemeredisTheorem
/- Materialize compiler-generated declarations promised by this bundle. -/
run_meta do
for requiredName in #[
`Wikipedia.SzemeredisTheorem.FacePartition.complexity.eq_1,
`Wikipedia.SzemeredisTheorem.FacePartition.congr_simp,
`Wikipedia.SzemeredisTheorem.FacePartition.indiscrete.eq_1,
`Wikipedia.SzemeredisTheorem.FacePartition.join.eq_1,
`Wikipedia.SzemeredisTheorem.FacePartition.joinFinset.congr_simp,
`Wikipedia.SzemeredisTheorem.FacePartition.joinFinset.eq_1
] do
let actualName ← Lean.realizeGlobalConstNoOverloadCore requiredName
unless actualName == requiredName do
throwError "Generated companion resolved to an unexpected name"
Source