Theorem 12, p. 217 — f = f₁ + ⋯ + f_s + w with s ≤ 1/ε² cut functions and ‖w‖_C ≤ ε‖f‖₂
ProvedFriezeKannan.Continuum.theorem_12Let be Lebesgue measurable with
and let . For measurable write , and let over measurable be the cut norm. A cut function is the function equal to on and elsewhere, for measurable and real .
Theorem 12. There exist cut functions with such that the error satisfies
This is the continuous analogue of the matrix cut decomposition (Theorem 7 of the paper), and the form of weak regularity used for graph limits: every square-integrable kernel on is, in cut norm, within of a sum of boundedly many rectangle step functions, the number depending on alone.
Formalization Note. is Mathlib's unitInterval with Lebesgue measure; (Lebesgue) measurable with is MemLp f 2, which includes almost-everywhere strong measurability, i.e. measurability for the completed Lebesgue measure; no Borel Measurable f is required. The cut norm bound is the supremum unfolded: for all measurable . The cut functions are indexed by and must have measurable sets. is the paper's implicit range of the error parameter (§2.3); for the bound is meaningless. The bound is what makes the theorem: without it the statement follows from density of step functions in .
import Mathlib import Definitions.Def_FriezeKannan_Continuum_Setting open MeasureTheory
namespace FriezeKannan.Continuum
theorem theorem_12 (f : Sq → ℝ) (hf : MemLp f 2)
(ε : ℝ) (hε : 0 < ε) :
∃ s : ℕ, (s : ℝ) ≤ 1 / ε ^ 2 ∧
∃ (Ss Ts : Fin s → Set unitInterval) (d : Fin s → ℝ),
(∀ t, MeasurableSet (Ss t) ∧ MeasurableSet (Ts t)) ∧
∀ S T : Set unitInterval, MeasurableSet S → MeasurableSet T →
|rectInt (fun p => f p - cutFunSum Ss Ts d p) S T| ≤ ε * l2Norm f := by sorry
end FriezeKannan.Continuum
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.