Sum conditions (1)–(2) make closed under and
ProvedSymBoolPCSP.CFixing.sum_conditions_add_closedadditive-combinatoricspolymorphismspromise-csp
Let and , and let with and . Assume the sum conditions (1)–(2) of Lemma 4.9 of Brakensiek–Guruswami in the bounded form of the Remark following it: for all and ,
- whenever , and
- whenever .
Then both and are closed under adding and under adding , as long as the result is at most : for and ,
These closure properties are the facts (6)–(8) derived in the proof of Lemma 4.9 (for the step is obtained by the same chain). Together with a Frobenius-type closure lemma they give the eventual periodicity of and used in the analysis of polymorphisms avoiding Parity and Alternating-Threshold (Lemma 4.10 ff.).
Formalization Note Tuples are functions Fin n → ℕ. Taking large recovers the unbounded conditions of Lemma 4.9.
Preamble
import Mathlib
Formal statement
namespace SymBoolPCSP.CFixing
/-- The sum conditions (1)–(2) of Lemma 4.9 (bounded by `N`), with `n ≥ 2`, `0 ∈ S₀`,
`1 ∈ S₁`, make both `S₀` and `S₁` closed under adding `2n-2` and adding `3n-4`
(as long as the result is at most `N`). -/
theorem sum_conditions_add_closed (n N : ℕ) (hn : 2 ≤ n) (S₀ S₁ : Set ℕ)
(h0 : 0 ∈ S₀) (h1 : 1 ∈ S₁)
(hs0 : ∀ b : Fin n → ℕ, (∀ i, b i ∈ S₁) → ∑ i, b i ≤ N → ∑ i, b i ∈ S₀)
(hs1 : ∀ a ∈ S₀, ∀ b : Fin (n - 1) → ℕ, (∀ i, b i ∈ S₁) →
a + ∑ i, b i ≤ N → a + ∑ i, b i ∈ S₁) :
(∀ x ∈ S₀, x + (2 * n - 2) ≤ N → x + (2 * n - 2) ∈ S₀) ∧
(∀ x ∈ S₀, x + (3 * n - 4) ≤ N → x + (3 * n - 4) ∈ S₀) ∧
(∀ x ∈ S₁, x + (2 * n - 2) ≤ N → x + (2 * n - 2) ∈ S₁) ∧
(∀ x ∈ S₁, x + (3 * n - 4) ≤ N → x + (3 * n - 4) ∈ 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, proof of Lemma 4.9, facts (3)–(8), pp. 21–22, and the Remark after Lemma 4.9, p. 22