two_fractional_order_four_charpoly_certificate_D_bound
For an order-4 two-fractional standardized Laplacian L, the characteristic-polynomial coefficients c2, c3 satisfy c3^2 - 3 c2 ≥ -11/16.
Statement
theorem two_fractional_order_four_charpoly_certificate_D_bound (L : Matrix (Fin 4) (Fin 4) ℝ)
(hL : is_standardized_laplacian_two_fractional 4 L) :
-(11 / 16 : ℝ) ≤ (L.charpoly).coeff 3 ^ 2 - 3 * (L.charpoly).coeff 2- Source
- step towards standardized_laplacian_order_four_two_fractional_im_le
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- two_fractional_order_four_row_boundary_entryEvery row of an order-4 standardized Laplacian with at most two strictly fractional off-diagonal entries has an off-diagonal entry equal…
- 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
The certificate bound c3^2 - 3 c2 ≥ -11/16 is proved by expressing the characteristic-polynomial coefficients in terms of matrix traces: c3 = -tr(L) and c2 = (tr(L)^2 - tr(L^2))/2, so that c3^2 - 3 c2 = (3 tr(L^2) - tr(L)^2)/2. Letting b_i = L i i ≥ 0 and P = ∑_{i < j} (-L i j)(-L j i), this quantity becomes 3P + (3 ∑ b_i^2 - (∑ b_i)^2)/2. The entrywise bounds 0 ≤ -L i j ≤ 1/4 yield ∑ b_i ≤ 3 and, via the nonnegativity of (1/4 - (-L i j))(1/4 - (-L j i)), the key coupling 16P ≥ 4 ∑ b_i - 6. Finally, Cauchy-Schwarz gives (∑ b_i)^2 ≤ 4 ∑ b_i^2, and a case split on whether ∑ b_i ≤ 3/2 establishes the lower bound -11/16 by non-linear arithmetic.
The determinant of a 2×2 matrix A on a two-element type {a, b} equals A a a * A b b - A a b * A b a modulo an equivalence with Fin 2
The cardinality of the type is 2 (Finset.card_pair, Finset.card_univ), yielding an equivalence e with Fin 2. Reindexing rows and columns via e preserves the determinant (Matrix.det_submatrix_equiv_self), reducing it to the canonical 2×2 determinant formula on Fin 2 (Matrix.det_fin_two).
uses
Finset.card_pair,Finset.card_univ,Matrix.det_fin_two,Matrix.det_submatrix_equiv_selfhave hcard : Fintype.card α = 2 := by rw [← Finset.card_univ, huniv, Finset.card_pair hab] let e : α ≃ Fin 2 := Fintype.equivFinOfCardEq hcard have hA : A = (A.submatrix e.symm e.symm).submatrix e e := by ext i j; simp rw [hA, Matrix.det_submatrix_equiv_self e, Matrix.det_fin_two]
Evaluating the submatrix determinant entries on the images of 0 and 1 yields A a a * A b b - A a b * A b a
Since e is bijective, e.symm 0 and e.symm 1 are distinct elements of {a, b} (Finset.mem_univ). Case analysis on their values shows they are either (a, b) or (b, a). In both cases, expanding the submatrix entries (Matrix.submatrix_apply, Equiv.symm_apply_apply) gives A a a * A b b - A a b * A b a by ring arithmetic.
uses
Equiv.symm_apply_apply,Finset.mem_univ,Matrix.submatrix_applyhave h01 : e.symm 0 ≠ e.symm 1 := by intro h; exact (by decide : (0:Fin 2) ≠ 1) (e.symm.injective h) have key : ∀ x : Fin 2, e.symm x = a ∨ e.symm x = b := by intro x have hx : e.symm x ∈ ({a, b} : Finset α) := by rw [← huniv]; exact Finset.mem_univ _ rcases Finset.mem_insert.mp hx with h | h · exact Or.inl h · exact Or.inr (Finset.mem_singleton.mp h) rcases key 0 with h0 | h0 <;> rcases key 1 with h1 | h1 · exact absurd (h0.trans h1.symm) h01 · simp only [Matrix.submatrix_apply, h0, h1, Equiv.symm_apply_apply] · simp only [Matrix.submatrix_apply, h0, h1, Equiv.symm_apply_apply]; ring · exact absurd (h0.trans h1.symm) h01
For any distinct indices i ≠ j in Fin 4, the determinant of the 2×2 principal submatrix on {i, j} is L i i * L j j - L i j * L j i
We apply the previous two-element determinant lemma to the subtype corresponding to {i, j}. The distinctness of i and j ensures the canonical subtype elements are distinct, and Finset.eq_univ_of_forall together with Subtype.ext verifies that {i, j} exhausts the subtype universe.
uses
Finset.eq_univ_of_forall,Subtype.ext,two_fractional_order_four_charpoly_certificate_D_bound_det_two_card_tworefine two_fractional_order_four_charpoly_certificate_D_bound_det_two_card_two (α := ({i,j} : Finset (Fin 4))) _ ⟨i, by simp⟩ ⟨j, by simp⟩ ?_ ?_ · intro h; exact hij (congrArg Subtype.val h) · apply (Finset.eq_univ_of_forall ?_).symm intro x have hx : (x : Fin 4) = i ∨ (x : Fin 4) = j := by rcases Finset.mem_insert.mp x.2 with h | h · exact Or.inl h · exact Or.inr (Finset.mem_singleton.mp h) have hmem : x ∈ ({⟨i, by simp⟩, ⟨j, by simp⟩} : Finset ({i,j} : Finset (Fin 4))) := by rcases hx with h | h · rw [Finset.mem_insert]; left; exact Subtype.ext h · rw [Finset.mem_insert]; right; rw [Finset.mem_singleton]; exact Subtype.ext h simpa using hmem
The sum of any function f over all 2-element subsets of Fin 4 expands into the sum of the six pairs
The set of 2-element subsets of Fin 4 is decided to be exactly the six pairs {0,1}, {0,2}, {0,3}, {1,2}, {1,3}, and {2,3}. Successively extracting each element with Finset.sum_insert and finishing with Finset.sum_singleton produces the explicit six-term sum.
uses
Finset.sum_insert,Finset.sum_singletonhave hp : (Finset.univ : Finset (Fin 4)).powersetCard 2 = ({({0,1} : Finset (Fin 4)), {0,2}, {0,3}, {1,2}, {1,3}, {2,3}} : Finset (Finset (Fin 4))) := by decide rw [hp] rw [Finset.sum_insert (by decide), Finset.sum_insert (by decide), Finset.sum_insert (by decide), Finset.sum_insert (by decide), Finset.sum_insert (by decide), Finset.sum_singleton] ring
The characteristic polynomial coefficient c2 of L equals the sum of all six 2×2 principal minors
By Matrix.charpoly_coeff_eq_sum_minors at k = 2 and Fintype.card_fin, the coefficient at degree 4 - 2 = 2 equals (-1)^2 times the sum of the determinants of all 2×2 principal submatrices.
uses
Fintype.card_fin,Matrix.charpoly_coeff_eq_sum_minorshave h := Matrix.charpoly_coeff_eq_sum_minors (M := L) 2 (by norm_num : 2 ≤ Fintype.card (Fin 4)) simp only [Fintype.card_fin] at h rw [show (4 - 2 : ℕ) = 2 from rfl] at h rw [h]
The coefficient c2 equals (tr(L)^2 - tr(L^2)) / 2
We rewrite the sum of minors using two_fractional_order_four_charpoly_certificate_D_bound_sum_powerset_two and evaluate each 2×2 determinant using two_fractional_order_four_charpoly_certificate_D_bound_det_pp. Expanding the definitions of matrix trace, diagonal, and product on Fin 4 (Matrix.trace, Matrix.diag, Matrix.mul_apply, Fin.sum_univ_four), ring algebra confirms that this sum matches (tr(L)^2 - tr(L^2)) / 2.
uses
Fin.sum_univ_four,Matrix.diag,Matrix.mul_apply,Matrix.trace,two_fractional_order_four_charpoly_certificate_D_bound_det_pp,two_fractional_order_four_charpoly_certificate_D_bound_sum_powerset_twohave hp2 : (∑ s ∈ (Finset.univ : Finset (Fin 4)).powersetCard 2, (L.submatrix (Subtype.val : s → Fin 4) (Subtype.val : s → Fin 4)).det) = ((L.trace ^ 2 - (L * L).trace) / 2) := by rw [two_fractional_order_four_charpoly_certificate_D_bound_sum_powerset_two] rw [two_fractional_order_four_charpoly_certificate_D_bound_det_pp L 0 1 (by decide), two_fractional_order_four_charpoly_certificate_D_bound_det_pp L 0 2 (by decide), two_fractional_order_four_charpoly_certificate_D_bound_det_pp L 0 3 (by decide), two_fractional_order_four_charpoly_certificate_D_bound_det_pp L 1 2 (by decide), two_fractional_order_four_charpoly_certificate_D_bound_det_pp L 1 3 (by decide), two_fractional_order_four_charpoly_certificate_D_bound_det_pp L 2 3 (by decide)] simp only [Matrix.trace, Matrix.diag, Matrix.mul_apply, Fin.sum_univ_four] ring rw [hp2]; norm_num
The Cauchy-Schwarz inequality (∑ b_i)^2 ≤ 4 ∑ b_i^2 holds, and the expression decomposes into 3P + (3 ∑ b_i^2 - (∑ b_i)^2)/2
Summing the nonnegativity of all six pairwise squared differences (b_i - b_j)^2 ≥ 0 via sq_nonneg establishes (b0 + b1 + b2 + b3)^2 ≤ 4 (b0^2 + b1^2 + b2^2 + b3^2). Elementary algebra splits the fraction into 3P plus the quadratic form in the b_i.
uses
sq_nonneghave hsq : (b0 + b1 + b2 + b3) ^ 2 ≤ 4 * (b0 ^ 2 + b1 ^ 2 + b2 ^ 2 + b3 ^ 2) := by nlinarith [sq_nonneg (b0 - b1), sq_nonneg (b0 - b2), sq_nonneg (b0 - b3), sq_nonneg (b1 - b2), sq_nonneg (b1 - b3), sq_nonneg (b2 - b3)] have hTn : 0 ≤ b0 + b1 + b2 + b3 := by linarith rw [show (3 * (b0 ^ 2 + b1 ^ 2 + b2 ^ 2 + b3 ^ 2 + 2 * P) - (b0 + b1 + b2 + b3) ^ 2) / 2 = 3 * P + (3 * (b0 ^ 2 + b1 ^ 2 + b2 ^ 2 + b3 ^ 2) - (b0 + b1 + b2 + b3) ^ 2) / 2 from by ring]
Under the numeric hypotheses on b_i and P, the expression is bounded below by -11/16 automation
We split into cases on whether T = b0 + b1 + b2 + b3 ≤ 3/2. If T ≤ 3/2, using P ≥ 0 and the Cauchy-Schwarz bound ∑ b_i^2 ≥ T^2/4, nlinarith shows the expression is at least -T^2/8 ≥ -9/32 ≥ -11/16. If T > 3/2, using 16P ≥ 4T - 6 and T ≤ 3, nlinarith similarly verifies that the resulting quadratic in T is bounded below by -11/16.
by_cases hc : b0 + b1 + b2 + b3 ≤ 3/2 · nlinarith [hsq, hP0, hc, hTn] · push Not at hc nlinarith [hsq, hP16, hc, hTle]
The off-diagonal entries satisfy 0 ≤ -L i j ≤ 1/4 and row sums are zero
By definition of a standardized Laplacian, off-diagonal entries satisfy -1/4 ≤ L i j ≤ 0, so 0 ≤ -L i j ≤ 1/4. The zero row-sum property ∑_j L i j = 0 is expanded over Fin 4 via Fin.sum_univ_four.
uses
Fin.sum_univ_fourhave hb : ∀ i j : Fin 4, i ≠ j → (0:ℝ) ≤ -L i j ∧ -L i j ≤ 1/4 := by intro i j hij have h := hL.1.2 i j hij constructor <;> linarith [h.1, h.2] have hr : ∀ i : Fin 4, L i 0 + L i 1 + L i 2 + L i 3 = 0 := by intro i; have h := hL.1.1 i; simpa [Fin.sum_univ_four] using h
c3^2 - 3 c2 expresses in terms of traces as (3 tr(L^2) - tr(L)^2) / 2
By Matrix.trace_eq_neg_charpoly_coeff and Fintype.card_fin, c3 = -tr(L). Substituting this and the formula for c2 from two_fractional_order_four_charpoly_certificate_D_bound_coeff_two, ring algebra simplifies (-tr(L))^2 - 3(tr(L)^2 - tr(L^2))/2 to (3 tr(L^2) - tr(L)^2) / 2.
uses
Fintype.card_fin,Matrix.trace_eq_neg_charpoly_coeff,two_fractional_order_four_charpoly_certificate_D_bound_coeff_twohave hc3 : (L.charpoly).coeff 3 = -L.trace := by have h := Matrix.trace_eq_neg_charpoly_coeff (M := L) simp only [Fintype.card_fin] at h; linarith have hc2 := two_fractional_order_four_charpoly_certificate_D_bound_coeff_two L have hgoal : (L.charpoly).coeff 3 ^ 2 - 3 * (L.charpoly).coeff 2 = (3 * (L * L).trace - L.trace ^ 2) / 2 := by rw [hc3, hc2]; ring rw [hgoal]
Diagonal entries and traces are expressed in terms of off-diagonal negatives and their products
From the zero row sums, each diagonal entry L i i equals the sum of the negatives of the off-diagonal entries in that row. Expanding tr(L^2) and tr(L) via Matrix.trace, Matrix.diag, Matrix.mul_apply, and Fin.sum_univ_four reveals that tr(L^2) = ∑ L i i^2 + 2P where P = ∑_{i < j} (-L i j)(-L j i), and tr(L) = ∑ L i i.
uses
Fin.sum_univ_four,Matrix.diag,Matrix.mul_apply,Matrix.tracehave hd0 : L 0 0 = (-L 0 1) + (-L 0 2) + (-L 0 3) := by linarith [hr 0] have hd1 : L 1 1 = (-L 1 0) + (-L 1 2) + (-L 1 3) := by linarith [hr 1] have hd2 : L 2 2 = (-L 2 0) + (-L 2 1) + (-L 2 3) := by linarith [hr 2] have hd3 : L 3 3 = (-L 3 0) + (-L 3 1) + (-L 3 2) := by linarith [hr 3] have htr : (L * L).trace = L 0 0 ^ 2 + L 1 1 ^ 2 + L 2 2 ^ 2 + L 3 3 ^ 2 + 2 * ((-L 0 1) * (-L 1 0) + (-L 0 2) * (-L 2 0) + (-L 0 3) * (-L 3 0) + (-L 1 2) * (-L 2 1) + (-L 1 3) * (-L 3 1) + (-L 2 3) * (-L 3 2)) := by simp only [Matrix.trace, Matrix.diag, Matrix.mul_apply, Fin.sum_univ_four] ring have hT : L.trace = L 0 0 + L 1 1 + L 2 2 + L 3 3 := by simp [Matrix.trace, Matrix.diag, Fin.sum_univ_four] rw [htr, hT, hd0, hd1, hd2, hd3]
The problem reduces to verifying 4T - 6 ≤ 16P via the numeric lemma
We instantiate the entrywise bounds 0 ≤ -L i j ≤ 1/4 for all pairs. Setting b_i = L i i, each b_i is nonnegative, P is nonnegative by positivity, and T = ∑ b_i ≤ 12 * (1/4) = 3. Invoking two_fractional_order_four_charpoly_certificate_D_bound_numeric reduces the goal to proving 4T - 6 ≤ 16P.
uses
two_fractional_order_four_charpoly_certificate_D_bound_numericobtain ⟨e01, e01'⟩ := hb 0 1 (by decide) obtain ⟨e02, e02'⟩ := hb 0 2 (by decide) obtain ⟨e03, e03'⟩ := hb 0 3 (by decide) obtain ⟨e10, e10'⟩ := hb 1 0 (by decide) obtain ⟨e12, e12'⟩ := hb 1 2 (by decide) obtain ⟨e13, e13'⟩ := hb 1 3 (by decide) obtain ⟨e20, e20'⟩ := hb 2 0 (by decide) obtain ⟨e21, e21'⟩ := hb 2 1 (by decide) obtain ⟨e23, e23'⟩ := hb 2 3 (by decide) obtain ⟨e30, e30'⟩ := hb 3 0 (by decide) obtain ⟨e31, e31'⟩ := hb 3 1 (by decide) obtain ⟨e32, e32'⟩ := hb 3 2 (by decide) refine two_fractional_order_four_charpoly_certificate_D_bound_numeric ((-L 0 1) + (-L 0 2) + (-L 0 3)) ((-L 1 0) + (-L 1 2) + (-L 1 3)) ((-L 2 0) + (-L 2 1) + (-L 2 3)) ((-L 3 0) + (-L 3 1) + (-L 3 2)) ((-L 0 1) * (-L 1 0) + (-L 0 2) * (-L 2 0) + (-L 0 3) * (-L 3 0) + (-L 1 2) * (-L 2 1) + (-L 1 3) * (-L 3 1) + (-L 2 3) * (-L 3 2)) (by linarith) (by linarith) (by linarith) (by linarith) (by positivity) ?_ (by linarith)
The inequality 4T - 6 ≤ 16P holds, concluding the bound -11/16
For each of the six pairs {i, j}, since -L i j ≤ 1/4 and -L j i ≤ 1/4, the product (1/4 - (-L i j)) * (1/4 - (-L j i)) is nonnegative (mul_nonneg). Summing these six products expands to 6/16 - T/4 + P ≥ 0, which rearranges to 16P ≥ 4T - 6. The tactic nlinarith concludes the inequality and establishes -(11/16) ≤ c3^2 - 3 c2.
uses
mul_nonneg· have p01 : 0 ≤ (1/4 - (-L 0 1)) * (1/4 - (-L 1 0)) := mul_nonneg (by linarith) (by linarith) have p02 : 0 ≤ (1/4 - (-L 0 2)) * (1/4 - (-L 2 0)) := mul_nonneg (by linarith) (by linarith) have p03 : 0 ≤ (1/4 - (-L 0 3)) * (1/4 - (-L 3 0)) := mul_nonneg (by linarith) (by linarith) have p12 : 0 ≤ (1/4 - (-L 1 2)) * (1/4 - (-L 2 1)) := mul_nonneg (by linarith) (by linarith) have p13 : 0 ≤ (1/4 - (-L 1 3)) * (1/4 - (-L 3 1)) := mul_nonneg (by linarith) (by linarith) have p23 : 0 ≤ (1/4 - (-L 2 3)) * (1/4 - (-L 3 2)) := mul_nonneg (by linarith) (by linarith) nlinarith
Matrix.det_fin_two- The determinant of a 2×2 matrix indexed by Fin 2 is A 0 0 * A 1 1 - A 0 1 * A 1 0.
Matrix.det_submatrix_equiv_self- Reindexing both rows and columns of a square matrix by an equivalence of index types preserves the determinant.
Matrix.diag- The diagonal of a square matrix maps each index i to the entry A i i.
Matrix.mul_apply- The (i, k) entry of the matrix product M * N is the sum over j of M i j * N j k.
Matrix.trace- The trace of a square matrix is the sum of its diagonal entries.
Matrix.charpoly_coeff_eq_sum_minors- For k ≤ n, the coefficient of X^(n - k) in the characteristic polynomial of an n×n matrix equals (-1)^k times the sum of the determinants of all k×k principal submatrices.
Matrix.trace_eq_neg_charpoly_coeff- The trace of an n×n matrix equals the negative of the coefficient of X^(n-1) in its characteristic polynomial.
Matrix.submatrix_apply- Entry (i, j) of the submatrix of A with row map r and column map c is A (r i) (c j).
Equiv.symm_apply_apply- Applying the inverse of an equivalence to the image of an element yields the original element: e.symm (e x) = x.
Fin.sum_univ_four- The sum of a function over Fin 4 equals f 0 + f 1 + f 2 + f 3.
Finset.card_pair- For distinct elements a ≠ b, the cardinality of the pair set {a, b} is 2.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the cardinality of the type.
Finset.eq_univ_of_forall- A subset of a finite type containing every element equals the universal set Finset.univ.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
Finset.sum_insert- If a ∉ s, then the sum of f over insert a s equals f a plus the sum of f over s.
Finset.sum_singleton- The sum of a function over a singleton set {a} equals f a.
Fintype.card_fin- The cardinality of the finite type Fin n is n.
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
mul_nonneg- The product of two nonnegative real numbers is nonnegative.
sq_nonneg- The square of any real number is nonnegative: a^2 ≥ 0.
two_fractional_order_four_charpoly_certificate_D_bound_coeff_two- For a 4×4 real matrix L, the coefficient of X^2 in its characteristic polynomial is (tr(L)^2 - tr(L^2)) / 2.
two_fractional_order_four_charpoly_certificate_D_bound_numeric- For nonnegative b0, b1, b2, b3, P with ∑ b_i ≤ 3 and 16 P ≥ 4 ∑ b_i - 6, the expression (3(∑ b_i^2 + 2P) - (∑ b_i)^2)/2 is at least -11/16.
two_fractional_order_four_charpoly_certificate_D_bound_det_pp- For distinct indices i ≠ j in Fin 4, the determinant of the 2×2 principal submatrix indexed by {i, j} equals L i i * L j j - L i j * L j i.
two_fractional_order_four_charpoly_certificate_D_bound_det_two_card_two- The determinant of any matrix over a 2-element type {a, b} equals A a a * A b b - A a b * A b a.
two_fractional_order_four_charpoly_certificate_D_bound_sum_powerset_two- The sum of a function over the 2-element subsets of Fin 4 equals the sum of the values on the six pairs {0,1}, {0,2}, {0,3}, {1,2}, {1,3}, and {2,3}.
- The non-linear inequalities in step 8 and step 13 are discharged by the `nlinarith` tactic, which verifies real polynomial inequalities from nonnegativity of squares and given bounds without producing an explicit paper-style calculation.
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.
private lemma two_fractional_order_four_charpoly_certificate_D_bound_det_two_card_two {α : Type*} [Fintype α] [DecidableEq α] (A : Matrix α α ℝ) (a b : α) (hab : a ≠ b) (huniv : (Finset.univ : Finset α) = {a, b}) : A.det = A a a * A b b - A a b * A b a := by have hcard : Fintype.card α = 2 := by rw [← Finset.card_univ, huniv, Finset.card_pair hab] let e : α ≃ Fin 2 := Fintype.equivFinOfCardEq hcard have hA : A = (A.submatrix e.symm e.symm).submatrix e e := by ext i j; simp rw [hA, Matrix.det_submatrix_equiv_self e, Matrix.det_fin_two] have h01 : e.symm 0 ≠ e.symm 1 := by intro h; exact (by decide : (0:Fin 2) ≠ 1) (e.symm.injective h) have key : ∀ x : Fin 2, e.symm x = a ∨ e.symm x = b := by intro x have hx : e.symm x ∈ ({a, b} : Finset α) := by rw [← huniv]; exact Finset.mem_univ _ rcases Finset.mem_insert.mp hx with h | h · exact Or.inl h · exact Or.inr (Finset.mem_singleton.mp h) rcases key 0 with h0 | h0 <;> rcases key 1 with h1 | h1 · exact absurd (h0.trans h1.symm) h01 · simp only [Matrix.submatrix_apply, h0, h1, Equiv.symm_apply_apply] · simp only [Matrix.submatrix_apply, h0, h1, Equiv.symm_apply_apply]; ring · exact absurd (h0.trans h1.symm) h01private lemma two_fractional_order_four_charpoly_certificate_D_bound_det_pp (L : Matrix (Fin 4) (Fin 4) ℝ) (i j : Fin 4) (hij : i ≠ j) : (L.submatrix (Subtype.val : ({i,j} : Finset (Fin 4)) → Fin 4) (Subtype.val : ({i,j} : Finset (Fin 4)) → Fin 4)).det = L i i * L j j - L i j * L j i := by refine two_fractional_order_four_charpoly_certificate_D_bound_det_two_card_two (α := ({i,j} : Finset (Fin 4))) _ ⟨i, by simp⟩ ⟨j, by simp⟩ ?_ ?_ · intro h; exact hij (congrArg Subtype.val h) · apply (Finset.eq_univ_of_forall ?_).symm intro x have hx : (x : Fin 4) = i ∨ (x : Fin 4) = j := by rcases Finset.mem_insert.mp x.2 with h | h · exact Or.inl h · exact Or.inr (Finset.mem_singleton.mp h) have hmem : x ∈ ({⟨i, by simp⟩, ⟨j, by simp⟩} : Finset ({i,j} : Finset (Fin 4))) := by rcases hx with h | h · rw [Finset.mem_insert]; left; exact Subtype.ext h · rw [Finset.mem_insert]; right; rw [Finset.mem_singleton]; exact Subtype.ext h simpa using hmemprivate lemma two_fractional_order_four_charpoly_certificate_D_bound_sum_powerset_two (f : Finset (Fin 4) → ℝ) : (∑ s ∈ (Finset.univ : Finset (Fin 4)).powersetCard 2, f s) = f {0,1} + f {0,2} + f {0,3} + f {1,2} + f {1,3} + f {2,3} := by have hp : (Finset.univ : Finset (Fin 4)).powersetCard 2 = ({({0,1} : Finset (Fin 4)), {0,2}, {0,3}, {1,2}, {1,3}, {2,3}} : Finset (Finset (Fin 4))) := by decide rw [hp] rw [Finset.sum_insert (by decide), Finset.sum_insert (by decide), Finset.sum_insert (by decide), Finset.sum_insert (by decide), Finset.sum_insert (by decide), Finset.sum_singleton] ringprivate lemma two_fractional_order_four_charpoly_certificate_D_bound_coeff_two (L : Matrix (Fin 4) (Fin 4) ℝ) : L.charpoly.coeff 2 = (L.trace ^ 2 - (L * L).trace) / 2 := by have h := Matrix.charpoly_coeff_eq_sum_minors (M := L) 2 (by norm_num : 2 ≤ Fintype.card (Fin 4)) simp only [Fintype.card_fin] at h rw [show (4 - 2 : ℕ) = 2 from rfl] at h rw [h] have hp2 : (∑ s ∈ (Finset.univ : Finset (Fin 4)).powersetCard 2, (L.submatrix (Subtype.val : s → Fin 4) (Subtype.val : s → Fin 4)).det) = ((L.trace ^ 2 - (L * L).trace) / 2) := by rw [two_fractional_order_four_charpoly_certificate_D_bound_sum_powerset_two] rw [two_fractional_order_four_charpoly_certificate_D_bound_det_pp L 0 1 (by decide), two_fractional_order_four_charpoly_certificate_D_bound_det_pp L 0 2 (by decide), two_fractional_order_four_charpoly_certificate_D_bound_det_pp L 0 3 (by decide), two_fractional_order_four_charpoly_certificate_D_bound_det_pp L 1 2 (by decide), two_fractional_order_four_charpoly_certificate_D_bound_det_pp L 1 3 (by decide), two_fractional_order_four_charpoly_certificate_D_bound_det_pp L 2 3 (by decide)] simp only [Matrix.trace, Matrix.diag, Matrix.mul_apply, Fin.sum_univ_four] ring rw [hp2]; norm_numprivate lemma two_fractional_order_four_charpoly_certificate_D_bound_numeric (b0 b1 b2 b3 P : ℝ) (hb0 : 0 ≤ b0) (hb1 : 0 ≤ b1) (hb2 : 0 ≤ b2) (hb3 : 0 ≤ b3) (hP0 : 0 ≤ P) (hP16 : 4 * (b0 + b1 + b2 + b3) - 6 ≤ 16 * P) (hTle : b0 + b1 + b2 + b3 ≤ 3) : -(11 / 16 : ℝ) ≤ (3 * (b0 ^ 2 + b1 ^ 2 + b2 ^ 2 + b3 ^ 2 + 2 * P) - (b0 + b1 + b2 + b3) ^ 2) / 2 := by have hsq : (b0 + b1 + b2 + b3) ^ 2 ≤ 4 * (b0 ^ 2 + b1 ^ 2 + b2 ^ 2 + b3 ^ 2) := by nlinarith [sq_nonneg (b0 - b1), sq_nonneg (b0 - b2), sq_nonneg (b0 - b3), sq_nonneg (b1 - b2), sq_nonneg (b1 - b3), sq_nonneg (b2 - b3)] have hTn : 0 ≤ b0 + b1 + b2 + b3 := by linarith rw [show (3 * (b0 ^ 2 + b1 ^ 2 + b2 ^ 2 + b3 ^ 2 + 2 * P) - (b0 + b1 + b2 + b3) ^ 2) / 2 = 3 * P + (3 * (b0 ^ 2 + b1 ^ 2 + b2 ^ 2 + b3 ^ 2) - (b0 + b1 + b2 + b3) ^ 2) / 2 from by ring] by_cases hc : b0 + b1 + b2 + b3 ≤ 3/2 · nlinarith [hsq, hP0, hc, hTn] · push Not at hc nlinarith [hsq, hP16, hc, hTle]/-- First half of the charpoly certificate: c3^2 - 3c2 ≥ -11/16 for two-fractional order-4 standardized Laplacians. -/theorem two_fractional_order_four_charpoly_certificate_D_bound (L : Matrix (Fin 4) (Fin 4) ℝ) (hL : is_standardized_laplacian_two_fractional 4 L) : -(11 / 16 : ℝ) ≤ (L.charpoly).coeff 3 ^ 2 - 3 * (L.charpoly).coeff 2 := by have hb : ∀ i j : Fin 4, i ≠ j → (0:ℝ) ≤ -L i j ∧ -L i j ≤ 1/4 := by intro i j hij have h := hL.1.2 i j hij constructor <;> linarith [h.1, h.2] have hr : ∀ i : Fin 4, L i 0 + L i 1 + L i 2 + L i 3 = 0 := by intro i; have h := hL.1.1 i; simpa [Fin.sum_univ_four] using h have hc3 : (L.charpoly).coeff 3 = -L.trace := by have h := Matrix.trace_eq_neg_charpoly_coeff (M := L) simp only [Fintype.card_fin] at h; linarith have hc2 := two_fractional_order_four_charpoly_certificate_D_bound_coeff_two L have hgoal : (L.charpoly).coeff 3 ^ 2 - 3 * (L.charpoly).coeff 2 = (3 * (L * L).trace - L.trace ^ 2) / 2 := by rw [hc3, hc2]; ring rw [hgoal] have hd0 : L 0 0 = (-L 0 1) + (-L 0 2) + (-L 0 3) := by linarith [hr 0] have hd1 : L 1 1 = (-L 1 0) + (-L 1 2) + (-L 1 3) := by linarith [hr 1] have hd2 : L 2 2 = (-L 2 0) + (-L 2 1) + (-L 2 3) := by linarith [hr 2] have hd3 : L 3 3 = (-L 3 0) + (-L 3 1) + (-L 3 2) := by linarith [hr 3] have htr : (L * L).trace = L 0 0 ^ 2 + L 1 1 ^ 2 + L 2 2 ^ 2 + L 3 3 ^ 2 + 2 * ((-L 0 1) * (-L 1 0) + (-L 0 2) * (-L 2 0) + (-L 0 3) * (-L 3 0) + (-L 1 2) * (-L 2 1) + (-L 1 3) * (-L 3 1) + (-L 2 3) * (-L 3 2)) := by simp only [Matrix.trace, Matrix.diag, Matrix.mul_apply, Fin.sum_univ_four] ring have hT : L.trace = L 0 0 + L 1 1 + L 2 2 + L 3 3 := by simp [Matrix.trace, Matrix.diag, Fin.sum_univ_four] rw [htr, hT, hd0, hd1, hd2, hd3] obtain ⟨e01, e01'⟩ := hb 0 1 (by decide) obtain ⟨e02, e02'⟩ := hb 0 2 (by decide) obtain ⟨e03, e03'⟩ := hb 0 3 (by decide) obtain ⟨e10, e10'⟩ := hb 1 0 (by decide) obtain ⟨e12, e12'⟩ := hb 1 2 (by decide) obtain ⟨e13, e13'⟩ := hb 1 3 (by decide) obtain ⟨e20, e20'⟩ := hb 2 0 (by decide) obtain ⟨e21, e21'⟩ := hb 2 1 (by decide) obtain ⟨e23, e23'⟩ := hb 2 3 (by decide) obtain ⟨e30, e30'⟩ := hb 3 0 (by decide) obtain ⟨e31, e31'⟩ := hb 3 1 (by decide) obtain ⟨e32, e32'⟩ := hb 3 2 (by decide) refine two_fractional_order_four_charpoly_certificate_D_bound_numeric ((-L 0 1) + (-L 0 2) + (-L 0 3)) ((-L 1 0) + (-L 1 2) + (-L 1 3)) ((-L 2 0) + (-L 2 1) + (-L 2 3)) ((-L 3 0) + (-L 3 1) + (-L 3 2)) ((-L 0 1) * (-L 1 0) + (-L 0 2) * (-L 2 0) + (-L 0 3) * (-L 3 0) + (-L 1 2) * (-L 2 1) + (-L 1 3) * (-L 3 1) + (-L 2 3) * (-L 3 2)) (by linarith) (by linarith) (by linarith) (by linarith) (by positivity) ?_ (by linarith) · have p01 : 0 ≤ (1/4 - (-L 0 1)) * (1/4 - (-L 1 0)) := mul_nonneg (by linarith) (by linarith) have p02 : 0 ≤ (1/4 - (-L 0 2)) * (1/4 - (-L 2 0)) := mul_nonneg (by linarith) (by linarith) have p03 : 0 ≤ (1/4 - (-L 0 3)) * (1/4 - (-L 3 0)) := mul_nonneg (by linarith) (by linarith) have p12 : 0 ≤ (1/4 - (-L 1 2)) * (1/4 - (-L 2 1)) := mul_nonneg (by linarith) (by linarith) have p13 : 0 ≤ (1/4 - (-L 1 3)) * (1/4 - (-L 3 1)) := mul_nonneg (by linarith) (by linarith) have p23 : 0 ≤ (1/4 - (-L 2 3)) * (1/4 - (-L 3 2)) := mul_nonneg (by linarith) (by linarith) nlinarith