booleanDegree
def
The degree of a Boolean function p : (Fin n → ZMod 2) → ZMod 2 is the maximum cardinality of a subset S of coordinates such that the algebraic normal form coefficient c_S is nonzero.
Statement
open scoped BigOperators in noncomputable def booleanDegree {n : ℕ} (p : (Fin n → ZMod 2) → ZMod 2) : ℕ
- Defined in
- arXiv:2611.03452, Section 2.4
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Used by 1
- not_boolean_subspace_degree_reduction_criterionThe statement
boolean_subspace_degree_reduction_criterionis false: The statement is false for d = 0. When d = 0: Let n = 1, p : (Fin 1…
- not_boolean_subspace_degree_reduction_criterionThe statement
Read back from the Lean
Given n : ℕ (implicit) and a Boolean function p : (Fin n → ZMod 2) → ZMod 2, booleanDegree p is defined as the supremum (in ℕ, where the supremum of the empty set is 0) of the cardinalities of all subsets S : Finset (Fin n) such that:
∑ x ∈ {x : Fin n → ZMod 2 | ∀ i, x i ≠ 0 → i ∈ S}, p x ≠ 0
evaluated in ZMod 2 (i.e., the algebraic normal form / Möbius inversion coefficient of the monomial corresponding to S is nonzero in ZMod 2).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
open scoped BigOperators in /-- The F_2-degree of a Boolean function p : (Fin n → ZMod 2) → ZMod 2, defined as the maximum size of a monomial with nonzero coefficient in its algebraic normal form. -/ noncomputable def booleanDegree {n : ℕ} (p : (Fin n → ZMod 2) → ZMod 2) : ℕ := Finset.sup (Finset.univ.filter (fun S : Finset (Fin n) => (∑ x ∈ Finset.univ.filter (fun (x : Fin n → ZMod 2) => ∀ i, x i ≠ 0 → i ∈ S), p x) ≠ 0)) Finset.card