Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The cycle-space construction of Section 5

Definition
BourgainUnion_Euclidean_Supplement_CycleSpaceModel

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

discrete-geometryfunctional-analysisp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let G=(V,E)G=(V,E)G=(V,E) be a finite simple graph with an orientation: every edge e=(u,v)e=(u,v)e=(u,v) goes from uuu to vvv. On RE\mathbb R^ERE:

  1. the net inflow ∂:RE→RV\partial:\mathbb R^E\to\mathbb R^V∂:RE→RV, (∂x)w=∑e into wxe−∑e out of wxe(\partial x)_w=\sum_{e\text{ into }w}x_e-\sum_{e\text{ out of }w}x_e(∂x)w​=∑e into w​xe​−∑e out of w​xe​, and the cycle space Z=ker⁡∂Z=\ker\partialZ=ker∂;
  2. the norm (20), with ggg the girth of GGG:
∥x∥W=inf⁡z∈Z(∥z∥2+∥x−z∥1g);\|x\|_W=\inf_{z\in Z}\Bigl(\|z\|_2+\frac{\|x-z\|_1}{\sqrt g}\Bigr);∥x∥W​=z∈Zinf​(∥z∥2​+g​∥x−z∥1​​);
  1. the family P\mathcal PP of linear maps P:RE→ZP:\mathbb R^E\to ZP:RE→Z fixing ZZZ, the norm ∥P∥W→Z=sup⁡w≠0∥Pw∥W/∥w∥W\|P\|_{W\to Z}=\sup_{w\ne0}\|Pw\|_W/\|w\|_W∥P∥W→Z​=supw=0​∥Pw∥W​/∥w∥W​ (where ZZZ carries the norm inherited from WWW), and the relative projection constant λ(Z,W)=inf⁡P∈P∥P∥W→Z\lambda(Z,W)=\inf_{P\in\mathcal P}\|P\|_{W\to Z}λ(Z,W)=infP∈P​∥P∥W→Z​.

Given a spanning tree TTT of GGG and a root ooo: pv∈REp_v\in\mathbb R^Epv​∈RE is the signed indicator of the tree path from ooo to vvv (+1+1+1 on edges traversed along their orientation, −1-1−1 against it); DDD is the depth of TTT from ooo; for each non-tree edge ej=(uj,vj)e_j=(u_j,v_j)ej​=(uj​,vj​), cj=puj+ej−pvjc_j=p_{u_j}+e_j-p_{v_j}cj​=puj​​+ej​−pvj​​, and Ca=∑jajcjCa=\sum_j a_jc_jCa=∑j​aj​cj​ for integer vectors aaa indexed by the non-tree edges. For an integer N≥1N\ge1N≥1, the cells are Uv,N={pv+Ca:a∈{−N,…,N}r}U_{v,N}=\{p_v+Ca: a\in\{-N,\dots,N\}^r\}Uv,N​={pv​+Ca:a∈{−N,…,N}r}, XN=⋃vUv,NX_N=\bigcup_vU_{v,N}XN​=⋃v​Uv,N​ with the metric of ∥⋅∥W\|\cdot\|_W∥⋅∥W​, and AN=Uo,NA_N=U_{o,N}AN​=Uo,N​. Finally e(AN)e(A_N)e(AN​) is the least L≥0L\ge0L≥0 for which some F:XN→ZF:X_N\to ZF:XN​→Z with F(Ca)=CaF(Ca)=CaF(Ca)=Ca on ANA_NAN​ satisfies ∥F(x)−F(y)∥W≤L∥x−y∥W\|F(x)-F(y)\|_W\le L\|x-y\|_W∥F(x)−F(y)∥W​≤L∥x−y∥W​ on XNX_NXN​.

Formalization Note The orientation picks one dart per edge. The tree path is the unique path of the tree, obtained from Mathlib's IsTree.existsUnique_path. The non-tree edges index the coordinates of Zr\mathbb Z^rZr directly. ∥P∥W→Z\|P\|_{W\to Z}∥P∥W→Z​, λ(Z,W)\lambda(Z,W)λ(Z,W) and e(AN)e(A_N)e(AN​) are computed in [0,∞][0,\infty][0,∞].

Definition code
import Mathlib

set_option autoImplicit false
open scoped BigOperators ENNReal
noncomputable section

namespace BourgainUnion.Euclidean.Supplement

variable {V : Type*} [Fintype V] [DecidableEq V]

/-- §5.1, p. 23: an orientation of the simple graph `G` picks, for each edge, one of its two
darts; the edge then goes from the dart's first vertex (its tail) to its second (its head). -/
structure Orientation (G : SimpleGraph V) where
  dart : G.edgeSet → G.Dart
  edge_eq : ∀ e, (dart e).edge = e

variable {G : SimpleGraph V} [DecidableRel G.Adj]

/-- The net inflow map `∂ : ℝ^E → ℝ^V`, `(∂x)_w = Σ_{e into w} x_e − Σ_{e out of w} x_e`. -/
def inflow (O : Orientation G) : (G.edgeSet → ℝ) →ₗ[ℝ] (V → ℝ) :=
  LinearMap.pi fun w => ∑ e : G.edgeSet,
    ((if (O.dart e).snd = w then (1:ℝ) else 0) - (if (O.dart e).fst = w then (1:ℝ) else 0)) •
      LinearMap.proj e

/-- The cycle space `Z = ker ∂ ⊆ ℝ^E`. -/
def cycleSpace (O : Orientation G) : Submodule ℝ (G.edgeSet → ℝ) := LinearMap.ker (inflow O)

/-- The Euclidean norm `‖x‖₂` on `ℝ^E`. -/
def l2 (x : G.edgeSet → ℝ) : ℝ := Real.sqrt (∑ e, x e ^ 2)

/-- The `ℓ₁` norm `‖x‖₁` on `ℝ^E`. -/
def l1 (x : G.edgeSet → ℝ) : ℝ := ∑ e, |x e|

/-- The norm (20), p. 24: `‖x‖_W = inf_{z ∈ Z} (‖z‖₂ + ‖x − z‖₁ / √g)`, `g` the girth of `G`. -/
def normW (O : Orientation G) (x : G.edgeSet → ℝ) : ℝ :=
  ⨅ z : cycleSpace O, (l2 (z : G.edgeSet → ℝ) + l1 (x - (z : G.edgeSet → ℝ)) / Real.sqrt (G.girth : ℝ))

/-- The family `𝒫` of §5.3: linear maps `ℝ^E → Z` that fix `Z` (written as endomorphisms of
`ℝ^E` with range in `Z`). -/
def IsCycleProjection (O : Orientation G) (P : (G.edgeSet → ℝ) →ₗ[ℝ] (G.edgeSet → ℝ)) : Prop :=
  (∀ w, P w ∈ cycleSpace O) ∧ ∀ z ∈ cycleSpace O, P z = z

/-- `‖P‖_{W→Z} = sup_{w ≠ 0} ‖Pw‖ / ‖w‖_W` (p. 23), with `Z` carrying the norm inherited from
`W`; computed in `ℝ≥0∞`. -/
def opNormW (O : Orientation G) (P : (G.edgeSet → ℝ) →ₗ[ℝ] (G.edgeSet → ℝ)) : ℝ≥0∞ :=
  ⨆ w : {w : G.edgeSet → ℝ // w ≠ 0}, ENNReal.ofReal (normW O (P w) / normW O w)

/-- The relative projection constant `λ(Z, W) = inf_{P ∈ 𝒫} ‖P‖_{W→Z}` (p. 23). -/
def projConst (O : Orientation G) : ℝ≥0∞ :=
  ⨅ P : {P : (G.edgeSet → ℝ) →ₗ[ℝ] (G.edgeSet → ℝ) // IsCycleProjection O P}, opNormW O P.1

/-- The indicator vector of an edge, `e ∈ ℝ^E`. -/
def edgeVec (e : G.edgeSet) : G.edgeSet → ℝ := Pi.single e 1

/-- The signed indicator in `ℝ^E` of a walk: `+1` per traversal of an edge along its orientation,
`−1` per traversal against it. -/
def walkVec (O : Orientation G) {a b : V} (p : G.Walk a b) : G.edgeSet → ℝ :=
  fun e => (p.darts.map fun d =>
    if d = O.dart e then (1:ℝ) else if d = (O.dart e).symm then -1 else 0).sum

/-- `p_v` (p. 23): the signed indicator of the path from the root `o` to `v` in the spanning tree
`T ≤ G`. -/
def pathVec (O : Orientation G) {T : SimpleGraph V} (hTG : T ≤ G) (hT : T.IsTree) (o v : V) :
    G.edgeSet → ℝ :=
  walkVec O (((hT.existsUnique_path o v).exists.choose).mapLe hTG)

/-- The depth of the spanning tree `T` from the root `o`. -/
def treeDepth (T : SimpleGraph V) (o : V) : ℕ := Finset.univ.sup fun v => T.dist o v

/-- The non-tree edges `e_j`, indexing the coordinates of `ℤ^r`. -/
abbrev NonTree (G : SimpleGraph V) (T : SimpleGraph V) : Type _ := {e : G.edgeSet // e.1 ∉ T.edgeSet}

open Classical in
/-- `C a = Σ_j a_j c_j` with `c_j = p_{u_j} + e_j − p_{v_j}` for the non-tree edge
`e_j = (u_j, v_j)` (p. 23). -/
def cycleComb (O : Orientation G) {T : SimpleGraph V} (hTG : T ≤ G) (hT : T.IsTree) (o : V)
    (a : NonTree G T → ℤ) : G.edgeSet → ℝ :=
  ∑ j : NonTree G T, (a j : ℝ) • (pathVec O hTG hT o (O.dart j.1).fst + edgeVec j.1 -
      pathVec O hTG hT o (O.dart j.1).snd)

/-- The cell `U_{v,N} = {p_v + C a : a ∈ {−N, …, N}^r}` (p. 24). -/
def cell (O : Orientation G) {T : SimpleGraph V} (hTG : T ≤ G) (hT : T.IsTree) (o : V) (N : ℕ)
    (v : V) : Set (G.edgeSet → ℝ) :=
  {x | ∃ a : NonTree G T → ℤ, (∀ j, |a j| ≤ (N : ℤ)) ∧
    x = pathVec O hTG hT o v + cycleComb O hTG hT o a}

/-- `X_N = ⋃_v U_{v,N}`. -/
def cellUnion (O : Orientation G) {T : SimpleGraph V} (hTG : T ≤ G) (hT : T.IsTree) (o : V)
    (N : ℕ) : Set (G.edgeSet → ℝ) :=
  ⋃ v, cell O hTG hT o N v

/-- `e(A_N)` (p. 24): the optimal Lipschitz constant, for the metric of `‖·‖_W`, of an extension
`F : X_N → Z` of `ϕ(Ca) = Ca` from `A_N = U_{o,N}`; computed in `ℝ≥0∞`. -/
def cellExtConst (O : Orientation G) {T : SimpleGraph V} (hTG : T ≤ G) (hT : T.IsTree) (o : V)
    (N : ℕ) : ℝ≥0∞ :=
  sInf {q | ∃ L : ℝ, 0 ≤ L ∧ (∃ F : (G.edgeSet → ℝ) → (G.edgeSet → ℝ),
      (∀ x ∈ cellUnion O hTG hT o N, F x ∈ cycleSpace O) ∧
      (∀ x ∈ cell O hTG hT o N o, F x = x) ∧
      ∀ x ∈ cellUnion O hTG hT o N, ∀ y ∈ cellUnion O hTG hT o N,
        normW O (F x - F y) ≤ L * normW O (x - y)) ∧
    q = ENNReal.ofReal L}

end BourgainUnion.Euclidean.Supplement
Source
Dimitar Chakarov, Sepideh Mahabadi, Yury Makarychev, Ali Vakilian, Bourgain's Theorem for a Union of Euclidean Metric Spaces, STOC 2027 submission #699 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/699.pdf, PDF = printed p. 23–24, §§5.1–5.4, equation (20), definitions of P, λ(Z, W), p_v, c_j, C, B_N, U_{v,N}, X_N, A_N, e(A_N)

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