AFTD Auto-Formalizing Theoretical Domains

standardized_laplacian_order_four_diagonal_lt_one

theoremverified

Every diagonal entry of an order-four standardized Laplacian is less than one.

Statement

theorem standardized_laplacian_order_four_diagonal_lt_one (L : Matrix (Fin 4) (Fin 4) ℝ)
    (hL : is_standardized_laplacian 4 L) (i : Fin 4) : L i i < 1
Source
Sector-bound formalization for IN-166; arXiv:math/0508176, Theorem 5.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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 uses the two defining conditions of an order-four standardized Laplacian: the row sums are zero, and every off-diagonal entry is at least $-1/4$. Summing this lower bound across the three off-diagonal entries in row $i$ shows that their sum is at least $3 \times (-1/4) = -3/4$. Because the diagonal entry $L_{i, i}$ plus the off-diagonal entries sum to zero, $L_{i, i} \le 3/4$, which is strictly less than $1$.

  1. The $i$-th row sums to 0, and splits into the diagonal entry $L_{i, i}$ and the sum of the off-diagonal entries $\sum_{j \ne i} L_{i, j}$.

    By the definition of a standardized Laplacian, the sum of all entries in row $i$ is zero. Using `Finset.add_sum_erase` and `Finset.mem_univ`, the full row sum is separated into the diagonal term $L_{i, i}$ and the sum over all remaining indices $j \in \mathrm{univ} \setminus \{i\}$.

    lines 3–4

    uses Finset.add_sum_erase, Finset.mem_univ

      have hrow := hL.1 i
      have hsplit := Finset.add_sum_erase Finset.univ (fun j => L i j) (Finset.mem_univ i)
  2. Every off-diagonal entry $L_{i, j}$ with $j \ne i$ is at least $-1/4$.

    For any index $j \in \mathrm{univ} \setminus \{i\}$, `Finset.ne_of_mem_erase` ensures $j \ne i$, so $i \ne j$. The second defining condition of an order-four standardized Laplacian then provides the lower bound $-(1/4) \le L_{i, j}$.

    lines 5–7

    uses Finset.ne_of_mem_erase

      have hbound : ∀ j ∈ Finset.univ.erase i, -(1 : ℝ) / 4 ≤ L i j := by
        intro j hj
        exact (hL.2 i j (Finset.ne_of_mem_erase hj).symm).1
  3. The sum of the constant lower bounds $-1/4$ is at most the sum of the off-diagonal entries $\sum_{j \ne i} L_{i, j}$.

    Summing the pointwise inequality $-(1/4) \le L_{i, j}$ over all off-diagonal indices using `Finset.sum_le_sum` yields $\sum_{j \ne i} (-1/4) \le \sum_{j \ne i} L_{i, j}$.

    line 8

    uses Finset.sum_le_sum

      have hsum := Finset.sum_le_sum hbound
  4. The sum of the off-diagonal entries is at least $-3/4$.

    Erasing one index from the 4-element universe leaves a set of cardinality 3. Rewriting the constant sum using `Finset.sum_const` and `nsmul_eq_mul` gives $3 \cdot (-1/4)$, which evaluates to $-3/4$ via `norm_num`. Substituting this constant sum into the off-diagonal inequality yields $-3/4 \le \sum_{j \ne i} L_{i, j}$.

    lines 9–13

    uses Finset.sum_const, nsmul_eq_mul

      have hcard : (Finset.univ.erase i).card = 3 := by simp
      have hconst : (∑ _j ∈ Finset.univ.erase i, -(1 : ℝ) / 4) = -(3 : ℝ) / 4 := by
        rw [Finset.sum_const, hcard, nsmul_eq_mul]
        norm_num
      rw [hconst] at hsum
  5. The diagonal entry $L_{i, i}$ is strictly less than 1. automation

    Since $L_{i, i} + \sum_{j \ne i} L_{i, j} = 0$ and $\sum_{j \ne i} L_{i, j} \ge -3/4$, it follows that $L_{i, i} \le 3/4 < 1$. Linear arithmetic (`linarith`) combines these inequalities to close the goal.

    line 14

      linarith
Finset.add_sum_erase
For a finite set $s$ and an element $a \in s$, the sum of a function $f$ over $s$ equals $f(a)$ plus the sum of $f$ over $s \setminus \{a\}$.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set `Finset.univ`.
Finset.ne_of_mem_erase
An element belonging to a set with $a$ erased is not equal to $a$.
Finset.sum_le_sum
If $f(x) \le g(x)$ for all $x \in s$, then the sum of $f$ over $s$ is at most the sum of $g$ over $s$.
Finset.sum_const
Summing a constant value $b$ over a finite set $s$ is equivalent to multiplying $b$ by the cardinality of $s$.
nsmul_eq_mul
Natural number scalar multiplication $n \bullet a$ equals the ring product $(\uparrow n) \cdot 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_diagonal_lt_one (L : Matrix (Fin 4) (Fin 4) ℝ)    (hL : is_standardized_laplacian 4 L) (i : Fin 4) : L i i < 1 := by  have hrow := hL.1 i  have hsplit := Finset.add_sum_erase Finset.univ (fun j => L i j) (Finset.mem_univ i)  have hbound : ∀ j ∈ Finset.univ.erase i, -(1 : ℝ) / 4 ≤ L i j := by    intro j hj    exact (hL.2 i j (Finset.ne_of_mem_erase hj).symm).1  have hsum := Finset.sum_le_sum hbound  have hcard : (Finset.univ.erase i).card = 3 := by simp  have hconst : (∑ _j ∈ Finset.univ.erase i, -(1 : ℝ) / 4) = -(3 : ℝ) / 4 := by    rw [Finset.sum_const, hcard, nsmul_eq_mul]    norm_num  rw [hconst] at hsum  linarith
See it in the graphDiscuss this resultChallenge it