Lemma 4.5 — Attained defect identity
OpenFiniteGroupTesting.LinearQuery.Supplement.lemma_4_5group-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1property-testingquery-complexity
Let be nonempty finite sets of the same size , and let be any partial map. Then
The minimum is attained by an actual bijection. This identifies image defect with the least disagreement probability and supplies the bijection needed for transport.
Differences from the source:
- encoding: minimum over bijections → IsLeast of the range of bijection error, including membership in that range; reason: this states both attainment and the bound for every bijection, without default infima
- encoding: |G| = |H| = n (Section 4.5) → nonempty finite types with equal cardinality; reason: n >= 1 throughout the paper, and defect divides by n
Preamble
import Definitions.Def_FiniteGroupTesting_LinearQuery_Supplement_PartialMaps set_option autoImplicit false
Formal statement
namespace FiniteGroupTesting.LinearQuery.Supplement
theorem lemma_4_5 {G H : Type} [Fintype G] [Fintype H] [Nonempty G]
[Nonempty H] (hcard : Fintype.card G = Fintype.card H) (ψ : PartialMap G H) :
IsLeast (Set.range (bijectionError ψ)) (defect ψ) := by sorry
end FiniteGroupTesting.LinearQuery.Supplement
Source
Nader Bshouty, STOC 2027 submission #622 (October 2026), p. 28, Lemma 4.5