AFTD Auto-Formalizing Theoretical Domains

op_258_forces_of_capacity_lt_one

theoremverified

If k ≥ 2 and Σ_i min(a_i, 1 - 1/(k-1)) < 1, then every a-bounded colouring of K_n for large n already contains a monochromatic K_k; i.e. a forces a monochromatic K_k.

Statement

theorem op_258_forces_of_capacity_lt_one (a : ℕ+ → ℝ) (k : ℕ) (hk : 2 ≤ k)
    (hcap : (∑' i : ℕ+, ENNReal.ofReal (min (a i) (1 - 1 / ((k : ℝ) - 1)))) < 1) :
    op_258_forces a k
Source
step towards op_258_forces_step
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • op_258_mono_clique_of_fiber_gt_turanIf a single colour class of an edge colouring of K_n has strictly more edges than the Turán bound for K_{r+1}-free graphs (r ≥ 1), then…
  • op_258_card_fiber_sumFor any colouring c of the edges of the complete graph on Fin n, the sum over the colours actually used of the number of edges of that…
  • op_258_forces_twoFor every decay profile a, a forces a monochromatic K_2.
  • op_258_forcesThe decay profile a forces a monochromatic K_k if for all sufficiently large n, every a-bounded colouring of the edges of K_n has a…
  • op_258_boundedA colouring c of the edges of the complete graph K_n is a-bounded if for every colour i the number of edges of colour i is at most a i *…
  • op_258_has_mono_cliqueThe colouring c of the edges of K_n has a monochromatic K_k: there are a k-element vertex set s and a colour i such that every edge inside…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

The proof, explained

The proof proceeds by contradiction. For k = 2 the result is trivial; for k ≥ 3, any k-clique-free colouring of K_n must obey Turán's theorem, which caps the size of every color class at roughly (1 - 1/(k - 1)) choose(n, 2) + n. Since the capped profile sum S is strictly less than 1 by deficit ε = 1 - S > 0, at most two colors can exceed the threshold θ = 1 - 1/(k - 1), contributing at most 2n surplus edges beyond S choose(n, 2). For large n, this linear surplus 2n cannot compensate for the quadratic deficit ε choose(n, 2), showing that no such colouring can exist.

  1. The edge count of the Turán graph T(n, r) is at most (1 - 1/r) n² / 2.

    The expression ((n² - (n % r)²)(r - 1)) / (2r) + choose(n % r, 2) is the exact number of edges of the Turán graph T(n, r). By the Turán graph edge bound SimpleGraph.mul_card_edgeFinset_turanGraph_le, 2r |E(T(n, r))| ≤ (r - 1)n². Dividing by 2r on both sides gives |E(T(n, r))| ≤ ((r - 1) / (2r)) n² = (1 - 1/r) n² / 2.

    lines 3–18

    uses SimpleGraph.card_edgeFinset_turanGraph.symm, SimpleGraph.mul_card_edgeFinset_turanGraph_le, le_div_iff₀

      have h1 : (n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2 =
          (SimpleGraph.turanGraph n r).edgeFinset.card := SimpleGraph.card_edgeFinset_turanGraph.symm
      rw [h1]
      have h2 := SimpleGraph.mul_card_edgeFinset_turanGraph_le (n := n) (r := r)
      have hr_pos : (0 : ℝ) < (r : ℝ) := Nat.cast_pos.mpr hr
      have h2_real : 2 * (r : ℝ) * ((SimpleGraph.turanGraph n r).edgeFinset.card : ℝ) ≤ ((r - 1 : ℕ) : ℝ) * (n ^ 2 : ℝ) := by
        exact_mod_cast h2
      have hr_sub : ((r - 1 : ℕ) : ℝ) = (r : ℝ) - 1 := by push_cast [hr]; rfl
      rw [hr_sub] at h2_real
      have hdiv : ((SimpleGraph.turanGraph n r).edgeFinset.card : ℝ) ≤ ((r : ℝ) - 1) * (n ^ 2 : ℝ) / (2 * (r : ℝ)) := by
        exact (le_div_iff₀ (by positivity)).mpr (by linarith)
      have heq : ((r : ℝ) - 1) * (n ^ 2 : ℝ) / (2 * (r : ℝ)) = (1 - 1 / (r : ℝ)) * (n ^ 2 : ℝ) / 2 := by
        have : (r : ℝ) ≠ 0 := by positivity
        field_simp
      have h_mid : ((SimpleGraph.turanGraph n r).edgeFinset.card : ℝ) ≤ (1 - 1 / (r : ℝ)) * (n ^ 2 : ℝ) / 2 := by
        rwa [← heq]
  2. The edge count of T(n, r) is at most (1 - 1/r) choose(n, 2) + n.

    Using choose(n, 2) = n(n - 1) / 2, the term (1 - 1/r) n² / 2 expands as (1 - 1/r) choose(n, 2) + (1 - 1/r) n / 2. Since r ≥ 1, we have 1 - 1/r ≤ 1, so the remainder (1 - 1/r) n / 2 is at most n / 2 ≤ n. Adding this yields the desired upper bound.

    lines 19–34

    uses Nat.cast_choose_two, div_le_iff₀, div_pos

      have hch : (n.choose 2 : ℝ) = (n : ℝ) * ((n : ℝ) - 1) / 2 := Nat.cast_choose_two ℝ n
      have h_sq : (1 - 1 / (r : ℝ)) * (n ^ 2 : ℝ) / 2 = (1 - 1 / (r : ℝ)) * (n.choose 2 : ℝ) + (1 - 1 / (r : ℝ)) * (n : ℝ) / 2 := by
        rw [hch]
        ring
      rw [h_sq] at h_mid
      have hr_le : (1 : ℝ) / (r : ℝ) ≤ 1 := by
        rw [div_le_iff₀ hr_pos]
        have : (1 : ℝ) ≤ (r : ℝ) := by exact_mod_cast hr
        linarith
      have : (1 - 1 / (r : ℝ)) * (n : ℝ) / 2 ≤ (n : ℝ) := by
        have h_nonneg : (n : ℝ) ≥ 0 := by positivity
        have : 1 - 1 / (r : ℝ) ≤ 1 := by
          have : 0 < (1 : ℝ) / (r : ℝ) := div_pos (by norm_num) hr_pos
          linarith
        nlinarith
      linarith
  3. If k ≥ 3 and |J|(1 - 1/(k - 1)) ≤ 1, then |J| ≤ 2.

    Since k ≥ 3, we have k - 1 ≥ 2, so 1 / (k - 1) ≤ 1/2, which implies 1 - 1/(k - 1) ≥ 1/2. Therefore |J| * (1/2) ≤ |J|(1 - 1/(k - 1)) ≤ 1, which implies |J| ≤ 2.

    lines 39–50

    uses div_le_div_iff₀

      have hk_sub : (2 : ℝ) ≤ (k : ℝ) - 1 := by
        have : (3 : ℝ) ≤ (k : ℝ) := by exact_mod_cast hk
        linarith
      have htheta : (1 / 2 : ℝ) ≤ 1 - 1 / ((k : ℝ) - 1) := by
        have : 1 / ((k : ℝ) - 1) ≤ 1 / 2 := by
          rw [div_le_div_iff₀ (by positivity) (by norm_num)]
          linarith
        linarith
      have : (J_card : ℝ) * (1 / 2) ≤ (J_card : ℝ) * (1 - 1 / ((k : ℝ) - 1)) := by
        have : 0 ≤ (J_card : ℝ) := by positivity
        nlinarith
      linarith
  4. The theorem holds in the base case k = 2.

    We split on whether k = 2 or k ≥ 3. In the case k = 2, every edge is a monochromatic K₂, so op_258_forces_two immediately proves the claim.

    lines 56–57

    uses eq_or_lt_of_le, op_258_forces_two

      rcases eq_or_lt_of_le hk with rfl | hk3
      · exact op_258_forces_two a
  5. For k ≥ 3, the threshold θ = 1 - 1/(k - 1) is at least 1/2, and the deficit ε = 1 - S is positive.

    When k ≥ 3, k - 1 ≥ 2, so θ = 1 - 1/(k - 1) ≥ 1/2 > 0. The capacity hypothesis says that the series S = ∑_i min(a_i, θ) is strictly less than 1 in ENNReal. Thus S is finite and its real value satisfies S.toReal < 1, leaving a positive deficit ε = 1 - S.toReal > 0.

    lines 58–74

    uses div_le_div_iff₀, ne_of_lt, le_top, ENNReal.toReal_lt_toReal

      · set θ : ℝ := 1 - 1 / ((k : ℝ) - 1)
        have hk_sub : (2 : ℝ) ≤ (k : ℝ) - 1 := by
          have : (3 : ℝ) ≤ (k : ℝ) := by exact_mod_cast hk3
          linarith
        have hθ_ge : (1 / 2 : ℝ) ≤ θ := by
          have : 1 / ((k : ℝ) - 1) ≤ 1 / 2 := by
            rw [div_le_div_iff₀ (by positivity) (by norm_num)]
            linarith
          linarith
        have hθ_pos : 0 < θ := by linarith
        set S : ENNReal := ∑' i : ℕ+, ENNReal.ofReal (min (a i) θ)
        have hne : S ≠ ⊤ := ne_of_lt (hcap.trans_le le_top)
        have hS_lt : S.toReal < 1 := by
          have h_lt := (ENNReal.toReal_lt_toReal hne (by norm_num)).mpr hcap
          simpa using h_lt
        set ε : ℝ := 1 - S.toReal
        have hε : 0 < ε := by linarith
  6. Choose n₀ > 4/ε + 5; any counterexample on K_n with n ≥ n₀ has n ≥ 2 and choose(n, 2) > 0.

    We choose n₀ > 4/ε + 5 by Archimedean property. For any n ≥ n₀ and any a-bounded colouring c of K_n, suppose for contradiction that c contains no monochromatic K_k. Since n > 5, we have n ≥ 2, so the edge set of K_n is non-empty with choose(n, 2) > 0.

    lines 75–91

    uses exists_nat_gt, div_pos, Nat.choose_pos

        obtain ⟨n₀, hn₀⟩ := exists_nat_gt (4 / ε + 5)
        use n₀
        intro n hn c hc
        by_contra h_no
        have hn_pos : 0 < (n : ℝ) := by
          have : 0 < 4 / ε + 5 := by positivity
          have : 4 / ε + 5 < (n : ℝ) := hn₀.trans_le (by exact_mod_cast hn)
          linarith
        have hn2 : 2 ≤ n := by
          have : (2 : ℝ) ≤ (n : ℝ) := by
            have : 0 < 4 / ε := div_pos (by norm_num) hε
            have : 4 / ε + 5 < (n : ℝ) := hn₀.trans_le (by exact_mod_cast hn)
            linarith
          exact_mod_cast this
        have hpos : 0 < (n.choose 2 : ℝ) := by
          have : 0 < n.choose 2 := Nat.choose_pos hn2
          exact_mod_cast this
  7. Each color class has size at most θ choose(n, 2) + n.

    Let r = k - 1 ≥ 1. If any color class had more edges than the Turán graph T(n, r), Turán's theorem op_258_mono_clique_of_fiber_gt_turan would produce a monochromatic K_{r+1} = K_k, contradicting the absence of monochromatic K_k. Combining this with the Turán bound lemma op_258_forces_of_capacity_lt_one_turan_bound_le gives an upper bound of θ choose(n, 2) + n for each color class.

    lines 92–113

    uses Nat.cast_sub, op_258_mono_clique_of_fiber_gt_turan, op_258_forces_of_capacity_lt_one_turan_bound_le

        set r := k - 1
        have hr : 1 ≤ r := by omega
        have hr_add : r + 1 = k := by omega
        have hr_cast : (r : ℝ) = (k : ℝ) - 1 := by
          simpa using Nat.cast_sub (R := ℝ) (by omega : 1 ≤ k)
        have h_turan_i : ∀ i : ℕ+, (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card : ℝ)
            ≤ θ * (n.choose 2 : ℝ) + n := by
          intro i
          have h_not_gt : ¬ ((Finset.univ.filter (fun e => c e = i)).card >
              (n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2) := by
            intro h_gt
            have h_mono := op_258_mono_clique_of_fiber_gt_turan n r hr c i h_gt
            rw [hr_add] at h_mono
            exact h_no h_mono
          have h_le_turan : ((Finset.univ.filter (fun e => c e = i)).card : ℝ) ≤
              (((n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2 : ℕ) : ℝ) := by
            have : (Finset.univ.filter (fun e => c e = i)).card ≤
                (n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2 := by omega
            exact_mod_cast this
          have hturan := op_258_forces_of_capacity_lt_one_turan_bound_le n r hr
          rw [hr_cast] at hturan
          exact h_le_turan.trans hturan
  8. The set J of heavy colors (with a_i > θ) satisfies |J| ≤ 2, so |J|n ≤ 2n.

    Let U be the set of colors appearing on the edges of K_n. Every color in U has at least one edge, so a_i ≥ 0, which implies min(a_i, θ) ≥ 0. The sum of min(a_i, θ) over U is at most the total sum S. On the subset J where a_i > θ, min(a_i, θ) = θ, so |J|θ ≤ S.toReal < 1. By the lemma op_258_forces_of_capacity_lt_one_card_le_two, this implies |J| ≤ 2, and therefore |J|n ≤ 2n.

    lines 114–150

    uses nonneg_of_mul_nonneg_left, le_min, le_of_lt, ENNReal.sum_le_tsum, ne_of_lt, le_top, ENNReal.toReal_le_toReal, ENNReal.ofReal_sum_of_nonneg, ENNReal.toReal_ofReal, Finset.sum_nonneg, Finset.filter_subset, Finset.sum_le_sum_of_subset_of_nonneg, min_eq_right, Finset.sum_congr, Finset.sum_const, nsmul_eq_mul, op_258_forces_of_capacity_lt_one_card_le_two

        set U := Finset.univ.image c
        set J := U.filter (fun i => θ < a i)
        have ha_nonneg : ∀ i ∈ U, 0 ≤ a i := by
          intro i hi
          rcases Finset.mem_image.mp hi with ⟨e, -, he⟩
          have hmem : e ∈ (Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e' => c e' = i) := by
            simp [he]
          have hcard : 1 ≤ ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e' => c e' = i)).card :=
            Finset.card_pos.mpr ⟨e, hmem⟩
          have hcard_real : (1 : ℝ) ≤ (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e' => c e' = i)).card : ℝ) := by
            exact_mod_cast hcard
          have hle_i := hc i
          have : 0 < a i * (n.choose 2 : ℝ) := by linarith
          exact nonneg_of_mul_nonneg_left (by linarith) hpos
        have hmin_nonneg : ∀ i ∈ U, 0 ≤ min (a i) θ := by
          intro i hi
          exact le_min (ha_nonneg i hi) (le_of_lt hθ_pos)
        have h1 : ∑ i ∈ U, ENNReal.ofReal (min (a i) θ) ≤ S := ENNReal.sum_le_tsum U
        have hne1 : (∑ i ∈ U, ENNReal.ofReal (min (a i) θ)) ≠ ⊤ := ne_of_lt (h1.trans_lt (hcap.trans_le le_top))
        have h_sum_le := (ENNReal.toReal_le_toReal hne1 hne).mpr h1
        rw [← ENNReal.ofReal_sum_of_nonneg hmin_nonneg] at h_sum_le
        rw [ENNReal.toReal_ofReal (Finset.sum_nonneg hmin_nonneg)] at h_sum_le
        have hJ_sub : J ⊆ U := Finset.filter_subset _ _
        have h_subsum : (∑ i ∈ J, min (a i) θ) ≤ ∑ i ∈ U, min (a i) θ :=
          Finset.sum_le_sum_of_subset_of_nonneg hJ_sub (fun i hi _ => hmin_nonneg i hi)
        have hJ_eq : ∀ i ∈ J, min (a i) θ = θ := by
          intro i hi
          have : θ < a i := (Finset.mem_filter.mp hi).2
          exact min_eq_right (le_of_lt this)
        have hJ_sum : (∑ i ∈ J, min (a i) θ) = (J.card : ℝ) * θ := by
          rw [Finset.sum_congr rfl hJ_eq, Finset.sum_const, nsmul_eq_mul]
        have hJ_le_S : (J.card : ℝ) * θ ≤ S.toReal := by
          linarith
        have hJ_le_two : (J.card : ℝ) ≤ 2 :=
          op_258_forces_of_capacity_lt_one_card_le_two k hk3 J.card (by linarith)
        have hJ_mul_le : (J.card : ℝ) * (n : ℝ) ≤ 2 * (n : ℝ) := by
          nlinarith
  9. The sum of all color class sizes is at most (∑_{i ∈ U} min(a_i, θ)) choose(n, 2) + |J|n.

    We partition the colors in U into J and U \ J. For each color i ∈ J, its size is at most min(a_i, θ) choose(n, 2) + n by the Turán bound. For each color i ∉ J, we have a_i ≤ θ, so min(a_i, θ) = a_i, and by the profile bound its size is at most a_i choose(n, 2) = min(a_i, θ) choose(n, 2). Summing over U gives the inequality.

    lines 151–177

    uses min_eq_left, Finset.sum_filter_add_sum_filter_not, add_mul, Finset.sum_le_sum, Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul, Finset.sum_mul

        set fib := fun i : ℕ+ => (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card : ℝ)
        have hJ_fib : ∀ i ∈ J, fib i ≤ min (a i) θ * (n.choose 2 : ℝ) + n := by
          intro i hi
          rw [hJ_eq i hi]
          exact h_turan_i i
        have hnotJ_fib : ∀ i ∈ U.filter (fun x => ¬ (θ < a x)), fib i ≤ min (a i) θ * (n.choose 2 : ℝ) := by
          intro i hi
          have hnot : ¬ (θ < a i) := (Finset.mem_filter.mp hi).2
          have hle : a i ≤ θ := not_lt.mp hnot
          have heq : min (a i) θ = a i := min_eq_left hle
          rw [heq]
          exact hc i
        have h_fib_sum : ∑ i ∈ U, fib i ≤ (∑ i ∈ U, min (a i) θ) * (n.choose 2 : ℝ) + (J.card : ℝ) * (n : ℝ) := by
          have h1 : ∑ i ∈ U, fib i = (∑ i ∈ J, fib i) + ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), fib i :=
            (Finset.sum_filter_add_sum_filter_not U (fun x => θ < a x) fib).symm
          have h2 : ∑ i ∈ U, min (a i) θ = (∑ i ∈ J, min (a i) θ) + ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), min (a i) θ :=
            (Finset.sum_filter_add_sum_filter_not U (fun x => θ < a x) (fun i => min (a i) θ)).symm
          rw [h1, h2, add_mul]
          have s1 : ∑ i ∈ J, fib i ≤ ∑ i ∈ J, (min (a i) θ * (n.choose 2 : ℝ) + n) :=
            Finset.sum_le_sum hJ_fib
          have s2 : ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), fib i ≤ ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), (min (a i) θ * (n.choose 2 : ℝ)) :=
            Finset.sum_le_sum hnotJ_fib
          rw [Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul] at s1
          rw [← Finset.sum_mul] at s1
          rw [← Finset.sum_mul] at s2
          linarith
        have h_card_fiber : ∑ i ∈ U, fib i = (n.choose 2 : ℝ) := op_258_card_fiber_sum n c
  10. The total edge count choose(n, 2) contradicts the upper bound, proving the theorem.

    The color classes partition the choose(n, 2) edges of K_n by op_258_card_fiber_sum. Combining this with the bounds on the weight sum and |J|n gives choose(n, 2) ≤ S.toReal choose(n, 2) + 2n, which rearranges to ε choose(n, 2) ≤ 2n. Substituting choose(n, 2) = n(n - 1) / 2 and simplifying yields ε(n - 1) ≤ 4. But our choice of n ≥ n₀ > 4/ε + 5 guarantees ε(n - 1) > 4, a contradiction.

    lines 178–198

    uses op_258_card_fiber_sum, Nat.cast_choose_two, div_lt_iff₀

        have h_le_almost : (n.choose 2 : ℝ) ≤ S.toReal * (n.choose 2 : ℝ) + 2 * (n : ℝ) := by
          calc
            (n.choose 2 : ℝ) = ∑ i ∈ U, fib i := h_card_fiber.symm
            _ ≤ (∑ i ∈ U, min (a i) θ) * (n.choose 2 : ℝ) + (J.card : ℝ) * (n : ℝ) := h_fib_sum
            _ ≤ S.toReal * (n.choose 2 : ℝ) + 2 * (n : ℝ) := by
              have : (∑ i ∈ U, min (a i) θ) * (n.choose 2 : ℝ) ≤ S.toReal * (n.choose 2 : ℝ) := by
                nlinarith
              linarith
        have h_le_fin : ε * (n.choose 2 : ℝ) ≤ 2 * (n : ℝ) := by
          linarith
        have hch : (n.choose 2 : ℝ) = (n : ℝ) * ((n : ℝ) - 1) / 2 := Nat.cast_choose_two ℝ n
        rw [hch] at h_le_fin
        have hn_gt : 4 / ε + 5 < (n : ℝ) := hn₀.trans_le (by exact_mod_cast hn)
        have h4 : 4 < ε * ((n : ℝ) - 1) := by
          have h1 : 4 / ε < (n : ℝ) - 1 := by linarith
          have h2 := (div_lt_iff₀ hε).mp h1
          linarith
        have : 2 * (n : ℝ) < ε * ((n : ℝ) * ((n : ℝ) - 1) / 2) := by
          have : 4 * (n : ℝ) < ε * ((n : ℝ) - 1) * (n : ℝ) := by nlinarith
          linarith
        linarith
SimpleGraph.card_edgeFinset_turanGraph.symm
The number of edges in the Turán graph T(n, r) equals ((n² - (n % r)²)(r - 1)) / (2r) + choose(n % r, 2)
SimpleGraph.mul_card_edgeFinset_turanGraph_le
The number of edges in the Turán graph T(n, r) satisfies 2r |E(T(n, r))| ≤ (r - 1)n²
le_div_iff₀
For c > 0, a ≤ b / c is equivalent to a * c ≤ b
Nat.cast_choose_two
The binomial coefficient choose(n, 2) cast to a division ring equals n(n - 1) / 2
div_le_iff₀
For c > 0, b / c ≤ a is equivalent to b ≤ a * c
div_pos
The quotient of two positive numbers is positive
div_le_div_iff₀
For b > 0 and d > 0, a / b ≤ c / d is equivalent to a * d ≤ c * b
eq_or_lt_of_le
If a ≤ b, then either a = b or a < b
op_258_forces_two
Any profile forces a monochromatic K₂
ne_of_lt
A number strictly less than another cannot equal it
le_top
Every element in a type with a top element is at most ⊤
ENNReal.toReal_lt_toReal
For non-infinite ENNReal values, a.toReal < b.toReal if and only if a < b
exists_nat_gt
For any real number, there exists a strictly greater natural number
Nat.choose_pos
If k ≤ n, then choose(n, k) is strictly positive
Nat.cast_sub
Casting n - m to an additive group with one equals n - m when m ≤ n
op_258_mono_clique_of_fiber_gt_turan
If a color class in a graph on n vertices has more edges than the Turán graph T(n, r), it contains a monochromatic K_{r+1}
op_258_forces_of_capacity_lt_one_turan_bound_le
The edge count of T(n, r) is at most (1 - 1/r) choose(n, 2) + n
nonneg_of_mul_nonneg_left
If a * b ≥ 0 and b > 0, then a ≥ 0
le_min
A number is at most min a b if it is at most both a and b
le_of_lt
If a < b then a ≤ b
ENNReal.sum_le_tsum
A finite sum of nonnegative terms is bounded by the infinite series
ENNReal.toReal_le_toReal
For non-infinite ENNReal values, a.toReal ≤ b.toReal if and only if a ≤ b
ENNReal.ofReal_sum_of_nonneg
ENNReal.ofReal distributes over finite sums of nonnegative real numbers
ENNReal.toReal_ofReal
The real value of ENNReal.ofReal r is r when r ≥ 0
Finset.sum_nonneg
A finite sum of nonnegative terms is nonnegative
Finset.filter_subset
Filtering a finset produces a subset
Finset.sum_le_sum_of_subset_of_nonneg
A sum of nonnegative terms over a subset is at most the sum over the superset
min_eq_right
If b ≤ a, then min a b = b
Finset.sum_congr
Sums of equal functions over equal sets are equal
Finset.sum_const
The sum of a constant b over a finset s equals |s| • b
nsmul_eq_mul
Scalar multiplication by a natural n equals multiplication by n cast to the ring
op_258_forces_of_capacity_lt_one_card_le_two
If k ≥ 3 and |J|(1 - 1/(k - 1)) ≤ 1, then |J| ≤ 2
min_eq_left
If a ≤ b, then min a b = a
Finset.sum_filter_add_sum_filter_not
A sum over a finset equals the sum over elements satisfying p plus the sum over elements satisfying ¬p
add_mul
Right distributivity of multiplication over addition
Finset.sum_le_sum
If f x ≤ g x for all x in s, then sum f ≤ sum g
Finset.sum_add_distrib
The sum of f + g over a finset equals the sum of f plus the sum of g
Finset.sum_mul
Factoring a constant out of a finite sum
op_258_card_fiber_sum
The sum of the sizes of the color classes in K_n equals choose(n, 2)
div_lt_iff₀
For c > 0, b / c < a is equivalent to b < a * c

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

lemma op_258_forces_of_capacity_lt_one_turan_bound_le (n r : ℕ) (hr : 1 ≤ r) :    (((n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2 : ℕ) : ℝ) ≤ (1 - 1 / (r : ℝ)) * (n.choose 2 : ℝ) + n := by  have h1 : (n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2 =      (SimpleGraph.turanGraph n r).edgeFinset.card := SimpleGraph.card_edgeFinset_turanGraph.symm  rw [h1]  have h2 := SimpleGraph.mul_card_edgeFinset_turanGraph_le (n := n) (r := r)  have hr_pos : (0 : ℝ) < (r : ℝ) := Nat.cast_pos.mpr hr  have h2_real : 2 * (r : ℝ) * ((SimpleGraph.turanGraph n r).edgeFinset.card : ℝ) ≤ ((r - 1 : ℕ) : ℝ) * (n ^ 2 : ℝ) := by    exact_mod_cast h2  have hr_sub : ((r - 1 : ℕ) : ℝ) = (r : ℝ) - 1 := by push_cast [hr]; rfl  rw [hr_sub] at h2_real  have hdiv : ((SimpleGraph.turanGraph n r).edgeFinset.card : ℝ) ≤ ((r : ℝ) - 1) * (n ^ 2 : ℝ) / (2 * (r : ℝ)) := by    exact (le_div_iff₀ (by positivity)).mpr (by linarith)  have heq : ((r : ℝ) - 1) * (n ^ 2 : ℝ) / (2 * (r : ℝ)) = (1 - 1 / (r : ℝ)) * (n ^ 2 : ℝ) / 2 := by    have : (r : ℝ) ≠ 0 := by positivity    field_simp  have h_mid : ((SimpleGraph.turanGraph n r).edgeFinset.card : ℝ) ≤ (1 - 1 / (r : ℝ)) * (n ^ 2 : ℝ) / 2 := by    rwa [← heq]  have hch : (n.choose 2 : ℝ) = (n : ℝ) * ((n : ℝ) - 1) / 2 := Nat.cast_choose_two ℝ n  have h_sq : (1 - 1 / (r : ℝ)) * (n ^ 2 : ℝ) / 2 = (1 - 1 / (r : ℝ)) * (n.choose 2 : ℝ) + (1 - 1 / (r : ℝ)) * (n : ℝ) / 2 := by    rw [hch]    ring  rw [h_sq] at h_mid  have hr_le : (1 : ℝ) / (r : ℝ) ≤ 1 := by    rw [div_le_iff₀ hr_pos]    have : (1 : ℝ) ≤ (r : ℝ) := by exact_mod_cast hr    linarith  have : (1 - 1 / (r : ℝ)) * (n : ℝ) / 2 ≤ (n : ℝ) := by    have h_nonneg : (n : ℝ) ≥ 0 := by positivity    have : 1 - 1 / (r : ℝ) ≤ 1 := by      have : 0 < (1 : ℝ) / (r : ℝ) := div_pos (by norm_num) hr_pos      linarith    nlinarith  linarithlemma op_258_forces_of_capacity_lt_one_card_le_two (k : ℕ) (hk : 3 ≤ k) (J_card : ℕ)    (hJ : (J_card : ℝ) * (1 - 1 / ((k : ℝ) - 1)) ≤ 1) :    (J_card : ℝ) ≤ 2 := by  have hk_sub : (2 : ℝ) ≤ (k : ℝ) - 1 := by    have : (3 : ℝ) ≤ (k : ℝ) := by exact_mod_cast hk    linarith  have htheta : (1 / 2 : ℝ) ≤ 1 - 1 / ((k : ℝ) - 1) := by    have : 1 / ((k : ℝ) - 1) ≤ 1 / 2 := by      rw [div_le_div_iff₀ (by positivity) (by norm_num)]      linarith    linarith  have : (J_card : ℝ) * (1 / 2) ≤ (J_card : ℝ) * (1 - 1 / ((k : ℝ) - 1)) := by    have : 0 ≤ (J_card : ℝ) := by positivity    nlinarith  linarith/-- Capacity test: if the capped profile sums below 1, the profile forces a monochromatic K_k. -/theorem op_258_forces_of_capacity_lt_one (a : ℕ+ → ℝ) (k : ℕ) (hk : 2 ≤ k)    (hcap : (∑' i : ℕ+, ENNReal.ofReal (min (a i) (1 - 1 / ((k : ℝ) - 1)))) < 1) :    op_258_forces a k := by  rcases eq_or_lt_of_le hk with rfl | hk3  · exact op_258_forces_two a  · set θ : ℝ := 1 - 1 / ((k : ℝ) - 1)    have hk_sub : (2 : ℝ) ≤ (k : ℝ) - 1 := by      have : (3 : ℝ) ≤ (k : ℝ) := by exact_mod_cast hk3      linarith    have hθ_ge : (1 / 2 : ℝ) ≤ θ := by      have : 1 / ((k : ℝ) - 1) ≤ 1 / 2 := by        rw [div_le_div_iff₀ (by positivity) (by norm_num)]        linarith      linarith    have hθ_pos : 0 < θ := by linarith    set S : ENNReal := ∑' i : ℕ+, ENNReal.ofReal (min (a i) θ)    have hne : S ≠ ⊤ := ne_of_lt (hcap.trans_le le_top)    have hS_lt : S.toReal < 1 := by      have h_lt := (ENNReal.toReal_lt_toReal hne (by norm_num)).mpr hcap      simpa using h_lt    set ε : ℝ := 1 - S.toReal    have hε : 0 < ε := by linarith    obtain ⟨n₀, hn₀⟩ := exists_nat_gt (4 / ε + 5)    use n₀    intro n hn c hc    by_contra h_no    have hn_pos : 0 < (n : ℝ) := by      have : 0 < 4 / ε + 5 := by positivity      have : 4 / ε + 5 < (n : ℝ) := hn₀.trans_le (by exact_mod_cast hn)      linarith    have hn2 : 2 ≤ n := by      have : (2 : ℝ) ≤ (n : ℝ) := by        have : 0 < 4 / ε := div_pos (by norm_num) hε        have : 4 / ε + 5 < (n : ℝ) := hn₀.trans_le (by exact_mod_cast hn)        linarith      exact_mod_cast this    have hpos : 0 < (n.choose 2 : ℝ) := by      have : 0 < n.choose 2 := Nat.choose_pos hn2      exact_mod_cast this    set r := k - 1    have hr : 1 ≤ r := by omega    have hr_add : r + 1 = k := by omega    have hr_cast : (r : ℝ) = (k : ℝ) - 1 := by      simpa using Nat.cast_sub (R := ℝ) (by omega : 1 ≤ k)    have h_turan_i : ∀ i : ℕ+, (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card : ℝ)        ≤ θ * (n.choose 2 : ℝ) + n := by      intro i      have h_not_gt : ¬ ((Finset.univ.filter (fun e => c e = i)).card >          (n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2) := by        intro h_gt        have h_mono := op_258_mono_clique_of_fiber_gt_turan n r hr c i h_gt        rw [hr_add] at h_mono        exact h_no h_mono      have h_le_turan : ((Finset.univ.filter (fun e => c e = i)).card : ℝ) ≤          (((n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2 : ℕ) : ℝ) := by        have : (Finset.univ.filter (fun e => c e = i)).card ≤            (n ^ 2 - (n % r) ^ 2) * (r - 1) / (2 * r) + (n % r).choose 2 := by omega        exact_mod_cast this      have hturan := op_258_forces_of_capacity_lt_one_turan_bound_le n r hr      rw [hr_cast] at hturan      exact h_le_turan.trans hturan    set U := Finset.univ.image c    set J := U.filter (fun i => θ < a i)    have ha_nonneg : ∀ i ∈ U, 0 ≤ a i := by      intro i hi      rcases Finset.mem_image.mp hi with ⟨e, -, he⟩      have hmem : e ∈ (Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e' => c e' = i) := by        simp [he]      have hcard : 1 ≤ ((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e' => c e' = i)).card :=        Finset.card_pos.mpr ⟨e, hmem⟩      have hcard_real : (1 : ℝ) ≤ (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e' => c e' = i)).card : ℝ) := by        exact_mod_cast hcard      have hle_i := hc i      have : 0 < a i * (n.choose 2 : ℝ) := by linarith      exact nonneg_of_mul_nonneg_left (by linarith) hpos    have hmin_nonneg : ∀ i ∈ U, 0 ≤ min (a i) θ := by      intro i hi      exact le_min (ha_nonneg i hi) (le_of_lt hθ_pos)    have h1 : ∑ i ∈ U, ENNReal.ofReal (min (a i) θ) ≤ S := ENNReal.sum_le_tsum U    have hne1 : (∑ i ∈ U, ENNReal.ofReal (min (a i) θ)) ≠ ⊤ := ne_of_lt (h1.trans_lt (hcap.trans_le le_top))    have h_sum_le := (ENNReal.toReal_le_toReal hne1 hne).mpr h1    rw [← ENNReal.ofReal_sum_of_nonneg hmin_nonneg] at h_sum_le    rw [ENNReal.toReal_ofReal (Finset.sum_nonneg hmin_nonneg)] at h_sum_le    have hJ_sub : J ⊆ U := Finset.filter_subset _ _    have h_subsum : (∑ i ∈ J, min (a i) θ) ≤ ∑ i ∈ U, min (a i) θ :=      Finset.sum_le_sum_of_subset_of_nonneg hJ_sub (fun i hi _ => hmin_nonneg i hi)    have hJ_eq : ∀ i ∈ J, min (a i) θ = θ := by      intro i hi      have : θ < a i := (Finset.mem_filter.mp hi).2      exact min_eq_right (le_of_lt this)    have hJ_sum : (∑ i ∈ J, min (a i) θ) = (J.card : ℝ) * θ := by      rw [Finset.sum_congr rfl hJ_eq, Finset.sum_const, nsmul_eq_mul]    have hJ_le_S : (J.card : ℝ) * θ ≤ S.toReal := by      linarith    have hJ_le_two : (J.card : ℝ) ≤ 2 :=      op_258_forces_of_capacity_lt_one_card_le_two k hk3 J.card (by linarith)    have hJ_mul_le : (J.card : ℝ) * (n : ℝ) ≤ 2 * (n : ℝ) := by      nlinarith    set fib := fun i : ℕ+ => (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card : ℝ)    have hJ_fib : ∀ i ∈ J, fib i ≤ min (a i) θ * (n.choose 2 : ℝ) + n := by      intro i hi      rw [hJ_eq i hi]      exact h_turan_i i    have hnotJ_fib : ∀ i ∈ U.filter (fun x => ¬ (θ < a x)), fib i ≤ min (a i) θ * (n.choose 2 : ℝ) := by      intro i hi      have hnot : ¬ (θ < a i) := (Finset.mem_filter.mp hi).2      have hle : a i ≤ θ := not_lt.mp hnot      have heq : min (a i) θ = a i := min_eq_left hle      rw [heq]      exact hc i    have h_fib_sum : ∑ i ∈ U, fib i ≤ (∑ i ∈ U, min (a i) θ) * (n.choose 2 : ℝ) + (J.card : ℝ) * (n : ℝ) := by      have h1 : ∑ i ∈ U, fib i = (∑ i ∈ J, fib i) + ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), fib i :=        (Finset.sum_filter_add_sum_filter_not U (fun x => θ < a x) fib).symm      have h2 : ∑ i ∈ U, min (a i) θ = (∑ i ∈ J, min (a i) θ) + ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), min (a i) θ :=        (Finset.sum_filter_add_sum_filter_not U (fun x => θ < a x) (fun i => min (a i) θ)).symm      rw [h1, h2, add_mul]      have s1 : ∑ i ∈ J, fib i ≤ ∑ i ∈ J, (min (a i) θ * (n.choose 2 : ℝ) + n) :=        Finset.sum_le_sum hJ_fib      have s2 : ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), fib i ≤ ∑ i ∈ U.filter (fun x => ¬ (θ < a x)), (min (a i) θ * (n.choose 2 : ℝ)) :=        Finset.sum_le_sum hnotJ_fib      rw [Finset.sum_add_distrib, Finset.sum_const, nsmul_eq_mul] at s1      rw [← Finset.sum_mul] at s1      rw [← Finset.sum_mul] at s2      linarith    have h_card_fiber : ∑ i ∈ U, fib i = (n.choose 2 : ℝ) := op_258_card_fiber_sum n c    have h_le_almost : (n.choose 2 : ℝ) ≤ S.toReal * (n.choose 2 : ℝ) + 2 * (n : ℝ) := by      calc        (n.choose 2 : ℝ) = ∑ i ∈ U, fib i := h_card_fiber.symm        _ ≤ (∑ i ∈ U, min (a i) θ) * (n.choose 2 : ℝ) + (J.card : ℝ) * (n : ℝ) := h_fib_sum        _ ≤ S.toReal * (n.choose 2 : ℝ) + 2 * (n : ℝ) := by          have : (∑ i ∈ U, min (a i) θ) * (n.choose 2 : ℝ) ≤ S.toReal * (n.choose 2 : ℝ) := by            nlinarith          linarith    have h_le_fin : ε * (n.choose 2 : ℝ) ≤ 2 * (n : ℝ) := by      linarith    have hch : (n.choose 2 : ℝ) = (n : ℝ) * ((n : ℝ) - 1) / 2 := Nat.cast_choose_two ℝ n    rw [hch] at h_le_fin    have hn_gt : 4 / ε + 5 < (n : ℝ) := hn₀.trans_le (by exact_mod_cast hn)    have h4 : 4 < ε * ((n : ℝ) - 1) := by      have h1 : 4 / ε < (n : ℝ) - 1 := by linarith      have h2 := (div_lt_iff₀ hε).mp h1      linarith    have : 2 * (n : ℝ) < ε * ((n : ℝ) * ((n : ℝ) - 1) / 2) := by      have : 4 * (n : ℝ) < ε * ((n : ℝ) - 1) * (n : ℝ) := by nlinarith      linarith    linarith
See it in the graphDiscuss this resultChallenge it