op_729_and3_has_rational_torus_approximation
The 3-variable conjunction function on Fin 3 → Bool has a degree 1 rational torus approximation with error 1/6: HasRationalTorusApproximation (fun x : Fin 3 → Bool => x 0 && x 1 && x 2) 1 (1 / 6).
Statement
theorem op_729_and3_has_rational_torus_approximation : HasRationalTorusApproximation (fun x : Fin 3 → Bool => x 0 && x 1 && x 2) 1 (1 / 6)
- Source
- arXiv:2610.19174
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- HasRationalTorusApproximationFor a Boolean function f : (Fin n → Bool) → Bool on n variables, natural degree d, and error ε : ℝ, HasRationalTorusApproximation f d ε…
- 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 1
- inner_product_c_zero_leftFor any complex-valued function g on the Boolean hypercube {0,1}^n, the inner product of the zero function with g equals 0.
Read back from the Lean
The declaration asserts that the 3-input Boolean AND function, defined by $f(x) = x(0) \land x(1) \land x(2)$ for $x : \mathrm{Fin}\ 3 \to \mathrm{Bool}$, admits a rational torus approximation of degree $1$ with error at most $1/6$. Specifically, there exists a function $P : (\mathrm{Fin}\ 3 \to \mathrm{Bool}) \to \mathbb{Q}$ such that: 1. $P$ belongs to the $\mathbb{Q}$-submodule spanned by monomials of degree at most $1$ (that is, $P$ is an affine linear combination with rational coefficients of the functions $x \mapsto \prod_{i \in S} (\text{if } x(i) \text{ then } 1 \text{ else } 0)$ for subsets $S \subseteq \mathrm{Fin}\ 3$ with $|S| \le 1$); and 2. There exists an integer-valued function $Z : (\mathrm{Fin}\ 3 \to \mathrm{Bool}) \to \mathbb{Z}$ such that for all $x : \mathrm{Fin}\ 3 \to \mathrm{Bool}$, $$|P(x) - Z(x) - \tfrac{1}{2} \cdot \mathrm{bit}(x(0) \land x(1) \land x(2))| \le \frac{1}{6},$$ where $\mathrm{bit}(\mathrm{true}) = 1$ and $\mathrm{bit}(\mathrm{false}) = 0$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To prove that the 3-variable AND function has a degree 1 rational torus approximation with error 1/6, the proof provides explicit witnesses: the affine polynomial P(x) = 13/6 - 7/6 * (x 0 + x 1 + x 2) and an integer rounding function Z(x) taking values in {-2, 0, 1, 2} according to the Hamming weight of x. The polynomial is shown to lie in degreeSpace ℚ (Fin 3) 1 by decomposing it into a linear combination of degree-0 and degree-1 basis monomials. Finally, the error inequality |P(x) - Z(x) - bit(f(x))/2| ≤ 1/6 is verified across all 8 Boolean input vectors by exhaustive case analysis and rational arithmetic.
We choose the rational polynomial P(x) = 13/6 - 7/6 * (x 0 + x 1 + x 2) and the integer-valued function Z(x), reducing the theorem to showing P has degree at most 1 and the approximation bound holds everywhere.
We instantiate the existential quantifiers in the definition of HasRationalTorusApproximation with an explicit affine polynomial P and an integer function Z. Here, Z is defined by nested conditionals that map x to -2 when all three inputs are true, 0 when two are true, 1 when one is true, and 2 when none is true.
classical refine ⟨fun x : Fin 3 → Bool => 13/6 - 7/6 * ((if x 0 = true then (1:ℚ) else 0) + (if x 1 = true then (1:ℚ) else 0) + (if x 2 = true then (1:ℚ) else 0)), ?_, fun x : Fin 3 → Bool => if x 0 then (if x 1 then (if x 2 then (-2:ℤ) else 0) else (if x 2 then 0 else 1)) else (if x 1 then (if x 2 then 0 else 1) else (if x 2 then 1 else 2)), ?_⟩
The constant function x ↦ 1 belongs to degreeSpace ℚ (Fin 3) 1.
By definition, degreeSpace ℚ (Fin 3) 1 is the span of monomial functions indexed by subsets of Fin 3 of cardinality at most 1. The constant function 1 is the empty product, corresponding to the subset ∅ of cardinality 0 ≤ 1, so it belongs to the generating set and therefore to the span.
uses
Submodule.subset_span· have hm0 : (fun _ : Fin 3 → Bool => (1:ℚ)) ∈ degreeSpace ℚ (Fin 3) 1 := by refine Submodule.subset_span ⟨∅, by simp, ?_⟩ funext x; simp
For every coordinate i : Fin 3, the variable indicator function x ↦ (if x i = true then 1 else 0) belongs to degreeSpace ℚ (Fin 3) 1.
Each variable indicator function is the monomial given by the singleton set {i}. Since |{i}| = 1 ≤ 1, it lies in the generating set and thus in its submodule span.
uses
Submodule.subset_spanhave hm : ∀ i : Fin 3, (fun x : Fin 3 → Bool => (if x i = true then (1:ℚ) else 0)) ∈ degreeSpace ℚ (Fin 3) 1 := by intro i refine Submodule.subset_span ⟨{i}, by simp, ?_⟩ funext x; simp
The polynomial P decomposes as the linear combination (13/6) • 1 + (-7/6) • x 0 + (-7/6) • x 1 + (-7/6) • x 2.
Evaluating pointwise on an arbitrary input x, the function addition and scalar multiplication expand to addition and multiplication in ℚ, which ring arithmetic confirms is identical to the definition of P.
uses
Pi.add_apply,Pi.smul_apply,smul_eq_mulhave key : (fun x : Fin 3 → Bool => 13/6 - 7/6 * ((if x 0 = true then (1:ℚ) else 0) + (if x 1 = true then (1:ℚ) else 0) + (if x 2 = true then (1:ℚ) else 0))) = (13/6 : ℚ) • (fun _ : Fin 3 → Bool => (1:ℚ)) + ((-7/6 : ℚ) • (fun x : Fin 3 → Bool => (if x 0 = true then (1:ℚ) else 0)) + ((-7/6 : ℚ) • (fun x : Fin 3 → Bool => (if x 1 = true then (1:ℚ) else 0)) + (-7/6 : ℚ) • (fun x : Fin 3 → Bool => (if x 2 = true then (1:ℚ) else 0)))) := by funext x simp only [Pi.add_apply, Pi.smul_apply, smul_eq_mul] ring
P belongs to degreeSpace ℚ (Fin 3) 1.
Rewriting P via the linear decomposition, membership follows from the fact that submodules are closed under vector addition and scalar multiplication, applied to the constant function and the coordinate indicators.
uses
Submodule.add_mem,Submodule.smul_memrw [key] exact Submodule.add_mem _ (Submodule.smul_mem _ _ hm0) (Submodule.add_mem _ (Submodule.smul_mem _ _ (hm 0)) (Submodule.add_mem _ (Submodule.smul_mem _ _ (hm 1)) (Submodule.smul_mem _ _ (hm 2))))
For all x : Fin 3 → Bool, |P(x) - Z(x) - bit(x 0 && x 1 && x 2)/2| ≤ 1/6. automation
We split into all 2³ = 8 cases for the Boolean values of (x 0, x 1, x 2). In each case, simplifying the definitions of P, Z, and bit leaves a concrete rational inequality, all of which are closed by norm_num.
· intro x cases h0 : x 0 <;> cases h1 : x 1 <;> cases h2 : x 2 <;> simp [h0, h1, h2, bit] <;> norm_num
Pi.add_apply- The sum of two functions evaluated at a point equals the sum of their individual values at that point.
Pi.smul_apply- A scalar multiple of a function evaluated at a point equals the scalar multiplied by the function's value at that point.
smul_eq_mul- Scalar multiplication on an algebra over itself coincides with ring multiplication.
Submodule.add_mem- A submodule is closed under addition: if x and y belong to the submodule, so does x + y.
Submodule.smul_mem- A submodule is closed under scalar multiplication: if x belongs to the submodule and r is a scalar, then r • x belongs to the submodule.
Submodule.subset_span- Every subset of a module is contained in the submodule it spans.
- While a mathematical proof on paper could exploit permutation symmetry to check only the four possible Hamming weights (0, 1, 2, 3), the formal proof checks all 8 truth assignments individually using automated case splitting and arithmetic.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The 3-variable AND function has a degree 1 rational torus approximation with error 1/6. -/theorem op_729_and3_has_rational_torus_approximation : HasRationalTorusApproximation (fun x : Fin 3 → Bool => x 0 && x 1 && x 2) 1 (1 / 6) := by classical refine ⟨fun x : Fin 3 → Bool => 13/6 - 7/6 * ((if x 0 = true then (1:ℚ) else 0) + (if x 1 = true then (1:ℚ) else 0) + (if x 2 = true then (1:ℚ) else 0)), ?_, fun x : Fin 3 → Bool => if x 0 then (if x 1 then (if x 2 then (-2:ℤ) else 0) else (if x 2 then 0 else 1)) else (if x 1 then (if x 2 then 0 else 1) else (if x 2 then 1 else 2)), ?_⟩ · have hm0 : (fun _ : Fin 3 → Bool => (1:ℚ)) ∈ degreeSpace ℚ (Fin 3) 1 := by refine Submodule.subset_span ⟨∅, by simp, ?_⟩ funext x; simp have hm : ∀ i : Fin 3, (fun x : Fin 3 → Bool => (if x i = true then (1:ℚ) else 0)) ∈ degreeSpace ℚ (Fin 3) 1 := by intro i refine Submodule.subset_span ⟨{i}, by simp, ?_⟩ funext x; simp have key : (fun x : Fin 3 → Bool => 13/6 - 7/6 * ((if x 0 = true then (1:ℚ) else 0) + (if x 1 = true then (1:ℚ) else 0) + (if x 2 = true then (1:ℚ) else 0))) = (13/6 : ℚ) • (fun _ : Fin 3 → Bool => (1:ℚ)) + ((-7/6 : ℚ) • (fun x : Fin 3 → Bool => (if x 0 = true then (1:ℚ) else 0)) + ((-7/6 : ℚ) • (fun x : Fin 3 → Bool => (if x 1 = true then (1:ℚ) else 0)) + (-7/6 : ℚ) • (fun x : Fin 3 → Bool => (if x 2 = true then (1:ℚ) else 0)))) := by funext x simp only [Pi.add_apply, Pi.smul_apply, smul_eq_mul] ring rw [key] exact Submodule.add_mem _ (Submodule.smul_mem _ _ hm0) (Submodule.add_mem _ (Submodule.smul_mem _ _ (hm 0)) (Submodule.add_mem _ (Submodule.smul_mem _ _ (hm 1)) (Submodule.smul_mem _ _ (hm 2)))) · intro x cases h0 : x 0 <;> cases h1 : x 1 <;> cases h2 : x 2 <;> simp [h0, h1, h2, bit] <;> norm_num