hasTorusApproximation_of_hasRationalTorusApproximation
For any Boolean function f on n variables, natural degree d, and error ε, if f has a rational torus approximation of degree d with error ε, then f has a real torus approximation of degree d with error ε.
Statement
theorem hasTorusApproximation_of_hasRationalTorusApproximation {n : ℕ}
(f : (Fin n → Bool) → Bool) (d : ℕ) (ε : ℝ)
(h : HasRationalTorusApproximation f d ε) :
HasTorusApproximation f d ε- Source
- step towards op_729_torus_degree_n_sub_two_exact_anf_spectrum
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- HasRationalTorusApproximationFor a Boolean function f : (Fin n → Bool) → Bool on n variables, natural degree d, and error ε : ℝ, HasRationalTorusApproximation f d ε…
- HasTorusApproximationFor a Boolean function f : (Fin n → Bool) → Bool, natural number d, and real error ε, HasTorusApproximation f d ε asserts the existence of…
- 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.
The proof, explained
A rational torus approximation provides a rational polynomial P of degree at most d and an integer offset Z approximating a Boolean function f within error ε. To obtain a real torus approximation with the same parameters, the proof embeds rational-valued functions into real-valued functions via a ℚ-linear map F and applies submodule span induction over ℚ to show that F(P) belongs to the real degree-d space. The base generators (monomials of degree at most d) map directly to real monomial generators, and linearity preserves zero, sums, and scalar multiples, while the distance bound holds identically.
Obtain the rational polynomial P of degree at most d, the integer offset function Z, and the approximation bound.
By definition of `HasRationalTorusApproximation`, there exist a rational polynomial P in the rational degree-d space, an integer-valued function Z, and a guarantee that for all inputs x, |(P(x) : ℝ) - Z(x) - bit(f(x)) / 2| ≤ ε.
obtain ⟨P, hP, Z, hZ⟩ := hDefine the canonical ℚ-linear embedding F from ℚ-valued functions to ℝ-valued functions.
We define F pointwise by casting rational outputs to real numbers, (F(p))(x) = (p(x) : ℝ). It is verified to be ℚ-linear by checking that it preserves pointwise addition and commutes with rational scalar multiplication.
uses
Algebra.smul_def,Rat.cast_mullet F : ((Fin n → Bool) → ℚ) →ₗ[ℚ] ((Fin n → Bool) → ℝ) := { toFun := fun p x => (p x : ℝ) map_add' := by intro p q; funext x; simp map_smul' := by intro a p; funext x; simp [Algebra.smul_def, Rat.cast_mul] }
Every monomial generator of the rational degree-d space maps under F to an element of the real degree-d space.
The generators of the rational degree-d space are monomials indexed by subsets S with |S| ≤ d. By pushing the real cast through the finite product, F maps each rational monomial to the corresponding real monomial. Since this real monomial is one of the designated generators for the real degree-d space, it belongs to its span.
uses
LinearMap.coe_mk,AddHom.coe_mk,Finset.prod_congr,Submodule.subset_spanhave hmem : (fun x => (P x : ℝ)) ∈ degreeSpace ℝ (Fin n) d := by let p : ((Fin n → Bool) → ℚ) → Prop := fun x => F x ∈ degreeSpace ℝ (Fin n) d have hgen : ∀ x ∈ ({f : (Fin n → Bool) → ℚ | ∃ S : Finset (Fin n), S.card ≤ d ∧ f = fun x => ∏ i ∈ S, if x i = true then 1 else 0} : Set _), p x := by rintro g ⟨S, hS, rfl⟩ have hcast : F (fun x => ∏ i ∈ S, if x i = true then (1:ℚ) else 0) = fun x => ∏ i ∈ S, if x i = true then (1:ℝ) else 0 := by funext x simp only [F, LinearMap.coe_mk, AddHom.coe_mk] push_cast apply Finset.prod_congr rfl intro i hi split <;> simp show F _ ∈ degreeSpace ℝ (Fin n) d rw [hcast] exact Submodule.subset_span ⟨S, hS, rfl⟩
By submodule span induction, the real cast of P lies in the real degree-d space, reducing the claim to the zero, addition, and scalar multiplication cases.
Since P lies in the rational span of the monomial generators, `Submodule.span_induction` reduces proving that F(P) belongs to the real degree-d space to checking the base cases (zero, addition, and rational scalar multiplication). The induction hypothesis then immediately yields the desired membership for P.
uses
Submodule.span_inductionhave h := Submodule.span_induction (R := ℚ) (s := ({f : (Fin n → Bool) → ℚ | ∃ S : Finset (Fin n), S.card ≤ d ∧ f = fun x => ∏ i ∈ S, if x i = true then 1 else 0} : Set _)) (p := fun x _ => p x) hgen ?_ ?_ ?_ hP · simpa [p, F] using h
The induction property holds for zero: F(0) lies in the real degree-d space.
Since F(0) = 0 and every submodule contains 0, F(0) belongs to the real degree-d space.
uses
Submodule.zero_mem· show p 0 change F 0 ∈ degreeSpace ℝ (Fin n) d have h0 : F 0 = 0 := by funext y; simp [F] rw [h0] exact Submodule.zero_mem _
The induction property is preserved under addition: if F(x) and F(y) lie in the real degree-d space, so does F(x + y).
Because F is additive, F(x + y) = F(x) + F(y). Since submodules are closed under addition, F(x + y) belongs to the real degree-d space.
uses
map_add,Submodule.add_mem· intro x y hx hy hpx hpy change F (x + y) ∈ degreeSpace ℝ (Fin n) d rw [map_add] exact Submodule.add_mem _ hpx hpy
The induction property is preserved under rational scalar multiplication, completing the proof that the real cast of P lies in the real degree-d space.
For any rational scalar a, F(a • x) = (a : ℝ) • F(x). Since the real degree-d space is an ℝ-submodule, it is closed under scaling by any real scalar, and in particular by (a : ℝ). This completes the span induction and establishes `hmem`.
uses
Algebra.smul_def,Rat.cast_mul,Submodule.smul_mem· intro a x hx hpx change F (a • x) ∈ degreeSpace ℝ (Fin n) d have : F (a • x) = (a : ℝ) • F x := by funext y simp [F, Algebra.smul_def, Rat.cast_mul] rw [this] exact Submodule.smul_mem _ (a : ℝ) hpx
f has a real torus approximation of degree d and error ε.
We instantiate the existential quantifiers with the real polynomial x ↦ (P(x) : ℝ) and the same integer offset Z. Its degree bound is given by `hmem`, and the error bound is identical to the rational approximation hypothesis.
exact ⟨fun x => (P x : ℝ), hmem, Z, fun x => by simpa using hZ x⟩
Algebra.smul_def- in an algebra, scalar multiplication r • x equals multiplication by the image of r under the algebra map
Rat.cast_mul- the canonical cast from ℚ to ℝ preserves multiplication: ↑(p * q) = ↑p * ↑q
LinearMap.coe_mk- evaluating a linear map constructed via LinearMap.mk applies its underlying function
AddHom.coe_mk- evaluating an additive homomorphism constructed via AddHom.mk applies its underlying function
Finset.prod_congr- two finite products over the same index set are equal if their terms are equal at every element of the index set
Submodule.subset_span- every element of a generating set s is contained in the submodule span of s
Submodule.span_induction- to prove a property holds for all elements of Submodule.span R s, it suffices to prove it for generators in s, 0, and show closure under addition and scalar multiplication
Submodule.zero_mem- the zero element of a module belongs to any submodule
map_add- an additive homomorphism preserves addition: f (x + y) = f x + f y
Submodule.add_mem- a submodule is closed under addition: if x ∈ p and y ∈ p, then x + y ∈ p
Submodule.smul_mem- a submodule is closed under scalar multiplication: if x ∈ p, then r • x ∈ p
- The definition of `HasRationalTorusApproximation` already evaluates the torus approximation inequality in ℝ by casting the value of P(x) to ℝ. Thus, once P is shown to belong to the real degree-d space, the approximation bound and integer offset Z carry over immediately without any arithmetic adjustments.
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.
/-- A rational torus approximation of degree d and error ε induces a real torus approximation with the same parameters. -/theorem hasTorusApproximation_of_hasRationalTorusApproximation {n : ℕ} (f : (Fin n → Bool) → Bool) (d : ℕ) (ε : ℝ) (h : HasRationalTorusApproximation f d ε) : HasTorusApproximation f d ε := by obtain ⟨P, hP, Z, hZ⟩ := h let F : ((Fin n → Bool) → ℚ) →ₗ[ℚ] ((Fin n → Bool) → ℝ) := { toFun := fun p x => (p x : ℝ) map_add' := by intro p q; funext x; simp map_smul' := by intro a p; funext x; simp [Algebra.smul_def, Rat.cast_mul] } have hmem : (fun x => (P x : ℝ)) ∈ degreeSpace ℝ (Fin n) d := by let p : ((Fin n → Bool) → ℚ) → Prop := fun x => F x ∈ degreeSpace ℝ (Fin n) d have hgen : ∀ x ∈ ({f : (Fin n → Bool) → ℚ | ∃ S : Finset (Fin n), S.card ≤ d ∧ f = fun x => ∏ i ∈ S, if x i = true then 1 else 0} : Set _), p x := by rintro g ⟨S, hS, rfl⟩ have hcast : F (fun x => ∏ i ∈ S, if x i = true then (1:ℚ) else 0) = fun x => ∏ i ∈ S, if x i = true then (1:ℝ) else 0 := by funext x simp only [F, LinearMap.coe_mk, AddHom.coe_mk] push_cast apply Finset.prod_congr rfl intro i hi split <;> simp show F _ ∈ degreeSpace ℝ (Fin n) d rw [hcast] exact Submodule.subset_span ⟨S, hS, rfl⟩ have h := Submodule.span_induction (R := ℚ) (s := ({f : (Fin n → Bool) → ℚ | ∃ S : Finset (Fin n), S.card ≤ d ∧ f = fun x => ∏ i ∈ S, if x i = true then 1 else 0} : Set _)) (p := fun x _ => p x) hgen ?_ ?_ ?_ hP · simpa [p, F] using h · show p 0 change F 0 ∈ degreeSpace ℝ (Fin n) d have h0 : F 0 = 0 := by funext y; simp [F] rw [h0] exact Submodule.zero_mem _ · intro x y hx hy hpx hpy change F (x + y) ∈ degreeSpace ℝ (Fin n) d rw [map_add] exact Submodule.add_mem _ hpx hpy · intro a x hx hpx change F (a • x) ∈ degreeSpace ℝ (Fin n) d have : F (a • x) = (a : ℝ) • F x := by funext y simp [F, Algebra.smul_def, Rat.cast_mul] rw [this] exact Submodule.smul_mem _ (a : ℝ) hpx exact ⟨fun x => (P x : ℝ), hmem, Z, fun x => by simpa using hZ x⟩