has_degree_le
def
A Boolean function f has algebraic degree at most d if it can be represented as a sum of monomials of degree at most d over ZMod 2.
Statement
def has_degree_le {n : ℕ} (f : (Fin n → ZMod 2) → ZMod 2) (d : ℕ) : Prop
- Defined in
- arXiv:2610.32239 Section 2
- Verified
- 26 Oct 2026
- Axioms
- none listed
- Used by 3
- bent_sum_counterexample_not_has_degree_ltFor any m ≥ 4 and any k < m, bent_sum_counterexample_func m hm does not have algebraic degree at most k.
- bent_sum_counterexample_has_degree_leFor any m ≥ 4, the Boolean function bent_sum_counterexample_func m hm has algebraic degree at most m.
- boolean_derivative_has_degree_le_predThe directional derivative of any Boolean function of algebraic degree at most d + 1 along any vector v has algebraic degree at most d.
Read back from the Lean
For a natural number $n$, a function $f : (\mathrm{Fin}\ n \to \mathbb{Z}/2\mathbb{Z}) \to \mathbb{Z}/2\mathbb{Z}$, and a natural number $d$, has_degree_le f d asserts that there exists a finite set $c$ of subsets of $\mathrm{Fin}\ n$ such that:
1. Every subset $S \in c$ has cardinality at most $d$ ($|S| \le d$), and
2. For all $x : \mathrm{Fin}\ n \to \mathbb{Z}/2\mathbb{Z}$, $f(x) = \sum_{S \in c} \prod_{i \in S} x(i)$ in $\mathbb{Z}/2\mathbb{Z}$.
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
/-- A Boolean function has algebraic degree at most d if its algebraic normal form contains only monomials of degree at most d. -/ def has_degree_le {n : ℕ} (f : (Fin n → ZMod 2) → ZMod 2) (d : ℕ) : Prop := ∃ c : Finset (Finset (Fin n)), (∀ S ∈ c, S.card ≤ d) ∧ ∀ x, f x = ∑ S ∈ c, ∏ i ∈ S, x i