Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Tal's bound: block sensitivity at most degree squared

Proved
DegreeSensitivity.tal_blockSensitivity_le_polyDegree_sq

by queelius · Nov 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

boolean-functionspolynomial-degreesensitivity

For every Boolean function fff, bs(f)≤deg⁡(f)2bs(f) \le \deg(f)^2bs(f)≤deg(f)2.

Preamble
import Definitions.Def_BoolFunc
import Definitions.Def_blockSensitivity
import Definitions.Def_polyDegree
Formal statement
namespace DegreeSensitivity

theorem tal_blockSensitivity_le_polyDegree_sq {n : ℕ} (f : BoolFunc n) :
    blockSensitivity f ≤ polyDegree f ^ 2 := by sorry

end DegreeSensitivity
Source
A. Tal, Properties and applications of Boolean function composition, ITCS 2013, 441-454, doi:10.1145/2422436.2422485 (improving Nisan and Szegedy 1994 by a factor 2).
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Statement. For every natural number nnn (an implicit parameter, and n=0n = 0n=0 is allowed) and every Boolean function f:{0,1}n→{0,1}f : \{0,1\}^n \to \{0,1\}f:{0,1}n→{0,1} (formally a map from nnn-tuples of Booleans, indexed by {0,…,n−1}\{0, \dots, n-1\}{0,…,n−1}, to a Boolean), the theorem asserts

bs⁡(f)  ≤  deg⁡(f)2,\operatorname{bs}(f) \;\le\; \deg(f)^2 ,bs(f)≤deg(f)2,

an inequality between natural numbers, with no further hypotheses on fff. Both quantities are defined in this bundle as follows.

Block sensitivity bs⁡(f)\operatorname{bs}(f)bs(f). For x∈{0,1}nx \in \{0,1\}^nx∈{0,1}n and a set of coordinates B⊆{0,…,n−1}B \subseteq \{0,\dots,n-1\}B⊆{0,…,n−1}, let xBx^{B}xB be xxx with every bit whose index lies in BBB flipped and all other bits unchanged. A sensitive block of fff at xxx is a nonempty set BBB with f(xB)≠f(x)f(x^{B}) \ne f(x)f(xB)=f(x). The pointwise block sensitivity bs⁡(f,x)\operatorname{bs}(f,x)bs(f,x) is the largest cardinality kkk of a family {B1,…,Bk}\{B_1,\dots,B_k\}{B1​,…,Bk​} of pairwise-disjoint sensitive blocks at xxx. The maximum is taken over the finite collection of all such families (every set of subsets of the nnn coordinates is a candidate), so it is a true maximum. The empty family always qualifies, so bs⁡(f,x)≥0\operatorname{bs}(f,x) \ge 0bs(f,x)≥0, and bs⁡(f,x)=0\operatorname{bs}(f,x) = 0bs(f,x)=0 exactly when xxx has no sensitive block. Then

bs⁡(f)  =  max⁡x∈{0,1}nbs⁡(f,x).\operatorname{bs}(f) \;=\; \max_{x \in \{0,1\}^n} \operatorname{bs}(f,x).bs(f)=x∈{0,1}nmax​bs(f,x).

Polynomial degree deg⁡(f)\deg(f)deg(f). Write ι(x)∈{0,1}n⊂Rn\iota(x) \in \{0,1\}^n \subset \mathbb{R}^nι(x)∈{0,1}n⊂Rn for the point obtained by sending true to 111 and false to 000 in each coordinate. Say that fff has a representation of degree at most ddd if there is a polynomial p∈R[X0,…,Xn−1]p \in \mathbb{R}[X_0,\dots,X_{n-1}]p∈R[X0​,…,Xn−1​] of total degree at most ddd with

p(ι(x))={1if f(x) is true,0otherwisefor every x∈{0,1}n.p(\iota(x)) = \begin{cases} 1 & \text{if } f(x) \text{ is true},\\ 0 & \text{otherwise}\end{cases} \qquad \text{for every } x \in \{0,1\}^n .p(ι(x))={10​if f(x) is true,otherwise​for every x∈{0,1}n.

The code does not require ppp to be multilinear: any real polynomial that agrees with fff on the 2n2^n2n cube points qualifies. Then deg⁡(f)\deg(f)deg(f) is the least natural number ddd for which such a representation exists. A representation always exists with d=nd = nd=n (the bundle proves this with the Lagrange interpolant \sum_{x} f(x)\prod_i (\text{X_iifififx_i=1, else } 1-X_i)), so deg⁡(f)\deg(f)deg(f) is a genuine minimum, satisfies 0≤deg⁡(f)≤n0 \le \deg(f) \le n0≤deg(f)≤n, and has no junk value. By the usual convention for total degree, the zero polynomial has total degree 000.

Edge cases. When n=0n = 0n=0 the cube has a single point, fff is constant, there is no nonempty block, and both sides are 000. For any constant fff (any nnn) no sensitive block exists, so bs⁡(f)=0\operatorname{bs}(f) = 0bs(f)=0, and the constant polynomial 000 or 111 gives deg⁡(f)=0\deg(f) = 0deg(f)=0, so the inequality reads 0≤00 \le 00≤0. The inequality involves no subtraction or division, so there are no truncation effects. The statement is for all fff and nnn, so it is not vacuous.

Human review
  • Endorsed by Shuze Chen · Nov 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by queelius · Nov 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me