two_fractional_order_four_row_boundary_entry
Every row of an order-4 standardized Laplacian with at most two strictly fractional off-diagonal entries has an off-diagonal entry equal to 0 or to -1/4 (i.e. on the boundary of the range [-1/4, 0]).
Statement
theorem two_fractional_order_four_row_boundary_entry (L : Matrix (Fin 4) (Fin 4) ℝ)
(hL : is_standardized_laplacian_two_fractional 4 L) (i : Fin 4) :
∃ j : Fin 4, j ≠ i ∧ (L i j = 0 ∨ L i j = -(1 : ℝ) / 4)- Source
- step towards standardized_laplacian_order_four_two_fractional_im_le
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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].
- Used by 1
- two_fractional_order_four_charpoly_certificate_D_boundFor an order-4 two-fractional standardized Laplacian L, the characteristic-polynomial coefficients c2, c3 satisfy c3^2 - 3 c2 ≥ -11/16.
The proof, explained
The proof proceeds by contradiction. For an order-4 standardized Laplacian, every row contains 3 off-diagonal entries, each constrained to the interval [-1/4, 0]. If no off-diagonal entry in row i is on the boundary (0 or -1/4), all 3 off-diagonal entries must lie strictly inside (-1/4, 0). However, the two-fractional hypothesis restricts the number of such entries in any row to at most 2, producing the arithmetic contradiction 3 ≤ 2.
Assume for contradiction that no off-diagonal entry in row i equals 0 or -1/4, so every off-diagonal entry L i j satisfies L i j ≠ 0 and L i j ≠ -1/4.
We proceed by contradiction using `by_contra`. Pushing the negation through the existential quantifier and the connectives using De Morgan's laws (`not_exists`, `not_and`, `not_or`) leaves the hypothesis that for every index j ≠ i, the entry L i j is neither 0 nor -1/4.
uses
not_exists,not_and,not_orby_contra h simp only [not_exists, not_and, not_or] at h
Define S as the set of strictly fractional off-diagonal indices in row i, and note that |S| ≤ 2.
We define S to be the set of off-diagonal indices j ≠ i such that -1/4 < L i j < 0. By the second property of an order-4 standardized Laplacian with at most two fractional entries (`hL.2 i`), row i has at most 2 such entries, so |S| ≤ 2 after simplifying the cast of 4 to the real numbers (`Nat.cast_ofNat`).
uses
Nat.cast_ofNatset S : Finset (Fin 4) := Finset.univ.filter (fun j : Fin 4 => j ≠ i ∧ -1 / ((4:ℕ):ℝ) < L i j ∧ L i j < 0) with hS have hScard : S.card ≤ 2 := by have h := hL.2 i simpa only [hS, Nat.cast_ofNat] using h
Every off-diagonal index belongs to S, so (Fin 4) \ {i} ⊆ S.
Let j be any index distinct from i (`Finset.mem_erase`). The standardized Laplacian definition (`hL.1.2`) bounds each off-diagonal entry by -1/4 ≤ L i j ≤ 0. Under the contradiction hypothesis, L i j cannot equal -1/4 or 0. Combining these bounds with the inequalities using `lt_of_le_of_ne` yields -1/4 < L i j < 0. Together with j ≠ i and j ∈ Finset.univ (`Finset.mem_univ`), this satisfies the membership condition of S (`Finset.mem_filter`), establishing the inclusion.
uses
Finset.mem_erase,Finset.mem_filter,Finset.mem_univ,lt_of_le_of_nehave hsub : Finset.univ.erase i ⊆ S := by intro j hj rw [Finset.mem_erase] at hj rw [hS, Finset.mem_filter] refine ⟨Finset.mem_univ j, hj.1, ?_, ?_⟩ · exact lt_of_le_of_ne (hL.1.2 i j hj.1.symm).1 (fun hh => (h j hj.1).2 (by rw [← hh]; norm_num)) · exact lt_of_le_of_ne (hL.1.2 i j hj.1.symm).2 (fun hh => (h j hj.1).1 hh)
The cardinality of (Fin 4) \ {i} is 3, contradicting |S| ≤ 2.
Since (Fin 4) \ {i} ⊆ S, its size is at most |S| by `Finset.card_le_card`. Since Fin 4 has 4 elements (`Fintype.card_fin`, `Finset.card_univ`), removing {i} leaves 4 - 1 = 3 elements (`Finset.card_erase_of_mem`). This implies 3 ≤ |S|, directly contradicting |S| ≤ 2; integer linear arithmetic (`omega`) closes the goal.
uses
Finset.card_le_card,Finset.card_erase_of_mem,Finset.card_univ,Fintype.card_finhave hc := Finset.card_le_card hsub rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ] at hc simp only [Fintype.card_fin] at hc omega
not_exists- The negation of an existential quantifier is equivalent to a universal negation: ¬(∃ x, p x) ↔ ∀ x, ¬p x.
not_and- The negation of a conjunction is equivalent to an implication: ¬(a ∧ b) ↔ a → ¬b.
not_or- De Morgan's law: the negation of a disjunction is the conjunction of the negations: ¬(p ∨ q) ↔ ¬p ∧ ¬q.
Nat.cast_ofNat- Coercion of a numeral literal from ℕ into another type preserves the numeral: ↑(OfNat.ofNat n) = OfNat.ofNat n.
Finset.mem_erase- An element a belongs to s.erase b if and only if a ≠ b and a ∈ s.
Finset.mem_filter- An element a belongs to Finset.filter p s if and only if a ∈ s and p a holds.
Finset.mem_univ- Every element of a finite type belongs to Finset.univ.
lt_of_le_of_ne- If a ≤ b and a ≠ b in a partial order, then a < b.
Finset.card_le_card- If s ⊆ t for finsets s and t, then s.card ≤ t.card.
Finset.card_erase_of_mem- Removing an element a ∈ s from a finset s decreases its size by 1: (s.erase a).card = s.card - 1.
Finset.card_univ- The cardinality of Finset.univ equals the cardinality of the underlying finite type: Finset.univ.card = Fintype.card α.
Fintype.card_fin- The cardinality of Fin n is n: Fintype.card (Fin n) = n.
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.
/-- In a two-fractional order-4 standardized Laplacian each row has an off-diagonal entry at 0 or -1/4. -/theorem two_fractional_order_four_row_boundary_entry (L : Matrix (Fin 4) (Fin 4) ℝ) (hL : is_standardized_laplacian_two_fractional 4 L) (i : Fin 4) : ∃ j : Fin 4, j ≠ i ∧ (L i j = 0 ∨ L i j = -(1 : ℝ) / 4) := by by_contra h simp only [not_exists, not_and, not_or] at h set S : Finset (Fin 4) := Finset.univ.filter (fun j : Fin 4 => j ≠ i ∧ -1 / ((4:ℕ):ℝ) < L i j ∧ L i j < 0) with hS have hScard : S.card ≤ 2 := by have h := hL.2 i simpa only [hS, Nat.cast_ofNat] using h have hsub : Finset.univ.erase i ⊆ S := by intro j hj rw [Finset.mem_erase] at hj rw [hS, Finset.mem_filter] refine ⟨Finset.mem_univ j, hj.1, ?_, ?_⟩ · exact lt_of_le_of_ne (hL.1.2 i j hj.1.symm).1 (fun hh => (h j hj.1).2 (by rw [← hh]; norm_num)) · exact lt_of_le_of_ne (hL.1.2 i j hj.1.symm).2 (fun hh => (h j hj.1).1 hh) have hc := Finset.card_le_card hsub rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ] at hc simp only [Fintype.card_fin] at hc omega