bool_func_alternating_sum_sensitivity
Provedgotsman_linial_chainsensitivity_theorem
Alternating sum sensitivity bound (Gotsman–Linial parity step).
Let be monotone, and suppose that for every and every with , there is with . Then for every Boolean function and every non-empty whose Möbius alternating sum
we have
This is the combinatorial half of Gotsman–Linial 1992. Sketch of proof: restrict to the -subcube to obtain a function whose top alternating sum is non-zero. Let and . The non-zero alternating sum gives ; WLOG . Form the parity-aligned majority subset , which has . Apply at to obtain with ; a parity case-analysis on the neighbour shows , which lifts to via the -extension.
Preamble
import Definitions.Def_Hypercube
import Definitions.Def_BoolFunc
import Definitions.Def_sensitivity
import Mathlib.Algebra.BigOperators.Group.Finset.Powerset
import Mathlib.Data.Finset.Powerset
import Mathlib.Data.Real.Basic
/-!
# Alternating-sum ⇒ sensitivity bound (Gotsman–Linial parity step)
If `f : BoolFunc n` has a non-zero Möbius alternating sum on some
`S ⊆ Fin n` with `|S| ≥ 1`, then `sensitivity f` is bounded below by
`h |S|`, given the hypercube max-degree hypothesis `hQ`.
This is the combinatorial half of Gotsman–Linial 1992. The proof
restricts `f` to the `S`-subcube (via `Finset.orderIsoOfFin`) to get
a Boolean function `g : BoolFunc S.card` with non-zero top
alternating sum, then builds the parity-aligned majority subset
`H ⊆ {0,1}^|S|` of size `> 2^(|S|-1)` and applies `hQ`. The
`H`-degree of any `v ∈ H` equals the local sensitivity of `g` at `v`,
which lifts to the local sensitivity of `f` at the `S`-extension of
`v`.
Stating this directly on `f` (instead of on the restricted `g`)
spares downstream consumers the bijection bookkeeping.
-/
/-- **Alternating-sum ⇒ sensitivity bound (parity step of GL 1992).**
If `f : BoolFunc n` has a non-zero Möbius alternating sum on some
non-empty index set `S`, then `h |S| ≤ sensitivity f`. -/Formal statement
theorem bool_func_alternating_sum_sensitivity
(h : ℕ → ℝ) (hmono : Monotone h)
(hQ : ∀ m, 0 < m → ∀ S : Finset (Fin m → Bool),
2 ^ (m - 1) < S.card →
∃ v ∈ S, h m ≤ (Hypercube.degreeIn m S v : ℝ))
{n : ℕ} (f : BoolFunc n) (S : Finset (Fin n))
(h_pos : 1 ≤ S.card)
(h_alt :
(∑ T ∈ S.powerset,
(if (S.card - T.card) % 2 = 0 then (1 : ℝ) else -1) *
(if f (fun i => decide (i ∈ T)) then (1 : ℝ) else 0))
≠ 0) :
h S.card ≤ (sensitivity f : ℝ) := by sorrySource
Gotsman, Chaim, and Nathan Linial. "The equivalence of two problems on the cube." Journal of Combinatorial Theory, Series A 61.1 (1992): 142-146. (Direction used in Huang, Hao. "Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture." Annals of Mathematics 190.3 (2019): 949-955.)