Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.1 (algebraic core) — Pol(Γ) ⊆ Pol(Γ′) makes every relation of Γ′ ppp-definable from Γ

Proved
SymBoolPCSP.Galois.theorem_6_1_ppp

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

galois-correspondencep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphismspromise-csp

Let DDD be a finite domain, let Γ\GammaΓ be a finite family of promise relations on DDD and Γ′\Gamma'Γ′ a family of promise relations on DDD. If

Pol(Γ)⊆Pol(Γ′),\mathrm{Pol}(\Gamma) \subseteq \mathrm{Pol}(\Gamma'),Pol(Γ)⊆Pol(Γ′),

then every promise relation (P′,Q′)∈Γ′(P', Q') \in \Gamma'(P′,Q′)∈Γ′ is ppp-definable from Γ\GammaΓ: there are ℓ≥0\ell \ge 0ℓ≥0 and a Γ∪{EQUAL}\Gamma \cup \{\mathrm{EQUAL}\}Γ∪{EQUAL}-PCSP Ψ\PsiΨ on k+ℓk + \ellk+ℓ variables (kkk the arity of (P′,Q′)(P', Q')(P′,Q′)) such that every x∈P′x \in P'x∈P′ extends to an assignment satisfying ΨP\Psi_PΨP​, and every assignment satisfying ΨQ\Psi_QΨQ​ restricts on its first kkk variables to an element of Q′Q'Q′.

This is the promise analogue of the Galois correspondence between clones and relational clones for ordinary CSPs. The printed Theorem 6.1 concludes that there is a polynomial-time reduction from PCSP(Γ′)\mathrm{PCSP}(\Gamma')PCSP(Γ′) to PCSP(Γ)\mathrm{PCSP}(\Gamma)PCSP(Γ); its proof derives that reduction from the ppp-definability stated here, by replacing every clause of Γ′\Gamma'Γ′ with its gadget.

Formalization Note The polynomial-time reduction is not formalized; this is the algebraic statement the proof establishes ("it suffices to show that every promise relation (P′,Q′)∈Γ′(P', Q') \in \Gamma'(P′,Q′)∈Γ′ is ppp-definable from Γ\GammaΓ"). Pol(Γ)⊆Pol(Γ′)\mathrm{Pol}(\Gamma) \subseteq \mathrm{Pol}(\Gamma')Pol(Γ)⊆Pol(Γ′) ranges over all arities L≥0L \ge 0L≥0, nullary (constant) functions included; restricted to L≥1L \ge 1L≥1 the statement would be false (Γ={(D,D)}\Gamma = \{(D, D)\}Γ={(D,D)}, Γ′={(∅,∅)}\Gamma' = \{(\emptyset, \emptyset)\}Γ′={(∅,∅)}, both unary). No assumption P′≠∅P' \ne \emptysetP′=∅ is made. Γ\GammaΓ is finite ([Fintype τ]); Γ′\Gamma'Γ′ may be infinite, since the conclusion is stated per relation.

Preamble
import Mathlib
import Definitions.Def_SymBoolPCSP_Galois_Basic
Formal statement
namespace SymBoolPCSP.Galois

open PCSPBLPAff.Symmetric

/-- **Theorem 6.1, algebraic core** (p. 27; proof p. 28). Let `Γ = (𝔸, 𝔹)` be a finite family and
`Γ′ = (𝔸', 𝔹')` a family of promise relations over the finite domain `D` such that
`Pol(Γ) ⊆ Pol(Γ′)` (polymorphisms of every arity `L ≥ 0`). Then every promise relation
`(P', Q') ∈ Γ′` is ppp-definable from `Γ`. (The printed theorem concludes a polynomial-time
reduction from `PCSP(Γ′)` to `PCSP(Γ)`; that complexity statement is not formalized.) -/
theorem theorem_6_1_ppp {τ τ' : Type} [Fintype τ] {ar : τ → ℕ} {ar' : τ' → ℕ}
    {D : Type} [Fintype D] [DecidableEq D]
    (𝔸 𝔹 : RelStruct τ ar D) (𝔸' 𝔹' : RelStruct τ' ar' D)
    (hΓ : IsPromiseFamily 𝔸 𝔹) (hΓ' : IsPromiseFamily 𝔸' 𝔹')
    (hPol : PolSubset 𝔸 𝔹 𝔸' 𝔹') :
    ∀ R' : τ', PPPDefinable 𝔸 𝔹 (𝔸'.rel R') (𝔹'.rel R') := by sorry

end SymBoolPCSP.Galois
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, p. 27, Theorem 6.1 (proof p. 28)
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

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