Lemma 1 — attained LP representation of a fractional sorted sum
ProvedChenWasserstein.Reform.lemma_1Let , let be arbitrary real numbers, and let . Let denote the fractional sum of the smallest entries, counting ties with multiplicity. Then the following maximum is attained and equals that sum:
In particular, there exist feasible achieving the displayed value, and every feasible 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 , and 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 , and is not rounded away.
import Mathlib import Definitions.Def_ChenWasserstein_Reform_Data open scoped BigOperators
/- 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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. is a natural number, is an arbitrary real vector (entries may be negative), and is a real number.
Hypotheses. and .
Notation used in the conclusion.
- are the entries of sorted, with repeats kept.
- , which satisfies .
- is the fractional sum of the smallest entries:
- A pair with and is called feasible if and for every .
Conclusion.
- There is a feasible pair with
- Every feasible pair satisfies
So the maximum of over feasible pairs exists, is attained, and equals .
Degenerate cases:
- and . Both are excluded.
- , or more generally . Then and ; for this is .
- Edge cases of the floor. Because , the floor is never clamped and the fractional term is always present. Its coefficient is when is an integer.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.