AFTD Auto-Formalizing Theoretical Domains

op_729_and3_has_rational_torus_approximation

theoremverified

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.

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

    lines 4–9

      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)), ?_⟩
  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.

    lines 10–12

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

    lines 13–17

    uses Submodule.subset_span

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

    lines 18–27

    uses Pi.add_apply, Pi.smul_apply, smul_eq_mul

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

    lines 28–31

    uses Submodule.add_mem, Submodule.smul_mem

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

    lines 32–34

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

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

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