Lemma 5.3 — Full action-defect inequality
OpenFiniteGroupTesting.LinearQuery.Supplement.lemma_5_3group-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1property-testingquery-complexity
Let be nonempty finite sets of equal size, with a group structure on , an arbitrary operation on , and arbitrary visible signed labels . Choose marks , a partial map , and any positive conductance lower bound for the marked Cayley multigraph. Then
The action failure rate includes undefined values, the forward multiplication comparison, and the reverse query . No permutation or inverse promise is imposed on the visible maps. The statement covers both image-size regimes in the proof.
Differences from the source:
- encoding: normalized minimum conductance at least Phi>0 → the corresponding boundary inequality for every nonempty set of size at most half; reason: multiplicities are retained and k>0 makes the normalization nonzero
- generalization: the nontrivial-size candidate Cayley graphs of the tester → all equal-size nonempty finite carriers, including size one; reason: at size one the boundary condition is vacuous, but defect is zero for a defined map and one for an undefined map, whose action failure rate is one
Preamble
import Definitions.Def_FiniteGroupTesting_LinearQuery_Supplement_PartialMaps set_option autoImplicit false
Formal statement
namespace FiniteGroupTesting.LinearQuery.Supplement
theorem lemma_5_3 {G H : Type} [Fintype G] [Fintype H] [Nonempty G]
[Group H] (hcard : Fintype.card G = Fintype.card H) {k : ℕ} (hk : 0 < k)
(op : G → G → G) (u : Signed k → G) (a : Fin k → H) (ψ : PartialMap G H)
(Φ : ℝ) (hΦ : 0 < Φ) (hexp : ConductanceAtLeast a Φ) :
defect ψ ≤ ((1 + Φ) / Φ) * etaAct op u a ψ := by sorry
end FiniteGroupTesting.LinearQuery.Supplement
Source
Nader Bshouty, STOC 2027 submission #622 (October 2026), p. 31, Lemma 5.3