AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it