Documentation

MIPStarRE.LDT.SelfImprovement.Theorems.Results.BoundednessTransport.BoundednessGap

Boundedness transport boundedness-gap estimates #

This file contains the helper boundedness-gap decomposition, its data-processing transport, and the final projective-residual boundedness constructors used in the self-improvement proof.

References #

theorem MIPStarRE.LDT.SelfImprovement.helper_boundedness_gap_eq_upper_gap_add_off_diagonal_avg {ι : Type u_1} [Fintype ι] [DecidableEq ι] (params : Parameters) [FieldModel params.q] (strategy : SymStrat params ι) (H : SubMeas (Polynomial params) ι) (Z : Quantum.Op ι) :
helperBoundednessGap params strategy H Z = ev strategy.state (helperUpperOperator params Z) - ev strategy.state (rightTensor H.total) + avgOver (uniformDistribution (Point params)) fun (u : Point params) => ∑ h : Polynomial params, ∑ a ∈ Finset.univ.erase (h.toFun u), ev strategy.state (opTensor ((strategy.pointMeasurement u).outcome a) (H.outcome h))

Algebraic decomposition of the helper boundedness gap.

The scalar gap ⟨Z ⊗ I - helperAgreementAverageOperator⟩ is the sum of ⟨Z ⊗ I⟩ - ⟨I ⊗ H.total⟩ and the off-diagonal average produced by helper_boundedness_slack_average_ev_eq_off_diagonal_avg. This is the formal algebraic bridge between the reindexing calculation and the final boundedness estimate in the proof of self-improvement.

theorem MIPStarRE.LDT.SelfImprovement.helper_boundedness_gap_le_selfImprovementHelperError {ι : Type u_1} [Fintype ι] [DecidableEq ι] (params : Parameters) [FieldModel params.q] (strategy : SymStrat params ι) (eps delta : Error) (heps : 0 ≤ eps) (hdelta : 0 ≤ delta) {Hhat : SubMeas (Polynomial params) ι} {Z : Quantum.Op ι} (hZ_vs_H : ev strategy.state (helperUpperOperator params Z) - ev strategy.state (rightTensor Hhat.total) ≤ 3 * √delta) (hoffdiag : (avgOver (uniformDistribution (Point params)) fun (u : Point params) => ∑ h : Polynomial params, ∑ a ∈ Finset.univ.erase (h.toFun u), ev strategy.state (opTensor ((strategy.pointMeasurement u).outcome a) (Hhat.outcome h))) ≤ 4 * √(selfImprovementVarianceError params eps delta)) :
helperBoundednessGap params strategy Hhat Z ≤ selfImprovementHelperError params eps delta

Helper-stage boundedness from the scalar comparison and the off-diagonal estimate.

The helper boundedness gap decomposes as ⟨Z ⊗ I⟩ - ⟨I ⊗ Hhat.total⟩ plus the off-diagonal average from helper_boundedness_slack_average_ev_eq_off_diagonal_avg. Thus the comparison ⟨Z ⊗ I⟩ - ⟨I ⊗ Hhat.total⟩ ≤ 3 √δ, together with the off-diagonal estimate ≤ 4 √ζ_variance, gives the helper threshold after applying helper_boundedness_error_le_selfImprovementHelperError.

theorem MIPStarRE.LDT.SelfImprovement.helper_boundedness_gap_le_selfImprovementHelperError_of_pointConsistencyAddInU_transfer {ι : Type u_1} [Fintype ι] [DecidableEq ι] (params : Parameters) [FieldModel params.q] (strategy : SymStrat params ι) (eps delta : Error) (heps : 0 ≤ eps) (hdelta : 0 ≤ delta) {T Hhat : SubMeas (Polynomial params) ι} {Z : Quantum.Op ι} (hZ_vs_H : ev strategy.state (helperUpperOperator params Z) - ev strategy.state (rightTensor Hhat.total) ≤ 3 * √delta) (htransfer : |addInULeftQuantity params strategy strategy.pointMeasurement.toIdxSubMeas Hhat (pointConsistencyAddInUSelection params) - addInURightQuantity params strategy strategy.pointMeasurement.toIdxSubMeas T (pointConsistencyAddInUSelection params)| ≤ addInUError params eps delta) :
helperBoundednessGap params strategy Hhat Z ≤ selfImprovementHelperError params eps delta

Helper-stage boundedness from the scalar comparison and the point-consistency add-in-u transfer.

This theorem composes the off-diagonal estimate supplied by pointConsistencyAddInUSelection with helper_boundedness_gap_le_selfImprovementHelperError. It is the formal statement of the sentence "combined with the explicit A-consistency bound" in the boundedness paragraph of the self-improvement proof.

theorem MIPStarRE.LDT.SelfImprovement.helper_upper_gap_rightTensor_le_three_sqrt_delta_of_helper_outputs {ι : Type u_1} [Fintype ι] [DecidableEq ι] (params : Parameters) [FieldModel params.q] (strategy : SymStrat params ι) (eps delta : Error) {T : Measurement (Polynomial params) ι} {Hhat : SubMeas (Polynomial params) ι} {Z : Quantum.Op ι} (hhelper : SelfImprovementHelperConclusion params strategy T Hhat Z eps delta) (hssc : BipartiteSSCRel strategy.state (uniformDistribution (Point params)) strategy.pointMeasurement.toIdxSubMeas delta) (hslack : ∀ (h : Polynomial params), T.outcome h * averagedPointOperator params strategy h = T.outcome h * Z) :
ev strategy.state (helperUpperOperator params Z) - ev strategy.state (rightTensor Hhat.total) ≤ 3 * √delta

Convert the helper-completeness Hhat-versus-Z comparison to the right-placed total comparison used in the boundedness gap.

The helper-completeness paragraph naturally proves ⟨ψ, Z ⊗ I⟩ - 3√δ ≤ subMeasMass ψ Hhat.liftLeft. The boundedness decomposition, however, uses the right-placed total ⟨ψ, I ⊗ Hhat.total⟩. On the permutation-invariant strategy state these scalars agree, so the comparison becomes ⟨ψ, Z ⊗ I⟩ - ⟨ψ, I ⊗ Hhat.total⟩ ≤ 3√δ.

theorem MIPStarRE.LDT.SelfImprovement.helper_boundedness_gap_le_selfImprovementHelperError_of_helper_outputs {ι : Type u_1} [Fintype ι] [DecidableEq ι] (params : Parameters) [FieldModel params.q] (strategy : SymStrat params ι) (eps delta : Error) (heps : 0 ≤ eps) (hdelta : 0 ≤ delta) {T : Measurement (Polynomial params) ι} {Hhat : SubMeas (Polynomial params) ι} {Z : Quantum.Op ι} (hhelper : SelfImprovementHelperConclusion params strategy T Hhat Z eps delta) (hssc : BipartiteSSCRel strategy.state (uniformDistribution (Point params)) strategy.pointMeasurement.toIdxSubMeas delta) (hslack : ∀ (h : Polynomial params), T.outcome h * averagedPointOperator params strategy h = T.outcome h * Z) (htransfer : |addInULeftQuantity params strategy strategy.pointMeasurement.toIdxSubMeas Hhat (pointConsistencyAddInUSelection params) - addInURightQuantity params strategy strategy.pointMeasurement.toIdxSubMeas T.toSubMeas (pointConsistencyAddInUSelection params)| ≤ addInUError params eps delta) :
helperBoundednessGap params strategy Hhat Z ≤ selfImprovementHelperError params eps delta

Helper-stage boundedness from the actual helper comparison and the point-consistency add-in-u transfer.

This theorem composes the helper-completeness comparison Hhat-versus-Z with the boundedness off-diagonal estimate. Complementary slackness remains an explicit hypothesis because the reduced SelfImprovementHelperConclusion records only the presently formalized SDP facts. The off-diagonal transfer is likewise explicit: it is the formal statement of the add-in-u application with S_u = {(a,h) : h(u) ≠ a}.

theorem MIPStarRE.LDT.SelfImprovement.helper_boundedness_gap_transport_through_data_processing {ι : Type u_1} [Fintype ι] [DecidableEq ι] (params : Parameters) [FieldModel params.q] (strategy : SymStrat params ι) (Hhat : SubMeas (Polynomial params) ι) (H : ProjSubMeas (Polynomial params) ι) (Z : Quantum.Op ι) (ε : Error) (hdata : SDDRel strategy.state (uniformDistribution (Point params)) (polynomialEvaluationFamily params Hhat).liftLeft (polynomialEvaluationFamily params H.toSubMeas).liftLeft ε) :
helperBoundednessGap params strategy H.toSubMeas Z ≤ helperBoundednessGap params strategy Hhat Z + √ε

Transport the helper boundedness gap through the data-processing approximation between Hhat and H.

The input hdata is exactly the data-processing SDD bound already produced inside selfImprovement. The conclusion says that replacing the helper polynomial family in the point-agreement average by the projective family costs at most sqrt ε, matching Proposition easy-approx-from-approx-delta in the boundedness paragraph of the paper.

theorem MIPStarRE.LDT.SelfImprovement.projective_boundedness_gap_le_helper_boundedness_gap {ι : Type u_1} [Fintype ι] [DecidableEq ι] (params : Parameters) [FieldModel params.q] (strategy : SymStrat params ι) (H : ProjSubMeas (Polynomial params) ι) (Z : Quantum.Op ι) (hdual : ∀ (h : Polynomial params), 0 ≤ sdpDualSlackOperator params strategy Z h) :
projectiveBoundednessGap params strategy H Z ≤ helperBoundednessGap params strategy H.toSubMeas Z

Compare the final projective residual with the helper boundedness gap for the same projective family.

This is the SDP dual-slack step in the projective boundedness paragraph of thm:self-improvement (references/ldt-paper/self_improvement.tex, lines 742--749): the term Z ⊗ H_h in the projective residual dominates (E_u A^u_{h(u)}) ⊗ H_h for each polynomial h, and summing these inequalities turns Z ⊗ (I - H) into the helper-stage defect Z ⊗ I - E_u Σ_a A^u_a ⊗ H_[h(u)=a].

theorem MIPStarRE.LDT.SelfImprovement.final_fields_projective_residual_bound_natural {ι : Type u_1} [Fintype ι] [DecidableEq ι] (params : Parameters) [FieldModel params.q] (strategy : SymStrat params ι) (eps delta : Error) {T : Measurement (Polynomial params) ι} {Hhat : SubMeas (Polynomial params) ι} {H : ProjSubMeas (Polynomial params) ι} {Z : Quantum.Op ι} (hhelper : SelfImprovementHelperConclusion params strategy T Hhat Z eps delta) (hhelperBounded : helperBoundednessGap params strategy Hhat Z ≤ selfImprovementHelperError params eps delta) (hdata : SDDRel strategy.state (uniformDistribution (Point params)) (polynomialEvaluationFamily params Hhat).liftLeft (polynomialEvaluationFamily params H.toSubMeas).liftLeft (selfImprovementDataProcessingError params eps delta)) :

Natural-error projective-residual construction.

Given the helper-stage boundedness estimate for Hhat, the dual-slack comparator above and the existing data-processing transport produce the final projective residual at the paper's natural error selfImprovementHelperError + sqrt selfImprovementDataProcessingError. The separate numerical absorption into the literal selfImprovementError threshold is intentionally not hidden in this theorem.

Paper source: references/ldt-paper/self_improvement.tex lines 742--755. This is a source-faithful construction step for the final-fields boundedness conclusion.

theorem MIPStarRE.LDT.SelfImprovement.final_fields_projective_residual_bound {ι : Type u_1} [Fintype ι] [DecidableEq ι] (params : Parameters) [FieldModel params.q] (strategy : SymStrat params ι) (eps delta : Error) {T : Measurement (Polynomial params) ι} {Hhat : SubMeas (Polynomial params) ι} {H : ProjSubMeas (Polynomial params) ι} {Z : Quantum.Op ι} (hhelper : SelfImprovementHelperConclusion params strategy T Hhat Z eps delta) (hhelperBounded : helperBoundednessGap params strategy Hhat Z ≤ selfImprovementHelperError params eps delta) (hdata : SDDRel strategy.state (uniformDistribution (Point params)) (polynomialEvaluationFamily params Hhat).liftLeft (polynomialEvaluationFamily params H.toSubMeas).liftLeft (selfImprovementDataProcessingError params eps delta)) (habsorb : selfImprovementHelperError params eps delta + √(selfImprovementDataProcessingError params eps delta) ≤ selfImprovementError params eps delta) :
projectiveBoundednessGap params strategy H Z ≤ selfImprovementError params eps delta

Literal-threshold projective-residual construction.

This theorem combines final_fields_projective_residual_bound_natural with a separately named numerical absorption lemma. The analytic inputs are only the helper-stage boundedness estimate, dual feasibility from SelfImprovementHelperConclusion, and the data-processing SDD output already produced inside selfImprovement.

Paper source: references/ldt-paper/self_improvement.tex lines 742--755. This is a source-faithful construction step for the final-fields boundedness conclusion.

theorem MIPStarRE.LDT.SelfImprovement.final_fields_projective_residual_bound_of_small_errors {ι : Type u_1} [Fintype ι] [DecidableEq ι] (params : Parameters) [FieldModel params.q] (strategy : SymStrat params ι) (eps delta : Error) (heps : 0 ≤ eps) (heps_le_one : eps ≤ 1) (hdelta : 0 ≤ delta) (hdelta_le_one : delta ≤ 1) (hd_le_q : ↑params.d ≤ ↑params.q) {T : Measurement (Polynomial params) ι} {Hhat : SubMeas (Polynomial params) ι} {H : ProjSubMeas (Polynomial params) ι} {Z : Quantum.Op ι} (hhelper : SelfImprovementHelperConclusion params strategy T Hhat Z eps delta) (hhelperBounded : helperBoundednessGap params strategy Hhat Z ≤ selfImprovementHelperError params eps delta) (hdata : SDDRel strategy.state (uniformDistribution (Point params)) (polynomialEvaluationFamily params Hhat).liftLeft (polynomialEvaluationFamily params H.toSubMeas).liftLeft (selfImprovementDataProcessingError params eps delta)) :
projectiveBoundednessGap params strategy H Z ≤ selfImprovementError params eps delta

Literal-threshold projective-residual construction under the standard unit-interval smallness hypotheses.

This derived theorem follows from final_fields_projective_residual_bound: the numerical absorption input is provided by final_fields_projective_residual_error_le_selfImprovementError, so callers only need the helper-stage boundedness estimate, data-processing output, and the usual smallness assumptions on eps, delta, and d/q.

Paper source: references/ldt-paper/self_improvement.tex lines 742--755. This is a source-faithful construction step for the final-fields boundedness conclusion.

theorem MIPStarRE.LDT.SelfImprovement.final_fields_projective_residual_bound_of_helper_outputs {ι : Type u_1} [Fintype ι] [DecidableEq ι] (params : Parameters) [FieldModel params.q] (strategy : SymStrat params ι) (eps delta : Error) (heps : 0 ≤ eps) (heps_le_one : eps ≤ 1) (hdelta : 0 ≤ delta) (hdelta_le_one : delta ≤ 1) (hd_le_q : ↑params.d ≤ ↑params.q) {T : Measurement (Polynomial params) ι} {Hhat : SubMeas (Polynomial params) ι} {H : ProjSubMeas (Polynomial params) ι} {Z : Quantum.Op ι} (hhelper : SelfImprovementHelperConclusion params strategy T Hhat Z eps delta) (hssc : BipartiteSSCRel strategy.state (uniformDistribution (Point params)) strategy.pointMeasurement.toIdxSubMeas delta) (hslack : ∀ (h : Polynomial params), T.outcome h * averagedPointOperator params strategy h = T.outcome h * Z) (htransfer : |addInULeftQuantity params strategy strategy.pointMeasurement.toIdxSubMeas Hhat (pointConsistencyAddInUSelection params) - addInURightQuantity params strategy strategy.pointMeasurement.toIdxSubMeas T.toSubMeas (pointConsistencyAddInUSelection params)| ≤ addInUError params eps delta) (hdata : SDDRel strategy.state (uniformDistribution (Point params)) (polynomialEvaluationFamily params Hhat).liftLeft (polynomialEvaluationFamily params H.toSubMeas).liftLeft (selfImprovementDataProcessingError params eps delta)) :
projectiveBoundednessGap params strategy H Z ≤ selfImprovementError params eps delta

Final projective-residual construction from helper outputs and the point-consistency add-in-u transfer.

The theorem proves the boundedness part of the final-fields construction once the orthonormalization data-processing estimate is available. It supplies the helper-stage boundedness estimate from the helper comparison, complementary slackness, point self-consistency, and the off-diagonal add-in-u transfer, then applies the standard data-processing transport and numerical absorption into selfImprovementError.

Paper source: references/ldt-paper/self_improvement.tex lines 742--755. This is a source-faithful construction step for the final-fields boundedness conclusion.

theorem MIPStarRE.LDT.SelfImprovement.final_fields_bounded {ι : Type u_1} [Fintype ι] [DecidableEq ι] {α : Type u_2} [Fintype α] (ψ : QuantumState (ι × ι)) (A : SubMeas α ι) {Z : Quantum.Op ι} (hOne : 1 ≤ Z) {ε : Error} (hε : 0 ≤ ε) :

Final-fields constructor for the BoundedByOperator conclusion.

If the SDP dual witness dominates the identity, then the left-placed mass of any submeasurement is dominated by Z ⊗ I: the total bound A.total ≤ 1 ≤ Z lifts by monotonicity to leftTensor A.total ≤ leftTensor Z, and evaluation against the state preserves this order. Consequently bndError ψ A.liftLeft (Z ⊗ I) = 0, so the boundedness statement holds at any nonnegative tolerance. The selfImprovement proof uses this constructor instead of requiring a combined boundedness-field hypothesis.