Claim 4.6 — AT(Ham_k(S)) for |S| ≤ 2
ProvedSymBoolPCSP.CFixing.claim_4_6booleanp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphismspromise-csp
Write for the set of all tuples obtained by applying an alternating-threshold function of odd arity coordinate-wise to elements of . Let . Then
- ;
- ;
- ;
- if and , then ;
- if and in with , then .
These computations identify which symmetric relations can witness that is not a polymorphism, the first step of Lemma 4.5.
Formalization Note In fact 5 the weights range over , the possible Hamming weights, as the source's notation implies.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic open PCSPBLPAff.Symmetric
Formal statement
namespace SymBoolPCSP.CFixing
/-- Claim 4.6 (p. 17), with `AT(P) = ⋃_{L odd} AT_L(P)`: for `k ≥ 1`,
1. `AT(Ham_k({0})) = Ham_k({0})`;
2. `AT(Ham_k({k})) = Ham_k({k})`;
3. `AT(Ham_k({0, k})) = Ham_k({0, k})`;
4. `AT(Ham_k({ℓ})) = Ham_k({1, …, k − 1})` for `k ≥ 2`, `ℓ ∈ {1, …, k − 1}`;
5. `AT(Ham_k({ℓ₁, ℓ₂})) = {0,1}^k` for `k ≥ 2`, `ℓ₁ ≠ ℓ₂` in `{0, …, k}`, `{ℓ₁, ℓ₂} ≠ {0, k}`. -/
theorem claim_4_6 (k : ℕ) (hk : 1 ≤ k) :
ATImage (Ham k {0}) = Ham k {0} ∧
ATImage (Ham k {k}) = Ham k {k} ∧
ATImage (Ham k {0, k}) = Ham k {0, k} ∧
(2 ≤ k → ∀ l : ℕ, 1 ≤ l → l ≤ k - 1 → ATImage (Ham k {l}) = Ham k (Set.Icc 1 (k - 1))) ∧
(2 ≤ k → ∀ l₁ l₂ : ℕ, l₁ ≤ k → l₂ ≤ k → ({l₁, l₂} : Set ℕ) ≠ {0, k} → l₁ ≠ l₂ →
ATImage (Ham k {l₁, l₂}) = Set.univ) := by sorry
end SymBoolPCSP.CFixing
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, p. 17, Claim 4.6 (in the proof of Lemma 4.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.