op_258_one_le_tsum_of_bounded
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— 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).
(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.
uses
Nat.choose_poshave hpos : 0 < (n.choose 2 : ℝ) := by have : 0 < n.choose 2 := Nat.choose_pos hn exact_mod_cast this
(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.
uses
op_258_card_fiber_sum,Finset.sum_le_sum,Finset.sum_mulhave 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
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.
uses
mul_le_mul_iff_of_pos_righthave 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
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.
uses
Finset.mem_image.mp,Finset.card_pos.mpr,nonneg_of_mul_nonneg_lefthave 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
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.
uses
ENNReal.ofReal_one,ENNReal.ofReal_le_ofReal,ENNReal.ofReal_sum_of_nonneghave 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
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.
uses
ENNReal.sum_le_tsumexact 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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))