Cauchy–Schwarz display: when (Section 2.4)
ProvedExplicitExpanders.Attach.cauchy_schwarz_Rcauchy-schwarzexpander-graphsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite set, let be a set of further elements, and let be a real function on (disjoint union) with . Then
The equality holds because the two partial sums are negatives of each other, and the inequality is the Cauchy–Schwarz inequality. In the proof of Theorem 1.2 this shows that a unit vector orthogonal to the constant vector on has only a small component along the constant vector of the old vertex set , since .
Formalization Note The paper also uses to write ; the statement keeps the unnormalised form, from which that follows.
Preamble
import Mathlib
Formal statement
namespace ExplicitExpanders.Attach
/-- The Cauchy–Schwarz display (arXiv:2003.11673v1, §2.4, p. 9): for a real function `f` on
`U = V ⊕ R`, `R = Fin r`, with `∑_{u ∈ U} f(u) = 0`, one has
`|∑_{u∈V} f(u)|² = |∑_{u∈R} f(u)|² ≤ |R| ∑_{u∈R} f(u)²`. -/
theorem cauchy_schwarz_R {V : Type*} [Fintype V] {r : ℕ} (f : V ⊕ Fin r → ℝ)
(hf : ∑ u, f u = 0) :
(∑ v, f (Sum.inl v)) ^ 2 = (∑ i, f (Sum.inr i)) ^ 2 ∧
(∑ i, f (Sum.inr i)) ^ 2 ≤ (r : ℝ) * ∑ i, f (Sum.inr i) ^ 2 := by sorry
end ExplicitExpanders.Attach
Source
N. Alon, Explicit expanders of every degree and size, arXiv:2003.11673v1, p. 9, Section 2.4, unnumbered display after (2) ("By Cauchy-Schwarz ...")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.