optimalTorusError
For a Boolean function f : (Fin n → Bool) → Bool and natural number d, optimalTorusError f d is the real infimum of all errors ε : ℝ such that HasTorusApproximation f d ε holds.
Statement
noncomputable def optimalTorusError {n : ℕ} (f : (Fin n → Bool) → Bool) (d : ℕ) : ℝ
- Defined in
- arXiv:2610.19174, Section 2.1 and Listing A.1
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Built on 1
- HasTorusApproximationFor a Boolean function f : (Fin n → Bool) → Bool, natural number d, and real error ε, HasTorusApproximation f d ε asserts the existence of…
- Used by 1
- op_729_case_n_twoFor every Boolean function f : (Fin 2 → Bool) → Bool on 2 variables, optimalTorusError f 0 = predictedTorusError 2 f and…
Read back from the Lean
The definition optimalTorusError takes an implicit dimension n : ℕ, a Boolean function f : (Fin n → Bool) → Bool, and a degree bound d : ℕ. It returns the infimum (sInf) in ℝ of the set of all error bounds ε : ℝ for which f has a degree-d torus approximation with error ε (that is, HasTorusApproximation f d ε).
Here, HasTorusApproximation f d ε asserts that there exists a function P : (Fin n → Bool) → ℝ in degreeSpace (K := ℝ) (Fin n) d (the ℝ-submodule spanned by multilinear monomials on Fin n of degree at most d) and an integer-valued function Z : (Fin n → Bool) → ℤ such that for every input x : Fin n → Bool,
|P x - (Z x : ℝ) - (bit (f x) / 2)| ≤ ε,
where bit b is 1 if b = true and 0 if b = false.
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
/-- Optimal torus approximation error of degree at most d for a Boolean function f. -/ noncomputable def optimalTorusError {n : ℕ} (f : (Fin n → Bool) → Bool) (d : ℕ) : ℝ := sInf { ε : ℝ | HasTorusApproximation f d ε }