A Boolean function vanishing at 0 vanishes off its somewhere-increasing coordinates
ProvedSymBoolPCSP.CFixing.eq_false_of_vanish_increasingbooleanpolymorphismspromise-csp
Let with . Call a coordinate somewhere-increasing for if there is with , and , where is the indicator vector of . Let be the set of somewhere-increasing coordinates. Then for every with for all .
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic
Formal statement
open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.CFixing
/-- If `f(0) = 0`, then `f(x) = 0` for every `x` vanishing on the set of coordinates on which
`f` is somewhere-increasing, i.e. the `j` with `f(e_Y) = 0`, `f(e_{Y ∪ {j}}) = 1` for some
`Y ∌ j` (BG, proof of Lemma 4.12, Case 1). -/
theorem eq_false_of_vanish_increasing {L : ℕ} (f : (Fin L → Bool) → Bool)
(h0 : f (fun _ => false) = false) (x : Fin L → Bool)
(hx : ∀ i ∈ Finset.univ.filter (fun j : Fin L => ∃ Y : Finset (Fin L), j ∉ Y ∧
f (indicator Y) = false ∧ f (indicator (insert j Y)) = true), x i = false) :
f x = false := by sorry
end SymBoolPCSP.CFixing
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, proof of Lemma 4.12, Case 1, p. 24