Ld Dnoteq
ProvedLIDT.MIPStarRE.LDT.Pasting.ldDnoteqThe distinct-height distribution is close to the uniform tuple distribution.
Let params be LIDT parameters and let . Let be the uniform distribution on all tuples of field elements, and let be the uniform distribution on injective tuples, so no two selected slice heights coincide. Their total variation distance satisfies
The estimate remains valid when , where the distinct-tuple support is empty and the right-hand side is already large enough. It quantifies the loss incurred when an average over all tuples is replaced by the distribution required for interpolation. The bound is used in the H-B consistency aggregation, the eligible-mass estimate, and the final pasted-submeasurement expansion 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.Pasting.ldDnoteq; its Lean statement gives the exact quantifier order and all boundary hypotheses.
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_DistributionUniformSums import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LinePolynomialEmbedding import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LinePolynomials import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LowDegreePolynomial import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_MeasurementLift 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_CommutativityPoints_Approximation import Definitions.Def_LIDT_MIPStarRE_LDT_CommutativityPoints_Defs import Definitions.Def_LIDT_MIPStarRE_LDT_Commutativity_Defs_Core import Definitions.Def_LIDT_MIPStarRE_LDT_Commutativity_Defs_Normalization import Definitions.Def_LIDT_MIPStarRE_LDT_Commutativity_Defs_Stability import Definitions.Def_LIDT_MIPStarRE_LDT_Commutativity_Scaffold_Core import Definitions.Def_LIDT_MIPStarRE_LDT_ExpansionHypercubeGraph_Defs_Core import Definitions.Def_LIDT_MIPStarRE_LDT_GlobalVariance_Defs_Core import Definitions.Def_LIDT_MIPStarRE_LDT_MainInductionStep_Defs import Definitions.Def_LIDT_MIPStarRE_LDT_MakingMeasurementsProjective_Defs import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Defs_Families import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Defs_Interpolation import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Defs_Tuples import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Sandwich_GHatSandwich import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Sandwich_PastedFamilies import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Sandwich_Switcheroo import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Statements import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_ComparisonCore import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_Defs import Definitions.Def_LIDT_MIPStarRE_LDT_Tactic_QuantumNonneg 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 Definitions.Def_LIDT_MIPStarRE_Quantum_Measurement import Mathlib import Mathlib.Analysis.MeanInequalitiesPow import Mathlib.Probability.ProbabilityMassFunction.Integrals import Mathlib.Probability.ProbabilityMassFunction.Monad namespace LIDT.MIPStarRE.LDT end LIDT.MIPStarRE.LDT namespace LIDT.MIPStarRE.LDT.Pasting end LIDT.MIPStarRE.LDT.Pasting open LIDT /-! # Section 12 pasting: distinct tuple distribution bound The total variation distance between the uniform distribution on all point tuples and the distribution restricted to distinct tuples. -/ @[expose] public section open LIDT.MIPStarRE.LDT.Pasting open MIPStarRE.LDT open scoped BigOperators
theorem LIDT.MIPStarRE.LDT.Pasting.ldDnoteq
(params : _root_.LIDT.MIPStarRE.LDT.Parameters) (k : ℕ) :
_root_.LIDT.MIPStarRE.LDT.totalVariationDistance (_root_.LIDT.MIPStarRE.LDT.uniformDistribution (_root_.LIDT.MIPStarRE.LDT.PointTuple params k))
(_root_.LIDT.MIPStarRE.LDT.Pasting.distinctTupleDistribution params k)
≤ ((k : _root_.LIDT.MIPStarRE.LDT.Error) ^ (2 : ℕ)) / (params.q : _root_.LIDT.MIPStarRE.LDT.Error) := by sorry