cube_alt_sum_to_sensitivity_univ
Provedgotsman_linial_chainsensitivity_theorem
Alternating sum on the full -cube sensitivity bound.
Let be monotone, and suppose that for every and every set of vertices of the -cube with , there is with internal degree . Then for every and every Boolean function whose Möbius alternating sum on the full index set is non-zero,
we have
where is the indicator of and is the sensitivity.
This is the core combinatorial lemma of the Gotsman–Linial parity step, with the sub-cube reindexing stripped away. The general case (alt-sum on an arbitrary ) reduces to this via .
Sketch: parity-split the alternating sum as where and . Non-zero gives ; WLOG . Form , which (using ) has . Apply at to get with . A parity case-analysis on the neighbour gives .
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
/-!
# d-cube alternating-sum ⇒ sensitivity bound
Specialised to `Finset.univ : Finset (Fin d)`. If `g : BoolFunc d` has
non-zero top Möbius alternating sum, then `h d ≤ sensitivity g`. This is
the "core" Gotsman–Linial parity step, with the sub-cube bridge stripped
away — the parent theorem `bool_func_alternating_sum_sensitivity`
reduces to this via `Finset.orderEmbOfFin`.
Proof outline (in the sketch):
- Parity-split the alternating sum: it equals `(-1)^d · (A − B)` where
`A := #{z : g z = true ∧ |z| even}`, `B := #{z : g z = true ∧ |z| odd}`.
Hence `A ≠ B`.
- WLOG `A > B`. Define the "parity-aligned" majority set
`H := {z : g z = true ∧ |z| even} ∪ {z : g z = false ∧ |z| odd}`.
Then `|H| = 2^(d-1) + (A − B) > 2^(d-1)`.
- Apply `hQ` at `m = d` to pick `v ∈ H` with `h d ≤ degreeIn d H v`.
- For `v ∈ H`, every neighbour `u` of `v` satisfies `u ∈ H ↔ g u ≠ g v`
(parity flips when one bit is flipped). Hence
`degreeIn d H v = sensitivityAt g v ≤ sensitivity g`.
-/
/-- **d-cube alternating-sum ⇒ sensitivity bound.** If `g : BoolFunc d`
with `d ≥ 1` has a non-zero Möbius alternating sum on
`Finset.univ : Finset (Fin d)`, then `h d ≤ sensitivity g`. -/Formal statement
theorem cube_alt_sum_to_sensitivity_univ
(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 : ℝ))
{d : ℕ} (h_pos : 1 ≤ d) (g : BoolFunc d)
(h_alt :
(∑ T ∈ (Finset.univ : Finset (Fin d)).powerset,
(if (d - T.card) % 2 = 0 then (1 : ℝ) else -1) *
(if g (fun i => decide (i ∈ T)) then (1 : ℝ) else 0))
≠ 0) :
h d ≤ (sensitivity g : ℝ) := 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.)