Cascade Zeta1 Bound General
ProvedLIDT.MIPStarRE.LDT.Test.cascadeZeta1_bound_generallidt
The general first-stage cascade bound has the same explicit envelope form.
Assume the cascade hypotheses, the coarse bound on nu, and exclude the exceptional branch and . Then
The theorem combines the tight first-stage estimate with the degree-size and square-root envelope bounds. Together with the exceptional branch it yields a uniform first-stage estimate.
Formalization credit: Sirui Lu, Ruixuan Deng, Yanqiao Zhu, and Zhengfeng Ji (arXiv:2609.19814). Mathematical source: Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen (arXiv:2009.12982).
Formalization Note. The source declaration is MIPStarRE.LDT.Test.cascadeZeta1_bound_general; its Lean statement gives the exact quantifier order and all boundary hypotheses.
Preamble
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_ParametersBase import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_SqrtBounds import Definitions.Def_LIDT_MIPStarRE_LDT_Test_MainTheorem_ScalarBounds_Definitions import Definitions.Def_LIDT_MIPStarRE_LDT_Test_MainTheorem_ScalarBounds_EnvelopeBounds import Mathlib namespace LIDT.MIPStarRE.LDT end LIDT.MIPStarRE.LDT namespace LIDT.MIPStarRE.LDT.Test end LIDT.MIPStarRE.LDT.Test open LIDT /-! # Error cascade — bounds for `σ` and `ζ₁` This module proves the tight and absorbing bounds for the first two cascade variables, `σ` and `ζ₁`. The later variables `ζ₂`, `ζ₃`, and `ζ₄`, together with the top-level consolidator `errorCascade_le_mainFormalError`, are in the subsequent leaves of `Test.MainTheorem.ScalarBounds.CascadeBounds`. The first cascade steps have three components: * The **tight cascade bound** (`cascadeSigma_tight_bound`, `cascadeZeta1_bound`, …), deriving the native estimate directly from the cascade definition. * The **absorbing bound** (`sigma_bound`, `zeta1_bound`, …), coarsening the tight estimate to the final `mainFormalEnvelope` envelope. * The corresponding nonnegativity lemmas (`cascadeSigma_nonneg`, `cascadeZeta1_nonneg`), used by the later cascade estimates. ## References * `references/ldt-paper/inductive_step.tex`, lines 187–234. -/ @[expose] public section open scoped BigOperators open LIDT.MIPStarRE.LDT open LIDT.MIPStarRE.LDT.Test
Formal statement
theorem LIDT.MIPStarRE.LDT.Test.cascadeZeta1_bound_general {params : _root_.LIDT.MIPStarRE.LDT.Parameters} {k : ℕ} {eps : _root_.LIDT.MIPStarRE.LDT.Error}
(h : _root_.LIDT.MIPStarRE.LDT.Test.CascadeHypotheses params k eps) {ν : _root_.LIDT.MIPStarRE.LDT.Error}
(hν : ν ≤ 10000 * ((k : _root_.LIDT.MIPStarRE.LDT.Error) ^ (2 : ℕ)) * ((params.m : _root_.LIDT.MIPStarRE.LDT.Error) ^ (2 : ℕ)) *
(Real.rpow eps (1 / (1024 : _root_.LIDT.MIPStarRE.LDT.Error)) +
Real.rpow ((params.d : _root_.LIDT.MIPStarRE.LDT.Error) / (params.q : _root_.LIDT.MIPStarRE.LDT.Error)) (1 / (1024 : _root_.LIDT.MIPStarRE.LDT.Error))))
(hkm1 : ¬ (k = 1 ∧ params.m = 1)) :
_root_.LIDT.MIPStarRE.LDT.Test.cascadeZeta1 params eps (_root_.LIDT.MIPStarRE.LDT.Test.cascadeSigma params k ν) ≤
20204 * ((k : _root_.LIDT.MIPStarRE.LDT.Error) ^ (2 : ℕ)) * ((params.m : _root_.LIDT.MIPStarRE.LDT.Error) ^ (4 : ℕ)) *
_root_.LIDT.MIPStarRE.LDT.Test.stepEnvelope params k eps (2048 : _root_.LIDT.MIPStarRE.LDT.Error) (160000 : _root_.LIDT.MIPStarRE.LDT.Error) := by sorrySource