Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.1 — same-size distance testing for a large induced expander

Open
InducedExpanderTest989.Structural.Supplement.theorem_5_1

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

expandersgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1property-testing

Let d≥3d\ge3d≥3, α,ϕ∈(0,1]\alpha,\phi\in(0,1]α,ϕ∈(0,1], ε∈(0,1)\varepsilon\in(0,1)ε∈(0,1), δ∈(0,1/3]\delta\in(0,1/3]δ∈(0,1/3], put κ=1−min⁡{1/4,ε/(8α)}\kappa=1-\min\{1/4,\varepsilon/(8\alpha)\}κ=1−min{1/4,ε/(8α)} and let n≥4/((1−κ)α)n\ge4/((1-\kappa)\alpha)n≥4/((1−κ)α). Run Algorithm 1 (the mission's structural tester) with this κ\kappaκ, and let ψ\psiψ be its rejection threshold (21) at this κ\kappaκ. Define

μnstru=ψϕ2,μndist=μnstru2d+2.\mu_n^{\rm stru}=\frac{\psi}{\phi^2},\qquad \mu_n^{\rm dist}=\frac{\mu_n^{\rm stru}}{2d+2}.μnstru​=ϕ2ψ​,μndist​=2d+2μnstru​​.

For every simple graph GGG on [n][n][n] of maximum degree at most ddd and every adjacency-list ordering of GGG:

  1. if G∈Pα,ϕG\in\mathcal P_{\alpha,\phi}G∈Pα,ϕ​, the tester accepts with probability at least 1−δ1-\delta1−δ;
  2. if GGG is ε\varepsilonε-far from Pα,μndistϕ2\mathcal P_{\alpha,\mu_n^{\rm dist}\phi^2}Pα,μndist​ϕ2​, it rejects with probability at least 1−δ1-\delta1−δ;
  3. for every d≥3d\ge3d≥3 there is Cd>0C_d>0Cd​>0 such that it makes at most
min⁡{dn, Cd nlog⁡nϕ2⋅1−κα(1−κ)2α5/2log⁡2α log⁡1(1−κ)α⋅log⁡1δ}\min\Big\{dn,\ C_d\,\frac{\sqrt n\log n}{\phi^2}\cdot\frac{1-\kappa\alpha}{(1-\kappa)^2\alpha^{5/2}}\sqrt{\log\tfrac2\alpha\,\log\tfrac1{(1-\kappa)\alpha}}\cdot\log\tfrac1\delta\Big\}min{dn, Cd​ϕ2n​logn​⋅(1−κ)2α5/21−κα​logα2​log(1−κ)α1​​⋅logδ1​}

adjacency-list queries; 4. for fixed d,α,ϕ,ε,δd,\alpha,\phi,\varepsilon,\deltad,α,ϕ,ε,δ and all sufficiently large nnn, its running time is at most a constant times the second term; 5. there are universal constants c1,c2>0c_1,c_2>0c1​,c2​>0 with

c12d+2 ϑn≤μndist≤c22d+2 ϑn,ϑn=(1−κ)2α3(1−κα)log⁡n log⁡1(1−κ)α log⁡2α.\frac{c_1}{2d+2}\,\vartheta_n\le\mu_n^{\rm dist}\le\frac{c_2}{2d+2}\,\vartheta_n,\qquad \vartheta_n=\frac{(1-\kappa)^2\alpha^3}{(1-\kappa\alpha)\log n\,\log\frac1{(1-\kappa)\alpha}\,\log\frac2\alpha}.2d+2c1​​ϑn​≤μndist​≤2d+2c2​​ϑn​,ϑn​=(1−κα)lognlog(1−κ)α1​logα2​(1−κ)2α3​.

The structural tester therefore also solves distance testing at the original core size αn\alpha nαn, with the same query complexity and a rejection multiplier μndist=Θα,ε,d(1/log⁡n)\mu_n^{\rm dist}=\Theta_{\alpha,\varepsilon,d}(1/\log n)μndist​=Θα,ε,d​(1/logn). This is a companion theorem of the mission; it is not used in the proof of the goal.

Formalization Note The tester is the published anchorTest n d α κ ϕ δ at κ = distKappa α ε, and ψ\psiψ is psi n α κ ϕ; since κ≥3/4\kappa\ge3/4κ≥3/4 this is the multiplier of Theorem 4.1 at this κ\kappaκ. Rejection with probability at least 1−δ1-\delta1−δ is 1−δ≤1−Pr⁡[accept]1-\delta\le 1-\Pr[\text{accept}]1−δ≤1−Pr[accept] (the tester always halts with a Boolean output). ε\varepsilonε-far is the predicate FarFrom (strict, normalized by dndndn, targets of maximum degree at most ddd). The constant of clause 3 depends only on ddd; the constant and threshold of clause 4 depend on (d,α,ϕ,ε,δ)(d,\alpha,\phi,\varepsilon,\delta)(d,α,ϕ,ε,δ); the constants of clause 5 are universal.

Differences from the source:

  • encoding: Algorithm 1 run with κ = 1 − min{1/4, ε/(8α)} and ψ of (21) → the published anchorTest and psi at κ = distKappa α ε; reason: the same algorithm and threshold
  • encoding: query complexity and running time "as in Theorem 4.1" → clauses 3–4: queries ≤ min{dn, C_d·(cost shape)} with C_d depending only on d, and running time ≤ C·(cost shape) for all n ≥ N₀ with C, N₀ depending on (d, α, ϕ, ε, δ); reason: Theorem 4.1's bounds at this κ, with the base mission's constant conventions
  • reading: µ^stru is "the multiplier of Theorem 4.1 at the chosen κ" → clause 5 states its Θ-bounds (universal constants) divided by 2d + 2; reason: Theorem 4.1's multiplier carries the stated Θ, which the proof of Theorem 5.1 (PDF p. 36) substitutes and informal Theorem 1.3 states as Θ_{α,ε,d}(1/log n)
Preamble
import Mathlib
import Definitions.Def_InducedExpanderTest989_Structural_Algorithm
import Definitions.Def_InducedExpanderTest989_Structural_Supplement_Distance

set_option autoImplicit false
open scoped BigOperators ENNReal NNReal
noncomputable section
Formal statement
namespace InducedExpanderTest989.Structural.Supplement

/-- Peng–Shen, STOC 2027 #989, Theorem 5.1 (p. 32, PDF 34; multiplier on p. 34, PDF 36).
The tester is Algorithm 1 (`anchorTest`) run with `κ = distKappa α ε = 1 − min{1/4, ε/(8α)}`;
`ψ = psi n α κ ϕ` is (21), `µ^stru ϕ² = ψ` and `µ^dist ϕ² = ψ/(2d + 2)`. Clauses:
(1)–(2) completeness and soundness, (3) queries, (4) large-`n` running time,
(5) `µ^dist = µ^stru/(2d+2)` with `µ^stru = Θ(thetaShape)` and universal constants. -/
theorem theorem_5_1 :
    (∀ (n d : ℕ) (α ϕ ε δ : ℝ), 3 ≤ d → 0 < α → α ≤ 1 → 0 < ϕ → ϕ ≤ 1 → 0 < ε → ε < 1 →
      0 < δ → δ ≤ 1/3 → LargeEnough n α (distKappa α ε) →
      ∀ G : SimpleGraph (Fin n), DegreeBound d G → ∀ O : Oracle n d, IsAdjacencyList G O →
        (HasCore d G α ϕ → 1 - δ ≤ acceptProb O (anchorTest n d α (distKappa α ε) ϕ δ)) ∧
        (FarFrom d ε G (fun H => HasCore d H α (psi n α (distKappa α ε) ϕ / (2 * d + 2))) →
          1 - δ ≤ 1 - acceptProb O (anchorTest n d α (distKappa α ε) ϕ δ))) ∧
    (∀ d : ℕ, 3 ≤ d → ∃ C : ℝ, 0 < C ∧
      ∀ (n : ℕ) (α ϕ ε δ : ℝ), 0 < α → α ≤ 1 → 0 < ϕ → ϕ ≤ 1 → 0 < ε → ε < 1 →
        0 < δ → δ ≤ 1/3 → LargeEnough n α (distKappa α ε) →
        ∀ G : SimpleGraph (Fin n), DegreeBound d G → ∀ O : Oracle n d, IsAdjacencyList G O →
          Prog.queriesOn O (anchorTest n d α (distKappa α ε) ϕ δ) ≤ d * n ∧
          (Prog.queriesOn O (anchorTest n d α (distKappa α ε) ϕ δ) : ℝ) ≤
            C * costShape n α (distKappa α ε) ϕ δ) ∧
    (∀ (d : ℕ) (α ϕ ε δ : ℝ), 3 ≤ d → 0 < α → α ≤ 1 → 0 < ϕ → ϕ ≤ 1 → 0 < ε → ε < 1 →
      0 < δ → δ ≤ 1/3 →
      ∃ (C : ℝ) (N₀ : ℕ), 0 < C ∧ ∀ n : ℕ, N₀ ≤ n → LargeEnough n α (distKappa α ε) →
        ∀ G : SimpleGraph (Fin n), DegreeBound d G → ∀ O : Oracle n d, IsAdjacencyList G O →
          (Prog.timeOn O (anchorTest n d α (distKappa α ε) ϕ δ) : ℝ) ≤
            C * costShape n α (distKappa α ε) ϕ δ) ∧
    (∃ c₁ c₂ : ℝ, 0 < c₁ ∧ 0 < c₂ ∧
      ∀ (n d : ℕ) (α ϕ ε : ℝ), 3 ≤ d → 0 < α → α ≤ 1 → 0 < ϕ → ϕ ≤ 1 → 0 < ε → ε < 1 →
        LargeEnough n α (distKappa α ε) →
        c₁ * thetaShape n α (distKappa α ε) / (2 * d + 2) ≤
            psi n α (distKappa α ε) ϕ / ϕ ^ 2 / (2 * d + 2) ∧
          psi n α (distKappa α ε) ϕ / ϕ ^ 2 / (2 * d + 2) ≤
            c₂ * thetaShape n α (distKappa α ε) / (2 * d + 2)) := by sorry

end InducedExpanderTest989.Structural.Supplement
Source
Pan Peng, Ranran Shen, Testing for a Large Induced Expander: Sublinear Algorithms and Query Lower Bounds, STOC 2027 submission #989 (October 2026), source.pdf SHA-256 98b4035a0ac121d1c1bfb6abdeb3cdb6cf3304ef3cb21b2cd58c97e4bbce6334, p.32 (PDF p.34), Theorem 5.1; multipliers p.34 (PDF p.36); informal Theorem 1.3 p.4 (PDF p.6)

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