HasTorusApproximation
For a Boolean function f : (Fin n → Bool) → Bool, natural number d, and real error ε, HasTorusApproximation f d ε asserts the existence of a multilinear polynomial P : (Fin n → Bool) → ℝ in degreeSpace (K := ℝ) (Fin n) d and an integer lift Z : (Fin n → Bool) → ℤ such that |P x - Z x - bit (f x) / 2| ≤ ε for all x : Fin n → Bool.
Statement
def HasTorusApproximation {n : ℕ} (f : (Fin n → Bool) → Bool) (d : ℕ) (ε : ℝ) : Prop
- Defined in
- arXiv:2610.19174, Listing A.1
- Verified
- 21 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 3
- hasTorusApproximation_of_hasRationalTorusApproximationFor any Boolean function f on n variables, natural degree d, and error ε, if f has a rational torus approximation of degree d with error…
- optimalTorusErrorFor a Boolean function f : (Fin n → Bool) → Bool and natural number d, optimalTorusError f d is the real infimum of all errors ε : ℝ such…
- 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
Given a natural number $n$, a Boolean function $f : (\text{Fin } n \to \text{Bool}) \to \text{Bool}$, a degree bound $d \in \mathbb{N}$, and an error bound $\varepsilon \in \mathbb{R}$, HasTorusApproximation f d ε asserts that there exists a real-valued function $P : (\text{Fin } n \to \text{Bool}) \to \mathbb{R}$ such that:
1. $P$ belongs to the $\mathbb{R}$-submodule of functions $(\text{Fin } n \to \text{Bool}) \to \mathbb{R}$ spanned by monomial functions corresponding to subsets of $\text{Fin } n$ of size at most $d$ (that is, $P$ is a multilinear polynomial of degree at most $d$ on the Boolean hypercube); and
2. There exists a function $Z : (\text{Fin } n \to \text{Bool}) \to \mathbb{Z}$ such that for all $x : \text{Fin } n \to \text{Bool}$,
$$\left| P(x) - Z(x) - \frac{\text{bit}(f(x))}{2} \right| \le \varepsilon,$$
where $\text{bit}(b)$ is $1$ if $b = \text{true}$ and $0$ if $b = \text{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
/-- Predicate asserting that f has a torus polynomial approximation of degree at most d with error at most ε. -/ def HasTorusApproximation {n : ℕ} (f : (Fin n → Bool) → Bool) (d : ℕ) (ε : ℝ) : Prop := ∃ P : (Fin n → Bool) → ℝ, P ∈ degreeSpace (K := ℝ) (Fin n) d ∧ ∃ Z : (Fin n → Bool) → ℤ, ∀ x, |P x - (Z x : ℝ) - bit (f x) / 2| ≤ ε