AFTD Auto-Formalizing Theoretical Domains

spectral_moore_adj_quadform_le_add_sum_sq

theoremverified

For a k-regular finite simple graph G on a vertex type V with second largest adjacency eigenvalue at most θ and k ≤ θ + |V|/2, every x : V → ℝ satisfies x ⬝ᵥ (G.adjMatrix ℝ *ᵥ x) ≤ θ * (x ⬝ᵥ x) + (∑ v, x v)^2 / 2; that is, θI + J/2 - A_G is positive semidefinite.

Statement

open Classical SimpleGraph Matrix in
theorem spectral_moore_adj_quadform_le_add_sum_sq {V : Type*} [Fintype V]
    (G : SimpleGraph V) (k : ℕ) (θ : ℝ) (hreg : G.IsRegularOfDegree k)
    (hθ : spectral_moore_second_eigenvalue_le G θ)
    (hk : (k : ℝ) ≤ θ + (Fintype.card V : ℝ) / 2) (x : V → ℝ) :
    x ⬝ᵥ (G.adjMatrix ℝ *ᵥ x) ≤ θ * (x ⬝ᵥ x) + (∑ v, x v) ^ 2 / 2
Source
arXiv:2611.00591 (A spectral Moore problem and the Yang-Koolen conjecture), Section 5, the positive semidefiniteness of M = I + αS_G in (11)
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

The proof decomposes an arbitrary vector $x$ into its projection $c \mathbf{1}$ along the all-ones vector and an orthogonal zero-sum component $z = x - c \mathbf{1}$. Because $G$ is $k$-regular, $\mathbf{1}$ is an eigenvector of the adjacency matrix $A$ with eigenvalue $k$, which makes $z$ and $\mathbf{1}$ mutually orthogonal both under the standard inner product and with respect to $A$. The quadratic forms $x \cdot (A x)$ and $x \cdot x$ split cleanly without cross terms, and applying the second eigenvalue bound $z \cdot (A z) \le \theta (z \cdot z)$ together with the hypothesis $k \le \theta + |V|/2$ yields the inequality.

  1. The inequality holds vacuously when the vertex set $V$ is empty.

    We perform a case split on whether $|V| = 0$ or $|V| > 0$. If $|V| = 0$, the type $V$ is empty, meaning all sums and dot products over $V$ vanish, reducing the inequality to $0 \le 0$.

    lines 7–9

    uses Nat.eq_zero_or_pos, Fintype.card_eq_zero_iff.mp

      rcases Nat.eq_zero_or_pos (Fintype.card V) with hn | hn
      · have : IsEmpty V := Fintype.card_eq_zero_iff.mp hn
        simp [dotProduct]
  2. When $|V| > 0$, decomposing $x$ as $x = z + c \mathbf{1}$ with mean $c = (\sum_v x_v) / |V|$ yields a component $z$ whose coordinates sum to zero.

    We define the scalar $c$ as the average of the coordinates of $x$, and set $z = x - c \mathbf{1}$ where $\mathbf{1}$ is the all-ones vector. Summing the coordinates of $z$ gives $\sum_v z_v = \sum_v x_v - |V| \cdot c = 0$.

    lines 10–18

    uses Pi.sub_apply, Pi.smul_apply, smul_eq_mul, mul_one, Finset.sum_sub_distrib, Finset.sum_const, Finset.card_univ, nsmul_eq_mul

      have hn' : (0 : ℝ) < Fintype.card V := by exact_mod_cast hn
      set A := G.adjMatrix ℝ with hA
      set one : V → ℝ := fun _ => 1 with hone
      set c : ℝ := (∑ v, x v) / Fintype.card V with hc
      set z : V → ℝ := x - c • one with hzdef
      have hz : ∑ v, z v = 0 := by
        simp only [hzdef, Pi.sub_apply, Pi.smul_apply, smul_eq_mul, hone, mul_one,
          Finset.sum_sub_distrib, Finset.sum_const, Finset.card_univ, nsmul_eq_mul, hc]
        field_simp; ring
  3. The zero-sum component $z$ satisfies $z \cdot (A z) \le \theta (z \cdot z)$, and $x$ reconstructs as $z + c \mathbf{1}$.

    Because $\sum_v z_v = 0$, the vector $z$ is orthogonal to the constant eigenvector, so the library lemma `spectral_moore_adj_quadform_le_of_sum_eq_zero` applies to bound its Rayleigh quotient by the second eigenvalue $\theta$. By definition of $z$, we also have $x = z + c \mathbf{1}$.

    lines 19–20

    uses spectral_moore_adj_quadform_le_of_sum_eq_zero

      have hqz := spectral_moore_adj_quadform_le_of_sum_eq_zero G k θ hreg hθ z hz
      have hx : x = z + c • one := by simp [hzdef]
  4. The adjacency matrix satisfies $A \mathbf{1} = k \mathbf{1}$ and is symmetric with respect to the dot product.

    Since $G$ is $k$-regular, multiplying $A$ by the all-ones vector evaluates at each vertex $v$ to the cardinality of its neighborhood finset, which is its degree $k$. The symmetry of the adjacency matrix ensures that $x \cdot (A y) = (A x) \cdot y$ for all vectors $x, y$.

    lines 21–27

    uses adjMatrix_mulVec_apply, Finset.sum_const, card_neighborFinset_eq_degree, mul_one, nsmul_eq_mul, dotProduct_mulVec, mulVec_transpose, dotProduct_comm

      have h1 : A *ᵥ one = fun _ => (k : ℝ) := by
        funext v
        simp only [hA, hone, adjMatrix_mulVec_apply, Finset.sum_const, card_neighborFinset_eq_degree,
          hreg.degree_eq, nsmul_eq_mul, mul_one]
      have hAsymm : ∀ x y : V → ℝ, x ⬝ᵥ (A *ᵥ y) = (A *ᵥ x) ⬝ᵥ y := by
        intro x y
        rw [dotProduct_mulVec, ← mulVec_transpose, (G.isSymm_adjMatrix (α := ℝ)).eq, dotProduct_comm]
  5. The cross terms between $z$ and $\mathbf{1}$ vanish ($z \cdot \mathbf{1} = 0$ and $z \cdot (A \mathbf{1}) = 0$), and the norms evaluate to $\mathbf{1} \cdot \mathbf{1} = |V|$, $\mathbf{1} \cdot (A \mathbf{1}) = k |V|$, and $\sum_v x_v = c |V|$.

    The inner product $z \cdot \mathbf{1}$ is simply $\sum_v z_v = 0$. By the symmetry of $A$ and the eigenvector equation $A \mathbf{1} = k \mathbf{1}$, the cross term $z \cdot (A \mathbf{1}) = (A z) \cdot \mathbf{1} = k (z \cdot \mathbf{1})$ also vanishes. Computing the inner products of the all-ones vector gives $\mathbf{1} \cdot \mathbf{1} = |V|$ and $\mathbf{1} \cdot (A \mathbf{1}) = k |V|$, and rewriting the definition of $c$ gives $\sum_v x_v = c |V|$.

    lines 28–38

    uses dotProduct_comm, Finset.mul_sum, mul_comm, mul_one, Finset.sum_const, Finset.card_univ, nsmul_eq_mul

      have z_one : z ⬝ᵥ one = 0 := by simp [dotProduct, hone, hz]
      have one_z : one ⬝ᵥ z = 0 := by rw [dotProduct_comm]; exact z_one
      have one_A_z : one ⬝ᵥ (A *ᵥ z) = 0 := by
        rw [hAsymm, h1]; simp [dotProduct, ← Finset.mul_sum, hz]
      have z_A_one : z ⬝ᵥ (A *ᵥ one) = 0 := by rw [hAsymm, dotProduct_comm, one_A_z]
      have one_A_one : one ⬝ᵥ (A *ᵥ one) = k * Fintype.card V := by
        rw [h1]; simp [dotProduct, hone, mul_comm]
      have one_one : one ⬝ᵥ one = Fintype.card V := by
        simp only [hone, dotProduct, mul_one, Finset.sum_const, Finset.card_univ, nsmul_eq_mul]
      have hsum : ∑ v, x v = c * Fintype.card V := by
        rw [hc]; field_simp
  6. Expanding the quadratic forms and applying the inequality $k \le \theta + |V|/2$ yields the theorem. automation

    Substituting $x = z + c \mathbf{1}$ and $\sum_v x_v = c |V|$ into both sides, the bilinearity of the dot product and the vanishing cross terms expand $x \cdot (A x)$ to $z \cdot (A z) + c^2 k |V|$ and $x \cdot x$ to $z \cdot z + c^2 |V|$. Since $z \cdot (A z) \le \theta (z \cdot z)$ and $c^2 |V| \ge 0$, the hypothesis $k \le \theta + |V|/2$ implies $c^2 k |V| \le \theta c^2 |V| + (c |V|)^2 / 2$, which allows non-linear arithmetic (`nlinarith`) to close the goal.

    lines 39–43

    uses mulVec_add, mulVec_smul, add_dotProduct, dotProduct_add, smul_dotProduct, dotProduct_smul, smul_eq_mul

      rw [hsum, hx]
      simp only [mulVec_add, mulVec_smul, add_dotProduct, dotProduct_add, smul_dotProduct,
        dotProduct_smul, smul_eq_mul, one_A_z, z_A_one, z_one, one_z, one_A_one, one_one]
      have hc2 : 0 ≤ c ^ 2 * Fintype.card V := by positivity
      nlinarith
Nat.eq_zero_or_pos
Every natural number is either zero or strictly positive ($n = 0 \lor n > 0$).
Fintype.card_eq_zero_iff.mp
If the cardinality of a finite type is zero, then the type has no elements (it is empty).
Pi.sub_apply
Evaluating a difference of functions at an argument is the difference of their evaluations: $(f - g)(x) = f(x) - g(x)$.
Pi.smul_apply
Evaluating a scalar multiple of a function at an argument is the scalar multiple of its evaluation: $(c \cdot f)(x) = c \cdot f(x)$.
smul_eq_mul
Scalar multiplication in a ring coincides with standard multiplication: $a \cdot b = a * b$.
mul_one
Multiplying an element by 1 on the right leaves it unchanged: $a * 1 = a$.
Finset.sum_sub_distrib
The sum of a difference over a finite set equals the difference of the sums: $\sum_{x \in s} (f x - g x) = \sum_{x \in s} f x - \sum_{x \in s} g x$.
Finset.sum_const
The sum of a constant value $b$ over a finite set $s$ is $|s| \cdot b$.
Finset.card_univ
The cardinality of the universal finset on a finite type is `Fintype.card`.
nsmul_eq_mul
Scalar multiplication by a natural number $n$ equals multiplication by the natural number cast to the ring: $n \cdot a = (\uparrow n) * a$.
spectral_moore_adj_quadform_le_of_sum_eq_zero
For a $k$-regular graph with second adjacency eigenvalue at most $\theta$, any vector $z$ summing to zero satisfies $z \cdot (A z) \le \theta (z \cdot z)$.
adjMatrix_mulVec_apply
The $v$-th coordinate of the matrix-vector product $A v$ for the adjacency matrix is the sum of the vector's coordinates over the neighbors of $v$.
card_neighborFinset_eq_degree
The number of neighbors in the neighbor finset of a vertex equals its degree.
dotProduct_mulVec
Matrix-vector multiplication shifts across the dot product as $v \cdot (A w) = (v A) \cdot w$.
mulVec_transpose
Multiplying by the transpose matrix $A^T x$ is the vector-matrix product $x A$.
dotProduct_comm
The dot product is commutative: $v \cdot w = w \cdot v$.
Finset.mul_sum
Multiplication distributes over finite sums: $a * \sum_{i \in s} f i = \sum_{i \in s} a * f i$.
mul_comm
Multiplication is commutative: $a * b = b * a$.
mulVec_add
Matrix-vector multiplication distributes over vector addition: $A (x + y) = A x + A y$.
mulVec_smul
Matrix-vector multiplication commutes with scalar multiplication: $A (b \cdot v) = b \cdot (A v)$.
add_dotProduct
The dot product is additive in the first argument: $(u + v) \cdot w = u \cdot w + v \cdot w$.
dotProduct_add
The dot product is additive in the second argument: $u \cdot (v + w) = u \cdot v + u \cdot w$.
smul_dotProduct
Scalar multiplication in the first argument pulls out of the dot product: $(x \cdot v) \cdot w = x \cdot (v \cdot w)$.
dotProduct_smul
Scalar multiplication in the second argument pulls out of the dot product: $v \cdot (x \cdot w) = x \cdot (v \cdot w)$.

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

open Classical SimpleGraph Matrix intheorem spectral_moore_adj_quadform_le_add_sum_sq {V : Type*} [Fintype V]    (G : SimpleGraph V) (k : ℕ) (θ : ℝ) (hreg : G.IsRegularOfDegree k)    (hθ : spectral_moore_second_eigenvalue_le G θ)    (hk : (k : ℝ) ≤ θ + (Fintype.card V : ℝ) / 2) (x : V → ℝ) :    x ⬝ᵥ (G.adjMatrix ℝ *ᵥ x) ≤ θ * (x ⬝ᵥ x) + (∑ v, x v) ^ 2 / 2 := by  rcases Nat.eq_zero_or_pos (Fintype.card V) with hn | hn  · have : IsEmpty V := Fintype.card_eq_zero_iff.mp hn    simp [dotProduct]  have hn' : (0 : ℝ) < Fintype.card V := by exact_mod_cast hn  set A := G.adjMatrix ℝ with hA  set one : V → ℝ := fun _ => 1 with hone  set c : ℝ := (∑ v, x v) / Fintype.card V with hc  set z : V → ℝ := x - c • one with hzdef  have hz : ∑ v, z v = 0 := by    simp only [hzdef, Pi.sub_apply, Pi.smul_apply, smul_eq_mul, hone, mul_one,      Finset.sum_sub_distrib, Finset.sum_const, Finset.card_univ, nsmul_eq_mul, hc]    field_simp; ring  have hqz := spectral_moore_adj_quadform_le_of_sum_eq_zero G k θ hreg hθ z hz  have hx : x = z + c • one := by simp [hzdef]  have h1 : A *ᵥ one = fun _ => (k : ℝ) := by    funext v    simp only [hA, hone, adjMatrix_mulVec_apply, Finset.sum_const, card_neighborFinset_eq_degree,      hreg.degree_eq, nsmul_eq_mul, mul_one]  have hAsymm : ∀ x y : V → ℝ, x ⬝ᵥ (A *ᵥ y) = (A *ᵥ x) ⬝ᵥ y := by    intro x y    rw [dotProduct_mulVec, ← mulVec_transpose, (G.isSymm_adjMatrix (α := ℝ)).eq, dotProduct_comm]  have z_one : z ⬝ᵥ one = 0 := by simp [dotProduct, hone, hz]  have one_z : one ⬝ᵥ z = 0 := by rw [dotProduct_comm]; exact z_one  have one_A_z : one ⬝ᵥ (A *ᵥ z) = 0 := by    rw [hAsymm, h1]; simp [dotProduct, ← Finset.mul_sum, hz]  have z_A_one : z ⬝ᵥ (A *ᵥ one) = 0 := by rw [hAsymm, dotProduct_comm, one_A_z]  have one_A_one : one ⬝ᵥ (A *ᵥ one) = k * Fintype.card V := by    rw [h1]; simp [dotProduct, hone, mul_comm]  have one_one : one ⬝ᵥ one = Fintype.card V := by    simp only [hone, dotProduct, mul_one, Finset.sum_const, Finset.card_univ, nsmul_eq_mul]  have hsum : ∑ v, x v = c * Fintype.card V := by    rw [hc]; field_simp  rw [hsum, hx]  simp only [mulVec_add, mulVec_smul, add_dotProduct, dotProduct_add, smul_dotProduct,    dotProduct_smul, smul_eq_mul, one_A_z, z_A_one, z_one, one_z, one_A_one, one_one]  have hc2 : 0 ≤ c ^ 2 * Fintype.card V := by positivity  nlinarith
See it in the graphDiscuss this resultChallenge it