Tal's bound: block sensitivity at most degree squared
ProvedDegreeSensitivity.tal_blockSensitivity_le_polyDegree_sqFor every Boolean function , .
import Definitions.Def_BoolFunc import Definitions.Def_blockSensitivity import Definitions.Def_polyDegree
namespace DegreeSensitivity
theorem tal_blockSensitivity_le_polyDegree_sq {n : ℕ} (f : BoolFunc n) :
blockSensitivity f ≤ polyDegree f ^ 2 := by sorry
end DegreeSensitivity
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Statement. For every natural number (an implicit parameter, and is allowed) and every Boolean function (formally a map from -tuples of Booleans, indexed by , to a Boolean), the theorem asserts
an inequality between natural numbers, with no further hypotheses on . Both quantities are defined in this bundle as follows.
Block sensitivity . For and a set of coordinates , let be with every bit whose index lies in flipped and all other bits unchanged. A sensitive block of at is a nonempty set with . The pointwise block sensitivity is the largest cardinality of a family of pairwise-disjoint sensitive blocks at . The maximum is taken over the finite collection of all such families (every set of subsets of the coordinates is a candidate), so it is a true maximum. The empty family always qualifies, so , and exactly when has no sensitive block. Then
Polynomial degree . Write for the point obtained by sending true to and false to in each coordinate. Say that has a representation of degree at most if there is a polynomial of total degree at most with
The code does not require to be multilinear: any real polynomial that agrees with on the cube points qualifies. Then is the least natural number for which such a representation exists. A representation always exists with (the bundle proves this with the Lagrange interpolant \sum_{x} f(x)\prod_i (\text{X_ix_i=1, else } 1-X_i)), so is a genuine minimum, satisfies , and has no junk value. By the usual convention for total degree, the zero polynomial has total degree .
Edge cases. When the cube has a single point, is constant, there is no nonempty block, and both sides are . For any constant (any ) no sensitive block exists, so , and the constant polynomial or gives , so the inequality reads . The inequality involves no subtraction or division, so there are no truncation effects. The statement is for all and , so it is not vacuous.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.