Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Cellwise label flows, capacity, conservation and actual allowance

Definition
MultiwayGap2325_Main_Supplement_Flows

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

integrality-gapmainmultiway-cutp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1supplement

For every truncated face ΩS\Omega_SΩS​ and every allowed label ℓ∈S∪{∗}\ell\in S\cup\{*\}ℓ∈S∪{∗}, raw flow data supply a vector-field formula on each cell, and a nonnegative allowance density ϵS\epsilon^SϵS. The star flow is zero. Valid fields are bounded and tangent, continuously differentiable on each closed cell, with equal normal components across shared facets; tangential components may jump.

For every point of each closed cell, all allowed labels ℓ,m\ell,mℓ,m, and every nonempty proper subset I⊂SI\subset SI⊂S, capacity requires

∣∑i∈I(Fℓ,iS−Fm,iS)∣≤∑i∈I,j∈S∖IwijS.\left|\sum_{i\in I}(F_{\ell,i}^S-F_{m,i}^S)\right| \le\sum_{i\in I,j\in S\setminus I}w_{ij}^S.​i∈I∑​(Fℓ,iS​−Fm,iS​)​≤i∈I,j∈S∖I∑​wijS​.

Here weights at a cell boundary use the continuous extension from that cell. The terminal condition is Fℓ,iS=giS1[ℓ=i]F_{\ell,i}^S=g_i^S1[\ell=i]Fℓ,iS​=giS​1[ℓ=i] on ΦiS\Phi_i^SΦiS​. Conservation requires, almost everywhere on each face,

div⁡FℓS≤−∑j∉SFℓ,jS∪{j}+ϵS.\operatorname{div}F_\ell^S\le-\sum_{j\notin S}F_{\ell,j}^{S\cup\{j\}}+\epsilon^S.divFℓS​≤−j∈/S∑​Fℓ,jS∪{j}​+ϵS.

Divergence is the trace of the derivative in deleted coordinates. Parent supply uses the parent's field at the same geometric point. Each face has its own field. Allowances are integrable, and their total is computed once per face:

R=∑S∫ΩSϵS dx.R=\sum_S\int_{\Omega_S}\epsilon^S\,dx.R=S∑​∫ΩS​​ϵSdx.

Flow-instance validity consists of the preceding regularity, capacity, terminal and conservation conditions, with the weighting regularity. It contains no lower bound, cost inequality, certificate existence or optimality assumption. Separate predicates express that label fields are affine on their entire faces and that interior and terminal densities are constant. These allow the existence result to assert its geometric structure explicitly.

Formalization Note A fixed incident-cell choice evaluates formulas on cell walls. Normal continuity makes the relevant normal fluxes agree on shared facets. The source's almost-everywhere conservation leaves lower-dimensional cell intersections immaterial.

Definition code
import Definitions.Def_MultiwayGap2325_Main_Supplement_Geometry

noncomputable section
open MeasureTheory Set
open scoped BigOperators

namespace MultiwayGap2325.Main.Supplement

attribute [local instance] Classical.propDecidable

/-- The star label and precisely the terminal labels of this face. -/
def Allowed {q : ℕ} (S : Face q) (l : CutLabel q) : Prop :=
  l = none ∨ ∃ i ∈ S.val, l = some i

/-- Raw cell formulas and allowances, without validity or any target inequality. -/
structure FlowData (q : ℕ) where
  weighting : Weighting q
  field : (S : Face q) → Set (Vec q) → CutLabel q → Vec q → Vec q
  allowance : Face q → Vec q → ℝ

/-- A fixed choice of incident cell. Only normal components are independent on cell walls. -/
def incidentCell {q : ℕ} (D : FlowData q) (S : Face q) (x : Vec q) : Set (Vec q) :=
  if h : ∃ P ∈ D.weighting.cells S, x ∈ P then h.choose else ∅

def flowAt {q : ℕ} (D : FlowData q) (S : Face q) (l : CutLabel q) (x : Vec q) : Vec q :=
  D.field S (incidentCell D S x) l x

/-- Trace of the derivative in the independent coordinates, with the cell formula at its walls. -/
def cellDivergence {q : ℕ} (D : FlowData q) (S : Face q)
    (P : Set (Vec q)) (l : CutLabel q) (x : Vec q) : ℝ :=
  ∑ i : Coordinates S,
    (fderivWithin ℝ (fun y => D.field S P l (lift S y) i.val)
      (lift S ⁻¹' P) (drop S x)) (Pi.single i 1)

def divergenceAt {q : ℕ} (D : FlowData q) (S : Face q)
    (l : CutLabel q) (x : Vec q) : ℝ :=
  cellDivergence D S (incidentCell D S x) l x

/-- Normal covectors live on all coordinates; adding a constant has no effect on tangent flows. -/
def pairing {q : ℕ} (S : Face q) (a v : Vec q) : ℝ := ∑ i ∈ S.val, a i * v i

/-- Common facets, rather than lower-dimensional intersections, carry normal matching. -/
def CommonFacet {q : ℕ} (S : Face q) (P Q : Set (Vec q)) (a : Vec q) (b : ℝ) : Prop :=
  (P ∩ Q).Nonempty ∧
  Module.finrank ℝ (vectorSpan ℝ (P ∩ Q)) = S.val.card - 2 ∧
  (∃ i ∈ S.val, ∃ j ∈ S.val, a i ≠ a j) ∧
  (∀ x ∈ P, pairing S a x ≤ b) ∧
  (∀ x ∈ Q, b ≤ pairing S a x)

def FlowData.Regular {q : ℕ} (T : ℝ) (D : FlowData q) : Prop :=
  D.weighting.Regular T ∧
  (∀ S P, P ∈ D.weighting.cells S → ∀ l, Allowed S l →
    ContDiffOn ℝ 1 (fun y => D.field S P l (lift S y)) (lift S ⁻¹' P) ∧
    (∀ x ∈ P, (∀ i, i ∉ S.val → D.field S P l x i = 0) ∧
      ∑ i ∈ S.val, D.field S P l x i = 0) ∧
    (∃ M : ℝ, ∀ x ∈ P, ‖D.field S P l x‖ ≤ M)) ∧
  (∀ S P, P ∈ D.weighting.cells S → ∀ x ∈ P, D.field S P none x = 0) ∧
  (∀ S P, P ∈ D.weighting.cells S → ∀ Q ∈ D.weighting.cells S, P ≠ Q →
    ∀ a b, CommonFacet S P Q a b → ∀ l, Allowed S l → ∀ x ∈ P ∩ Q,
      pairing S a (D.field S P l x) = pairing S a (D.field S Q l x)) ∧
  (∀ S, (∀ x ∈ omega T S, 0 ≤ D.allowance S x) ∧
    Integrable (D.allowance S) (faceVolume T S))

/-- Equation (8) at every point of every closed cell. -/
def Capacity {q : ℕ} (D : FlowData q) : Prop :=
  ∀ S P, P ∈ D.weighting.cells S → ∀ x ∈ P,
    ∀ l m, Allowed S l → Allowed S m → ∀ I : Finset (Fin q),
      I.Nonempty → I ⊂ S.val →
      |∑ i ∈ I, (D.field S P l x i - D.field S P m x i)| ≤
        ∑ i ∈ I, ∑ j ∈ S.val \ I, D.weighting.cellWeight S P i j x

/-- The actual terminal boundary values, using every incident cell's formula. -/
def TerminalCondition {q : ℕ} (T : ℝ) (D : FlowData q) : Prop :=
  ∀ S P, P ∈ D.weighting.cells S → ∀ i ∈ S.val,
    ∀ x ∈ P ∩ terminalFacet T S i, ∀ l, Allowed S l →
      D.field S P l x i = if l = some i then D.weighting.terminal S i x else 0

def parent {q : ℕ} (S : Face q) (j : Fin q) : Face q :=
  ⟨insert j S.val, le_trans S.property (Finset.card_le_card (Finset.subset_insert j S.val))⟩

/-- The source sign is minus the parent coordinate flow, not the child's field. -/
def incomingSupply {q : ℕ} (D : FlowData q) (S : Face q)
    (l : CutLabel q) (x : Vec q) : ℝ :=
  - ∑ j ∈ Finset.univ \ S.val, flowAt D (parent S j) l x j

/-- Equation (9) almost everywhere; the top face has the empty parent sum. -/
def Conservation {q : ℕ} (T : ℝ) (D : FlowData q) : Prop :=
  ∀ S l, Allowed S l → ∀ᵐ x ∂faceVolume T S,
    divergenceAt D S l x ≤ incomingSupply D S l x + D.allowance S x

/-- Definition 3.3 with exactly the regularity specified in §5.1. No cost bounds occur here. -/
def IsFlowInstance {q : ℕ} (T : ℝ) (D : FlowData q) : Prop :=
  D.Regular T ∧ Capacity D ∧ TerminalCondition T D ∧ Conservation T D

/-- Each face's allowance is counted once, never once per label. -/
def totalR {q : ℕ} (T : ℝ) (D : FlowData q) : ℝ :=
  ∑ S : Face q, ∫ x, D.allowance S x ∂faceVolume T S

/-- For the existential statement in Theorem 3.5, affine on each whole truncated face. -/
def HasAffineLabelFlows {q : ℕ} (_T : ℝ) (D : FlowData q) : Prop :=
  ∀ S l, Allowed S l → ∃ A : Vec q →L[ℝ] Vec q, ∃ b : Vec q,
    ∀ P ∈ D.weighting.cells S, ∀ x ∈ P, D.field S P l x = A x + b

def HasConstantWeights {q : ℕ} (T : ℝ) (D : FlowData q) : Prop :=
  (∀ S i j, i ∈ S.val → j ∈ S.val → i ≠ j →
    ∃ c : ℝ, ∀ x ∈ omega T S, D.weighting.weight S i j x = c) ∧
  (∀ S i, i ∈ S.val → ∃ c : ℝ, ∀ x ∈ terminalFacet T S i,
    D.weighting.terminal S i x = c)

end MultiwayGap2325.Main.Supplement
Source
Dimitar Chakarov, Yury Makarychev, STOC 2027 submission #697 (October 2026), Definition 3.3, p. 7; §5.1, pp. 11–13, equations (8)–(9), (11)–(13)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me