spectral_distances_knnn_hn_eigenvalues
Let n >= 2 and let l1, l2, l3 be real numbers such that l1 + l2 + l3 = n, l1 < 2 * n, 0 < l2, and -n < l3. Let Lam = 2 * n - l1. Then 0 < Lam, the Manhattan spectral distance spectral_distance_l1 between knnn_eigenvalues n and hn_eigenvalues n l1 l2 l3 equals 2 * Lam, and the squared Euclidean spectral distance spectral_distance_l2_sq equals 2 * (Lam ^ 2 - Lam * l2 + l2 ^ 2).
Statement
theorem spectral_distances_knnn_hn_eigenvalues (n : ℕ) (hle : 2 ≤ n) (l1 l2 l3 : ℝ) (hsum : l1 + l2 + l3 = (n : ℝ)) (hl1 : l1 < 2 * (n : ℝ)) (hl2 : 0 < l2) (hl3 : -(n : ℝ) < l3) : let Lam := 2 * (n : ℝ) - l1 0 < Lam ∧ spectral_distance_l1 (knnn_eigenvalues n) (hn_eigenvalues n l1 l2 l3) = 2 * Lam ∧ spectral_distance_l2_sq (knnn_eigenvalues n) (hn_eigenvalues n l1 l2 l3) = 2 * (Lam ^ 2 - Lam * l2 + l2 ^ 2)
- Formalizes
- arXiv:2610.18636 Theorem 5
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- knnn_eigenvaluesFor a natural number n, knnn_eigenvalues n is the function on Fin (3 * n) defined by: 2 * (n : ℝ) at index 0, 0 at indices strictly…
- hn_eigenvaluesFor a natural number n and real numbers l1, l2, l3, hn_eigenvalues n l1 l2 l3 is the function on Fin (3 * n) defined by: l1 at index 0, l2…
- hn_eigenvalue_shift_identityFor any natural number n and real numbers l1, l2, l3, if l1 + l2 + l3 = n and Lam = 2 * (n : ℝ) - l1, then (n : ℝ) + l3 = Lam - l2.
- spectral_distance_l1The Manhattan spectral distance between two eigenvalue sequences of length m is the sum of the absolute differences of their coordinates.
- spectral_distance_l2_sqThe squared Euclidean spectral distance between two eigenvalue sequences of length m is the sum of the squared differences of their…
Read back from the Lean
For every natural number $n$ such that $2 ≤ n$, and for all real numbers $l_1, l_2, l_3$ satisfying:
1. $l_1 + l_2 + l_3 = n$,
2. $l_1 < 2n$,
3. $0 < l_2$, and
4. $-n < l_3$,
letting $\text{Lam} = 2n - l_1$, the following three conditions hold simultaneously:
1. $0 < \text{Lam}$,
2. The $\ell_1$ spectral distance spectral_distance_l1 between knnn_eigenvalues n and hn_eigenvalues n l1 l2 l3 equals $2 \cdot \text{Lam}$,
3. The squared $\ell_2$ spectral distance spectral_distance_l2_sq between knnn_eigenvalues n and hn_eigenvalues n l1 l2 l3 equals $2(\text{Lam}^2 - \text{Lam} \cdot l_2 + l_2^2)$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To compute the Manhattan and squared Euclidean spectral distances between knnn_eigenvalues and hn_eigenvalues, the proof first observes that the two eigenvalue spectra coincide everywhere on Fin (3 * n) except at three indices: 0, 1, and 3 * n - 2. At these three points, the differences are Lam, -l2, and -(Lam - l2). Using an auxiliary lemma that reduces sums of functions supported on three points to a three-term sum, the L1 distance sums the absolute values Lam + l2 + (Lam - l2) = 2 * Lam, and the squared L2 distance sums the squares Lam ^ 2 + l2 ^ 2 + (Lam - l2) ^ 2 = 2 * (Lam ^ 2 - Lam * l2 + l2 ^ 2).
The sum of f over the universe equals the sum of f over {a, b, c}.
Since {a, b, c} is a subset of the universe and f vanishes on all elements outside {a, b, c} by hypothesis, the sum over the universe restricts to the sum over {a, b, c} by sum_subset.
uses
subset_univ,sum_subset,mem_insert,mem_singleton,not_orhave hsub : ({a, b, c} : Finset (Fin m)) ⊆ univ := subset_univ _ have h_eq : ∑ x, f x = ∑ x ∈ ({a, b, c} : Finset (Fin m)), f x := by apply (sum_subset hsub _).symm intro x _ hx simp only [mem_insert, mem_singleton, not_or] at hx exact h_zero x hx.1 hx.2.1 hx.2.2 rw [h_eq]
The sum of f over {a, b, c} equals f a + f b + f c.
Because b ≠ c and a is distinct from both b and c, sum_insert and sum_singleton unpack the sum over {a, b, c} into f a + f b + f c.
uses
sum_insert,sum_singleton,add_assochave hbc' : b ∉ ({c} : Finset (Fin m)) := by simp [hbc] have ha' : a ∉ ({b, c} : Finset (Fin m)) := by simp [hab, hac] rw [sum_insert ha', sum_insert hbc', sum_singleton, add_assoc]
0 < Lam, n + l3 = Lam - l2, and 0 < Lam - l2.
From l1 < 2 * n we obtain 0 < Lam using sub_pos.mpr. The identity n + l3 = Lam - l2 holds by hn_eigenvalue_shift_identity, and combined with -n < l3 this gives 0 < Lam - l2.
uses
sub_pos.mpr,hn_eigenvalue_shift_identityintro Lam have hLam : 0 < Lam := sub_pos.mpr hl1 have hshift : (n : ℝ) + l3 = Lam - l2 := hn_eigenvalue_shift_identity n l1 l2 l3 hsum have hpos3 : 0 < Lam - l2 := by rw [← hshift] linarith [hl3]
The indices i0 = 0, i1 = 1, and i2 = 3 * n - 2 in Fin (3 * n) are pairwise distinct.
Since 2 ≤ n, the values 0, 1, and 3 * n - 2 are strictly bounded by 3 * n and mutually distinct.
let i0 : Fin (3 * n) := ⟨0, by omega⟩ let i1 : Fin (3 * n) := ⟨1, by omega⟩ let i2 : Fin (3 * n) := ⟨3 * n - 2, by omega⟩ have hab : i0 ≠ i1 := by intro h; injection h; omega have hbc : i1 ≠ i2 := by intro h; injection h; omega have hac : i0 ≠ i2 := by intro h; injection h; omega
At index i0, the difference of eigenvalues is Lam.
At index 0, the first eigenvalue is 2 * n and the second is l1, so their difference is 2 * n - l1 = Lam by definition.
have heval0 : knnn_eigenvalues n i0 - hn_eigenvalues n l1 l2 l3 i0 = Lam := by rfl
At index i1, the difference of eigenvalues is -l2.
Since 1 < 3 * n - 2 for n ≥ 2, the first eigenvalue is 0 and the second is l2, giving a difference of -l2.
have heval1 : knnn_eigenvalues n i1 - hn_eigenvalues n l1 l2 l3 i1 = -l2 := by dsimp [i1, knnn_eigenvalues, hn_eigenvalues] have hlt : 1 < 3 * n - 2 := by omega simp [hlt]
At index i2, the difference of eigenvalues is -(Lam - l2).
At index 3 * n - 2, the first eigenvalue is -n and the second is l3. Their difference is -n - l3 = -(n + l3), which equals -(Lam - l2) by the shift identity.
have heval2 : knnn_eigenvalues n i2 - hn_eigenvalues n l1 l2 l3 i2 = -(Lam - l2) := by dsimp [i2, knnn_eigenvalues, hn_eigenvalues] have h0 : 3 * n - 2 ≠ 0 := by omega have h1 : 3 * n - 2 ≠ 1 := by omega have hlt : ¬ (3 * n - 2 < 3 * n - 2) := by omega simp only [h0, h1, hlt, ↓reduceIte] linarith [hshift]
At every index x other than i0, i1, i2, the difference of eigenvalues is 0.
For any other index x, if x < 3 * n - 2 both eigenvalues are 0, and if x > 3 * n - 2 both are -n. In both cases the difference is 0.
have heval_other : ∀ x : Fin (3 * n), x ≠ i0 → x ≠ i1 → x ≠ i2 → knnn_eigenvalues n x - hn_eigenvalues n l1 l2 l3 x = 0 := by intro x h0 h1 h2 have hx0 : (x : ℕ) ≠ 0 := by intro h; apply h0; ext; exact h have hx1 : (x : ℕ) ≠ 1 := by intro h; apply h1; ext; exact h have hx2 : (x : ℕ) ≠ 3 * n - 2 := by intro h; apply h2; ext; exact h dsimp [knnn_eigenvalues, hn_eigenvalues] simp only [hx0, hx1, hx2, ↓reduceIte] split_ifs <;> ring
The Manhattan spectral distance between the two eigenvalue vectors is 2 * Lam.
By definition, the L1 spectral distance is the sum of absolute differences. Using the helper lemma, this reduces to |Lam| + |-l2| + |-(Lam - l2)|, which simplifies to Lam + l2 + (Lam - l2) = 2 * Lam since each term is positive.
uses
spectral_distances_knnn_hn_eigenvalues_helper,abs_of_pos,abs_negrefine ⟨hLam, ?_, ?_⟩ · -- spectral_distance_l1 dsimp [spectral_distance_l1] rw [spectral_distances_knnn_hn_eigenvalues_helper (fun i => |knnn_eigenvalues n i - hn_eigenvalues n l1 l2 l3 i|) i0 i1 i2 hab hbc hac] · rw [heval0, heval1, heval2] rw [abs_of_pos hLam] rw [abs_neg, abs_of_pos hl2] rw [abs_neg, abs_of_pos hpos3] ring · intro x h0 h1 h2 rw [heval_other x h0 h1 h2] simp
The squared Euclidean spectral distance between the two eigenvalue vectors is 2 * (Lam ^ 2 - Lam * l2 + l2 ^ 2).
By definition, the squared L2 spectral distance is the sum of squared differences. By the helper lemma, this reduces to Lam ^ 2 + (-l2) ^ 2 + (-(Lam - l2)) ^ 2, which expands and simplifies algebraically to 2 * (Lam ^ 2 - Lam * l2 + l2 ^ 2).
uses
spectral_distances_knnn_hn_eigenvalues_helper· -- spectral_distance_l2_sq dsimp [spectral_distance_l2_sq] rw [spectral_distances_knnn_hn_eigenvalues_helper (fun i => (knnn_eigenvalues n i - hn_eigenvalues n l1 l2 l3 i) ^ 2) i0 i1 i2 hab hbc hac] · rw [heval0, heval1, heval2] ring · intro x h0 h1 h2 rw [heval_other x h0 h1 h2] simp
Finset.sum_subset- The sum of a function over a subset equals the sum over the superset when the function vanishes outside the subset.
Finset.subset_univ- Every finset is a subset of the universal finset.
mem_insert- Membership in a finset obtained by inserting an element.
mem_singleton- Membership in a singleton finset.
not_or- De Morgan's law: not (P or Q) is equivalent to not P and not Q.
Finset.sum_insert- Inserting an element not in a finset adds its value to the sum over the finset.
Finset.sum_singleton- The sum of a function over a singleton set is the value at that element.
add_assoc- Addition in an additive semigroup is associative: a + b + c = a + (b + c).
sub_pos.mpr- If a < b, then 0 < b - a.
hn_eigenvalue_shift_identity- For eigenvalues of H_n, (n : ℝ) + l3 = Lam - l2 where Lam = 2 * n - l1.
spectral_distances_knnn_hn_eigenvalues_helper- A sum over a finite domain supported on three distinct points equals the sum of the three values.
abs_of_pos- The absolute value of a positive real number is itself.
abs_neg- The absolute value of -a equals the absolute value of a.
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.
open Finsettheorem spectral_distances_knnn_hn_eigenvalues_helper {m : ℕ} (f : Fin m → ℝ) (a b c : Fin m) (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c) (h_zero : ∀ x : Fin m, x ≠ a → x ≠ b → x ≠ c → f x = 0) : ∑ x, f x = f a + f b + f c := by have hsub : ({a, b, c} : Finset (Fin m)) ⊆ univ := subset_univ _ have h_eq : ∑ x, f x = ∑ x ∈ ({a, b, c} : Finset (Fin m)), f x := by apply (sum_subset hsub _).symm intro x _ hx simp only [mem_insert, mem_singleton, not_or] at hx exact h_zero x hx.1 hx.2.1 hx.2.2 rw [h_eq] have hbc' : b ∉ ({c} : Finset (Fin m)) := by simp [hbc] have ha' : a ∉ ({b, c} : Finset (Fin m)) := by simp [hab, hac] rw [sum_insert ha', sum_insert hbc', sum_singleton, add_assoc]/-- Closed form Manhattan and squared Euclidean spectral distances between knnn_eigenvalues and hn_eigenvalues. -/theorem spectral_distances_knnn_hn_eigenvalues (n : ℕ) (hle : 2 ≤ n) (l1 l2 l3 : ℝ) (hsum : l1 + l2 + l3 = (n : ℝ)) (hl1 : l1 < 2 * (n : ℝ)) (hl2 : 0 < l2) (hl3 : -(n : ℝ) < l3) : let Lam := 2 * (n : ℝ) - l1 0 < Lam ∧ spectral_distance_l1 (knnn_eigenvalues n) (hn_eigenvalues n l1 l2 l3) = 2 * Lam ∧ spectral_distance_l2_sq (knnn_eigenvalues n) (hn_eigenvalues n l1 l2 l3) = 2 * (Lam ^ 2 - Lam * l2 + l2 ^ 2) := by intro Lam have hLam : 0 < Lam := sub_pos.mpr hl1 have hshift : (n : ℝ) + l3 = Lam - l2 := hn_eigenvalue_shift_identity n l1 l2 l3 hsum have hpos3 : 0 < Lam - l2 := by rw [← hshift] linarith [hl3] let i0 : Fin (3 * n) := ⟨0, by omega⟩ let i1 : Fin (3 * n) := ⟨1, by omega⟩ let i2 : Fin (3 * n) := ⟨3 * n - 2, by omega⟩ have hab : i0 ≠ i1 := by intro h; injection h; omega have hbc : i1 ≠ i2 := by intro h; injection h; omega have hac : i0 ≠ i2 := by intro h; injection h; omega have heval0 : knnn_eigenvalues n i0 - hn_eigenvalues n l1 l2 l3 i0 = Lam := by rfl have heval1 : knnn_eigenvalues n i1 - hn_eigenvalues n l1 l2 l3 i1 = -l2 := by dsimp [i1, knnn_eigenvalues, hn_eigenvalues] have hlt : 1 < 3 * n - 2 := by omega simp [hlt] have heval2 : knnn_eigenvalues n i2 - hn_eigenvalues n l1 l2 l3 i2 = -(Lam - l2) := by dsimp [i2, knnn_eigenvalues, hn_eigenvalues] have h0 : 3 * n - 2 ≠ 0 := by omega have h1 : 3 * n - 2 ≠ 1 := by omega have hlt : ¬ (3 * n - 2 < 3 * n - 2) := by omega simp only [h0, h1, hlt, ↓reduceIte] linarith [hshift] have heval_other : ∀ x : Fin (3 * n), x ≠ i0 → x ≠ i1 → x ≠ i2 → knnn_eigenvalues n x - hn_eigenvalues n l1 l2 l3 x = 0 := by intro x h0 h1 h2 have hx0 : (x : ℕ) ≠ 0 := by intro h; apply h0; ext; exact h have hx1 : (x : ℕ) ≠ 1 := by intro h; apply h1; ext; exact h have hx2 : (x : ℕ) ≠ 3 * n - 2 := by intro h; apply h2; ext; exact h dsimp [knnn_eigenvalues, hn_eigenvalues] simp only [hx0, hx1, hx2, ↓reduceIte] split_ifs <;> ring refine ⟨hLam, ?_, ?_⟩ · -- spectral_distance_l1 dsimp [spectral_distance_l1] rw [spectral_distances_knnn_hn_eigenvalues_helper (fun i => |knnn_eigenvalues n i - hn_eigenvalues n l1 l2 l3 i|) i0 i1 i2 hab hbc hac] · rw [heval0, heval1, heval2] rw [abs_of_pos hLam] rw [abs_neg, abs_of_pos hl2] rw [abs_neg, abs_of_pos hpos3] ring · intro x h0 h1 h2 rw [heval_other x h0 h1 h2] simp · -- spectral_distance_l2_sq dsimp [spectral_distance_l2_sq] rw [spectral_distances_knnn_hn_eigenvalues_helper (fun i => (knnn_eigenvalues n i - hn_eigenvalues n l1 l2 l3 i) ^ 2) i0 i1 i2 hab hbc hac] · rw [heval0, heval1, heval2] ring · intro x h0 h1 h2 rw [heval_other x h0 h1 h2] simp