HasRealApproximation
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)| ≤ ε