AFTD Auto-Formalizing Theoretical Domains

explicitError

def

The explicit torus approximation error: 2^{-n-1} if the number of accepting inputs of f is odd, and 0 if even.

Statement

noncomputable def explicitError {n : ℕ} (f : (Fin n → Bool) → Bool) : ℝ
Defined in
arXiv:2610.19174, Listing A.13
Verified
21 Oct 2026
Axioms
none listed
Built on 1
  • acceptingCountThe number of accepting inputs |f⁻¹(1)| of a Boolean function f.
Used by 1
  • explicitApproximant_torusDistanceFor any Boolean function f : (Fin n → Bool) → Bool on n > 0 variables and any x : Fin n → Bool, torusDistance (explicitApproximant f x -…

Read back from the Lean

Given a natural number $n$ and a Boolean function $f : (\text{Fin } n \to \text{Bool}) \to \text{Bool}$, explicitError f is the real number equal to $1 / 2^{n+1}$ if the number of inputs $x : \text{Fin } n \to \text{Bool}$ for which $f(x) = \text{true}$ (acceptingCount f) is odd, and $0$ otherwise.

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 explicit error bound 2^{-n-1} when acceptingCount is odd, and 0 when even. -/
noncomputable def explicitError {n : ℕ} (f : (Fin n → Bool) → Bool) : ℝ := if Odd (acceptingCount f) then 1 / (2 : ℝ) ^ (n + 1) else 0
See it in the graphDiscuss this resultChallenge it