Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 14, p. 12 — the error term beyond bucket N is at most δ1·Σ_{k=0}^N e^{−(k−1)σβ}·B_k + δ2·B_1

Proved
APrioriTSP.Sampling.lemma_14

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

a-priori-tspapproximation-algorithmslinear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1random-samplingstochastic-combinatorial-optimization

Let α≥0\alpha \ge 0α≥0, σ>0\sigma > 0σ>0, β>0\beta > 0β>0 and N∈NN \in \mathbb NN∈N, and let (Bi)i≥0(B_i)_{i\ge0}(Bi​)i≥0​ be nonnegative with Bi+j≤Bi+BjB_{i+j} \le B_i + B_jBi+j​≤Bi​+Bj​ for all i,j≥1i, j \ge 1i,j≥1. With

δ1=4βeNσβ(eσβ−1),δ2=(α+2βeNσβ(eσβ−1))⋅e−Nσβ(1−e−σβ)2⋅(1+N−e−σβN),\delta_1 = \frac{4\beta}{e^{N\sigma\beta}(e^{\sigma\beta}-1)},\qquad \delta_2 = \Big(\alpha + \frac{2\beta}{e^{N\sigma\beta}(e^{\sigma\beta}-1)}\Big)\cdot\frac{e^{-N\sigma\beta}}{(1-e^{-\sigma\beta})^2}\cdot(1 + N - e^{-\sigma\beta}N),δ1​=eNσβ(eσβ−1)4β​,δ2​=(α+eNσβ(eσβ−1)2β​)⋅(1−e−σβ)2e−Nσβ​⋅(1+N−e−σβN),

we have

α∑k=N+1∞e−(k−1)σβBk+2β∑i,j∈Z≥0max⁡{i,j}>Ne−(i+j−1)σβmin⁡{Bi,Bj}  ≤  δ1∑k=0Ne−(k−1)σβBk+δ2B1.\alpha\sum_{k=N+1}^\infty e^{-(k-1)\sigma\beta}B_k + 2\beta\sum_{\substack{i,j\in\mathbb Z_{\ge0}\\ \max\{i,j\}>N}} e^{-(i+j-1)\sigma\beta}\min\{B_i,B_j\} \;\le\; \delta_1\sum_{k=0}^N e^{-(k-1)\sigma\beta}B_k + \delta_2 B_1 .αk=N+1∑∞​e−(k−1)σβBk​+2βi,j∈Z≥0​max{i,j}>N​∑​e−(i+j−1)σβmin{Bi​,Bj​}≤δ1​k=0∑N​e−(k−1)σβBk​+δ2​B1​.

The lemma bounds the contribution of buckets beyond NNN to the bucket form (10) of the sampling constraint by terms in B0,…,BNB_0, \dots, B_NB0​,…,BN​ only, which is what makes (Sampling-LP) finite.

Formalization Note The first series is a tsum over k∈Nk \in \mathbb Nk∈N of terms that vanish for k≤Nk \le Nk≤N; the double series is a tsum over N×N\mathbb N \times \mathbb NN×N of terms that vanish when max⁡{i,j}≤N\max\{i,j\} \le Nmax{i,j}≤N. Under the hypotheses Bk≤kB1B_k \le kB_1Bk​≤kB1​ for k≥1k \ge 1k≥1, so both families are summable. Exponents are real: k=0k = 0k=0 gives eσβe^{\sigma\beta}eσβ.

Differences from the source:

  • reading: δ1 · Σ_{k=0}^N e^{−(k−1)·σβ} · B_i (the summand's index i is unbound) → δ1 · Σ_{k=0}^N e^{−(k−1)σβ} · B_k; reason: the only well-formed reading; it is the sum (11) and (13) use, and the proof's last line (p. 14) has the same sum with index and summand i
  • generalization: the buckets B of a feasible solution of (Sampling-OP) (B ≥ 0 and Proposition 12) → any sequence B ≥ 0 with B_{i+j} ≤ B_i + B_j for i, j ≥ 1; reason: the proof uses only these two properties, which the buckets of a feasible solution have
  • generalization: α ≥ 1, the approximation guarantee of the TSP algorithm of step (ii) (p. 4) → every real α ≥ 0; reason: (2) is a formula in α and the argument uses only α ≥ 0; at every α ≥ 1 the Lean statement is the paper's
  • generalization: σ = 0.663, fixed at the start of §2 (p. 7) → every σ > 0; reason: the proof uses only σβ > 0; σ = 0.663 is an instance
  • encoding: N an integer (the buckets B_0, …, B_N) → N ∈ ℕ; reason: N indexes the buckets kept, so N ≥ 0
  • encoding: the series over k ≥ N + 1 and over i, j ∈ ℤ_{≥0} with max{i, j} > N → tsums over ℕ and ℕ × ℕ of the terms multiplied by the indicator of the index range; reason: same sums; the families are nonnegative and summable since B_k ≤ k·B_1
Preamble
import Mathlib
import Definitions.Def_APrioriTSP_Sampling_Setting
import Definitions.Def_APrioriTSP_Sampling_LP
Formal statement
namespace APrioriTSP.Sampling

/-- Lemma 14 (p. 12): the error term beyond bucket `N` is bounded by
`δ₁ Σ_{k=0}^N e^{−(k−1)σβ} B_k + δ₂ B_1`. -/
theorem lemma_14 (α σ β : ℝ) (hα : 0 ≤ α) (hσ : 0 < σ) (hβ : 0 < β) (N : ℕ)
    (B : ℕ → ℝ) (hB0 : ∀ i, 0 ≤ B i)
    (hB : ∀ i j, 1 ≤ i → 1 ≤ j → B (i + j) ≤ B i + B j) :
    α * ∑' k : ℕ, (if N < k then Real.exp (-(((k : ℝ) - 1) * σ * β)) * B k else 0) +
        2 * β * ∑' q : ℕ × ℕ, (if N < max q.1 q.2 then
          Real.exp (-(((q.1 : ℝ) + q.2 - 1) * σ * β)) * min (B q.1) (B q.2) else 0) ≤
      delta1 β σ N * ∑ k ∈ Finset.range (N + 1), Real.exp (-(((k : ℝ) - 1) * σ * β)) * B k +
        delta2 α β σ N * B 1 := by sorry

end APrioriTSP.Sampling
Source
Blauth, Neuwohner, Puhlmann & Vygen, Improved guarantees for the a priori TSP, arXiv:2309.10663v1, p. 12, Lemma 14 (proof p. 14)
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

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