balanced_multipartite_nearest_spectral_distance_nonneg
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
- balanced_multipartite_nearest_spectral_distanceFor natural numbers r and n, balanced_multipartite_nearest_spectral_distance r n = c_r(n) is the infimum in ℝ (a minimum over a finite set…
- balanced_complete_multipartite_graphFor natural numbers r and n, balanced_complete_multipartite_graph r n is the simple graph on Fin (r * n) in which u and v are adjacent…
- spectral_distance_l2_sqThe squared Euclidean spectral distance between two eigenvalue sequences of length m is the sum of the squared differences of their…
- simple_graph_adj_eigenvalues_sortedFor a type V with [Fintype V] and [DecidableEq V] (implicit V) and a simple graph G : SimpleGraph V, simple_graph_adj_eigenvalues_sorted G…
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.
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.
uses
Real.sInf_nonnegapply Real.sInf_nonnegEvery 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.
uses
Finset.sum_nonneg,sq_nonnegrintro 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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 _)