AFTD Auto-Formalizing Theoretical Domains

spectral_moore_seidel_switch_degree_sum_ge

theoremverified

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

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.

  1. 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.

    lines 8–11

      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
  2. 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).

    lines 12–22

    uses adjMatrix_apply

      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]
  3. 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.

    lines 23–43

    uses abs_le, Finset.sum_neg_distrib, Finset.sum_le_sum, adjMatrix_apply

      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
  4. 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).

    lines 44–53

    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_congr

      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
  5. ∑_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|.

    lines 54–74

    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_mul

      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)]
  6. ∑_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.

    lines 75–82

    uses Finset.sum_add_distrib, Finset.sum_div, Finset.sum_sub_distrib, Finset.sum_mul, Finset.sum_const, Finset.card_univ, nsmul_eq_mul

      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
  7. 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.

    lines 83–119

    uses abs_le, Fintype.card_pos_iff.mp, Finset.sum_mul, Finset.sum_const, Finset.card_univ, nsmul_eq_mul

      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
  8. 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.

    lines 120–136

    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
  9. 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.

    lines 137–162

    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_nonneg

      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
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.

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_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
See it in the graphDiscuss this resultChallenge it