boolAnfCoefficient
For a Boolean function f : (Fin n → Bool) → Bool on n variables and a subset S : Finset (Fin n), the algebraic normal form coefficient boolAnfCoefficient f S is the Bool value indicating whether the number of inputs x : Fin n → Bool satisfying f x = true and x j = false for all j ∉ S is odd.
Statement
def boolAnfCoefficient {n : ℕ} (f : (Fin n → Bool) → Bool) (S : Finset (Fin n)) : Bool- Related work
- arXiv:2610.19174, Majority and Torus Polynomials: Bounded-Lift Lower Bounds and Explicit Constructions
- Verified
- 30 Oct 2026
- Axioms
- none listed
- Used by 4
- boolNextToTopAnfCountFor a Boolean function f : (Fin n → Bool) → Bool on n variables, boolNextToTopAnfCount f is the number of indices i : Fin n such that the…
- predictedTorusErrorFor a natural number n and Boolean function f : (Fin n → Bool) → Bool on n variables, predictedTorusError n f is the real error: 1 / (2 *…
- op_729_case_n_twoFor every Boolean function f : (Fin 2 → Bool) → Bool on 2 variables, optimalTorusError f 0 = predictedTorusError 2 f and…
- boolAnfCoefficient_univFor any Boolean function f : (Fin n → Bool) → Bool on n variables, boolAnfCoefficient f Finset.univ equals decide (Odd (acceptingCount f)).
Read back from the Lean
A definition boolAnfCoefficient that takes an implicit natural number n : ℕ, a Boolean function f : (Fin n → Bool) → Bool, and a subset S : Finset (Fin n), and returns a Bool. The returned value is true if the number of inputs x : Fin n → Bool such that f x = true and x j = false for all j ∉ S is odd, and false otherwise (i.e., if that count is even).
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
/-- The algebraic normal form coefficient of a Bool-valued Boolean function at subset S. -/ def boolAnfCoefficient {n : ℕ} (f : (Fin n → Bool) → Bool) (S : Finset (Fin n)) : Bool := decide (Odd (Fintype.card { x : Fin n → Bool // f x = true ∧ ∀ j, j ∉ S → x j = false }))