Lemma 4.2 — interpolating distribution with the same moments, and
OpenQMomentMatch.FirstBound.Supplement.lemma_4_2moment-matchingp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let be integers and let be probability distributions on with matching moments through order :
Let . Then there is a probability distribution on with the same moments of orders such that
In the proof of Theorem 2.6, is the common endpoint of two linear paths from and along which every distribution has all its masses bounded below, as Lemma 4.1 requires.
Differences from the source:
- encoding: distributions on {0} ∪ [A] → probability vectors Fin (A + 1) → ℝ (base IsProbVec, moment); reason: base conventions
Preamble
import Mathlib import Definitions.Def_QMomentMatch_FirstBound_Basic
Formal statement
namespace QMomentMatch.FirstBound.Supplement
open QMomentMatch.FirstBound
/-- Lemma 4.2, p. 24 (proof p. 33), with `δ = ‖π_1 − π_0‖₁ = ∑_s |π_1(s) − π_0(s)|`. -/
theorem lemma_4_2 (A r : ℕ) (hr : 2 ≤ r) (hrA : r ≤ A) (π₀ π₁ : Fin (A + 1) → ℝ)
(h₀ : IsProbVec π₀) (h₁ : IsProbVec π₁) (hne : π₀ ≠ π₁)
(hmom : ∀ k : ℕ, 1 ≤ k → k ≤ r - 1 → moment π₀ k = moment π₁ k) :
∃ ω : Fin (A + 1) → ℝ, IsProbVec ω ∧
(∀ k : ℕ, 1 ≤ k → k ≤ r - 1 → moment ω k = moment π₀ k) ∧
(∀ s, (∑ t, |π₁ t - π₀ t|) / (32 : ℝ) ^ A ≤ ω s) ∧
∑ t, |ω t - π₀ t| ≤ ∑ t, |π₁ t - π₀ t| ∧
∑ t, |ω t - π₁ t| ≤ ∑ t, |π₁ t - π₀ t| := by sorry
end QMomentMatch.FirstBound.Supplement
Source
Chandrima Kayal, Frédéric Magniez, Sayantan Sen, Dániel Szabó, STOC 2027 submission #564 (October 2026), Lemma 4.2, p. 24 (proof p. 33)