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)