A Boolean function beating the Kushilevitz exponent
OpenDegreeSensitivity.exists_beats_kushilevitzThere exist and a Boolean function on bits with whose sensitivity at the origin exceeds . Equivalently, for some .
import Definitions.Def_BoolFunc import Definitions.Def_sensitivity import Definitions.Def_polyDegree import Mathlib.Analysis.SpecialFunctions.Pow.Real
namespace DegreeSensitivity
theorem exists_beats_kushilevitz :
∃ (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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Statement. There exist a natural number and a Boolean function (formally, any function from -bit vectors , with each , to ; there are no other restrictions on , such as symmetry or self-duality) such that all three of the following hold:
The degree . This is the smallest natural number for which there is a polynomial with total degree at most such that, for every , evaluating at the real point whose -th coordinate is if is true and if is false gives if is true and if is false. The definition does not require to be multilinear: any real polynomial is allowed, and only its values on the cube points are constrained. Such a always exists, with (the Lagrange interpolant is a witness), so is a genuine minimum with no junk value. The condition means , which rules out constant functions and functions that agree on the cube with an affine polynomial.
The sensitivity . Here is the all-false (all-zero) input. is the number of indices for which flipping coordinate of (that is, using the -th standard basis vector ) changes the value: . It is a natural number between and . Only this one point matters. The statement does not involve the global sensitivity , block sensitivity, or any other input.
The inequality. Both sides are read as real numbers. The exponent is the real number (natural logarithms; the ratio is base-independent), and is the real power of a positive integer, so no edge cases arise. The inequality is strict. Since , any witness must satisfy . For example, requires , and requires . The values of and are not specified; the statement asserts only that some pair with these properties exists. The hypothesis is separate, but together with already forces it.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.