spectral_moore_seidel_switch_degree_sum_ge
Let G be a k-regular finite simple graph on V with n = |V| ≥ 2k + 2, X : Set V, and suppose every vertex of the Seidel switching F = spectral_moore_seidel_switch G X has degree at most d0, where d0 < k. Then n * ((n - 2k + 1) / 2) ≤ ∑ v, F.degree v + 2 * d0 ^ 2 (natural-number division and subtraction); that is, the average degree of F is at least ⌈(n - 2k)/2⌉ - 2 d0²/n.
Statement
open Classical SimpleGraph Matrix in theorem spectral_moore_seidel_switch_degree_sum_ge {V : Type*} [Fintype V] (G : SimpleGraph V) (X : Set V) (k d0 : ℕ) (hreg : G.IsRegularOfDegree k) (hd0 : d0 < k) (hF : ∀ v, (spectral_moore_seidel_switch G X).degree v ≤ d0) (hn : 2 * k + 2 ≤ Fintype.card V) : Fintype.card V * ((Fintype.card V - 2 * k + 1) / 2) ≤ ∑ v, (spectral_moore_seidel_switch G X).degree v + 2 * d0 ^ 2
- Source
- arXiv:2611.00591 (A spectral Moore problem and the Yang-Koolen conjecture), Section 5, Lemma 5.2, inequality (13)
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- spectral_moore_seidel_switchSeidel switching: for a simple graph G : SimpleGraph V and a set X : Set V, the simple graph on V in which distinct vertices u, v are…
- Used by 1
- spectral_moore_max_order_le_of_large_degree_of_switch_degree_boundsLet θ ≥ 1. Suppose (i) there are D, N₀ such that every k-regular graph G on Fin n with second largest adjacency eigenvalue at most θ, 2k +…
The proof, explained
The proof uses the algebraic representation of Seidel switching via a signature vector s ∈ {-1, 1}^V. By expressing the switched adjacency matrix in terms of s and computing vertex degrees, the total degree sum is written as (n² - T²)/2 + ∑_v s(v) R(v), where T = ∑ s(v) and R = A_G s. A triangle inequality yields ∑_v s(v) R(v) ≥ 2k|T| - kn, while the assumption that all switched degrees are at most d0 < k forces both signs to occur, yielding n - 2k + |T| ≤ 2 d0. Squaring this two-sided bound and analyzing the parity of T completes the inequality.
Define the switched graph F, the number of vertices n, and the signature vector s ∈ {-1, 1}^V.
Let F be the Seidel switch of G with respect to X, let n = |V|, and define the sign vector s : V → ℝ by s(v) = 1 if v ∈ X and s(v) = -1 if v ∉ X. In particular, s(v)² = 1 for every vertex v.
set F := spectral_moore_seidel_switch G X with hFdef set n := Fintype.card V with hndef set s : V → ℝ := fun v => if v ∈ X then 1 else -1 with hs have hs2 : ∀ v, s v * s v = 1 := by intro v; simp only [hs]; split_ifs <;> norm_num
The adjacency matrix of F satisfies A_F(u, v) = (1 - s(u)s(v))/2 + s(u)s(v) A_G(u, v) for all u, v.
If u = v, both sides equal 0 because simple graphs have no self-loops and s(u)² = 1. If u ≠ v, by definition of Seidel switching, u and v are adjacent in F if and only if either they are adjacent in G and have the same sign (both in X or neither in X), or they are non-adjacent in G and have opposite signs. Testing the four sign combinations shows this equivalence matches the algebraic expression (1 - s(u)s(v))/2 + s(u)s(v) A_G(u, v).
uses
adjMatrix_applyhave hentry : ∀ u v, F.adjMatrix ℝ u v = (1 - s u * s v) / 2 + s u * s v * G.adjMatrix ℝ u v := by intro u v by_cases huv : u = v · subst huv; simp [hs2] have hadj : F.Adj u v ↔ (G.Adj u v ↔ (u ∈ X ↔ v ∈ X)) := by change u ≠ v ∧ _ ↔ _ simp [huv] rw [adjMatrix_apply, adjMatrix_apply] simp only [hs] by_cases hu : u ∈ X <;> by_cases hv : v ∈ X <;> by_cases hG : G.Adj u v <;> simp [hu, hv, hG, hadj]
The row sums of A_G equal k, and the vector R = A_G s satisfies |R(v)| ≤ k for every vertex v.
Define R(v) = ∑_u A_G(v, u) s(u) and T = ∑_u s(u). Because G is k-regular, each row sum of its adjacency matrix A_G is k. Since the matrix entries are non-negative and -1 ≤ s(u) ≤ 1, each row product R(v) is bounded in absolute value by the row sum k.
uses
abs_le,Finset.sum_neg_distrib,Finset.sum_le_sum,adjMatrix_applyset R : V → ℝ := fun v => ∑ u, G.adjMatrix ℝ v u * s u with hR set T : ℝ := ∑ u, s u with hT have hrow : ∀ v, ∑ u, G.adjMatrix ℝ v u = k := by intro v have := G.adjMatrix_mulVec_const_apply (α := ℝ) (a := 1) (v := v) simpa [mulVec, dotProduct, hreg.degree_eq] using this have hRle : ∀ v, |R v| ≤ k := by intro v rw [abs_le, ← hrow v] constructor · rw [← Finset.sum_neg_distrib] simp only [hR] refine Finset.sum_le_sum fun u _ => ?_ have h0 : 0 ≤ G.adjMatrix ℝ v u := by rw [adjMatrix_apply]; split_ifs <;> norm_num have : -1 ≤ s u := by simp only [hs]; split_ifs <;> norm_num nlinarith · simp only [hR] refine Finset.sum_le_sum fun u _ => ?_ have h0 : 0 ≤ G.adjMatrix ℝ v u := by rw [adjMatrix_apply]; split_ifs <;> norm_num have : s u ≤ 1 := by simp only [hs]; split_ifs <;> norm_num nlinarith
For each vertex v, deg_F(v) = (n - s(v) T)/2 + s(v) R(v).
The degree of v in F is the sum of row v of A_F. Summing the formula A_F(v, u) = (1 - s(v)s(u))/2 + s(v)s(u) A_G(v, u) over all u yields (n - s(v) ∑_u s(u))/2 + s(v) ∑_u A_G(v, u) s(u), which simplifies to (n - s(v) T)/2 + s(v) R(v).
uses
mul_one,Function.const_apply,Finset.sum_add_distrib,Finset.sum_div,Finset.sum_sub_distrib,Finset.mul_sum,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,Finset.sum_congrhave hdeg : ∀ v, (F.degree v : ℝ) = (n - s v * T) / 2 + s v * R v := by intro v have := F.adjMatrix_mulVec_const_apply (α := ℝ) (a := 1) (v := v) rw [mul_one] at this rw [← this] simp only [mulVec, dotProduct, Function.const_apply, mul_one, hentry, Finset.sum_add_distrib, ← Finset.sum_div, Finset.sum_sub_distrib, hR, hT, Finset.mul_sum] simp only [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, mul_one, hndef] congr 1 exact Finset.sum_congr rfl fun u _ => by ring
∑_v R(v) = k T, and 2k |T| ≤ ∑_v (s(v) R(v) + k).
Summing R(v) over all vertices and exchanging the order of summation using the symmetry of A_G gives ∑_v R(v) = k ∑_u s(u) = k T. Furthermore, since s(v) ∈ {-1, 1} and |R(v)| ≤ k, we have s(v) R(v) + k = |R(v) + k s(v)|. Summing this and applying the triangle inequality yields ∑_v |R(v) + k s(v)| ≥ |∑_v (R(v) + k s(v))| = |k T + k T| = 2k |T|.
uses
Finset.sum_comm,Finset.mul_sum,Finset.sum_congr,Finset.sum_mul,abs_le,abs_of_nonneg,abs_of_nonpos,le_trans,Finset.abs_sum_le_sum_abs,Finset.sum_add_distrib,abs_mulhave hsumR : ∑ v, R v = k * T := by simp only [hR, hT] rw [Finset.sum_comm, Finset.mul_sum] refine Finset.sum_congr rfl fun u _ => ?_ rw [← Finset.sum_mul, ← hrow u] congr 1 exact Finset.sum_congr rfl fun v _ => by rw [(G.isSymm_adjMatrix (α := ℝ)).apply] have hterm : ∀ v, s v * R v + k = |R v + k * s v| := by intro v have := hRle v rw [abs_le] at this simp only [hs] at this ⊢ split_ifs · rw [abs_of_nonneg (by linarith)]; ring · rw [abs_of_nonpos (by linarith)]; ring have hkey : 2 * k * |T| ≤ ∑ v, (s v * R v + k) := by simp only [hterm] refine le_trans ?_ (Finset.abs_sum_le_sum_abs _ _) rw [Finset.sum_add_distrib, hsumR, ← Finset.mul_sum, ← hT] rw [show (k : ℝ) * T + k * T = 2 * k * T by ring, abs_mul, abs_of_nonneg (by positivity : (0:ℝ) ≤ 2 * k)]
∑_v deg_F(v) = (n² - T²)/2 + ∑_v s(v) R(v), with ∑_v s(v) R(v) ≥ 2k |T| - kn.
Summing the degree formula over all v gives ∑_v deg_F(v) = (n² - T²)/2 + ∑_v s(v) R(v). Expanding ∑_v (s(v) R(v) + k) = ∑_v s(v) R(v) + kn in the inequality 2k |T| ≤ ∑_v (s(v) R(v) + k) and rearranging gives the lower bound ∑_v s(v) R(v) ≥ 2k |T| - kn.
uses
Finset.sum_add_distrib,Finset.sum_div,Finset.sum_sub_distrib,Finset.sum_mul,Finset.sum_const,Finset.card_univ,nsmul_eq_mulhave hsumdeg : ∑ v, (F.degree v : ℝ) = (n * n - T * T) / 2 + ∑ v, s v * R v := by simp only [hdeg, Finset.sum_add_distrib, ← Finset.sum_div, Finset.sum_sub_distrib, ← Finset.sum_mul, ← hT, Finset.sum_const, Finset.card_univ, nsmul_eq_mul, hndef] have hsR : ∑ v, s v * R v ≥ 2 * k * |T| - k * n := by have := hkey rw [Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, nsmul_eq_mul] at this rw [← hndef] at this linarith
Both s = 1 and s = -1 occur, implying (n - T)/2 - k ≤ d0 and (n + T)/2 - k ≤ d0, hence n - 2k + |T| ≤ 2 d0.
For every vertex v, deg_F(v) ≤ d0 and s(v) R(v) ≥ -k imply (n - s(v) T)/2 - k ≤ d0. If s were constant on V (meaning X = ∅ or X = V), then F would equal G, so every vertex would have degree k > d0, a contradiction. Hence there exist vertices v1 with s(v1) = 1 and v2 with s(v2) = -1. Evaluating the lower bound at both vertices produces (n ∓ T)/2 - k ≤ d0, which together give n - 2k + |T| ≤ 2 d0.
uses
abs_le,Fintype.card_pos_iff.mp,Finset.sum_mul,Finset.sum_const,Finset.card_univ,nsmul_eq_mulhave hlow : ∀ v, (n - s v * T) / 2 - k ≤ d0 := by intro v have h1 := hdeg v have h2 : (F.degree v : ℝ) ≤ d0 := by exact_mod_cast hF v have h3 := hRle v have h4 : -(k : ℝ) ≤ s v * R v := by rw [abs_le] at h3 simp only [hs]; split_ifs <;> linarith [h3.1, h3.2] linarith have hcard_pos : 0 < n := by omega have hallX : ∀ σ : ℝ, (∀ v, s v = σ) → σ * σ = 1 → False := by intro σ hσ hσ2 obtain ⟨v⟩ : Nonempty V := Fintype.card_pos_iff.mp (by rw [← hndef]; exact hcard_pos) have hRv : R v = σ * k := by simp only [hR, hσ, ← Finset.sum_mul, hrow]; ring have hTv : T = σ * n := by simp only [hT, hσ, Finset.sum_const, Finset.card_univ, nsmul_eq_mul, hndef]; ring have h1 := hdeg v rw [hσ v, hRv, hTv] at h1 have h2 : (F.degree v : ℝ) ≤ d0 := by exact_mod_cast hF v have h3 : (d0 : ℝ) < k := by exact_mod_cast hd0 have : (F.degree v : ℝ) = k := by rw [h1]; linear_combination (k - n / 2) * hσ2 linarith have hX : ∃ v, s v = 1 := by by_contra h push Not at h exact hallX (-1) (fun v => by have := h v; simp only [hs] at this ⊢; split_ifs at this ⊢ <;> simp_all) (by norm_num) have hY : ∃ v, s v = -1 := by by_contra h push Not at h exact hallX 1 (fun v => by have := h v; simp only [hs] at this ⊢; split_ifs at this ⊢ <;> simp_all) (by norm_num) obtain ⟨v1, hv1⟩ := hX obtain ⟨v2, hv2⟩ := hY have hl1 := hlow v1 have hl2 := hlow v2 rw [hv1] at hl1 rw [hv2] at hl2
T = 2|X| - n, and setting c = ⌊(n - 2k + 1)/2⌋ gives 2c + 2k ≤ n + 1.
Let a = |X|. Partitioning V into X and V \ X shows T = a - (n - a) = 2a - n. Setting c = (n - 2k + 1) / 2 using integer division, we have 2c + 2k ≤ n + 1 by definition of integer division.
uses
Finset.sum_ite,Finset.sum_const,nsmul_eq_mul,mul_one,mul_neg,Finset.card_filter_add_card_filter_not,Finset.card_univ,Finset.card_filter_le-- parity of T set a := (Finset.univ.filter (fun v => v ∈ X)).card with ha have hTa : T = 2 * (a : ℝ) - n := by simp only [hT, hs, Finset.sum_ite, Finset.sum_const, nsmul_eq_mul, mul_one, mul_neg] have := Finset.card_filter_add_card_filter_not (s := Finset.univ) (fun v => v ∈ X) rw [Finset.card_univ, ← hndef, ← ha] at this have h' : ((Finset.univ.filter (fun v => ¬ v ∈ X)).card : ℝ) = n - a := by rw [← this]; push_cast; ring rw [h']; ring have ha_le : a ≤ n := by rw [ha, hndef]; exact (Finset.card_filter_le _ _).trans (by rw [Finset.card_univ]) set c := (n - 2 * k + 1) / 2 with hc have hc1 : 2 * c + 2 * k ≤ n + 1 := by omega have hc1r : 2 * (c : ℝ) + 2 * k ≤ n + 1 := by exact_mod_cast hc1 have hd0r : (0 : ℝ) ≤ d0 := by positivity have hnr : 2 * (k : ℝ) + 2 ≤ n := by exact_mod_cast hn have hkr : (0 : ℝ) ≤ k := by positivity
n * c ≤ ∑_v deg_F(v) + 2 d0².
We split into cases based on whether 2a = n: - If 2a = n, then T = 0 and n is even, so 2c + 2k ≤ n. Then ∑_v deg_F(v) ≥ n²/2 - kn = n(n - 2k)/2 ≥ n c, which finishes the claim since 2 d0² ≥ 0. - If 2a ≠ n, then T is a non-zero integer, so |T| ≥ 1. Squaring n - 2k + |T| ≤ 2 d0 gives (n - 2k + |T|)² ≤ 4 d0². Combining this with the lower bound on ∑_v deg_F(v), the bound n(2c + 2k) ≤ n(n + 1), and the non-negativity of (n - 2k)(n - 2k + 2|T| - 1) and k(|T| - 1) implies n c ≤ ∑_v deg_F(v) + 2 d0² over ℝ. Casting back to ℕ completes the proof.
uses
eq_or_ne,abs_zero,Int.one_le_abs,abs_mul_abs_self,abs_cases,mul_le_mul_of_nonneg_left,mul_self_le_mul_self,mul_nonneghave goal : (n : ℝ) * c ≤ ∑ v, (F.degree v : ℝ) + 2 * (d0 : ℝ) ^ 2 := by rw [hsumdeg] rcases eq_or_ne (2 * a) n with h2a | h2a · have hT0 : T = 0 := by rw [hTa]; exact_mod_cast (by omega : (2 * a : ℤ) - n = 0) have hc0 : 2 * c + 2 * k ≤ n := by omega have hc0r : 2 * (c : ℝ) + 2 * k ≤ n := by exact_mod_cast hc0 rw [hT0, abs_zero] at hsR rw [hT0] nlinarith · have hT1 : 1 ≤ |T| := by rw [hTa] have : (1 : ℤ) ≤ |(2 * a : ℤ) - n| := Int.one_le_abs (by omega) exact_mod_cast this have hTT : T * T = |T| * |T| := (abs_mul_abs_self T).symm have hm : (n : ℝ) - 2 * k + |T| ≤ 2 * d0 := by rcases abs_cases T with ⟨h, _⟩ | ⟨h, _⟩ <;> rw [h] <;> linarith rw [hTT] have hn0 : (0 : ℝ) ≤ n := by positivity have F1 : (n : ℝ) * (2 * c + 2 * k) ≤ n * (n + 1) := mul_le_mul_of_nonneg_left hc1r hn0 have F2 : ((n : ℝ) - 2 * k + |T|) * ((n : ℝ) - 2 * k + |T|) ≤ (2 * d0) * (2 * d0) := mul_self_le_mul_self (by linarith) hm have F3 : 0 ≤ ((n : ℝ) - 2 * k) * ((n : ℝ) - 2 * k + 2 * |T| - 1) := mul_nonneg (by linarith) (by linarith) have F4 : 0 ≤ (k : ℝ) * (|T| - 1) := mul_nonneg hkr (by linarith) linarith exact_mod_cast goal
adjMatrix_apply- The (u, v)-entry of the adjacency matrix of a simple graph is 1 if u and v are adjacent and 0 otherwise.
abs_le- |a| ≤ b if and only if -b ≤ a and a ≤ b.
Finset.sum_neg_distrib- The sum of negations over a finite set equals the negation of the sum.
Finset.sum_le_sum- If f(i) ≤ g(i) for every element in a finite set, then the sum of f is at most the sum of g.
mul_one- Multiplying an element by 1 leaves it unchanged.
Function.const_apply- Evaluating a constant function at any point gives the constant value.
Finset.sum_add_distrib- The sum of a term-by-term sum of two functions equals the sum of their individual sums.
Finset.sum_div- Dividing a finite sum by a scalar distributes over each term of the sum.
Finset.sum_sub_distrib- The sum of a difference of functions equals the difference of their individual sums.
Finset.mul_sum- Multiplying a finite sum by a scalar on the left distributes into each summand.
Finset.sum_const- Summing a constant value b over a finite set s equals |s| times b.
Finset.card_univ- The cardinality of the universal finset of a finite type equals the type's cardinality.
nsmul_eq_mul- Natural-number scalar multiplication in a semiring equals multiplication by the natural number cast to the ring.
Finset.sum_congr- Two finite sums are equal if their index sets are identical and their summands agree on all elements.
Finset.sum_comm- The order of summation in a double finite sum may be interchanged.
Finset.sum_mul- Multiplying a finite sum by a scalar on the right distributes into each summand.
abs_of_nonneg- The absolute value of a non-negative number is the number itself.
abs_of_nonpos- The absolute value of a non-positive number is its negation.
le_trans- The less-than-or-equal relation is transitive.
Finset.abs_sum_le_sum_abs- The triangle inequality for finite sums: the absolute value of a sum is at most the sum of the absolute values.
abs_mul- The absolute value of a product is the product of the absolute values.
Fintype.card_pos_iff.mp- If a finite type has strictly positive cardinality, it is nonempty.
Finset.sum_ite- A sum of conditional terms can be split into the sum over elements satisfying the condition plus the sum over those that do not.
mul_neg- Multiplying by a negated number negates the product.
Finset.card_filter_add_card_filter_not- The size of the subset of elements satisfying a predicate plus the size of the subset not satisfying it equals the cardinality of the full set.
Finset.card_filter_le- The cardinality of a filtered subset is at most the cardinality of the original finite set.
eq_or_ne- Any two elements in a type are either equal or not equal.
abs_zero- The absolute value of 0 is 0.
Int.one_le_abs- Any non-zero integer has absolute value at least 1.
abs_mul_abs_self- The square of the absolute value of a real number equals the square of the number itself.
abs_cases- Every real number either is non-negative and equals its absolute value, or is negative and equals the negation of its absolute value.
mul_le_mul_of_nonneg_left- Multiplying an inequality on the left by a non-negative scalar preserves the inequality.
mul_self_le_mul_self- If 0 ≤ a ≤ b, then a² ≤ b².
mul_nonneg- The product of two non-negative numbers is non-negative.
- In Step 9, the final inequality in ℝ is deduced by linarith from four explicit intermediate inequalities (labelled F1 through F4 in the source), which bound the integral quotient c, square the two-sided degree bound on T, and verify the non-negativity of cross-terms.
- The theorem uses integer division and natural subtraction in its statement: (n - 2 * k + 1) / 2 is the integer quotient ⌊(n - 2k + 1)/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_seidel_switch_degree_sum_ge {V : Type*} [Fintype V] (G : SimpleGraph V) (X : Set V) (k d0 : ℕ) (hreg : G.IsRegularOfDegree k) (hd0 : d0 < k) (hF : ∀ v, (spectral_moore_seidel_switch G X).degree v ≤ d0) (hn : 2 * k + 2 ≤ Fintype.card V) : Fintype.card V * ((Fintype.card V - 2 * k + 1) / 2) ≤ ∑ v, (spectral_moore_seidel_switch G X).degree v + 2 * d0 ^ 2 := by set F := spectral_moore_seidel_switch G X with hFdef set n := Fintype.card V with hndef set s : V → ℝ := fun v => if v ∈ X then 1 else -1 with hs have hs2 : ∀ v, s v * s v = 1 := by intro v; simp only [hs]; split_ifs <;> norm_num have hentry : ∀ u v, F.adjMatrix ℝ u v = (1 - s u * s v) / 2 + s u * s v * G.adjMatrix ℝ u v := by intro u v by_cases huv : u = v · subst huv; simp [hs2] have hadj : F.Adj u v ↔ (G.Adj u v ↔ (u ∈ X ↔ v ∈ X)) := by change u ≠ v ∧ _ ↔ _ simp [huv] rw [adjMatrix_apply, adjMatrix_apply] simp only [hs] by_cases hu : u ∈ X <;> by_cases hv : v ∈ X <;> by_cases hG : G.Adj u v <;> simp [hu, hv, hG, hadj] set R : V → ℝ := fun v => ∑ u, G.adjMatrix ℝ v u * s u with hR set T : ℝ := ∑ u, s u with hT have hrow : ∀ v, ∑ u, G.adjMatrix ℝ v u = k := by intro v have := G.adjMatrix_mulVec_const_apply (α := ℝ) (a := 1) (v := v) simpa [mulVec, dotProduct, hreg.degree_eq] using this have hRle : ∀ v, |R v| ≤ k := by intro v rw [abs_le, ← hrow v] constructor · rw [← Finset.sum_neg_distrib] simp only [hR] refine Finset.sum_le_sum fun u _ => ?_ have h0 : 0 ≤ G.adjMatrix ℝ v u := by rw [adjMatrix_apply]; split_ifs <;> norm_num have : -1 ≤ s u := by simp only [hs]; split_ifs <;> norm_num nlinarith · simp only [hR] refine Finset.sum_le_sum fun u _ => ?_ have h0 : 0 ≤ G.adjMatrix ℝ v u := by rw [adjMatrix_apply]; split_ifs <;> norm_num have : s u ≤ 1 := by simp only [hs]; split_ifs <;> norm_num nlinarith have hdeg : ∀ v, (F.degree v : ℝ) = (n - s v * T) / 2 + s v * R v := by intro v have := F.adjMatrix_mulVec_const_apply (α := ℝ) (a := 1) (v := v) rw [mul_one] at this rw [← this] simp only [mulVec, dotProduct, Function.const_apply, mul_one, hentry, Finset.sum_add_distrib, ← Finset.sum_div, Finset.sum_sub_distrib, hR, hT, Finset.mul_sum] simp only [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, mul_one, hndef] congr 1 exact Finset.sum_congr rfl fun u _ => by ring have hsumR : ∑ v, R v = k * T := by simp only [hR, hT] rw [Finset.sum_comm, Finset.mul_sum] refine Finset.sum_congr rfl fun u _ => ?_ rw [← Finset.sum_mul, ← hrow u] congr 1 exact Finset.sum_congr rfl fun v _ => by rw [(G.isSymm_adjMatrix (α := ℝ)).apply] have hterm : ∀ v, s v * R v + k = |R v + k * s v| := by intro v have := hRle v rw [abs_le] at this simp only [hs] at this ⊢ split_ifs · rw [abs_of_nonneg (by linarith)]; ring · rw [abs_of_nonpos (by linarith)]; ring have hkey : 2 * k * |T| ≤ ∑ v, (s v * R v + k) := by simp only [hterm] refine le_trans ?_ (Finset.abs_sum_le_sum_abs _ _) rw [Finset.sum_add_distrib, hsumR, ← Finset.mul_sum, ← hT] rw [show (k : ℝ) * T + k * T = 2 * k * T by ring, abs_mul, abs_of_nonneg (by positivity : (0:ℝ) ≤ 2 * k)] have hsumdeg : ∑ v, (F.degree v : ℝ) = (n * n - T * T) / 2 + ∑ v, s v * R v := by simp only [hdeg, Finset.sum_add_distrib, ← Finset.sum_div, Finset.sum_sub_distrib, ← Finset.sum_mul, ← hT, Finset.sum_const, Finset.card_univ, nsmul_eq_mul, hndef] have hsR : ∑ v, s v * R v ≥ 2 * k * |T| - k * n := by have := hkey rw [Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, nsmul_eq_mul] at this rw [← hndef] at this linarith have hlow : ∀ v, (n - s v * T) / 2 - k ≤ d0 := by intro v have h1 := hdeg v have h2 : (F.degree v : ℝ) ≤ d0 := by exact_mod_cast hF v have h3 := hRle v have h4 : -(k : ℝ) ≤ s v * R v := by rw [abs_le] at h3 simp only [hs]; split_ifs <;> linarith [h3.1, h3.2] linarith have hcard_pos : 0 < n := by omega have hallX : ∀ σ : ℝ, (∀ v, s v = σ) → σ * σ = 1 → False := by intro σ hσ hσ2 obtain ⟨v⟩ : Nonempty V := Fintype.card_pos_iff.mp (by rw [← hndef]; exact hcard_pos) have hRv : R v = σ * k := by simp only [hR, hσ, ← Finset.sum_mul, hrow]; ring have hTv : T = σ * n := by simp only [hT, hσ, Finset.sum_const, Finset.card_univ, nsmul_eq_mul, hndef]; ring have h1 := hdeg v rw [hσ v, hRv, hTv] at h1 have h2 : (F.degree v : ℝ) ≤ d0 := by exact_mod_cast hF v have h3 : (d0 : ℝ) < k := by exact_mod_cast hd0 have : (F.degree v : ℝ) = k := by rw [h1]; linear_combination (k - n / 2) * hσ2 linarith have hX : ∃ v, s v = 1 := by by_contra h push Not at h exact hallX (-1) (fun v => by have := h v; simp only [hs] at this ⊢; split_ifs at this ⊢ <;> simp_all) (by norm_num) have hY : ∃ v, s v = -1 := by by_contra h push Not at h exact hallX 1 (fun v => by have := h v; simp only [hs] at this ⊢; split_ifs at this ⊢ <;> simp_all) (by norm_num) obtain ⟨v1, hv1⟩ := hX obtain ⟨v2, hv2⟩ := hY have hl1 := hlow v1 have hl2 := hlow v2 rw [hv1] at hl1 rw [hv2] at hl2 -- parity of T set a := (Finset.univ.filter (fun v => v ∈ X)).card with ha have hTa : T = 2 * (a : ℝ) - n := by simp only [hT, hs, Finset.sum_ite, Finset.sum_const, nsmul_eq_mul, mul_one, mul_neg] have := Finset.card_filter_add_card_filter_not (s := Finset.univ) (fun v => v ∈ X) rw [Finset.card_univ, ← hndef, ← ha] at this have h' : ((Finset.univ.filter (fun v => ¬ v ∈ X)).card : ℝ) = n - a := by rw [← this]; push_cast; ring rw [h']; ring have ha_le : a ≤ n := by rw [ha, hndef]; exact (Finset.card_filter_le _ _).trans (by rw [Finset.card_univ]) set c := (n - 2 * k + 1) / 2 with hc have hc1 : 2 * c + 2 * k ≤ n + 1 := by omega have hc1r : 2 * (c : ℝ) + 2 * k ≤ n + 1 := by exact_mod_cast hc1 have hd0r : (0 : ℝ) ≤ d0 := by positivity have hnr : 2 * (k : ℝ) + 2 ≤ n := by exact_mod_cast hn have hkr : (0 : ℝ) ≤ k := by positivity have goal : (n : ℝ) * c ≤ ∑ v, (F.degree v : ℝ) + 2 * (d0 : ℝ) ^ 2 := by rw [hsumdeg] rcases eq_or_ne (2 * a) n with h2a | h2a · have hT0 : T = 0 := by rw [hTa]; exact_mod_cast (by omega : (2 * a : ℤ) - n = 0) have hc0 : 2 * c + 2 * k ≤ n := by omega have hc0r : 2 * (c : ℝ) + 2 * k ≤ n := by exact_mod_cast hc0 rw [hT0, abs_zero] at hsR rw [hT0] nlinarith · have hT1 : 1 ≤ |T| := by rw [hTa] have : (1 : ℤ) ≤ |(2 * a : ℤ) - n| := Int.one_le_abs (by omega) exact_mod_cast this have hTT : T * T = |T| * |T| := (abs_mul_abs_self T).symm have hm : (n : ℝ) - 2 * k + |T| ≤ 2 * d0 := by rcases abs_cases T with ⟨h, _⟩ | ⟨h, _⟩ <;> rw [h] <;> linarith rw [hTT] have hn0 : (0 : ℝ) ≤ n := by positivity have F1 : (n : ℝ) * (2 * c + 2 * k) ≤ n * (n + 1) := mul_le_mul_of_nonneg_left hc1r hn0 have F2 : ((n : ℝ) - 2 * k + |T|) * ((n : ℝ) - 2 * k + |T|) ≤ (2 * d0) * (2 * d0) := mul_self_le_mul_self (by linarith) hm have F3 : 0 ≤ ((n : ℝ) - 2 * k) * ((n : ℝ) - 2 * k + 2 * |T| - 1) := mul_nonneg (by linarith) (by linarith) have F4 : 0 ≤ (k : ℝ) * (|T| - 1) := mul_nonneg hkr (by linarith) linarith exact_mod_cast goal