Degree five on fourteen variables suffices
ProvedDegreeSensitivity.degree_five_full_sensitivity_implies_goalIf some Boolean function on 14 bits has degree at most 5, value 0 at the origin and value 1 at every unit vector, then the goal holds: some on bits has and .
import Definitions.Def_BoolFunc import Definitions.Def_sensitivity import Definitions.Def_polyDegree import Mathlib.Analysis.SpecialFunctions.Pow.Real
namespace DegreeSensitivity
theorem degree_five_full_sensitivity_implies_goal
(h : ∃ g : BoolFunc 14, polyDegree g ≤ 5 ∧ g (fun _ => false) = false ∧
∀ i : Fin 14, g (Function.update (fun _ => false) i true) = true) :
∃ (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
Setting. For , a Boolean function on bits is any map (inputs are -tuples of Booleans indexed by , outputs are Booleans). Write for the all-false input and for the input that is true in coordinate and false elsewhere. Two notions from this bundle are used:
- Polynomial degree : the least for which there is a real polynomial of total degree at most with for every (Booleans read as the reals and ). The polynomial is not required to be multilinear; any real polynomial counts. Such a always exists (the Lagrange interpolant gives ), so is a genuine minimum and satisfies .
- Pointwise sensitivity : the number of coordinates such that flipping bit of changes the value, i.e.
At the origin this is .
Hypothesis. There exists a Boolean function on exactly bits such that
(Equivalently, together with and .) The statement itself does not establish whether such a exists; if none exists, the theorem holds vacuously.
Conclusion. There exist a natural number and a Boolean function on bits such that
where is the natural logarithm (so the exponent is ), the power is the real power of the real number , and the comparison is a strict inequality of real numbers. The conclusion is purely existential: it does not require , does not bound by , does not require or full sensitivity at the origin, and does not require to be the from the hypothesis; it only asks for some function on more than one bit, of polynomial degree at least , whose sensitivity at the all-false input strictly exceeds . Since , no degenerate values of the real power or logarithm arise.
Overall. The theorem asserts: if a -bit Boolean function of polynomial degree at most exists that is at the origin and at every unit vector, then there exist and an -bit Boolean function with and .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.