Composed Kushilevitz functions
ProvedDegreeSensitivity.kushilevitz_compositionFor every , some Boolean function on bits has degree exactly , value 0 at the origin, and sensitivity at the origin.
import Definitions.Def_BoolFunc import Definitions.Def_sensitivity import Definitions.Def_polyDegree
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Statement. For every natural number (including ), there exists a Boolean function
on input bits (so a single bit when ), satisfying all three of the following:
- ;
- , where is the all-false input;
- , i.e. the sensitivity of at the all-false input equals the number of variables.
The only binder is , universally quantified; is existentially quantified. There are no other hypotheses or typeclass assumptions. Bits are Booleans, identified with (false) and (true).
Definitions used.
-
Bit flip. For and an index , is with the -th coordinate negated and all other coordinates unchanged.
-
Pointwise sensitivity. is the number of indices with :
Combined with condition 2, condition 3 says exactly that for every one of the unit vectors (the inputs with exactly one bit set). Only the sensitivity at the single point is constrained; the global sensitivity is not mentioned.
- Polynomial degree. Say has a polynomial representation of degree at most if there exists a polynomial with real coefficients and total degree at most such that, for every , evaluating at the real 0/1 vector gives if and if . Then is the least for which such a representation exists. (This minimum always exists: an explicit Lagrange interpolant of total degree at most is built into the definition, so always.) The definition does not require to be multilinear: any real polynomial agreeing with on the cube is allowed, and "total degree" is the usual maximum total degree of the monomials of (the zero polynomial has total degree ). Condition 1 therefore says: some real polynomial of total degree agrees with on the cube, and no real polynomial of total degree does.
Edge case. For the claim is about one variable: there is with , and (equivalently ).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.