Finite face-regularity states and one-cut refinement
DefinitionGreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_Regularityarithmetic-progressionscombinatoricsgreen-tao-port-8822hypergraph-regularity
A Boolean cut test is represented by its finite support and evaluated by its zero–one indicator. A real function is measurable with respect to a finite partition when it is constant on each atom.
A face-regularity state records the current partition. Its structured component is the conditional mean, its residual is the original function minus that component, and its energy is the mean square of the structured component. Boolean cut correlation is the normalized pairing of the residual with a cut indicator. Refinement by one cut joins the current partition with the partition generated by that cut's membership bit. Included support gives the finite energy-increment framework used by subsequent refinement definitions.
Definition code
import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_Energy
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
/-!
# A finite energy-increment regularity step
This file isolates the quantitative part of finite hypergraph regularity which
is independent of the eventual removal argument. A state consists of a
partition of one finite face space. For a hypergraph with several face
spaces, such states are simply assembled into a dependent family
(`FaceRegularitySystem` below).
A Boolean cut test is represented by its support `A : Finset Ω`, and hence by
the `{0,1}`-valued function `finsetIndicator A`. Refining a state by `A`
means adjoining its membership bit to the current partition. The central
result, `energy_increment_of_booleanCut`, says
`ε ≤ |𝔼 x, residual x * 1_A x|`
implies an energy gain of at least `ε ^ 2`. The proof is the exact finite
conditional-expectation proof: the new partition makes `1_A` measurable,
Cauchy--Schwarz bounds the correlation by the squared norm of the new
projection, and the Pythagorean identity identifies that norm with the energy
increment.
-/
namespace Wikipedia.SzemeredisTheorem
open scoped BigOperators
variable {Ω : Type*} [Fintype Ω] [DecidableEq Ω]
/-- A canonical finite `{0,1}`-valued cut test, represented by its support. -/
abbrev BooleanCutTest (Ω : Type*) [DecidableEq Ω] :=
Finset Ω
namespace BooleanCutTest
/-- Evaluation of a Boolean cut test as a real-valued function. -/
def eval (A : BooleanCutTest Ω) : Ω → ℝ :=
finsetIndicator A
omit [Fintype Ω] in
@[simp]
theorem eval_of_mem (A : BooleanCutTest Ω) {x : Ω} (hx : x ∈ A) :
A.eval x = 1 :=
finsetIndicator_of_mem hx
omit [Fintype Ω] in
@[simp]
theorem eval_of_not_mem (A : BooleanCutTest Ω) {x : Ω} (hx : x ∉ A) :
A.eval x = 0 :=
finsetIndicator_of_not_mem hx
omit [Fintype Ω] in
theorem eval_sq (A : BooleanCutTest Ω) (x : Ω) :
A.eval x ^ 2 = A.eval x := by
by_cases hx : x ∈ A <;> simp [hx]
omit [Fintype Ω] in
theorem eval_le_one (A : BooleanCutTest Ω) (x : Ω) :
A.eval x ≤ 1 := by
by_cases hx : x ∈ A <;> simp [hx]
end BooleanCutTest
/-- A real-valued function is measurable with respect to `P` when it is
constant on every atom of `P`. -/
def IsPartitionMeasurable (P : FacePartition Ω) (g : Ω → ℝ) : Prop :=
∀ x y, y ∈ P.part x → g y = g x
namespace IsPartitionMeasurable
/-- Measurability is preserved when the partition is refined. -/
theorem of_le {P Q : FacePartition Ω} {g : Ω → ℝ}
(hPQ : P ≤ Q) (hg : IsPartitionMeasurable Q g) :
IsPartitionMeasurable P g := by
intro x y hy
exact hg x y (FacePartition.part_subset_of_le hPQ x hy)
end IsPartitionMeasurable
/-- The indicator of a generator is measurable for the partition generated
by that cut. -/
theorem booleanCut_measurable_generatedBy (A : BooleanCutTest Ω) :
IsPartitionMeasurable
(FacePartition.generatedBy ({A} : Finset (Finset Ω))) A.eval := by
intro x y hy
have hxy : x ∈ A ↔ y ∈ A := by
have hsignature :=
(FacePartition.mem_part_generatedBy_iff
({A} : Finset (Finset Ω)) x y).1 hy
exact hsignature A (by simp)
by_cases hx : x ∈ A
· have hyA : y ∈ A := hxy.mp hx
simp [hx, hyA]
· have hyA : y ∉ A := by
intro hy
exact hx (hxy.mpr hy)
simp [hx, hyA]
/-- Minimal regularity state for one finite face space. -/
structure FaceRegularityState (Ω : Type*) [Fintype Ω] [DecidableEq Ω] where
partition : FacePartition Ω
namespace FaceRegularityState
/-- The structured component at the current state. -/
noncomputable def structured (S : FaceRegularityState Ω)
(f : Ω → ℝ) : Ω → ℝ :=
conditionalMean S.partition f
/-- The residual after removing the current structured component. -/
noncomputable def residual (S : FaceRegularityState Ω)
(f : Ω → ℝ) : Ω → ℝ :=
fun x => f x - S.structured f x
/-- The `L²` energy visible at the current state. -/
noncomputable def energy (S : FaceRegularityState Ω)
(f : Ω → ℝ) : ℝ :=
partitionEnergy S.partition f
/-- Residual correlation with a Boolean cut test. -/
noncomputable def booleanCutCorrelation
(S : FaceRegularityState Ω) (f : Ω → ℝ)
(A : BooleanCutTest Ω) : ℝ :=
mean fun x => S.residual f x * A.eval x
/-- Adjoin one cut-membership bit to the current partition. -/
def refineBy (S : FaceRegularityState Ω)
(A : BooleanCutTest Ω) : FaceRegularityState Ω where
partition :=
FacePartition.join S.partition
(FacePartition.generatedBy ({A} : Finset (Finset Ω)))
/-- Refining by a cut really refines the old partition. -/
theorem refineBy_le (S : FaceRegularityState Ω)
(A : BooleanCutTest Ω) :
(S.refineBy A).partition ≤ S.partition :=
FacePartition.join_le_left _ _
/-- The adjoined cut is measurable for the refined partition. -/
theorem booleanCut_measurable_refineBy (S : FaceRegularityState Ω)
(A : BooleanCutTest Ω) :
IsPartitionMeasurable (S.refineBy A).partition A.eval := by
apply IsPartitionMeasurable.of_le
(FacePartition.join_le_right S.partition
(FacePartition.generatedBy ({A} : Finset (Finset Ω))))
exact booleanCut_measurable_generatedBy A
/-- Projecting the old residual onto a refinement gives exactly the change
in structured components. -/
theorem conditionalMean_residual_refineBy
(S : FaceRegularityState Ω) (f : Ω → ℝ)
(A : BooleanCutTest Ω) (x : Ω) :
conditionalMean (S.refineBy A).partition (S.residual f) x =
(S.refineBy A).structured f x - S.structured f x := by
change
conditionalMean (S.refineBy A).partition
(fun y => f y - conditionalMean S.partition f y) x =
conditionalMean (S.refineBy A).partition f x -
conditionalMean S.partition f x
rw [conditionalMean_sub]
rw [conditionalMean_reverse_tower_of_le
(S.refineBy A).partition S.partition (S.refineBy_le A)]
/-- A measurable factor may be pulled through a conditional projection in a
global pairing. -/
theorem mean_mul_eq_mean_conditionalMean_mul
(P : FacePartition Ω) (u v : Ω → ℝ)
(hv : IsPartitionMeasurable P v) :
mean (fun x => u x * v x) =
mean (fun x => conditionalMean P u x * v x) := by
calc
mean (fun x => u x * v x) =
mean (conditionalMean P (fun x => u x * v x)) :=
(mean_conditionalMean P _).symm
_ = mean (fun x => conditionalMean P u x * v x) := by
apply congrArg mean
funext x
exact conditionalMean_mul_right_of_constant_on_part
P u v x (hv x)
/-- The residual/cut pairing is the pairing of the new structured increment
with the same cut. -/
theorem booleanCutCorrelation_eq_projection
(S : FaceRegularityState Ω) (f : Ω → ℝ)
(A : BooleanCutTest Ω) :
S.booleanCutCorrelation f A =
mean (fun x =>
((S.refineBy A).structured f x - S.structured f x) *
A.eval x) := by
rw [booleanCutCorrelation]
calc
mean (fun x => S.residual f x * A.eval x) =
mean (fun x =>
conditionalMean (S.refineBy A).partition (S.residual f) x *
A.eval x) :=
mean_mul_eq_mean_conditionalMean_mul
(S.refineBy A).partition (S.residual f) A.eval
(S.booleanCut_measurable_refineBy A)
_ = mean (fun x =>
((S.refineBy A).structured f x - S.structured f x) *
A.eval x) := by
apply congrArg mean
funext x
rw [S.conditionalMean_residual_refineBy f A x]
omit [DecidableEq Ω] in
/-- Global finite Cauchy--Schwarz for the normalized mean. -/
theorem mean_mul_sq_le_sq_mul_sq (u v : Ω → ℝ) :
mean (fun x => u x * v x) ^ 2 ≤
mean (fun x => u x ^ 2) * mean (fun x => v x ^ 2) := by
simpa [mean] using
(Finset.expect_mul_sq_le_sq_mul_sq
(Finset.univ : Finset Ω) u v)
/-- A Boolean cut test has squared `L²` norm at most one. -/
theorem mean_booleanCut_sq_le_one [Nonempty Ω]
(A : BooleanCutTest Ω) :
mean (fun x => A.eval x ^ 2) ≤ 1 := by
apply mean_le_of_le_const
intro x
rw [A.eval_sq x]
exact A.eval_le_one x
/-- Pythagoras identifies the energy increment under one cut refinement. -/
theorem energy_refineBy_sub_eq_mean_sq
(S : FaceRegularityState Ω) (f : Ω → ℝ)
(A : BooleanCutTest Ω) :
(S.refineBy A).energy f - S.energy f =
mean (fun x =>
((S.refineBy A).structured f x - S.structured f x) ^ 2) := by
simpa [energy, structured] using
partitionEnergy_sub_eq_mean_sq
(S.refineBy A).partition S.partition (S.refineBy_le A) f
/-- Squared residual correlation with a Boolean cut is bounded by the exact
energy gained after adjoining that cut. -/
theorem booleanCutCorrelation_sq_le_energyIncrement [Nonempty Ω]
(S : FaceRegularityState Ω) (f : Ω → ℝ)
(A : BooleanCutTest Ω) :
S.booleanCutCorrelation f A ^ 2 ≤
(S.refineBy A).energy f - S.energy f := by
rw [S.booleanCutCorrelation_eq_projection f A]
let d : Ω → ℝ :=
fun x => (S.refineBy A).structured f x - S.structured f x
have hcs :
mean (fun x => d x * A.eval x) ^ 2 ≤
mean (fun x => d x ^ 2) *
mean (fun x => A.eval x ^ 2) :=
mean_mul_sq_le_sq_mul_sq d A.eval
have hd : 0 ≤ mean (fun x => d x ^ 2) :=
mean_nonneg fun x => sq_nonneg _
have hA := mean_booleanCut_sq_le_one A
calc
mean (fun x =>
((S.refineBy A).structured f x - S.structured f x) *
A.eval x) ^ 2 =
mean (fun x => d x * A.eval x) ^ 2 := rfl
_ ≤ mean (fun x => d x ^ 2) *
mean (fun x => A.eval x ^ 2) := hcs
_ ≤ mean (fun x => d x ^ 2) := by
nlinarith
_ = (S.refineBy A).energy f - S.energy f := by
exact (S.energy_refineBy_sub_eq_mean_sq f A).symm
/-- **Quantitative energy increment.** Residual correlation at least `ε`
in absolute value against a `{0,1}` cut test forces energy gain at least
`ε ^ 2` after adjoining that test. -/
theorem energy_increment_of_booleanCut [Nonempty Ω]
(S : FaceRegularityState Ω) (f : Ω → ℝ)
(A : BooleanCutTest Ω) {ε : ℝ}
(hε : 0 ≤ ε)
(hcorrelation : ε ≤ |S.booleanCutCorrelation f A|) :
S.energy f + ε ^ 2 ≤ (S.refineBy A).energy f := by
have hsquare :
ε ^ 2 ≤ S.booleanCutCorrelation f A ^ 2 := by
rw [sq_le_sq]
simpa [abs_of_nonneg hε] using hcorrelation
have hincrement :=
S.booleanCutCorrelation_sq_le_energyIncrement f A
linarith
end FaceRegularityState
end Wikipedia.SzemeredisTheorem
/- Materialize compiler-generated declarations promised by this bundle. -/
run_meta do
for requiredName in #[
`Wikipedia.SzemeredisTheorem.FaceRegularityState.booleanCutCorrelation.eq_1,
`Wikipedia.SzemeredisTheorem.FaceRegularityState.ctorIdx,
`Wikipedia.SzemeredisTheorem.FaceRegularityState.energy.eq_1,
`Wikipedia.SzemeredisTheorem.FaceRegularityState.mk.inj,
`Wikipedia.SzemeredisTheorem.FaceRegularityState.mk.injEq,
`Wikipedia.SzemeredisTheorem.FaceRegularityState.mk.sizeOf_spec,
`Wikipedia.SzemeredisTheorem.FaceRegularityState.noConfusionType,
`Wikipedia.SzemeredisTheorem.FaceRegularityState.structured.eq_1
] do
let actualName ← Lean.realizeGlobalConstNoOverloadCore requiredName
unless actualName == requiredName do
throwError "Generated companion resolved to an unexpected name"
Source