Theorem 6.1 — Adaptive randomized two-sided lower-bound companion theorem
OpenFiniteGroupTesting.LinearQuery.Supplement.theorem_6_1group-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1property-testingquery-complexity
There are absolute constants and an infinite set of sizes such that, for every , every adaptive randomized two-sided -tester for the group property has worst-case query bound satisfying
Both constants are fixed before the infinite size family, accuracy and tester. Each selected size is at least three and has a nonempty accuracy interval. Randomization is an arbitrary probability distribution over the finite set of depth- adaptive query trees, so the statement includes arbitrary internal randomization and unrestricted offline computation. Both lower-bound terms are retained; there is no restriction to constant distance or nonadaptive algorithms.
Differences from the source:
- encoding: labels [n]={1,...,n} → Fin n with zero representing paper label 1; reason: bijective relabelling preserves all tables, distances and query policies
- encoding: every randomized adaptive tester with worst-case query bound t → every probability distribution on all deterministic depth-t adaptive ordered-pair query trees; reason: fixing randomness yields such a tree, and pushing forward any internal random law gives an arbitrary distribution on this finite set
- encoding: infinitely many sizes with the stated accuracy range → an infinite set S with n>=3 and n^(-2)<=epsilon_0 explicitly; reason: discarding finitely many small sizes preserves the source family and makes nonvacuity of every interval explicit
Preamble
import Definitions.Def_FiniteGroupTesting_LinearQuery_Supplement_TranscriptModel set_option autoImplicit false
Formal statement
namespace FiniteGroupTesting.LinearQuery.Supplement
theorem theorem_6_1 :
∃ c ε₀ : ℝ, 0 < c ∧ 0 < ε₀ ∧ ∃ S : Set ℕ, S.Infinite ∧
∀ n ∈ S, 3 ≤ n ∧ (n : ℝ)⁻¹ ^ 2 ≤ ε₀ ∧
∀ ε : ℝ, (n : ℝ)⁻¹ ^ 2 ≤ ε → ε ≤ ε₀ →
∀ t : ℕ, ∀ μ : PMF (QueryTree n t), RandomizedTester ε μ →
c * ((n : ℝ) ^ (1/5 : ℝ) + 1 / ε) ≤ t := by sorry
end FiniteGroupTesting.LinearQuery.Supplement
Source
Nader Bshouty, STOC 2027 submission #622 (October 2026), p. 34–35, Theorem 6.1