Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§8, proof of Theorem 12, p. 217 — if ‖w_t‖²₂ ≤ (1 − ε²t)‖f‖²₂ then (63) holds or one more cut function gives ‖w_{t+1}‖²₂ ≤ (1 − ε²(t+1))‖f‖²₂

Proved
FriezeKannan.Continuum.inductive_step

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

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

Let fff be a measurable real function on [0,1]2[0,1]^2[0,1]2 with ∥f∥2<∞\|f\|_2<\infty∥f∥2​<∞, and let ϵ>0\epsilon>0ϵ>0. Suppose fj=CUT(Sj,Tj,dj)f_j=\mathrm{CUT}(S_j,T_j,d_j)fj​=CUT(Sj​,Tj​,dj​), 1≤j≤t1\le j\le t1≤j≤t, are cut functions with measurable Sj,Tj⊆[0,1]S_j,T_j\subseteq[0,1]Sj​,Tj​⊆[0,1], and that the error wt=f−(f1+⋯+ft)w_t=f-(f_1+\dots+f_t)wt​=f−(f1​+⋯+ft​) satisfies

∥wt∥22≤(1−ϵ2t) ∥f∥22.\|w_t\|_2^2\le(1-\epsilon^2 t)\,\|f\|_2^2 .∥wt​∥22​≤(1−ϵ2t)∥f∥22​.

Then one of the following holds:

  1. ∣wt(S,T)∣≤ϵ∥f∥2|w_t(S,T)|\le\epsilon\|f\|_2∣wt​(S,T)∣≤ϵ∥f∥2​ for all measurable S,T⊆[0,1]S,T\subseteq[0,1]S,T⊆[0,1], i.e. ∥wt∥C≤ϵ∥f∥2\|w_t\|_C\le\epsilon\|f\|_2∥wt​∥C​≤ϵ∥f∥2​ (inequality (63) with s=ts=ts=t);
  2. there are measurable S,T⊆[0,1]S,T\subseteq[0,1]S,T⊆[0,1] and a real ddd such that
∥wt−CUT(S,T,d)∥22≤(1−ϵ2(t+1)) ∥f∥22.\|w_t-\mathrm{CUT}(S,T,d)\|_2^2\le\big(1-\epsilon^2(t+1)\big)\,\|f\|_2^2 .∥wt​−CUT(S,T,d)∥22​≤(1−ϵ2(t+1))∥f∥22​.

This is the induction of the proof of Theorem 12: as long as the cut norm of the error exceeds ϵ∥f∥2\epsilon\|f\|_2ϵ∥f∥2​, one more cut function preserves the invariant with ttt replaced by t+1t+1t+1.

Formalization Note. The family of cut functions is indexed by {0,…,t−1}\{0,\dots,t-1\}{0,…,t−1} (the page's f0=0f_0=0f0​=0 is the empty sum). The cut norm bound is the definition ∥w∥C=sup⁡S,T∣w(S,T)∣\|w\|_C=\sup_{S,T}|w(S,T)|∥w∥C​=supS,T​∣w(S,T)∣ unfolded over measurable S,TS,TS,T. ϵ>0\epsilon>0ϵ>0 is the paper's implicit range. "fff measurable with ∥f∥2<∞\|f\|_2<\infty∥f∥2​<∞" is MemLp f 2 (which includes almost-everywhere measurability, i.e. Lebesgue measurability).

Preamble
import Mathlib
import Definitions.Def_FriezeKannan_Continuum_Setting

open MeasureTheory
Formal statement
namespace FriezeKannan.Continuum

theorem inductive_step (f : Sq → ℝ) (hf : MemLp f 2)
    (ε : ℝ) (hε : 0 < ε)
    (t : ℕ) (Ss Ts : Fin t → Set unitInterval) (d : Fin t → ℝ)
    (hmS : ∀ j, MeasurableSet (Ss j) ∧ MeasurableSet (Ts j))
    (hinv : l2Norm (fun p => f p - cutFunSum Ss Ts d p) ^ 2
      ≤ (1 - ε ^ 2 * t) * l2Norm f ^ 2) :
    (∀ S T : Set unitInterval, MeasurableSet S → MeasurableSet T →
        |rectInt (fun p => f p - cutFunSum Ss Ts d p) S T| ≤ ε * l2Norm f) ∨
    ∃ (S T : Set unitInterval) (d' : ℝ), MeasurableSet S ∧ MeasurableSet T ∧
      l2Norm (fun p => f p - cutFunSum Ss Ts d p - cutFun S T d' p) ^ 2
        ≤ (1 - ε ^ 2 * (t + 1)) * l2Norm f ^ 2 := 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 (inductive hypothesis and the case split)
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