Upper half of Maj(Ham_k(S)): weights ≤ 2·max S − 1, and every weight in [ℓ, 2·max S − 1] occurs
ProvedSymBoolPCSP.CFixing.majImage_ham_uppermajoritypolymorphismspromise-csp
Let and , and let be its maximum ( for all ), with . Suppose some has . Write . Then:
- every has Hamming weight ;
- for every with and , we have .
This is the "upper half" of Claim 4.8 of Brakensiek–Guruswami; the lower half follows by negation, replacing by .
Part 1 is double counting: each -column of the output has more than ones, while the total number of ones is at most .
Part 2 is the paper's cyclic-shift construction, with all rows supported as follows:
- if : rows of weight that are cyclic shifts inside the first coordinates;
- if : rows, namely copies of the weight- prefix and cyclic shifts of a weight- set inside the first coordinates.
In both cases the output is the weight- prefix. Symmetry of then moves it to an arbitrary of weight .
Formalization Note iff (Maj L), and is MajImage P. The bound uses natural-number subtraction, which is exact since .
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic
Formal statement
open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.CFixing
/-- Upper half of `Maj(Ham_k(S))`: if `w = max S ≤ k` and `ℓ ∈ S` with `ℓ ≥ 1`, then every tuple in `Maj(Ham_k(S))` has weight at most `2w - 1`, and every weight `b` with `ℓ ≤ b ≤ min(k, 2w - 1)` occurs (`Ham_k({b}) ⊆ Maj(Ham_k(S))`). -/
theorem majImage_ham_upper {k : ℕ} {S : Set ℕ} {l w : ℕ} (hl : l ∈ S) (hl1 : 1 ≤ l)
(hwS : w ∈ S) (hwk : w ≤ k) (hmax : ∀ s ∈ S, s ≤ w) :
(∀ y ∈ MajImage (Ham k S), hw y ≤ 2 * w - 1) ∧
(∀ b : ℕ, l ≤ b → b ≤ k → b ≤ 2 * w - 1 → Ham k {b} ⊆ MajImage (Ham k S)) := by sorry
end SymBoolPCSP.CFixing
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, §4.2, Claim 4.8 and its proof, p. 19