AFTD Auto-Formalizing Theoretical Domains

spectral_distances_knnn_hn_eigenvalues

theoremverifiedformalization

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).

  1. 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.

    lines 7–13

    uses subset_univ, sum_subset, mem_insert, mem_singleton, not_or

      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]
  2. 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.

    lines 14–16

    uses sum_insert, sum_singleton, add_assoc

      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]
  3. 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.

    lines 30–35

    uses sub_pos.mpr, hn_eigenvalue_shift_identity

      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]
  4. 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.

    lines 36–42

      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
    
  5. 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.

    lines 43–44

      have heval0 : knnn_eigenvalues n i0 - hn_eigenvalues n l1 l2 l3 i0 = Lam := by
        rfl
  6. 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.

    lines 45–48

      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]
  7. 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.

    lines 49–55

      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]
  8. 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.

    lines 56–65

      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
    
  9. 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.

    lines 66–79

    uses spectral_distances_knnn_hn_eigenvalues_helper, abs_of_pos, abs_neg

      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
  10. 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).

    lines 80–89

    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

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
See it in the graphDiscuss this resultChallenge it