Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 12, p. 217 — f = f₁ + ⋯ + f_s + w with s ≤ 1/ε² cut functions and ‖w‖_C ≤ ε‖f‖₂

Proved
FriezeKannan.Continuum.theorem_12

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

cut-decompositioncut-norml2-spacep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1weak-regularity

Let f:[0,1]2→Rf:[0,1]^2\to\mathbb Rf:[0,1]2→R be Lebesgue measurable with

∥f∥22=∫[0,1]2f(x,y)2 dx dy<∞,\|f\|_2^2=\int_{[0,1]^2}f(x,y)^2\,dx\,dy<\infty,∥f∥22​=∫[0,1]2​f(x,y)2dxdy<∞,

and let ϵ>0\epsilon>0ϵ>0. For measurable S,T⊆[0,1]S,T\subseteq[0,1]S,T⊆[0,1] write g(S,T)=∫S×Tg(x,y) dx dyg(S,T)=\int_{S\times T}g(x,y)\,dx\,dyg(S,T)=∫S×T​g(x,y)dxdy, and let ∥g∥C=sup⁡S,T∣g(S,T)∣\|g\|_C=\sup_{S,T}|g(S,T)|∥g∥C​=supS,T​∣g(S,T)∣ over measurable S,TS,TS,T be the cut norm. A cut function CUT(S,T,d)\mathrm{CUT}(S,T,d)CUT(S,T,d) is the function equal to ddd on S×TS\times TS×T and 000 elsewhere, for measurable S,TS,TS,T and real ddd.

Theorem 12. There exist cut functions f1,…,fsf_1,\dots,f_sf1​,…,fs​ with s≤1/ϵ2s\le 1/\epsilon^2s≤1/ϵ2 such that the error ws=f−(f1+⋯+fs)w_s=f-(f_1+\dots+f_s)ws​=f−(f1​+⋯+fs​) satisfies

∥ws∥C≤ϵ∥f∥2.(63)\|w_s\|_C\le\epsilon\|f\|_2. \tag{63}∥ws​∥C​≤ϵ∥f∥2​.(63)

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 [0,1]2[0,1]^2[0,1]2 is, in cut norm, within ϵ∥f∥2\epsilon\|f\|_2ϵ∥f∥2​ of a sum of boundedly many rectangle step functions, the number depending on ϵ\epsilonϵ alone.

Formalization Note. [0,1][0,1][0,1] is Mathlib's unitInterval with Lebesgue measure; fff (Lebesgue) measurable with ∥f∥2<∞\|f\|_2<\infty∥f∥2​<∞ 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: ∣ws(S,T)∣≤ϵ∥f∥2|w_s(S,T)|\le\epsilon\|f\|_2∣ws​(S,T)∣≤ϵ∥f∥2​ for all measurable S,TS,TS,T. The cut functions are indexed by {0,…,s−1}\{0,\dots,s-1\}{0,…,s−1} and must have measurable sets. ϵ>0\epsilon>0ϵ>0 is the paper's implicit range of the error parameter (§2.3); for ϵ≤0\epsilon\le0ϵ≤0 the bound s≤1/ϵ2s\le1/\epsilon^2s≤1/ϵ2 is meaningless. The bound s≤1/ϵ2s\le1/\epsilon^2s≤1/ϵ2 is what makes the theorem: without it the statement follows from density of step functions in L2L^2L2.

Preamble
import Mathlib
import Definitions.Def_FriezeKannan_Continuum_Setting

open MeasureTheory
Formal statement
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
Source
Frieze and Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), p. 217, Theorem 12 and (63)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me