Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

LIDT definitions: LDT / MainInductionStep / Theorems / InductionParameterBounds / Averaging

Definition
LIDT_MIPStarRE_LDT_MainInductionStep_Theorems_InductionParameterBounds_Averaging

by Dengnifer · Oct 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

lidt

This bundle supplies the averaging inequalities needed when slice errors are conditioned on a height in the main induction step. Jensen's inequality moves fractional powers through a uniform average, while the other bounds absorb the slice-conditioning loss into the successor dimension parameter.

Principal definitions:

  • avgOver_uniform_rpow_one_div_le_rpow_avg: For nonnegative fff on a nonempty finite set and n≥1n\ge1n≥1, E[f1/n]≤(Ef)1/n\mathbb E[f^{1/n}]\le(\mathbb E f)^{1/n}E[f1/n]≤(Ef)1/n.
  • m_mul_sliceConditioningLoss_rpow_le_next_m_mul_rpow: If x≥0x\ge0x≥0 and 0≤c≤10\le c\le10≤c≤1, then m rpow⁡(λx,c)≤(m+1)rpow⁡(x,c)m\,\operatorname{rpow}(\lambda x,c)\le(m+1)\operatorname{rpow}(x,c)mrpow(λx,c)≤(m+1)rpow(x,c) for the slice-conditioning loss λ=(m+1)/m\lambda=(m+1)/mλ=(m+1)/m.
  • m_sq_mul_sliceConditioningLoss_rpow_le_next_sq_mul_rpow: The same comparison with the squared dimension factors m2m^2m2 and (m+1)2(m+1)^2(m+1)2.

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

Definition code
-- Generated from MIPStarRE/LDT/MainInductionStep/Theorems/InductionParameterBounds/Averaging.lean by skeleton subtraction.
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_AxisParallelLine
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_DiagonalLine
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_Distribution
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_DistributionAvg
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_DistributionPMF
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_DistributionUniformSums
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LinePolynomials
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LowDegreePolynomial
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_OpFamily
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_OperatorExpectations
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_PMFAverages
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_PMFUniformAverages
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_ParametersBase
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_ParametersFiniteAnswers
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_QuantumState
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_SubMeasurementCore
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_SubMeasurementFamilies
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_TensorPlacement
import Definitions.Def_LIDT_MIPStarRE_LDT_MainInductionStep_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_MainInductionStep_Statements
import Definitions.Def_LIDT_MIPStarRE_LDT_MainInductionStep_Theorems_InductionParameterBounds_Preliminaries
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyCore
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyFailures
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyPolynomialFamilies
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyRole_Algebra
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyRole_Core
import Definitions.Def_LIDT_MIPStarRE_Quantum_FiniteMatrix_Basic
import Definitions.Def_LIDT_MIPStarRE_Quantum_FiniteMatrix_BlockDiagonal
import Definitions.Def_LIDT_MIPStarRE_Quantum_FiniteMatrix_NormalizedTrace
import Definitions.Def_LIDT_MIPStarRE_Quantum_FiniteMatrix_Order
import Definitions.Def_LIDT_MIPStarRE_Quantum_FiniteMatrix_TracePairing
import Mathlib
import Mathlib.Analysis.Convex.SpecificFunctions.Pow
import Mathlib.Analysis.MeanInequalitiesPow
import Mathlib.Probability.ProbabilityMassFunction.Integrals
import Mathlib.Probability.ProbabilityMassFunction.Monad

namespace LIDT

/-!
# Section 6 — Induction Parameter Averaging Bounds

This file contains the uniform Jensen estimate used for averaged slice errors,
together with the
`sliceConditioningLoss` comparisons which replace the ambient factor `m` by
`m + 1` in the induction step.

## References

- `blueprint/src/chapter/ch10_induction.tex`
- `references/ldt-paper/inductive_step.tex`
-/

@[expose] public section

namespace MIPStarRE.LDT.MainInductionStep

open MIPStarRE.LDT
open scoped MatrixOrder

/-- Jensen's inequality for `Real.rpow (1/n)` against a uniform distribution:
the average of `(f a)^{1/n}` is at most `(average f)^{1/n}`. This is the
workhorse used inside each of the averaged-slice bounds (`average_slice…_le`)
to push `rpow (1/32)` or `rpow (1/1024)` through a uniform `avgOver` on
`Fq params`. -/
lemma avgOver_uniform_rpow_one_div_le_rpow_avg
    {α : Type*} [Fintype α] [DecidableEq α] [Nonempty α]
    (f : α → Error) (n : ℕ) (hn : 1 ≤ n) (hf : ∀ a, 0 ≤ f a) :
    avgOver (uniformDistribution α)
        (fun a => Real.rpow (f a) (1 / (n : Error))) ≤
      Real.rpow (avgOver (uniformDistribution α) f) (1 / (n : Error)) := by
  rw [avgOver_uniform_eq_pmf_realWeightedSum, avgOver_uniform_eq_pmf_realWeightedSum]
  exact PMF.realWeightedSum_rpow_one_div_le_rpow
    (p := PMF.uniformOfFintype α) (f := f) (n := n) hn hf

/-- Internal helper: `m · (sliceConditioningLoss · x)^c ≤ m_next · x^c` for `c ≤ 1`.

Exposed for cross-module use in `AvgSliceErrors`. -/
lemma m_mul_sliceConditioningLoss_rpow_le_next_m_mul_rpow
    (params : Parameters) {x c : Error}
    (hx : 0 ≤ x) (_hc_nonneg : 0 ≤ c) (hc_le_one : c ≤ 1) :
    (params.m : Error) * Real.rpow (sliceConditioningLoss params * x) c ≤
      (params.next.m : Error) * Real.rpow x c := by
  have hm0 : (params.m : Error) ≠ 0 := by
    exact_mod_cast Nat.ne_of_gt params.hm
  have hloss_nonneg : 0 ≤ sliceConditioningLoss params := by
    unfold sliceConditioningLoss
    positivity
  have hloss_ge_one : (1 : Error) ≤ sliceConditioningLoss params := by
    unfold sliceConditioningLoss
    have hm_pos : (0 : Error) < (params.m : Error) := by
      exact_mod_cast params.hm
    have hnum_ge : (params.m : Error) ≤ ((params.m + 1 : ℕ) : Error) := by
      exact_mod_cast Nat.le_succ params.m
    exact (one_le_div₀ hm_pos).2 hnum_ge
  have hloss_rpow_le :
      Real.rpow (sliceConditioningLoss params) c ≤ sliceConditioningLoss params := by
    calc
      Real.rpow (sliceConditioningLoss params) c
          ≤ Real.rpow (sliceConditioningLoss params) 1 := by
            exact Real.rpow_le_rpow_of_exponent_le hloss_ge_one hc_le_one
      _ = sliceConditioningLoss params := by simp
  calc
    (params.m : Error) * Real.rpow (sliceConditioningLoss params * x) c
      = (params.m : Error) *
          (Real.rpow (sliceConditioningLoss params) c * Real.rpow x c) := by
            rw [show Real.rpow (sliceConditioningLoss params * x) c =
                Real.rpow (sliceConditioningLoss params) c * Real.rpow x c by
                exact Real.mul_rpow hloss_nonneg hx]
    _ ≤ (params.m : Error) * (sliceConditioningLoss params * Real.rpow x c) := by
          gcongr
          exact Real.rpow_nonneg hx c
    _ = (params.next.m : Error) * Real.rpow x c := by
          have hnext_eq : (params.next.m : Error) = ((params.m + 1 : ℕ) : Error) := by
            norm_num [Parameters.next]
          rw [hnext_eq]
          unfold sliceConditioningLoss
          field_simp [hm0]
/-- Internal helper: `m² · (sliceConditioningLoss · x)^c ≤ m_next² · x^c` for `c ≤ 1`.

Exposed for cross-module use in `AvgSliceErrors`. -/
lemma m_sq_mul_sliceConditioningLoss_rpow_le_next_sq_mul_rpow
    (params : Parameters) {x c : Error}
    (hx : 0 ≤ x) (hc_nonneg : 0 ≤ c) (hc_le_one : c ≤ 1) :
    ((params.m : Error) ^ (2 : ℕ)) * Real.rpow (sliceConditioningLoss params * x) c ≤
      ((params.next.m : Error) ^ (2 : ℕ)) * Real.rpow x c := by
  have hm_le_next : (params.m : Error) ≤ (params.next.m : Error) := by
    exact_mod_cast Nat.le_succ params.m
  calc
    ((params.m : Error) ^ (2 : ℕ)) * Real.rpow (sliceConditioningLoss params * x) c
      = (params.m : Error) *
          ((params.m : Error) * Real.rpow (sliceConditioningLoss params * x) c) := by
            ring
    _ ≤ (params.m : Error) * ((params.next.m : Error) * Real.rpow x c) := by
          exact mul_le_mul_of_nonneg_left
            (m_mul_sliceConditioningLoss_rpow_le_next_m_mul_rpow params hx hc_nonneg hc_le_one)
            (by positivity)
    _ ≤ ((params.next.m : Error) ^ (2 : ℕ)) * Real.rpow x c := by
          have hcoef :
              (params.m : Error) * (params.next.m : Error) ≤
                ((params.next.m : Error) ^ (2 : ℕ)) := by
            nlinarith
          have hrpow_nonneg : 0 ≤ Real.rpow x c := Real.rpow_nonneg hx c
          simpa [mul_assoc] using (mul_le_mul_of_nonneg_right hcoef hrpow_nonneg)

end MIPStarRE.LDT.MainInductionStep

end

end LIDT
Source
https://github.com/LionSR/MIPStarRE/blob/f382c801026f53a9efc260fdee707cb35e0adb15/MIPStarRE/LDT/MainInductionStep/Theorems/InductionParameterBounds/Averaging.lean#L27-L110

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