HasRationalTorusApproximation
For a Boolean function f : (Fin n → Bool) → Bool on n variables, natural degree d, and error ε : ℝ, HasRationalTorusApproximation 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 HasRationalTorusApproximation {n : ℕ} (f : (Fin n → Bool) → Bool) (d : ℕ) (ε : ℝ) : Prop
- Related work
- arXiv:2610.19174, Majority and Torus Polynomials: Bounded-Lift Lower Bounds and Explicit Constructions
- Verified
- 30 Oct 2026
- Axioms
- none listed
- Built on 2
- degreeSpaceFor a commutative ring K, a finite type ι with decidable equality, and a natural number d, degreeSpace K ι d is the K-submodule of (ι →…
- bitThe real embedding of a Boolean value, sending false to 0 and true to 1.
- 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…
- op_729_case_n_twoFor every Boolean function f : (Fin 2 → Bool) → Bool on 2 variables, optimalTorusError f 0 = predictedTorusError 2 f and…
- op_729_and3_has_rational_torus_approximationThe 3-variable conjunction function on Fin 3 → Bool has a degree 1 rational torus approximation with error 1/6:…
Read back from the Lean
Given a dimension $n : ℕ$, a Boolean function $f : (\mathrm{Fin}\ n \to \mathrm{Bool}) \to \mathrm{Bool}$, a degree bound $d : ℕ$, and an error parameter $\varepsilon : ℝ$, this defines the proposition that there exists a rational function $P : (\mathrm{Fin}\ n \to \mathrm{Bool}) \to ℚ$ such that:
1. $P$ belongs to degreeSpace (K := ℚ) (Fin n) d, meaning $P$ is in the $ℚ$-submodule spanned by the multilinear monomials of degree at most $d$ (functions of the form $x \mapsto \prod_{i \in S} (\mathrm{if}\ x(i)\ \mathrm{then}\ 1\ \mathrm{else}\ 0)$ for subsets $S \subseteq \mathrm{Fin}\ n$ with $|S| \le d$); and
2. There exists an integer-valued function $Z : (\mathrm{Fin}\ n \to \mathrm{Bool}) \to ℤ$ such that for every input $x : \mathrm{Fin}\ n \to \mathrm{Bool}$,
$$ |(P(x) : ℝ) - (Z(x) : ℝ) - \frac{\mathrm{bit}(f(x))}{2}| \le \varepsilon $$
where $\mathrm{bit}(b)$ is $1$ if $b = \mathrm{true}$ and $0$ if $b = \mathrm{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
/-- Torus approximation by a multilinear polynomial with rational coefficients. -/ def HasRationalTorusApproximation {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| ≤ ε