Claim 4.8 — Maj(Ham_k(S)) is Ham_k of an interval
ProvedSymBoolPCSP.CFixing.claim_4_8booleanp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polymorphismspromise-csp
Write . Let .
- If , then .
- If with and , then
This is the majority analogue of Claim 4.6, the first step of Lemma 4.7.
Formalization Note The interval bounds are computed in , since can be negative. is a finite set of weights in , the setting in which and are the extreme weights of ; its nonemptiness is a binder only so that and are defined (it follows from ).
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.8 (p. 19), with `Maj(P) = ⋃_{L odd} Maj_L(P)`: for `k ≥ 1`, if `P ⊆ Ham_k({0, k})` then
`Maj(P) = P`; and if `P = Ham_k(S)` with `S ⊆ {0, …, k}` and `S ∖ {0, k} ≠ ∅`, then
`Maj(P) = Ham_k({0, …, k} ∩ {2(min S) − k + 1, …, 2(max S) − 1})` (bounds computed in `ℤ`). -/
theorem claim_4_8 (k : ℕ) (hk : 1 ≤ k) :
(∀ P : Set (Fin k → Bool), P ⊆ Ham k {0, k} → MajImage P = P) ∧
(∀ (S : Finset ℕ) (hne : S.Nonempty), (∀ s ∈ S, s ≤ k) → (S \ {0, k}).Nonempty →
MajImage (Ham k (S : Set ℕ)) =
Ham k {b : ℕ | b ≤ k ∧ 2 * (S.min' hne : ℤ) - k + 1 ≤ b ∧
(b : ℤ) ≤ 2 * (S.max' hne : ℤ) - 1}) := by sorry
end SymBoolPCSP.CFixing
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, p. 19, Claim 4.8 (in the proof of Lemma 4.7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.