AFTD Auto-Formalizing Theoretical Domains

hasTorusApproximation_of_hasRationalTorusApproximation

theoremverified

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.

  1. 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| ≤ ε.

    line 6

      obtain ⟨P, hP, Z, hZ⟩ := h
  2. Define 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.

    lines 7–10

    uses Algebra.smul_def, Rat.cast_mul

      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] }
  3. 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.

    lines 11–25

    uses LinearMap.coe_mk, AddHom.coe_mk, Finset.prod_congr, Submodule.subset_span

      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⟩
  4. 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.

    lines 26–27

    uses Submodule.span_induction

        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
  5. 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.

    lines 28–32

    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 _
  6. 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.

    lines 33–36

    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
  7. 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`.

    lines 37–43

    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
  8. 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.

    line 44

      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

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

/-- 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⟩
See it in the graphDiscuss this resultChallenge it