Polymorphisms of the canonical template are the functions whose -ary minors lie in
ProvedSymBoolPCSP.PolChar.pol_canonical_template_iffThis is the canonical (long-code) promise template behind the Galois correspondence between polymorphism families and finite families of promise relations.
Let be a set, , and let , with the coordinates identified with the tuples through a fixed bijection . Let be any set of functions . Consider the single promise relation of arity , where
- consists of the dictator tuples, and
- consists of the value tables of the members of .
Then for every ,
where is the projection (minor) of along . No condition is placed on , so is not assumed.
The statement isolates the construction in the proof of Lemma 6.7 of Brakensiek–Guruswami: polymorphisms of the canonical template are exactly the functions all of whose -ary minors lie in . It can be reused for any Pippenger-type characterization of polymorphism families (promise or ordinary CSPs, e.g. Theorem 6.8 of the same paper) and wherever free structures or minion homomorphisms are described by minor conditions.
Formalization Note The signature has one relation symbol (Unit) of arity N; a tuple of the relation is a function Fin N → D, read through the bijection e : Fin N ≃ (Fin R → D). IsPolymorphism and projection are the platform definitions from PCSPBLPAff_Symmetric_Setting and SymBoolPCSP_PolChar_Basic.
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_PolChar_Basic
namespace SymBoolPCSP.PolChar
open PCSPBLPAff.Symmetric
/-- The canonical ("long-code") promise template of arity `|D^R|`: coordinates are indexed by
`D^R` through `e`, the strong relation consists of the `R` dictator tuples `(y ↦ y_j)`, and the
weak relation consists of the graphs `(y ↦ g y)` of the functions `g ∈ S`. An `L`-ary `f` is a
polymorphism of this single promise relation iff every projection `f^π`, `π : [L] → [R]`,
lies in `S`. -/
theorem pol_canonical_template_iff {D : Type} {R N L : ℕ} (e : Fin N ≃ (Fin R → D))
(S : Set ((Fin R → D) → D)) (f : (Fin L → D) → D) :
IsPolymorphism
(⟨fun _ => {t | ∃ j : Fin R, t = fun c => e c j}⟩ : RelStruct Unit (fun _ => N) D)
(⟨fun _ => {t | ∃ g ∈ S, t = fun c => g (e c)}⟩ : RelStruct Unit (fun _ => N) D) f ↔
∀ π : Fin L → Fin R, projection f π ∈ S := by sorry
end SymBoolPCSP.PolChar