Theorem 4.7 — lower bound for non-adaptive testers with two-sided error
OpenMonoTestDAG.Supplement.theorem_4_7combinatoricsdagmonotonicity-testingp2o-gran-per-chapterp2o-plan-paperp2o-v1property-testing
Let , and let be any -PMRS graph with . Orient every edge from to to form the bipartite DAG . If is sufficiently large, then every randomized non-adaptive -tester for monotonicity on , even with two-sided error, makes
queries in the worst case.
This converts a large edge-disjoint family of positive matchings into an information-theoretic lower bound for monotonicity testing.
Formalization Note. The constants hidden by and by “sufficiently large” are absolute and are quantified before every graph instance. The published PMRS predicate at parameter already contains exactly the conditions and .
Differences from the source:
- encoding: “ is sufficiently large” and → absolute constants with and for every real worst-case query budget ; reason: this expands the two asymptotic phrases and represents the integer query count by an equivalent real upper bound
Preamble
import Mathlib import Definitions.Def_MonoTestDAG_Tester import Definitions.Def_MonoTestDAG_IsPMRSWitness
Formal statement
namespace MonoTestDAG.Supplement
/-- **Theorem 4.7 (Ω(√s) lower bound for non-adaptive testers with two-sided error).** Let
`ε ∈ (0,1/8]`, let `U = (L,R;E)` be any `(s,4ε)`-PMRS graph with `|L|=|R|=n₀`, and
put `G=P(U)`. If `εn₀` is sufficiently large, every randomized non-adaptive two-sided
`ε`-tester on `G` makes `Ω(√s)` queries.
Yoshida, *Testing Monotonicity of Real-Valued Functions on DAGs*, arXiv:2602.15341
(sha256 454609db…), Theorem 4.7, p.20.
**Formalization Note.** The positive constants `C` and `K` are absolute and precede every graph
instance. "Sufficiently large" is `K ≤ ε|L|`; `Ω(√s)` is the worst-case bound
`C√s ≤ q` for every real query budget `q`. -/
theorem theorem_4_7 :
∃ C : ℝ, 0 < C ∧ ∃ K : ℝ, 0 < K ∧
∀ {L R : Type} [Fintype L] [Fintype R] (EU : Finset (L × R)) (ε : ℝ) (s : ℕ),
IsPMRSGraph EU (4 * ε) s →
K ≤ ε * (Fintype.card L : ℝ) →
∀ (T : Tester (L ⊕ R)) (q : ℝ), IsTwoSidedTester (bipDAG EU) ε T →
T.QueriesAtMost q → C * Real.sqrt (s : ℝ) ≤ q := by sorry
end MonoTestDAG.Supplement
Source
Yoshida, Testing Monotonicity of Real-Valued Functions on DAGs, arXiv:2602.15341 (sha256 454609db…), Theorem 4.7, p.20 (PDF 22)