Lemma 6.7 — a projection-closed finitizable family containing id_D is Pol(Γ) for a finite Γ
ProvedSymBoolPCSP.PolChar.lemma_6_7p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphismspromise-csp
Let be a finite domain and let be a family of functions over which is projection-closed and finitizable and contains the identity . Then there is a family of finitely many promise relations over such that
This is the sufficiency half of Theorem 6.5, a finite-signature analogue of Pippenger's characterization of polymorphism families.
Formalization Note The finite family is existential together with its signature: a finite type τ, arities ar : τ → ℕ, and structures 𝔸 ⊆ 𝔹. The equality is asserted at every arity . No assumption is made.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_PolChar_Basic
Formal statement
namespace SymBoolPCSP.PolChar
open PCSPBLPAff.Symmetric
/-- Lemma 6.7 (p. 29): if a family `F` of functions over a finite domain `D` is
projection-closed, finitizable and contains `id_D`, then there is a finite family `Γ` of
promise relations (a finite signature `τ` with arities `ar` and structures `𝔸 ⊆ 𝔹`) with
`Pol(Γ) = F` at every arity `L ≥ 1`. -/
theorem lemma_6_7 {D : Type} [Fintype D] [DecidableEq D] (F : FunFamily D)
(hpc : ProjectionClosed F) (hfin : Finitizable F) (hid : ContainsId F) :
∃ (τ : Type) (_ : Fintype τ) (ar : τ → ℕ) (𝔸 𝔹 : RelStruct τ ar D),
(∀ R : τ, 𝔸.rel R ⊆ 𝔹.rel R) ∧ ∀ L : ℕ, 0 < L → Pol 𝔸 𝔹 L = F L := by sorry
end SymBoolPCSP.PolChar
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, p. 29, Lemma 6.7 (proof pp. 29–30)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.