Lemma 4.9 (bounded, explicit constant )
ProvedSymBoolPCSP.CFixing.lemma_4_9_bounded_explicitadditive-combinatoricspolymorphismspromise-csp
This is Lemma 4.9 of Brakensiek–Guruswami in the bounded form of the Remark following it, with an explicit constant.
Let , , and let with and , satisfying the bounded sum conditions: for all and ,
- whenever this sum is at most , and
- whenever this sum is at most .
Put
Then:
- if is odd and , then ;
- if is even, then every even with lies in , and every odd with lies in .
The constant depends on only, which is exactly what Lemma 4.9 (unbounded, arbitrary) and its Remark (sets inside ) require; both follow directly from this statement. The explicit value of makes the bounds , quantitative for later use (e.g. the constant in Lemma 4.10).
Formalization Note Tuples are functions Fin n → ℕ and Fin (n-1) → ℕ; the constant is written as if n = 1 then 0 else 1 + (2n-2)(3n-4) with natural-number subtraction, which is exact for .
Preamble
import Mathlib
Formal statement
namespace SymBoolPCSP.CFixing
/-- Bounded form of Lemma 4.9 of Brakensiek–Guruswami, with the explicit constant `c(n) = 0` for `n = 1` and
`c(n) = 1 + (2n-2)(3n-4)` for `n ≥ 2`. -/
theorem lemma_4_9_bounded_explicit (n N : ℕ) (hn : 0 < 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₁) :
(Odd n → (if n = 1 then 0 else 1 + (2 * n - 2) * (3 * n - 4)) ≤ N →
(if n = 1 then 0 else 1 + (2 * n - 2) * (3 * n - 4)) ∈ S₀ ∧
(if n = 1 then 0 else 1 + (2 * n - 2) * (3 * n - 4)) ∈ S₁) ∧
(Even n → ∀ M : ℕ, (if n = 1 then 0 else 1 + (2 * n - 2) * (3 * n - 4)) ≤ M → M ≤ N →
(Even M → M ∈ S₀) ∧ (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, §4, Lemma 4.9 and the Remark after it, pp. 21–22