Grouping frozen bundle remainders into proper-face cut tests
DefinitionGreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_HypergraphBundleFrozenCutA selected nonempty occurrence edge is enumerated by its ordered projected base face. The bundle supplies the corresponding occurrence-vertex and tuple equivalences.
For each remainder edge after erasing a maximum-cardinality edge, a selected vertex omitted by that remainder is chosen and converted to its canonical coordinate. The missing-vertex choice is totalized outside the used remainder edges by an arbitrary vertex of the selected edge.
Insertion reconstructs a selected-edge tuple from an erased coordinate and a filler value, then combines it with frozen outside variables. Grouping each remainder factor by its chosen missing coordinate gives the deleted-coordinate cut-test family. Factors remain indexed by occurrence edges, so repeated projected base faces remain separate contributions.
import Definitions.Def_GreenTaoPort_Wikipedia_SzemeredisTheorem_Hypergraph_HypergraphBundleFrozenUniformity
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.Algebra.Order.Chebyshev
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
/-!
# Frozen bundle remainders are face cuts
Fix a maximum-cardinality nonempty occurrence edge `g₀`. Every other
occurrence edge omits a vertex of `g₀`; we assign that edge to the
corresponding coordinate in the increasing enumeration of the projected
edge. After the variables outside `g₀` are frozen, factors with the same
assigned coordinate form one member of a face-cut family.
The construction groups *occurrence* edges, rather than projected faces.
This is important because distinct occurrence edges in a bundle may have
the same projection. The resulting product therefore retains every
factor with its correct multiplicity.
-/
namespace Wikipedia.SzemeredisTheorem
open scoped BigOperators
namespace HypergraphBundle
variable {G : Type*} [Fintype G] [DecidableEq G]
{k r : ℕ}
/-! ## The canonical occurrence-edge ordering -/
/-- The increasing enumeration of the projected selected edge. -/
noncomputable def frozenProjectedEdgeOrderIso
{K : Type*} [Fintype K] [DecidableEq K]
(B : HypergraphBundle (Fin k) K
(orderedConfigurationBaseEdges k r))
{g : Finset K} (hg : g ∈ B.edges)
(hne : g.Nonempty) :
Fin ((B.orderedConfigurationBundleFace hg hne).lowerRank.1 + 1) ≃
{j : Fin k // j ∈ g.image B.projection} := by
let t := g.image B.projection
let e := B.orderedConfigurationBundleFace hg hne
have hcard : t.card = e.lowerRank.1 + 1 := by
have hedge :
positiveOrderedFaceEdge e = t := by
dsimp [e, orderedConfigurationBundleFace, t]
exact positiveOrderedFaceEdge_ofEdge
(g.image B.projection)
(B.projectedEdge_nonempty hg hne)
(B.projectedEdge_card_le hg)
calc
t.card = (positiveOrderedFaceEdge e).card :=
congrArg Finset.card hedge.symm
_ = e.rank := positiveOrderedFaceEdge_card e
_ = e.lowerRank.1 + 1 := rfl
exact (t.orderIsoOfFin hcard).toEquiv
/-- Increasing projected coordinates, lifted to their unique occurrence
vertices in the selected edge. -/
noncomputable def frozenOccurrenceOrderEquiv
{K : Type*} [Fintype K] [DecidableEq K]
(B : HypergraphBundle (Fin k) K
(orderedConfigurationBaseEdges k r))
{g : Finset K} (hg : g ∈ B.edges)
(hne : g.Nonempty) :
Fin ((B.orderedConfigurationBundleFace hg hne).lowerRank.1 + 1) ≃
{v : K // v ∈ g} :=
(B.frozenProjectedEdgeOrderIso hg hne).trans
(B.projectionEquiv hg).symm
/-- Reindex selected-occurrence-edge tuples by their canonical projected
face coordinates. -/
noncomputable def frozenBundleFaceTupleEquiv
{K : Type*} [Fintype K] [DecidableEq K]
(B : HypergraphBundle (Fin k) K
(orderedConfigurationBaseEdges k r))
{g : Finset K} (hg : g ∈ B.edges)
(hne : g.Nonempty) :
({v : K // v ∈ g} → G) ≃
(Fin ((B.orderedConfigurationBundleFace hg hne).lowerRank.1 + 1) →
G) :=
(Equiv.arrowCongr
(B.projectionEquiv hg)
(Equiv.refl G)).trans
(Equiv.arrowCongr
(B.frozenProjectedEdgeOrderIso hg hne).symm
(Equiv.refl G))
/-! ## Assigning each remainder edge to a missing coordinate -/
/-- A totalized selected vertex omitted by a remainder occurrence edge.
The fallback branch is never used in the cut product. -/
noncomputable def frozenBundleMissingVertex
{K : Type*} [Fintype K] [DecidableEq K]
(B : HypergraphBundle (Fin k) K
(orderedConfigurationBaseEdges k r))
{g₀ : Finset K}
(hmax : ∀ g ∈ B.edges, g.card ≤ g₀.card)
(hne : g₀.Nonempty)
(g : Finset K) : {v : K // v ∈ g₀} :=
if hg : g ∈ B.edges.erase g₀ then
⟨Classical.choose
(B.exists_selectedVertex_not_mem_of_mem_erase hg hmax),
(Classical.choose_spec
(B.exists_selectedVertex_not_mem_of_mem_erase hg hmax)).1⟩
else
⟨Classical.choose hne, Classical.choose_spec hne⟩
/-- Coordinate of the selected missing occurrence vertex. -/
noncomputable def frozenBundleMissingCoordinate
{K : Type*} [Fintype K] [DecidableEq K]
(B : HypergraphBundle (Fin k) K
(orderedConfigurationBaseEdges k r))
{g₀ : Finset K} (hg₀ : g₀ ∈ B.edges)
(hmax : ∀ g ∈ B.edges, g.card ≤ g₀.card)
(hne : g₀.Nonempty)
(g : Finset K) :
Fin ((B.orderedConfigurationBundleFace hg₀ hne).lowerRank.1 + 1) :=
(B.frozenOccurrenceOrderEquiv hg₀ hne).symm
(B.frozenBundleMissingVertex hmax hne g)
/-! ## Reconstructing and grouping a frozen remainder -/
/-- Insert an arbitrary value at one erased canonical face coordinate and
transport the resulting tuple back to the selected occurrence edge. -/
noncomputable def frozenBundleInsertedSelectedTuple
{K : Type*} [Fintype K] [DecidableEq K]
(B : HypergraphBundle (Fin k) K
(orderedConfigurationBaseEdges k r))
{g₀ : Finset K} (hg₀ : g₀ ∈ B.edges)
(hne : g₀.Nonempty)
(i :
Fin ((B.orderedConfigurationBundleFace hg₀ hne).lowerRank.1 + 1))
(a : G)
(y :
Fin (B.orderedConfigurationBundleFace hg₀ hne).lowerRank.1 → G) :
{v : K // v ∈ g₀} → G :=
(B.frozenBundleFaceTupleEquiv hg₀ hne).symm
(Fin.insertNth i a y)
/-- Recombine an inserted selected-edge tuple with the frozen outside
variables. -/
noncomputable def frozenBundleInsertedAssignment
{K : Type*} [Fintype K] [DecidableEq K]
(B : HypergraphBundle (Fin k) K
(orderedConfigurationBaseEdges k r))
{g₀ : Finset K} (hg₀ : g₀ ∈ B.edges)
(hne : g₀.Nonempty)
(i :
Fin ((B.orderedConfigurationBundleFace hg₀ hne).lowerRank.1 + 1))
(a : G)
(y :
Fin (B.orderedConfigurationBundleFace hg₀ hne).lowerRank.1 → G)
(z : EdgeComplement g₀ → G) : K → G :=
(splitEdgeEquiv g₀).symm
(B.frozenBundleInsertedSelectedTuple hg₀ hne i a y, z)
/-- The grouped frozen remainder cut test. The product is indexed by
occurrence edges, so repeated projected faces remain separate factors. -/
noncomputable def frozenBundleRemainderCutTest
{K : Type*} [Fintype K] [DecidableEq K]
{C : OrderedPartitionComplex G k r}
(A : ClosedOrderedAtomConfiguration G k r C)
(B : HypergraphBundle (Fin k) K
(orderedConfigurationBaseEdges k r))
{g₀ : Finset K} (hg₀ : g₀ ∈ B.edges)
(hmax : ∀ g ∈ B.edges, g.card ≤ g₀.card)
(hne : g₀.Nonempty)
(a : G)
(z : EdgeComplement g₀ → G) :
CutTestFamily G
((B.orderedConfigurationBundleFace hg₀ hne).lowerRank.1 + 1) :=
fun i y =>
∏ g ∈ B.edges.erase g₀,
if _hcoord :
B.frozenBundleMissingCoordinate hg₀ hmax hne g = i
then
B.pullbackBaseEdgeWeight
(orderedConfigurationBaseWeight A) g
(edgeTuple g
(B.frozenBundleInsertedAssignment hg₀ hne i a y z))
else 1
/-! ## Exact correlation transport -/
end HypergraphBundle
end Wikipedia.SzemeredisTheorem
/- Materialize compiler-generated declarations promised by this bundle. -/
run_meta do
for requiredName in #[
`Wikipedia.SzemeredisTheorem.HypergraphBundle.frozenBundleMissingCoordinate.congr_simp,
`Wikipedia.SzemeredisTheorem.HypergraphBundle.frozenBundleMissingCoordinate.eq_1,
`Wikipedia.SzemeredisTheorem.HypergraphBundle.frozenBundleMissingVertex.congr_simp,
`Wikipedia.SzemeredisTheorem.HypergraphBundle.frozenBundleMissingVertex.eq_1
] do
let actualName ← Lean.realizeGlobalConstNoOverloadCore requiredName
unless actualName == requiredName do
throwError "Generated companion resolved to an unexpected name"