AFTD Auto-Formalizing Theoretical Domains

acceptingCount

def

The number of accepting inputs |f⁻¹(1)| of a Boolean function f.

Statement

def acceptingCount {n : ℕ} (f : (Fin n → Bool) → Bool) : ℕ
Defined in
arXiv:2610.19174, Section 2.3 and Listing A.13
Verified
21 Oct 2026
Axioms
none listed
Used by 3
  • explicitApproximant_torusDistanceFor any Boolean function f : (Fin n → Bool) → Bool on n > 0 variables and any x : Fin n → Bool, torusDistance (explicitApproximant f x -…
  • explicitErrorThe explicit torus approximation error: 2^{-n-1} if the number of accepting inputs of f is odd, and 0 if even.
  • 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

Given a natural number $n$ and a Boolean function $f : (\text{Fin } n \to \text{Bool}) \to \text{Bool}$, acceptingCount f is defined as the cardinality (number of elements) of the subtype of inputs $x : \text{Fin } n \to \text{Bool}$ such that $f(x) = \text{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 accepting inputs of a Boolean function. -/
def acceptingCount {n : ℕ} (f : (Fin n → Bool) → Bool) : ℕ := Fintype.card {x : Fin n → Bool // f x = true}
See it in the graphDiscuss this resultChallenge it