Theorem 6.1 — query lower bound Ω(n^{1/2+c_{κ,ϕ}µ}) for structural testing
OpenInducedExpanderTest989.Structural.Supplement.theorem_6_1Let . Fix , and , and put
There are a constant and an integer such that the following holds for every and every . Suppose a randomized adaptive algorithm with unrestricted computation, on simple graphs on of maximum degree at most , accepts every graph in with probability at least and rejects every graph outside with probability at least (conductance normalized by ). Then there are a graph satisfying one of the two promises and an adjacency-list ordering of on which, with positive probability over the internal randomness,
In particular the worst-case query complexity exceeds ; the constants do not depend on .
Together with Theorem 4.1 this nearly determines the best rejection threshold attainable with about queries. This is a companion theorem of the mission; it is not used in the proof of the goal.
Formalization Note Algorithms are probability laws on arbitrary transcript-to-move strategies (the mission's RandAlg), so free uniform vertex samples and unrestricted computation are included. Rejection with probability at least is read as acceptance probability at most . Query counts lie in , a run that never halts counting ; is the ceiling of the real base-2 logarithm and the natural logarithm.
Differences from the source:
- generalization: rejects every NO graph with probability at least 2/3 → accepts every NO graph with probability at most 1/3; reason: a weaker hypothesis on the algorithm (a non-halting run is neither), so the theorem covers every algorithm the source covers
- generalization: worst-case query complexity over promise graphs and internal randomness exceeds A n^{1/2+cµ} → some promise graph with some valid adjacency list has positive probability of more than A n^{1/2+cµ} queries; reason: positive probability gives a random tape exceeding the bound, which is the source's conclusion
- encoding: a randomized adaptive algorithm with unrestricted computation → a probability measure on arbitrary maps from transcripts to moves, queries counted in ℕ∞; reason: every algorithm with a random seed pushes forward to such a law
import Mathlib import Definitions.Def_InducedExpanderTest989_Structural_Graph import Definitions.Def_InducedExpanderTest989_Structural_Supplement_QueryAlgorithms set_option autoImplicit false open scoped BigOperators ENNReal NNReal noncomputable section
namespace InducedExpanderTest989.Structural.Supplement
open MeasureTheory
/-- Peng–Shen, STOC 2027 #989, Theorem 6.1 (p. 34, PDF 36). `d₀ = 512`,
`q = 2^⌈log₂(2/κ)⌉`, `c_{κ,ϕ} = qκϕ²/(16(q − 1) ln d₀)` (22). Every correct randomized adaptive
tester has, on some graph satisfying one of the promises (with some valid adjacency list), positive
probability of making more than `A n^{1/2 + c_{κ,ϕ} µ}` queries. `A` and `n₀` depend only on
`α, κ, ϕ`. -/
theorem theorem_6_1 :
∀ α κ ϕ : ℝ, 0 < α → α ≤ 1 → 0 < κ → κ < 1 → 0 < ϕ → ϕ ≤ 9/20 →
∃ A : ℝ, 0 < A ∧ ∃ n₀ : ℕ, ∀ n : ℕ, n₀ ≤ n → ∀ μ : ℝ, 0 < μ → μ ≤ 1 →
∀ 𝒜 : RandAlg n 512,
IsCorrectTester 𝒜 (fun G => HasCore 512 G α ϕ)
(fun G => ¬ HasCore 512 G (κ * α) (μ * ϕ ^ 2)) →
∃ (G : SimpleGraph (Fin n)) (O : Oracle n 512),
DegreeBound 512 G ∧ IsAdjacencyList G O ∧
(HasCore 512 G α ϕ ∨ ¬ HasCore 512 G (κ * α) (μ * ϕ ^ 2)) ∧
0 < (𝒜 : Measure (QStrategy n 512))
{s | ENNReal.ofReal (A * (n : ℝ) ^ ((1 : ℝ) / 2 +
((2 : ℝ) ^ ⌈Real.logb 2 (2 / κ)⌉₊ * κ * ϕ ^ 2 /
(16 * ((2 : ℝ) ^ ⌈Real.logb 2 (2 / κ)⌉₊ - 1) * Real.log 512)) * μ)) <
((queryCount s O : ℕ∞) : ℝ≥0∞)} := by sorry
end InducedExpanderTest989.Structural.Supplement