§8, proof of Theorem 12, p. 217 — ‖w − CUT(S,T,d)‖²₂ − ‖w‖²₂ = −|S||T|d² = −w(S,T)²/(|S||T|) for d = w(S,T)/(|S||T|)
ProvedFriezeKannan.Continuum.l2_dropcut-decompositionl2-spacep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1weak-regularity
Let be a square-integrable real function on , and let be measurable sets with , where is the Lebesgue measure of . Put
and let be with the cut function of value on subtracted. Then
This is the computation at the heart of the proof of Theorem 12: subtracting the best constant on a rectangle lowers the squared norm by exactly .
Formalization Note. is not written on the page, where it follows from ; it is assumed here because divides by . Square integrability of (Mathlib's MemLp w 2) is the page's standing assumption ; without it Lean's integrals default to .
Preamble
import Mathlib import Definitions.Def_FriezeKannan_Continuum_Setting open MeasureTheory
Formal statement
namespace FriezeKannan.Continuum
theorem l2_drop (w : Sq → ℝ) (hw : MemLp w 2) (S T : Set unitInterval)
(hS : MeasurableSet S) (hT : MeasurableSet T)
(hpos : 0 < (volume S).toReal * (volume T).toReal) :
let d := rectInt w S T / ((volume S).toReal * (volume T).toReal)
(l2Norm (fun p => w p - cutFun S T d p) ^ 2 - l2Norm w ^ 2
= ∫ p in S ×ˢ T, ((w p - d) ^ 2 - w p ^ 2)) ∧
(l2Norm (fun p => w p - cutFun S T d p) ^ 2 - l2Norm w ^ 2
= -((volume S).toReal * (volume T).toReal) * d ^ 2) ∧
(l2Norm (fun p => w p - cutFun S T d p) ^ 2 - l2Norm w ^ 2
= -(rectInt w S T) ^ 2 / ((volume S).toReal * (volume T).toReal)) := by sorry
end FriezeKannan.Continuum
Source
Frieze and Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), p. 217, §8, proof of Theorem 12 (the three equalities of the displayed computation)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.