Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proskurin's constant: (10−2) bs(f)≤deg⁡(f)2(\sqrt{10}-2)\,bs(f) \le \deg(f)^2(10​−2)bs(f)≤deg(f)2

Open
DegreeSensitivity.proskurin_blockSensitivity_bound

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

boolean-functionspolynomial-degreesensitivity

For every Boolean function fff whose degree is not 1, (10−2) bs(f)≤deg⁡(f)2(\sqrt{10}-2)\, bs(f) \le \deg(f)^2(10​−2)bs(f)≤deg(f)2. Degree-1 functions (literals) are excluded because they violate the inequality.

Preamble
import Definitions.Def_BoolFunc
import Definitions.Def_blockSensitivity
import Definitions.Def_polyDegree
import Mathlib.Analysis.SpecialFunctions.Pow.Real
Formal statement
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
Source
N. V. Proskurin, On separation between the degree of a Boolean function and the block sensitivity, arXiv:2101.08600 (2021), Theorem 1. The paper states it for all Boolean functions; a single literal (degree 1, block sensitivity 1) is a counterexample, so the hypothesis deg f != 1 is added (it excludes exactly the degree-1 functions).
Read-back

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

Setting. Let n≥0n \ge 0n≥0 be a natural number (implicit; n=0n = 0n=0 is allowed). A Boolean function on nnn bits is any map f:{0,1}n→{0,1}f : \{0,1\}^n \to \{0,1\}f:{0,1}n→{0,1}, where {0,1}n\{0,1\}^n{0,1}n is the set of all 2n2^n2n bit-vectors x=(x1,…,xn)x = (x_1, \dots, x_n)x=(x1​,…,xn​) (true/false values, identified with 1/01/01/0). No further restriction is placed on fff; constant functions are included.

Polynomial degree deg⁡(f)\deg(f)deg(f). Say fff has a polynomial representation of degree at most ddd if there is a polynomial p∈R[X1,…,Xn]p \in \mathbb{R}[X_1, \dots, X_n]p∈R[X1​,…,Xn​] with real coefficients (any polynomial, not required to be multilinear) whose total degree is at most ddd and which satisfies, for every x∈{0,1}nx \in \{0,1\}^nx∈{0,1}n,

p(x1,…,xn)=f(x)∈{0,1}⊂R,p(x_1, \dots, x_n) = f(x) \in \{0, 1\} \subset \mathbb{R},p(x1​,…,xn​)=f(x)∈{0,1}⊂R,

where each bit is evaluated as the real number 111 (true) or 000 (false). Then deg⁡(f)\deg(f)deg(f) is the least natural number ddd for which such a ppp exists. (Such a ddd always exists, with d≤nd \le nd≤n, via the interpolant \sum_{x : f(x) = 1} \prod_i (\text{X_iifififx_i = 1,else, else ,else1 - X_i}); so deg⁡(f)\deg(f)deg(f) is a genuine minimum in {0,1,…,n}\{0, 1, \dots, n\}{0,1,…,n}, and in particular deg⁡(f)=0\deg(f) = 0deg(f)=0 exactly when fff is constant, the zero polynomial representing the constant-000 function.)

Block sensitivity bs⁡(f)\operatorname{bs}(f)bs(f). For x∈{0,1}nx \in \{0,1\}^nx∈{0,1}n and a set B⊆{1,…,n}B \subseteq \{1, \dots, n\}B⊆{1,…,n}, let xBx^{B}xB be xxx with every bit whose index lies in BBB flipped (other bits unchanged). BBB is a sensitive block of fff at xxx if B≠∅B \ne \emptysetB=∅ and 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 sets, each of which is a sensitive block of fff at xxx (the empty family is always admissible, so bs⁡(f,x)≥0\operatorname{bs}(f, x) \ge 0bs(f,x)≥0, and the maximum is over a finite set, so it is attained). 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),

a natural number (equal to 000 when n=0n = 0n=0 or fff is constant).

Hypothesis. The only hypothesis is deg⁡(f)≠1\deg(f) \ne 1deg(f)=1. Thus deg⁡(f)=0\deg(f) = 0deg(f)=0 and every deg⁡(f)≥2\deg(f) \ge 2deg(f)≥2 are allowed; only Boolean functions of degree exactly 111 are excluded.

Conclusion. For every nnn and every Boolean function fff on nnn bits with deg⁡(f)≠1\deg(f) \ne 1deg(f)=1, the following inequality holds between real numbers:

(10−2)⋅bs⁡(f)  ≤  deg⁡(f)2,\bigl(\sqrt{10} - 2\bigr) \cdot \operatorname{bs}(f) \;\le\; \deg(f)^2 ,(10​−2)⋅bs(f)≤deg(f)2,

where 10\sqrt{10}10​ is the positive real square root and 10−2≈1.162\sqrt{10} - 2 \approx 1.16210​−2≈1.162; the inequality is non-strict. Equivalently, bs⁡(f)≤deg⁡(f)2/(10−2)\operatorname{bs}(f) \le \deg(f)^2 / (\sqrt{10} - 2)bs(f)≤deg(f)2/(10​−2).

Degenerate cases. If n=0n = 0n=0, or more generally if fff is constant, then deg⁡(f)=0\deg(f) = 0deg(f)=0 and bs⁡(f)=0\operatorname{bs}(f) = 0bs(f)=0, so the statement reads 0≤00 \le 00≤0 and is trivially satisfied; these cases are covered by the hypothesis, since 0≠10 \ne 10=1. The hypothesis is satisfiable (e.g. by constant functions) and is never 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