AFTD Auto-Formalizing Theoretical Domains

standardized_laplacian_order_four_im_le_three_quarters

theoremverified

For any standardized Laplacian matrix L of order 4, the imaginary part of every complex eigenvalue z satisfies |Im z| ≤ 3/4.

Statement

theorem standardized_laplacian_order_four_im_le_three_quarters (L : Matrix (Fin 4) (Fin 4) ℝ)
    (hL : is_standardized_laplacian 4 L) (z : ℂ)
    (hz : z ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ))) :
    |z.im| ≤ (3 : ℝ) / 4
Source
step towards op_465_standardized_laplacian_order_four_polygon_conjecture
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The proof uses Gershgorin's disc theorem for standardized Laplacians to place the eigenvalue z in a disc centered at a diagonal entry L k k with radius L k k, meaning ‖z - L k k‖ ≤ L k k. Since L k k is real, the imaginary part is preserved under centering, giving |z.im| ≤ ‖z - L k k‖. Because row sums are zero and each off-diagonal entry satisfies -1/4 ≤ L k j ≤ 0, the diagonal entry L k k equals the sum of 3 negated off-diagonal entries, each bounded by 1/4, so L k k ≤ 3/4. Chaining these bounds yields |z.im| ≤ 3/4.

  1. There exists a row index k such that the eigenvalue z lies in the k-th Gershgorin disc: ‖z - L k k‖ ≤ L k k.

    By Gershgorin's disc theorem adapted for standardized Laplacians (standardized_laplacian_eigenvalue_gershgorin_disc), every eigenvalue z of L is contained in the Gershgorin disc centered at some diagonal entry L k k with radius L k k.

    line 5

    uses standardized_laplacian_eigenvalue_gershgorin_disc

      obtain ⟨k, hk⟩ := standardized_laplacian_eigenvalue_gershgorin_disc 4 L hL z hz
  2. |z.im| ≤ ‖z - L k k‖

    Because the matrix entry L k k is a real number, its imaginary part is zero (Complex.ofReal_im), so (z - L k k).im = z.im (Complex.sub_im). The absolute value of the imaginary part of any complex number is bounded by its complex modulus (Complex.abs_im_le_norm).

    lines 6–10

    uses Complex.sub_im, Complex.ofReal_im, Complex.abs_im_le_norm

      have h_im_le : |z.im| ≤ ‖z - (L k k : ℂ)‖ := by
        have h_im_eq : z.im = (z - (L k k : ℂ)).im := by
          simp [Complex.sub_im, Complex.ofReal_im]
        rw [h_im_eq]
        exact Complex.abs_im_le_norm (z - (L k k : ℂ))
  3. The diagonal entry L k k equals the sum of the negated off-diagonal entries in its row: L k k = ∑ j ≠ k, -L k j.

    In a standardized Laplacian, every row sums to zero (hL.1 k). Separating the diagonal entry L k k from the off-diagonal sum over Finset.univ.erase k (Finset.add_sum_erase, Finset.mem_univ) gives L k k + ∑ j ≠ k, L k j = 0. Factoring out negation (Finset.sum_neg_distrib) and rearranging by linear arithmetic gives L k k = ∑ j ≠ k, -L k j. Substituting this expression reduces bounding L k k to bounding the sum of negated off-diagonal entries.

    lines 11–20

    uses Finset.add_sum_erase, Finset.mem_univ, Finset.sum_neg_distrib

      have h_diag_le : L k k ≤ (3 : ℝ) / 4 := by
        have h_row := hL.1 k
        have h_off := hL.2
        have h_split : L k k + ∑ j ∈ Finset.univ.erase k, L k j = ∑ j, L k j :=
          Finset.add_sum_erase Finset.univ (fun j => L k j) (Finset.mem_univ k)
        rw [h_row] at h_split
        have h_diag : L k k = ∑ j ∈ Finset.univ.erase k, -L k j := by
          rw [Finset.sum_neg_distrib]
          linarith
        rw [h_diag]
  4. For each off-diagonal index j ≠ k, -L k j ≤ 1 / 4.

    For any j distinct from k (Finset.ne_of_mem_erase), the definition of a standardized Laplacian of order 4 (hL.2) ensures that -1 / 4 ≤ L k j. Negating this inequality yields -L k j ≤ 1 / 4.

    lines 21–25

    uses Finset.ne_of_mem_erase

        have h_le : ∀ j ∈ Finset.univ.erase k, -L k j ≤ (1 : ℝ) / 4 := by
          intro j hj
          have h_ne : k ≠ j := (Finset.ne_of_mem_erase hj).symm
          have := (h_off k j h_ne).1
          linarith
  5. L k k ≤ 3 / 4

    Summing the termwise inequality -L k j ≤ 1 / 4 over all j ≠ k (Finset.sum_le_sum) bounds the off-diagonal sum by the sum of 1 / 4 over the 3 remaining indices (Finset.card_erase_of_mem, Finset.mem_univ). The constant sum evaluates to 3 * (1 / 4) = 3 / 4 (Finset.sum_const, nsmul_eq_mul), from which linear arithmetic establishes L k k ≤ 3 / 4.

    lines 26–33

    uses Finset.sum_le_sum, Finset.card_erase_of_mem, Finset.mem_univ, Finset.sum_const, nsmul_eq_mul

        have h_sum_le := Finset.sum_le_sum h_le
        have h_card : (Finset.univ.erase k).card = 3 := by
          rw [Finset.card_erase_of_mem (Finset.mem_univ k)]
          simp
        have h_const : ∑ j ∈ Finset.univ.erase k, ((1 : ℝ) / 4) = (3 : ℝ) / 4 := by
          rw [Finset.sum_const, h_card, nsmul_eq_mul]
          ring
        linarith
  6. |z.im| ≤ 3 / 4

    Linear arithmetic combines the three inequalities |z.im| ≤ ‖z - L k k‖, ‖z - L k k‖ ≤ L k k, and L k k ≤ 3 / 4 to conclude that |z.im| ≤ 3 / 4.

    line 34

      linarith
standardized_laplacian_eigenvalue_gershgorin_disc
For any complex eigenvalue z of a standardized Laplacian matrix of order n, there exists a row index k such that ‖z - L k k‖ ≤ L k k.
Complex.abs_im_le_norm
The absolute value of the imaginary part of a complex number is at most its complex norm: |z.im| ≤ ‖z‖.
Complex.sub_im
The imaginary part of a difference of complex numbers is the difference of their imaginary parts: (z - w).im = z.im - w.im.
Complex.ofReal_im
The imaginary part of a real number regarded as a complex number is zero: (r : ℂ).im = 0.
Finset.add_sum_erase
A sum over a finite set s can be split into the value at a chosen element a ∈ s and the sum over s \ {a}.
Finset.mem_univ
Every element of a finite type belongs to its universal Finset univ.
Finset.sum_neg_distrib
Negation distributes over a finite sum: ∑ x ∈ s, -f x = -∑ x ∈ s, f x.
Finset.ne_of_mem_erase
If an element b belongs to s \ {a}, then b ≠ a.
Finset.sum_le_sum
If f i ≤ g i for every element i in a finite set s, then ∑ i ∈ s, f i ≤ ∑ i ∈ s, g i.
Finset.card_erase_of_mem
Removing an element a from a finite set s decreases its cardinality by one: (s \ {a}).card = s.card - 1.
Finset.sum_const
Summing a constant value b over a finite set s equals s.card • b.
nsmul_eq_mul
Scalar multiplication by a natural number n coincides with multiplication by n in a semiring: n • a = n * 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

theorem standardized_laplacian_order_four_im_le_three_quarters (L : Matrix (Fin 4) (Fin 4) ℝ)    (hL : is_standardized_laplacian 4 L) (z : ℂ)    (hz : z ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ))) :    |z.im| ≤ (3 : ℝ) / 4 := by  obtain ⟨k, hk⟩ := standardized_laplacian_eigenvalue_gershgorin_disc 4 L hL z hz  have h_im_le : |z.im| ≤ ‖z - (L k k : ℂ)‖ := by    have h_im_eq : z.im = (z - (L k k : ℂ)).im := by      simp [Complex.sub_im, Complex.ofReal_im]    rw [h_im_eq]    exact Complex.abs_im_le_norm (z - (L k k : ℂ))  have h_diag_le : L k k ≤ (3 : ℝ) / 4 := by    have h_row := hL.1 k    have h_off := hL.2    have h_split : L k k + ∑ j ∈ Finset.univ.erase k, L k j = ∑ j, L k j :=      Finset.add_sum_erase Finset.univ (fun j => L k j) (Finset.mem_univ k)    rw [h_row] at h_split    have h_diag : L k k = ∑ j ∈ Finset.univ.erase k, -L k j := by      rw [Finset.sum_neg_distrib]      linarith    rw [h_diag]    have h_le : ∀ j ∈ Finset.univ.erase k, -L k j ≤ (1 : ℝ) / 4 := by      intro j hj      have h_ne : k ≠ j := (Finset.ne_of_mem_erase hj).symm      have := (h_off k j h_ne).1      linarith    have h_sum_le := Finset.sum_le_sum h_le    have h_card : (Finset.univ.erase k).card = 3 := by      rw [Finset.card_erase_of_mem (Finset.mem_univ k)]      simp    have h_const : ∑ j ∈ Finset.univ.erase k, ((1 : ℝ) / 4) = (3 : ℝ) / 4 := by      rw [Finset.sum_const, h_card, nsmul_eq_mul]      ring    linarith  linarith
See it in the graphDiscuss this resultChallenge it