Distributed Boolean-cut refinement of shared ordered-face layers
DefinitionGreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_PreliminaryOrderedRegularityA Boolean boundary assignment places one Boolean predicate on each immediate deleted-coordinate space. Its product support is the set of upper tuples satisfying all component predicates. A violating upper witness distributes those component cuts to their genuine immediate lower faces, and the corresponding shared partitions are refined by the generated cuts.
The aggregate layer energy sums the upper-atom energies over all ordered upper faces. Preliminary regularity requires every upper atom's residual correlation with every Boolean boundary product cut to be at most in absolute value. An irregular witness records a face, atom, and cut whose correlation exceeds that tolerance.
The total refinement step leaves a regular layer fixed; otherwise it chooses such a witness and distributes its cuts. The run starts at the supplied lower layer and iterates this step while keeping the upper layer and tolerance fixed.
import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_OrderedAtomEnergy
import Lean
import Mathlib.Algebra.BigOperators.Expect
import Mathlib.Algebra.BigOperators.Fin
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Algebra.Order.BigOperators.Expect
import Mathlib.Algebra.Order.BigOperators.GroupWithZero.Finset
import Mathlib.Analysis.LocallyConvex.Separation
import Mathlib.Data.Fin.Tuple.Basic
import Mathlib.Data.Fin.Tuple.Finset
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
import Mathlib.Topology.ContinuousMap.Weierstrass
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Distributed preliminary ordered regularity
A Boolean cut witness on an upper face is a product of one predicate on each
immediate lower face. In the shared-face architecture, adjoining such a
witness must refine those genuine lower-face partitions, rather than adjoin
the whole product support to an independent upper partition.
This file carries out that distributed refinement for one witness. It
proves that the induced new boundary refines the abstract one-cut upper
refinement, and therefore inherits the same `ε²` energy increment. Summing
the disjoint upper-atom energies over every upper face gives the preliminary
regularity potential. A single violating atom/cut witness raises this
global potential by `ε²`, while the whole potential is bounded by the number
of upper faces.
-/
namespace Wikipedia.SzemeredisTheorem
open scoped BigOperators
/-- A Boolean product-cut assignment at successor arity, with the deleted
tuple type normalized to `Fin j → G`. -/
abbrev BoundaryBooleanCutAssignment
(G : Type*) (j : ℕ) :=
(i : Fin (j + 1)) → (Fin j → G) → Bool
/-- The support of one coordinate predicate in a boundary Boolean cut. -/
noncomputable def boundaryBooleanComponentCut
{G : Type*} [Fintype G] [DecidableEq G]
{j : ℕ}
(b : BoundaryBooleanCutAssignment G j)
(i : Fin (j + 1)) :
BooleanCutTest (Fin j → G) := by
classical
exact Finset.univ.filter fun z => b i z = true
@[simp]
theorem mem_boundaryBooleanComponentCut
{G : Type*} [Fintype G] [DecidableEq G]
{j : ℕ}
(b : BoundaryBooleanCutAssignment G j)
(i : Fin (j + 1)) (z : Fin j → G) :
z ∈ boundaryBooleanComponentCut b i ↔
b i z = true := by
simp [boundaryBooleanComponentCut]
/-- Full upper-tuple support of a boundary Boolean product cut. -/
noncomputable def boundaryBooleanCutSupport
{G : Type*} [Fintype G] [DecidableEq G]
{j : ℕ}
(b : BoundaryBooleanCutAssignment G j) :
BooleanCutTest (Fin (j + 1) → G) := by
classical
exact Finset.univ.filter fun x =>
∀ i, b i (eraseBoundaryCoordinate i x) = true
@[simp]
theorem mem_boundaryBooleanCutSupport
{G : Type*} [Fintype G] [DecidableEq G]
{j : ℕ}
(b : BoundaryBooleanCutAssignment G j)
(x : Fin (j + 1) → G) :
x ∈ boundaryBooleanCutSupport b ↔
∀ i, b i (eraseBoundaryCoordinate i x) = true := by
simp [boundaryBooleanCutSupport]
/-- Lower-face component cuts contributed to one genuine lower face by a
single upper witness. The definition allows repeated incidences, although
for an increasing ordered face the immediate subfaces are distinct. -/
noncomputable def orderedBoundaryComponentCuts
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(e : OrderedFace k (j + 1))
(b : BoundaryBooleanCutAssignment G j)
(g : OrderedFace k j) :
Finset (BooleanCutTest (Fin j → G)) := by
classical
exact
((Finset.univ : Finset (Fin (j + 1))).filter
(fun i => eraseBoundaryFace e i = g)).image
(fun i => boundaryBooleanComponentCut b i)
theorem boundaryBooleanComponentCut_mem_orderedBoundaryComponentCuts
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(e : OrderedFace k (j + 1))
(b : BoundaryBooleanCutAssignment G j)
(i : Fin (j + 1)) :
boundaryBooleanComponentCut b i ∈
orderedBoundaryComponentCuts e b
(eraseBoundaryFace e i) := by
classical
apply Finset.mem_image.mpr
refine ⟨i, ?_, rfl⟩
simp
/-- Distribute one upper Boolean witness to its genuine immediate subface
partitions. -/
noncomputable def refineOrderedFacePartitionsByBoundaryCut
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(P : OrderedFacePartitionSystem G k j)
(e : OrderedFace k (j + 1))
(b : BoundaryBooleanCutAssignment G j) :
OrderedFacePartitionSystem G k j :=
fun g =>
FacePartition.join (P g)
(FacePartition.generatedBy
(orderedBoundaryComponentCuts e b g))
/-- Distributed component refinement refines every old genuine lower-face
partition. -/
theorem refineOrderedFacePartitionsByBoundaryCut_refines
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(P : OrderedFacePartitionSystem G k j)
(e : OrderedFace k (j + 1))
(b : BoundaryBooleanCutAssignment G j) :
OrderedFacePartitionRefines
(refineOrderedFacePartitionsByBoundaryCut P e b) P := by
intro g
exact FacePartition.join_le_left _ _
/-- At incidence `i`, the refined genuine subface partition also refines
the partition generated by that component predicate alone. -/
theorem refineOrderedFacePartitionsByBoundaryCut_le_component
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(P : OrderedFacePartitionSystem G k j)
(e : OrderedFace k (j + 1))
(b : BoundaryBooleanCutAssignment G j)
(i : Fin (j + 1)) :
refineOrderedFacePartitionsByBoundaryCut P e b
(eraseBoundaryFace e i) ≤
FacePartition.generatedBy
({boundaryBooleanComponentCut b i} :
Finset (Finset (Fin j → G))) := by
apply le_trans (FacePartition.join_le_right _ _)
apply FacePartition.generatedBy_antitone
intro A hA
have hAeq : A = boundaryBooleanComponentCut b i := by
simpa using hA
subst A
exact
boundaryBooleanComponentCut_mem_orderedBoundaryComponentCuts
e b i
/-- Membership in a refined immediate lower atom preserves the corresponding
Boolean component bit. -/
theorem boundaryComponentBit_eq_of_mem_refined_part
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(P : OrderedFacePartitionSystem G k j)
(e : OrderedFace k (j + 1))
(b : BoundaryBooleanCutAssignment G j)
(i : Fin (j + 1))
(x y : Fin j → G)
(hy :
y ∈
(refineOrderedFacePartitionsByBoundaryCut P e b
(eraseBoundaryFace e i)).part x) :
b i x = b i y := by
have hpart :
y ∈
(FacePartition.generatedBy
({boundaryBooleanComponentCut b i} :
Finset (Finset (Fin j → G)))).part x :=
FacePartition.part_subset_of_le
(refineOrderedFacePartitionsByBoundaryCut_le_component
P e b i) x hy
have hsignature :=
(FacePartition.mem_part_generatedBy_iff
({boundaryBooleanComponentCut b i} :
Finset (Finset (Fin j → G))) x y).1 hpart
(boundaryBooleanComponentCut b i) (by simp)
cases hbx : b i x <;> cases hby : b i y <;>
simp [mem_boundaryBooleanComponentCut, hbx, hby] at hsignature ⊢
/-- The distributed boundary refinement makes the full Boolean product
support measurable. Equivalently, it refines the partition generated by
that support. -/
theorem orderedBoundaryPartition_refined_le_generatedSupport
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(P : OrderedFacePartitionSystem G k j)
(e : OrderedFace k (j + 1))
(b : BoundaryBooleanCutAssignment G j) :
orderedBoundaryPartition
(refineOrderedFacePartitionsByBoundaryCut P e b) e ≤
FacePartition.generatedBy
({boundaryBooleanCutSupport b} :
Finset (Finset (Fin (j + 1) → G))) := by
rw [FacePartition.le_iff_part_subset]
intro x y hy
rw [FacePartition.mem_part_generatedBy_iff]
intro A hA
have hAeq : A = boundaryBooleanCutSupport b := by
simpa using hA
subst A
rw [mem_boundaryBooleanCutSupport,
mem_boundaryBooleanCutSupport]
have hboundary :=
(mem_orderedBoundaryPartition_part_iff
(refineOrderedFacePartitionsByBoundaryCut P e b)
e x y).1 hy
constructor
· intro hx i
have hbit :=
boundaryComponentBit_eq_of_mem_refined_part
P e b i
(eraseBoundaryCoordinate i x)
(eraseBoundaryCoordinate i y)
(hboundary i)
exact hbit ▸ hx i
· intro hy' i
have hbit :=
boundaryComponentBit_eq_of_mem_refined_part
P e b i
(eraseBoundaryCoordinate i x)
(eraseBoundaryCoordinate i y)
(hboundary i)
exact hbit.symm ▸ hy' i
/-- The induced distributed boundary refines the abstract refinement
obtained by adjoining the full upper support in one step. -/
theorem orderedBoundaryPartition_refined_le_refineBy
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(P : OrderedFacePartitionSystem G k j)
(e : OrderedFace k (j + 1))
(b : BoundaryBooleanCutAssignment G j) :
orderedBoundaryPartition
(refineOrderedFacePartitionsByBoundaryCut P e b) e ≤
((⟨orderedBoundaryPartition P e⟩ :
FaceRegularityState (Fin (j + 1) → G)).refineBy
(boundaryBooleanCutSupport b)).partition := by
apply FacePartition.le_join_iff.mpr
constructor
· exact orderedBoundaryPartition_mono
(refineOrderedFacePartitionsByBoundaryCut_refines P e b) e
· exact orderedBoundaryPartition_refined_le_generatedSupport
P e b
/-- Aggregate upper-atom energy of a whole rank layer. -/
noncomputable def orderedLayerAtomEnergy
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1)) : ℝ :=
∑ e : OrderedFace k (j + 1),
orderedAtomEnergy lower e (upper e)
theorem orderedLayerAtomEnergy_nonneg
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1)) :
0 ≤ orderedLayerAtomEnergy lower upper := by
unfold orderedLayerAtomEnergy
exact Finset.sum_nonneg fun e _ =>
orderedAtomEnergy_nonneg lower e (upper e)
/-- The atom-energy potential of a whole upper layer is bounded by the
number of upper faces. -/
theorem orderedLayerAtomEnergy_le_card
{G : Type*} [Fintype G] [DecidableEq G] [Nonempty G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1)) :
orderedLayerAtomEnergy lower upper ≤
(Fintype.card (OrderedFace k (j + 1)) : ℝ) := by
unfold orderedLayerAtomEnergy
calc
(∑ e : OrderedFace k (j + 1),
orderedAtomEnergy lower e (upper e)) ≤
∑ _e : OrderedFace k (j + 1), (1 : ℝ) := by
apply Finset.sum_le_sum
intro e _
exact orderedAtomEnergy_le_one lower e (upper e)
_ = (Fintype.card (OrderedFace k (j + 1)) : ℝ) := by
simp
theorem orderedLayerAtomEnergy_mono
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
{fine coarse : OrderedFacePartitionSystem G k j}
(hfc : OrderedFacePartitionRefines fine coarse)
(upper : OrderedFacePartitionSystem G k (j + 1)) :
orderedLayerAtomEnergy coarse upper ≤
orderedLayerAtomEnergy fine upper := by
unfold orderedLayerAtomEnergy
apply Finset.sum_le_sum
intro e _
exact orderedAtomEnergy_mono hfc e (upper e)
/-- One violating upper atom and one Boolean boundary product cut raise the
global layer atom-energy potential by at least `ε²`. -/
theorem orderedLayerAtomEnergy_increment_of_boundaryCut
{G : Type*} [Fintype G] [DecidableEq G] [Nonempty G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
(e : OrderedFace k (j + 1))
(a : (upper e).parts)
(b : BoundaryBooleanCutAssignment G j)
{ε : ℝ} (hε : 0 ≤ ε)
(hcorrelation :
ε ≤
|FaceRegularityState.booleanCutCorrelation
(⟨orderedBoundaryPartition lower e⟩ :
FaceRegularityState (Fin (j + 1) → G))
(partitionAtomIndicator (upper e) a)
(boundaryBooleanCutSupport b)|) :
orderedLayerAtomEnergy lower upper + ε ^ 2 ≤
orderedLayerAtomEnergy
(refineOrderedFacePartitionsByBoundaryCut lower e b)
upper := by
classical
let fine :=
refineOrderedFacePartitionsByBoundaryCut lower e b
let S : FaceRegularityState (Fin (j + 1) → G) :=
⟨orderedBoundaryPartition lower e⟩
have hincrement :
S.energy (partitionAtomIndicator (upper e) a) + ε ^ 2 ≤
(S.refineBy (boundaryBooleanCutSupport b)).energy
(partitionAtomIndicator (upper e) a) :=
S.energy_increment_of_booleanCut
(partitionAtomIndicator (upper e) a)
(boundaryBooleanCutSupport b) hε hcorrelation
have hrefined :
orderedBoundaryPartition fine e ≤
(S.refineBy (boundaryBooleanCutSupport b)).partition := by
exact orderedBoundaryPartition_refined_le_refineBy
lower e b
have hatom :
orderedAtomEnergy lower e (upper e) + ε ^ 2 ≤
orderedAtomEnergy fine e (upper e) := by
unfold orderedAtomEnergy partitionAtomEnergy
let U : Finset (upper e).parts := Finset.univ
have haU : a ∈ U := by simp [U]
have hother :
∑ c ∈ U.erase a,
partitionEnergy
(orderedBoundaryPartition lower e)
(partitionAtomIndicator (upper e) c) ≤
∑ c ∈ U.erase a,
partitionEnergy
(orderedBoundaryPartition fine e)
(partitionAtomIndicator (upper e) c) := by
apply Finset.sum_le_sum
intro c _
exact partitionEnergy_mono
(orderedBoundaryPartition fine e)
(orderedBoundaryPartition lower e)
(orderedBoundaryPartition_mono
(refineOrderedFacePartitionsByBoundaryCut_refines
lower e b) e)
(partitionAtomIndicator (upper e) c)
have hchosen :
partitionEnergy
(orderedBoundaryPartition lower e)
(partitionAtomIndicator (upper e) a) +
ε ^ 2 ≤
partitionEnergy
(orderedBoundaryPartition fine e)
(partitionAtomIndicator (upper e) a) := by
exact le_trans hincrement
(partitionEnergy_mono
(orderedBoundaryPartition fine e)
(S.refineBy (boundaryBooleanCutSupport b)).partition
hrefined
(partitionAtomIndicator (upper e) a))
change
(∑ c ∈ U,
partitionEnergy
(orderedBoundaryPartition lower e)
(partitionAtomIndicator (upper e) c)) +
ε ^ 2 ≤
∑ c ∈ U,
partitionEnergy
(orderedBoundaryPartition fine e)
(partitionAtomIndicator (upper e) c)
calc
(∑ c ∈ U,
partitionEnergy
(orderedBoundaryPartition lower e)
(partitionAtomIndicator (upper e) c)) +
ε ^ 2 =
(∑ c ∈ U.erase a,
partitionEnergy
(orderedBoundaryPartition lower e)
(partitionAtomIndicator (upper e) c)) +
(partitionEnergy
(orderedBoundaryPartition lower e)
(partitionAtomIndicator (upper e) a) +
ε ^ 2) := by
rw [← Finset.sum_erase_add U _ haU]
ring
_ ≤
(∑ c ∈ U.erase a,
partitionEnergy
(orderedBoundaryPartition fine e)
(partitionAtomIndicator (upper e) c)) +
partitionEnergy
(orderedBoundaryPartition fine e)
(partitionAtomIndicator (upper e) a) :=
add_le_add hother hchosen
_ =
∑ c ∈ U,
partitionEnergy
(orderedBoundaryPartition fine e)
(partitionAtomIndicator (upper e) c) :=
Finset.sum_erase_add U _ haU
unfold orderedLayerAtomEnergy
let E : Finset (OrderedFace k (j + 1)) := Finset.univ
have heE : e ∈ E := by simp [E]
have hotherFaces :
∑ d ∈ E.erase e,
orderedAtomEnergy lower d (upper d) ≤
∑ d ∈ E.erase e,
orderedAtomEnergy fine d (upper d) := by
apply Finset.sum_le_sum
intro d _
exact orderedAtomEnergy_mono
(refineOrderedFacePartitionsByBoundaryCut_refines
lower e b)
d (upper d)
change
(∑ d ∈ E, orderedAtomEnergy lower d (upper d)) +
ε ^ 2 ≤
∑ d ∈ E, orderedAtomEnergy fine d (upper d)
calc
(∑ d ∈ E, orderedAtomEnergy lower d (upper d)) +
ε ^ 2 =
(∑ d ∈ E.erase e,
orderedAtomEnergy lower d (upper d)) +
(orderedAtomEnergy lower e (upper e) + ε ^ 2) := by
rw [← Finset.sum_erase_add E _ heE]
ring
_ ≤
(∑ d ∈ E.erase e,
orderedAtomEnergy fine d (upper d)) +
orderedAtomEnergy fine e (upper e) :=
add_le_add hotherFaces hatom
_ =
∑ d ∈ E, orderedAtomEnergy fine d (upper d) :=
Finset.sum_erase_add E _ heE
/-! ## Canonical preliminary regularity run -/
/-- Every upper atom has small residual correlation with every Boolean
boundary product cut. -/
def IsPreliminaryOrderedRegular
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
(ε : ℝ) : Prop :=
∀ (e : OrderedFace k (j + 1))
(a : (upper e).parts)
(b : BoundaryBooleanCutAssignment G j),
|FaceRegularityState.booleanCutCorrelation
(⟨orderedBoundaryPartition lower e⟩ :
FaceRegularityState (Fin (j + 1) → G))
(partitionAtomIndicator (upper e) a)
(boundaryBooleanCutSupport b)| ≤ ε
/-- Failure of preliminary regularity supplies an upper face, one genuine
upper atom, and a violating Boolean boundary cut. -/
theorem exists_boundaryCut_of_not_preliminaryRegular
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
{ε : ℝ}
(h : ¬IsPreliminaryOrderedRegular lower upper ε) :
∃ (e : OrderedFace k (j + 1))
(a : (upper e).parts)
(b : BoundaryBooleanCutAssignment G j),
ε <
|FaceRegularityState.booleanCutCorrelation
(⟨orderedBoundaryPartition lower e⟩ :
FaceRegularityState (Fin (j + 1) → G))
(partitionAtomIndicator (upper e) a)
(boundaryBooleanCutSupport b)| := by
unfold IsPreliminaryOrderedRegular at h
obtain ⟨e, he⟩ := not_forall.mp h
obtain ⟨a, ha⟩ := not_forall.mp he
obtain ⟨b, hb⟩ := not_forall.mp ha
exact ⟨e, a, b, lt_of_not_ge hb⟩
/-- Chosen data witnessing a failure of preliminary regularity. -/
structure PreliminaryIrregularWitness
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
(ε : ℝ) where
face : OrderedFace k (j + 1)
atom : (upper face).parts
cut : BoundaryBooleanCutAssignment G j
correlation :
ε <
|FaceRegularityState.booleanCutCorrelation
(⟨orderedBoundaryPartition lower face⟩ :
FaceRegularityState (Fin (j + 1) → G))
(partitionAtomIndicator (upper face) atom)
(boundaryBooleanCutSupport cut)|
noncomputable def chosenPreliminaryIrregularWitness
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
(ε : ℝ)
(h : ¬IsPreliminaryOrderedRegular lower upper ε) :
PreliminaryIrregularWitness lower upper ε := by
classical
let hex :=
exists_boundaryCut_of_not_preliminaryRegular
lower upper h
let e := Classical.choose hex
let he := Classical.choose_spec hex
let a := Classical.choose he
let ha := Classical.choose_spec he
let b := Classical.choose ha
have hcorr := Classical.choose_spec ha
exact ⟨e, a, b, hcorr⟩
/-- One total preliminary-regularity step. At a regular layer it is the
identity; otherwise it distributes the chosen violating cut. -/
noncomputable def preliminaryOrderedRegularityStep
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
(ε : ℝ) :
OrderedFacePartitionSystem G k j := by
classical
exact
if h : IsPreliminaryOrderedRegular lower upper ε then
lower
else
let W :=
chosenPreliminaryIrregularWitness lower upper ε h
refineOrderedFacePartitionsByBoundaryCut
lower W.face W.cut
/-- Every preliminary step refines the current shared lower layer. -/
theorem preliminaryOrderedRegularityStep_refines
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
(ε : ℝ) :
OrderedFacePartitionRefines
(preliminaryOrderedRegularityStep lower upper ε)
lower := by
classical
by_cases h :
IsPreliminaryOrderedRegular lower upper ε
· simpa [preliminaryOrderedRegularityStep, h] using
OrderedFacePartitionRefines.refl lower
· simp only [preliminaryOrderedRegularityStep, dif_neg h]
let W :=
chosenPreliminaryIrregularWitness lower upper ε h
exact refineOrderedFacePartitionsByBoundaryCut_refines
lower W.face W.cut
/-- At an irregular layer, one total step raises atom energy by `ε²`. -/
theorem preliminaryOrderedRegularityStep_energy_increment
{G : Type*} [Fintype G] [DecidableEq G] [Nonempty G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
{ε : ℝ} (hε : 0 ≤ ε)
(h : ¬IsPreliminaryOrderedRegular lower upper ε) :
orderedLayerAtomEnergy lower upper + ε ^ 2 ≤
orderedLayerAtomEnergy
(preliminaryOrderedRegularityStep lower upper ε)
upper := by
classical
simp only [preliminaryOrderedRegularityStep, dif_neg h]
let W :=
chosenPreliminaryIrregularWitness lower upper ε h
exact orderedLayerAtomEnergy_increment_of_boundaryCut
lower upper W.face W.atom W.cut hε
(le_of_lt W.correlation)
/-- Canonical iteration of distributed preliminary refinement. -/
noncomputable def preliminaryOrderedRegularityRun
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
(ε : ℝ) :
ℕ → OrderedFacePartitionSystem G k j
| 0 => lower
| n + 1 =>
preliminaryOrderedRegularityStep
(preliminaryOrderedRegularityRun lower upper ε n)
upper ε
@[simp]
theorem preliminaryOrderedRegularityRun_zero
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
(ε : ℝ) :
preliminaryOrderedRegularityRun lower upper ε 0 =
lower :=
rfl
@[simp]
theorem preliminaryOrderedRegularityRun_succ
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
(ε : ℝ) (n : ℕ) :
preliminaryOrderedRegularityRun lower upper ε (n + 1) =
preliminaryOrderedRegularityStep
(preliminaryOrderedRegularityRun lower upper ε n)
upper ε :=
rfl
/-- Every run layer refines the initial shared lower layer. -/
theorem preliminaryOrderedRegularityRun_refines
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
(ε : ℝ) (n : ℕ) :
OrderedFacePartitionRefines
(preliminaryOrderedRegularityRun lower upper ε n)
lower := by
induction n with
| zero =>
exact OrderedFacePartitionRefines.refl lower
| succ n ih =>
exact OrderedFacePartitionRefines.trans
(preliminaryOrderedRegularityStep_refines
(preliminaryOrderedRegularityRun lower upper ε n)
upper ε)
ih
/-- The canonical run reaches simultaneous atom regularity before any
prescribed cutoff exceeding the finite layer-energy budget. -/
theorem exists_preliminaryOrderedRegularityRun_index_before
{G : Type*} [Fintype G] [DecidableEq G] [Nonempty G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
{ε : ℝ} {m : ℕ}
(hε : 0 ≤ ε)
(hlong :
(Fintype.card (OrderedFace k (j + 1)) : ℝ) <
(m : ℝ) * ε ^ 2) :
∃ n : ℕ, n < m ∧
IsPreliminaryOrderedRegular
(preliminaryOrderedRegularityRun
lower upper ε n)
upper ε := by
by_contra hregular
have hnotregular :
∀ n, n < m →
¬IsPreliminaryOrderedRegular
(preliminaryOrderedRegularityRun
lower upper ε n)
upper ε := by
intro n hn hreg
exact hregular ⟨n, hn, hreg⟩
have hgain :
∀ n, n < m →
orderedLayerAtomEnergy
(preliminaryOrderedRegularityRun
lower upper ε n)
upper +
ε ^ 2 ≤
orderedLayerAtomEnergy
(preliminaryOrderedRegularityRun
lower upper ε (n + 1))
upper := by
intro n hn
rw [preliminaryOrderedRegularityRun_succ]
exact preliminaryOrderedRegularityStep_energy_increment
(preliminaryOrderedRegularityRun
lower upper ε n)
upper hε (hnotregular n hn)
have growth :
∀ n : ℕ,
(∀ i, i < n →
orderedLayerAtomEnergy
(preliminaryOrderedRegularityRun
lower upper ε i)
upper +
ε ^ 2 ≤
orderedLayerAtomEnergy
(preliminaryOrderedRegularityRun
lower upper ε (i + 1))
upper) →
orderedLayerAtomEnergy
(preliminaryOrderedRegularityRun
lower upper ε 0)
upper +
(n : ℝ) * ε ^ 2 ≤
orderedLayerAtomEnergy
(preliminaryOrderedRegularityRun
lower upper ε n)
upper := by
intro n
induction n with
| zero =>
intro _
simp
| succ n ih =>
intro hn
have hprevious :=
ih (fun i hi =>
hn i (Nat.lt_trans hi (Nat.lt_succ_self n)))
have hstep := hn n (Nat.lt_succ_self n)
calc
orderedLayerAtomEnergy
(preliminaryOrderedRegularityRun
lower upper ε 0)
upper +
(↑(Nat.succ n) : ℝ) * ε ^ 2 =
(orderedLayerAtomEnergy
(preliminaryOrderedRegularityRun
lower upper ε 0)
upper +
(n : ℝ) * ε ^ 2) +
ε ^ 2 := by
push_cast
ring
_ ≤
orderedLayerAtomEnergy
(preliminaryOrderedRegularityRun
lower upper ε n)
upper +
ε ^ 2 := by
linarith
_ ≤
orderedLayerAtomEnergy
(preliminaryOrderedRegularityRun
lower upper ε (n + 1))
upper :=
hstep
have hgrowth := growth m hgain
have hnonneg :
0 ≤
orderedLayerAtomEnergy
(preliminaryOrderedRegularityRun
lower upper ε 0)
upper :=
orderedLayerAtomEnergy_nonneg _ _
have hupper :
orderedLayerAtomEnergy
(preliminaryOrderedRegularityRun
lower upper ε m)
upper ≤
(Fintype.card
(OrderedFace k (j + 1)) : ℝ) :=
orderedLayerAtomEnergy_le_card _ _
linarith
/-! ## Ambient-independent complexity bounds -/
theorem card_orderedBoundaryComponentCuts_le
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(e : OrderedFace k (j + 1))
(b : BoundaryBooleanCutAssignment G j)
(g : OrderedFace k j) :
(orderedBoundaryComponentCuts e b g).card ≤
j + 1 := by
classical
let I : Finset (Fin (j + 1)) :=
(Finset.univ : Finset (Fin (j + 1))).filter
(fun i => eraseBoundaryFace e i = g)
calc
(orderedBoundaryComponentCuts e b g).card ≤
I.card := by
exact Finset.card_image_le
_ ≤ (Finset.univ : Finset (Fin (j + 1))).card := by
exact Finset.card_le_card (Finset.filter_subset _ _)
_ = j + 1 := by simp
/-- One distributed witness multiplies the complexity of each genuine lower
partition by at most `2^(j+1)`. -/
theorem complexity_refineOrderedFacePartitionsByBoundaryCut_le
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(P : OrderedFacePartitionSystem G k j)
(e : OrderedFace k (j + 1))
(b : BoundaryBooleanCutAssignment G j)
(g : OrderedFace k j) :
FacePartition.complexity
(refineOrderedFacePartitionsByBoundaryCut P e b g) ≤
2 ^ (j + 1) *
FacePartition.complexity (P g) := by
have hgenerated :
FacePartition.complexity
(FacePartition.generatedBy
(orderedBoundaryComponentCuts e b g)) ≤
2 ^ (j + 1) := by
exact le_trans
(FacePartition.complexity_generatedBy_le
(orderedBoundaryComponentCuts e b g))
(Nat.pow_le_pow_right (by decide)
(card_orderedBoundaryComponentCuts_le e b g))
calc
FacePartition.complexity
(refineOrderedFacePartitionsByBoundaryCut P e b g) ≤
FacePartition.complexity (P g) *
FacePartition.complexity
(FacePartition.generatedBy
(orderedBoundaryComponentCuts e b g)) :=
FacePartition.complexity_join_le _ _
_ ≤
FacePartition.complexity (P g) *
2 ^ (j + 1) :=
Nat.mul_le_mul_left _ hgenerated
_ =
2 ^ (j + 1) *
FacePartition.complexity (P g) :=
Nat.mul_comm _ _
theorem complexity_preliminaryOrderedRegularityStep_le
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
(ε : ℝ) (g : OrderedFace k j) :
FacePartition.complexity
(preliminaryOrderedRegularityStep
lower upper ε g) ≤
2 ^ (j + 1) *
FacePartition.complexity (lower g) := by
classical
by_cases h :
IsPreliminaryOrderedRegular lower upper ε
· simp only [preliminaryOrderedRegularityStep, dif_pos h]
exact Nat.le_mul_of_pos_left _
(by positivity : 0 < 2 ^ (j + 1))
· simp only [preliminaryOrderedRegularityStep, dif_neg h]
let W :=
chosenPreliminaryIrregularWitness lower upper ε h
exact
complexity_refineOrderedFacePartitionsByBoundaryCut_le
lower W.face W.cut g
/-- Complexity after `n` preliminary steps remains independent of
`Fintype.card G`. -/
theorem complexity_preliminaryOrderedRegularityRun_le
{G : Type*} [Fintype G] [DecidableEq G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
(ε : ℝ) (n : ℕ) (g : OrderedFace k j) :
FacePartition.complexity
(preliminaryOrderedRegularityRun
lower upper ε n g) ≤
(2 ^ (j + 1)) ^ n *
FacePartition.complexity (lower g) := by
induction n with
| zero =>
simp
| succ n ih =>
calc
FacePartition.complexity
(preliminaryOrderedRegularityRun
lower upper ε (n + 1) g) ≤
2 ^ (j + 1) *
FacePartition.complexity
(preliminaryOrderedRegularityRun
lower upper ε n g) := by
rw [preliminaryOrderedRegularityRun_succ]
exact complexity_preliminaryOrderedRegularityStep_le
(preliminaryOrderedRegularityRun
lower upper ε n)
upper ε g
_ ≤
2 ^ (j + 1) *
((2 ^ (j + 1)) ^ n *
FacePartition.complexity (lower g)) :=
Nat.mul_le_mul_left _ ih
_ =
(2 ^ (j + 1)) ^ (n + 1) *
FacePartition.complexity (lower g) := by
rw [pow_succ]
ring
/-- Fixed-budget preliminary regularity with its explicit
ambient-independent lower-layer complexity certificate. -/
theorem exists_preliminaryOrderedRegular_refinement_with_complexity_before
{G : Type*} [Fintype G] [DecidableEq G] [Nonempty G]
{k j : ℕ}
(lower : OrderedFacePartitionSystem G k j)
(upper : OrderedFacePartitionSystem G k (j + 1))
{ε : ℝ} {m : ℕ}
(hε : 0 ≤ ε)
(hlong :
(Fintype.card (OrderedFace k (j + 1)) : ℝ) <
(m : ℝ) * ε ^ 2) :
∃ n : ℕ,
∃ fine : OrderedFacePartitionSystem G k j,
n < m ∧
OrderedFacePartitionRefines fine lower ∧
IsPreliminaryOrderedRegular fine upper ε ∧
∀ g,
FacePartition.complexity (fine g) ≤
(2 ^ (j + 1)) ^ n *
FacePartition.complexity (lower g) := by
obtain ⟨n, hn, hregular⟩ :=
exists_preliminaryOrderedRegularityRun_index_before
lower upper hε hlong
exact
⟨n,
preliminaryOrderedRegularityRun lower upper ε n,
hn,
preliminaryOrderedRegularityRun_refines
lower upper ε n,
hregular,
complexity_preliminaryOrderedRegularityRun_le
lower upper ε n⟩
end Wikipedia.SzemeredisTheorem
/- Materialize compiler-generated declarations promised by this bundle. -/
run_meta do
for requiredName in #[
`Wikipedia.SzemeredisTheorem.PreliminaryIrregularWitness.ctorIdx,
`Wikipedia.SzemeredisTheorem.PreliminaryIrregularWitness.mk.inj,
`Wikipedia.SzemeredisTheorem.PreliminaryIrregularWitness.mk.injEq,
`Wikipedia.SzemeredisTheorem.PreliminaryIrregularWitness.mk.sizeOf_spec,
`Wikipedia.SzemeredisTheorem.PreliminaryIrregularWitness.noConfusionType,
`Wikipedia.SzemeredisTheorem.boundaryBooleanComponentCut.eq_1,
`Wikipedia.SzemeredisTheorem.boundaryBooleanCutSupport.eq_1,
`Wikipedia.SzemeredisTheorem.chosenPreliminaryIrregularWitness.congr_simp,
`Wikipedia.SzemeredisTheorem.preliminaryOrderedRegularityRun.match_1,
`Wikipedia.SzemeredisTheorem.preliminaryOrderedRegularityStep.eq_1
] do
let actualName ← Lean.realizeGlobalConstNoOverloadCore requiredName
unless actualName == requiredName do
throwError "Generated companion resolved to an unexpected name"