AFTD Auto-Formalizing Theoretical Domains

regular_graph_lap_mul_pow_scalar_sub_all_ones_trace

theoremverifiedformalization

For each d-regular graph G on n vertices and each pair of positive integers i and j, the trace of L(G)^i ((d+1)I_n - J_n)^j equals (d+1)^j ℓ_i(G), where J_n is the all-ones matrix and ℓ_i(G) is the Laplacian trace sequence.

Statement

open scoped Classical in
theorem regular_graph_lap_mul_pow_scalar_sub_all_ones_trace
    {V : Type*} [Fintype V] (d : ℕ) (G : SimpleGraph V)
    (hreg : G.IsRegularOfDegree d) (i j : ℕ+) :
    Matrix.trace (((G.lapMatrix ℝ) ^ (i : ℕ)) *
      (((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ)) ^ (j : ℕ))) =
    ((d + 1 : ℝ) ^ (j : ℕ)) * graph_lap_trace_seq G i
Formalizes
arXiv:2610.36127 Lemma 34
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • graph_lap_trace_seqFor a graph G on a finite vertex set V, its Laplacian trace sequence (ℓ_i(G))_{i=1}^∞ is the sequence of real numbers tr(L(G)^i) for…

Read back from the Lean

For any finite type $V$, natural number $d$, simple graph $G$ on $V$ such that $G$ is regular of degree $d$, and any positive integers $i$ and $j$: The trace of the matrix product $$(L^i) \cdot \left((d + 1) I - J\right)^j$$ equals $$(d + 1)^j \cdot \operatorname{graph\_lap\_trace\_seq}(G, i),$$ where: - $L = G.\text{lapMatrix } \mathbb{R}$ is the real Laplacian matrix of $G$, - $I$ is the identity matrix on $V$, - $J$ is the all-ones matrix on $V \times V$ (Matrix.of fun _ _ ↦ 1), - matrix powers and products are taken in $\mathrm{Matrix}(V, V, \mathbb{R})$, and - $\operatorname{graph\_lap\_trace\_seq}(G, i)$ is the trace of $L^i$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem is proved by first showing that any matrix L annihilating the all-ones matrix J satisfies L ((d+1)I - J)^j = (d+1)^j L by induction on j, because L ((d+1)I - J) = (d+1)L - LJ = (d+1)L. Factoring L^i = L^(i-1) L for positive i extends this to L^i ((d+1)I - J)^j = (d+1)^j L^i, from which taking traces yields tr(L^i ((d+1)I - J)^j) = (d+1)^j tr(L^i). Finally, since the row sums of any graph Laplacian are zero, L(G) J = 0 holds, and applying the general trace identity to L(G) gives the desired formula (d+1)^j ℓ_i(G).

  1. For the base case j = 0, L ((d+1)I - J)^0 = (d+1)^0 • L holds. automation

    By induction on j. When j = 0, the matrix power ((d+1)I - J)^0 is the identity matrix and (d+1)^0 = 1, so both sides simplify to L.

    lines 7–8

      induction j with
      | zero => simp
  2. If L * J = 0, then L * ((d+1)I - J)^j = (d+1)^j • L for all j ∈ ℕ.

    For the inductive step, we first prove the base algebraic identity L ((d+1)I - J) = (d+1) • L (labeled `hLA`): distributing multiplication over subtraction gives (d+1)L - LJ, and LJ = 0 leaves (d+1)L. Then, writing ((d+1)I - J)^(k+1) as ((d+1)I - J)^k * ((d+1)I - J), we reassociate to isolate L ((d+1)I - J)^k, apply the induction hypothesis to replace it with (d+1)^k • L, pull the scalar out, apply `hLA`, and combine the scalar powers to obtain (d+1)^(k+1) • L.

    lines 9–13

    uses Matrix.mul_sub, Matrix.mul_smul, Matrix.mul_one, sub_zero, pow_succ, mul_assoc, Matrix.smul_mul, smul_smul

      | succ k ih =>
        have hLA : L * ((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ)) =
            (d + 1 : ℝ) • L := by
          rw [Matrix.mul_sub, Matrix.mul_smul, Matrix.mul_one, hLJ, sub_zero]
        rw [pow_succ, ← mul_assoc, ih, Matrix.smul_mul, hLA, smul_smul, pow_succ]
  3. For all m, j ∈ ℕ, L^(m+1) * ((d+1)I - J)^j = (d+1)^j • L^(m+1).

    We write L^(m+1) as L^m * L using `pow_succ`. Associating L with ((d+1)I - J)^j allows us to apply the lemma `regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux1`, which reduces L * ((d+1)I - J)^j to (d+1)^j • L. Factoring the scalar out of the matrix product with `Matrix.mul_smul` and recombining L^m * L = L^(m+1) establishes the result.

    lines 21–22

    uses pow_succ, mul_assoc, regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux1, Matrix.mul_smul

      rw [pow_succ, mul_assoc, regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux1 L d hLJ j,
        Matrix.mul_smul, ← pow_succ]
  4. For all positive integers i and j, the trace of L^i ((d+1)I - J)^j equals (d+1)^j tr(L^i).

    Since i is a positive integer, it is nonzero, so by `Nat.exists_eq_succ_of_ne_zero` it can be written as m + 1 for some m ∈ ℕ. Substituting this into `regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux2` gives L^i ((d+1)I - J)^j = (d+1)^j • L^i. Taking traces on both sides and pulling out the scalar factor (d+1)^j via `Matrix.trace_smul` proves the identity.

    lines 30–32

    uses Nat.exists_eq_succ_of_ne_zero, regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux2, Matrix.trace_smul, smul_eq_mul

      obtain ⟨m, hm⟩ := Nat.exists_eq_succ_of_ne_zero (show (i : ℕ) ≠ 0 from i.pos.ne')
      rw [hm, regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux2 L d hLJ m (j : ℕ),
        Matrix.trace_smul, smul_eq_mul]
  5. The Laplacian matrix of G satisfies L(G) * J = 0, where J is the all-ones matrix.

    By matrix extensionality (`ext a b`), it suffices to check each matrix entry. For any pair of vertices a, b, the (a, b)-th entry of L(G) * J is the row sum ∑_c L(G)_{a, c} * 1. By `SimpleGraph.lapMatrix_mulVec_const_eq_zero`, multiplying the Laplacian by the constant all-ones vector gives the zero vector. Evaluating this vector equation at component a shows that the sum of the entries across row a is 0, so every entry of L(G) * J is zero.

    lines 42–49

    uses Matrix.mul_apply, Matrix.of_apply, mul_one, Matrix.zero_apply, congrFun, SimpleGraph.lapMatrix_mulVec_const_eq_zero, Matrix.mulVec_apply, Matrix.row_apply, Pi.zero_apply

      classical
      have hLJ : G.lapMatrix ℝ * Matrix.of (fun (_ _ : V) ↦ (1 : ℝ)) = 0 := by
        ext a b
        rw [Matrix.mul_apply]
        simp only [Matrix.of_apply, mul_one, Matrix.zero_apply]
        have h := congrFun (SimpleGraph.lapMatrix_mulVec_const_eq_zero (G := G) (R := ℝ)) a
        simp only [Matrix.mulVec_apply, dotProduct, Matrix.row_apply, Pi.zero_apply, mul_one] at h
        simpa using h
  6. The trace of L(G)^i ((d+1)I - J)^j equals (d+1)^j ℓ_i(G).

    We apply `regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux3` with L = L(G) and the established fact that L(G) * J = 0. This evaluates the trace as (d+1)^j tr(L(G)^i), which is by definition (d+1)^j * graph_lap_trace_seq G i.

    line 50

    uses regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux3

      exact regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux3 (G.lapMatrix ℝ) d hLJ i j
mul_assoc
Multiplication is associative: (a * b) * c = a * (b * c).
mul_one
Multiplying an element by 1 on the right leaves it unchanged: a * 1 = a.
pow_succ
The (n + 1)-th power of an element in a monoid equals its n-th power multiplied by the element: a^(n + 1) = a^n * a.
sub_zero
Subtracting zero from an element leaves it unchanged: a - 0 = a.
smul_smul
Successive scalar multiplications compose by multiplying the scalars: a₁ • (a₂ • b) = (a₁ * a₂) • b.
smul_eq_mul
Scalar multiplication by an element of the ring agrees with regular multiplication: a • b = a * b.
congrFun
If two functions are equal, their values on any argument are equal: if f = g then f(a) = g(a).
Nat.exists_eq_succ_of_ne_zero
Any nonzero natural number is the successor of some natural number: if n ≠ 0, then n = k + 1 for some k.
Pi.zero_apply
The zero function evaluated at any point gives zero: 0(i) = 0.
Matrix.mul_apply
The (i, k)-th entry of the product of two matrices M and N is the sum ∑ j, M i j * N j k.
Matrix.mul_one
Multiplying a matrix on the right by the identity matrix leaves it unchanged: M * 1 = M.
Matrix.mul_smul
A scalar multiple on the right factor can be factored out of matrix multiplication: M * (a • N) = a • (M * N).
Matrix.mul_sub
Matrix multiplication distributes over subtraction on the right: M * (N - N') = M * N - M * N'.
Matrix.of_apply
The (i, j)-th entry of a matrix defined by a function f is f(i, j).
Matrix.zero_apply
Every entry of the zero matrix is zero: 0 i j = 0.
Matrix.row_apply
The j-th component of the i-th row of matrix A is the matrix entry A i j.
Matrix.mulVec_apply
The i-th component of the matrix-vector product M v is the dot product of the i-th row of M with v.
Matrix.smul_mul
A scalar multiple on the left factor can be factored out of matrix multiplication: (a • M) * N = a • (M * N).
Matrix.trace_smul
The trace of a scalar multiple of a matrix is the scalar multiple of the trace: tr(r • A) = r • tr(A).
SimpleGraph.lapMatrix_mulVec_const_eq_zero
Multiplying the Laplacian matrix of a graph by the constant all-ones vector yields the zero vector (every row sum of the Laplacian is zero).
regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux1
If L * J = 0 for the all-ones matrix J, then L * ((d + 1)I - J)^j = (d + 1)^j • L for all natural numbers j.
regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux2
If L * J = 0 for the all-ones matrix J, then L^(m + 1) * ((d + 1)I - J)^j = (d + 1)^j • L^(m + 1) for all natural numbers m and j.
regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux3
If L * J = 0 for the all-ones matrix J, then tr(L^i ((d + 1)I - J)^j) = (d + 1)^j tr(L^i) for all positive integers i and j.

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

/-- If `L * J = 0` (`J` the all-ones matrix), then `L * ((d+1)I - J)^j = (d+1)^j • L`. -/lemma regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux1 {V : Type*} [Fintype V] [DecidableEq V]    (L : Matrix V V ℝ) (d : ℕ)    (hLJ : L * Matrix.of (fun (_ _ : V) ↦ (1 : ℝ)) = 0) (j : ℕ) :    L * (((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ)) ^ j) =      ((d + 1 : ℝ) ^ j) • L := by  induction j with  | zero => simp  | succ k ih =>    have hLA : L * ((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ)) =        (d + 1 : ℝ) • L := by      rw [Matrix.mul_sub, Matrix.mul_smul, Matrix.mul_one, hLJ, sub_zero]    rw [pow_succ, ← mul_assoc, ih, Matrix.smul_mul, hLA, smul_smul, pow_succ]/-- Hence `L^(m+1) * ((d+1)I - J)^j = (d+1)^j • L^(m+1)`. -/lemma regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux2 {V : Type*} [Fintype V] [DecidableEq V]    (L : Matrix V V ℝ) (d : ℕ)    (hLJ : L * Matrix.of (fun (_ _ : V) ↦ (1 : ℝ)) = 0) (m j : ℕ) :    L ^ (m + 1) * (((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ)) ^ j) =      ((d + 1 : ℝ) ^ j) • L ^ (m + 1) := by  rw [pow_succ, mul_assoc, regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux1 L d hLJ j,    Matrix.mul_smul, ← pow_succ]/-- Taking traces: `tr (L^i ((d+1)I - J)^j) = (d+1)^j tr (L^i)` for positive `i`, `j`. -/lemma regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux3 {V : Type*} [Fintype V] [DecidableEq V]    (L : Matrix V V ℝ) (d : ℕ)    (hLJ : L * Matrix.of (fun (_ _ : V) ↦ (1 : ℝ)) = 0) (i j : ℕ+) :    (L ^ (i : ℕ) * (((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ)) ^ (j : ℕ))).trace =      ((d + 1 : ℝ) ^ (j : ℕ)) * (L ^ (i : ℕ)).trace := by  obtain ⟨m, hm⟩ := Nat.exists_eq_succ_of_ne_zero (show (i : ℕ) ≠ 0 from i.pos.ne')  rw [hm, regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux2 L d hLJ m (j : ℕ),    Matrix.trace_smul, smul_eq_mul]open scoped Classical in/-- For any d-regular graph G and positive integers i and j, the trace of L(G)^i ((d+1)I - J)^j equals (d+1)^j tr(L(G)^i). -/theorem regular_graph_lap_mul_pow_scalar_sub_all_ones_trace    {V : Type*} [Fintype V] (d : ℕ) (G : SimpleGraph V)    (hreg : G.IsRegularOfDegree d) (i j : ℕ+) :    Matrix.trace (((G.lapMatrix ℝ) ^ (i : ℕ)) *      (((d + 1 : ℝ) • (1 : Matrix V V ℝ) - Matrix.of fun (_ _ : V) ↦ (1 : ℝ)) ^ (j : ℕ))) =    ((d + 1 : ℝ) ^ (j : ℕ)) * graph_lap_trace_seq G i := by  classical  have hLJ : G.lapMatrix ℝ * Matrix.of (fun (_ _ : V) ↦ (1 : ℝ)) = 0 := by    ext a b    rw [Matrix.mul_apply]    simp only [Matrix.of_apply, mul_one, Matrix.zero_apply]    have h := congrFun (SimpleGraph.lapMatrix_mulVec_const_eq_zero (G := G) (R := ℝ)) a    simp only [Matrix.mulVec_apply, dotProduct, Matrix.row_apply, Pi.zero_apply, mul_one] at h    simpa using h  exact regular_graph_lap_mul_pow_scalar_sub_all_ones_trace_aux3 (G.lapMatrix ℝ) d hLJ i j
See it in the graphDiscuss this resultChallenge it