Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.3 — Uniform adaptive transcript total-variation bound

Open
LocalProbeMIS871.Greedy.Supplement.lemma_4_3

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

local-computationmaximal-independent-setp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability

There exist an absolute C>0C>0C>0, an integer threshold Δ0≥2\Delta_0\ge2Δ0​≥2, and positive constants KΔK_\DeltaKΔ​ depending only on Δ\DeltaΔ, such that for every Δ≥Δ0\Delta\ge\Delta_0Δ≥Δ0​, every integer q≥1q\ge1q≥1, every admissible mmm and every deterministic adaptive procedure BBB using at most qqq individual oracle calls,

dTV(T0,T1)≤CqΔ3/2+min⁡{1,KΔ(q+1)2m}.d_{\rm TV}(T_0,T_1)\le \frac{Cq}{\Delta^{3/2}}+\min\left\{1,\frac{K_\Delta(q+1)^2}{m}\right\}.dTV​(T0​,T1​)≤Δ3/2Cq​+min{1,mKΔ​(q+1)2​}.

Here TiT_iTi​ is the observed transcript of that same procedure on the actual finite DiD_iDi​ experiment, comprising the uniform hidden-AAA query's label, all probes and replies, and any final output. The procedure may use n,Δ,k,ℓ,mn,\Delta,k,\ell,mn,Δ,k,ℓ,m as free advice and has no MIS-correctness obligation. The constants are uniform over q,m,Bq,m,Bq,m,B and its output type; CCC is also uniform over Δ\DeltaΔ. The statement includes n≤2q+1n\le2q+1n≤2q+1 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 qqq calls stops or diverges. A transcript is the absorbing state after q+1q+1q+1 local actions, paired with the initial root. The output type is arbitrary, and real exponentiation represents Δ3/2\Delta^{3/2}Δ3/2.

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
Preamble
import Definitions.Def_LocalProbeMIS871_Greedy_Supplement_Observation

open MeasureTheory
open scoped BigOperators Classical
noncomputable section
set_option autoImplicit false
universe uLemma43
Formal statement
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
Source
Peter Kiss, Yuichi Yoshida, The Local Probe Complexity of Maximal Independent Set, STOC 2027 submission #871 (October 2026), p. 27, PDF p. 29, Lemma 4.3

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