order_four_two_fractional_im_le_of_certificate
If the coefficients c1, c2, c3 of the characteristic polynomial of an order-4 two-fractional standardized Laplacian satisfy the D- and H-certificate, then every z in the complexified spectrum has |Im z| ≤ 1/4.
Statement
theorem order_four_two_fractional_im_le_of_certificate (L : Matrix (Fin 4) (Fin 4) ℝ) (hL : is_standardized_laplacian_two_fractional 4 L) (z : ℂ) (hz : z ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ))) (hcert : let c1 := (L.charpoly).coeff 1 let c2 := (L.charpoly).coeff 2 let c3 := (L.charpoly).coeff 3 (-(11 / 16 : ℝ) ≤ c3 ^ 2 - 3 * c2) ∧ (0 ≤ 4 * (c3 ^ 2 * c2 ^ 2 - 4 * c2 ^ 3 - 4 * c3 ^ 3 * c1 - 27 * c1 ^ 2 + 18 * c1 * c2 * c3) + (c3 ^ 2 - 3 * c2 + 1 / 4) ^ 2)) : |z.im| ≤ 1 / 4
- Source
- step towards standardized_laplacian_order_four_two_fractional_im_le
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- real_cubic_im_le_quarter_of_certificateA complex root z of the real monic cubic z^3 + c3 z^2 + c2 z + c1 has |Im z| ≤ 1/4 provided c3^2 - 3 c2 ≥ -11/16 and 4(c3^2 c2^2 - 4 c2^3…
- standardized_laplacian_order_four_zero_mem_spectrumFor every standardized Laplacian matrix L of order 4, zero is an eigenvalue of L.
- is_standardized_laplacian_two_fractionalA real matrix L of order n is a standardized Laplacian with at most two fractional entries per row if L is a standardized Laplacian and…
- 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].
The proof, explained
Because L is an order-4 standardized Laplacian, zero is in its spectrum, which forces the constant term of its monic degree-4 characteristic polynomial to vanish. Any eigenvalue z therefore satisfies z(z³ + c₃z² + c₂z + c₁) = 0. If z = 0, its imaginary part is trivially zero; otherwise, z is a root of the cubic factor, and the D- and H-certificate inequalities on the coefficients guarantee |Im z| ≤ 1/4 via the cubic certificate theorem.
The certificate inequalities hD and hH are unpacked, and c₁, c₂, c₃ are defined as the coefficients of degrees 1, 2, and 3 of the characteristic polynomial of L.
We simplify and decompose the certificate hypothesis into its two components: the discriminant bound hD and the nonnegativity condition hH, while fixing abbreviations c₁, c₂, and c₃ for the linear, quadratic, and cubic coefficients of the characteristic polynomial.
dsimp only at hcert obtain ⟨hD, hH⟩ := hcert set c1 := (L.charpoly).coeff 1 set c2 := (L.charpoly).coeff 2 set c3 := (L.charpoly).coeff 3
The constant term of the characteristic polynomial of L is zero: [X⁰] charpoly(L) = 0.
Because L is an order-4 standardized Laplacian, 0 is an eigenvalue of L in the complex spectrum (standardized_laplacian_order_four_zero_mem_spectrum). Thus 0 is a root of the complex characteristic polynomial (Matrix.mem_spectrum_iff_isRoot_charpoly.mp), which implies that its constant term is 0 (Polynomial.zero_isRoot_iff_coeff_zero_eq_zero.mp). Pulling this back through the injective embedding ℝ ↪ ℂ (Matrix.charpoly_map, Polynomial.coeff_map) shows that the constant term of the real characteristic polynomial is 0.
uses
standardized_laplacian_order_four_zero_mem_spectrum,Matrix.mem_spectrum_iff_isRoot_charpoly.mp,Polynomial.zero_isRoot_iff_coeff_zero_eq_zero.mp,Matrix.charpoly_map,Polynomial.coeff_maphave hc0 : (L.charpoly).coeff 0 = 0 := by have h0 : (0 : ℂ) ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ)) := standardized_laplacian_order_four_zero_mem_spectrum L hL.1 have h1 : ((L.map (algebraMap ℝ ℂ)).charpoly).IsRoot 0 := Matrix.mem_spectrum_iff_isRoot_charpoly.mp h0 have h2 : ((L.map (algebraMap ℝ ℂ)).charpoly).coeff 0 = 0 := Polynomial.zero_isRoot_iff_coeff_zero_eq_zero.mp h1 rw [Matrix.charpoly_map, Polynomial.coeff_map] at h2 exact (algebraMap ℝ ℂ).injective (by simpa using h2)
The characteristic polynomial of L has degree 4 and leading coefficient 1: [X⁴] charpoly(L) = 1.
The degree of the characteristic polynomial of an n × n matrix equals the matrix dimension, which is 4 (Matrix.charpoly_natDegree_eq_dim, Fintype.card_fin). Because the characteristic polynomial of any square matrix is monic (Matrix.charpoly_monic), its coefficient at degree 4 is 1.
uses
Matrix.charpoly_natDegree_eq_dim,Fintype.card_fin,Matrix.charpoly_monichave hd : L.charpoly.natDegree = 4 := by rw [Matrix.charpoly_natDegree_eq_dim, Fintype.card_fin] have hm : L.charpoly.coeff 4 = 1 := by have h := (Matrix.charpoly_monic L).coeff_natDegree rwa [hd] at h
The characteristic polynomial of L is equal to X⁴ + c₃X³ + c₂X² + c₁X.
Two polynomials are equal when all their coefficients match. We test each index n: for n = 0, the coefficient is 0 by hc0; for n = 1, 2, 3, the coefficients are c₁, c₂, c₃ by definition; for n = 4, the leading coefficient is 1 by hm. For n ≥ 5, both polynomials have degree at most 4, so their coefficients vanish (Polynomial.coeff_eq_zero_of_natDegree_lt).
uses
Polynomial.coeff_eq_zero_of_natDegree_lthave hpoly : L.charpoly = Polynomial.X^4 + Polynomial.C c3 * Polynomial.X^3 + Polynomial.C c2 * Polynomial.X^2 + Polynomial.C c1 * Polynomial.X := by ext n rcases n with _ | _ | _ | _ | _ | n · simp [hc0] · simp [c1] · simp [c2] · simp [c3] · simp [hm] · have h1 : L.charpoly.coeff (n + 5) = 0 := by apply Polynomial.coeff_eq_zero_of_natDegree_lt omega have h2 : (Polynomial.X^4 + Polynomial.C c3 * Polynomial.X^3 + Polynomial.C c2 * Polynomial.X^2 + Polynomial.C c1 * Polynomial.X : Polynomial ℝ).coeff (n + 5) = 0 := by apply Polynomial.coeff_eq_zero_of_natDegree_lt have : (Polynomial.X^4 + Polynomial.C c3 * Polynomial.X^3 + Polynomial.C c2 * Polynomial.X^2 + Polynomial.C c1 * Polynomial.X : Polynomial ℝ).natDegree ≤ 4 := by compute_degree! omega rw [h1, h2]
Every eigenvalue z in the complex spectrum of L satisfies z(z³ + c₃z² + c₂z + c₁) = 0.
Since z is an eigenvalue of L, it is a root of the complex characteristic polynomial (Matrix.mem_spectrum_iff_isRoot_charpoly.mp). Evaluating the polynomial X⁴ + c₃X³ + c₂X² + c₁X at z gives z⁴ + c₃z³ + c₂z² + c₁z = 0 (using the homomorphisms Matrix.charpoly_map, Polynomial.map_*, and Polynomial.eval_*). Factoring out z yields z(z³ + c₃z² + c₂z + c₁) = 0.
uses
Matrix.mem_spectrum_iff_isRoot_charpoly.mp,Matrix.charpoly_map,Polynomial.map_add,Polynomial.map_mul,Polynomial.map_pow,Polynomial.map_X,Polynomial.map_C,Polynomial.eval_add,Polynomial.eval_mul,Polynomial.eval_pow,Polynomial.eval_X,Polynomial.eval_Chave hroot : ((L.map (algebraMap ℝ ℂ)).charpoly).IsRoot z := Matrix.mem_spectrum_iff_isRoot_charpoly.mp hz rw [Matrix.charpoly_map, hpoly] at hroot dsimp [Polynomial.IsRoot] at hroot simp only [Polynomial.map_add, Polynomial.map_mul, Polynomial.map_pow, Polynomial.map_X, Polynomial.map_C, Polynomial.eval_add, Polynomial.eval_mul, Polynomial.eval_pow, Polynomial.eval_X, Polynomial.eval_C] at hroot have hfactor : z * (z ^ 3 + (c3 : ℂ) * z ^ 2 + (c2 : ℂ) * z + (c1 : ℂ)) = 0 := by linear_combination hroot
In all cases, |Im z| ≤ 1/4.
Because the product z(z³ + c₃z² + c₂z + c₁) is zero, either z = 0 or z³ + c₃z² + c₂z + c₁ = 0 (mul_eq_zero.mp). If z = 0, then |Im z| = 0 ≤ 1/4. If z is a root of the cubic factor, the certificate hypotheses hD and hH satisfy the requirements of real_cubic_im_le_quarter_of_certificate, which yields |Im z| ≤ 1/4.
uses
mul_eq_zero.mp,real_cubic_im_le_quarter_of_certificatercases mul_eq_zero.mp hfactor with hz0 | hcubic · subst hz0 simp · exact real_cubic_im_le_quarter_of_certificate c1 c2 c3 z hcubic hD hH
Fintype.card_fin- The cardinality of Fin n is n.
Matrix.charpoly_monic- The characteristic polynomial of any square matrix is monic (its leading coefficient is 1).
Matrix.charpoly_natDegree_eq_dim- The degree of the characteristic polynomial of an n × n matrix is n.
Matrix.charpoly_map- The characteristic polynomial of a matrix whose entries are mapped under a ring homomorphism f is the polynomial obtained by applying f to the coefficients of the original characteristic polynomial.
Matrix.mem_spectrum_iff_isRoot_charpoly.mp- If a scalar is in the spectrum of a matrix, then it is a root of the matrix's characteristic polynomial.
Polynomial.coeff_eq_zero_of_natDegree_lt- Any coefficient of a polynomial at an index strictly greater than its degree is zero.
Polynomial.coeff_map- The n-th coefficient of the polynomial obtained by applying a ring homomorphism f to the coefficients is the image under f of the original n-th coefficient.
Polynomial.eval_C- Evaluating a constant polynomial C(a) at any point yields a.
Polynomial.eval_X- Evaluating the indeterminate X at a point x yields x.
Polynomial.eval_add- Evaluating a sum of polynomials at a point equals the sum of the evaluations of the polynomials.
Polynomial.eval_mul- Evaluating a product of polynomials at a point equals the product of the evaluations of the polynomials.
Polynomial.eval_pow- Evaluating a power of a polynomial at a point equals the power of the evaluation of the polynomial.
Polynomial.map_C- Applying a ring homomorphism over a constant polynomial C(a) yields C(f(a)).
Polynomial.map_X- Applying a ring homomorphism over the indeterminate X yields X.
Polynomial.map_add- Applying a ring homomorphism over a sum of polynomials equals the sum of the mapped polynomials.
Polynomial.map_mul- Applying a ring homomorphism over a product of polynomials equals the product of the mapped polynomials.
Polynomial.map_pow- Applying a ring homomorphism over a power of a polynomial equals the power of the mapped polynomial.
Polynomial.zero_isRoot_iff_coeff_zero_eq_zero.mp- If 0 is a root of a polynomial, then its constant term (degree 0 coefficient) is zero.
mul_eq_zero.mp- If a product of two elements is zero, then at least one factor is zero.
real_cubic_im_le_quarter_of_certificate- If the coefficients of a monic real cubic z³ + c₃z² + c₂z + c₁ = 0 satisfy the D- and H-certificates, then every complex root z satisfies |Im z| ≤ 1/4.
standardized_laplacian_order_four_zero_mem_spectrum- Every 4 × 4 standardized Laplacian has 0 in its complex spectrum.
- The characteristic polynomial of L is identified with X⁴ + c₃X³ + c₂X² + c₁X by a coefficient-by-coefficient extensionality proof, where coefficients of degree 5 and higher are shown to vanish using degree bounds.
- The fact that 0 is an eigenvalue of L is established in the complex spectrum and pulled back to deduce that the real characteristic polynomial has constant coefficient 0 via the injectivity of the inclusion ℝ ↪ ℂ.
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.
/-- Assembly: the coefficient certificate on L.charpoly plus z in the spectrum gives |Im z| ≤ 1/4. -/theorem order_four_two_fractional_im_le_of_certificate (L : Matrix (Fin 4) (Fin 4) ℝ) (hL : is_standardized_laplacian_two_fractional 4 L) (z : ℂ) (hz : z ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ))) (hcert : let c1 := (L.charpoly).coeff 1 let c2 := (L.charpoly).coeff 2 let c3 := (L.charpoly).coeff 3 (-(11 / 16 : ℝ) ≤ c3 ^ 2 - 3 * c2) ∧ (0 ≤ 4 * (c3 ^ 2 * c2 ^ 2 - 4 * c2 ^ 3 - 4 * c3 ^ 3 * c1 - 27 * c1 ^ 2 + 18 * c1 * c2 * c3) + (c3 ^ 2 - 3 * c2 + 1 / 4) ^ 2)) : |z.im| ≤ 1 / 4 := by dsimp only at hcert obtain ⟨hD, hH⟩ := hcert set c1 := (L.charpoly).coeff 1 set c2 := (L.charpoly).coeff 2 set c3 := (L.charpoly).coeff 3 have hc0 : (L.charpoly).coeff 0 = 0 := by have h0 : (0 : ℂ) ∈ spectrum ℂ (L.map (algebraMap ℝ ℂ)) := standardized_laplacian_order_four_zero_mem_spectrum L hL.1 have h1 : ((L.map (algebraMap ℝ ℂ)).charpoly).IsRoot 0 := Matrix.mem_spectrum_iff_isRoot_charpoly.mp h0 have h2 : ((L.map (algebraMap ℝ ℂ)).charpoly).coeff 0 = 0 := Polynomial.zero_isRoot_iff_coeff_zero_eq_zero.mp h1 rw [Matrix.charpoly_map, Polynomial.coeff_map] at h2 exact (algebraMap ℝ ℂ).injective (by simpa using h2) have hd : L.charpoly.natDegree = 4 := by rw [Matrix.charpoly_natDegree_eq_dim, Fintype.card_fin] have hm : L.charpoly.coeff 4 = 1 := by have h := (Matrix.charpoly_monic L).coeff_natDegree rwa [hd] at h have hpoly : L.charpoly = Polynomial.X^4 + Polynomial.C c3 * Polynomial.X^3 + Polynomial.C c2 * Polynomial.X^2 + Polynomial.C c1 * Polynomial.X := by ext n rcases n with _ | _ | _ | _ | _ | n · simp [hc0] · simp [c1] · simp [c2] · simp [c3] · simp [hm] · have h1 : L.charpoly.coeff (n + 5) = 0 := by apply Polynomial.coeff_eq_zero_of_natDegree_lt omega have h2 : (Polynomial.X^4 + Polynomial.C c3 * Polynomial.X^3 + Polynomial.C c2 * Polynomial.X^2 + Polynomial.C c1 * Polynomial.X : Polynomial ℝ).coeff (n + 5) = 0 := by apply Polynomial.coeff_eq_zero_of_natDegree_lt have : (Polynomial.X^4 + Polynomial.C c3 * Polynomial.X^3 + Polynomial.C c2 * Polynomial.X^2 + Polynomial.C c1 * Polynomial.X : Polynomial ℝ).natDegree ≤ 4 := by compute_degree! omega rw [h1, h2] have hroot : ((L.map (algebraMap ℝ ℂ)).charpoly).IsRoot z := Matrix.mem_spectrum_iff_isRoot_charpoly.mp hz rw [Matrix.charpoly_map, hpoly] at hroot dsimp [Polynomial.IsRoot] at hroot simp only [Polynomial.map_add, Polynomial.map_mul, Polynomial.map_pow, Polynomial.map_X, Polynomial.map_C, Polynomial.eval_add, Polynomial.eval_mul, Polynomial.eval_pow, Polynomial.eval_X, Polynomial.eval_C] at hroot have hfactor : z * (z ^ 3 + (c3 : ℂ) * z ^ 2 + (c2 : ℂ) * z + (c1 : ℂ)) = 0 := by linear_combination hroot rcases mul_eq_zero.mp hfactor with hz0 | hcubic · subst hz0 simp · exact real_cubic_im_le_quarter_of_certificate c1 c2 c3 z hcubic hD hH