AFTD Auto-Formalizing Theoretical Domains

spectral_moore_adj_quadform_le_of_sum_eq_zero

theoremverified

For a k-regular finite simple graph G on a vertex type V whose second largest adjacency eigenvalue is at most θ (spectral_moore_second_eigenvalue_le G θ), every real vector z : V → ℝ with coordinate sum zero satisfies z ⬝ᵥ (G.adjMatrix ℝ *ᵥ z) ≤ θ * (z ⬝ᵥ z).

Statement

open Classical SimpleGraph Matrix in
theorem spectral_moore_adj_quadform_le_of_sum_eq_zero {V : Type*} [Fintype V]
    (G : SimpleGraph V) (k : ℕ) (θ : ℝ) (hreg : G.IsRegularOfDegree k)
    (hθ : spectral_moore_second_eigenvalue_le G θ) (z : V → ℝ) (hz : ∑ v, z v = 0) :
    z ⬝ᵥ (G.adjMatrix ℝ *ᵥ z) ≤ θ * (z ⬝ᵥ z)
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

For a k-regular graph whose second adjacency eigenvalue is bounded by θ, we show that any vector z with coordinate sum zero satisfies z ⬝ᵥ (A *ᵥ z) ≤ θ (z ⬝ᵥ z). If k ≤ θ, the result follows immediately because the Laplacian is positive semidefinite, giving z ⬝ᵥ (A *ᵥ z) ≤ k (z ⬝ᵥ z) ≤ θ (z ⬝ᵥ z). When θ < k, the spectral theorem guarantees that any vector orthogonal to the top eigenvector b satisfies the Rayleigh bound with constant θ; projecting z parallel to the all-ones vector 𝟏 onto b^⊥ via y = z - β • 𝟏 and expanding the quadratic forms yields z ⬝ᵥ (A *ᵥ z) + β² k |V| ≤ θ (z ⬝ᵥ z) + θ β² |V|, which implies the desired inequality because (k - θ) β² |V| ≥ 0.

  1. For a symmetric linear operator T with orthonormal eigenvector basis e_i and eigenvalues λ_i, the quadratic form satisfies ⟨T v, v⟩ = ∑_i λ_i ⟨e_i, v⟩².

    Expanding T v along the orthonormal eigenvector basis and using the self-adjointness ⟨T v, e_i⟩ = ⟨v, T e_i⟩ = λ_i ⟨v, e_i⟩ expresses the quadratic form as the weighted sum of squared coordinates ∑_i λ_i ⟨e_i, v⟩².

    lines 7–14

    uses OrthonormalBasis.sum_inner_mul_inner, Finset.sum_congr, inner_smul_right, RCLike.ofReal_real_eq_id, id_eq, real_inner_comm

      have qform : inner ℝ (T v) v = ∑ i : Fin N, hT.eigenvalues hN i * (inner ℝ (hT.eigenvectorBasis hN i) v)^2 := by
        rw [← OrthonormalBasis.sum_inner_mul_inner (hT.eigenvectorBasis hN) (T v) v]
        apply Finset.sum_congr rfl
        intro i _
        rw [hT v (hT.eigenvectorBasis hN i), hT.apply_eigenvectorBasis hN i, inner_smul_right]
        simp only [RCLike.ofReal_real_eq_id, id_eq]
        rw [real_inner_comm v]
        ring
  2. By Parseval's identity, ⟨v, v⟩ = ∑_i ⟨e_i, v⟩².

    Expanding v along the orthonormal eigenvector basis expresses the squared norm ⟨v, v⟩ as the sum of squared coordinate projections ∑_i ⟨e_i, v⟩².

    lines 15–20

    uses OrthonormalBasis.sum_inner_mul_inner, Finset.sum_congr, real_inner_comm

      have pars : inner ℝ v v = ∑ i : Fin N, (inner ℝ (hT.eigenvectorBasis hN i) v)^2 := by
        rw [← OrthonormalBasis.sum_inner_mul_inner (hT.eigenvectorBasis hN) v v]
        apply Finset.sum_congr rfl
        intro i _
        rw [real_inner_comm v]
        ring
  3. If v is orthogonal to the j₀-th eigenvector and all other eigenvalues satisfy λ_k ≤ c, then ⟨T v, v⟩ ≤ c ⟨v, v⟩.

    In the spectral sum for ⟨T v, v⟩, the term for k = j₀ vanishes because ⟨e_{j₀}, v⟩ = 0. For every other index k ≠ j₀, the eigenvalue satisfies λ_k ≤ c and the squared projection ⟨e_k, v⟩² is non-negative, so each term is bounded by c ⟨e_k, v⟩². Summing over all indices gives ⟨T v, v⟩ ≤ c ∑_k ⟨e_k, v⟩² = c ⟨v, v⟩.

    lines 21–26

    uses Finset.mul_sum, Finset.sum_le_sum, mul_le_mul_of_nonneg_right, sq_nonneg

      rw [qform, pars, Finset.mul_sum]
      apply Finset.sum_le_sum
      intro k _
      by_cases hk : k = j0
      · subst hk; rw [hv]; simp
      · exact mul_le_mul_of_nonneg_right (hc k hk) (sq_nonneg _)
  4. For any k-regular graph G and any vector x, the adjacency quadratic form satisfies x ⬝ᵥ (A *ᵥ x) ≤ k * (x ⬝ᵥ x).

    The graph Laplacian L = D - A is positive semidefinite, so x ⬝ᵥ (L *ᵥ x) = x ⬝ᵥ (D *ᵥ x) - x ⬝ᵥ (A *ᵥ x) ≥ 0. For a k-regular graph, every vertex degree is k, so x ⬝ᵥ (D *ᵥ x) = ∑_i d(i) x(i)² = k (x ⬝ᵥ x). Linear arithmetic then yields x ⬝ᵥ (A *ᵥ x) ≤ k (x ⬝ᵥ x).

    lines 32–38

    uses star_trivial, lapMatrix, sub_mulVec, dotProduct_sub, dotProduct_mulVec_degMatrix, dotProduct, Finset.mul_sum, Finset.sum_congr

      have h := (G.posSemidef_lapMatrix ℝ).dotProduct_mulVec_nonneg x
      simp only [star_trivial, lapMatrix, sub_mulVec, dotProduct_sub,
        dotProduct_mulVec_degMatrix] at h
      have : ∑ i : V, (G.degree i : ℝ) * x i * x i = k * (x ⬝ᵥ x) := by
        simp only [dotProduct, Finset.mul_sum, hreg.degree_eq]
        exact Finset.sum_congr rfl fun i _ => by ring
      linarith
  5. The adjacency matrix A defines a symmetric linear operator on Euclidean space, and the degree bound applies to A.

    We name the adjacency matrix A and record the degree quadratic bound for G from the auxiliary lemma. Since the adjacency matrix of a simple graph is Hermitian (symmetric over ℝ), its induced linear map on Euclidean space is symmetric.

    lines 45–48

    uses spectral_moore_adj_quadform_aux_deg

      set A := G.adjMatrix ℝ with hA
      have hdeg := spectral_moore_adj_quadform_aux_deg G k hreg
      have hsymm : A.toEuclideanLin.IsSymmetric :=
        isSymmetric_toEuclideanLin_iff.mpr (G.isHermitian_adjMatrix ℝ)
  6. The all-ones vector 𝟏 satisfies A *ᵥ 𝟏 = k • 𝟏.

    Multiplying the adjacency matrix by the all-ones vector at any vertex v computes the sum of ones over the neighbors of v, which equals the degree d(v) = k by k-regularity.

    lines 49–52

    uses adjMatrix_mulVec_apply, Finset.sum_const, card_neighborFinset_eq_degree, nsmul_eq_mul, mul_one

      have h1 : A *ᵥ (fun _ : V => (1 : ℝ)) = fun _ => (k : ℝ) := by
        funext v
        simp only [A, adjMatrix_mulVec_apply, Finset.sum_const, card_neighborFinset_eq_degree,
          hreg.degree_eq, nsmul_eq_mul, mul_one]
  7. The matrix A is self-adjoint with respect to the dot product: x ⬝ᵥ (A *ᵥ y) = (A *ᵥ x) ⬝ᵥ y.

    Since A is symmetric (Aᵀ = A), x ⬝ᵥ (A *ᵥ y) = (x A) ⬝ᵥ y = (Aᵀ *ᵥ x) ⬝ᵥ y = (A *ᵥ x) ⬝ᵥ y by commutativity of the dot product.

    lines 53–55

    uses dotProduct_mulVec, mulVec_transpose, dotProduct_comm

      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]
  8. The all-ones vector satisfies 𝟏 ⬝ᵥ (A *ᵥ z) = 0, 𝟏 ⬝ᵥ (A *ᵥ 𝟏) = k |V|, 𝟏 ⬝ᵥ 𝟏 = |V|, and z ⬝ᵥ 𝟏 = 0.

    Since ∑_v z(v) = 0, we have z ⬝ᵥ 𝟏 = 0. By self-adjointness, 𝟏 ⬝ᵥ (A *ᵥ z) = (A *ᵥ 𝟏) ⬝ᵥ z = (k • 𝟏) ⬝ᵥ z = k ∑_v z(v) = 0. Furthermore, 𝟏 ⬝ᵥ (A *ᵥ 𝟏) = 𝟏 ⬝ᵥ (k • 𝟏) = k |V| and 𝟏 ⬝ᵥ 𝟏 = ∑_v 1 = |V|.

    lines 56–62

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

      have one_A_z : (fun _ : V => (1 : ℝ)) ⬝ᵥ (A *ᵥ z) = 0 := by
        rw [hAsymm, h1]; simp [dotProduct, ← Finset.mul_sum, hz]
      have one_A_one : (fun _ : V => (1 : ℝ)) ⬝ᵥ (A *ᵥ (fun _ : V => (1 : ℝ))) = k * Fintype.card V := by
        rw [h1]; simp [dotProduct, mul_comm]
      have one_one : (fun _ : V => (1 : ℝ)) ⬝ᵥ (fun _ : V => (1 : ℝ)) = Fintype.card V := by
        simp only [dotProduct, mul_one, Finset.sum_const, Finset.card_univ, nsmul_eq_mul]
      have z_one : z ⬝ᵥ (fun _ : V => (1 : ℝ)) = 0 := by simp [dotProduct, hz]
  9. If k ≤ θ, the inequality z ⬝ᵥ (A *ᵥ z) ≤ θ * (z ⬝ᵥ z) holds immediately. automation

    From the degree bound, z ⬝ᵥ (A *ᵥ z) ≤ k (z ⬝ᵥ z). Because z ⬝ᵥ z = ∑_v z(v)² ≥ 0, multiplying k ≤ θ by z ⬝ᵥ z preserves the inequality, giving k (z ⬝ᵥ z) ≤ θ (z ⬝ᵥ z). Non-linear arithmetic closes the goal.

    lines 63–67

    uses dotProduct, Finset.sum_nonneg, mul_self_nonneg

      by_cases hkθ : (k : ℝ) ≤ θ
      · have := hdeg z
        have hzz : 0 ≤ z ⬝ᵥ z := by
          simp only [dotProduct]; exact Finset.sum_nonneg fun i _ => mul_self_nonneg _
        nlinarith
  10. If θ < k and the vertex set V is empty, the inequality holds vacuously. automation

    When |V| = 0, the vertex type V is empty, so all vectors are empty and both sides of the quadratic form inequality evaluate to 0.

    lines 68–71

    uses not_le, Nat.eq_zero_or_pos, dotProduct

      rw [not_le] at hkθ
      rcases Nat.eq_zero_or_pos (Fintype.card V) with hn | hn
      · have : IsEmpty V := Fintype.card_eq_zero_iff.mp hn
        simp [dotProduct]
  11. Any vector y orthogonal to the top eigenvector b of A satisfies y ⬝ᵥ (A *ᵥ y) ≤ θ * (y ⬝ᵥ y).

    We identify (V → ℝ) with Euclidean space ℝ^{|V|}, where the inner product coincides with the vector dot product. We choose b to be the eigenvector corresponding to the first eigenvalue (index 0). By the spectral hypothesis, all other eigenvalues are at most θ, so the auxiliary lemma spectral_moore_adj_quadform_aux_qf implies that any y with ⟨b, y⟩ = 0 satisfies the quadratic form bound with constant θ.

    lines 73–85

    uses EuclideanSpace.inner_eq_star_dotProduct, dotProduct_comm, finrank_euclideanSpace, spectral_moore_adj_quadform_aux_qf, ne_eq, Fin.mk.injEq

      have e1 : ∀ u w : V → ℝ, inner ℝ (WithLp.toLp 2 u) (WithLp.toLp 2 w) = u ⬝ᵥ w := by
        intro u w; rw [EuclideanSpace.inner_eq_star_dotProduct]; simp [dotProduct_comm]
      set b := hsymm.eigenvectorBasis finrank_euclideanSpace ⟨0, by simpa [finrank_euclideanSpace] using hn⟩ with hb
      have key : ∀ y : V → ℝ, inner ℝ b (WithLp.toLp 2 y) = 0 →
          y ⬝ᵥ (A *ᵥ y) ≤ θ * (y ⬝ᵥ y) := by
        intro y hy
        have := spectral_moore_adj_quadform_aux_qf A.toEuclideanLin hsymm finrank_euclideanSpace _ θ
          (fun i hi => hθ i (by
            rcases i with ⟨i, hi'⟩
            simp only [ne_eq, Fin.mk.injEq] at hi
            simp only; omega)) _ hy
        rw [show A.toEuclideanLin (WithLp.toLp 2 y) = WithLp.toLp 2 (A *ᵥ y) from rfl, e1, e1] at this
        rwa [dotProduct_comm]
  12. The top eigenvector b is not orthogonal to the all-ones vector 𝟏. automation

    If ⟨b, 𝟏⟩ were 0, we could apply the quadratic form bound to 𝟏, giving 𝟏 ⬝ᵥ (A *ᵥ 𝟏) ≤ θ (𝟏 ⬝ᵥ 𝟏), which translates to k |V| ≤ θ |V|. Since |V| > 0, this would imply k ≤ θ, contradicting θ < k.

    lines 86–91

      set one : V → ℝ := fun _ => 1 with hone
      have hn' : (0 : ℝ) < Fintype.card V := by exact_mod_cast hn
      by_cases hγ : inner ℝ b (WithLp.toLp 2 one) = 0
      · have := key one hγ
        rw [one_A_one, one_one] at this
        nlinarith
  13. Setting β = ⟨b, z⟩ / ⟨b, 𝟏⟩, the shifted vector y = z - β • 𝟏 is orthogonal to b and satisfies the Rayleigh bound.

    By linearity of the inner product, ⟨b, z - β • 𝟏⟩ = ⟨b, z⟩ - β ⟨b, 𝟏⟩ = 0. Therefore the key quadratic form bound applies to y = z - β • 𝟏.

    lines 92–96

    uses WithLp.toLp_sub, WithLp.toLp_smul, inner_sub_right, inner_smul_right

      set β := inner ℝ b (WithLp.toLp 2 z) / inner ℝ b (WithLp.toLp 2 one) with hβ
      have hy : inner ℝ b (WithLp.toLp 2 (z - β • one)) = 0 := by
        rw [WithLp.toLp_sub, WithLp.toLp_smul, inner_sub_right, inner_smul_right, hβ]
        field_simp; ring
      have := key _ hy
  14. The quadratic form of z - β • 𝟏 expands as z ⬝ᵥ (A *ᵥ z) - 2 β (𝟏 ⬝ᵥ (A *ᵥ z)) + β² (𝟏 ⬝ᵥ (A *ᵥ 𝟏)).

    Expanding the bilinear form using linearity of matrix-vector multiplication and dot product, the two cross terms combine into -2 β (𝟏 ⬝ᵥ (A *ᵥ z)) because A is self-adjoint.

    lines 97–102

    uses dotProduct_comm, mulVec_sub, mulVec_smul, sub_dotProduct, dotProduct_sub, smul_dotProduct, dotProduct_smul, smul_eq_mul

      have exp1 : (z - β • one) ⬝ᵥ (A *ᵥ (z - β • one)) =
          z ⬝ᵥ (A *ᵥ z) - 2 * β * (one ⬝ᵥ (A *ᵥ z)) + β ^ 2 * (one ⬝ᵥ (A *ᵥ one)) := by
        have hs : one ⬝ᵥ (A *ᵥ z) = z ⬝ᵥ (A *ᵥ one) := by rw [hAsymm, dotProduct_comm]
        simp only [mulVec_sub, mulVec_smul, sub_dotProduct, dotProduct_sub, smul_dotProduct,
          dotProduct_smul, smul_eq_mul, hs]
        ring
  15. The squared norm of z - β • 𝟏 expands as z ⬝ᵥ z + β² (𝟏 ⬝ᵥ 𝟏).

    Expanding (z - β • 𝟏) ⬝ᵥ (z - β • 𝟏) = z ⬝ᵥ z - 2 β (z ⬝ᵥ 𝟏) + β² (𝟏 ⬝ᵥ 𝟏), the cross term vanishes because z ⬝ᵥ 𝟏 = ∑_v z(v) = 0.

    lines 103–107

    uses dotProduct_comm, sub_dotProduct, dotProduct_sub, smul_dotProduct, dotProduct_smul, smul_eq_mul

      have exp2 : (z - β • one) ⬝ᵥ (z - β • one) = z ⬝ᵥ z + β ^ 2 * (one ⬝ᵥ one) := by
        have hs : one ⬝ᵥ z = 0 := by rw [dotProduct_comm]; exact z_one
        simp only [sub_dotProduct, dotProduct_sub, smul_dotProduct, dotProduct_smul, smul_eq_mul, hs,
          z_one]
        ring
  16. The quadratic form bound on z - β • 𝟏 implies z ⬝ᵥ (A *ᵥ z) ≤ θ * (z ⬝ᵥ z). automation

    Substituting the inner products with 𝟏 into the quadratic bound yields z ⬝ᵥ (A *ᵥ z) + β² k |V| ≤ θ (z ⬝ᵥ z) + θ β² |V|. Rearranging gives z ⬝ᵥ (A *ᵥ z) ≤ θ (z ⬝ᵥ z) - (k - θ) β² |V|. Since k > θ and β² |V| ≥ 0, the term subtracted on the right is non-negative, concluding the inequality.

    lines 108–110

      rw [exp1, exp2, one_A_z, one_A_one, one_one] at this
      have hβ2 : 0 ≤ β ^ 2 * Fintype.card V := by positivity
      nlinarith
adjMatrix_mulVec_apply
Evaluating the matrix-vector product of the adjacency matrix at a vertex v sums the vector entries over the neighbors of v.
card_neighborFinset_eq_degree
The number of neighbors in the neighbor finset of a vertex v equals its degree.
dotProduct_comm
The vector dot product is commutative: v ⬝ᵥ w = w ⬝ᵥ v.
dotProduct
Definition of the vector dot product as the sum over coordinates of pointwise products.
dotProduct_mulVec_degMatrix
The dot product with a degree matrix satisfies x ⬝ᵥ (D *ᵥ x) = ∑_i d(i) x(i)².
dotProduct_mulVec
Associativity of dot product with matrix-vector multiplication: v ⬝ᵥ (A *ᵥ w) = (v A) ⬝ᵥ w.
dotProduct_smul
The dot product distributes over scalar multiplication in the second argument: v ⬝ᵥ (x • w) = x (v ⬝ᵥ w).
dotProduct_sub
The dot product distributes over subtraction in the second argument: u ⬝ᵥ (v - w) = u ⬝ᵥ v - u ⬝ᵥ w.
EuclideanSpace.inner_eq_star_dotProduct
The inner product on Euclidean space corresponds to the vector dot product.
Fin.mk.injEq
Two elements of Fin n are equal if and only if their underlying natural values are equal.
Finset.card_univ
The cardinality of the universal finset on a finite type equals the cardinality of the type.
Finset.mul_sum
Multiplication distributes over finite sums: a * ∑ i, f i = ∑ i, a * f i.
Finset.sum_congr
Two finite sums are equal if their terms are pointwise equal.
Finset.sum_const
The sum of a constant c over a finite set s equals |s| • c.
Finset.sum_le_sum
A finite sum is bounded by another if each corresponding term is bounded.
Finset.sum_nonneg
A finite sum of non-negative elements is non-negative.
finrank_euclideanSpace
The dimension of the Euclidean space on index type ι equals the cardinality of ι.
id_eq
The identity function satisfies id(a) = a.
inner_smul_right
Scalar multiplication factors out of the right argument of an inner product: ⟨x, r • y⟩ = r ⟨x, y⟩.
inner_sub_right
The inner product distributes over subtraction in the right argument: ⟨x, y - z⟩ = ⟨x, y⟩ - ⟨x, z⟩.
lapMatrix
Definition of the graph Laplacian matrix L = D - A.
mul_comm
Multiplication in a commutative ring is commutative: a * b = b * a.
mul_le_mul_of_nonneg_right
Multiplying an inequality b ≤ c by a non-negative element a on the right preserves the inequality: b * a ≤ c * a.
mul_one
Multiplying by 1 on the right is the identity: a * 1 = a.
mul_self_nonneg
The product of any real number with itself is non-negative: 0 ≤ a * a.
mulVec_smul
Matrix-vector multiplication preserves scalar multiplication: A *ᵥ (b • v) = b • (A *ᵥ v).
mulVec_sub
Matrix-vector multiplication distributes over subtraction: A *ᵥ (x - y) = A *ᵥ x - A *ᵥ y.
mulVec_transpose
Multiplication by the transpose matrix equals left multiplication by the vector: Aᵀ *ᵥ x = x A.
Nat.eq_zero_or_pos
Every natural number is either zero or strictly positive.
ne_eq
Inequality a ≠ b is defined as the negation of equality ¬(a = b).
not_le
The negation of a ≤ b in a linear order is equivalent to b < a.
nsmul_eq_mul
Scalar multiplication by a natural number n on ℝ equals multiplication by (n : ℝ).
OrthonormalBasis.sum_inner_mul_inner
For any orthonormal basis b, the inner product ⟨x, y⟩ equals the sum over basis vectors ∑ i, ⟨x, b i⟩ ⟨b i, y⟩.
RCLike.ofReal_real_eq_id
The real coercion from ℝ to ℝ is the identity.
real_inner_comm
The real inner product is symmetric: ⟨y, x⟩ = ⟨x, y⟩.
smul_dotProduct
Scalar multiplication factors out of the left argument of a dot product: (x • v) ⬝ᵥ w = x (v ⬝ᵥ w).
smul_eq_mul
Scalar multiplication on ℝ is ordinary multiplication.
spectral_moore_adj_quadform_aux_deg
For any k-regular graph, every vector x satisfies the quadratic form bound x ⬝ᵥ (A *ᵥ x) ≤ k * (x ⬝ᵥ x).
spectral_moore_adj_quadform_aux_qf
For a symmetric linear operator whose non-top eigenvalues are at most c, any vector orthogonal to the top eigenvector satisfies ⟨T v, v⟩ ≤ c ⟨v, v⟩.
sq_nonneg
The square of any real number is non-negative: 0 ≤ a².
star_trivial
The star operation (involution) on ℝ is the identity.
sub_dotProduct
The dot product distributes over subtraction in the first argument: (u - v) ⬝ᵥ w = u ⬝ᵥ w - v ⬝ᵥ w.
WithLp.toLp_smul
The identification map WithLp.toLp preserves scalar multiplication: toLp (c • x) = c • toLp x.
WithLp.toLp_sub
The identification map WithLp.toLp preserves vector subtraction: toLp (x - y) = toLp x - toLp y.

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

lemma spectral_moore_adj_quadform_aux_qf    {E : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [FiniteDimensional ℝ E]    {N : ℕ} (T : E →ₗ[ℝ] E) (hT : T.IsSymmetric) (hN : Module.finrank ℝ E = N)    (j0 : Fin N) (c : ℝ) (hc : ∀ k, k ≠ j0 → hT.eigenvalues hN k ≤ c)    (v : E) (hv : inner ℝ (hT.eigenvectorBasis hN j0) v = 0) :    inner ℝ (T v) v ≤ c * inner ℝ v v := by  have qform : inner ℝ (T v) v = ∑ i : Fin N, hT.eigenvalues hN i * (inner ℝ (hT.eigenvectorBasis hN i) v)^2 := by    rw [← OrthonormalBasis.sum_inner_mul_inner (hT.eigenvectorBasis hN) (T v) v]    apply Finset.sum_congr rfl    intro i _    rw [hT v (hT.eigenvectorBasis hN i), hT.apply_eigenvectorBasis hN i, inner_smul_right]    simp only [RCLike.ofReal_real_eq_id, id_eq]    rw [real_inner_comm v]    ring  have pars : inner ℝ v v = ∑ i : Fin N, (inner ℝ (hT.eigenvectorBasis hN i) v)^2 := by    rw [← OrthonormalBasis.sum_inner_mul_inner (hT.eigenvectorBasis hN) v v]    apply Finset.sum_congr rfl    intro i _    rw [real_inner_comm v]    ring  rw [qform, pars, Finset.mul_sum]  apply Finset.sum_le_sum  intro k _  by_cases hk : k = j0  · subst hk; rw [hv]; simp  · exact mul_le_mul_of_nonneg_right (hc k hk) (sq_nonneg _)open Classical SimpleGraph Matrix inlemma spectral_moore_adj_quadform_aux_deg {V : Type*} [Fintype V] (G : SimpleGraph V) (k : ℕ)    (hreg : G.IsRegularOfDegree k) (x : V → ℝ) :    x ⬝ᵥ (G.adjMatrix ℝ *ᵥ x) ≤ k * (x ⬝ᵥ x) := by  have h := (G.posSemidef_lapMatrix ℝ).dotProduct_mulVec_nonneg x  simp only [star_trivial, lapMatrix, sub_mulVec, dotProduct_sub,    dotProduct_mulVec_degMatrix] at h  have : ∑ i : V, (G.degree i : ℝ) * x i * x i = k * (x ⬝ᵥ x) := by    simp only [dotProduct, Finset.mul_sum, hreg.degree_eq]    exact Finset.sum_congr rfl fun i _ => by ring  linarithopen Classical SimpleGraph Matrix intheorem spectral_moore_adj_quadform_le_of_sum_eq_zero {V : Type*} [Fintype V]    (G : SimpleGraph V) (k : ℕ) (θ : ℝ) (hreg : G.IsRegularOfDegree k)    (hθ : spectral_moore_second_eigenvalue_le G θ) (z : V → ℝ) (hz : ∑ v, z v = 0) :    z ⬝ᵥ (G.adjMatrix ℝ *ᵥ z) ≤ θ * (z ⬝ᵥ z) := by  set A := G.adjMatrix ℝ with hA  have hdeg := spectral_moore_adj_quadform_aux_deg G k hreg  have hsymm : A.toEuclideanLin.IsSymmetric :=    isSymmetric_toEuclideanLin_iff.mpr (G.isHermitian_adjMatrix ℝ)  have h1 : A *ᵥ (fun _ : V => (1 : ℝ)) = fun _ => (k : ℝ) := by    funext v    simp only [A, 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 one_A_z : (fun _ : V => (1 : ℝ)) ⬝ᵥ (A *ᵥ z) = 0 := by    rw [hAsymm, h1]; simp [dotProduct, ← Finset.mul_sum, hz]  have one_A_one : (fun _ : V => (1 : ℝ)) ⬝ᵥ (A *ᵥ (fun _ : V => (1 : ℝ))) = k * Fintype.card V := by    rw [h1]; simp [dotProduct, mul_comm]  have one_one : (fun _ : V => (1 : ℝ)) ⬝ᵥ (fun _ : V => (1 : ℝ)) = Fintype.card V := by    simp only [dotProduct, mul_one, Finset.sum_const, Finset.card_univ, nsmul_eq_mul]  have z_one : z ⬝ᵥ (fun _ : V => (1 : ℝ)) = 0 := by simp [dotProduct, hz]  by_cases hkθ : (k : ℝ) ≤ θ  · have := hdeg z    have hzz : 0 ≤ z ⬝ᵥ z := by      simp only [dotProduct]; exact Finset.sum_nonneg fun i _ => mul_self_nonneg _    nlinarith  rw [not_le] at hkθ  rcases Nat.eq_zero_or_pos (Fintype.card V) with hn | hn  · have : IsEmpty V := Fintype.card_eq_zero_iff.mp hn    simp [dotProduct]  -- the Rayleigh bound on the complement of the top eigenvector  have e1 : ∀ u w : V → ℝ, inner ℝ (WithLp.toLp 2 u) (WithLp.toLp 2 w) = u ⬝ᵥ w := by    intro u w; rw [EuclideanSpace.inner_eq_star_dotProduct]; simp [dotProduct_comm]  set b := hsymm.eigenvectorBasis finrank_euclideanSpace ⟨0, by simpa [finrank_euclideanSpace] using hn⟩ with hb  have key : ∀ y : V → ℝ, inner ℝ b (WithLp.toLp 2 y) = 0 →      y ⬝ᵥ (A *ᵥ y) ≤ θ * (y ⬝ᵥ y) := by    intro y hy    have := spectral_moore_adj_quadform_aux_qf A.toEuclideanLin hsymm finrank_euclideanSpace _ θ      (fun i hi => hθ i (by        rcases i with ⟨i, hi'⟩        simp only [ne_eq, Fin.mk.injEq] at hi        simp only; omega)) _ hy    rw [show A.toEuclideanLin (WithLp.toLp 2 y) = WithLp.toLp 2 (A *ᵥ y) from rfl, e1, e1] at this    rwa [dotProduct_comm]  set one : V → ℝ := fun _ => 1 with hone  have hn' : (0 : ℝ) < Fintype.card V := by exact_mod_cast hn  by_cases hγ : inner ℝ b (WithLp.toLp 2 one) = 0  · have := key one hγ    rw [one_A_one, one_one] at this    nlinarith  set β := inner ℝ b (WithLp.toLp 2 z) / inner ℝ b (WithLp.toLp 2 one) with hβ  have hy : inner ℝ b (WithLp.toLp 2 (z - β • one)) = 0 := by    rw [WithLp.toLp_sub, WithLp.toLp_smul, inner_sub_right, inner_smul_right, hβ]    field_simp; ring  have := key _ hy  have exp1 : (z - β • one) ⬝ᵥ (A *ᵥ (z - β • one)) =      z ⬝ᵥ (A *ᵥ z) - 2 * β * (one ⬝ᵥ (A *ᵥ z)) + β ^ 2 * (one ⬝ᵥ (A *ᵥ one)) := by    have hs : one ⬝ᵥ (A *ᵥ z) = z ⬝ᵥ (A *ᵥ one) := by rw [hAsymm, dotProduct_comm]    simp only [mulVec_sub, mulVec_smul, sub_dotProduct, dotProduct_sub, smul_dotProduct,      dotProduct_smul, smul_eq_mul, hs]    ring  have exp2 : (z - β • one) ⬝ᵥ (z - β • one) = z ⬝ᵥ z + β ^ 2 * (one ⬝ᵥ one) := by    have hs : one ⬝ᵥ z = 0 := by rw [dotProduct_comm]; exact z_one    simp only [sub_dotProduct, dotProduct_sub, smul_dotProduct, dotProduct_smul, smul_eq_mul, hs,      z_one]    ring  rw [exp1, exp2, one_A_z, one_A_one, one_one] at this  have hβ2 : 0 ≤ β ^ 2 * Fintype.card V := by positivity  nlinarith
See it in the graphDiscuss this resultChallenge it