AFTD Auto-Formalizing Theoretical Domains

explicitApproximant

def

For a Boolean function f : (Fin n → Bool) → Bool and input x : Fin n → Bool, explicitApproximant f x is (if f x then 1 else 0)/2 - (topCoefficient f / 2 : ℤ) * fullMonomial x - (topCoefficient f % 2 : ℤ) * parityCharacter x / 2^(n + 1).

Statement

noncomputable def explicitApproximant {n : ℕ} (f : (Fin n → Bool) → Bool) (x : Fin n → Bool) : ℝ
Defined in
arXiv:2610.19174, Theorem 4.1.1 eq (6) and Listing A.13
Verified
21 Oct 2026
Axioms
none listed
Built on 3
  • topCoefficientFor an implicit natural number n and a Boolean-valued function f : (Fin n → Bool) → Bool, topCoefficient f is the integer defined by the…
  • fullMonomialThe full monomial x_[n] = ∏_{i=1}^n x_i evaluated at a point in {0,1}^n.
  • parityCharacterFor an implicit natural number n and a Boolean assignment x : Fin n → Bool, parityCharacter x is the real number defined by the product…
Used by 3
  • explicitApproximant_mem_degreeSpaceFor any Boolean function f : (Fin n → Bool) → Bool on n > 0 variables, the explicit approximant P_f belongs to degreeSpace (K := ℝ) (Fin…
  • explicitApproximant_torusDistanceFor any Boolean function f : (Fin n → Bool) → Bool on n > 0 variables and any x : Fin n → Bool, torusDistance (explicitApproximant f x -…
  • explicitApproximant_permFor any Boolean function f : (Fin n → Bool) → Bool on n variables, any permutation e : Equiv.Perm (Fin n), if f (x ∘ e) = f x for all x…

Read back from the Lean

For any natural number n, Boolean function f : (Fin n → Bool) → Bool, and input x : Fin n → Bool, explicitApproximant f x is the real number defined by: (if f x then 1/2 else 0) - ((topCoefficient f / 2 : ℤ) : ℝ) * fullMonomial x - ((topCoefficient f % 2 : ℤ) : ℝ) * parityCharacter x / 2^(n + 1) where / and % on topCoefficient f and 2 denote Lean's integer division and modulo on ℤ.

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 approximating polynomial of degree at most n - 1 evaluated at x. -/
noncomputable def explicitApproximant {n : ℕ} (f : (Fin n → Bool) → Bool) (x : Fin n → Bool) : ℝ := (if f x then (1 : ℝ) else 0) / 2 -
  ((topCoefficient f / 2 : ℤ) : ℝ) * fullMonomial x -
  ((topCoefficient f % 2 : ℤ) : ℝ) * parityCharacter x / (2 : ℝ) ^ (n + 1)
See it in the graphDiscuss this resultChallenge it