AFTD Auto-Formalizing Theoretical Domains

HasRealApproximation

def

For a Boolean function f : (Fin n → Bool) → Bool, natural number d, and real error ε, HasRealApproximation f d ε asserts the existence of a multilinear polynomial P : (Fin n → Bool) → ℝ in degreeSpace (K := ℝ) (Fin n) d such that |P x - bit (f x)| ≤ ε for all x : Fin n → Bool.

Statement

def HasRealApproximation {n : ℕ} (f : (Fin n → Bool) → Bool) (d : ℕ) (ε : ℝ) : Prop
Defined in
arXiv:2610.19174 Listing A.1
Verified
23 Oct 2026
Axioms
none listed
Built on 2
  • bitThe real embedding of a Boolean value, sending false to 0 and true to 1.
  • degreeSpaceFor a commutative ring K, a finite type ι with decidable equality, and a natural number d, degreeSpace K ι d is the K-submodule of (ι →…
Used by 2
  • realApproxDegreeFor a Boolean function f : (Fin n → Bool) → Bool and real error ε, realApproxDegree f ε is the infimum of all degrees d : ℕ such that…
  • ternary_lift_realApproxDegree_leSuppose n, d : ℕ with 40 ≤ n. If f : (Fin n → Bool) → Bool, P : (Fin n → Bool) → ℝ is in degreeSpace ℝ (Fin n) d, and Z : (Fin n → Bool) →…

Read back from the Lean

For a natural number $n$, a Boolean function $f : (\text{Fin } n \to \text{Bool}) \to \text{Bool}$, a degree bound $d : \mathbb{N}$, and an error bound $\varepsilon : \mathbb{R}$, HasRealApproximation f d ε asserts that there exists a function $P : (\text{Fin } n \to \text{Bool}) \to \mathbb{R}$ such that: 1. $P$ belongs to degreeSpace (K := ℝ) (Fin n) d, and 2. For all inputs $x : \text{Fin } n \to \text{Bool}$, $|P(x) - \text{bit}(f(x))| \le \varepsilon$.

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

/-- Existence of a degree-d real polynomial approximating a Boolean function f within error ε. -/
def HasRealApproximation {n : ℕ} (f : (Fin n → Bool) → Bool) (d : ℕ) (ε : ℝ) : Prop := ∃ P : (Fin n → Bool) → ℝ,
    P ∈ degreeSpace (K := ℝ) (Fin n) d ∧
    ∀ x, |P x - bit (f x)| ≤ ε
See it in the graphDiscuss this resultChallenge it