gotsman_linial_with_zero
Provedgotsman_linial_chainsensitivity_theorem
Gotsman–Linial 1992 (corrected applied form, with the boundary case).
Let be monotone with . Suppose that for every and every set of vertices of the -cube with , there exists whose internal degree (number of neighbours of inside ) satisfies
Then for every Boolean function ,
where is the polynomial degree of and is its sensitivity.
This is the corrected form of gotsman_linial: the extra hypothesis rescues the constant-function case ( and ), where the original statement was unprovable because only constrains at . Downstream consumers using supply trivially.
Preamble
import Definitions.Def_Hypercube
import Definitions.Def_BoolFunc
import Definitions.Def_sensitivity
import Definitions.Def_polyDegree
import Mathlib.Data.Real.Basic
/-!
# Gotsman–Linial 1992 (corrected applied form, including `polyDegree = 0`)
The classical equivalence used by Huang 2019 to lift an induced-subgraph
max-degree bound on the hypercube to a sensitivity–degree lower bound on
Boolean functions. We state only the direction actually needed by
Huang's Thm 1.4: *hypercube bound ⇒ sensitivity/degree bound*.
This is the corrected form that supersedes `gotsman_linial`. The original
statement was unprovable for `polyDegree f = 0` (constant Boolean
functions), because `hQ` only constrains `h` on `m > 0`, leaving `h 0`
unconstrained. Concrete counter-example to the un-corrected form:
`h(0) = 1/4`, `h(m) = √m` for `m ≥ 1` is monotone and satisfies `hQ`
(matching Huang's bound), but for `f ≡ false` the conclusion `1/4 ≤ 0`
is false.
The fix is the additional hypothesis `(h0 : h 0 ≤ 0)`. Downstream
consumers (e.g. `sensitivity_sq_ge_polyDegree`) supply this trivially
since they take `h = Real.sqrt`, where `h 0 = 0 ≤ 0`.
-/
/-- **Gotsman–Linial 1992** (direction used in Huang 2019 §1, with
correct boundary case for constant functions).
Let `h : ℕ → ℝ` be monotone with `h 0 ≤ 0`. If every induced
subgraph of `Qₘ` of size `> 2^(m-1)` contains a vertex of internal
degree at least `h m`, then for every Boolean function
`f : {0,1}ⁿ → {0,1}`, the sensitivity `s(f)` is at least `h (deg f)`.
-/Formal statement
theorem gotsman_linial_with_zero
(h : ℕ → ℝ) (hmono : Monotone h) (h0 : h 0 ≤ 0)
(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) :
h (polyDegree f) ≤ (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.)