AFTD Auto-Formalizing Theoretical Domains

standardized_laplacian_spectra_subset_of_dvd

theoremverifiedformalization

Let m, n ≥ 2 be natural numbers such that m divides n. Then the set of eigenvalues of standardized Laplacian matrices of order m is a subset of the set of eigenvalues of standardized Laplacian matrices of order n.

Statement

theorem standardized_laplacian_spectra_subset_of_dvd (m n : ℕ) (hm : 2 ≤ m) (hn : 2 ≤ n)
    (hdvd : m ∣ n) :
    standardized_laplacian_spectra m ⊆ standardized_laplacian_spectra n
Formalizes
scout/2610-14100-digraph-laplacian-spectra-the-2005-polygon-conjecture-fails.md:1044
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • is_standardized_laplacianA standardized Laplacian matrix of order n is a real n x n matrix with zero row sums and off-diagonal entries in [-1/n, 0].
  • standardized_laplacian_spectraThe set Lambda_n of all complex eigenvalues of standardized Laplacian matrices of order n.
  • balanced_blowup_matrixFor natural numbers m and d, and an m x m real matrix L on Fin m, balanced_blowup_matrix m d L is the real matrix on Fin m × Fin d defined…
  • balanced_blowup_matrix_row_sumFor natural numbers m and d with 1 ≤ d, and an m x m real matrix L on Fin m with zero row sums, each row of the balanced blow-up matrix…
  • balanced_blowup_matrix_off_diagFor natural numbers m and d with 1 ≤ m and 1 ≤ d, and an m x m real matrix L on Fin m with off-diagonal entries in [-1/m, 0], all…
  • balanced_blowup_spectrum_subsetFor natural numbers m and d with 1 ≤ d, and an m x m real matrix L on Fin m, the complex spectrum of L is a subset of the complex spectrum…

Read back from the Lean

For any natural numbers m and n, if 2 ≤ m, 2 ≤ n, and m ∣ n, then the set of standardized Laplacian spectra of order m is a subset of the set of standardized Laplacian spectra of order n.

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 show that every eigenvalue of an m × m standardized Laplacian matrix is also an eigenvalue of an n × n standardized Laplacian when m divides n, we set d = n / m and construct the balanced blowup matrix L' of size (m · d) × (m · d). By the spectral inclusion theorem for balanced blowups, L' retains the spectrum of L. Reindexing L' along a bijection Fin m × Fin d ≃ Fin n produces an n × n matrix M whose row sums and off-diagonal bounds satisfy the standardized Laplacian axioms. Finally, because reindexing is an algebra isomorphism, it preserves the spectrum, showing that the eigenvalue belongs to the standardized Laplacian spectrum of order n.

  1. Let z be an eigenvalue of some standardized Laplacian matrix L of order m.

    We take an arbitrary element z in the standardized Laplacian spectrum of order m. By definition, there exists a matrix L of size m × m with zero row sums and off-diagonal entries in [-1/m, 0] such that z is in the spectrum of L.

    lines 5–8

      intro z hz
      simp only [standardized_laplacian_spectra] at hz ⊢
      rcases hz with ⟨L, hL, hzL⟩
      rcases hL with ⟨hL_row, hL_off⟩
  2. The blowup factor d = n / m is at least 1, satisfies m * d = n, and the balanced blowup matrix L' retains the eigenvalue z.

    Since m divides n and both are at least 2, d = n / m is a positive natural number satisfying m * d = n. We construct the balanced blowup matrix L' of L of block size d. By balanced_blowup_spectrum_subset, the spectrum of L' contains that of L, so z is in the spectrum of L'.

    lines 9–15

    uses Nat.div_pos, Nat.le_of_dvd, Nat.mul_div_cancel', balanced_blowup_spectrum_subset

      set d := n / m with hd_def
      have hm1 : 1 ≤ m := by omega
      have hd : 1 ≤ d := Nat.div_pos (Nat.le_of_dvd (by omega) hdvd) (by omega)
      have h_mul : m * d = n := Nat.mul_div_cancel' hdvd
      set L' := balanced_blowup_matrix m d L with hL'_def
      have hzL' : z ∈ spectrum ℂ (L'.map Complex.ofReal) :=
        balanced_blowup_spectrum_subset m d hd L hzL
  3. Reindexing L' via the bijection Fin m × Fin d ≃ Fin n yields an n × n matrix M, proposed as the standardized Laplacian witness.

    Using the arithmetic identity m * d = n, we compose the product equivalence Fin m × Fin d ≃ Fin (m * d) with finCongr to get a bijection e : Fin m × Fin d ≃ Fin n. Reindexing L' by e gives an n × n matrix M, which we propose as the witness for z being in the standardized Laplacian spectrum of order n.

    lines 16–19

    uses finCongr

      let e : Fin m × Fin d ≃ Fin n := finProdFinEquiv.trans (finCongr h_mul)
      set M := Matrix.reindex e e L' with hM_def
      use M
      refine ⟨⟨?_, ?_⟩, ?_⟩
  4. Every row sum of M is zero.

    For each row index i, rewriting the sum over j : Fin n using the equivalence e converts it into a double sum over Fin m × Fin d. Evaluating at the pre-image e⁻¹(i) = (i₁, s₁), the sum vanishes by balanced_blowup_matrix_row_sum.

    lines 20–26

    uses Equiv.sum_comp, Matrix.reindex_apply, Matrix.submatrix_apply, Equiv.symm_apply_apply, Fintype.sum_prod_type, balanced_blowup_matrix_row_sum

      · intro i
        change ∑ j : Fin n, Matrix.reindex e e L' i j = 0
        rw [← Equiv.sum_comp e (fun j => Matrix.reindex e e L' i j)]
        simp only [Matrix.reindex_apply, Matrix.submatrix_apply, Equiv.symm_apply_apply]
        rcases e.symm i with ⟨i₁, s₁⟩
        rw [Fintype.sum_prod_type]
        exact balanced_blowup_matrix_row_sum m d hd L hL_row i₁ s₁
  5. For distinct indices i ≠ j, the off-diagonal entry M i j lies in [-1/n, 0].

    Because e⁻¹ is injective, i ≠ j implies e⁻¹(i) ≠ e⁻¹(j). The entry M i j corresponds to an off-diagonal entry of L', which by balanced_blowup_matrix_off_diag lies in [-1/(m * d), 0]. Substituting m * d = n yields the required bound [-1/n, 0].

    lines 27–37

    uses Matrix.reindex_apply, Matrix.submatrix_apply, balanced_blowup_matrix_off_diag

      · intro i j hij
        change -(1 : ℝ) / (n : ℝ) ≤ Matrix.reindex e e L' i j ∧ Matrix.reindex e e L' i j ≤ 0
        simp only [Matrix.reindex_apply, Matrix.submatrix_apply]
        have hne : e.symm i ≠ e.symm j := by
          intro h
          apply hij
          exact e.symm.injective h
        have h_off := balanced_blowup_matrix_off_diag m d hm1 hd L hL_off (e.symm i).1 (e.symm j).1 (e.symm i).2 (e.symm j).2 hne
        have h_cast : (n : ℝ) = (m * d : ℝ) := by rw [← h_mul]; push_cast; rfl
        rw [h_cast]
        exact h_off
  6. The complex eigenvalue z belongs to the spectrum of M.

    Reindexing along e induces an algebra isomorphism Matrix.reindexAlgEquiv between the matrix algebras. By AlgEquiv.spectrum_eq, an algebra isomorphism preserves spectra, so the spectrum of M matches that of L', which contains z.

    lines 38–44

    uses Matrix.coe_reindexAlgEquiv, AlgEquiv.spectrum_eq

      · have h_map : M.map Complex.ofReal = Matrix.reindexAlgEquiv ℂ ℂ e (L'.map Complex.ofReal) := by
          rw [hM_def]
          ext i j
          simp [Matrix.coe_reindexAlgEquiv]
        rw [h_map]
        rw [AlgEquiv.spectrum_eq (Matrix.reindexAlgEquiv ℂ ℂ e) (L'.map Complex.ofReal)]
        exact hzL'
Nat.le_of_dvd
If a natural number m divides n and n > 0, then m ≤ n.
Nat.div_pos
For natural numbers a and b, if b ≤ a and b > 0, then a / b > 0.
Nat.mul_div_cancel'
If n divides m, then n * (m / n) = m.
balanced_blowup_spectrum_subset
Every eigenvalue of a matrix L is also an eigenvalue of its balanced blowup matrix.
finCongr
An equality of natural numbers n = m induces an equivalence between Fin n and Fin m.
Equiv.sum_comp
Summing over a finite set is invariant under reindexing the terms by an equivalence.
Matrix.reindex_apply
Reindexing a matrix by row and column equivalences corresponds to taking the submatrix via their inverses.
Matrix.submatrix_apply
The (i, j)-th entry of a submatrix formed by index maps r and c is the (r i, c j)-th entry of the original matrix.
Equiv.symm_apply_apply
Applying an equivalence and then its inverse is the identity.
Fintype.sum_prod_type
A sum over a Cartesian product of finite types equals the iterated sum over each component.
balanced_blowup_matrix_row_sum
If the row sums of L are zero, then the row sums of its balanced blowup matrix are also zero.
balanced_blowup_matrix_off_diag
If the off-diagonal entries of L lie in [-1/m, 0], then the off-diagonal entries of its balanced blowup matrix lie in [-1/(m * d), 0].
Matrix.coe_reindexAlgEquiv
The underlying map of the matrix algebra equivalence induced by an index equivalence is given by Matrix.reindex.
AlgEquiv.spectrum_eq
An algebra equivalence preserves the spectrum of an element.

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

/-- If m divides n for integers m, n >= 2, then Lambda_m is a subset of Lambda_n. -/theorem standardized_laplacian_spectra_subset_of_dvd (m n : ℕ) (hm : 2 ≤ m) (hn : 2 ≤ n)    (hdvd : m ∣ n) :    standardized_laplacian_spectra m ⊆ standardized_laplacian_spectra n := by  intro z hz  simp only [standardized_laplacian_spectra] at hz ⊢  rcases hz with ⟨L, hL, hzL⟩  rcases hL with ⟨hL_row, hL_off⟩  set d := n / m with hd_def  have hm1 : 1 ≤ m := by omega  have hd : 1 ≤ d := Nat.div_pos (Nat.le_of_dvd (by omega) hdvd) (by omega)  have h_mul : m * d = n := Nat.mul_div_cancel' hdvd  set L' := balanced_blowup_matrix m d L with hL'_def  have hzL' : z ∈ spectrum ℂ (L'.map Complex.ofReal) :=    balanced_blowup_spectrum_subset m d hd L hzL  let e : Fin m × Fin d ≃ Fin n := finProdFinEquiv.trans (finCongr h_mul)  set M := Matrix.reindex e e L' with hM_def  use M  refine ⟨⟨?_, ?_⟩, ?_⟩  · intro i    change ∑ j : Fin n, Matrix.reindex e e L' i j = 0    rw [← Equiv.sum_comp e (fun j => Matrix.reindex e e L' i j)]    simp only [Matrix.reindex_apply, Matrix.submatrix_apply, Equiv.symm_apply_apply]    rcases e.symm i with ⟨i₁, s₁⟩    rw [Fintype.sum_prod_type]    exact balanced_blowup_matrix_row_sum m d hd L hL_row i₁ s₁  · intro i j hij    change -(1 : ℝ) / (n : ℝ) ≤ Matrix.reindex e e L' i j ∧ Matrix.reindex e e L' i j ≤ 0    simp only [Matrix.reindex_apply, Matrix.submatrix_apply]    have hne : e.symm i ≠ e.symm j := by      intro h      apply hij      exact e.symm.injective h    have h_off := balanced_blowup_matrix_off_diag m d hm1 hd L hL_off (e.symm i).1 (e.symm j).1 (e.symm i).2 (e.symm j).2 hne    have h_cast : (n : ℝ) = (m * d : ℝ) := by rw [← h_mul]; push_cast; rfl    rw [h_cast]    exact h_off  · have h_map : M.map Complex.ofReal = Matrix.reindexAlgEquiv ℂ ℂ e (L'.map Complex.ofReal) := by      rw [hM_def]      ext i j      simp [Matrix.coe_reindexAlgEquiv]    rw [h_map]    rw [AlgEquiv.spectrum_eq (Matrix.reindexAlgEquiv ℂ ℂ e) (L'.map Complex.ofReal)]    exact hzL'
See it in the graphDiscuss this resultChallenge it