Lemma 5.5 — Soundness of the same Section 5 program
OpenFiniteGroupTesting.LinearQuery.Supplement.lemma_5_5group-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1property-testingquery-complexity
For every and , if the arbitrary input operation is -far from every group operation on the same labels, the complete Section 5 tester satisfies
No spectral, inverse, cancellation, or group promise is imposed on a far input. Undefined locator values are failures. The finite distance grid ensures that -farness also implies -farness when .
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: sufficient absolute constants in Sections 4–5 → fixed c_D=1/500, n_0=1500, gamma=1/10000, C_L=100, C_A=2000000, C_P=1000 and globally chosen expansion/fallback parameters; reason: these instantiate the displayed proof estimates uniformly; the predicates selecting numeric constants assume no existence or correctness, and the existing base theorems supply their witnesses
- encoding: candidate filters and possible early offline rejection before later trials → offline conjunction checked at the final decision, after shared action and product records are sampled; reason: this preserves every acceptance probability and the stated worst-case budget; it accesses the input only through the same visible oracle queries
Preamble
import Definitions.Def_FiniteGroupTesting_LinearQuery_Supplement_UpperTester set_option autoImplicit false
Formal statement
namespace FiniteGroupTesting.LinearQuery.Supplement
theorem lemma_5_5 (n : ℕ) (hn : 2 ≤ n) (ε : ℝ) (hε : 0 < ε)
(hεhalf : ε < 1/2) (op : Table n) (hfar : Far ε op) :
(2/3 : ℝ) ≤ OracleRun.probability op (· = false) (sublinearTester n ε) := by sorry
end FiniteGroupTesting.LinearQuery.Supplement
Source
Nader Bshouty, STOC 2027 submission #622 (October 2026), p. 34, Lemma 5.5