Lemma 7(a), p. 203 — if Q refines P and M is compatible with P, then sup|A(S,T) − A_Q(S,T)| ≤ 2 sup|A(S,T) − M(S,T)|
ProvedFriezeKannan.PseudoReg.lemma_7aLet be a finite set, and real matrices, a partition of , and a refinement of . If is compatible with , then
Here is the block average of over the blocks , and both suprema range over all pairs of subsets of (a finite family, so they are maxima).
The lemma says that, up to a factor 2 in the cut norm, block-averaging over any refinement of approximates as well as the best matrix that is constant on the blocks of .
Formalization Note. The inequality between suprema is stated in the equivalent form: for every real , if for all , then for all . In Section 5.1 is an adjacency matrix; the lemma uses nothing about it and is stated for every real matrix . " refines " is Mathlib's order on Finpartition (: every part of lies in a part of ).
import Mathlib import Definitions.Def_FriezeKannan_PseudoReg_Setting
namespace FriezeKannan.PseudoReg
theorem lemma_7a {V : Type*} [Fintype V] [DecidableEq V]
(A M : Matrix V V ℝ) (P Q : Finpartition (Finset.univ : Finset V)) (hQP : Q ≤ P)
(hM : Compatible P M) (c : ℝ)
(hc : ∀ S T : Finset V, |blockSum (A - M) S T| ≤ c) :
∀ S T : Finset V, |blockSum (A - blockAvg Q A) S T| ≤ 2 * c := by sorry
end FriezeKannan.PseudoReg
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.