Lemma 4.3 — Uniform adaptive transcript total-variation bound
OpenLocalProbeMIS871.Greedy.Supplement.lemma_4_3There exist an absolute , an integer threshold , and positive constants depending only on , such that for every , every integer , every admissible and every deterministic adaptive procedure using at most individual oracle calls,
Here is the observed transcript of that same procedure on the actual finite experiment, comprising the uniform hidden- query's label, all probes and replies, and any final output. The procedure may use as free advice and has no MIS-correctness obligation. The constants are uniform over and its output type; is also uniform over . The statement includes and post-simplification graphs whose degrees have dropped.
This is the indistinguishability estimate used in the companion lower bound. The probability distance concerns finite inputs, rather than the auxiliary unbounded explorations of the proof.
Formalization Note A deterministic procedure is an arbitrary next-action rule on root and history; all bounded procedures have a representation whose next action after calls stops or diverges. A transcript is the absorbing state after local actions, paired with the initial root. The output type is arbitrary, and real exponentiation represents .
Differences from the source:
- encoding: vertices labeled in [n] → vertices represented by Fin n; reason: adding one to each label is a bijection and preserves all graph and oracle information
- encoding: the finite distributions D₀ and D₁ of §4.1 → uniform counting on finite permutation seeds followed by the specified graph, list and query maps; reason: all fibers have constant multiplicity, so these are exactly the source laws, with no conditioning
- encoding: a procedure using at most q probes and its transcript → a history policy normalized to request no probe at histories of length at least q, observed through step q+1; reason: all source q-probe interactions have this representation, including early stopping or local divergence; unreachable histories can be completed arbitrarily
import Definitions.Def_LocalProbeMIS871_Greedy_Supplement_Observation open MeasureTheory open scoped BigOperators Classical noncomputable section set_option autoImplicit false universe uLemma43
namespace LocalProbeMIS871.Greedy.Supplement
/-- Lemma 4.3, printed p.27 / PDF29; no restriction n > 2q+1 and no MIS premise. -/
theorem lemma_4_3 :
∃ C : ℝ, 0 < C ∧ ∃ Δ₀ : ℕ, 2 ≤ Δ₀ ∧ ∃ K : ℕ → ℝ,
∀ Δ : ℕ, Δ₀ ≤ Δ → 0 < K Δ ∧
∀ q : ℕ, 1 ≤ q → ∀ m : ℕ, Admissible Δ m →
∀ (O : Type uLemma43) (B : Procedure (graphSize Δ m) O), BoundedProcedure B q →
transcriptTV B q ≤ C * (q : ℝ) / (Δ : ℝ) ^ (3 / 2 : ℝ) + rho K Δ q m := by sorry
end LocalProbeMIS871.Greedy.Supplement