Sqrt Step Envelope Le
ProvedLIDT.MIPStarRE.LDT.Test.sqrt_stepEnvelope_lelidt
Taking a square root doubles both parameters of the step envelope.
Assume the scalar cascade hypotheses and let and . For
one has
The proof applies the square-root subadditivity estimate to the three summands, uses the fractional-power identity for the first two, and halves the exponential rate by doubling .
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.sqrt_stepEnvelope_le; 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 open LIDT /-! # Error cascade — envelope and root bounding machinery Internal helper lemmas for the error-cascade bookkeeping of Step 8. These provide the step-envelope interpolation (`stepEnvelope`), monotonicity under denominator enlargement, square-root scaling, and explicit numeric bounds on various `rpow` and `sqrt` expressions. All lemmas are technical and should not be part of downstream API. ## 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.sqrt_stepEnvelope_le {params : _root_.LIDT.MIPStarRE.LDT.Parameters} {k : ℕ} {eps : _root_.LIDT.MIPStarRE.LDT.Error}
(h : _root_.LIDT.MIPStarRE.LDT.Test.CascadeHypotheses params k eps) {n N : _root_.LIDT.MIPStarRE.LDT.Error} (hn : 0 < n) (hN : 0 < N) :
Real.sqrt (_root_.LIDT.MIPStarRE.LDT.Test.stepEnvelope params k eps n N) ≤ _root_.LIDT.MIPStarRE.LDT.Test.stepEnvelope params k eps (2 * n) (2 * N) := by sorrySource