Duplicating occurrence vertices outside a distinguished set
DefinitionGreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_HypergraphBundleDuplicationarithmetic-progressionscombinatoricsgreen-tao-port-8822hypergraph-regularity
Let be a type of occurrence vertices and let be a finite distinguished subset. Vertices of remain shared, while each vertex outside receives a Boolean copy label. Thus the doubled occurrence type has the form
The forgetful map removes the label, and the two lift maps place an old vertex into either copy while agreeing on . For assignments with values in a type , the construction supplies the corresponding bijection between an assignment on and one shared assignment together with two assignments on the complement. It also defines the lifted occurrence edges, source-edge products, and duplicated hypergraph bundle. The projection to the original base hypergraph is composed with the forgetful map.
Definition code
import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_HypergraphBundleCounting
import Lean
import Mathlib.Algebra.BigOperators.Expect
import Mathlib.Data.Fintype.Card
import Mathlib.Tactic
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Duplicating the variables outside one bundle edge
The squared remainder in the bundle counting argument identifies the
variables on a selected edge `g₀` and takes two independent copies of every
variable outside `g₀`. This file realizes that operation as a finite
hypergraph bundle.
An occurrence vertex in the doubled bundle is either a shared vertex of
`g₀`, or an outside vertex together with a Boolean copy label. Every
remaining occurrence edge is lifted once into each copy. The lift is
injective, preserves edge cardinality and projected base edges, and
therefore produces another valid bundle over the same base hypergraph.
-/
namespace Wikipedia.SzemeredisTheorem
open scoped BigOperators
namespace HypergraphBundle
variable {J K G : Type*}
[DecidableEq J] [DecidableEq K]
{H : Finset (Finset J)}
/-- Occurrence vertices after identifying `g₀` and doubling its
complement. -/
abbrev DoubledOccurrenceVertex (g₀ : Finset K) :=
{v : K // v ∈ g₀} ⊕ (Bool × EdgeComplement g₀)
/-- Forget the copy label of a doubled occurrence vertex. -/
def doubledVertexForget
(g₀ : Finset K) :
DoubledOccurrenceVertex g₀ → K
| Sum.inl v => v.1
| Sum.inr v => v.2.1
/-- Put an old occurrence vertex into one of the two copies, sharing it
when it lies in `g₀`. -/
def doubledVertexLift
(g₀ : Finset K) (copy : Bool) (v : K) :
DoubledOccurrenceVertex g₀ :=
if hv : v ∈ g₀ then
Sum.inl ⟨v, hv⟩
else
Sum.inr ⟨copy, ⟨v, hv⟩⟩
@[simp]
theorem doubledVertexForget_lift
(g₀ : Finset K) (copy : Bool) (v : K) :
doubledVertexForget g₀
(doubledVertexLift g₀ copy v) = v := by
by_cases hv : v ∈ g₀ <;>
simp [doubledVertexLift, doubledVertexForget, hv]
/-- Assemble one assignment on the shared vertices and two assignments on
the outside vertices into an assignment on the doubled occurrence set. -/
def doubledAssignment
(g₀ : Finset K)
(y : {v : K // v ∈ g₀} → G)
(z : (EdgeComplement g₀ → G) ×
(EdgeComplement g₀ → G)) :
DoubledOccurrenceVertex g₀ → G
| Sum.inl v => y v
| Sum.inr (false, v) => z.1 v
| Sum.inr (true, v) => z.2 v
/-- Splitting an assignment on the doubled occurrence set recovers exactly
one shared assignment and a pair of independent outside assignments. -/
def splitDoubledAssignmentEquiv
(g₀ : Finset K) :
(DoubledOccurrenceVertex g₀ → G) ≃
(({v : K // v ∈ g₀} → G) ×
((EdgeComplement g₀ → G) ×
(EdgeComplement g₀ → G))) where
toFun x :=
(fun v => x (Sum.inl v),
(fun v => x (Sum.inr (false, v)),
fun v => x (Sum.inr (true, v))))
invFun p := doubledAssignment g₀ p.1 p.2
left_inv x := by
funext v
rcases v with v | ⟨copy, v⟩
· rfl
· cases copy <;> rfl
right_inv p := by
rcases p with ⟨y, zfalse, ztrue⟩
rfl
/-- Lift an old occurrence edge into one Boolean copy. -/
def doubledEdge
(g₀ : Finset K) (copy : Bool) (g : Finset K) :
Finset (DoubledOccurrenceVertex g₀) :=
g.image (doubledVertexLift g₀ copy)
theorem mem_doubledEdge
(g₀ : Finset K) (copy : Bool)
(g : Finset K) (v : K) (hv : v ∈ g) :
doubledVertexLift g₀ copy v ∈
doubledEdge g₀ copy g :=
Finset.mem_image.mpr ⟨v, hv, rfl⟩
/-- Every old edge/copy pair which contributes an edge to the doubled
bundle. -/
abbrev DoubledEdgeSource
(B : HypergraphBundle J K H) (g₀ : Finset K) :=
Bool × {g : Finset K // g ∈ (B.edges.erase g₀)}
/-- The doubled edge belonging to one source edge and one copy. -/
def doubledEdgeOfSource
(B : HypergraphBundle J K H) (g₀ : Finset K)
(s : B.DoubledEdgeSource g₀) :
Finset (DoubledOccurrenceVertex g₀) :=
doubledEdge g₀ s.1 s.2.1
/-- Product indexed by the two labelled copies of every remaining edge.
This source-indexed form retains multiplicity even before one proves that
distinct sources give distinct doubled `Finset` edges. -/
noncomputable def doubledSourceProduct
(B : HypergraphBundle J K H) (g₀ : Finset K)
(A : (g : Finset K) →
({v : K // v ∈ g} → G) → ℝ)
(x : DoubledOccurrenceVertex g₀ → G) : ℝ :=
∏ s : B.DoubledEdgeSource g₀,
A s.2.1 (fun v =>
x (doubledVertexLift g₀ s.1 v.1))
/-- The finite family of all lifted remaining edges. Using an image
correctly identifies two lifted edges when all their vertices lie in the
shared selected edge. -/
def doubledEdges
(B : HypergraphBundle J K H) (g₀ : Finset K) :
Finset (Finset (DoubledOccurrenceVertex g₀)) :=
Finset.univ.image (B.doubledEdgeOfSource g₀)
theorem mem_doubledEdges_iff
(B : HypergraphBundle J K H) (g₀ : Finset K)
(d : Finset (DoubledOccurrenceVertex g₀)) :
d ∈ B.doubledEdges g₀ ↔
∃ (copy : Bool) (g : Finset K),
g ∈ B.edges.erase g₀ ∧
doubledEdge g₀ copy g = d := by
classical
constructor
· intro hd
obtain ⟨s, _hs, hsd⟩ :=
Finset.mem_image.mp hd
exact ⟨s.1, s.2.1, s.2.2, hsd⟩
· rintro ⟨copy, g, hg, rfl⟩
exact
Finset.mem_image.mpr
⟨(copy, ⟨g, hg⟩), Finset.mem_univ _, rfl⟩
/-- The doubled occurrence projection forgets the copy label and then uses
the original bundle projection. -/
def doubledProjection
(B : HypergraphBundle J K H) (g₀ : Finset K) :
DoubledOccurrenceVertex g₀ → J :=
fun v => B.projection (doubledVertexForget g₀ v)
@[simp]
theorem doubledProjection_lift
(B : HypergraphBundle J K H) (g₀ : Finset K)
(copy : Bool) (v : K) :
B.doubledProjection g₀
(doubledVertexLift g₀ copy v) =
B.projection v := by
simp [doubledProjection]
/-- A lifted occurrence edge has the same projected base edge. -/
@[simp]
theorem image_doubledProjection_doubledEdge
(B : HypergraphBundle J K H) (g₀ : Finset K)
(copy : Bool) (g : Finset K) :
(doubledEdge g₀ copy g).image
(B.doubledProjection g₀) =
g.image B.projection := by
classical
ext j
constructor
· intro hj
obtain ⟨v, hv, hvj⟩ := Finset.mem_image.mp hj
obtain ⟨w, hw, rfl⟩ := Finset.mem_image.mp hv
exact Finset.mem_image.mpr
⟨w, hw, by simpa using hvj⟩
· intro hj
obtain ⟨v, hv, hvj⟩ := Finset.mem_image.mp hj
exact
Finset.mem_image.mpr
⟨doubledVertexLift g₀ copy v,
mem_doubledEdge g₀ copy g v hv,
by simpa using hvj⟩
/-- The occurrence bundle obtained by identifying `g₀` and duplicating all
outside vertices and remaining edges. -/
def duplicateOutside
(B : HypergraphBundle J K H) (g₀ : Finset K) :
HypergraphBundle J (DoubledOccurrenceVertex g₀) H where
edges := B.doubledEdges g₀
projection := B.doubledProjection g₀
projection_injective_on_edge := by
intro d hd v hv w hw hvw
obtain ⟨copy, g, hg, rfl⟩ :=
(B.mem_doubledEdges_iff g₀ d).1 hd
obtain ⟨v₀, hv₀, rfl⟩ :=
Finset.mem_image.mp hv
obtain ⟨w₀, hw₀, rfl⟩ :=
Finset.mem_image.mp hw
apply congrArg (doubledVertexLift g₀ copy)
apply B.projection_injective_on_edge g
(Finset.mem_of_mem_erase hg) hv₀ hw₀
simpa using hvw
projection_mem_base := by
intro d hd
obtain ⟨copy, g, hg, rfl⟩ :=
(B.mem_doubledEdges_iff g₀ d).1 hd
rw [image_doubledProjection_doubledEdge]
exact B.projection_mem_base g
(Finset.mem_of_mem_erase hg)
end HypergraphBundle
end Wikipedia.SzemeredisTheorem
/- Materialize compiler-generated declarations promised by this bundle. -/
run_meta do
for requiredName in #[
`Wikipedia.SzemeredisTheorem.HypergraphBundle.doubledAssignment.eq_1,
`Wikipedia.SzemeredisTheorem.HypergraphBundle.doubledAssignment.eq_2,
`Wikipedia.SzemeredisTheorem.HypergraphBundle.doubledAssignment.eq_3,
`Wikipedia.SzemeredisTheorem.HypergraphBundle.doubledAssignment.match_1,
`Wikipedia.SzemeredisTheorem.HypergraphBundle.doubledEdge.eq_1,
`Wikipedia.SzemeredisTheorem.HypergraphBundle.doubledProjection.eq_1,
`Wikipedia.SzemeredisTheorem.HypergraphBundle.doubledVertexForget.eq_1,
`Wikipedia.SzemeredisTheorem.HypergraphBundle.doubledVertexForget.eq_2,
`Wikipedia.SzemeredisTheorem.HypergraphBundle.doubledVertexForget.match_1,
`Wikipedia.SzemeredisTheorem.HypergraphBundle.doubledVertexLift.eq_1
] do
let actualName ← Lean.realizeGlobalConstNoOverloadCore requiredName
unless actualName == requiredName do
throwError "Generated companion resolved to an unexpected name"
Source