AFTD Auto-Formalizing Theoretical Domains

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

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