A folded function agreeing with parity on large subsets has Par_L₁ as a minor
ProvedSymBoolPCSP.CFixing.par_minor_of_paritybooleanminorspolymorphismspromise-csp
Let be folded with , let be odd, let and . Suppose that
and that . Then is a minor of : there is a map with
Preamble
import Mathlib import Definitions.Def_PCSPBLPAff_Symmetric_Setting import Definitions.Def_SymBoolPCSP_CFixing_Basic
Formal statement
open PCSPBLPAff.Symmetric
namespace SymBoolPCSP.CFixing
/-- Parity as a minor: let `f : {0,1}^L → {0,1}` be folded with `f(0,…,0) = 0`, let `L₁` be odd, `T ⊆ [L]` and `C ∈ ℕ`. If `f(e_X) = |X| mod 2` for every `X ⊆ T` with `|X| ≥ C`, and `|T| ≥ L₁(C + 1)`, then `Par_{L₁}` is a minor of `f`: there is `π : [L] → [L₁]` with `f(y_{π(1)}, …, y_{π(L)}) = Par_{L₁}(y)` for all `y ∈ {0,1}^{L₁}`. -/
theorem par_minor_of_parity {L L₁ : ℕ} (f : (Fin L → Bool) → Bool) (hfold : IsFolded f)
(h0 : f (fun _ => false) = false) (hL₁ : Odd L₁) (T : Finset (Fin L)) (C : ℕ)
(hpar : ∀ X ⊆ T, C ≤ X.card → f (indicator X) = decide (X.card % 2 = 1))
(hT : L₁ * (C + 1) ≤ T.card) :
∃ π : Fin L → Fin L₁, ∀ y : Fin L₁ → Bool, f (fun i => y (π i)) = Par L₁ y := by sorry
end SymBoolPCSP.CFixing
Source
J. Brakensiek, V. Guruswami, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, arXiv:1704.01937v2, end of the proof of Lemma 4.10, p. 23