Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.3 — Full action-defect inequality

Open
FiniteGroupTesting.LinearQuery.Supplement.lemma_5_3

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

group-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1property-testingquery-complexity

Let G,HG,HG,H be nonempty finite sets of equal size, with a group structure on HHH, an arbitrary operation ∗*∗ on GGG, and arbitrary visible signed labels uju_juj​. Choose k>0k>0k>0 marks ai∈Ha_i\in Hai​∈H, a partial map Ψ:G⇀H\Psi:G\rightharpoonup HΨ:G⇀H, and any positive conductance lower bound Φ\PhiΦ for the marked Cayley multigraph. Then

defect⁡(Ψ)≤1+ΦΦηact(Ψ).\operatorname{defect}(\Psi)\le\frac{1+\Phi}{\Phi}\eta_{\rm act}(\Psi).defect(Ψ)≤Φ1+Φ​ηact​(Ψ).

The action failure rate includes undefined values, the forward multiplication comparison, and the reverse query (x∗uj)∗u−j=x(x*u_j)*u_{-j}=x(x∗uj​)∗u−j​=x. 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

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me