AFTD Auto-Formalizing Theoretical Domains

boolAnfCoefficient

deforiginal

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