spectral_moore_adj_quadform_le_of_sum_eq_zero
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
- spectral_moore_second_eigenvalue_leFor a finite simple graph G, the second largest adjacency eigenvalue is at most θ.
- IsSymmetricA symmetric bilinear function.
- Used by 1
- spectral_moore_adj_quadform_le_add_sum_sqFor 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…
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.
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⟩².
uses
OrthonormalBasis.sum_inner_mul_inner,Finset.sum_congr,inner_smul_right,RCLike.ofReal_real_eq_id,id_eq,real_inner_commhave 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
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⟩².
uses
OrthonormalBasis.sum_inner_mul_inner,Finset.sum_congr,real_inner_commhave 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
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⟩.
uses
Finset.mul_sum,Finset.sum_le_sum,mul_le_mul_of_nonneg_right,sq_nonnegrw [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 _)
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).
uses
star_trivial,lapMatrix,sub_mulVec,dotProduct_sub,dotProduct_mulVec_degMatrix,dotProduct,Finset.mul_sum,Finset.sum_congrhave 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
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.
uses
spectral_moore_adj_quadform_aux_degset 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 ℝ)
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.
uses
adjMatrix_mulVec_apply,Finset.sum_const,card_neighborFinset_eq_degree,nsmul_eq_mul,mul_onehave 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]
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.
uses
dotProduct_mulVec,mulVec_transpose,dotProduct_commhave 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]
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|.
uses
dotProduct,Finset.mul_sum,mul_comm,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,mul_onehave 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]
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.
uses
dotProduct,Finset.sum_nonneg,mul_self_nonnegby_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
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.
uses
not_le,Nat.eq_zero_or_pos,dotProductrw [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]
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 θ.
uses
EuclideanSpace.inner_eq_star_dotProduct,dotProduct_comm,finrank_euclideanSpace,spectral_moore_adj_quadform_aux_qf,ne_eq,Fin.mk.injEqhave 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]
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.
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
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 - β • 𝟏.
uses
WithLp.toLp_sub,WithLp.toLp_smul,inner_sub_right,inner_smul_rightset β := 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
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.
uses
dotProduct_comm,mulVec_sub,mulVec_smul,sub_dotProduct,dotProduct_sub,smul_dotProduct,dotProduct_smul,smul_eq_mulhave 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
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.
uses
dotProduct_comm,sub_dotProduct,dotProduct_sub,smul_dotProduct,dotProduct_smul,smul_eq_mulhave 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
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.
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.
- The proof operates in two formal settings: matrix-vector algebra on (V → ℝ) with dotProduct, and coordinate-free geometry on EuclideanSpace ℝ V with the inner product. The bridge between them is WithLp.toLp 2, and the top eigenvector basis vector b is obtained from the spectral theorem at index ⟨0, _⟩.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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