AFTD Auto-Formalizing Theoretical Domains

op_258_one_le_tsum_of_bounded

theoremverified

Let n ≥ 2, let a : ℕ+ → ℝ and let c be an a-bounded colouring of the edges of K_n. Then the ENNReal-sum of the a i is at least 1.

Statement

theorem op_258_one_le_tsum_of_bounded (n : ℕ) (hn : 2 ≤ n) (a : ℕ+ → ℝ)
    (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+)
    (hc : op_258_bounded a n c) :
    1 ≤ ∑' i : ℕ+, ENNReal.ofReal (a i)
Source
step towards op_258_triangle_forcing_implies_decay_ramsey
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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_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…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

The proof, explained

The total number of edges of K_n is n.choose 2, which partitions into the monochromatic fibers under the colouring c. Summing the boundedness condition |c⁻¹(i)| ≤ a i * (n.choose 2) over all colors in the image of c yields n.choose 2 ≤ (∑ a i) * (n.choose 2), which simplifies to 1 ≤ ∑ a i since n.choose 2 > 0. Because each color class in the image is nonempty, each relevant a i is non-negative, allowing the inequality to be transferred to ENNReal and bounded above by the full infinite series ∑' i, ofReal (a i).

  1. (n.choose 2 : ℝ) is strictly positive.

    Since n ≥ 2, the binomial coefficient n.choose 2 is strictly positive as a natural number by Nat.choose_pos, and casting it to the real numbers preserves strict positivity.

    lines 6–8

    uses Nat.choose_pos

      have hpos : 0 < (n.choose 2 : ℝ) := by
        have : 0 < n.choose 2 := Nat.choose_pos hn
        exact_mod_cast this
  2. (n.choose 2 : ℝ) ≤ (∑ i ∈ Finset.univ.image c, a i) * (n.choose 2 : ℝ).

    By op_258_card_fiber_sum, the sum of the fiber sizes over all colors in the image of c equals the total number of edges, n.choose 2. Summing the boundedness hypothesis hc over all colors in the image using Finset.sum_le_sum and factoring out n.choose 2 using Finset.sum_mul gives the desired inequality.

    lines 9–16

    uses op_258_card_fiber_sum, Finset.sum_le_sum, Finset.sum_mul

      have hfiber := op_258_card_fiber_sum n c
      have hle : (∑ i ∈ Finset.univ.image c, (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card : ℝ))
          ≤ ∑ i ∈ Finset.univ.image c, (a i * (n.choose 2 : ℝ)) := by
        apply Finset.sum_le_sum
        intro i hi
        exact hc i
      rw [hfiber] at hle
      rw [← Finset.sum_mul] at hle
  3. 1 ≤ ∑ i ∈ Finset.univ.image c, a i.

    Cancelling the strictly positive factor (n.choose 2 : ℝ) from both sides of the inequality via mul_le_mul_iff_of_pos_right leaves 1 ≤ ∑ i ∈ Finset.univ.image c, a i.

    lines 17–20

    uses mul_le_mul_iff_of_pos_right

      have h1 : 1 ≤ ∑ i ∈ Finset.univ.image c, a i := by
        have hmul : 1 * (n.choose 2 : ℝ) ≤ (∑ i ∈ Finset.univ.image c, a i) * (n.choose 2 : ℝ) := by
          simpa using hle
        exact (mul_le_mul_iff_of_pos_right hpos).mp hmul
  4. For every color i in the image of c, 0 ≤ a i.

    Every color i in the image is assigned to at least one edge by Finset.mem_image.mp, so its fiber is nonempty and has cardinality at least 1 by Finset.card_pos.mpr. From 1 ≤ |c⁻¹(i)| ≤ a i * (n.choose 2) and n.choose 2 > 0, linear arithmetic and nonneg_of_mul_nonneg_left imply 0 ≤ a i.

    lines 21–32

    uses Finset.mem_image.mp, Finset.card_pos.mpr, nonneg_of_mul_nonneg_left

      have hnonneg : ∀ i ∈ Finset.univ.image c, 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
  5. 1 ≤ ∑ i ∈ Finset.univ.image c, ENNReal.ofReal (a i).

    Applying ENNReal.ofReal preserves the inequality 1 ≤ ∑ a i by ENNReal.ofReal_le_ofReal and ENNReal.ofReal_one. Because each a i is non-negative on the image of c, ENNReal.ofReal_sum_of_nonneg distributes ofReal across the finite sum.

    lines 33–38

    uses ENNReal.ofReal_one, ENNReal.ofReal_le_ofReal, ENNReal.ofReal_sum_of_nonneg

      have hone_le_ofReal : 1 ≤ ENNReal.ofReal (∑ i ∈ Finset.univ.image c, a i) := by
        rw [← ENNReal.ofReal_one]
        exact ENNReal.ofReal_le_ofReal h1
      have hsum_eq : ENNReal.ofReal (∑ i ∈ Finset.univ.image c, a i) = ∑ i ∈ Finset.univ.image c, ENNReal.ofReal (a i) :=
        ENNReal.ofReal_sum_of_nonneg hnonneg
      rw [hsum_eq] at hone_le_ofReal
  6. 1 ≤ ∑' i : ℕ+, ENNReal.ofReal (a i).

    In ENNReal, the finite partial sum over the image of c is bounded above by the total sum of the infinite series over all colors by ENNReal.sum_le_tsum. Chaining this with the lower bound 1 ≤ ∑ a i finishes the proof.

    line 39

    uses ENNReal.sum_le_tsum

      exact hone_le_ofReal.trans (ENNReal.sum_le_tsum (Finset.univ.image c))
Nat.choose_pos
For natural numbers k ≤ n, the binomial coefficient n.choose k is strictly positive.
op_258_card_fiber_sum
The sum of the sizes of the color classes over all colors in the image of c equals the total number of edges, n.choose 2, of the complete graph K_n.
Finset.sum_le_sum
If f i ≤ g i for every element i in a finite set s, then the sum of f over s is at most the sum of g over s.
Finset.sum_mul
Multiplication by an element distributes from the right over a finite sum: (∑ i ∈ s, f i) * a = ∑ i ∈ s, f i * a.
mul_le_mul_iff_of_pos_right
Multiplying both sides by a strictly positive element preserves and reflects the weak inequality: b * a ≤ c * a ↔ b ≤ c.
Finset.mem_image.mp
If y is in the image of a finite set under f, then there is some element x in the set such that f x = y.
Finset.card_pos.mpr
A nonempty finite set has strictly positive cardinality.
nonneg_of_mul_nonneg_left
If a * b ≥ 0 and b > 0, then a ≥ 0.
ENNReal.ofReal_one
The value of ENNReal.ofReal 1 is 1.
ENNReal.ofReal_le_ofReal
The function ENNReal.ofReal preserves order: p ≤ q implies ofReal p ≤ ofReal q.
ENNReal.ofReal_sum_of_nonneg
The function ENNReal.ofReal distributes over finite sums of non-negative real numbers.
ENNReal.sum_le_tsum
Any finite sum is bounded above by the total sum of the infinite series in ENNReal.

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

/-- Any a-bounded colouring of K_n with n ≥ 2 forces `1 ≤ Σ a`; in particular a profile with `Σ a < 1` admits no a-bounded colouring at all, so its forcing statements are vacuous. This is why the target's hypothesis `1 < Σ a` is the marginal one. -/theorem op_258_one_le_tsum_of_bounded (n : ℕ) (hn : 2 ≤ n) (a : ℕ+ → ℝ)    (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+)    (hc : op_258_bounded a n c) :    1 ≤ ∑' i : ℕ+, ENNReal.ofReal (a i) := by  have hpos : 0 < (n.choose 2 : ℝ) := by    have : 0 < n.choose 2 := Nat.choose_pos hn    exact_mod_cast this  have hfiber := op_258_card_fiber_sum n c  have hle : (∑ i ∈ Finset.univ.image c, (((Finset.univ : Finset (SimpleGraph.completeGraph (Fin n)).edgeSet).filter (fun e => c e = i)).card : ℝ))      ≤ ∑ i ∈ Finset.univ.image c, (a i * (n.choose 2 : ℝ)) := by    apply Finset.sum_le_sum    intro i hi    exact hc i  rw [hfiber] at hle  rw [← Finset.sum_mul] at hle  have h1 : 1 ≤ ∑ i ∈ Finset.univ.image c, a i := by    have hmul : 1 * (n.choose 2 : ℝ) ≤ (∑ i ∈ Finset.univ.image c, a i) * (n.choose 2 : ℝ) := by      simpa using hle    exact (mul_le_mul_iff_of_pos_right hpos).mp hmul  have hnonneg : ∀ i ∈ Finset.univ.image c, 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 hone_le_ofReal : 1 ≤ ENNReal.ofReal (∑ i ∈ Finset.univ.image c, a i) := by    rw [← ENNReal.ofReal_one]    exact ENNReal.ofReal_le_ofReal h1  have hsum_eq : ENNReal.ofReal (∑ i ∈ Finset.univ.image c, a i) = ∑ i ∈ Finset.univ.image c, ENNReal.ofReal (a i) :=    ENNReal.ofReal_sum_of_nonneg hnonneg  rw [hsum_eq] at hone_le_ofReal  exact hone_le_ofReal.trans (ENNReal.sum_le_tsum (Finset.univ.image c))
See it in the graphDiscuss this resultChallenge it