Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The universal S-gadget and the specified Phi transformation

Definition
AbelianPromises_Dichotomy_Supplement_Gadget

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

complexity-theoryminionsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1pcsp

For each vertex vvv of a finite Label Cover instance LLL, take a copy of the direct power SXvS^{X_v}SXv​, whose variables are functions Xv→dom⁡(S)X_v\to\operatorname{dom}(S)Xv​→dom(S). For each edge e:v→we:v\to we:v→w, identify bbb in the www-copy with b∘πeb\circ\pi_eb∘πe​ in the vvv-copy. Retain every induced ternary SSS-constraint in the quotient. This defines the concrete universal gadget πS(L)\pi_S(L)πS​(L).

Let J∘J_\circJ∘​ have one variable and the single repeated-variable constraint (x,x,x)(x,x,x)(x,x,x). On a base input III with fixed source template RRR, define

ΦS(I)={J∘,if CSinglAIP rejects on LC⁡(I), πS(κCSinglAIP(LC⁡(I))),otherwise.\Phi_S(I)=\begin{cases} J_\circ,&\text{if CSinglAIP rejects on }\operatorname{LC}(I),\ \pi_S(\kappa_{\mathrm{CSinglAIP}}(\operatorname{LC}(I))),&\text{otherwise}. \end{cases}ΦS​(I)={J∘​,​if CSinglAIP rejects on LC(I), πS​(κCSinglAIP​(LC(I))),​otherwise.​

The source template supplies the current domains implicit in the paper's notation. The definition includes the actual quotient construction and all positional constraints, including repeated variables, empty templates, and isolated variables. It does not postulate the universal-gadget polymorphism correspondence. This is the specific transformation characterized by Theorem C.15.

Definition code
import Mathlib
import Definitions.Def_AbelianPromises_Dichotomy_Supplement_LabelCover

set_option autoImplicit false

namespace AbelianPromises.Dichotomy.Supplement

/-- Vertices of the disjoint union of the direct powers S^(X_v). -/
abbrev PowerVertex {A : Type} (S : Relation A) (L : LCData) :=
  (v : Fin L.n) × ({a // a ∈ L.domain v} → Carrier S)

/-- The universal gadget's identifications b at w ~ b∘π_e at v.
Quot takes the equivalence closure, so chains, either orientation, and parallel edges
all impose their identifications. This is not a homomorphism-existence predicate. -/
def GadgetIdentification {A : Type} (S : Relation A) (L : LCData)
    (u v : PowerVertex S L) : Prop :=
  ∃ (e : Fin L.m)
    (π : {a // a ∈ L.domain (L.source e)} → {a // a ∈ L.domain (L.target e)})
    (b : {a // a ∈ L.domain (L.target e)} → Carrier S),
    (∀ a, (π a).val = L.projection e a.val) ∧
      u = ⟨L.target e, b⟩ ∧ v = ⟨L.source e, b ∘ π⟩

abbrev GadgetVertex {A : Type} (S : Relation A) (L : LCData) :=
  Quot (GadgetIdentification S L)

/-- All constraints from each direct power, mapped to the quotient. -/
def GadgetConstraint {A : Type} (S : Relation A) (L : LCData)
    (t : Fin 3 → GadgetVertex S L) : Prop :=
  ∃ (v : Fin L.n) (u : Fin 3 → ({a // a ∈ L.domain v} → Carrier S)),
    (∀ a, (fun i => u i a) ∈ (actual S).rel ()) ∧
      ∀ i, t i = Quot.mk (GadgetIdentification S L) ⟨v, u i⟩

/-- Turn a concrete finite set of ordered ternary constraints into the base Instance.
The use of sets discards duplicate constraints but preserves repeated positions. -/
noncomputable def instanceOf {V : Type} [Fintype V]
    (constraints : Finset (Fin 3 → V)) : Instance := by
  classical
  exact {
    n := Fintype.card V
    m := constraints.card
    sym := fun _ => ()
    scope := fun c i => Fintype.equivFin V
      (((Fintype.equivFin {t // t ∈ constraints}).symm (Fin.cast (by simp) c)).val i) }

/-- The universal S-gadget π_S(L), including every power constraint and exactly the
edge-generated quotient identifications. Empty S and empty L are retained. -/
noncomputable def universalGadget {A : Type} [Fintype A] (S : Relation A)
    (L : LCData) : Instance := by
  classical
  letI : Fintype (PowerVertex S L) := inferInstance
  letI : Fintype (GadgetVertex S L) := Fintype.ofFinite _
  exact instanceOf (Finset.univ.filter (GadgetConstraint S L))

/-- The current-domain CSP associated with a base input over template R. -/
noncomputable def templateCSP {A : Type} [Fintype A] (R : Relation A)
    (I : Instance) : CurrentCSP := by
  classical
  let e := Fintype.equivFin (Carrier R)
  let tuples : Finset (Fin 3 → ℕ) :=
    (Finset.univ.filter fun t : Fin 3 → Carrier R => t ∈ (actual R).rel ()).image
      (fun t i => (e (t i)).val)
  exact {
    n := I.n
    m := I.m
    arity := fun _ => 3
    scope := I.scope
    domain := fun _ => Finset.range (Fintype.card (Carrier R))
    tuples := fun _ => tuples }

/-- The explicit rejection instance J_circle of Definition C.13. -/
def rejectionInstance : Instance where
  n := 1
  m := 1
  sym _ := ()
  scope _ _ := 0

/-- Definition C.13: reject to J_circle, otherwise output the universal gadget of
kappa(LC(I)). The fixed source R supplies the domains that are implicit in the paper. -/
noncomputable def phi {A C : Type} [Fintype A] [Fintype C] (R : Relation A)
    (S : Relation C) (I : Instance) : Instance :=
  let L := incidence (templateCSP R I)
  match kappa (labelCSP L) with
  | none => rejectionInstance
  | some J => universalGadget S (residualLC L J)

end AbelianPromises.Dichotomy.Supplement
Source
Tamio-Vesa Nakajima, Zephyr Verwimp, Stanislav Živný, STOC 2027 submission #967 (October 2026). Canonical submission artifact; no arXiv pin or acceptance claim. printed p. 21 (PDF p. 22), universal S-gadget paragraph and Definition C.13; Section 2 for template instances.

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