Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computable analysis · FiniteExponentialProduct · fd889115 k1

Definition
liuyao_ca_fd889115_k1_Analysis_FiniteExponentialProduct

by liuyao · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

ca-fd889115-k1

Private dependency for the Distribution Theory mission. Module ComputableAnalysis/FiniteExponentialProduct.lean from the frozen computable-analysis foundation with kernel-checked rational decision proofs.

Definition code
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_ExpProofs
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_FiniteExponentialTaylor
import Definitions.Def_liuyao_ca_fd889115_k1_Analysis_Series

set_option autoImplicit true

/-!
# Finite products of factorial exponential prefixes

This module develops the rational Cauchy-product algebra needed to identify
the negative exponential series with the reciprocal of the positive series.
It begins with the factorial/binomial coefficient identity and then exposes
the cancellation of every nonconstant diagonal at opposite inputs.
-/

namespace ComputableAnalysis
namespace FiniteExponentialProduct

private theorem rat_eq_of_mul_eq_mul_ne {a b c : Rat}
    (hc : c ≠ 0) (h : c * a = c * b) : a = b := by
  calc
    a = c⁻¹ * (c * a) := by
      have hcancel : c⁻¹ * c = 1 := Rat.inv_mul_cancel c hc
      grind [Rat.mul_assoc]
    _ = c⁻¹ * (c * b) := by rw [h]
    _ = b := by
      have hcancel : c⁻¹ * c = 1 := Rat.inv_mul_cancel c hc
      grind [Rat.mul_assoc]

private theorem expCoeff_shift (n : Nat) :
    (((n + 1 : Nat) : Rat)) * FormalPowerSeries.expCoeff (n + 1) =
      FormalPowerSeries.expCoeff n := by
  have h := congrFun FormalPowerSeries.expCoeff_derivative n
  exact h

/-- The factorial coefficients reproduce the project binomial coefficient.
This proof uses only Pascal recursion and the coefficient-shift identity
`(n+1)/(n+1)! = 1/n!`. -/
theorem expCoeff_mul_expCoeff_eq_expCoeff_mul_combination :
    forall n k : Nat, k <= n ->
      FormalPowerSeries.expCoeff k *
          FormalPowerSeries.expCoeff (n - k) =
        FormalPowerSeries.expCoeff n *
          (FiniteCounting.combination n k : Rat)
  | 0, k, hk => by
      have hk0 : k = 0 := by omega
      subst k
      decide +kernel
  | n + 1, 0, _hk => by
      simp [FormalPowerSeries.expCoeff, factorialRat, factorial,
        FiniteCounting.combination_zero_right]
      grind [Rat.div_def]
  | n + 1, k + 1, hk => by
      have hkn : k <= n := by omega
      by_cases htop : k = n
      · subst k
        simp [FormalPowerSeries.expCoeff, factorialRat, factorial,
          FiniteCounting.combination_rat_self]
        grind [Rat.div_def]
      · have hklt : k < n := by omega
        have hkSucc : k + 1 <= n := by omega
        have ihLeft :=
          expCoeff_mul_expCoeff_eq_expCoeff_mul_combination
            n (k + 1) hkSucc
        have ihRight :=
          expCoeff_mul_expCoeff_eq_expCoeff_mul_combination
            n k hkn
        have hshiftK := expCoeff_shift k
        have hshiftRest := expCoeff_shift (n - (k + 1))
        have hshiftN := expCoeff_shift n
        have hrestSucc : n - (k + 1) + 1 = n - k := by omega
        have hsub : n + 1 - (k + 1) = n - k := by omega
        have hcastSplit :
            ((((n - k : Nat) : Rat)) + (((k + 1 : Nat) : Rat))) =
              ((n + 1 : Nat) : Rat) := by
          exact_mod_cast (by omega : (n - k) + (k + 1) = n + 1)
        rw [FiniteCounting.combination_rat_pascal]
        apply rat_eq_of_mul_eq_mul_ne
          (c := ((n + 1 : Nat) : Rat))
          (by exact_mod_cast Nat.succ_ne_zero n)
        rw [hrestSucc] at hshiftRest
        rw [hsub]
        calc
          ((n + 1 : Nat) : Rat) *
              (FormalPowerSeries.expCoeff (k + 1) *
                FormalPowerSeries.expCoeff (n - k)) =
              ((((n - k : Nat) : Rat)) + (((k + 1 : Nat) : Rat))) *
                (FormalPowerSeries.expCoeff (k + 1) *
                  FormalPowerSeries.expCoeff (n - k)) := by rw [hcastSplit]
          _ = FormalPowerSeries.expCoeff n *
                (FiniteCounting.combination n (k + 1) : Rat) +
              FormalPowerSeries.expCoeff n *
                (FiniteCounting.combination n k : Rat) := by
            rw [← ihLeft, ← ihRight]
            grind [Rat.mul_add, Rat.add_mul,
              Rat.mul_assoc, Rat.mul_comm, Rat.add_assoc, Rat.add_comm]
          _ = ((n + 1 : Nat) : Rat) *
              (FormalPowerSeries.expCoeff (n + 1) *
                ((FiniteCounting.combination n k : Rat) +
                  (FiniteCounting.combination n (k + 1) : Rat))) := by
            grind [Rat.mul_add, Rat.add_mul,
              Rat.mul_assoc, Rat.mul_comm, Rat.add_assoc, Rat.add_comm]

/-- One diagonal term of the product of two factorial exponential prefixes. -/
def diagonalTerm (n k : Nat) (x y : Rat) : Rat :=
  FormalPowerSeries.expCoeff k * x ^ k *
    (FormalPowerSeries.expCoeff (n - k) * y ^ (n - k))

def diagonalSum (n : Nat) (x y : Rat) : Nat -> Rat
  | 0 => 0
  | k + 1 => diagonalSum n x y k + diagonalTerm n k x y

theorem diagonalSum_succ (n k : Nat) (x y : Rat) :
    diagonalSum n x y (k + 1) =
      diagonalSum n x y k + diagonalTerm n k x y := by
  rfl

theorem diagonalTerm_eq_expCoeff_mul_binomialTerm
    (n k : Nat) (hk : k <= n) (x y : Rat) :
    diagonalTerm n k x y =
      FormalPowerSeries.expCoeff n * Series.binomialTerm n k y x := by
  unfold diagonalTerm Series.binomialTerm
  have hcoeff :=
    expCoeff_mul_expCoeff_eq_expCoeff_mul_combination n k hk
  grind [Rat.mul_assoc, Rat.mul_comm]

/-- A complete factorial Cauchy-product diagonal is the factorial coefficient
times the corresponding binomial power. -/
theorem diagonalSum_eq_expCoeff_mul_pow
    (n : Nat) (x y : Rat) :
    diagonalSum n x y (n + 1) =
      FormalPowerSeries.expCoeff n * (x + y) ^ n := by
  have hpartial : forall count : Nat, count <= n + 1 ->
      diagonalSum n x y count =
        FormalPowerSeries.expCoeff n * Series.binomialSum n y x count := by
    intro count hcount
    induction count with
    | zero => simp [diagonalSum, Series.binomialSum]
    | succ count ih =>
        rw [diagonalSum_succ, Series.binomialSum_succ, ih (by omega)]
        rw [diagonalTerm_eq_expCoeff_mul_binomialTerm n count (by omega)]
        grind [Rat.mul_add]
  rw [hpartial (n + 1) (Nat.le_refl _), Series.binomialSum_eq_pow]
  grind [Rat.add_comm]

/-- At opposite inputs every nonconstant factorial Cauchy-product diagonal
vanishes exactly. -/
theorem diagonalSum_opposite_eq_zero
    (n : Nat) (hn : 0 < n) (x : Rat) :
    diagonalSum n x (-x) (n + 1) = 0 := by
  rw [diagonalSum_eq_expCoeff_mul_pow]
  have hzero : x + -x = 0 := Rat.add_neg_cancel x
  rw [hzero]
  rw [Series.rat_zero_pow_of_pos hn]
  simp

theorem diagonalSum_zero_opposite_eq_one (x : Rat) :
    diagonalSum 0 x (-x) 1 = 1 := by
  simp [diagonalSum, diagonalTerm, FormalPowerSeries.expCoeff,
    factorialRat, factorial]
  grind [Rat.div_def]

/-! ## Quantitative outer-diagonal budget -/

/-- The complete absolute-value diagonal at radius `C` is exactly the
factorial-tail term with parameter `2*C`. -/
theorem diagonalSum_nonnegative_eq_factorialTailTerm
    (C : Rat) (n : Nat) :
    diagonalSum n C C (n + 1) =
      RationalMajorant.factorialTailTerm (2 * C) n := by
  rw [diagonalSum_eq_expCoeff_mul_pow]
  unfold FormalPowerSeries.expCoeff
    RationalMajorant.factorialTailTerm
  have hadd : C + C = 2 * C := by grind
  rw [hadd]
  grind [Rat.div_def, Rat.mul_assoc, Rat.mul_comm]

/-- A finite budget for consecutive complete outer Cauchy-product diagonals.
It is definitionally the repository's factorial-tail partial sum at radius
`2*C`. -/
def outerDiagonalBudget (C : Rat) (start terms : Nat) : Rat :=
  RationalMajorant.factorialTailPartial (2 * C) start terms

theorem outerDiagonalBudget_succ
    (C : Rat) (start terms : Nat) :
    outerDiagonalBudget C start (terms + 1) =
      outerDiagonalBudget C start terms +
        diagonalSum (start + terms) C C (start + terms + 1) := by
  unfold outerDiagonalBudget
  rw [RationalMajorant.factorialTailPartial,
    diagonalSum_nonnegative_eq_factorialTailTerm]

theorem outerDiagonalBudget_nonneg
    (C : Rat) (hC : 0 <= C) (start terms : Nat) :
    0 <= outerDiagonalBudget C start terms := by
  unfold outerDiagonalBudget
  induction terms with
  | zero => simp [RationalMajorant.factorialTailPartial]
  | succ terms ih =>
      rw [RationalMajorant.factorialTailPartial]
      have hterm := RationalMajorant.factorialTailTerm_nonneg
        (C := 2 * C) (by grind) (start + terms)
      grind

/-- Once the outer diagonals enter the half-ratio region, every finite block
is bounded by twice its first complete diagonal. -/
theorem outerDiagonalBudget_le_two_first
    (C : Rat) (hC : 0 <= C) (start terms : Nat)
    (hstart : 2 * C <= (((start + 1 : Nat) : Rat) / 2)) :
    outerDiagonalBudget C start terms <=
      2 * RationalMajorant.factorialTailTerm (2 * C) start := by
  unfold outerDiagonalBudget
  exact RationalMajorant.factorialTailPartial_bound
    (C := 2 * C) (by grind) hstart terms

/-- The complete outer-diagonal budget has an executable epsilon schedule. -/
theorem outerDiagonalBudget_scheduled_le_eps
    (C : Rat) (hC : 0 <= C) (eps : QPos) (terms : Nat) :
    outerDiagonalBudget C
      (RationalMajorant.factorialTailStart (2 * C) +
        RationalMajorant.halfDecayShift
          (2 * RationalMajorant.factorialTailTerm (2 * C)
            (RationalMajorant.factorialTailStart (2 * C))) eps)
      terms <= eps.val := by
  unfold outerDiagonalBudget
  exact RationalMajorant.factorialTailPartial_shifted_le_eps
    (C := 2 * C) (by grind) eps terms

/-! ## Literal rectangular prefixes and their outer remainder -/

/-- The exact finite center used by the exponential evaluator, with the number
of included factorial terms made explicit. -/
def factorialPrefix (terms : Nat) (x : Rat) : Rat :=
  ExpProofs.powerSeriesCenterAtTerms x terms

theorem factorialPrefix_zero (x : Rat) : factorialPrefix 0 x = 0 := by
  rfl

theorem factorialPrefix_succ (terms : Nat) (x : Rat) :
    factorialPrefix (terms + 1) x =
      factorialPrefix terms x +
        FormalPowerSeries.expCoeff terms * x ^ terms := by
  unfold factorialPrefix
  rw [ExpProofs.powerSeriesCenterAtTerms_succ,
    ExpProofs.powerSeriesTermAtTerms_eq_expCoeff_monomial]

def factorialMonomial (degree : Nat) (x : Rat) : Rat :=
  FormalPowerSeries.expCoeff degree * x ^ degree

theorem factorialPrefix_succ_monomial (terms : Nat) (x : Rat) :
    factorialPrefix (terms + 1) x =
      factorialPrefix terms x + factorialMonomial terms x := by
  exact factorialPrefix_succ terms x

/-- The difference of two literal evaluator prefixes is the corresponding
finite block of factorial monomials. -/
theorem factorialPrefix_add_sub_eq_remainderPartial
    (x : Rat) (start count : Nat) :
    factorialPrefix (start + count) x - factorialPrefix start x =
      FiniteExponentialTaylor.remainderPartial x start count := by
  induction count with
  | zero =>
      rw [Nat.add_zero, FiniteExponentialTaylor.remainderPartial]
      grind [Rat.sub_eq_add_neg]
  | succ count ih =>
      rw [show start + (count + 1) = (start + count) + 1 by omega,
        factorialPrefix_succ_monomial,
        FiniteExponentialTaylor.remainderPartial, ← ih]
      rw [Rat.sub_eq_add_neg, Rat.sub_eq_add_neg]
      unfold factorialMonomial
      grind [Rat.add_assoc, Rat.add_comm]

theorem factorialMonomial_eq_factorialTailTerm
    (C : Rat) (degree : Nat) :
    factorialMonomial degree C =
      RationalMajorant.factorialTailTerm C degree := by
  unfold factorialMonomial FormalPowerSeries.expCoeff
    RationalMajorant.factorialTailTerm
  grind [Rat.div_def, Rat.mul_assoc, Rat.mul_comm]

/-- At a nonnegative majorant input, the finite exponential remainder block
is definitionally the corresponding factorial-tail partial sum.  The
identity itself does not require the sign hypothesis. -/
theorem remainderPartial_eq_factorialTailPartial
    (C : Rat) (start terms : Nat) :
    FiniteExponentialTaylor.remainderPartial C start terms =
      RationalMajorant.factorialTailPartial C start terms := by
  induction terms with
  | zero => rfl
  | succ terms ih =>
      rw [FiniteExponentialTaylor.remainderPartial,
        RationalMajorant.factorialTailPartial, ih]
      have hterm := factorialMonomial_eq_factorialTailTerm
        C (start + terms)
      unfold factorialMonomial at hterm
      rw [hterm]

theorem factorialPrefix_eq_factorialTailPartial
    (C : Rat) (terms : Nat) :
    factorialPrefix terms C =
      RationalMajorant.factorialTailPartial C 0 terms := by
  have h := factorialPrefix_add_sub_eq_remainderPartial C 0 terms
  rw [Nat.zero_add, factorialPrefix_zero,
    remainderPartial_eq_factorialTailPartial] at h
  grind [Rat.sub_eq_add_neg]

theorem factorialPrefix_mono
    {C : Rat} (hC : 0 <= C) {a b : Nat} (hab : a <= b) :
    factorialPrefix a C <= factorialPrefix b C := by
  rw [factorialPrefix_eq_factorialTailPartial,
    factorialPrefix_eq_factorialTailPartial]
  exact RationalMajorant.factorialTailPartial_mono hC 0 a b hab

theorem factorialPrefix_nonneg
    {C : Rat} (hC : 0 <= C) (terms : Nat) :
    0 <= factorialPrefix terms C := by
  rw [factorialPrefix_eq_factorialTailPartial]
  have hmono := RationalMajorant.factorialTailPartial_mono hC 0 0 terms
    (Nat.zero_le terms)
  simpa [RationalMajorant.factorialTailPartial] using hmono

/-- A finite positive factorial prefix is monotone in its nonnegative rational
input.  This is a finite polynomial fact; no completed exponential or
continuity theorem is used. -/
theorem factorialPrefix_mono_input
    {a b : Rat} (ha : 0 <= a) (hab : a <= b) :
    forall terms : Nat, factorialPrefix terms a <= factorialPrefix terms b
  | 0 => Rat.le_refl
  | terms + 1 => by
      rw [factorialPrefix_succ, factorialPrefix_succ]
      apply rat_add_le_add
      · exact factorialPrefix_mono_input ha hab terms
      · have hb : 0 <= b := Rat.le_trans ha hab
        have hpow : a ^ terms <= b ^ terms := by
          induction terms with
          | zero => simp
          | succ terms ih =>
              rw [Rat.pow_succ, Rat.pow_succ]
              calc
                a ^ terms * a <= b ^ terms * a :=
                  Rat.mul_le_mul_of_nonneg_right ih ha
                _ <= b ^ terms * b :=
                  Rat.mul_le_mul_of_nonneg_left hab (Rat.pow_nonneg hb)
        have hcoeff : 0 <= FormalPowerSeries.expCoeff terms := by
          unfold FormalPowerSeries.expCoeff
          rw [Rat.div_def, Rat.one_mul]
          exact Rat.le_of_lt
            ((Rat.inv_pos).2 (RationalMajorant.factorialRat_pos terms))
        exact Rat.mul_le_mul_of_nonneg_left hpow hcoeff

theorem factorialPrefix_ge_one_add
    {x : Rat} (hx : 0 <= x) (terms : Nat) (hterms : 2 <= terms) :
    1 + x <= factorialPrefix terms x := by
  have hmono := factorialPrefix_mono hx (a := 2) (b := terms) hterms
  have htwo : factorialPrefix 2 x = 1 + x := by
    rw [show 2 = 1 + 1 by omega, factorialPrefix_succ,
      show 1 = 0 + 1 by omega, factorialPrefix_succ,
      factorialPrefix_zero]
    simp [FormalPowerSeries.expCoeff, factorialRat, factorial]
    grind [Rat.div_def]
  rw [htwo] at hmono
  exact hmono

/-- The first `count` rows of the rectangular product with a fixed
`terms`-term second factor. -/
def rectangularRows (terms : Nat) (x y : Rat) : Nat -> Rat
  | 0 => 0
  | count + 1 =>
      rectangularRows terms x y count +
        factorialMonomial count x * factorialPrefix terms y

theorem rectangularRows_succ
    (terms count : Nat) (x y : Rat) :
    rectangularRows terms x y (count + 1) =
      rectangularRows terms x y count +
        factorialMonomial count x * factorialPrefix terms y := by
  rfl

theorem rectangularRows_eq_prefix_mul
    (terms count : Nat) (x y : Rat) :
    rectangularRows terms x y count =
      factorialPrefix count x * factorialPrefix terms y := by
  induction count with
  | zero => simp [rectangularRows, factorialPrefix_zero]
  | succ count ih =>
      rw [rectangularRows_succ, ih,
        factorialPrefix_succ_monomial]
      grind [Rat.add_mul]

/-- The first `count` rows below the total-degree boundary `degree < terms`.
The intended uses keep `count <= terms`; natural subtraction makes the
runtime definition total. -/
def completeTriangleRows (terms : Nat) (x y : Rat) : Nat -> Rat
  | 0 => 0
  | count + 1 =>
      completeTriangleRows terms x y count +
        factorialMonomial count x * factorialPrefix (terms - count) y

theorem completeTriangleRows_succ
    (terms count : Nat) (x y : Rat) :
    completeTriangleRows terms x y (count + 1) =
      completeTriangleRows terms x y count +
        factorialMonomial count x * factorialPrefix (terms - count) y := by
  rfl

private theorem diagonalTerm_eq_monomial_mul_monomial
    (n k : Nat) (x y : Rat) :
    diagonalTerm n k x y =
      factorialMonomial k x * factorialMonomial (n - k) y := by
  unfold diagonalTerm factorialMonomial
  grind [Rat.mul_assoc, Rat.mul_comm]

/-- Increasing the total-degree boundary by one adds exactly one complete
Cauchy-product diagonal, row by row. -/
theorem completeTriangleRows_next
    (terms count : Nat) (hcount : count <= terms + 1) (x y : Rat) :
    completeTriangleRows (terms + 1) x y count =
      completeTriangleRows terms x y count +
        diagonalSum terms x y count := by
  induction count with
  | zero =>
      simp [completeTriangleRows, diagonalSum]
      grind
  | succ count ih =>
      have hcountTerms : count <= terms := by omega
      have hsub : terms + 1 - count = (terms - count) + 1 := by omega
      rw [completeTriangleRows_succ, completeTriangleRows_succ,
        diagonalSum_succ, ih (by omega), hsub,
        factorialPrefix_succ_monomial,
        diagonalTerm_eq_monomial_mul_monomial]
      grind [Rat.mul_add, Rat.add_assoc, Rat.add_comm]

theorem completeTriangleRows_extra_zero
    (terms : Nat) (x y : Rat) :
    completeTriangleRows terms x y (terms + 1) =
      completeTriangleRows terms x y terms := by
  rw [completeTriangleRows_succ]
  simp [factorialPrefix_zero]
  grind

/-- The complete inner triangle of a rectangular prefix. -/
def completeTrianglePrefix (terms : Nat) (x y : Rat) : Rat :=
  completeTriangleRows terms x y terms

/-- The first `count` row tails outside the complete total-degree triangle. -/
def outerRows (terms : Nat) (x y : Rat) : Nat -> Rat
  | 0 => 0
  | count + 1 =>
      outerRows terms x y count +
        factorialMonomial count x *
          (factorialPrefix terms y - factorialPrefix (terms - count) y)

theorem outerRows_succ
    (terms count : Nat) (x y : Rat) :
    outerRows terms x y (count + 1) =
      outerRows terms x y count +
        factorialMonomial count x *
          (factorialPrefix terms y - factorialPrefix (terms - count) y) := by
  rfl

/-- A nonnegative rational majorant for the row tails.  It has exactly the
same finite shape as `outerRows`, with each monomial and tail block replaced
by its factorial majorant. -/
def outerRowsMajorant (terms : Nat) (C : Rat) : Nat -> Rat
  | 0 => 0
  | count + 1 =>
      outerRowsMajorant terms C count +
        RationalMajorant.factorialTailTerm C count *
          RationalMajorant.factorialTailPartial C (terms - count) count

theorem outerRowsMajorant_succ
    (terms count : Nat) (C : Rat) :
    outerRowsMajorant terms C (count + 1) =
      outerRowsMajorant terms C count +
        RationalMajorant.factorialTailTerm C count *
          RationalMajorant.factorialTailPartial C (terms - count) count := by
  rfl

/-- Absolute majorization of every initial collection of rectangular row
tails.  This is the analytic estimate corresponding to the exact row-wise
decomposition. -/
theorem qabs_outerRows_le_majorant
    {C x y : Rat} (hC : 0 <= C) (hx : qabs x <= C)
    (hy : qabs y <= C) (terms count : Nat) (hcount : count <= terms) :
    qabs (outerRows terms x y count) <=
      outerRowsMajorant terms C count := by
  induction count with
  | zero =>
      change qabs 0 <= 0
      decide +kernel
  | succ count ih =>
      have hcountTerms : count <= terms := by omega
      have hsplit : (terms - count) + count = terms := by omega
      have hmon :=
        FinitePolynomial.qabs_expCoeff_monomial_le_factorialTailTerm
          hC hx count
      have htail :=
        FiniteExponentialTaylor.remainderPartial_abs_le_factorialTailPartial
          hC hy (terms - count) count
      have htailEq :
          factorialPrefix terms y - factorialPrefix (terms - count) y =
            FiniteExponentialTaylor.remainderPartial y
              (terms - count) count := by
        calc
          factorialPrefix terms y - factorialPrefix (terms - count) y =
              factorialPrefix ((terms - count) + count) y -
                factorialPrefix (terms - count) y := by rw [hsplit]
          _ = FiniteExponentialTaylor.remainderPartial y
                (terms - count) count :=
            factorialPrefix_add_sub_eq_remainderPartial _ _ _
      have hmul :
          qabs
              (factorialMonomial count x *
                (factorialPrefix terms y -
                  factorialPrefix (terms - count) y)) <=
            RationalMajorant.factorialTailTerm C count *
              RationalMajorant.factorialTailPartial C
                (terms - count) count := by
        rw [qabs_mul, htailEq]
        exact Rat.le_trans
          (Rat.mul_le_mul_of_nonneg_right hmon
            (qabs_nonneg
              (FiniteExponentialTaylor.remainderPartial y
                (terms - count) count)))
          (Rat.mul_le_mul_of_nonneg_left htail
            (RationalMajorant.factorialTailTerm_nonneg hC count))
      rw [outerRows_succ, outerRowsMajorant_succ]
      exact Rat.le_trans
        (qabs_add_le _ _)
        (rat_add_le_add (ih (by omega)) hmul)

/-- At the nonnegative radius itself, the analytic majorant is exactly the
corresponding rectangular row-tail sum. -/
theorem outerRowsMajorant_eq_outerRows_self
    (C : Rat) (terms count : Nat) (hcount : count <= terms) :
    outerRowsMajorant terms C count = outerRows terms C C count := by
  induction count with
  | zero => rfl
  | succ count ih =>
      have hcountTerms : count <= terms := by omega
      have hsplit : (terms - count) + count = terms := by omega
      have htail :
          factorialPrefix terms C - factorialPrefix (terms - count) C =
            RationalMajorant.factorialTailPartial C
              (terms - count) count := by
        calc
          factorialPrefix terms C - factorialPrefix (terms - count) C =
              factorialPrefix ((terms - count) + count) C -
                factorialPrefix (terms - count) C := by rw [hsplit]
          _ = FiniteExponentialTaylor.remainderPartial C
                (terms - count) count :=
            factorialPrefix_add_sub_eq_remainderPartial _ _ _
          _ = RationalMajorant.factorialTailPartial C
                (terms - count) count :=
            remainderPartial_eq_factorialTailPartial _ _ _
      rw [outerRowsMajorant_succ, outerRows_succ,
        ih (by omega), ← htail,
        ← factorialMonomial_eq_factorialTailTerm]

theorem rectangularRows_eq_triangle_add_outer
    (terms count : Nat) (hcount : count <= terms) (x y : Rat) :
    rectangularRows terms x y count =
      completeTriangleRows terms x y count +
        outerRows terms x y count := by
  induction count with
  | zero =>
      simp [rectangularRows, completeTriangleRows, outerRows]
      grind
  | succ count ih =>
      rw [rectangularRows_succ, completeTriangleRows_succ,
        outerRows_succ, ih (by omega)]
      grind [Rat.mul_add, Rat.add_assoc, Rat.add_comm,
        Rat.sub_eq_add_neg]

theorem completeTriangleRows_mono_count
    {C : Rat} (hC : 0 <= C) (terms : Nat) :
    forall a b : Nat, a <= b ->
      completeTriangleRows terms C C a <=
        completeTriangleRows terms C C b
  | a, 0, hab => by
      have ha : a = 0 := by omega
      subst a
      exact Rat.le_refl
  | a, b + 1, hab => by
      by_cases ha : a = b + 1
      · subst a
        exact Rat.le_refl
      · have hab' : a <= b := by omega
        have ih := completeTriangleRows_mono_count hC terms a b hab'
        rw [completeTriangleRows_succ]
        have hmon : 0 <= factorialMonomial b C := by
          rw [factorialMonomial_eq_factorialTailTerm]
          exact RationalMajorant.factorialTailTerm_nonneg hC b
        have hp := factorialPrefix_nonneg hC (terms - b)
        have hproduct :
            0 <= factorialMonomial b C *
              factorialPrefix (terms - b) C :=
          Rat.mul_nonneg hmon hp
        grind

/-- Every row of an `N` by `N` factorial rectangle lies inside the complete
total-degree triangle with boundary `2*N`. -/
theorem rectangularRows_le_doubleTriangle
    {C : Rat} (hC : 0 <= C) (terms count : Nat)
    (hcount : count <= terms) :
    rectangularRows terms C C count <=
      completeTriangleRows (terms + terms) C C count := by
  induction count with
  | zero =>
      exact Rat.le_refl
  | succ count ih =>
      have hcountTerms : count <= terms := by omega
      have hprefixIndex :
          terms <= terms + terms - count := by omega
      have hp := factorialPrefix_mono hC hprefixIndex
      have hmon : 0 <= factorialMonomial count C := by
        rw [factorialMonomial_eq_factorialTailTerm]
        exact RationalMajorant.factorialTailTerm_nonneg hC count
      have hrow := Rat.mul_le_mul_of_nonneg_left hp hmon
      rw [rectangularRows_succ, completeTriangleRows_succ]
      exact rat_add_le_add (ih (by omega)) hrow

/-- Sum of the complete Cauchy-product diagonals strictly below `terms`. -/
def completeDiagonalPrefix : Nat -> Rat -> Rat -> Rat
  | 0, _x, _y => 0
  | terms + 1, x, y =>
      completeDiagonalPrefix terms x y +
        diagonalSum terms x y (terms + 1)

theorem completeDiagonalPrefix_zero (x y : Rat) :
    completeDiagonalPrefix 0 x y = 0 := by
  rfl

theorem completeDiagonalPrefix_succ (terms : Nat) (x y : Rat) :
    completeDiagonalPrefix (terms + 1) x y =
      completeDiagonalPrefix terms x y +
        diagonalSum terms x y (terms + 1) := by
  rfl

/-- Accumulating any positive number of complete diagonals at opposite inputs
gives exactly the constant diagonal `1`. -/
theorem completeDiagonalPrefix_opposite_eq_one
    (terms : Nat) (hterms : 0 < terms) (x : Rat) :
    completeDiagonalPrefix terms x (-x) = 1 := by
  obtain ⟨k, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (Nat.ne_of_gt hterms)
  induction k with
  | zero =>
      rw [completeDiagonalPrefix_succ, completeDiagonalPrefix_zero,
        diagonalSum_zero_opposite_eq_one]
      grind
  | succ k ih =>
      rw [completeDiagonalPrefix_succ,
        diagonalSum_opposite_eq_zero (k + 1) (Nat.succ_pos k),
        ih (Nat.succ_pos k)]
      grind

/-- The row-wise total-degree triangle is exactly the accumulated complete
diagonal prefix. -/
theorem completeTrianglePrefix_eq_completeDiagonalPrefix
    (terms : Nat) (x y : Rat) :
    completeTrianglePrefix terms x y =
      completeDiagonalPrefix terms x y := by
  induction terms with
  | zero => simp [completeTrianglePrefix, completeTriangleRows,
      completeDiagonalPrefix]
  | succ terms ih =>
      unfold completeTrianglePrefix
      rw [completeTriangleRows_next terms (terms + 1)
          (Nat.le_refl _) x y,
        completeTriangleRows_extra_zero]
      change completeTrianglePrefix terms x y +
          diagonalSum terms x y (terms + 1) =
        completeDiagonalPrefix (terms + 1) x y
      rw [ih, completeDiagonalPrefix_succ]

/-- Appending complete nonnegative diagonals is exactly the previously
scheduled outer-diagonal factorial budget. -/
theorem completeDiagonalPrefix_add_outerDiagonalBudget
    (C : Rat) (start count : Nat) :
    completeDiagonalPrefix (start + count) C C =
      completeDiagonalPrefix start C C +
        outerDiagonalBudget C start count := by
  induction count with
  | zero =>
      rw [Nat.add_zero]
      simp [outerDiagonalBudget,
        RationalMajorant.factorialTailPartial]
      grind
  | succ count ih =>
      rw [show start + (count + 1) = (start + count) + 1 by omega,
        completeDiagonalPrefix_succ, ih,
        outerDiagonalBudget_succ]
      grind [Rat.add_assoc, Rat.add_comm]

/-- The literal `N` by `N` factorial rectangle is contained in the complete
triangle through degree `2*N-1`.  We use boundary `2*N`, which also handles
the zero-term rectangle without a special predecessor convention. -/
theorem rectangularRows_le_completeDiagonalPrefix_double
    {C : Rat} (hC : 0 <= C) (terms : Nat) :
    rectangularRows terms C C terms <=
      completeDiagonalPrefix (terms + terms) C C := by
  rw [← completeTrianglePrefix_eq_completeDiagonalPrefix]
  unfold completeTrianglePrefix
  exact Rat.le_trans
    (rectangularRows_le_doubleTriangle hC terms terms (Nat.le_refl _))
    (completeTriangleRows_mono_count hC (terms + terms)
      terms (terms + terms) (by omega))

/-- The incomplete-outer-diagonal remainder of the literal rectangular
product.  Its forthcoming estimate is the sole missing finite reindexing step
in the reciprocal-exponential bridge. -/
def rectangularOuterRemainder (terms : Nat) (x y : Rat) : Rat :=
  factorialPrefix terms x * factorialPrefix terms y -
    completeDiagonalPrefix terms x y

theorem factorialPrefix_mul_eq_completeDiagonalPrefix_add_remainder
    (terms : Nat) (x y : Rat) :
    factorialPrefix terms x * factorialPrefix terms y =
      completeDiagonalPrefix terms x y +
        rectangularOuterRemainder terms x y := by
  unfold rectangularOuterRemainder
  grind [Rat.sub_eq_add_neg]

/-- The named rectangular remainder is literally the rectangular row sum
minus its complete total-degree triangle. -/
theorem rectangularOuterRemainder_eq_rows_sub_triangle
    (terms : Nat) (x y : Rat) :
    rectangularOuterRemainder terms x y =
      rectangularRows terms x y terms -
        completeTrianglePrefix terms x y := by
  unfold rectangularOuterRemainder
  rw [rectangularRows_eq_prefix_mul,
    completeTrianglePrefix_eq_completeDiagonalPrefix]

/-- The rectangular remainder is the executable sum of its row tails. -/
theorem rectangularOuterRemainder_eq_outerRows
    (terms : Nat) (x y : Rat) :
    rectangularOuterRemainder terms x y =
      outerRows terms x y terms := by
  rw [rectangularOuterRemainder_eq_rows_sub_triangle,
    rectangularRows_eq_triangle_add_outer terms terms (Nat.le_refl _) x y]
  unfold completeTrianglePrefix
  grind [Rat.sub_eq_add_neg]

/-- The literal rectangular Cauchy-product remainder is controlled by the
fully executable row-tail majorant. -/
theorem qabs_rectangularOuterRemainder_le_majorant
    {C x y : Rat} (hC : 0 <= C) (hx : qabs x <= C)
    (hy : qabs y <= C) (terms : Nat) :
    qabs (rectangularOuterRemainder terms x y) <=
      outerRowsMajorant terms C terms := by
  rw [rectangularOuterRemainder_eq_outerRows]
  exact qabs_outerRows_le_majorant hC hx hy terms terms (Nat.le_refl _)

/-- The row-tail majorant is a subset of the complete diagonals beginning at
the rectangular boundary.  This closes the finite reindexing estimate. -/
theorem outerRowsMajorant_le_outerDiagonalBudget
    {C : Rat} (hC : 0 <= C) (terms : Nat) :
    outerRowsMajorant terms C terms <=
      outerDiagonalBudget C terms terms := by
  rw [outerRowsMajorant_eq_outerRows_self C terms terms (Nat.le_refl _)]
  have hrect := rectangularRows_le_completeDiagonalPrefix_double hC terms
  have hsplit := rectangularRows_eq_triangle_add_outer
    terms terms (Nat.le_refl _) C C
  have htriangle := completeTrianglePrefix_eq_completeDiagonalPrefix
    terms C C
  have hbudget := completeDiagonalPrefix_add_outerDiagonalBudget
    C terms terms
  unfold completeTrianglePrefix at htriangle
  grind

/-- The actual rectangular remainder is bounded by the already scheduled
complete outer-diagonal budget. -/
theorem qabs_rectangularOuterRemainder_le_outerDiagonalBudget
    {C x y : Rat} (hC : 0 <= C) (hx : qabs x <= C)
    (hy : qabs y <= C) (terms : Nat) :
    qabs (rectangularOuterRemainder terms x y) <=
      outerDiagonalBudget C terms terms :=
  Rat.le_trans
    (qabs_rectangularOuterRemainder_le_majorant hC hx hy terms)
    (outerRowsMajorant_le_outerDiagonalBudget hC terms)

/-- Executable product stage at which every later complete outer-diagonal
block fits the requested positive rational tolerance. -/
def scheduledProductStage (C : Rat) (eps : QPos) : Nat :=
  RationalMajorant.factorialTailStart (2 * C) +
    RationalMajorant.halfDecayShift
      (2 * RationalMajorant.factorialTailTerm (2 * C)
        (RationalMajorant.factorialTailStart (2 * C))) eps

theorem scheduledProductStage_pos (C : Rat) (eps : QPos) :
    0 < scheduledProductStage C eps := by
  unfold scheduledProductStage RationalMajorant.factorialTailStart
  omega

theorem outerDiagonalBudget_later_scheduled_le_eps
    (C : Rat) (hC : 0 <= C) (eps : QPos)
    (start terms : Nat) (hstart : scheduledProductStage C eps <= start) :
    outerDiagonalBudget C start terms <= eps.val := by
  let scheduled := scheduledProductStage C eps
  have hadd : scheduled + (start - scheduled) = start := by omega
  have hsplit := RationalMajorant.factorialTailPartial_add
    (2 * C) scheduled (start - scheduled) terms
  rw [hadd] at hsplit
  have hfirst :
      0 <= RationalMajorant.factorialTailPartial
        (2 * C) scheduled (start - scheduled) := by
    exact outerDiagonalBudget_nonneg C hC scheduled (start - scheduled)
  have hwhole := outerDiagonalBudget_scheduled_le_eps
    C hC eps ((start - scheduled) + terms)
  change RationalMajorant.factorialTailPartial (2 * C) scheduled
      ((start - scheduled) + terms) <= eps.val at hwhole
  rw [hsplit] at hwhole
  unfold outerDiagonalBudget
  grind

/-- At opposite inputs the literal center product is `1` plus exactly the
named rectangular outer remainder. -/
theorem factorialPrefix_mul_opposite_eq_one_add_remainder
    (terms : Nat) (hterms : 0 < terms) (x : Rat) :
    factorialPrefix terms x * factorialPrefix terms (-x) =
      1 + rectangularOuterRemainder terms x (-x) := by
  rw [factorialPrefix_mul_eq_completeDiagonalPrefix_add_remainder,
    completeDiagonalPrefix_opposite_eq_one terms hterms]

/-- At the computable product stage, the literal opposite-input factorial
prefix product is within `eps` of one. -/
theorem factorialPrefix_mul_opposite_scheduled_close_to_one
    {C x : Rat} (hC : 0 <= C) (hx : qabs x <= C) (eps : QPos) :
    qabs
        (factorialPrefix (scheduledProductStage C eps) x *
            factorialPrefix (scheduledProductStage C eps) (-x) - 1) <=
      eps.val := by
  let stage := scheduledProductStage C eps
  have hstage : 0 < stage := scheduledProductStage_pos C eps
  have hproduct := factorialPrefix_mul_opposite_eq_one_add_remainder
    stage hstage x
  have hy : qabs (-x) <= C := by
    rw [qabs_neg]
    exact hx
  have hremainder :=
    qabs_rectangularOuterRemainder_le_outerDiagonalBudget
      (y := -x) hC hx hy stage
  have hscheduled := outerDiagonalBudget_scheduled_le_eps
    C hC eps stage
  change outerDiagonalBudget C stage stage <= eps.val at hscheduled
  change qabs
      (factorialPrefix stage x * factorialPrefix stage (-x) - 1) <=
    eps.val
  rw [hproduct]
  have heq :
      1 + rectangularOuterRemainder stage x (-x) - 1 =
        rectangularOuterRemainder stage x (-x) := by
    grind [Rat.sub_eq_add_neg]
  rw [heq]
  exact Rat.le_trans hremainder hscheduled

/-- The same product estimate holds at every later literal prefix, which is
the form needed to compare arbitrary earlier raw-real stages. -/
theorem factorialPrefix_mul_opposite_later_close_to_one
    {C x : Rat} (hC : 0 <= C) (hx : qabs x <= C) (eps : QPos)
    (terms : Nat) (hterms : scheduledProductStage C eps <= terms) :
    qabs (factorialPrefix terms x * factorialPrefix terms (-x) - 1) <=
      eps.val := by
  have htermsPos := Nat.lt_of_lt_of_le
    (scheduledProductStage_pos C eps) hterms
  rw [factorialPrefix_mul_opposite_eq_one_add_remainder
    terms htermsPos x]
  have heq :
      1 + rectangularOuterRemainder terms x (-x) - 1 =
        rectangularOuterRemainder terms x (-x) := by
    grind [Rat.sub_eq_add_neg]
  rw [heq]
  exact Rat.le_trans
    (qabs_rectangularOuterRemainder_le_outerDiagonalBudget
      (y := -x) hC hx (by simpa [qabs_neg] using hx) terms)
    (outerDiagonalBudget_later_scheduled_le_eps
      C hC eps terms terms hterms)

end FiniteExponentialProduct
end ComputableAnalysis

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me