Lemma 9, p. 11 — block-symmetric polymorphisms of arbitrarily high width give a minion homomorphism from M_BLP+Aff
ProvedPCSPBLPAff.Characterization.lemma_9block-symmetriccompactnessminionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphism
Let be relational structures with the same signature on finite domains . Suppose that for every there is a polymorphism that is block-symmetric of width at least , i.e. for some partition of its coordinates into at least one block, every block has at least elements and is invariant under permutations within each block. Then
This is the direction "concrete polymorphisms ⇒ minion homomorphism" of Theorem 4; together with Lemmas 7 and 8 it closes the cycle of equivalences.
Formalization Note The statement is the many-block version asserted by the lemma, not only the one-block case treated in the paper's proof. No promise-template hypothesis is assumed, as on the page.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Characterization_Setting
Formal statement
namespace PCSPBLPAff.Characterization
/-- Lemma 9, p. 11: if `Pol(𝔸, 𝔹)` (for `A`, `B` finite) contains block-symmetric
polymorphisms of arbitrarily high width, then `M_BLP+Aff` admits a minion homomorphism to
`Pol(𝔸, 𝔹)`. -/
theorem lemma_9 {τ : Type} {ar : τ → ℕ} {A B : Type} [Fintype A] [DecidableEq A] [Fintype B]
(𝔸 : PCSPBLPAff.Symmetric.RelStruct τ ar A) (𝔹 : PCSPBLPAff.Symmetric.RelStruct τ ar B)
(h : ∀ N : ℕ, ∃ (L : ℕ) (f : (Fin L → A) → B),
PCSPBLPAff.Symmetric.IsPolymorphism 𝔸 𝔹 f ∧ PCSPBLPAff.Symmetric.HasWidthAtLeast f N) :
HasMinionHomToPol 𝔸 𝔹 := by sorry
end PCSPBLPAff.Characterization
Source
arXiv:1907.04383v3, Lemma 9, p. 11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.