Lemma 8.7 — the three matrices of a cover are not all g-equivalent
ProvedAlgebraicPCSP.OneInThree.lemma_8_7cyclic-operationsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphismspromise-csp
Let be a set, , a homomorphism from (1-in-3) to , and a homomorphism from to (not-all-equal). Let be a polymorphism of and the -ary operation built from . If is a cover of zero-one matrices, then
that is, are not all -equivalent.
This is the single place where the polymorphism and the two homomorphisms enter the combinatorics of §8; every later lemma derives its non-equivalences from it.
Formalization Note Neither primality of nor finiteness of nor cyclicity of is used by the lemma, so they are not assumed.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_AlgebraicPCSP_OneInThree_Structures import Definitions.Def_AlgebraicPCSP_OneInThree_Matrices
Formal statement
namespace AlgebraicPCSP.OneInThree
open PCSPBLPAff.Symmetric
/-- Lemma 8.7 (p. 54): if `X, Y, Z` is a cover, then `X, Y, Z` are not all `g`-equivalent.
Here `s` is a polymorphism of `(D; R)`, `f : T → (D; R)` and `g : (D; R) → H₂` are
homomorphisms, and zero-one matrices are evaluated through `f`. -/
theorem lemma_8_7 {D : Type} (R : Set (Fin 3 → D)) (f : Fin 2 → D) (g : D → Fin 2)
(hf : IsHom oneInThree (ternaryStruct R) f) (hg : IsHom (ternaryStruct R) nae g)
{p : ℕ} (s : (Fin p → D) → D) (hs : IsPolymorphism (ternaryStruct R) (ternaryStruct R) s)
(X Y Z : Fin p → Fin p → Fin 2) (hcover : IsCover X Y Z) :
¬ (GEquiv f g s X Y ∧ GEquiv f g s Y Z) := by sorry
end AlgebraicPCSP.OneInThree
Source
L. Barto, J. Bulín, A. Krokhin, J. Opršal, Algebraic approach to promise constraint satisfaction, arXiv:1811.00970v3, p. 54, Lemma 8.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.