Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Degree five on fourteen variables suffices

Proved
DegreeSensitivity.degree_five_full_sensitivity_implies_goal

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

boolean-functionspolynomial-degreesensitivity

If some Boolean function on 14 bits has degree at most 5, value 0 at the origin and value 1 at every unit vector, then the goal holds: some fff on n>1n > 1n>1 bits has deg⁡f>1\deg f > 1degf>1 and s(f,0)>deg⁡(f)log⁡6/log⁡3s(f,\mathbf 0) > \deg(f)^{\log 6/\log 3}s(f,0)>deg(f)log6/log3.

Preamble
import Definitions.Def_BoolFunc
import Definitions.Def_sensitivity
import Definitions.Def_polyDegree
import Mathlib.Analysis.SpecialFunctions.Pow.Real
Formal statement
namespace DegreeSensitivity

theorem degree_five_full_sensitivity_implies_goal
    (h : ∃ g : BoolFunc 14, polyDegree g ≤ 5 ∧ g (fun _ => false) = false ∧
      ∀ i : Fin 14, g (Function.update (fun _ => false) i true) = true) :
    ∃ (n : ℕ) (f : BoolFunc n), 1 < n ∧ 1 < polyDegree f ∧
      (polyDegree f : ℝ) ^ (Real.log 6 / Real.log 3) <
        (sensitivityAt f (fun _ => false) : ℝ) := by sorry

end DegreeSensitivity
Source
Derived: degree at most 1 is impossible for such a function, and 5^(log 6/log 3) < 14 (since 6^30 < 3^49 and 5^49 < 14^30).
Read-back

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

Setting. For n∈Nn \in \mathbb{N}n∈N, 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} (inputs are nnn-tuples of Booleans indexed by {0,…,n−1}\{0,\dots,n-1\}{0,…,n−1}, outputs are Booleans). Write 0∈{0,1}n\mathbf{0} \in \{0,1\}^n0∈{0,1}n for the all-false input and eie_iei​ for the input that is true in coordinate iii and false elsewhere. Two notions from this bundle are used:

  • Polynomial degree deg⁡(f)\deg(f)deg(f): the least d∈Nd \in \mathbb{N}d∈N for which there is a real 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)=f(x)p(x) = f(x)p(x)=f(x) for every x∈{0,1}nx \in \{0,1\}^nx∈{0,1}n (Booleans read as the reals 111 and 000). The polynomial is not required to be multilinear; any real polynomial counts. Such a ddd always exists (the Lagrange interpolant gives d=nd = nd=n), so deg⁡(f)\deg(f)deg(f) is a genuine minimum and satisfies 0≤deg⁡(f)≤n0 \le \deg(f) \le n0≤deg(f)≤n.
  • Pointwise sensitivity s(f,x)s(f,x)s(f,x): the number of coordinates iii such that flipping bit iii of xxx changes the value, i.e.
s(f,x)=#{ i∈{0,…,n−1}:f(x⊕ei)≠f(x) }.s(f,x) = \#\{\, i \in \{0,\dots,n-1\} : f(x \oplus e_i) \ne f(x) \,\}.s(f,x)=#{i∈{0,…,n−1}:f(x⊕ei​)=f(x)}.

At the origin this is s(f,0)=#{i:f(ei)≠f(0)}s(f,\mathbf{0}) = \#\{ i : f(e_i) \ne f(\mathbf{0}) \}s(f,0)=#{i:f(ei​)=f(0)}.

Hypothesis. There exists a Boolean function ggg on exactly 141414 bits such that

deg⁡(g)≤5,g(0)=0,g(ei)=1  for all i∈{0,…,13}.\deg(g) \le 5, \qquad g(\mathbf{0}) = 0, \qquad g(e_i) = 1 \ \text{ for all } i \in \{0,\dots,13\}.deg(g)≤5,g(0)=0,g(ei​)=1  for all i∈{0,…,13}.

(Equivalently, deg⁡(g)≤5\deg(g) \le 5deg(g)≤5 together with g(0)=0g(\mathbf{0}) = 0g(0)=0 and s(g,0)=14s(g,\mathbf{0}) = 14s(g,0)=14.) The statement itself does not establish whether such a ggg exists; if none exists, the theorem holds vacuously.

Conclusion. There exist a natural number nnn and a Boolean function fff on nnn bits such that

n>1,deg⁡(f)>1,deg⁡(f) log⁡6/log⁡3  <  s(f,0),n > 1, \qquad \deg(f) > 1, \qquad \deg(f)^{\,\log 6/\log 3} \;<\; s(f,\mathbf{0}),n>1,deg(f)>1,deg(f)log6/log3<s(f,0),

where log⁡\loglog is the natural logarithm (so the exponent is log⁡6/log⁡3≈1.6309\log 6/\log 3 \approx 1.6309log6/log3≈1.6309), the power is the real power of the real number deg⁡(f)\deg(f)deg(f), and the comparison is a strict inequality of real numbers. The conclusion is purely existential: it does not require n=14n = 14n=14, does not bound deg⁡(f)\deg(f)deg(f) by 555, does not require f(0)=0f(\mathbf{0}) = 0f(0)=0 or full sensitivity at the origin, and does not require fff to be the ggg from the hypothesis; it only asks for some function on more than one bit, of polynomial degree at least 222, whose sensitivity at the all-false input strictly exceeds deg⁡(f)log⁡6/log⁡3\deg(f)^{\log 6/\log 3}deg(f)log6/log3. Since deg⁡(f)≥2>0\deg(f) \ge 2 > 0deg(f)≥2>0, no degenerate values of the real power or logarithm arise.

Overall. The theorem asserts: if a 141414-bit Boolean function of polynomial degree at most 555 exists that is 000 at the origin and 111 at every unit vector, then there exist n>1n > 1n>1 and an nnn-bit Boolean function fff with deg⁡(f)>1\deg(f) > 1deg(f)>1 and deg⁡(f)log⁡6/log⁡3<s(f,0)\deg(f)^{\log 6/\log 3} < s(f,\mathbf{0})deg(f)log6/log3<s(f,0).

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