AFTD Auto-Formalizing Theoretical Domains

balanced_multipartite_nearest_spectral_distance

deforiginal

For 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 when some H exists) of d_2^2(T, H) = Σ_i (λ_i(T) − λ_i(H))² over all simple graphs H on Fin (r * n) not isomorphic to T = balanced_complete_multipartite_graph r n, with λ the adjacency eigenvalues sorted nonincreasingly (spectral_distance_l2_sq of simple_graph_adj_eigenvalues_sorted).

Statement

noncomputable def balanced_multipartite_nearest_spectral_distance (r n : ℕ) : ℝ
Related work
Open problem OP-546 (posed in this knowledge base). arXiv:2610.18636 shows that a rank-four graph H_{3,n} beats the conjectured complete-tripartite nearest competitor of K_{n,n,n}, at squared spectral distance tending to 1/2 = 2((3-2)/(3-1))^2. It gives upper bounds on the unrestricted nearest distance and an asymptotic classification among complete multipartite competitors only. The unrestricted limit for r >= 4 is open; experiments 6265 and 6273 support the value 2((r-2)/(r-1))^2.
Verified
27 Oct 2026
Axioms
none listed
Built on 3
  • 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…
  • 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…
  • spectral_distance_l2_sqThe squared Euclidean spectral distance between two eigenvalue sequences of length m is the sum of the squared differences of their…
Used by 1

Read back from the Lean

For natural numbers $r$ and $n$, balanced_multipartite_nearest_spectral_distance r n is defined as the infimum (sInf) of the set of all real numbers $d$ for which there exists a simple graph $H$ on the vertex set $\mathrm{Fin}(r \cdot n)$ such that $H$ is not isomorphic to balanced_complete_multipartite_graph r n, and $d$ is equal to the squared $\ell_2$ distance between the sorted adjacency matrix eigenvalues of balanced_complete_multipartite_graph r n and the sorted adjacency matrix eigenvalues of $H$.

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

noncomputable def balanced_multipartite_nearest_spectral_distance (r n : ℕ) : ℝ := sInf {d : ℝ | ∃ H : SimpleGraph (Fin (r * n)), ¬ Nonempty (balanced_complete_multipartite_graph r n ≃g H) ∧ d = spectral_distance_l2_sq (simple_graph_adj_eigenvalues_sorted (balanced_complete_multipartite_graph r n)) (simple_graph_adj_eigenvalues_sorted H)}
See it in the graphDiscuss this resultChallenge it