Lemma 8, p. 11 — a minion homomorphism from M_BLP+Aff gives (2L+1)-ary polymorphisms with blocks of sizes L and L+1
ProvedPCSPBLPAff.Characterization.lemma_8block-symmetricminionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphism
Let be relational structures with the same signature. Suppose has a minion homomorphism to . Then for every there is a polymorphism and a partition of into two blocks, of sizes and , such that is invariant under every permutation of its arguments that preserves both blocks:
This is the direction "minion homomorphism ⇒ concrete polymorphisms" of the characterization in Theorem 4.
Formalization Note The partition is given by a labelling ; block has elements and block has . As on the page, no promise-template hypothesis is assumed.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Characterization_Setting
Formal statement
namespace PCSPBLPAff.Characterization
/-- Lemma 8, p. 11: if `M_BLP+Aff` has a minion homomorphism to `Pol(𝔸, 𝔹)`, then for every
`L ∈ ℕ`, `Pol(𝔸, 𝔹)` contains a block-symmetric polymorphism of arity `2L + 1` with two blocks
of size `L` and `L + 1`. -/
theorem lemma_8 {τ : Type} {ar : τ → ℕ} {A B : Type}
(𝔸 : PCSPBLPAff.Symmetric.RelStruct τ ar A) (𝔹 : PCSPBLPAff.Symmetric.RelStruct τ ar B) (h : HasMinionHomToPol 𝔸 𝔹) :
∀ L : ℕ, ∃ f : (Fin (2 * L + 1) → A) → B, PCSPBLPAff.Symmetric.IsPolymorphism 𝔸 𝔹 f ∧
∃ β : Fin (2 * L + 1) → Fin 2,
(Finset.univ.filter (fun l => β l = 0)).card = L ∧
(Finset.univ.filter (fun l => β l = 1)).card = L + 1 ∧
PCSPBLPAff.Symmetric.IsBlockSymmetricFor β f := by sorry
end PCSPBLPAff.Characterization
Source
arXiv:1907.04383v3, Lemma 8, p. 11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.