Lemma 7.1 — a prefix realizes an integral target sum
ProvedWeightedMajority.Shattered.lemma_7_1arithmeticonline-learningp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1weighted-majority
Let be positive real numbers, where , such that each adjacent quotient is an integer. If , , and is an integer, then some prefix of the list has sum exactly :
This arithmetic lemma is used to select an exact weight total in the next lemma.
Formalization Note Lean numbers the entries from zero, so is r 0. The explicit makes the source's well-defined.
Preamble
import Mathlib
Formal statement
namespace WeightedMajority.Shattered
/-- Littlestone--Warmuth, Lemma 7.1, p. 244. The book's indices 1,...,n are
represented by `Fin n`, starting at zero. -/
theorem lemma_7_1 {n : ℕ} (hn : 0 < n) (r : Fin n → ℝ)
(hr : ∀ i, 0 < r i)
(hquot : ∀ i j : Fin n, (j : ℕ) = (i : ℕ) + 1 →
∃ k : ℤ, r i / r j = (k : ℝ))
(s : ℝ) (hspos : 0 < s) (hsle : s ≤ ∑ i, r i)
(hsint : ∃ k : ℤ, s / r ⟨0, hn⟩ = (k : ℝ)) :
∃ m : ℕ, m ≤ n ∧ ∑ i ∈ Finset.univ.filter (fun i : Fin n => (i : ℕ) < m), r i = s := by sorry
end WeightedMajority.Shattered
Source
Littlestone and Warmuth, The Weighted Majority Algorithm, Information and Computation 108 (1994), p. 244, Lemma 7.1; https://doi.org/10.1006/inco.1994.1009
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.