spectral_moore_adj_quadform_le_add_sum_sq
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
- spectral_moore_adj_quadform_le_of_sum_eq_zeroFor a k-regular finite simple graph G on a vertex type V whose second largest adjacency eigenvalue is at most θ…
- spectral_moore_second_eigenvalue_leFor a finite simple graph G, the second largest adjacency eigenvalue is at most θ.
- Used by 1
- spectral_moore_seidel_switch_adj_quadform_leLet G be a k-regular finite simple graph on V with second largest adjacency eigenvalue at most θ and k ≤ θ + |V|/2. Then for every X : Set…
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.
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$.
uses
Nat.eq_zero_or_pos,Fintype.card_eq_zero_iff.mprcases Nat.eq_zero_or_pos (Fintype.card V) with hn | hn · have : IsEmpty V := Fintype.card_eq_zero_iff.mp hn simp [dotProduct]
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$.
uses
Pi.sub_apply,Pi.smul_apply,smul_eq_mul,mul_one,Finset.sum_sub_distrib,Finset.sum_const,Finset.card_univ,nsmul_eq_mulhave 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
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}$.
uses
spectral_moore_adj_quadform_le_of_sum_eq_zerohave 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]
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$.
uses
adjMatrix_mulVec_apply,Finset.sum_const,card_neighborFinset_eq_degree,mul_one,nsmul_eq_mul,dotProduct_mulVec,mulVec_transpose,dotProduct_commhave 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]
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|$.
uses
dotProduct_comm,Finset.mul_sum,mul_comm,mul_one,Finset.sum_const,Finset.card_univ,nsmul_eq_mulhave 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
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.
uses
mulVec_add,mulVec_smul,add_dotProduct,dotProduct_add,smul_dotProduct,dotProduct_smul,smul_eq_mulrw [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)$.
- The final inequality is closed by the automated non-linear arithmetic tactic `nlinarith`, which combines the quadratic form bound on the zero-sum component with the scalar inequality $k \le \theta + |V|/2$.
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.
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