Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.7 — Simple averaging (Algorithm 1)

Open
SubquadCutReach.Faster.Supplement.lemma_3_7

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

graph-theoryonline-learningp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity

Let HHH be a simple graph on nnn labelled vertices, accessible only through undirected cut queries S↦∣EH(S,V∖S)∣S\mapsto|E_H(S,V\setminus S)|S↦∣EH​(S,V∖S)∣, and let b∗∈Znb^*\in\mathbb Z^nb∗∈Zn be a feasible target imbalance vector: some orientation of HHH has imbalance b∗b^*b∗. Let z1,…,zTz_1,\dots,z_Tz1​,…,zT​ be the orientation rules of Algorithm 1 (step η=1/(2n2T)\eta=1/(2n\sqrt{2T})η=1/(2n2T​), y1=0y_1=0y1​=0, pairs directed from the smaller to the larger yty_tyt​-value with ties from the smaller label, yt+1=yt+η(bzt−b∗)y_{t+1}=y_t+\eta(b_{z_t}-b^*)yt+1​=yt​+η(bzt​​−b∗)), and let zˉ=1T∑tzt\bar z=\frac1T\sum_t z_tzˉ=T1​∑t​zt​.

There is a constant C>0C>0C>0 and one deterministic cut-query program such that, for every integer 1≤T≤n1\le T\le n1≤T≤n, every such HHH and every feasible b∗b^*b∗, the program, given nnn, TTT and b∗b^*b∗, halts after at most C nTC\,nTCnT cut queries with output exactly z1,…,zTz_1,\dots,z_Tz1​,…,zT​, and

∥bzˉ−b∗∥1≤4n2T.\|b_{\bar z}-b^*\|_1\le\frac{4n^2}{\sqrt T}.∥bzˉ​−b∗∥1​≤T​4n2​.

This is the averaging step of the warm-up protocol: an average of integral orientations whose imbalance is close to the target, at a query cost linear in nTnTnT.

Formalization Note The program is a finite rational-literal oracle program of the mission's published model; it never sees HHH or an orientation realising b∗b^*b∗. The query count is the charged count of the published model (each vertex-imbalance instruction costs six cut queries). The constant CCC is chosen before nnn, TTT, HHH and b∗b^*b∗.

Differences from the source:

  • encoding: Algorithm 1 deterministically uses O(nT)O(nT)O(nT) undirected cut queries → one Admissible, Deterministic program with RunsWithin … (C*n*T) and C>0C>0C>0 quantified before all instances; reason: the published operational cost model, with a uniform constant
  • encoding: rules z1,…,zTz_1,\dots,z_Tz1​,…,zT​ and potentials y1,…y_1,\dotsy1​,… → 0-based warmRule H b T t, warmPotential, output read by outputRules and required to agree on every pair u<vu<vu<v; reason: index shift; rule cells with u≥vu\ge vu≥v carry no direction in the published directs
  • encoding: bzˉb_{\bar z}bzˉ​ by formula (3) → fractionalImbalance H (warmAverage H b T) with the ±1\pm1±1 encoding of Definition 3.6; reason: the same formula
  • reading: "Only the imbalance computation requires queries to H" → no separate clause; reason: a description of the algorithm, fixed by the output equality, with the cut oracle as the only access to HHH
Preamble
import Definitions.Def_SubquadCutReach_Faster_Tasks
import Definitions.Def_SubquadCutReach_Faster_Supplement_Warmup

set_option autoImplicit false
Formal statement
namespace SubquadCutReach.Faster.Supplement

open SubquadCutReach.Faster

/-- Lemma 3.7, p. 9 (PDF 11), restated p. 13 (PDF 15). One deterministic cut-query program,
uniform over all instances, outputs exactly the rules `z_1, …, z_T` of Algorithm 1 with at most
`C·n·T` charged queries; their average satisfies `‖b_z̄ - b*‖₁ ≤ 4n²/√T`. -/
theorem lemma_3_7 :
    ∃ C : ℝ, 0 < C ∧ ∃ P : Program, Admissible P ∧ Deterministic P ∧
      ∀ (n T : ℕ) (H : SimpleGraph (Fin n)) (b : Fin n → ℤ),
        1 ≤ T → T ≤ n → Feasible H b →
        RunsWithin P (cut H) (targetInput b T)
          (fun m => (∀ t : Fin T, ∀ u v : Fin n, u < v →
              outputRules n T m t u v = warmRule H b T t.val u v) ∧
            l1 (fun v => fractionalImbalance H (warmAverage H b T) v - (b v : ℝ)) ≤
              4 * (n : ℝ) ^ 2 / Real.sqrt (T : ℝ))
          (C * n * T) := by sorry

end SubquadCutReach.Faster.Supplement
Source
Henry Fleischmann, Sagnik Mukhopadhyay, Swagato Sanyal, STOC 2027 submission #503 (October 2026), p. 9, Lemma 3.7 and Algorithm 1 (PDF p. 11); restated p. 13 (PDF p. 15), proof pp. 14–15 (PDF pp. 16–17)

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