Remark after Lemma 4.9 — the bounded version with the same A(n), d(n)
ProvedSymBoolPCSP.CFixing.remark_4_9additive-combinatoricsfrobenius-problemp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1promise-csp
Let be a positive integer. There are constants ( odd) and ( even) that satisfy Lemma 4.9 and in addition the following bounded version. Let be a positive integer and with , , such that (1) and (2) of Lemma 4.9 hold whenever the sum on the left is at most . Then
- for odd : if , then ;
- for even : if , then every even with lies in and every odd such lies in .
This is the form in which Lemma 4.9 is applied in Lemma 4.10, with the number of coordinates with .
Formalization Note The remark's "independent of " is a typo for . The statement asserts one constant serving both the unbounded lemma and its bounded version for every .
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic open PCSPBLPAff.Symmetric
Formal statement
namespace SymBoolPCSP.CFixing
/-- Remark after Lemma 4.9 (p. 22): the constants `A(n)`, `d(n)` of Lemma 4.9 also serve the
bounded version, in which `S₀, S₁ ⊆ {0, …, N}` and (1)–(2) are only required when the sum is at
most `N`: if `A(n) ≤ N` then `A(n) ∈ S₀ ∩ S₁` (odd `n`), and if `d(n) ≤ N` then every even
`m ∈ [d(n), N]` lies in `S₀` and every odd `m ∈ [d(n), N]` in `S₁` (even `n`). -/
theorem remark_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₁) ∧
(∀ N : ℕ, 0 < N → A ≤ N → ∀ S₀ S₁ : Set ℕ, S₀ ⊆ Set.Iic N → S₁ ⊆ Set.Iic N →
0 ∈ S₀ → 1 ∈ S₁ →
(∀ b : Fin n → ℕ, (∀ i, b i ∈ S₁) → ∑ i, b i ≤ N → ∑ i, b i ∈ S₀) →
(∀ a ∈ S₀, ∀ b : Fin (n - 1) → ℕ, (∀ i, b i ∈ S₁) →
a + ∑ i, b i ≤ N → 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₁)) ∧
(∀ N : ℕ, 0 < N → d ≤ N → ∀ S₀ S₁ : Set ℕ, S₀ ⊆ Set.Iic N → S₁ ⊆ Set.Iic N →
0 ∈ S₀ → 1 ∈ S₁ →
(∀ b : Fin n → ℕ, (∀ i, b i ∈ S₁) → ∑ i, b i ≤ N → ∑ i, b i ∈ S₀) →
(∀ a ∈ S₀, ∀ b : Fin (n - 1) → ℕ, (∀ i, b i ∈ S₁) →
a + ∑ i, b i ≤ N → a + ∑ i, b i ∈ S₁) →
(∀ m : ℕ, d ≤ m → m ≤ N → Even m → m ∈ S₀) ∧
(∀ m : ℕ, d ≤ m → m ≤ N → 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. 22, Remark after Lemma 4.9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.