Proskurin's constant:
OpenDegreeSensitivity.proskurin_blockSensitivity_boundFor every Boolean function whose degree is not 1, . Degree-1 functions (literals) are excluded because they violate the inequality.
import Definitions.Def_BoolFunc import Definitions.Def_blockSensitivity import Definitions.Def_polyDegree import Mathlib.Analysis.SpecialFunctions.Pow.Real
namespace DegreeSensitivity
theorem proskurin_blockSensitivity_bound {n : ℕ} (f : BoolFunc n) (hdeg : polyDegree f ≠ 1) :
(Real.sqrt 10 - 2) * (blockSensitivity f : ℝ) ≤ (polyDegree f : ℝ) ^ 2 := by sorry
end DegreeSensitivity
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Let be a natural number (implicit; is allowed). A Boolean function on bits is any map , where is the set of all bit-vectors (true/false values, identified with ). No further restriction is placed on ; constant functions are included.
Polynomial degree . Say has a polynomial representation of degree at most if there is a polynomial with real coefficients (any polynomial, not required to be multilinear) whose total degree is at most and which satisfies, for every ,
where each bit is evaluated as the real number (true) or (false). Then is the least natural number for which such a exists. (Such a always exists, with , via the interpolant \sum_{x : f(x) = 1} \prod_i (\text{X_ix_i = 11 - X_i}); so is a genuine minimum in , and in particular exactly when is constant, the zero polynomial representing the constant- function.)
Block sensitivity . For and a set , let be with every bit whose index lies in flipped (other bits unchanged). is a sensitive block of at if and . The pointwise block sensitivity is the largest cardinality of a family of pairwise disjoint sets, each of which is a sensitive block of at (the empty family is always admissible, so , and the maximum is over a finite set, so it is attained). Then
a natural number (equal to when or is constant).
Hypothesis. The only hypothesis is . Thus and every are allowed; only Boolean functions of degree exactly are excluded.
Conclusion. For every and every Boolean function on bits with , the following inequality holds between real numbers:
where is the positive real square root and ; the inequality is non-strict. Equivalently, .
Degenerate cases. If , or more generally if is constant, then and , so the statement reads and is trivially satisfied; these cases are covered by the hypothesis, since . The hypothesis is satisfiable (e.g. by constant functions) and is never vacuous.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.