Lemma 3.9 — scalar contraction
ProvedRandMatDisc.lemma_3_9discrepancyp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrandom-matrix-theoryrandomized-algorithms
For every there is with the following property. If is a non-negative sequence with
then for all , and for all .
Applied to , it shows that rounds bring the residual of the algorithm down to order .
Differences from the source: none.
Preamble
import Mathlib
Formal statement
namespace RandMatDisc
/-- **Lemma 3.9 (Scalar contraction)**, Kızıldağ, Li, arXiv:2610.01591 (held file sha256
889af7fc…), p.21 (PDF p.23).
For every `C > 0` there is `A ∈ [1, ∞)` such that every non-negative sequence `(y_k)_{k ≥ 0}`
with `y_{k+1} ≤ C(√y_k + 1)` (37) satisfies `y_k ≤ A` for all `k ≥ ⌈log₂(max{y₀, 1})⌉`, and
`y_k ≤ max{y₀, A}` for all `k`.
**Formalization Note.** `⌈log₂ ·⌉` is `Nat.ceil (Real.logb 2 ·)`; its argument is at least `1`,
so the logarithm is non-negative. -/
theorem lemma_3_9 :
∀ C : ℝ, 0 < C → ∃ A : ℝ, 1 ≤ A ∧ ∀ y : ℕ → ℝ, (∀ k, 0 ≤ y k) →
(∀ k, y (k + 1) ≤ C * (Real.sqrt (y k) + 1)) →
(∀ k : ℕ, ⌈Real.logb 2 (max (y 0) 1)⌉₊ ≤ k → y k ≤ A) ∧
(∀ k, y k ≤ max (y 0) A) := by sorry
end RandMatDisc
Source
Kızıldağ, Li, Stable and Online Algorithms for Random Matrix Discrepancy, arXiv:2610.01591 (held file sha256 889af7fc…), Lemma 3.9, p.21 (PDF p.23), eq. (37)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.