AFTD Auto-Formalizing Theoretical Domains

balanced_multipartite_nearest_spectral_distance_nonneg

theoremverified

The nearest squared spectral distance c_r(n) is nonnegative.

Statement

theorem balanced_multipartite_nearest_spectral_distance_nonneg (r n : ℕ) :
    0 ≤ balanced_multipartite_nearest_spectral_distance r n
Source
sanity lemma for balanced_multipartite_nearest_spectral_distance (OP-546)
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The nearest squared spectral distance is defined as the infimum of squared ℓ² spectral distances between the balanced complete multipartite graph and all non-isomorphic graphs on the same vertices. The proof reduces nonnegativity of the infimum to nonnegativity of every element in the set. Since each element is an ℓ² spectral distance defined as a sum of squared eigenvalue differences, it is nonnegative as a sum of squares of real numbers.

  1. It suffices to show that every squared spectral distance in the defining set is nonnegative.

    The nearest squared spectral distance is defined as the infimum of the set of squared spectral distances between the balanced complete multipartite graph and non-isomorphic graphs. By Real.sInf_nonneg, the infimum of a set of real numbers is nonnegative whenever every element in the set is nonnegative.

    line 3

    uses Real.sInf_nonneg

      apply Real.sInf_nonneg
  2. Every squared spectral distance in the set is nonnegative.

    Any element in the set is the squared distance between the sorted eigenvalue vectors of the balanced complete multipartite graph and some graph H. By definition of spectral_distance_l2_sq, this distance is the sum over all coordinates of the squared differences of their eigenvalues, ∑ i, (s₁(i) - s₂(i))². Since the square of every difference is nonnegative by sq_nonneg, the sum over the finite index set is nonnegative by Finset.sum_nonneg.

    lines 4–6

    uses Finset.sum_nonneg, sq_nonneg

      rintro d ⟨H, -, rfl⟩
      unfold spectral_distance_l2_sq
      exact Finset.sum_nonneg (fun i _ => sq_nonneg _)
Real.sInf_nonneg
The infimum of a set of real numbers is nonnegative if every element in the set is nonnegative.
Finset.sum_nonneg
A finite sum of nonnegative terms is nonnegative.
sq_nonneg
The square of any real number (or element of an ordered semiring) is nonnegative.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem balanced_multipartite_nearest_spectral_distance_nonneg (r n : ℕ) :    0 ≤ balanced_multipartite_nearest_spectral_distance r n := by  apply Real.sInf_nonneg  rintro d ⟨H, -, rfl⟩  unfold spectral_distance_l2_sq  exact Finset.sum_nonneg (fun i _ => sq_nonneg _)
See it in the graphDiscuss this resultChallenge it