Lemma 7.2 — subset of powers of two with prescribed sum
ProvedWeightedMajority.Shattered.lemma_7_2arithmeticonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1weighted-majority
Let be positive powers of two with integer exponents, and let . If every and , then a subset has exactly the target weight:
The lemma extracts a prescribed weight from a collection of dyadic weights.
Formalization Note Each hypothesis is represented as for an integer . The upper bound on each weight expresses the source's maximum condition without taking a maximum of an empty family; when , the total-weight condition is impossible.
Preamble
import Mathlib
Formal statement
namespace WeightedMajority.Shattered
/-- Littlestone--Warmuth, Lemma 7.2, p. 244. `r i = 2 ^ k i` encodes
the assertion that `log₂ (r i)` is an integer. -/
theorem lemma_7_2 {j : ℕ} (r : Fin j → ℝ) (k : Fin j → ℤ)
(hr : ∀ i, r i = (2 : ℝ) ^ (k i)) (l : ℤ)
(hmax : ∀ i, r i ≤ (2 : ℝ) ^ l)
(hsum : (2 : ℝ) ^ l ≤ ∑ i, r i) :
∃ K : Finset (Fin j), ∑ i ∈ K, r i = (2 : ℝ) ^ l := by sorry
end WeightedMajority.Shattered
Source
Littlestone and Warmuth, The Weighted Majority Algorithm, Information and Computation 108 (1994), p. 244, Lemma 7.2; https://doi.org/10.1006/inco.1994.1009
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.