Lemma 3.7 — Simple averaging (Algorithm 1)
OpenSubquadCutReach.Faster.Supplement.lemma_3_7Let be a simple graph on labelled vertices, accessible only through undirected cut queries , and let be a feasible target imbalance vector: some orientation of has imbalance . Let be the orientation rules of Algorithm 1 (step , , pairs directed from the smaller to the larger -value with ties from the smaller label, ), and let .
There is a constant and one deterministic cut-query program such that, for every integer , every such and every feasible , the program, given , and , halts after at most cut queries with output exactly , and
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 .
Formalization Note The program is a finite rational-literal oracle program of the mission's published model; it never sees or an orientation realising . The query count is the charged count of the published model (each vertex-imbalance instruction costs six cut queries). The constant is chosen before , , and .
Differences from the source:
- encoding: Algorithm 1 deterministically uses undirected cut queries → one
Admissible,Deterministicprogram withRunsWithin … (C*n*T)and quantified before all instances; reason: the published operational cost model, with a uniform constant - encoding: rules and potentials → 0-based
warmRule H b T t,warmPotential, output read byoutputRulesand required to agree on every pair ; reason: index shift; rule cells with carry no direction in the publisheddirects - encoding: by formula (3) →
fractionalImbalance H (warmAverage H b T)with the 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
import Definitions.Def_SubquadCutReach_Faster_Tasks import Definitions.Def_SubquadCutReach_Faster_Supplement_Warmup set_option autoImplicit false
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