Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1 — attained LP representation of a fractional sorted sum

Proved
ChenWasserstein.Reform.lemma_1

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

chance-constraintsoptimal-transportoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let N≥1N\ge1N≥1, let k1,…,kNk_1,\ldots,k_Nk1​,…,kN​ be arbitrary real numbers, and let 0<ε<10<\varepsilon<10<ε<1. Let Fk(εN)F_k(\varepsilon N)Fk​(εN) denote the fractional sum of the εN\varepsilon NεN smallest entries, counting ties with multiplicity. Then the following maximum is attained and equals that sum:

Fk(εN)=max⁡{εNt−∑i=1Nsi: t∈R, si≥0, t−si≤ki (1≤i≤N)}.F_k(\varepsilon N)=\max\left\{\varepsilon Nt-\sum_{i=1}^N s_i:\ t\in\mathbb R,\ s_i\ge0,\ t-s_i\le k_i\ (1\le i\le N)\right\}.Fk​(εN)=max{εNt−i=1∑N​si​: t∈R, si​≥0, t−si​≤ki​ (1≤i≤N)}.

In particular, there exist feasible s,ts,ts,t achieving the displayed value, and every feasible s′,t′s',t's′,t′ has objective at most that value.

This finite linear-program representation applies to arbitrary real arrays, and supplies the scalar threshold and slack variables in the deterministic chance-constraint reformulation.

Formalization Note No nonnegativity assumption is made on kik_iki​, and ttt is free. The maximum is expressed by an attaining pair and a universal upper bound, avoiding an unguarded real supremum. The fractional next entry is included when needed, including when εN<1\varepsilon N<1εN<1, and is not rounded away.

Preamble
import Mathlib
import Definitions.Def_ChenWasserstein_Reform_Data

open scoped BigOperators
Formal statement
/- Imported declaration bodies, quoted verbatim for standalone blind auditing.
These are comments, not redeclarations or additional assumptions.

noncomputable def kthSmallest {N : ℕ} (v : Fin N → ℝ) (j : ℕ) : ℝ :=
  ((Finset.univ.val.map v).sort (· ≤ ·)).getD j 0

noncomputable def fractionalSmallest {N : ℕ} (k : Fin N → ℝ) (ℓ : ℝ) : ℝ :=
  (∑ j ∈ Finset.range (min ⌊ℓ⌋₊ N), WassDRCCP.Improved.kthSmallest k j) +
    if ⌊ℓ⌋₊ < N then
      (ℓ - (⌊ℓ⌋₊ : ℝ)) * WassDRCCP.Improved.kthSmallest k ⌊ℓ⌋₊ else 0
-/

namespace ChenWasserstein.Reform

/-- Chen, Kuhn and Wiesemann (2024), Lemma 1, printed pp. 415–416 / PDF pp. 6–7.
The maximum is attained, and k may have negative entries. -/
theorem lemma_1 {N : ℕ} (k : Fin N → ℝ) (ε : ℝ)
    (hN : 0 < N) (hε : 0 < ε) (hε1 : ε < 1) :
    ∃ (s : Fin N → ℝ) (t : ℝ),
      (∀ i, 0 ≤ s i) ∧ (∀ i, t - s i ≤ k i) ∧
      ε * (N : ℝ) * t - ∑ i, s i = fractionalSmallest k (ε * (N : ℝ)) ∧
      ∀ (s' : Fin N → ℝ) (t' : ℝ),
        (∀ i, 0 ≤ s' i) → (∀ i, t' - s' i ≤ k i) →
        ε * (N : ℝ) * t' - ∑ i, s' i ≤ fractionalSmallest k (ε * (N : ℝ)) := by sorry

end ChenWasserstein.Reform
Source
Chen, Kuhn and Wiesemann, Technical Note—Data-Driven Chance Constrained Programs over Wasserstein Balls, Operations Research 72(1) (2024), 410–424, https://doi.org/10.1287/opre.2022.2330, Lemma 1, printed pp. 415–416, PDF pp. 6–7
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting. NNN is a natural number, k=(k0,…,kN−1)k=(k_0,\dots,k_{N-1})k=(k0​,…,kN−1​) is an arbitrary real vector (entries may be negative), and ε\varepsilonε is a real number.

Hypotheses. N>0N>0N>0 and 0<ε<10<\varepsilon<10<ε<1.

Notation used in the conclusion.

  • k(1)≤⋯≤k(N)k_{(1)}\le\dots\le k_{(N)}k(1)​≤⋯≤k(N)​ are the entries of kkk sorted, with repeats kept.
  • m=⌊εN⌋m=\lfloor\varepsilon N\rfloorm=⌊εN⌋, which satisfies 0≤m<N0\le m<N0≤m<N.
  • FFF is the fractional sum of the smallest entries:
F=∑j=1mk(j)+(εN−m) k(m+1).F=\sum_{j=1}^{m}k_{(j)}+(\varepsilon N-m)\,k_{(m+1)}.F=j=1∑m​k(j)​+(εN−m)k(m+1)​.
  • A pair (s,t)(s,t)(s,t) with s∈RNs\in\mathbb R^Ns∈RN and t∈Rt\in\mathbb Rt∈R is called feasible if si≥0s_i\ge0si​≥0 and t−si≤kit-s_i\le k_it−si​≤ki​ for every iii.

Conclusion.

  • There is a feasible pair (s,t)(s,t)(s,t) with
εN t−∑isi=F.\varepsilon N\,t-\sum_i s_i=F.εNt−i∑​si​=F.
  • Every feasible pair (s′,t′)(s',t')(s′,t′) satisfies
εN t′−∑isi′≤F.\varepsilon N\,t'-\sum_i s'_i\le F.εNt′−i∑​si′​≤F.

So the maximum of εN t−∑isi\varepsilon N\,t-\sum_i s_iεNt−∑i​si​ over feasible pairs exists, is attained, and equals FFF.

Degenerate cases:

  • N=0N=0N=0 and ε∉(0,1)\varepsilon\notin(0,1)ε∈/(0,1). Both are excluded.
  • N=1N=1N=1, or more generally εN<1\varepsilon N<1εN<1. Then m=0m=0m=0 and F=εN k(1)F=\varepsilon N\,k_{(1)}F=εNk(1)​; for N=1N=1N=1 this is F=εk0F=\varepsilon k_0F=εk0​.
  • Edge cases of the floor. Because 0<εN<N0<\varepsilon N<N0<εN<N, the floor is never clamped and the fractional term (εN−m)k(m+1)(\varepsilon N-m)k_{(m+1)}(εN−m)k(m+1)​ is always present. Its coefficient is 000 when εN\varepsilon NεN is an integer.
Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 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