Kushilevitz's six-variable function
ProvedDegreeSensitivity.kushilevitzSome 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 ).
import Definitions.Def_BoolFunc import Definitions.Def_sensitivity import Definitions.Def_polyDegree
namespace DegreeSensitivity
theorem kushilevitz :
∃ f : BoolFunc 6, polyDegree f = 3 ∧ f (fun _ => false) = false ∧
sensitivityAt f (fun _ => false) = 6 := by sorry
end DegreeSensitivity
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Theorem (kushilevitz). There exists a Boolean function on exactly input bits,
(a function from 6-tuples of Booleans, indexed by , to a Boolean value; true is identified with and false with ), that satisfies all three of the following conditions simultaneously:
- Polynomial degree exactly : . Here is defined as the least natural number such that there is a polynomial (an arbitrary real polynomial in six variables, not required to be multilinear) of total degree at most with
where each bit is evaluated as the real number (true) or (false). The least such always exists, since the Lagrange interpolant gives a representation of total degree at most . So the claim is that some polynomial of total degree agrees with on all points of the cube, and no polynomial of total degree does.
-
Value at the origin: , that is, returns false on the all-false input.
-
Full sensitivity at the origin: , where for an input the pointwise sensitivity is
and is with bit negated and all other bits unchanged. With and , this says for every one of the six unit vectors (the inputs with exactly one bit true).
The statement is a pure existence claim with no hypotheses or parameters: the number of variables (), the degree (, as an equality, not merely an upper bound) and the sensitivity value (, as an equality) are all fixed constants. It concerns only the sensitivity at the single point , not the global sensitivity , and it says nothing about the value of on inputs with two or more true bits beyond what the degree condition imposes.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.