realApproxDegree
def
For a Boolean function f : (Fin n → Bool) → Bool and real error ε, realApproxDegree f ε is the infimum of all degrees d : ℕ such that HasRealApproximation f d ε holds.
Statement
noncomputable def realApproxDegree {n : ℕ} (f : (Fin n → Bool) → Bool) (ε : ℝ) : ℕ
- Defined in
- arXiv:2610.19174 Definition 3.1, Listing A.1
- Verified
- 23 Oct 2026
- Axioms
- none listed
- Built on 1
- HasRealApproximationFor a Boolean function f : (Fin n → Bool) → Bool, natural number d, and real error ε, HasRealApproximation f d ε asserts the existence of…
- Used by 1
- 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
Given an implicit dimension n : ℕ, a Boolean function f : (Fin n → Bool) → Bool, and an error bound ε : ℝ, realApproxDegree f ε is defined as the infimum in ℕ of the set of all degrees d : ℕ for which f has a real ε-approximation of degree d (HasRealApproximation f d ε). In ℕ, this infimum is the least such degree d, or 0 if no such d exists.
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 real approximate degree of a Boolean function f with error ε. -/ noncomputable def realApproxDegree {n : ℕ} (f : (Fin n → Bool) → Bool) (ε : ℝ) : ℕ := sInf { d : ℕ | HasRealApproximation f d ε }