Theorem 6.1 (algebraic core) — Pol(Γ) ⊆ Pol(Γ′) makes every relation of Γ′ ppp-definable from Γ
ProvedSymBoolPCSP.Galois.theorem_6_1_pppLet be a finite domain, let be a finite family of promise relations on and a family of promise relations on . If
then every promise relation is ppp-definable from : there are and a -PCSP on variables ( the arity of ) such that every extends to an assignment satisfying , and every assignment satisfying restricts on its first variables to an element of .
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 to ; its proof derives that reduction from the ppp-definability stated here, by replacing every clause of 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 is ppp-definable from "). ranges over all arities , nullary (constant) functions included; restricted to the statement would be false (, , both unary). No assumption is made. is finite ([Fintype τ]); may be infinite, since the conclusion is stated per relation.
import Mathlib import Definitions.Def_SymBoolPCSP_Galois_Basic
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.