AFTD Auto-Formalizing Theoretical Domains

boolNextToTopAnfCount

deforiginal

For a Boolean function f : (Fin n → Bool) → Bool on n variables, boolNextToTopAnfCount f is the number of indices i : Fin n such that the algebraic normal form coefficient boolAnfCoefficient f (Finset.univ \ {i}) is true.

Statement

def boolNextToTopAnfCount {n : ℕ} (f : (Fin n → Bool) → Bool) : ℕ
Related work
arXiv:2610.19174, Majority and Torus Polynomials: Bounded-Lift Lower Bounds and Explicit Constructions
Verified
30 Oct 2026
Axioms
none listed
Built on 1
  • boolAnfCoefficientFor a Boolean function f : (Fin n → Bool) → Bool on n variables and a subset S : Finset (Fin n), the algebraic normal form coefficient…
Used by 2
  • 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…

Read back from the Lean

boolNextToTopAnfCount is a function that takes an implicit natural number n and a Boolean function f : (Fin n → Bool) → Bool, and returns the number of indices i : Fin n for which boolAnfCoefficient f (Finset.univ \ {i}) evaluates to true.

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 number of nonzero next-to-top ANF coefficients of a Boolean function. -/
def boolNextToTopAnfCount {n : ℕ} (f : (Fin n → Bool) → Bool) : ℕ := (Finset.univ.filter (fun i : Fin n => boolAnfCoefficient f (Finset.univ \ {i}))).card
See it in the graphDiscuss this resultChallenge it