Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Kushilevitz's six-variable function

Proved
DegreeSensitivity.kushilevitz

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

boolean-functionspolynomial-degreesensitivity

Some Boolean function on 6 bits has degree exactly 3, value 0 at the origin, and sensitivity 6 at the origin (it is fully sensitive at 0\mathbf 00).

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

theorem kushilevitz :
    ∃ f : BoolFunc 6, polyDegree f = 3 ∧ f (fun _ => false) = false ∧
      sensitivityAt f (fun _ => false) = 6 := by sorry

end DegreeSensitivity
Source
E. Kushilevitz, reported in N. Nisan and A. Wigderson, On rank vs. communication complexity, Combinatorica 15 (1995), footnote 1 on p. 560; explicit formula in K. Amano, Bulletin of the EATCS 101 (2010), and in Hatami, Kulkarni and Pankratov, Theory of Computing Graduate Surveys 4 (2011), Example 5.4.
Read-back

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

Theorem (kushilevitz). There exists a Boolean function on exactly 666 input bits,

f:{0,1}6→{0,1}f : \{0,1\}^6 \to \{0,1\}f:{0,1}6→{0,1}

(a function from 6-tuples of Booleans, indexed by i∈{0,…,5}i \in \{0,\dots,5\}i∈{0,…,5}, to a Boolean value; true is identified with 111 and false with 000), that satisfies all three of the following conditions simultaneously:

  1. Polynomial degree exactly 333: deg⁡(f)=3\deg(f) = 3deg(f)=3. Here deg⁡(f)\deg(f)deg(f) is defined as the least natural number ddd such that there is a polynomial p∈R[X0,…,X5]p \in \mathbb{R}[X_0,\dots,X_5]p∈R[X0​,…,X5​] (an arbitrary real polynomial in six variables, not required to be multilinear) of total degree at most ddd with
p(x0,…,x5)=f(x)for every x∈{0,1}6,p(x_0,\dots,x_5) = f(x) \quad \text{for every } x \in \{0,1\}^6,p(x0​,…,x5​)=f(x)for every x∈{0,1}6,

where each bit is evaluated as the real number 111 (true) or 000 (false). The least such ddd always exists, since the Lagrange interpolant gives a representation of total degree at most 666. So the claim is that some polynomial of total degree ≤3\le 3≤3 agrees with fff on all 646464 points of the cube, and no polynomial of total degree ≤2\le 2≤2 does.

  1. Value 000 at the origin: f(0,0,0,0,0,0)=0f(0,0,0,0,0,0) = 0f(0,0,0,0,0,0)=0, that is, fff returns false on the all-false input.

  2. Full sensitivity at the origin: s(f,0)=6s(f, \mathbf{0}) = 6s(f,0)=6, where for an input xxx the pointwise sensitivity is

s(f,x)=#{ i∈{0,…,5}:f(x⊕i)≠f(x) },s(f,x) = \#\{\, i \in \{0,\dots,5\} : f(x^{\oplus i}) \neq f(x) \,\},s(f,x)=#{i∈{0,…,5}:f(x⊕i)=f(x)},

and x⊕ix^{\oplus i}x⊕i is xxx with bit iii negated and all other bits unchanged. With x=0x = \mathbf{0}x=0 and f(0)=0f(\mathbf{0}) = 0f(0)=0, this says f(ei)=1f(e_i) = 1f(ei​)=1 for every one of the six unit vectors e0,…,e5e_0,\dots,e_5e0​,…,e5​ (the inputs with exactly one bit true).

The statement is a pure existence claim with no hypotheses or parameters: the number of variables (666), the degree (333, as an equality, not merely an upper bound) and the sensitivity value (666, as an equality) are all fixed constants. It concerns only the sensitivity at the single point 0\mathbf{0}0, not the global sensitivity max⁡xs(f,x)\max_x s(f,x)maxx​s(f,x), and it says nothing about the value of fff on inputs with two or more true bits beyond what the degree condition imposes.

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