A degree-five function fully sensitive on fourteen variables (open)
OpenDegreeSensitivity.degree_five_full_sensitivitySome Boolean function on 14 bits has degree at most 5, and for all .
import Definitions.Def_BoolFunc import Definitions.Def_sensitivity import Definitions.Def_polyDegree
namespace DegreeSensitivity
theorem degree_five_full_sensitivity :
∃ g : BoolFunc 14, polyDegree g ≤ 5 ∧ g (fun _ => false) = false ∧
∀ i : Fin 14, g (Function.update (fun _ => false) i true) = true := by sorry
end DegreeSensitivity
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Statement (existence claim, no hypotheses). There exists a Boolean function on exactly input bits (indexed by ) satisfying all three of the following conditions:
- ;
- , where is the all-false input;
- for every , , where is the input that is true in coordinate and false in every other coordinate.
The theorem has no binders other than the existentially quantified , and no assumptions.
Meaning of . Identify each input with the real point by sending and coordinatewise, and likewise identify the output with . Say has a polynomial representation of degree at most if there is a polynomial with real coefficients such that
Here is an arbitrary multivariate real polynomial: the definition does not require to be multilinear, and it constrains only at the cube points. The total degree is the largest total degree of a monomial with nonzero coefficient (the zero polynomial has total degree ). Then is defined as the least natural number for which such a representation exists; this minimum is well defined because the bundle proves (via the Lagrange interpolant ) that a representation of degree at most always exists. Consequently, condition 1 is equivalent to: there exists a real polynomial in variables of total degree at most whose values on coincide with (equal to where is false and where is true).
Edge notes. The statement does not mention sensitivity: the bundle's definitions of pointwise sensitivity and of are imported but not used. Conditions 2 and 3 together say directly that changes value under each of the single-bit flips of the all-false input, i.e. for every . Nothing is required of on inputs of Hamming weight beyond the global degree condition. The number of variables is fixed at and the degree bound at ; there is no parameter. In the file the proof is a placeholder (sorry), so the file states the claim and does not establish it.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.