Lemma 4.9 — two sets closed under the sums (1)–(2) meet, or contain all large evens/odds
ProvedSymBoolPCSP.CFixing.lemma_4_9additive-combinatoricsfrobenius-problemp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1promise-csp
Let be a positive integer. Say that satisfy (1)–(2) if for all and all (not necessarily distinct)
- If is odd, there is such that for every pair satisfying (1)–(2) with and .
- If is even, there is such that for every such pair, contains all even integers and contains all odd integers .
This additive-combinatorics lemma is what forces a polymorphism with many coordinates having to behave like parity (Lemma 4.10).
Formalization Note The constants depend on only, not on , as the notation , and the remark after the lemma state; the quantifiers are ordered accordingly.
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic open PCSPBLPAff.Symmetric
Formal statement
namespace SymBoolPCSP.CFixing
/-- Lemma 4.9 (p. 21). For a positive integer `n`, say that `S₀, S₁ ⊆ ℤ_{≥0}` satisfy (1)–(2) if
for all `a ∈ S₀` and `b₁, …, bₙ ∈ S₁`: (1) `b₁ + ⋯ + bₙ ∈ S₀` and (2) `a + b₁ + ⋯ + b_{n−1} ∈ S₁`.
If `n` is odd there is `A(n)` lying in `S₀ ∩ S₁` for every such pair with `0 ∈ S₀`, `1 ∈ S₁`; if `n`
is even there is `d(n)` such that every such pair has all even integers `≥ d(n)` in `S₀` and all
odd integers `≥ d(n)` in `S₁`. The constants depend on `n` only. -/
theorem lemma_4_9 (n : ℕ) (hn : 0 < n) :
(Odd n → ∃ A : ℕ, ∀ S₀ S₁ : Set ℕ, 0 ∈ S₀ → 1 ∈ S₁ →
(∀ b : Fin n → ℕ, (∀ i, b i ∈ S₁) → ∑ i, b i ∈ S₀) →
(∀ a ∈ S₀, ∀ b : Fin (n - 1) → ℕ, (∀ i, b i ∈ S₁) → a + ∑ i, b i ∈ S₁) →
A ∈ S₀ ∧ A ∈ S₁) ∧
(Even n → ∃ d : ℕ, ∀ S₀ S₁ : Set ℕ, 0 ∈ S₀ → 1 ∈ S₁ →
(∀ b : Fin n → ℕ, (∀ i, b i ∈ S₁) → ∑ i, b i ∈ S₀) →
(∀ a ∈ S₀, ∀ b : Fin (n - 1) → ℕ, (∀ i, b i ∈ S₁) → a + ∑ i, b i ∈ S₁) →
(∀ m : ℕ, d ≤ m → Even m → m ∈ S₀) ∧ (∀ m : ℕ, d ≤ m → Odd m → m ∈ S₁)) := by sorry
end SymBoolPCSP.CFixing
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, p. 21, Lemma 4.9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.