Normal form for degree five and sensitivity fourteen
ProvedDegreeSensitivity.full_sensitivity_normal_formSome Boolean function (on any number of bits) has degree at most 5 and sensitivity at least 14 if and only if some 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 full_sensitivity_normal_form :
(∃ (n : ℕ) (f : BoolFunc n), polyDegree f ≤ 5 ∧ 14 ≤ sensitivity f) ↔
∃ 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
Setting. For (including ), a Boolean function on bits is any map (bits are false/true, identified below with /). For and a coordinate , write for with its -th bit flipped and all other bits unchanged.
- The sensitivity of at is , and the sensitivity of is (a natural number; for it is ).
- has a polynomial representation of degree if there is a real polynomial of total degree such that for every , evaluating at the real 0/1 point corresponding to gives if and if . The polynomial is any real polynomial; the definition does not require it to be multilinear, and it constrains only on the cube points.
- The polynomial degree is the least for which such a representation exists (one always exists with , so this is well defined).
Statement. The theorem asserts the equivalence (both directions)
where is the all-zeros input and is the input with a in coordinate and elsewhere. On the left, is arbitrary (no bound is imposed, though can only hold when ), the sensitivity bound is the non-strict attained at some input, and the degree bound is the non-strict . On the right, the number of variables is exactly , and the conditions say that takes value at the origin and value at each of the neighbours of the origin (so ), together with . There are no other hypotheses or parameters.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.