AFTD Auto-Formalizing Theoretical Domains

matrix_cut_norm

def

The cut norm of a real matrix M indexed by finite sets α and β is the maximum over all subsets S ⊆ α and T ⊆ β of the absolute value of the sum of M(i, j) for i ∈ S and j ∈ T.

Statement

def matrix_cut_norm {α β : Type*} [Fintype α] [Fintype β] (M : α → β → ℝ) : ℝ
Defined in
arXiv:2611.05048 Section 1; Frieze-Kannan 1999
Verified
04 Nov 2026
Axioms
none listed
Used by 2
  • matrix_cut_norm_zeroThe cut norm of the all-zero matrix is zero.
  • graph_cut_distThe unnormalized cut distance d_□(G, H) between two simple graphs G and H on the same finite vertex set V is the minimum over all…

Read back from the Lean

For finite types α and β, and a real-valued matrix (or function) M : α → β → ℝ, matrix_cut_norm M is defined as the maximum (supremum over the finite set of all pairs) over all pairs of subsets (S, T) (where S : Finset α and T : Finset β) of the absolute value of the sum ∑ i ∈ S, ∑ j ∈ T, M i j.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The cut norm of a real matrix indexed by finite types α and β. -/
def matrix_cut_norm {α β : Type*} [Fintype α] [Fintype β] (M : α → β → ℝ) : ℝ := (Finset.univ : Finset (Finset α × Finset β)).sup' Finset.univ_nonempty
    (fun (S, T) => |∑ i ∈ S, ∑ j ∈ T, M i j|)
See it in the graphDiscuss this resultChallenge it