Proof of Theorem 6.1 — P′ ⊆ S′_m ⊆ T′_m ⊆ Q′
ProvedSymBoolPCSP.Galois.chaingalois-correspondencep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphismspromise-csp
Let be a finite domain, a finite family and a family of promise relations on with . Let have arity , let and let be an ordering of the elements of . With and as in the previous milestone,
Together with the sandwich remark this makes ppp-definable from , and then from by transitivity.
Formalization Note The ordering of is a bijection e : Fin m ≃ P', so is enforced by the bijection; (empty ) is included. ranges over all arities .
Preamble
import Mathlib import Definitions.Def_SymBoolPCSP_Galois_Basic
Formal statement
namespace SymBoolPCSP.Galois
open PCSPBLPAff.Symmetric
/-- Proof of Theorem 6.1, p. 28: let `Pol(Γ) ⊆ Pol(Γ′)`, let `(P', Q') = (𝔸'.rel R', 𝔹'.rel R')`
be a relation of `Γ′` with `m = |P'|`, and let `x^1, …, x^m` be an ordering `e` of `P'`. With
`(y_i)_j = (x^j)_i`, `S′_m = {(f(y_1), …, f(y_k)) : f ∈ S_m}` and
`T′_m = {(f(y_1), …, f(y_k)) : f ∈ T_m}`, we have `P' ⊆ S′_m ⊆ T′_m ⊆ Q'`. -/
theorem chain {τ τ' : Type} [Fintype τ] {ar : τ → ℕ} {ar' : τ' → ℕ}
{D : Type} [Fintype D] [DecidableEq D]
(𝔸 𝔹 : RelStruct τ ar D) (𝔸' 𝔹' : RelStruct τ' ar' D)
(hΓ : IsPromiseFamily 𝔸 𝔹) (hΓ' : IsPromiseFamily 𝔸' 𝔹')
(hPol : PolSubset 𝔸 𝔹 𝔸' 𝔹') (R' : τ') (m : ℕ) (e : Fin m ≃ 𝔸'.rel R') :
𝔸'.rel R' ⊆ evalAt (fun j => (e j : Fin (ar' R') → D)) (SL 𝔸 m) ∧
evalAt (fun j => (e j : Fin (ar' R') → D)) (SL 𝔸 m) ⊆
evalAt (fun j => (e j : Fin (ar' R') → D)) (TL 𝔸 𝔹 m) ∧
evalAt (fun j => (e j : Fin (ar' R') → D)) (TL 𝔸 𝔹 m) ⊆ 𝔹'.rel R' := by sorry
end SymBoolPCSP.Galois
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, p. 28, proof of Theorem 6.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.