polyDegree_distinguishing_units_bound
Provedpolynomial_methodsensitivity_theorem
Polynomial-degree lower bound for unit-distinguishing Boolean functions.
For every Boolean function with that satisfies
where is the standard basis vector with the -th bit set, the polynomial degree obeys
This is the core polynomial-method estimate that converts a sensitivity/degree gap into a block-sensitivity bound (Nisan–Szegedy 1994, Theorem 6). The proof goes through Minsky–Papert symmetrization and a Markov-type derivative bound:
- Take a multivariate real polynomial of total degree representing on the cube.
- Symmetrize over Hamming-weight classes to obtain a univariate of degree with , , and for every integer .
- By the mean-value theorem, some satisfies .
- By Markov's brothers inequality on the integer grid (Ehlich–Zeller / Coppersmith–Rivlin), for every .
- Combine: , hence .
Preamble
import Definitions.Def_BoolFunc
import Definitions.Def_polyDegree
/-!
# Boolean polynomial degree bound for unit-distinguishing functions
Core combinatorial step in the Nisan–Szegedy proof of `bs(f) ≤ 2 · deg(f)²`:
if a Boolean function `g : {0,1}ᵇ → {0,1}` distinguishes the all-zeros input
from each of the `b` standard basis vectors `eᵢ`, then its polynomial degree
is at least `√(b/2)` — equivalently, `b ≤ 2 · deg(g)²`.
The reduction from "block sensitivity" to this lemma is the L1 sketch
(`sketch_tal_block_sensitivity_bound`); the proof of this lemma itself
is the L2 sketch, which decomposes via Minsky–Papert symmetrization and
Markov's brothers inequality.
-/
/-- **Polynomial degree of a unit-distinguishing Boolean function.**
For every `g : {0,1}ᵇ → {0,1}` (with `b ≥ 1`) such that
`g(0) = false` and `g(eᵢ) = true` for every basis vector `eᵢ`,
the polynomial degree satisfies `b ≤ 2 · deg(g)²`. -/Formal statement
theorem polyDegree_distinguishing_units_bound
{b : ℕ} (hb : 1 ≤ b) (g : BoolFunc b)
(h_zero : g (fun _ => false) = false)
(h_units : ∀ i : Fin b, g (Function.update (fun _ => false) i true) = true) :
b ≤ 2 * (polyDegree g)^2 := by sorrySource
Nisan, Noam, and Mario Szegedy. "On the degree of Boolean functions as real polynomials." Computational Complexity 4.4 (1994): 301-313. (Bound used in Huang, Hao. "Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture." Annals of Mathematics 190.3 (2019): 949-955.)