Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Normal form for degree five and sensitivity fourteen

Proved
DegreeSensitivity.full_sensitivity_normal_form

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

boolean-functionspolynomial-degreesensitivity

Some Boolean function (on any number of bits) has degree at most 5 and sensitivity at least 14 if and only if some Boolean function ggg on 14 bits has degree at most 5, g(0)=0g(\mathbf 0) = 0g(0)=0 and g(ei)=1g(e_i) = 1g(ei​)=1 for all iii.

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

theorem full_sensitivity_normal_form :
    (∃ (n : ℕ) (f : BoolFunc n), polyDegree f ≤ 5 ∧ 14 ≤ sensitivity f) ↔
      ∃ g : BoolFunc 14, polyDegree g ≤ 5 ∧ g (fun _ => false) = false ∧
        ∀ i : Fin 14, g (Function.update (fun _ => false) i true) = true := by sorry

end DegreeSensitivity
Source
Standard normalization (restriction to sensitive coordinates, translation of the sensitive point to the origin, negation), as in Nisan and Szegedy (1994) and the remark in the Epoch statement; derived reduction, not a numbered theorem of a cited paper.
Read-back

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

Setting. For n∈Nn \in \mathbb{N}n∈N (including n=0n = 0n=0), 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} (bits are false/true, identified below with 000/111). For x∈{0,1}nx \in \{0,1\}^nx∈{0,1}n and a coordinate i∈{1,…,n}i \in \{1,\dots,n\}i∈{1,…,n}, write x⊕ix^{\oplus i}x⊕i for xxx with its iii-th bit flipped and all other bits unchanged.

  • The sensitivity of fff at xxx is s(f,x)=#{ i:f(x⊕i)≠f(x) }s(f,x) = \#\{\, i : f(x^{\oplus i}) \neq f(x) \,\}s(f,x)=#{i:f(x⊕i)=f(x)}, and the sensitivity of fff is s(f)=max⁡x∈{0,1}ns(f,x)s(f) = \max_{x \in \{0,1\}^n} s(f,x)s(f)=maxx∈{0,1}n​s(f,x) (a natural number; for n=0n = 0n=0 it is 000).
  • fff has a polynomial representation of degree ≤d\le d≤d if there is a real polynomial p∈R[X1,…,Xn]p \in \mathbb{R}[X_1,\dots,X_n]p∈R[X1​,…,Xn​] of total degree ≤d\le d≤d such that for every x∈{0,1}nx \in \{0,1\}^nx∈{0,1}n, evaluating ppp at the real 0/1 point corresponding to xxx gives 111 if f(x)=1f(x) = 1f(x)=1 and 000 if f(x)=0f(x) = 0f(x)=0. The polynomial is any real polynomial; the definition does not require it to be multilinear, and it constrains ppp only on the 2n2^n2n cube points.
  • The polynomial degree deg⁡(f)\deg(f)deg(f) is the least d∈Nd \in \mathbb{N}d∈N for which such a representation exists (one always exists with d=nd = nd=n, so this is well defined).

Statement. The theorem asserts the equivalence (both directions)

(∃ n∈N, ∃ f:{0,1}n→{0,1}: deg⁡(f)≤5 and s(f)≥14)  ⟺  (∃ g:{0,1}14→{0,1}: deg⁡(g)≤5, g(0)=0, and g(ei)=1 for all i∈{1,…,14}),\Bigl(\exists\, n \in \mathbb{N},\ \exists\, f : \{0,1\}^n \to \{0,1\} :\ \deg(f) \le 5 \ \text{and}\ s(f) \ge 14\Bigr) \iff \Bigl(\exists\, g : \{0,1\}^{14} \to \{0,1\} :\ \deg(g) \le 5,\ g(\mathbf{0}) = 0,\ \text{and}\ g(e_i) = 1 \text{ for all } i \in \{1,\dots,14\}\Bigr),(∃n∈N, ∃f:{0,1}n→{0,1}: deg(f)≤5 and s(f)≥14)⟺(∃g:{0,1}14→{0,1}: deg(g)≤5, g(0)=0, and g(ei​)=1 for all i∈{1,…,14}),

where 0∈{0,1}14\mathbf{0} \in \{0,1\}^{14}0∈{0,1}14 is the all-zeros input and ei∈{0,1}14e_i \in \{0,1\}^{14}ei​∈{0,1}14 is the input with a 111 in coordinate iii and 000 elsewhere. On the left, nnn is arbitrary (no bound is imposed, though s(f)≥14s(f) \ge 14s(f)≥14 can only hold when n≥14n \ge 14n≥14), the sensitivity bound is the non-strict s(f)≥14s(f) \ge 14s(f)≥14 attained at some input, and the degree bound is the non-strict deg⁡(f)≤5\deg(f) \le 5deg(f)≤5. On the right, the number of variables is exactly 141414, and the conditions say that ggg takes value 000 at the origin and value 111 at each of the 141414 neighbours of the origin (so s(g,0)=14s(g,\mathbf{0}) = 14s(g,0)=14), together with deg⁡(g)≤5\deg(g) \le 5deg(g)≤5. There are no other hypotheses or parameters.

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