Amano: no fully sensitive degree-4 function on 10 variables
ProvedDegreeSensitivity.amano_no_fully_sensitive_ten_variables_degree_fourNo Boolean function on 10 bits has degree at most 4 and sensitivity 10.
import Definitions.Def_BoolFunc import Definitions.Def_sensitivity import Definitions.Def_polyDegree
namespace DegreeSensitivity
theorem amano_no_fully_sensitive_ten_variables_degree_four :
¬ ∃ f : BoolFunc 10, polyDegree f ≤ 4 ∧ sensitivity f = 10 := by sorry
end DegreeSensitivity
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Statement. There is no Boolean function (formally, a function from 10-bit vectors with to ) that satisfies both
The theorem takes no parameters or hypotheses; the number of variables is fixed at and the degree bound at .
Degree. Identify a bit with the real number (true) or (false). is the least natural number such that there exists a real polynomial of total degree at most with
The polynomial is an arbitrary multivariate real polynomial (it is not required to be multilinear; agreement is only demanded on the cube). Such a always exists (the Lagrange interpolant gives ), so is a genuine minimum in , and holds exactly when some real polynomial of total degree at most agrees with on all of . Constant functions have degree .
Sensitivity. For and , let denote with only coordinate negated. The pointwise sensitivity is
and , a maximum over the finite cube (so ). Hence means: there exists a point at which flipping any single one of the 10 coordinates changes the value of .
Equivalent reading. For every and every point at which all 10 single-bit flips change , no real polynomial of total degree agrees with on the whole cube. The point is not required to be the origin, and no condition such as , symmetry, or self-duality is imposed on . (Block sensitivity is defined in the bundle but does not appear in this statement.)
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.