Lemma 6.2 — a finite affine cover of a compact convex set has a positive nonnegative combination
ProvedOnlineCarpoolingLei.Oblivious.positive_affine_combinationconvex-analysisdiscrepancyp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a nonempty compact convex set and let be affine functions. Suppose that
Then there exist such that
The weights are only required to be nonnegative; they need not sum to one. This finite separation lemma lets the proof of Theorem 3.3 combine finitely many test functions into one. If the hypothesis forces , which is excluded.
Differences from the source:
- encoding: →
Fin N → ℝ; reason: same vector space, topology and convex structure
Preamble
import Mathlib
Formal statement
namespace OnlineCarpoolingLei.Oblivious
/-- Lemma 6.2 (p.12). Let `B ⊂ ℝ^N` be nonempty, compact and convex, and `ϕ₁, …, ϕ_m` affine
functions on `ℝ^N` with `B = ⋃ᵢ {p ∈ B : ϕᵢ(p) > 0}`. Then there are `λ₁, …, λ_m ≥ 0` with
`∑ᵢ λᵢ ϕᵢ(p) > 0` for every `p ∈ B`. -/
theorem positive_affine_combination {N m : ℕ} (B : Set (Fin N → ℝ)) (hB_ne : B.Nonempty)
(hB_compact : IsCompact B) (hB_convex : Convex ℝ B)
(ϕ : Fin m → (Fin N → ℝ) →ᵃ[ℝ] ℝ)
(hcover : B = ⋃ i, {p | p ∈ B ∧ 0 < ϕ i p}) :
∃ lam : Fin m → ℝ, (∀ i, 0 ≤ lam i) ∧ ∀ p ∈ B, 0 < ∑ i, lam i * ϕ i p := by sorry
end OnlineCarpoolingLei.Oblivious
Source
Yuhao Lei, STOC 2027 submission #416 (October 2026), Lemma 6.2, p.12 (PDF p.12)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.