Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Composed Kushilevitz functions

Proved
DegreeSensitivity.kushilevitz_composition

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

boolean-functionspolynomial-degreesensitivity

For every k≥0k \ge 0k≥0, some Boolean function on 6k6^k6k bits has degree exactly 3k3^k3k, value 0 at the origin, and sensitivity 6k6^k6k at the origin.

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

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

end DegreeSensitivity
Source
Composition of a fully sensitive base function with itself on disjoint blocks; Nisan and Szegedy (1994) and Hatami, Kulkarni and Pankratov (2011), Example 5.4 ("the Kushilevitz base h and its powering").
Read-back

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

Statement. For every natural number k≥0k \ge 0k≥0 (including k=0k = 0k=0), there exists a Boolean function

f:{0,1}n→{0,1},n=6k,f : \{0,1\}^{n} \to \{0,1\}, \qquad n = 6^k,f:{0,1}n→{0,1},n=6k,

on n=6kn = 6^kn=6k input bits (so a single bit when k=0k = 0k=0), satisfying all three of the following:

  1. deg⁡(f)=3k\deg(f) = 3^kdeg(f)=3k;
  2. f(0)=0f(\mathbf{0}) = 0f(0)=0, where 0=(0,0,…,0)\mathbf{0} = (0,0,\dots,0)0=(0,0,…,0) is the all-false input;
  3. s(f,0)=6ks(f, \mathbf{0}) = 6^ks(f,0)=6k, i.e. the sensitivity of fff at the all-false input equals the number of variables.

The only binder is k∈Nk \in \mathbb{N}k∈N, universally quantified; fff is existentially quantified. There are no other hypotheses or typeclass assumptions. Bits are Booleans, identified with 000 (false) and 111 (true).

Definitions used.

  • Bit flip. For x∈{0,1}nx \in \{0,1\}^nx∈{0,1}n and an index i∈{1,…,n}i \in \{1,\dots,n\}i∈{1,…,n}, x⊕ix^{\oplus i}x⊕i is xxx with the iii-th coordinate negated and all other coordinates unchanged.

  • Pointwise sensitivity. s(f,x)s(f, x)s(f,x) is the number of indices iii with f(x⊕i)≠f(x)f(x^{\oplus i}) \ne f(x)f(x⊕i)=f(x):

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

Combined with condition 2, condition 3 says exactly that f(ei)=1f(e_i) = 1f(ei​)=1 for every one of the 6k6^k6k unit vectors eie_iei​ (the inputs with exactly one bit set). Only the sensitivity at the single point 0\mathbf{0}0 is constrained; the global sensitivity max⁡xs(f,x)\max_x s(f,x)maxx​s(f,x) is not mentioned.

  • Polynomial degree. Say fff has a polynomial representation of degree at most ddd if there exists a polynomial p∈R[X1,…,Xn]p \in \mathbb{R}[X_1,\dots,X_n]p∈R[X1​,…,Xn​] with real coefficients and total degree at most ddd such that, for every x∈{0,1}nx \in \{0,1\}^nx∈{0,1}n, evaluating ppp at the real 0/1 vector xxx gives 111 if f(x)=1f(x) = 1f(x)=1 and 000 if f(x)=0f(x) = 0f(x)=0. Then deg⁡(f)\deg(f)deg(f) is the least d∈Nd \in \mathbb{N}d∈N for which such a representation exists. (This minimum always exists: an explicit Lagrange interpolant of total degree at most nnn is built into the definition, so deg⁡(f)≤n\deg(f) \le ndeg(f)≤n always.) The definition does not require ppp to be multilinear: any real polynomial agreeing with fff on the cube {0,1}n\{0,1\}^n{0,1}n is allowed, and "total degree" is the usual maximum total degree of the monomials of ppp (the zero polynomial has total degree 000). Condition 1 therefore says: some real polynomial of total degree ≤3k\le 3^k≤3k agrees with fff on the cube, and no real polynomial of total degree ≤3k−1\le 3^k - 1≤3k−1 does.

Edge case. For k=0k = 0k=0 the claim is about one variable: there is f:{0,1}→{0,1}f : \{0,1\} \to \{0,1\}f:{0,1}→{0,1} with deg⁡(f)=1\deg(f) = 1deg(f)=1, f(0)=0f(0) = 0f(0)=0 and s(f,0)=1s(f, 0) = 1s(f,0)=1 (equivalently f(1)=1f(1) = 1f(1)=1).

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