AFTD Auto-Formalizing Theoretical Domains

amply_regular_dist_two_lipschitz_sum_bound

theoremverified

Scale-two Lipschitz estimate of arXiv:2610.36620, Section 3.1 (inequality (21) with gain B ≥ μ): let G be amply regular with parameters (k, ℓ, μ) with μ > 1 and ℓ ≤ μ, and let p, q be vertices at distance 2. Then for every 1-Lipschitz f : V → ℝ the two neighbourhood sums over N(p) and N(q) differ by at most 2(k − μ). Equivalently (Kantorovich duality) the Ollivier–Ricci curvature of the pair (p, q) is at least μ/k. Tight for the hypercube Q_n (k = n, ℓ = 0, μ = 2) and for K_{m,m}; the hypothesis μ > 1 is needed (large cycles, μ = 1, are counterexamples).

Statement

theorem amply_regular_dist_two_lipschitz_sum_bound {V : Type*} [Fintype V] {G : SimpleGraph V}
    [DecidableRel G.Adj] {k ℓ μ : ℕ} (hG : IsAmplyRegular G k ℓ μ) (hμ1 : 1 < μ) (hμℓ : ℓ ≤ μ)
    {p q : V} (hpq : G.dist p q = 2) (f : V → ℝ)
    (hf : ∀ a b : V, |f a - f b| ≤ (G.dist a b : ℝ)) :
    |∑ z ∈ G.neighborFinset p, f z - ∑ z ∈ G.neighborFinset q, f z| ≤ 2 * ((k - μ : ℕ) : ℝ)
Source
step towards amply_regular_diameter_bound_qpk
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • IsAmplyRegularA graph G on a finite vertex set is amply regular with parameters (k, ℓ, μ) if it is regular of degree k, every pair of adjacent vertices…

The proof, explained

The goal is to prove that for any 1-Lipschitz function f and vertices p, q at distance 2 in an amply regular graph with μ > 1 and ℓ ≤ μ, the neighborhood sums satisfy |∑_{N(p)} f - ∑_{N(q)} f| ≤ 2(k - μ). Common neighbors C = N(p) ∩ N(q) contribute identically to both sums and cancel, reducing the claim to bounding the difference of private neighborhood sums ∑_Y f - ∑_X f, where X = N(p) \ N(q) and Y = N(q) \ N(p) each have cardinality k - μ. Choosing a common neighbor z ∈ C (which exists because μ > 1) and considering Z = N(z) \ {p, q}, double summation over edges between X ∪ Y and Z yields the algebraic identity ∑_{x ∈ X, w ∈ N(x) ∩ Z} (f(w) - f(x)) + ∑_{y ∈ Y, w ∈ N(y) ∩ Z} (f(y) - f(w)) = (μ - 1)(∑_Y f - ∑_X f). Since ℓ ≤ μ, each vertex in X or Y has at most μ - 1 neighbors in Z; since f is 1-Lipschitz, each edge difference is at most 1, bounding the total sum by (|X| + |Y|)(μ - 1) = 2(k - μ)(μ - 1). Dividing by μ - 1 > 0 yields the one-sided bound, and symmetry between p and q concludes the two-sided estimate.

  1. It suffices to establish a one-sided bound on ∑_Y f - ∑_X f for arbitrary vertices p₀, q₀ at distance 2, whose common neighborhoods have cardinality ℓ if adjacent and μ if at distance 2.

    We introduce an auxiliary lemma `key` asserting ∑_{z ∈ Y} f(z) - ∑_{z ∈ X} f(z) ≤ 2(k - μ) for any vertices p₀, q₀ with dist(p₀, q₀) = 2, where C = N(p₀) ∩ N(q₀), X = N(p₀) \ N(q₀), and Y = N(q₀) \ N(p₀). We also establish that for any vertices a, b, the size of their neighborhood intersection |N(a) ∩ N(b)| equals the cardinality of their common neighbors, which is ℓ when a ~ b and μ when dist(a, b) = 2 by the definition of an amply regular graph.

    lines 7–24

    uses Set.toFinset_card, SimpleGraph.mem_commonNeighbors, SimpleGraph.mem_neighborFinset

      classical
      have key : ∀ (p0 q0 : V), G.dist p0 q0 = 2 →
          (∑ z ∈ G.neighborFinset q0 \ G.neighborFinset p0, f z)
            - (∑ z ∈ G.neighborFinset p0 \ G.neighborFinset q0, f z) ≤ 2 * ((k - μ : ℕ) : ℝ) := by
        intro p0 q0 hpq
        set C := G.neighborFinset p0 ∩ G.neighborFinset q0 with hCdef
        set X := G.neighborFinset p0 \ G.neighborFinset q0 with hXdef
        set Y := G.neighborFinset q0 \ G.neighborFinset p0 with hYdef
        have interCard : ∀ a b : V,
            (G.neighborFinset a ∩ G.neighborFinset b).card = Fintype.card (G.commonNeighbors a b) := by
          intro a b
          rw [← Set.toFinset_card]; congr 1; ext x
          simp [SimpleGraph.mem_commonNeighbors, SimpleGraph.mem_neighborFinset]
        have hcn_adj : ∀ a b : V, G.Adj a b → (G.neighborFinset a ∩ G.neighborFinset b).card = ℓ := by
          intro a b hab; rw [interCard]; exact hG.adj_commonNeighbors hab
        have hcn_dist : ∀ a b : V, G.dist a b = 2 →
            (G.neighborFinset a ∩ G.neighborFinset b).card = μ := by
          intro a b hab; rw [interCard]; exact hG.dist_two_commonNeighbors hab
  2. A 2-step walk between non-adjacent distinct vertices witnesses distance 2, |N(p₀)| = |N(q₀)| = k, |C| = μ, and there exists a common neighbor z ∈ C adjacent to both p₀ and q₀.

    We prove that if a ~ b ~ c with a ≁ c and a ≠ c, then dist(a, c) = 2 because the walk has length 2 and the distance cannot be 0 or 1. Regularity gives |N(p₀)| = |N(q₀)| = k, and the distance-2 condition gives |C| = μ. Since μ > 1, C is nonempty, so we can pick a common neighbor z ∈ C, which is adjacent to both p₀ and q₀. Finally, p₀ ≁ q₀ because dist(p₀, q₀) = 2 ≠ 1.

    lines 25–48

    uses SimpleGraph.dist_le, SimpleGraph.Walk.cons, SimpleGraph.Walk.nil, Finset.card_pos, Finset.mem_inter, SimpleGraph.dist_eq_one_iff_adj

        have dist2 : ∀ a b c : V, G.Adj a b → G.Adj b c → ¬ G.Adj a c → a ≠ c → G.dist a c = 2 := by
          intro a b c hab hbc hac hne
          have hle : G.dist a c ≤ 2 := by
            have h := SimpleGraph.dist_le
              (SimpleGraph.Walk.cons hab (SimpleGraph.Walk.cons hbc SimpleGraph.Walk.nil) : G.Walk a c)
            simpa using h
          have hreach : G.Reachable a c :=
            (SimpleGraph.Walk.cons hab (SimpleGraph.Walk.cons hbc SimpleGraph.Walk.nil)).reachable
          have hgt : 1 < G.dist a c := hreach.one_lt_dist_of_ne_of_not_adj hne hac
          omega
        have hNp : (G.neighborFinset p0).card = k := by
          rw [G.card_neighborFinset_eq_degree, hG.regular.degree_eq p0]
        have hNq : (G.neighborFinset q0).card = k := by
          rw [G.card_neighborFinset_eq_degree, hG.regular.degree_eq q0]
        have hC_card : C.card = μ := by
          rw [hCdef, interCard, hG.dist_two_commonNeighbors hpq]
        have hCne : C.Nonempty := Finset.card_pos.mp (by rw [hC_card]; omega)
        obtain ⟨z, hzC⟩ := hCne
        have hzNp : z ∈ G.neighborFinset p0 := (Finset.mem_inter.mp (hCdef ▸ hzC)).1
        have hzNq : z ∈ G.neighborFinset q0 := (Finset.mem_inter.mp (hCdef ▸ hzC)).2
        have hzp : G.Adj z p0 := ((G.mem_neighborFinset p0 z).mp hzNp).symm
        have hzq : G.Adj z q0 := ((G.mem_neighborFinset q0 z).mp hzNq).symm
        have hpq_adj : ¬ G.Adj p0 q0 := by
          intro h; have : G.dist p0 q0 = 1 := SimpleGraph.dist_eq_one_iff_adj.mpr h; omega
  3. The set Z = N(z) \ {p₀, q₀} is defined, and N(p₀) and N(q₀) decompose as disjoint unions X ∪ C and Y ∪ C.

    We define the auxiliary set Z by removing p₀ and q₀ from the neighborhood of z. The neighborhoods N(p₀) and N(q₀) partition into private and common neighbors: N(p₀) = X ∪ C and N(q₀) = Y ∪ C, with disjointness following from the definitions of set difference and intersection. We also characterize membership in X and Y in terms of adjacency: w ∈ X ↔ w ~ p₀ ∧ w ≁ q₀, and symmetrically for Y.

    lines 49–63

    uses Finset.sdiff_union_inter, Finset.inter_comm, Finset.disjoint_left, SimpleGraph.adj_comm

        set Z := G.neighborFinset z \ ({p0, q0} : Finset V) with hZdef
        have hNp_split : G.neighborFinset p0 = X ∪ C := by
          rw [hXdef, hCdef, Finset.sdiff_union_inter]
        have hNq_split : G.neighborFinset q0 = Y ∪ C := by
          rw [hYdef, hCdef, Finset.inter_comm, Finset.sdiff_union_inter]
        have hXC : Disjoint X C := by
          rw [hXdef, hCdef, Finset.disjoint_left]; intro a ha hb
          exact (Finset.mem_sdiff.mp ha).2 (Finset.mem_inter.mp hb).2
        have hYC : Disjoint Y C := by
          rw [hYdef, hCdef, Finset.disjoint_left]; intro a ha hb
          exact (Finset.mem_sdiff.mp ha).2 (Finset.mem_inter.mp hb).1
        have hXmem : ∀ w : V, w ∈ X ↔ G.Adj w p0 ∧ ¬ G.Adj w q0 := by
          intro w; rw [hXdef]; simp [SimpleGraph.mem_neighborFinset, SimpleGraph.adj_comm]
        have hYmem : ∀ w : V, w ∈ Y ↔ G.Adj w q0 ∧ ¬ G.Adj w p0 := by
          intro w; rw [hYdef]; simp [SimpleGraph.mem_neighborFinset, SimpleGraph.adj_comm]
  4. For every x ∈ X, |N(x) ∩ Z| = (μ - 1) + (ℓ - μ) 𝟏_{x ∈ Z}, which is bounded by μ - 1 since ℓ ≤ μ.

    For x ∈ X, the common neighbors of x and z decompose disjointly as (N(x) ∩ Z) ∪ {p₀} because x ~ p₀ and z ~ p₀ but x ≁ q₀. Therefore, |N(x) ∩ Z| = |N(x) ∩ N(z)| - 1. If x ∈ Z, then x ~ z, so they have ℓ common neighbors and |N(x) ∩ Z| = ℓ - 1. If x ∉ Z, then x ≁ z, and since x ~ p₀ ~ z we have dist(x, z) = 2, yielding μ common neighbors and |N(x) ∩ Z| = μ - 1. Since ℓ ≤ μ, in both cases |N(x) ∩ Z| ≤ μ - 1.

    lines 64–122

    uses Finset.card_union_of_disjoint, Finset.card_singleton, Finset.disjoint_singleton_right, if_pos, if_neg, Nat.cast_sub, Nat.cast_le

        have hXval : ∀ x ∈ X, ((G.neighborFinset x ∩ Z).card : ℝ)
            = ((μ:ℝ) - 1) + ((ℓ:ℝ) - μ) * (if x ∈ Z then 1 else 0) := by
          intro x hx
          have hxp : G.Adj x p0 := ((hXmem x).mp hx).1
          have hxq : ¬ G.Adj x q0 := ((hXmem x).mp hx).2
          have hxNq : x ∉ G.neighborFinset q0 := fun h => hxq ((G.mem_neighborFinset q0 x).mp h).symm
          have hxNp_ne : x ≠ p0 := fun h => G.irrefl (h ▸ hxp)
          have hxq_ne : x ≠ q0 := fun h => hpq_adj (h ▸ hxp).symm
          have hxmem : x ∉ ({p0, q0} : Finset V) := by
            simp only [Finset.mem_insert, Finset.mem_singleton, not_or]; exact ⟨hxNp_ne, hxq_ne⟩
          have hxne_z : x ≠ z := fun h => hxNq (h ▸ hzNq)
          have hrel : (G.neighborFinset x ∩ Z).card + 1
              = (G.neighborFinset x ∩ G.neighborFinset z).card := by
            have hunion : G.neighborFinset x ∩ G.neighborFinset z
                = (G.neighborFinset x ∩ Z) ∪ {p0} := by
              rw [hZdef]; ext w
              simp only [Finset.mem_inter, Finset.mem_union, Finset.mem_singleton, Finset.mem_sdiff,
                SimpleGraph.mem_neighborFinset]
              constructor
              · rintro ⟨hxw, hzw⟩
                by_cases hwp : w = p0
                · exact Or.inr hwp
                · refine Or.inl ⟨hxw, hzw, ?_⟩
                  simp only [Finset.mem_insert, Finset.mem_singleton, not_or]
                  exact ⟨hwp, fun h => hxq (h ▸ hxw)⟩
              · rintro (⟨hxw, hzw, -⟩ | rfl)
                · exact ⟨hxw, hzw⟩
                · exact ⟨hxp, hzp⟩
            rw [hunion, Finset.card_union_of_disjoint, Finset.card_singleton]
            rw [Finset.disjoint_singleton_right]; rw [hZdef]; simp
          by_cases hxZ : x ∈ Z
          · have hxNz : x ∈ G.neighborFinset z := (Finset.mem_sdiff.mp (hZdef ▸ hxZ)).1
            have hxz : G.Adj x z := ((G.mem_neighborFinset z x).mp hxNz).symm
            have hcn : (G.neighborFinset x ∩ G.neighborFinset z).card = ℓ := hcn_adj x z hxz
            have hcard : (G.neighborFinset x ∩ Z).card = ℓ - 1 := by omega
            rw [hcard, if_pos hxZ, Nat.cast_sub (by omega : 1 ≤ ℓ)]
            push_cast; ring
          · have hxNz : x ∉ G.neighborFinset z := by
              intro h; exact hxZ (by rw [hZdef, Finset.mem_sdiff]; exact ⟨h, hxmem⟩)
            have hxz_adj : ¬ G.Adj x z := fun h => hxNz ((G.mem_neighborFinset z x).mpr h.symm)
            have hdist : G.dist x z = 2 := dist2 x p0 z hxp hzp.symm hxz_adj hxne_z
            have hcn : (G.neighborFinset x ∩ G.neighborFinset z).card = μ := hcn_dist x z hdist
            have hcard : (G.neighborFinset x ∩ Z).card = μ - 1 := by omega
            rw [hcard, if_neg hxZ, Nat.cast_sub (by omega : 1 ≤ μ)]
            push_cast; ring
        have hXbound : ∀ x ∈ X, (G.neighborFinset x ∩ Z).card ≤ μ - 1 := by
          intro x hx
          have hv := hXval x hx
          have hμ1' : 1 ≤ μ := by omega
          have kk : ((G.neighborFinset x ∩ Z).card : ℝ) ≤ (μ:ℝ) - 1 := by
            rw [hv]
            by_cases hxZ : x ∈ Z
            · rw [if_pos hxZ]
              have hℓμ : (ℓ:ℝ) ≤ (μ:ℝ) := by exact_mod_cast hμℓ
              linarith
            · rw [if_neg hxZ]; linarith
          have kk2 : ((G.neighborFinset x ∩ Z).card : ℝ) ≤ ((μ - 1 : ℕ) : ℝ) := by
            rw [Nat.cast_sub hμ1']; simpa using kk
          exact Nat.cast_le.mp kk2
  5. Symmetrically, for every y ∈ Y, |N(y) ∩ Z| = (μ - 1) + (ℓ - μ) 𝟏_{y ∈ Z} ≤ μ - 1.

    By the symmetric argument exchanging p₀ and q₀, the common neighbors of y ∈ Y and z split into (N(y) ∩ Z) ∪ {q₀}. Thus |N(y) ∩ Z| = ℓ - 1 if y ∈ Z and μ - 1 if y ∉ Z. Using ℓ ≤ μ once again, |N(y) ∩ Z| ≤ μ - 1.

    lines 123–181

    uses Finset.card_union_of_disjoint, Finset.card_singleton, Finset.disjoint_singleton_right, if_pos, if_neg, Nat.cast_sub, Nat.cast_le

        have hYval : ∀ y ∈ Y, ((G.neighborFinset y ∩ Z).card : ℝ)
            = ((μ:ℝ) - 1) + ((ℓ:ℝ) - μ) * (if y ∈ Z then 1 else 0) := by
          intro y hy
          have hyq : G.Adj y q0 := ((hYmem y).mp hy).1
          have hyp : ¬ G.Adj y p0 := ((hYmem y).mp hy).2
          have hyNp : y ∉ G.neighborFinset p0 := fun h => hyp ((G.mem_neighborFinset p0 y).mp h).symm
          have hyNq_ne : y ≠ q0 := fun h => G.irrefl (h ▸ hyq)
          have hyp_ne : y ≠ p0 := fun h => hpq_adj (h ▸ hyq)
          have hymem : y ∉ ({p0, q0} : Finset V) := by
            simp only [Finset.mem_insert, Finset.mem_singleton, not_or]; exact ⟨hyp_ne, hyNq_ne⟩
          have hyne_z : y ≠ z := fun h => hyNp (h ▸ hzNp)
          have hrel : (G.neighborFinset y ∩ Z).card + 1
              = (G.neighborFinset y ∩ G.neighborFinset z).card := by
            have hunion : G.neighborFinset y ∩ G.neighborFinset z
                = (G.neighborFinset y ∩ Z) ∪ {q0} := by
              rw [hZdef]; ext w
              simp only [Finset.mem_inter, Finset.mem_union, Finset.mem_singleton, Finset.mem_sdiff,
                SimpleGraph.mem_neighborFinset]
              constructor
              · rintro ⟨hyw, hzw⟩
                by_cases hwq : w = q0
                · exact Or.inr hwq
                · refine Or.inl ⟨hyw, hzw, ?_⟩
                  simp only [Finset.mem_insert, Finset.mem_singleton, not_or]
                  exact ⟨fun h => hyp (h ▸ hyw), hwq⟩
              · rintro (⟨hyw, hzw, -⟩ | rfl)
                · exact ⟨hyw, hzw⟩
                · exact ⟨hyq, hzq⟩
            rw [hunion, Finset.card_union_of_disjoint, Finset.card_singleton]
            rw [Finset.disjoint_singleton_right]; rw [hZdef]; simp
          by_cases hyZ : y ∈ Z
          · have hyNz : y ∈ G.neighborFinset z := (Finset.mem_sdiff.mp (hZdef ▸ hyZ)).1
            have hyz : G.Adj y z := ((G.mem_neighborFinset z y).mp hyNz).symm
            have hcn : (G.neighborFinset y ∩ G.neighborFinset z).card = ℓ := hcn_adj y z hyz
            have hcard : (G.neighborFinset y ∩ Z).card = ℓ - 1 := by omega
            rw [hcard, if_pos hyZ, Nat.cast_sub (by omega : 1 ≤ ℓ)]
            push_cast; ring
          · have hyNz : y ∉ G.neighborFinset z := by
              intro h; exact hyZ (by rw [hZdef, Finset.mem_sdiff]; exact ⟨h, hymem⟩)
            have hyz_adj : ¬ G.Adj y z := fun h => hyNz ((G.mem_neighborFinset z y).mpr h.symm)
            have hdist : G.dist y z = 2 := dist2 y q0 z hyq hzq.symm hyz_adj hyne_z
            have hcn : (G.neighborFinset y ∩ G.neighborFinset z).card = μ := hcn_dist y z hdist
            have hcard : (G.neighborFinset y ∩ Z).card = μ - 1 := by omega
            rw [hcard, if_neg hyZ, Nat.cast_sub (by omega : 1 ≤ μ)]
            push_cast; ring
        have hYbound : ∀ y ∈ Y, (G.neighborFinset y ∩ Z).card ≤ μ - 1 := by
          intro y hy
          have hv := hYval y hy
          have hμ1' : 1 ≤ μ := by omega
          have kk : ((G.neighborFinset y ∩ Z).card : ℝ) ≤ (μ:ℝ) - 1 := by
            rw [hv]
            by_cases hyZ : y ∈ Z
            · rw [if_pos hyZ]
              have hℓμ : (ℓ:ℝ) ≤ (μ:ℝ) := by exact_mod_cast hμℓ
              linarith
            · rw [if_neg hyZ]; linarith
          have kk2 : ((G.neighborFinset y ∩ Z).card : ℝ) ≤ ((μ - 1 : ℕ) : ℝ) := by
            rw [Nat.cast_sub hμ1']; simpa using kk
          exact Nat.cast_le.mp kk2
  6. For any sets of vertices A and B and function g, ∑_{a ∈ A} ∑_{b ∈ N(a) ∩ B} g(b) = ∑_{b ∈ B} |N(b) ∩ A| g(b).

    We prove a general double-summation exchange lemma: expressing the condition b ∈ N(a) ∩ B as an indicator that a and b are adjacent, we swap the order of summation over A and B. The inner sum over a ∈ A adjacent to b then sums g(b) exactly |N(b) ∩ A| times.

    lines 182–199

    uses Finset.sum_congr, Finset.sum_filter, Finset.sum_comm, Finset.sum_const, nsmul_eq_mul

        have sum_swap : ∀ (A B : Finset V) (g : V → ℝ),
            (∑ a ∈ A, ∑ b ∈ G.neighborFinset a ∩ B, g b)
              = ∑ b ∈ B, ((G.neighborFinset b ∩ A).card : ℝ) * g b := by
          intro A B g
          have step1 : (∑ a ∈ A, ∑ b ∈ G.neighborFinset a ∩ B, g b)
              = ∑ a ∈ A, ∑ b ∈ B, (if G.Adj a b then g b else 0) := by
            apply Finset.sum_congr rfl; intro a _
            have hfil : G.neighborFinset a ∩ B = B.filter (G.Adj a) := by
              ext w; simp only [Finset.mem_inter, Finset.mem_filter, SimpleGraph.mem_neighborFinset]
              exact ⟨fun h => ⟨h.2, h.1⟩, fun h => ⟨h.2, h.1⟩⟩
            rw [hfil, Finset.sum_filter]
          rw [step1, Finset.sum_comm]
          apply Finset.sum_congr rfl; intro b _
          rw [← Finset.sum_filter]
          have hset : A.filter (fun a => G.Adj a b) = G.neighborFinset b ∩ A := by
            ext a; simp only [Finset.mem_filter, Finset.mem_inter, SimpleGraph.mem_neighborFinset]
            exact ⟨fun h => ⟨h.2.symm, h.1⟩, fun h => ⟨h.2, h.1.symm⟩⟩
          rw [hset, Finset.sum_const, nsmul_eq_mul]
  7. For each u ∈ Z, the degree difference |N(u) ∩ X| - |N(u) ∩ Y| equals (ℓ - μ) 𝟏_{u ∈ X} + (μ - ℓ) 𝟏_{u ∈ Y}.

    Partitioning N(p₀) and N(q₀) into their components gives |N(u) ∩ N(p₀)| = |N(u) ∩ X| + |N(u) ∩ C| and |N(u) ∩ N(q₀)| = |N(u) ∩ Y| + |N(u) ∩ C|, so the intersection with C cancels upon subtraction. Since u ∈ Z is adjacent to z and z ~ p₀, q₀, the distance from u to p₀ is 1 (if u ~ p₀) or 2 (otherwise), making |N(u) ∩ N(p₀)| equal ℓ or μ. Case analysis on whether u is adjacent to p₀ and/or q₀ evaluates the difference as (ℓ - μ) 𝟏_{u ∈ X} + (μ - ℓ) 𝟏_{u ∈ Y}.

    lines 200–281

    uses Finset.inter_union_distrib_left, Finset.card_union_of_disjoint, if_pos, if_neg, if_true, if_false

        have hac : ∀ u : V, (G.neighborFinset u ∩ G.neighborFinset p0).card
            = (G.neighborFinset u ∩ X).card + (G.neighborFinset u ∩ C).card := by
          intro u
          conv_lhs => rw [hNp_split]
          rw [Finset.inter_union_distrib_left]
          have hd : Disjoint (G.neighborFinset u ∩ X) (G.neighborFinset u ∩ C) := by
            rw [Finset.disjoint_left]; intro a ha hb
            exact (Finset.disjoint_left.mp hXC) (Finset.mem_inter.mp ha).2 (Finset.mem_inter.mp hb).2
          rw [Finset.card_union_of_disjoint hd]
        have hbc : ∀ u : V, (G.neighborFinset u ∩ G.neighborFinset q0).card
            = (G.neighborFinset u ∩ Y).card + (G.neighborFinset u ∩ C).card := by
          intro u
          conv_lhs => rw [hNq_split]
          rw [Finset.inter_union_distrib_left]
          have hd : Disjoint (G.neighborFinset u ∩ Y) (G.neighborFinset u ∩ C) := by
            rw [Finset.disjoint_left]; intro a ha hb
            exact (Finset.disjoint_left.mp hYC) (Finset.mem_inter.mp ha).2 (Finset.mem_inter.mp hb).2
          rw [Finset.card_union_of_disjoint hd]
        have hcoef : ∀ u ∈ Z, ((G.neighborFinset u ∩ X).card : ℝ) - ((G.neighborFinset u ∩ Y).card : ℝ)
            = ((ℓ:ℝ) - μ) * (if u ∈ X then 1 else 0) + ((μ:ℝ) - ℓ) * (if u ∈ Y then 1 else 0) := by
          intro u hu
          have hu0 : u ∈ G.neighborFinset z \ ({p0, q0} : Finset V) := hZdef ▸ hu
          obtain ⟨huNz, humem⟩ := Finset.mem_sdiff.mp hu0
          have huz : G.Adj u z := ((G.mem_neighborFinset z u).mp huNz).symm
          have hune_p : u ≠ p0 := fun h => humem (by simp [h])
          have hune_q : u ≠ q0 := fun h => humem (by simp [h])
          have hcnp : ((G.neighborFinset u ∩ G.neighborFinset p0).card : ℝ)
              = ((G.neighborFinset u ∩ X).card : ℝ) + ((G.neighborFinset u ∩ C).card : ℝ) := by
            rw [hac u]; push_cast; ring
          have hcnq : ((G.neighborFinset u ∩ G.neighborFinset q0).card : ℝ)
              = ((G.neighborFinset u ∩ Y).card : ℝ) + ((G.neighborFinset u ∩ C).card : ℝ) := by
            rw [hbc u]; push_cast; ring
          have hdiff : ((G.neighborFinset u ∩ X).card : ℝ) - ((G.neighborFinset u ∩ Y).card : ℝ)
              = ((G.neighborFinset u ∩ G.neighborFinset p0).card : ℝ)
                - ((G.neighborFinset u ∩ G.neighborFinset q0).card : ℝ) := by
            rw [hcnp, hcnq]; ring
          have hcp : ((G.neighborFinset u ∩ G.neighborFinset p0).card : ℝ)
              = if G.Adj u p0 then (ℓ:ℝ) else (μ:ℝ) := by
            by_cases hadj : G.Adj u p0
            · rw [if_pos hadj, hcn_adj u p0 hadj]
            · rw [if_neg hadj, hcn_dist u p0 (dist2 u z p0 huz hzp hadj hune_p)]
          have hcq : ((G.neighborFinset u ∩ G.neighborFinset q0).card : ℝ)
              = if G.Adj u q0 then (ℓ:ℝ) else (μ:ℝ) := by
            by_cases hadj : G.Adj u q0
            · rw [if_pos hadj, hcn_adj u q0 hadj]
            · rw [if_neg hadj, hcn_dist u q0 (dist2 u z q0 huz hzq hadj hune_q)]
          rw [hdiff, hcp, hcq]
          by_cases hp : G.Adj u p0
          · by_cases hq : G.Adj u q0
            · have e1 : ¬ (u ∈ X) := fun h => ((hXmem u).mp h).2 hq
              have e2 : ¬ (u ∈ Y) := fun h => ((hYmem u).mp h).2 hp
              simp only [if_pos hp, if_pos hq, if_neg e1, if_neg e2]; ring
            · have e1 : u ∈ X := (hXmem u).mpr ⟨hp, hq⟩
              have e2 : ¬ (u ∈ Y) := fun h => ((hYmem u).mp h).2 hp
              simp only [if_pos hp, if_neg hq, if_pos e1, if_neg e2]; ring
          · by_cases hq : G.Adj u q0
            · have e1 : ¬ (u ∈ X) := fun h => hp ((hXmem u).mp h).1
              have e2 : u ∈ Y := (hYmem u).mpr ⟨hq, hp⟩
              simp only [if_neg hp, if_pos hq, if_neg e1, if_pos e2]; ring
            · have e1 : ¬ (u ∈ X) := fun h => hp ((hXmem u).mp h).1
              have e2 : ¬ (u ∈ Y) := fun h => hq ((hYmem u).mp h).1
              simp only [if_neg hp, if_neg hq, if_neg e1, if_neg e2]; ring
        have hterm : ∀ u ∈ Z, ((G.neighborFinset u ∩ X).card : ℝ) * f u
            - ((G.neighborFinset u ∩ Y).card : ℝ) * f u
            = ((ℓ:ℝ) - μ) * (if u ∈ X then f u else 0) + ((μ:ℝ) - ℓ) * (if u ∈ Y then f u else 0) := by
          intro u hu
          have hc := hcoef u hu
          have hst : ((G.neighborFinset u ∩ X).card : ℝ) * f u
              - ((G.neighborFinset u ∩ Y).card : ℝ) * f u
              = (((G.neighborFinset u ∩ X).card : ℝ) - ((G.neighborFinset u ∩ Y).card : ℝ)) * f u := by
            ring
          rw [hst, hc]
          by_cases hx : u ∈ X
          · by_cases hy : u ∈ Y
            · simp only [hx, hy, if_true, if_false]; ring
            · simp only [hx, hy, if_true, if_false]; ring
          · by_cases hy : u ∈ Y
            · simp only [hx, hy, if_true, if_false]; ring
            · simp only [hx, hy, if_true, if_false]; ring
        have haxp : ∀ x, (((μ:ℝ) - 1) + ((ℓ:ℝ) - μ) * (if x ∈ Z then 1 else 0)) * f x
            = ((μ:ℝ) - 1) * f x + ((ℓ:ℝ) - μ) * (if x ∈ Z then f x else 0) := by
          intro x; by_cases hxZ : x ∈ Z <;> simp only [hxZ, if_true, if_false] <;> ring
  8. The sum of differences along edges between X and Z plus those between Y and Z equals (μ - 1)(∑_{y ∈ Y} f(y) - ∑_{x ∈ X} f(x)).

    We expand the edge difference sums: ∑_{x ∈ X, w ∈ N(x) ∩ Z} (f(w) - f(x)) decomposes into ∑_{u ∈ Z} |N(u) ∩ X| f(u) - ∑_{x ∈ X} |N(x) ∩ Z| f(x) using the summation exchange lemma, and similarly for Y. Substituting the expressions for |N(u) ∩ X| - |N(u) ∩ Y|, |N(x) ∩ Z|, and |N(y) ∩ Z|, the cross terms involving X ∩ Z and Y ∩ Z with coefficient ℓ - μ cancel out completely via linear combination, leaving exactly (μ - 1)(∑_{y ∈ Y} f(y) - ∑_{x ∈ X} f(x)).

    lines 282–338

    uses Finset.sum_sub_distrib, Finset.sum_add_distrib, Finset.mul_sum, Finset.sum_ite_mem, Finset.inter_comm

        have hA : (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, (f w - f x))
            + (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, (f y - f w))
            = ((∑ y ∈ Y, f y) - (∑ x ∈ X, f x)) * ((μ:ℝ) - 1) := by
          have e1 : (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, (f w - f x))
              = (∑ u ∈ Z, ((G.neighborFinset u ∩ X).card : ℝ) * f u)
                - (∑ x ∈ X, ((G.neighborFinset x ∩ Z).card : ℝ) * f x) := by
            have ha : (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, (f w - f x))
                = (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, f w)
                  - (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, f x) := by
              rw [← Finset.sum_sub_distrib]
              apply Finset.sum_congr rfl; intro x hx
              rw [Finset.sum_sub_distrib]
            have hb : (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, f x)
                = ∑ x ∈ X, ((G.neighborFinset x ∩ Z).card : ℝ) * f x := by
              apply Finset.sum_congr rfl; intro x hx
              rw [Finset.sum_const, nsmul_eq_mul]
            rw [ha, hb, sum_swap X Z f]
          have e2 : (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, (f y - f w))
              = (∑ y ∈ Y, ((G.neighborFinset y ∩ Z).card : ℝ) * f y)
                - (∑ u ∈ Z, ((G.neighborFinset u ∩ Y).card : ℝ) * f u) := by
            have ha : (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, (f y - f w))
                = (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, f y)
                  - (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, f w) := by
              rw [← Finset.sum_sub_distrib]
              apply Finset.sum_congr rfl; intro y hy
              rw [Finset.sum_sub_distrib]
            have hb : (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, f y)
                = ∑ y ∈ Y, ((G.neighborFinset y ∩ Z).card : ℝ) * f y := by
              apply Finset.sum_congr rfl; intro y hy
              rw [Finset.sum_const, nsmul_eq_mul]
            rw [ha, hb, sum_swap Y Z f]
          have e3 : (∑ u ∈ Z, ((G.neighborFinset u ∩ X).card : ℝ) * f u)
              - (∑ u ∈ Z, ((G.neighborFinset u ∩ Y).card : ℝ) * f u)
              = ((ℓ:ℝ) - μ) * (∑ x ∈ X ∩ Z, f x) + ((μ:ℝ) - ℓ) * (∑ y ∈ Y ∩ Z, f y) := by
            rw [← Finset.sum_sub_distrib, Finset.sum_congr rfl hterm, Finset.sum_add_distrib,
              ← Finset.mul_sum, ← Finset.mul_sum, Finset.sum_ite_mem, Finset.sum_ite_mem,
              Finset.inter_comm Z X, Finset.inter_comm Z Y]
          have e4 : (∑ x ∈ X, ((G.neighborFinset x ∩ Z).card : ℝ) * f x)
              = ((μ:ℝ) - 1) * (∑ x ∈ X, f x) + ((ℓ:ℝ) - μ) * (∑ x ∈ X ∩ Z, f x) := by
            rw [show (∑ x ∈ X, ((G.neighborFinset x ∩ Z).card : ℝ) * f x)
                = ∑ x ∈ X, (((μ:ℝ) - 1) + ((ℓ:ℝ) - μ) * (if x ∈ Z then 1 else 0)) * f x
                from Finset.sum_congr rfl (fun x hx => by rw [hXval x hx])]
            rw [show (∑ x ∈ X, (((μ:ℝ) - 1) + ((ℓ:ℝ) - μ) * (if x ∈ Z then 1 else 0)) * f x)
                = ∑ x ∈ X, (((μ:ℝ) - 1) * f x + ((ℓ:ℝ) - μ) * (if x ∈ Z then f x else 0))
                from Finset.sum_congr rfl (fun x _ => haxp x)]
            rw [Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.mul_sum, Finset.sum_ite_mem]
          have e5 : (∑ y ∈ Y, ((G.neighborFinset y ∩ Z).card : ℝ) * f y)
              = ((μ:ℝ) - 1) * (∑ y ∈ Y, f y) + ((ℓ:ℝ) - μ) * (∑ y ∈ Y ∩ Z, f y) := by
            rw [show (∑ y ∈ Y, ((G.neighborFinset y ∩ Z).card : ℝ) * f y)
                = ∑ y ∈ Y, (((μ:ℝ) - 1) + ((ℓ:ℝ) - μ) * (if y ∈ Z then 1 else 0)) * f y
                from Finset.sum_congr rfl (fun y hy => by rw [hYval y hy])]
            rw [show (∑ y ∈ Y, (((μ:ℝ) - 1) + ((ℓ:ℝ) - μ) * (if y ∈ Z then 1 else 0)) * f y)
                = ∑ y ∈ Y, (((μ:ℝ) - 1) * f y + ((ℓ:ℝ) - μ) * (if y ∈ Z then f y else 0))
                from Finset.sum_congr rfl (fun y _ => haxp y)]
            rw [Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.mul_sum, Finset.sum_ite_mem]
          rw [e1, e2]
          linear_combination e3 - e4 + e5
  9. The two double sums of edge differences are bounded by |X|(μ - 1) and |Y|(μ - 1) respectively.

    Because f is 1-Lipschitz, for any adjacent vertices w and x we have f(w) - f(x) ≤ 1. Summing over w ∈ N(x) ∩ Z gives at most |N(x) ∩ Z| ≤ μ - 1. Summing this over all x ∈ X yields ≤ |X|(μ - 1). The exact same reasoning applies to the sum over y ∈ Y and w ∈ N(y) ∩ Z since f(y) - f(w) ≤ 1, giving an upper bound of |Y|(μ - 1).

    lines 339–390

    uses Finset.sum_le_sum, SimpleGraph.dist_comm, SimpleGraph.dist_eq_one_iff_adj, abs_le, mul_le_mul_of_nonneg_right, Nat.cast_sub

        have hbound1 : (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, (f w - f x))
            ≤ ((X.card : ℝ)) * ((μ:ℝ) - 1) := by
          calc (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, (f w - f x))
              ≤ ∑ x ∈ X, ((G.neighborFinset x ∩ Z).card : ℝ) * 1 := by
                apply Finset.sum_le_sum; intro x hx
                calc (∑ w ∈ G.neighborFinset x ∩ Z, (f w - f x))
                    ≤ ∑ w ∈ G.neighborFinset x ∩ Z, (1:ℝ) := by
                      apply Finset.sum_le_sum; intro w hw
                      have hxw : G.Adj x w := (G.mem_neighborFinset x w).mp (Finset.mem_inter.mp hw).1
                      have hd : G.dist w x = 1 := by
                        rw [SimpleGraph.dist_comm]; exact SimpleGraph.dist_eq_one_iff_adj.mpr hxw
                      have hb := hf w x
                      rw [hd] at hb; push_cast at hb
                      linarith [abs_le.mp hb]
                  _ = ((G.neighborFinset x ∩ Z).card : ℝ) * 1 := by
                      rw [Finset.sum_const, nsmul_eq_mul]
            _ ≤ ∑ x ∈ X, ((μ - 1 : ℕ) : ℝ) := by
                apply Finset.sum_le_sum; intro x hx
                have hb := hXbound x hx
                have : ((G.neighborFinset x ∩ Z).card : ℝ) * 1 ≤ ((μ - 1 : ℕ) : ℝ) * 1 := by
                  apply mul_le_mul_of_nonneg_right _ (by norm_num)
                  exact_mod_cast hb
                simpa using this
            _ = ((X.card : ℝ)) * ((μ:ℝ) - 1) := by
                rw [Finset.sum_const, nsmul_eq_mul, Nat.cast_sub (by omega : 1 ≤ μ)]
                ring
        have hbound2 : (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, (f y - f w))
            ≤ ((Y.card : ℝ)) * ((μ:ℝ) - 1) := by
          calc (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, (f y - f w))
              ≤ ∑ y ∈ Y, ((G.neighborFinset y ∩ Z).card : ℝ) * 1 := by
                apply Finset.sum_le_sum; intro y hy
                calc (∑ w ∈ G.neighborFinset y ∩ Z, (f y - f w))
                    ≤ ∑ w ∈ G.neighborFinset y ∩ Z, (1:ℝ) := by
                      apply Finset.sum_le_sum; intro w hw
                      have hyw : G.Adj y w := (G.mem_neighborFinset y w).mp (Finset.mem_inter.mp hw).1
                      have hd : G.dist w y = 1 := by
                        rw [SimpleGraph.dist_comm]; exact SimpleGraph.dist_eq_one_iff_adj.mpr hyw
                      have hb := hf w y
                      rw [hd] at hb; push_cast at hb
                      linarith [abs_le.mp hb]
                  _ = ((G.neighborFinset y ∩ Z).card : ℝ) * 1 := by
                      rw [Finset.sum_const, nsmul_eq_mul]
            _ ≤ ∑ y ∈ Y, ((μ - 1 : ℕ) : ℝ) := by
                apply Finset.sum_le_sum; intro y hy
                have hb := hYbound y hy
                have : ((G.neighborFinset y ∩ Z).card : ℝ) * 1 ≤ ((μ - 1 : ℕ) : ℝ) * 1 := by
                  apply mul_le_mul_of_nonneg_right _ (by norm_num)
                  exact_mod_cast hb
                simpa using this
            _ = ((Y.card : ℝ)) * ((μ:ℝ) - 1) := by
                rw [Finset.sum_const, nsmul_eq_mul, Nat.cast_sub (by omega : 1 ≤ μ)]
                ring
  10. The private neighborhoods satisfy |X| = |Y| = k - μ, and `key` holds: ∑_{y ∈ Y} f(y) - ∑_{x ∈ X} f(x) ≤ 2(k - μ).

    Since |N(p₀)| = |N(q₀)| = k and |C| = μ, the sizes of the set differences are |X| = |Y| = k - μ. Adding the two bounds from the previous step yields (μ - 1)(∑_{y ∈ Y} f(y) - ∑_{x ∈ X} f(x)) ≤ (|X| + |Y|)(μ - 1) = 2(k - μ)(μ - 1). Because μ > 1, we have μ - 1 > 0, so dividing by μ - 1 concludes the proof of `key`.

    lines 391–406

    uses Finset.card_sdiff, Finset.inter_comm, add_le_add

        have hμpos : (0:ℝ) < (μ:ℝ) - 1 := by
          have : (1:ℝ) < (μ:ℝ) := by exact_mod_cast hμ1
          linarith
        have hXc : ((X.card : ℝ)) = ((k - μ : ℕ) : ℝ) := by
          rw [hXdef, Finset.card_sdiff, Finset.inter_comm, interCard,
            hG.dist_two_commonNeighbors hpq, hNp]
        have hYc : ((Y.card : ℝ)) = ((k - μ : ℕ) : ℝ) := by
          rw [hYdef, Finset.card_sdiff, interCard, hG.dist_two_commonNeighbors hpq, hNq]
        have hle := add_le_add hbound1 hbound2
        rw [hXc, hYc, hA] at hle
        have hg : (∑ y ∈ Y, f y) - (∑ x ∈ X, f x)
            = (∑ z ∈ G.neighborFinset q0 \ G.neighborFinset p0, f z)
              - (∑ z ∈ G.neighborFinset p0 \ G.neighborFinset q0, f z) := by
          rw [hYdef, hXdef]
        rw [hg] at hle
        nlinarith [hμpos, hle]
  11. The absolute difference |∑_{z ∈ N(p)} f(z) - ∑_{z ∈ N(q)} f(z)| is at most 2(k - μ).

    Applying `key` to (p, q) gives ∑_{N(q) \ N(p)} f - ∑_{N(p) \ N(q)} f ≤ 2(k - μ), and applying it to (q, p) gives ∑_{N(p) \ N(q)} f - ∑_{N(q) \ N(p)} f ≤ 2(k - μ). The common neighbors N(p) ∩ N(q) contribute equally to the two neighborhood sums and cancel out, so ∑_{N(p)} f - ∑_{N(q)} f = ∑_{N(p) \ N(q)} f - ∑_{N(q) \ N(p)} f. The two one-sided bounds together establish the required two-sided absolute bound.

    lines 407–424

    uses SimpleGraph.dist_comm, Finset.sum_sdiff, Finset.inter_subset_left, Finset.inter_subset_right, abs_le

      have h1 := key p q hpq
      have h2 := key q p (by rw [SimpleGraph.dist_comm]; exact hpq)
      have hsub : (∑ z ∈ G.neighborFinset p, f z) - (∑ z ∈ G.neighborFinset q, f z)
          = (∑ z ∈ G.neighborFinset p \ G.neighborFinset q, f z)
            - (∑ z ∈ G.neighborFinset q \ G.neighborFinset p, f z) := by
        have hs1 := Finset.sum_sdiff (s₁ := G.neighborFinset p ∩ G.neighborFinset q)
          (s₂ := G.neighborFinset p) (f := f) Finset.inter_subset_left
        have hs2 := Finset.sum_sdiff (s₁ := G.neighborFinset p ∩ G.neighborFinset q)
          (s₂ := G.neighborFinset q) (f := f) Finset.inter_subset_right
        rw [show G.neighborFinset p \ (G.neighborFinset p ∩ G.neighborFinset q)
            = G.neighborFinset p \ G.neighborFinset q from by
          ext x; simp only [Finset.mem_sdiff, Finset.mem_inter]; tauto] at hs1
        rw [show G.neighborFinset q \ (G.neighborFinset p ∩ G.neighborFinset q)
            = G.neighborFinset q \ G.neighborFinset p from by
          ext x; simp only [Finset.mem_sdiff, Finset.mem_inter]; tauto] at hs2
        linarith
      rw [abs_le, hsub]
      exact ⟨by linarith, h2⟩
add_le_add
Adding two inequalities preserves the order: a ≤ b and c ≤ d imply a + c ≤ b + d.
abs_le
The absolute value inequality |a| ≤ b is equivalent to -b ≤ a ∧ a ≤ b.
Finset.card_singleton
The cardinality of a singleton set is 1.
Finset.card_sdiff
The cardinality of the difference t \ s is |t| - |s ∩ t|.
Finset.card_pos
A finite set has strictly positive cardinality if and only if it is nonempty.
Finset.card_union_of_disjoint
The cardinality of the union of disjoint finite sets is the sum of their cardinalities.
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.disjoint_singleton_right
A finite set is disjoint from a singleton {a} if and only if a is not in the set.
Finset.inter_comm
Intersection of finite sets is commutative: s ∩ t = t ∩ s.
Finset.inter_subset_left
The intersection s₁ ∩ s₂ is a subset of s₁.
Finset.inter_subset_right
The intersection s₁ ∩ s₂ is a subset of s₂.
Finset.inter_union_distrib_left
Intersection distributes over union: s ∩ (t ∪ u) = (s ∩ t) ∪ (s ∩ u).
Finset.mem_inter
An element belongs to the intersection of two finite sets if and only if it belongs to both.
Finset.mul_sum
Multiplication distributes over finite summation: a · ∑_i f(i) = ∑_i a · f(i).
Finset.sdiff_union_inter
For any two finite sets s and t, (s \ t) ∪ (s ∩ t) = s.
Finset.sum_add_distrib
The sum of a sum of functions equals the sum of their individual sums.
Finset.sum_comm
Double sums over finite sets can be exchanged: ∑_x ∑_y f(x, y) = ∑_y ∑_x f(x, y).
Finset.sum_congr
Two sums over equal index sets are equal if their summands agree on all elements.
Finset.sum_const
Summing a constant b over a finite set s yields |s| · b.
Finset.sum_filter
Summing over a filtered set equals summing an if-then-else expression over the unfiltered set.
Finset.sum_ite_mem
Summing an if-then-else indicator for membership in t over s equals the sum over s ∩ t.
Finset.sum_le_sum
A sum is bounded by another if the inequality holds pointwise for each term.
Finset.sum_sdiff
For a subset s₁ ⊆ s₂, the sum over s₂ splits as the sum over s₂ \ s₁ plus the sum over s₁.
Finset.sum_sub_distrib
The sum of a difference of functions equals the difference of their sums.
if_false
An if-then-else on the false proposition False reduces to the second branch.
if_neg
If a condition is false, the if-then-else expression evaluates to the 'else' branch.
if_pos
If a condition is true, the if-then-else expression evaluates to the 'then' branch.
if_true
An if-then-else on the true proposition True reduces to the first branch.
mul_le_mul_of_nonneg_right
Multiplying an inequality b ≤ c by a non-negative value a ≥ 0 preserves the inequality: b · a ≤ c · a.
Nat.cast_le
Casting natural numbers into an ordered field preserves and reflects the order: ↑m ≤ ↑n ↔ m ≤ n.
Nat.cast_sub
For natural numbers m ≤ n, the cast of n - m to a ring equals ↑n - ↑m.
nsmul_eq_mul
Scalar multiplication by a natural number n equals multiplication by ↑n.
Set.toFinset_card
The cardinality of the finset of elements in a finite set equals the fintype cardinality of the set subtype.
SimpleGraph.adj_comm
Adjacency in a simple graph is symmetric: u ~ v ↔ v ~ u.
SimpleGraph.dist_comm
The distance function in a simple graph is symmetric: dist(u, v) = dist(v, u).
SimpleGraph.dist_eq_one_iff_adj
Two vertices have graph distance 1 if and only if they are adjacent.
SimpleGraph.dist_le
The graph distance between two vertices is at most the length of any walk connecting them.
SimpleGraph.mem_commonNeighbors
A vertex belongs to the common neighbors of u and v if and only if it is adjacent to both u and v.
SimpleGraph.mem_neighborFinset
A vertex w is in the neighbor finset of v if and only if v and w are adjacent.
SimpleGraph.Walk.cons
Prepending an incident edge to a walk produces a walk from the edge's source to the original walk's destination.
SimpleGraph.Walk.nil
The empty walk from a vertex to itself, with length 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

Lean’s trace was cut to the first 400 of 456 tactics.

/-- Distance-two 1-Lipschitz estimate for amply regular graphs: |Σ_{N(p)} f − Σ_{N(q)} f| ≤ 2(k − μ) whenever dist p q = 2, μ > 1 and ℓ ≤ μ. -/theorem amply_regular_dist_two_lipschitz_sum_bound {V : Type*} [Fintype V] {G : SimpleGraph V}    [DecidableRel G.Adj] {k ℓ μ : ℕ} (hG : IsAmplyRegular G k ℓ μ) (hμ1 : 1 < μ) (hμℓ : ℓ ≤ μ)    {p q : V} (hpq : G.dist p q = 2) (f : V → ℝ)    (hf : ∀ a b : V, |f a - f b| ≤ (G.dist a b : ℝ)) :    |∑ z ∈ G.neighborFinset p, f z - ∑ z ∈ G.neighborFinset q, f z| ≤ 2 * ((k - μ : ℕ) : ℝ) := by  classical  have key : ∀ (p0 q0 : V), G.dist p0 q0 = 2 →      (∑ z ∈ G.neighborFinset q0 \ G.neighborFinset p0, f z)        - (∑ z ∈ G.neighborFinset p0 \ G.neighborFinset q0, f z) ≤ 2 * ((k - μ : ℕ) : ℝ) := by    intro p0 q0 hpq    set C := G.neighborFinset p0 ∩ G.neighborFinset q0 with hCdef    set X := G.neighborFinset p0 \ G.neighborFinset q0 with hXdef    set Y := G.neighborFinset q0 \ G.neighborFinset p0 with hYdef    have interCard : ∀ a b : V,        (G.neighborFinset a ∩ G.neighborFinset b).card = Fintype.card (G.commonNeighbors a b) := by      intro a b      rw [← Set.toFinset_card]; congr 1; ext x      simp [SimpleGraph.mem_commonNeighbors, SimpleGraph.mem_neighborFinset]    have hcn_adj : ∀ a b : V, G.Adj a b → (G.neighborFinset a ∩ G.neighborFinset b).card = ℓ := by      intro a b hab; rw [interCard]; exact hG.adj_commonNeighbors hab    have hcn_dist : ∀ a b : V, G.dist a b = 2 →        (G.neighborFinset a ∩ G.neighborFinset b).card = μ := by      intro a b hab; rw [interCard]; exact hG.dist_two_commonNeighbors hab    have dist2 : ∀ a b c : V, G.Adj a b → G.Adj b c → ¬ G.Adj a c → a ≠ c → G.dist a c = 2 := by      intro a b c hab hbc hac hne      have hle : G.dist a c ≤ 2 := by        have h := SimpleGraph.dist_le          (SimpleGraph.Walk.cons hab (SimpleGraph.Walk.cons hbc SimpleGraph.Walk.nil) : G.Walk a c)        simpa using h      have hreach : G.Reachable a c :=        (SimpleGraph.Walk.cons hab (SimpleGraph.Walk.cons hbc SimpleGraph.Walk.nil)).reachable      have hgt : 1 < G.dist a c := hreach.one_lt_dist_of_ne_of_not_adj hne hac      omega    have hNp : (G.neighborFinset p0).card = k := by      rw [G.card_neighborFinset_eq_degree, hG.regular.degree_eq p0]    have hNq : (G.neighborFinset q0).card = k := by      rw [G.card_neighborFinset_eq_degree, hG.regular.degree_eq q0]    have hC_card : C.card = μ := by      rw [hCdef, interCard, hG.dist_two_commonNeighbors hpq]    have hCne : C.Nonempty := Finset.card_pos.mp (by rw [hC_card]; omega)    obtain ⟨z, hzC⟩ := hCne    have hzNp : z ∈ G.neighborFinset p0 := (Finset.mem_inter.mp (hCdef ▸ hzC)).1    have hzNq : z ∈ G.neighborFinset q0 := (Finset.mem_inter.mp (hCdef ▸ hzC)).2    have hzp : G.Adj z p0 := ((G.mem_neighborFinset p0 z).mp hzNp).symm    have hzq : G.Adj z q0 := ((G.mem_neighborFinset q0 z).mp hzNq).symm    have hpq_adj : ¬ G.Adj p0 q0 := by      intro h; have : G.dist p0 q0 = 1 := SimpleGraph.dist_eq_one_iff_adj.mpr h; omega    set Z := G.neighborFinset z \ ({p0, q0} : Finset V) with hZdef    have hNp_split : G.neighborFinset p0 = X ∪ C := by      rw [hXdef, hCdef, Finset.sdiff_union_inter]    have hNq_split : G.neighborFinset q0 = Y ∪ C := by      rw [hYdef, hCdef, Finset.inter_comm, Finset.sdiff_union_inter]    have hXC : Disjoint X C := by      rw [hXdef, hCdef, Finset.disjoint_left]; intro a ha hb      exact (Finset.mem_sdiff.mp ha).2 (Finset.mem_inter.mp hb).2    have hYC : Disjoint Y C := by      rw [hYdef, hCdef, Finset.disjoint_left]; intro a ha hb      exact (Finset.mem_sdiff.mp ha).2 (Finset.mem_inter.mp hb).1    have hXmem : ∀ w : V, w ∈ X ↔ G.Adj w p0 ∧ ¬ G.Adj w q0 := by      intro w; rw [hXdef]; simp [SimpleGraph.mem_neighborFinset, SimpleGraph.adj_comm]    have hYmem : ∀ w : V, w ∈ Y ↔ G.Adj w q0 ∧ ¬ G.Adj w p0 := by      intro w; rw [hYdef]; simp [SimpleGraph.mem_neighborFinset, SimpleGraph.adj_comm]    have hXval : ∀ x ∈ X, ((G.neighborFinset x ∩ Z).card : ℝ)        = ((μ:ℝ) - 1) + ((ℓ:ℝ) - μ) * (if x ∈ Z then 1 else 0) := by      intro x hx      have hxp : G.Adj x p0 := ((hXmem x).mp hx).1      have hxq : ¬ G.Adj x q0 := ((hXmem x).mp hx).2      have hxNq : x ∉ G.neighborFinset q0 := fun h => hxq ((G.mem_neighborFinset q0 x).mp h).symm      have hxNp_ne : x ≠ p0 := fun h => G.irrefl (h ▸ hxp)      have hxq_ne : x ≠ q0 := fun h => hpq_adj (h ▸ hxp).symm      have hxmem : x ∉ ({p0, q0} : Finset V) := by        simp only [Finset.mem_insert, Finset.mem_singleton, not_or]; exact ⟨hxNp_ne, hxq_ne⟩      have hxne_z : x ≠ z := fun h => hxNq (h ▸ hzNq)      have hrel : (G.neighborFinset x ∩ Z).card + 1          = (G.neighborFinset x ∩ G.neighborFinset z).card := by        have hunion : G.neighborFinset x ∩ G.neighborFinset z            = (G.neighborFinset x ∩ Z) ∪ {p0} := by          rw [hZdef]; ext w          simp only [Finset.mem_inter, Finset.mem_union, Finset.mem_singleton, Finset.mem_sdiff,            SimpleGraph.mem_neighborFinset]          constructor          · rintro ⟨hxw, hzw⟩            by_cases hwp : w = p0            · exact Or.inr hwp            · refine Or.inl ⟨hxw, hzw, ?_⟩              simp only [Finset.mem_insert, Finset.mem_singleton, not_or]              exact ⟨hwp, fun h => hxq (h ▸ hxw)⟩          · rintro (⟨hxw, hzw, -⟩ | rfl)            · exact ⟨hxw, hzw⟩            · exact ⟨hxp, hzp⟩        rw [hunion, Finset.card_union_of_disjoint, Finset.card_singleton]        rw [Finset.disjoint_singleton_right]; rw [hZdef]; simp      by_cases hxZ : x ∈ Z      · have hxNz : x ∈ G.neighborFinset z := (Finset.mem_sdiff.mp (hZdef ▸ hxZ)).1        have hxz : G.Adj x z := ((G.mem_neighborFinset z x).mp hxNz).symm        have hcn : (G.neighborFinset x ∩ G.neighborFinset z).card = ℓ := hcn_adj x z hxz        have hcard : (G.neighborFinset x ∩ Z).card = ℓ - 1 := by omega        rw [hcard, if_pos hxZ, Nat.cast_sub (by omega : 1 ≤ ℓ)]        push_cast; ring      · have hxNz : x ∉ G.neighborFinset z := by          intro h; exact hxZ (by rw [hZdef, Finset.mem_sdiff]; exact ⟨h, hxmem⟩)        have hxz_adj : ¬ G.Adj x z := fun h => hxNz ((G.mem_neighborFinset z x).mpr h.symm)        have hdist : G.dist x z = 2 := dist2 x p0 z hxp hzp.symm hxz_adj hxne_z        have hcn : (G.neighborFinset x ∩ G.neighborFinset z).card = μ := hcn_dist x z hdist        have hcard : (G.neighborFinset x ∩ Z).card = μ - 1 := by omega        rw [hcard, if_neg hxZ, Nat.cast_sub (by omega : 1 ≤ μ)]        push_cast; ring    have hXbound : ∀ x ∈ X, (G.neighborFinset x ∩ Z).card ≤ μ - 1 := by      intro x hx      have hv := hXval x hx      have hμ1' : 1 ≤ μ := by omega      have kk : ((G.neighborFinset x ∩ Z).card : ℝ) ≤ (μ:ℝ) - 1 := by        rw [hv]        by_cases hxZ : x ∈ Z        · rw [if_pos hxZ]          have hℓμ : (ℓ:ℝ) ≤ (μ:ℝ) := by exact_mod_cast hμℓ          linarith        · rw [if_neg hxZ]; linarith      have kk2 : ((G.neighborFinset x ∩ Z).card : ℝ) ≤ ((μ - 1 : ℕ) : ℝ) := by        rw [Nat.cast_sub hμ1']; simpa using kk      exact Nat.cast_le.mp kk2    have hYval : ∀ y ∈ Y, ((G.neighborFinset y ∩ Z).card : ℝ)        = ((μ:ℝ) - 1) + ((ℓ:ℝ) - μ) * (if y ∈ Z then 1 else 0) := by      intro y hy      have hyq : G.Adj y q0 := ((hYmem y).mp hy).1      have hyp : ¬ G.Adj y p0 := ((hYmem y).mp hy).2      have hyNp : y ∉ G.neighborFinset p0 := fun h => hyp ((G.mem_neighborFinset p0 y).mp h).symm      have hyNq_ne : y ≠ q0 := fun h => G.irrefl (h ▸ hyq)      have hyp_ne : y ≠ p0 := fun h => hpq_adj (h ▸ hyq)      have hymem : y ∉ ({p0, q0} : Finset V) := by        simp only [Finset.mem_insert, Finset.mem_singleton, not_or]; exact ⟨hyp_ne, hyNq_ne⟩      have hyne_z : y ≠ z := fun h => hyNp (h ▸ hzNp)      have hrel : (G.neighborFinset y ∩ Z).card + 1          = (G.neighborFinset y ∩ G.neighborFinset z).card := by        have hunion : G.neighborFinset y ∩ G.neighborFinset z            = (G.neighborFinset y ∩ Z) ∪ {q0} := by          rw [hZdef]; ext w          simp only [Finset.mem_inter, Finset.mem_union, Finset.mem_singleton, Finset.mem_sdiff,            SimpleGraph.mem_neighborFinset]          constructor          · rintro ⟨hyw, hzw⟩            by_cases hwq : w = q0            · exact Or.inr hwq            · refine Or.inl ⟨hyw, hzw, ?_⟩              simp only [Finset.mem_insert, Finset.mem_singleton, not_or]              exact ⟨fun h => hyp (h ▸ hyw), hwq⟩          · rintro (⟨hyw, hzw, -⟩ | rfl)            · exact ⟨hyw, hzw⟩            · exact ⟨hyq, hzq⟩        rw [hunion, Finset.card_union_of_disjoint, Finset.card_singleton]        rw [Finset.disjoint_singleton_right]; rw [hZdef]; simp      by_cases hyZ : y ∈ Z      · have hyNz : y ∈ G.neighborFinset z := (Finset.mem_sdiff.mp (hZdef ▸ hyZ)).1        have hyz : G.Adj y z := ((G.mem_neighborFinset z y).mp hyNz).symm        have hcn : (G.neighborFinset y ∩ G.neighborFinset z).card = ℓ := hcn_adj y z hyz        have hcard : (G.neighborFinset y ∩ Z).card = ℓ - 1 := by omega        rw [hcard, if_pos hyZ, Nat.cast_sub (by omega : 1 ≤ ℓ)]        push_cast; ring      · have hyNz : y ∉ G.neighborFinset z := by          intro h; exact hyZ (by rw [hZdef, Finset.mem_sdiff]; exact ⟨h, hymem⟩)        have hyz_adj : ¬ G.Adj y z := fun h => hyNz ((G.mem_neighborFinset z y).mpr h.symm)        have hdist : G.dist y z = 2 := dist2 y q0 z hyq hzq.symm hyz_adj hyne_z        have hcn : (G.neighborFinset y ∩ G.neighborFinset z).card = μ := hcn_dist y z hdist        have hcard : (G.neighborFinset y ∩ Z).card = μ - 1 := by omega        rw [hcard, if_neg hyZ, Nat.cast_sub (by omega : 1 ≤ μ)]        push_cast; ring    have hYbound : ∀ y ∈ Y, (G.neighborFinset y ∩ Z).card ≤ μ - 1 := by      intro y hy      have hv := hYval y hy      have hμ1' : 1 ≤ μ := by omega      have kk : ((G.neighborFinset y ∩ Z).card : ℝ) ≤ (μ:ℝ) - 1 := by        rw [hv]        by_cases hyZ : y ∈ Z        · rw [if_pos hyZ]          have hℓμ : (ℓ:ℝ) ≤ (μ:ℝ) := by exact_mod_cast hμℓ          linarith        · rw [if_neg hyZ]; linarith      have kk2 : ((G.neighborFinset y ∩ Z).card : ℝ) ≤ ((μ - 1 : ℕ) : ℝ) := by        rw [Nat.cast_sub hμ1']; simpa using kk      exact Nat.cast_le.mp kk2    have sum_swap : ∀ (A B : Finset V) (g : V → ℝ),        (∑ a ∈ A, ∑ b ∈ G.neighborFinset a ∩ B, g b)          = ∑ b ∈ B, ((G.neighborFinset b ∩ A).card : ℝ) * g b := by      intro A B g      have step1 : (∑ a ∈ A, ∑ b ∈ G.neighborFinset a ∩ B, g b)          = ∑ a ∈ A, ∑ b ∈ B, (if G.Adj a b then g b else 0) := by        apply Finset.sum_congr rfl; intro a _        have hfil : G.neighborFinset a ∩ B = B.filter (G.Adj a) := by          ext w; simp only [Finset.mem_inter, Finset.mem_filter, SimpleGraph.mem_neighborFinset]          exact ⟨fun h => ⟨h.2, h.1⟩, fun h => ⟨h.2, h.1⟩⟩        rw [hfil, Finset.sum_filter]      rw [step1, Finset.sum_comm]      apply Finset.sum_congr rfl; intro b _      rw [← Finset.sum_filter]      have hset : A.filter (fun a => G.Adj a b) = G.neighborFinset b ∩ A := by        ext a; simp only [Finset.mem_filter, Finset.mem_inter, SimpleGraph.mem_neighborFinset]        exact ⟨fun h => ⟨h.2.symm, h.1⟩, fun h => ⟨h.2, h.1.symm⟩⟩      rw [hset, Finset.sum_const, nsmul_eq_mul]    have hac : ∀ u : V, (G.neighborFinset u ∩ G.neighborFinset p0).card        = (G.neighborFinset u ∩ X).card + (G.neighborFinset u ∩ C).card := by      intro u      conv_lhs => rw [hNp_split]      rw [Finset.inter_union_distrib_left]      have hd : Disjoint (G.neighborFinset u ∩ X) (G.neighborFinset u ∩ C) := by        rw [Finset.disjoint_left]; intro a ha hb        exact (Finset.disjoint_left.mp hXC) (Finset.mem_inter.mp ha).2 (Finset.mem_inter.mp hb).2      rw [Finset.card_union_of_disjoint hd]    have hbc : ∀ u : V, (G.neighborFinset u ∩ G.neighborFinset q0).card        = (G.neighborFinset u ∩ Y).card + (G.neighborFinset u ∩ C).card := by      intro u      conv_lhs => rw [hNq_split]      rw [Finset.inter_union_distrib_left]      have hd : Disjoint (G.neighborFinset u ∩ Y) (G.neighborFinset u ∩ C) := by        rw [Finset.disjoint_left]; intro a ha hb        exact (Finset.disjoint_left.mp hYC) (Finset.mem_inter.mp ha).2 (Finset.mem_inter.mp hb).2      rw [Finset.card_union_of_disjoint hd]    have hcoef : ∀ u ∈ Z, ((G.neighborFinset u ∩ X).card : ℝ) - ((G.neighborFinset u ∩ Y).card : ℝ)        = ((ℓ:ℝ) - μ) * (if u ∈ X then 1 else 0) + ((μ:ℝ) - ℓ) * (if u ∈ Y then 1 else 0) := by      intro u hu      have hu0 : u ∈ G.neighborFinset z \ ({p0, q0} : Finset V) := hZdef ▸ hu      obtain ⟨huNz, humem⟩ := Finset.mem_sdiff.mp hu0      have huz : G.Adj u z := ((G.mem_neighborFinset z u).mp huNz).symm      have hune_p : u ≠ p0 := fun h => humem (by simp [h])      have hune_q : u ≠ q0 := fun h => humem (by simp [h])      have hcnp : ((G.neighborFinset u ∩ G.neighborFinset p0).card : ℝ)          = ((G.neighborFinset u ∩ X).card : ℝ) + ((G.neighborFinset u ∩ C).card : ℝ) := by        rw [hac u]; push_cast; ring      have hcnq : ((G.neighborFinset u ∩ G.neighborFinset q0).card : ℝ)          = ((G.neighborFinset u ∩ Y).card : ℝ) + ((G.neighborFinset u ∩ C).card : ℝ) := by        rw [hbc u]; push_cast; ring      have hdiff : ((G.neighborFinset u ∩ X).card : ℝ) - ((G.neighborFinset u ∩ Y).card : ℝ)          = ((G.neighborFinset u ∩ G.neighborFinset p0).card : ℝ)            - ((G.neighborFinset u ∩ G.neighborFinset q0).card : ℝ) := by        rw [hcnp, hcnq]; ring      have hcp : ((G.neighborFinset u ∩ G.neighborFinset p0).card : ℝ)          = if G.Adj u p0 then (ℓ:ℝ) else (μ:ℝ) := by        by_cases hadj : G.Adj u p0        · rw [if_pos hadj, hcn_adj u p0 hadj]        · rw [if_neg hadj, hcn_dist u p0 (dist2 u z p0 huz hzp hadj hune_p)]      have hcq : ((G.neighborFinset u ∩ G.neighborFinset q0).card : ℝ)          = if G.Adj u q0 then (ℓ:ℝ) else (μ:ℝ) := by        by_cases hadj : G.Adj u q0        · rw [if_pos hadj, hcn_adj u q0 hadj]        · rw [if_neg hadj, hcn_dist u q0 (dist2 u z q0 huz hzq hadj hune_q)]      rw [hdiff, hcp, hcq]      by_cases hp : G.Adj u p0      · by_cases hq : G.Adj u q0        · have e1 : ¬ (u ∈ X) := fun h => ((hXmem u).mp h).2 hq          have e2 : ¬ (u ∈ Y) := fun h => ((hYmem u).mp h).2 hp          simp only [if_pos hp, if_pos hq, if_neg e1, if_neg e2]; ring        · have e1 : u ∈ X := (hXmem u).mpr ⟨hp, hq⟩          have e2 : ¬ (u ∈ Y) := fun h => ((hYmem u).mp h).2 hp          simp only [if_pos hp, if_neg hq, if_pos e1, if_neg e2]; ring      · by_cases hq : G.Adj u q0        · have e1 : ¬ (u ∈ X) := fun h => hp ((hXmem u).mp h).1          have e2 : u ∈ Y := (hYmem u).mpr ⟨hq, hp⟩          simp only [if_neg hp, if_pos hq, if_neg e1, if_pos e2]; ring        · have e1 : ¬ (u ∈ X) := fun h => hp ((hXmem u).mp h).1          have e2 : ¬ (u ∈ Y) := fun h => hq ((hYmem u).mp h).1          simp only [if_neg hp, if_neg hq, if_neg e1, if_neg e2]; ring    have hterm : ∀ u ∈ Z, ((G.neighborFinset u ∩ X).card : ℝ) * f u        - ((G.neighborFinset u ∩ Y).card : ℝ) * f u        = ((ℓ:ℝ) - μ) * (if u ∈ X then f u else 0) + ((μ:ℝ) - ℓ) * (if u ∈ Y then f u else 0) := by      intro u hu      have hc := hcoef u hu      have hst : ((G.neighborFinset u ∩ X).card : ℝ) * f u          - ((G.neighborFinset u ∩ Y).card : ℝ) * f u          = (((G.neighborFinset u ∩ X).card : ℝ) - ((G.neighborFinset u ∩ Y).card : ℝ)) * f u := by        ring      rw [hst, hc]      by_cases hx : u ∈ X      · by_cases hy : u ∈ Y        · simp only [hx, hy, if_true, if_false]; ring        · simp only [hx, hy, if_true, if_false]; ring      · by_cases hy : u ∈ Y        · simp only [hx, hy, if_true, if_false]; ring        · simp only [hx, hy, if_true, if_false]; ring    have haxp : ∀ x, (((μ:ℝ) - 1) + ((ℓ:ℝ) - μ) * (if x ∈ Z then 1 else 0)) * f x        = ((μ:ℝ) - 1) * f x + ((ℓ:ℝ) - μ) * (if x ∈ Z then f x else 0) := by      intro x; by_cases hxZ : x ∈ Z <;> simp only [hxZ, if_true, if_false] <;> ring    have hA : (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, (f w - f x))        + (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, (f y - f w))        = ((∑ y ∈ Y, f y) - (∑ x ∈ X, f x)) * ((μ:ℝ) - 1) := by      have e1 : (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, (f w - f x))          = (∑ u ∈ Z, ((G.neighborFinset u ∩ X).card : ℝ) * f u)            - (∑ x ∈ X, ((G.neighborFinset x ∩ Z).card : ℝ) * f x) := by        have ha : (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, (f w - f x))            = (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, f w)              - (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, f x) := by          rw [← Finset.sum_sub_distrib]          apply Finset.sum_congr rfl; intro x hx          rw [Finset.sum_sub_distrib]        have hb : (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, f x)            = ∑ x ∈ X, ((G.neighborFinset x ∩ Z).card : ℝ) * f x := by          apply Finset.sum_congr rfl; intro x hx          rw [Finset.sum_const, nsmul_eq_mul]        rw [ha, hb, sum_swap X Z f]      have e2 : (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, (f y - f w))          = (∑ y ∈ Y, ((G.neighborFinset y ∩ Z).card : ℝ) * f y)            - (∑ u ∈ Z, ((G.neighborFinset u ∩ Y).card : ℝ) * f u) := by        have ha : (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, (f y - f w))            = (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, f y)              - (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, f w) := by          rw [← Finset.sum_sub_distrib]          apply Finset.sum_congr rfl; intro y hy          rw [Finset.sum_sub_distrib]        have hb : (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, f y)            = ∑ y ∈ Y, ((G.neighborFinset y ∩ Z).card : ℝ) * f y := by          apply Finset.sum_congr rfl; intro y hy          rw [Finset.sum_const, nsmul_eq_mul]        rw [ha, hb, sum_swap Y Z f]      have e3 : (∑ u ∈ Z, ((G.neighborFinset u ∩ X).card : ℝ) * f u)          - (∑ u ∈ Z, ((G.neighborFinset u ∩ Y).card : ℝ) * f u)          = ((ℓ:ℝ) - μ) * (∑ x ∈ X ∩ Z, f x) + ((μ:ℝ) - ℓ) * (∑ y ∈ Y ∩ Z, f y) := by        rw [← Finset.sum_sub_distrib, Finset.sum_congr rfl hterm, Finset.sum_add_distrib,          ← Finset.mul_sum, ← Finset.mul_sum, Finset.sum_ite_mem, Finset.sum_ite_mem,          Finset.inter_comm Z X, Finset.inter_comm Z Y]      have e4 : (∑ x ∈ X, ((G.neighborFinset x ∩ Z).card : ℝ) * f x)          = ((μ:ℝ) - 1) * (∑ x ∈ X, f x) + ((ℓ:ℝ) - μ) * (∑ x ∈ X ∩ Z, f x) := by        rw [show (∑ x ∈ X, ((G.neighborFinset x ∩ Z).card : ℝ) * f x)            = ∑ x ∈ X, (((μ:ℝ) - 1) + ((ℓ:ℝ) - μ) * (if x ∈ Z then 1 else 0)) * f x            from Finset.sum_congr rfl (fun x hx => by rw [hXval x hx])]        rw [show (∑ x ∈ X, (((μ:ℝ) - 1) + ((ℓ:ℝ) - μ) * (if x ∈ Z then 1 else 0)) * f x)            = ∑ x ∈ X, (((μ:ℝ) - 1) * f x + ((ℓ:ℝ) - μ) * (if x ∈ Z then f x else 0))            from Finset.sum_congr rfl (fun x _ => haxp x)]        rw [Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.mul_sum, Finset.sum_ite_mem]      have e5 : (∑ y ∈ Y, ((G.neighborFinset y ∩ Z).card : ℝ) * f y)          = ((μ:ℝ) - 1) * (∑ y ∈ Y, f y) + ((ℓ:ℝ) - μ) * (∑ y ∈ Y ∩ Z, f y) := by        rw [show (∑ y ∈ Y, ((G.neighborFinset y ∩ Z).card : ℝ) * f y)            = ∑ y ∈ Y, (((μ:ℝ) - 1) + ((ℓ:ℝ) - μ) * (if y ∈ Z then 1 else 0)) * f y            from Finset.sum_congr rfl (fun y hy => by rw [hYval y hy])]        rw [show (∑ y ∈ Y, (((μ:ℝ) - 1) + ((ℓ:ℝ) - μ) * (if y ∈ Z then 1 else 0)) * f y)            = ∑ y ∈ Y, (((μ:ℝ) - 1) * f y + ((ℓ:ℝ) - μ) * (if y ∈ Z then f y else 0))            from Finset.sum_congr rfl (fun y _ => haxp y)]        rw [Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.mul_sum, Finset.sum_ite_mem]      rw [e1, e2]      linear_combination e3 - e4 + e5    have hbound1 : (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, (f w - f x))        ≤ ((X.card : ℝ)) * ((μ:ℝ) - 1) := by      calc (∑ x ∈ X, ∑ w ∈ G.neighborFinset x ∩ Z, (f w - f x))          ≤ ∑ x ∈ X, ((G.neighborFinset x ∩ Z).card : ℝ) * 1 := by            apply Finset.sum_le_sum; intro x hx            calc (∑ w ∈ G.neighborFinset x ∩ Z, (f w - f x))                ≤ ∑ w ∈ G.neighborFinset x ∩ Z, (1:ℝ) := by                  apply Finset.sum_le_sum; intro w hw                  have hxw : G.Adj x w := (G.mem_neighborFinset x w).mp (Finset.mem_inter.mp hw).1                  have hd : G.dist w x = 1 := by                    rw [SimpleGraph.dist_comm]; exact SimpleGraph.dist_eq_one_iff_adj.mpr hxw                  have hb := hf w x                  rw [hd] at hb; push_cast at hb                  linarith [abs_le.mp hb]              _ = ((G.neighborFinset x ∩ Z).card : ℝ) * 1 := by                  rw [Finset.sum_const, nsmul_eq_mul]        _ ≤ ∑ x ∈ X, ((μ - 1 : ℕ) : ℝ) := by            apply Finset.sum_le_sum; intro x hx            have hb := hXbound x hx            have : ((G.neighborFinset x ∩ Z).card : ℝ) * 1 ≤ ((μ - 1 : ℕ) : ℝ) * 1 := by              apply mul_le_mul_of_nonneg_right _ (by norm_num)              exact_mod_cast hb            simpa using this        _ = ((X.card : ℝ)) * ((μ:ℝ) - 1) := by            rw [Finset.sum_const, nsmul_eq_mul, Nat.cast_sub (by omega : 1 ≤ μ)]            ring    have hbound2 : (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, (f y - f w))        ≤ ((Y.card : ℝ)) * ((μ:ℝ) - 1) := by      calc (∑ y ∈ Y, ∑ w ∈ G.neighborFinset y ∩ Z, (f y - f w))          ≤ ∑ y ∈ Y, ((G.neighborFinset y ∩ Z).card : ℝ) * 1 := by            apply Finset.sum_le_sum; intro y hy            calc (∑ w ∈ G.neighborFinset y ∩ Z, (f y - f w))                ≤ ∑ w ∈ G.neighborFinset y ∩ Z, (1:ℝ) := by                  apply Finset.sum_le_sum; intro w hw                  have hyw : G.Adj y w := (G.mem_neighborFinset y w).mp (Finset.mem_inter.mp hw).1                  have hd : G.dist w y = 1 := by                    rw [SimpleGraph.dist_comm]; exact SimpleGraph.dist_eq_one_iff_adj.mpr hyw                  have hb := hf w y                  rw [hd] at hb; push_cast at hb                  linarith [abs_le.mp hb]              _ = ((G.neighborFinset y ∩ Z).card : ℝ) * 1 := by                  rw [Finset.sum_const, nsmul_eq_mul]        _ ≤ ∑ y ∈ Y, ((μ - 1 : ℕ) : ℝ) := by            apply Finset.sum_le_sum; intro y hy            have hb := hYbound y hy            have : ((G.neighborFinset y ∩ Z).card : ℝ) * 1 ≤ ((μ - 1 : ℕ) : ℝ) * 1 := by              apply mul_le_mul_of_nonneg_right _ (by norm_num)              exact_mod_cast hb            simpa using this        _ = ((Y.card : ℝ)) * ((μ:ℝ) - 1) := by            rw [Finset.sum_const, nsmul_eq_mul, Nat.cast_sub (by omega : 1 ≤ μ)]            ring    have hμpos : (0:ℝ) < (μ:ℝ) - 1 := by      have : (1:ℝ) < (μ:ℝ) := by exact_mod_cast hμ1      linarith    have hXc : ((X.card : ℝ)) = ((k - μ : ℕ) : ℝ) := by      rw [hXdef, Finset.card_sdiff, Finset.inter_comm, interCard,        hG.dist_two_commonNeighbors hpq, hNp]    have hYc : ((Y.card : ℝ)) = ((k - μ : ℕ) : ℝ) := by      rw [hYdef, Finset.card_sdiff, interCard, hG.dist_two_commonNeighbors hpq, hNq]    have hle := add_le_add hbound1 hbound2    rw [hXc, hYc, hA] at hle    have hg : (∑ y ∈ Y, f y) - (∑ x ∈ X, f x)        = (∑ z ∈ G.neighborFinset q0 \ G.neighborFinset p0, f z)          - (∑ z ∈ G.neighborFinset p0 \ G.neighborFinset q0, f z) := by      rw [hYdef, hXdef]    rw [hg] at hle    nlinarith [hμpos, hle]  have h1 := key p q hpq  have h2 := key q p (by rw [SimpleGraph.dist_comm]; exact hpq)  have hsub : (∑ z ∈ G.neighborFinset p, f z) - (∑ z ∈ G.neighborFinset q, f z)      = (∑ z ∈ G.neighborFinset p \ G.neighborFinset q, f z)        - (∑ z ∈ G.neighborFinset q \ G.neighborFinset p, f z) := by    have hs1 := Finset.sum_sdiff (s₁ := G.neighborFinset p ∩ G.neighborFinset q)      (s₂ := G.neighborFinset p) (f := f) Finset.inter_subset_left    have hs2 := Finset.sum_sdiff (s₁ := G.neighborFinset p ∩ G.neighborFinset q)      (s₂ := G.neighborFinset q) (f := f) Finset.inter_subset_right    rw [show G.neighborFinset p \ (G.neighborFinset p ∩ G.neighborFinset q)        = G.neighborFinset p \ G.neighborFinset q from by      ext x; simp only [Finset.mem_sdiff, Finset.mem_inter]; tauto] at hs1    rw [show G.neighborFinset q \ (G.neighborFinset p ∩ G.neighborFinset q)        = G.neighborFinset q \ G.neighborFinset p from by      ext x; simp only [Finset.mem_sdiff, Finset.mem_inter]; tauto] at hs2    linarith  rw [abs_le, hsub]  exact ⟨by linarith, h2⟩
See it in the graphDiscuss this resultChallenge it