Proof of Lemma 4, p. ec15 — with n_k = L_k² T/Σ L_i², Σ L_k √n_k = √((Σ L_k²)(Σ n_k)) = √(T Σ L_k²)
ProvedPigeonholeDesign.Lower.cauchy_schwarz_displaycauchy-schwarzinequalitieslower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be real numbers with , let be a natural number, and put
Then
The first equality is the equality case of the Cauchy–Schwarz inequality, since is proportional to ; the second holds because . In the proof of Lemma 4 this turns the per-pigeonhole bound into .
Formalization Note In the paper the are the lengths of the cells of a partition of ; the identity is stated for any nonnegative reals with positive sum of squares, which covers them. The are real numbers here, as in the display.
Preamble
import Mathlib import Definitions.Def_PigeonholeDesign_Lower_Setting
Formal statement
namespace PigeonholeDesign.Lower
theorem cauchy_schwarz_display {K : ℕ} (L : Fin K → ℝ) (T : ℕ) (hL : ∀ k, 0 ≤ L k)
(hS : 0 < ∑ i, L i ^ 2) :
∑ k, L k * Real.sqrt (L k ^ 2 / (∑ i, L i ^ 2) * T) =
Real.sqrt ((∑ k, L k ^ 2) * ∑ k, L k ^ 2 / (∑ i, L i ^ 2) * T) ∧
Real.sqrt ((∑ k, L k ^ 2) * ∑ k, L k ^ 2 / (∑ i, L i ^ 2) * T) =
Real.sqrt (T * ∑ k, L k ^ 2) := by sorry
end PigeonholeDesign.Lower
Source
Zhao and Zhou, Pigeonhole Design: Balancing Sequential Experiments from an Online Matching Perspective, arXiv:2201.12936v6, p. ec15, proof of Lemma 4 (Cauchy-Schwarz display)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.