AFTD Auto-Formalizing Theoretical Domains

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 ε }
See it in the graphDiscuss this resultChallenge it