Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§4.1, proof of Theorem 7, p. 188 — ‖W − CUT(S,T,d)‖²_F − ‖W‖²_F = −|S||T|d² = −W(S,T)²/(|S||T|) for d = W(S,T)/(|S||T|)

Proved
FriezeKannan.CutDecomp.frobenius_drop

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

cut-decompositionenergy-incrementfrobenius-normp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let WWW be a real R×CR\times CR×C matrix and let S⊆RS\subseteq RS⊆R, T⊆CT\subseteq CT⊆C be nonempty. Put

d=W(S,T)∣S∣ ∣T∣,d=\frac{W(S,T)}{|S|\,|T|},d=∣S∣∣T∣W(S,T)​,

the average entry of WWW on the rectangle S×TS\times TS×T, and let D=CUT(S,T,d)D=\mathrm{CUT}(S,T,d)D=CUT(S,T,d). Then

∥W−D∥F2−∥W∥F2=∑i∈S, j∈T((W(i,j)−d)2−W(i,j)2)=−∣S∣ ∣T∣ d2=−W(S,T)2∣S∣ ∣T∣.\|W-D\|_F^2-\|W\|_F^2=\sum_{i\in S,\ j\in T}\big((W(i,j)-d)^2-W(i,j)^2\big)=-|S|\,|T|\,d^2=-\frac{W(S,T)^2}{|S|\,|T|}.∥W−D∥F2​−∥W∥F2​=i∈S, j∈T∑​((W(i,j)−d)2−W(i,j)2)=−∣S∣∣T∣d2=−∣S∣∣T∣W(S,T)2​.

Subtracting from WWW its average on a rectangle therefore lowers the squared Frobenius norm by exactly W(S,T)2/(∣S∣∣T∣)W(S,T)^2/(|S||T|)W(S,T)2/(∣S∣∣T∣). This is the energy-decrement computation that drives the existence proof of cut decompositions (Theorem 7).

Formalization Note SSS and TTT are assumed nonempty, as in the paper, where they come from a rectangle with W(S,T)≠0W(S,T)\ne 0W(S,T)=0; this keeps the division defining ddd meaningful. All three equalities of the display are stated.

Preamble
import Mathlib
import Definitions.Def_FriezeKannan_CutDecomp_Setting
Formal statement
namespace FriezeKannan.CutDecomp

/-- §4.1, proof of Theorem 7, p. 188: subtracting `CUT(S, T, d)` with
`d = W(S, T)/(|S||T|)` lowers `‖W‖²_F` by exactly `|S||T| d² = W(S, T)²/(|S||T|)`. -/
theorem frobenius_drop {R C : Type*} [Fintype R] [Fintype C] [DecidableEq R] [DecidableEq C]
    (W : Matrix R C ℝ) (S : Finset R) (T : Finset C) (hS : S.Nonempty) (hT : T.Nonempty) :
    let d : ℝ := blockSum W S T / ((S.card : ℝ) * T.card)
    (frobNorm (W - cutMatrix S T d) ^ 2 - frobNorm W ^ 2
        = ∑ i ∈ S, ∑ j ∈ T, ((W i j - d) ^ 2 - W i j ^ 2)) ∧
      (frobNorm (W - cutMatrix S T d) ^ 2 - frobNorm W ^ 2
        = -((S.card : ℝ) * T.card) * d ^ 2) ∧
      (frobNorm (W - cutMatrix S T d) ^ 2 - frobNorm W ^ 2
        = -(blockSum W S T) ^ 2 / ((S.card : ℝ) * T.card)) := by sorry

end FriezeKannan.CutDecomp
Source
Frieze and Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), p. 188, §4.1, proof of Theorem 7 (displayed computation of ‖W^(t+1)‖²_F − ‖W‖²_F)
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