AFTD Auto-Formalizing Theoretical Domains

two_fractional_order_four_row_boundary_entry

theoremverified

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

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.

  1. 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.

    lines 5–6

    uses not_exists, not_and, not_or

      by_contra h
      simp only [not_exists, not_and, not_or] at h
  2. 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`).

    lines 7–11

    uses Nat.cast_ofNat

      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
  3. 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.

    lines 12–18

    uses Finset.mem_erase, Finset.mem_filter, Finset.mem_univ, lt_of_le_of_ne

      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)
  4. 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.

    lines 19–22

    uses Finset.card_le_card, Finset.card_erase_of_mem, Finset.card_univ, Fintype.card_fin

      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
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

/-- 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
See it in the graphDiscuss this resultChallenge it