Documentation

MIPStarRE.LDT.MainInductionStep.Theorems.AvgSliceErrors.Successor

Section 6 — Averaged Slice Error Bounds: Successor Outputs #

This module packages recursive answer-valued slice measurements and the final self-improvement-to-main-induction error comparisons.

theorem MIPStarRE.LDT.MainInductionStep.answerSuccessorRecursiveSliceMeasurements_ofMainInductionHypothesis {ι : Type uι} [Fintype ι] [DecidableEq ι] (params : Parameters) [FieldModel params.q] (strategy : AnswerSymStrat params.next ι) (eps delta gamma : Error) (k : ℕ) (hgood : strategy.IsGood eps delta gamma) (hinduction : AnswerMainInductionHypothesis params) (hk_next : 400 * params.next.m * params.next.d ≤ k) (hsmall : mainInductionError params.next k eps delta gamma < 1) :
∃ (profile : AnswerSuccessorRestrictedFailureProfile params strategy) (sliceError : Fq params → Error) (sliceMeasurement : Fq params → Measurement (Polynomial params) ι), averageAnswerSuccessorRestrictedAxisParallelError params profile ≤ sliceConditioningLoss params * eps ∧ averageAnswerSuccessorRestrictedSelfConsistencyError params profile ≤ delta ∧ averageAnswerSuccessorRestrictedDiagonalError params profile ≤ sliceConditioningLoss params * gamma ∧ (∀ (x : Fq params), ConsRel strategy.state (uniformDistribution (Point params)) (xRestrictedAnswerSymStratOfAnswer params strategy x).pointMeasurement.toIdxSubMeas (polynomialEvaluationFamily params (sliceMeasurement x).toSubMeas) (sliceError x)) ∧ (∀ (x : Fq params), sliceError x ≤ mainInductionError params k (profile.axisParallel x) (profile.selfConsistency x) (profile.diagonal x)) ∧ avgOver (uniformDistribution (Fq params)) sliceError ≤ ↑params.m ^ 2 * (mainInductionNu params.next k eps delta gamma + Real.exp (-(↑k / (80000 * ↑params.m ^ 2))))

Extract the recursive answer-valued slice measurements and their averaged main-induction error bound.

Paper origin: references/ldt-paper/inductive_step.tex:441-551. After the restricted-probabilities theorem and the predecessor answer-valued induction hypothesis are applied to the restricted slices, this theorem packages the resulting measurements G^x and proves the displayed bound \mathbb E_x \sigma_x \leq \sigma.

Lean-only: This is an internal construction theorem for the simultaneous answer-valued successor route tracked in issue #1507; it does not add a predecessor conclusion as an assumption to any source-facing theorem. Discharge: proved here from the restricted-probabilities theorem and the answer-valued predecessor induction hypothesis.

theorem MIPStarRE.LDT.MainInductionStep.answerSuccessorSelfImprovementOutputs_ofMainInductionHypothesis {ι : Type uι} [Fintype ι] [DecidableEq ι] (params : Parameters) [FieldModel params.q] (strategy : AnswerSymStrat params.next ι) (eps delta gamma : Error) (k : ℕ) (hgood : strategy.IsGood eps delta gamma) (hinduction : AnswerMainInductionHypothesis params) (hk_next : 400 * params.next.m * params.next.d ≤ k) (hsmall : mainInductionError params.next k eps delta gamma < 1) :
∃ (profile : AnswerSuccessorRestrictedFailureProfile params strategy) (sliceError : Fq params → Error) (sliceMeasurement : Fq params → Measurement (Polynomial params) ι) (sliceProj : Fq params → ProjSubMeas (Polynomial params) ι) (sliceWitness : Fq params → Quantum.Op ι), averageAnswerSuccessorRestrictedAxisParallelError params profile ≤ sliceConditioningLoss params * eps ∧ averageAnswerSuccessorRestrictedSelfConsistencyError params profile ≤ delta ∧ averageAnswerSuccessorRestrictedDiagonalError params profile ≤ sliceConditioningLoss params * gamma ∧ (∀ (x : Fq params), ConsRel strategy.state (uniformDistribution (Point params)) (xRestrictedAnswerSymStratOfAnswer params strategy x).pointMeasurement.toIdxSubMeas (polynomialEvaluationFamily params (sliceMeasurement x).toSubMeas) (sliceError x)) ∧ (∀ (x : Fq params), sliceError x ≤ mainInductionError params k (profile.axisParallel x) (profile.selfConsistency x) (profile.diagonal x)) ∧ avgOver (uniformDistribution (Fq params)) sliceError ≤ ↑params.m ^ 2 * (mainInductionNu params.next k eps delta gamma + Real.exp (-(↑k / (80000 * ↑params.m ^ 2)))) ∧ (avgOver (uniformDistribution (Fq params)) fun (x : Fq params) => selfImprovementInInductionError params (profile.axisParallel x) (profile.selfConsistency x) (profile.diagonal x)) ≤ selfImprovementInInductionError params.next eps delta gamma ∧ (∀ (x : Fq params), CompletenessAtLeast strategy.state (sliceProj x).liftLeft (1 - sliceError x - selfImprovementInInductionError params (profile.axisParallel x) (profile.selfConsistency x) (profile.diagonal x))) ∧ (∀ (x : Fq params), ConsRel strategy.state (uniformDistribution (Point params)) (xRestrictedAnswerSymStratOfAnswer params strategy x).pointMeasurement.toIdxSubMeas (polynomialEvaluationFamily params (sliceProj x).toSubMeas) (selfImprovementInInductionError params (profile.axisParallel x) (profile.selfConsistency x) (profile.diagonal x))) ∧ (∀ (x : Fq params), BipartiteSSCRel strategy.state (uniformDistribution Unit) (constSubMeasFamily (sliceProj x).toSubMeas) (selfImprovementInInductionError params (profile.axisParallel x) (profile.selfConsistency x) (profile.diagonal x))) ∧ (∀ (x : Fq params), SDDRel strategy.state (uniformDistribution Unit) (constSubMeasFamily (leftPlacedSubMeas (sliceProj x).toSubMeas)) (constSubMeasFamily (rightPlacedSubMeas (sliceProj x).toSubMeas)) (selfImprovementInInductionError params (profile.axisParallel x) (profile.selfConsistency x) (profile.diagonal x))) ∧ (∀ (x : Fq params), tensorFailureExpectation strategy.state (sliceWitness x) (sliceProj x).toSubMeas ≤ selfImprovementInInductionError params (profile.axisParallel x) (profile.selfConsistency x) (profile.diagonal x)) ∧ ∀ (x : Fq params) (h : Polynomial params), IdxPolyFamily.averagedSlicePointEvaluationOperator (answerSelfImprovementCarrier params.next strategy) x h ≤ sliceWitness x

Apply self-improvement to the recursive answer-valued successor slices.

Paper origin: references/ldt-paper/inductive_step.tex:461-551. Starting from the recursive answer-valued slice measurements supplied by the predecessor induction hypothesis, this theorem constructs the projective slice submeasurements \widehat G^x and witnesses Z^x, proves their four self-improvement outputs, and keeps the averaged \zeta_x and \sigma_x bounds available.

Lean-only: The ordinary carrier appears only in the domination field, where its point measurement is the same last-coordinate restriction of the ambient answer-valued point measurement. The proof invokes only the axis-parallel/self-consistency form of self-improvement, and therefore does not claim that the carrier's dummy diagonal measurement is a good diagonal realization of the answer-valued strategy. This internal construction is tracked in issue #1507. Discharge: proved here from the recursive slice measurements and the formal self-improvement theorem.

theorem MIPStarRE.LDT.MainInductionStep.selfImprovementInInductionError_le_mainInductionNu {ι : Type uι} [Fintype ι] [DecidableEq ι] (params : Parameters) [FieldModel params.q] (strategy : SymStrat params.next ι) (eps delta gamma : Error) (k : ℕ) (hgood : strategy.IsGood eps delta gamma) (hsmall : mainInductionError params.next k eps delta gamma < 1) (heps_le_one : eps ≤ 1) (hdelta_le_one : delta ≤ 1) (hdq_le_q : params.d ≤ params.q) :
selfImprovementInInductionError params.next eps delta gamma ≤ mainInductionNu params.next k eps delta gamma

Paper's \eqref{eq:zeta-smaller-than-nu}: under the small-parameter hypotheses, the averaged self-improvement interface error \zeta is bounded by the next-stage induction parameter \nu.

theorem MIPStarRE.LDT.MainInductionStep.answer_selfImprovementInInductionError_le_mainInductionNu {ι : Type uι} [Fintype ι] [DecidableEq ι] (params : Parameters) [FieldModel params.q] (strategy : AnswerSymStrat params.next ι) (eps delta gamma : Error) (k : ℕ) (hgood : strategy.IsGood eps delta gamma) (hsmall : mainInductionError params.next k eps delta gamma < 1) (heps_le_one : eps ≤ 1) (hdelta_le_one : delta ≤ 1) (hdq_le_q : params.d ≤ params.q) :
selfImprovementInInductionError params.next eps delta gamma ≤ mainInductionNu params.next k eps delta gamma

Answer-valued analogue of selfImprovementInInductionError_le_mainInductionNu.

This is the scalar part of the successor proof for an ambient answer-valued strategy. It uses only the answer-valued goodness bounds and does not replace the answer-valued diagonal measurement by an ordinary one.