forest_greedy_high_tail_step
For two independent nonempty finite uniform integer laws and a fair tie coin, the updated tail at k is at most the first tail at k+1 plus the product of the two tails at k-1.
Statement
theorem forest_greedy_high_tail_step (α β : Type) [Fintype α] [Fintype β] [Nonempty α] [Nonempty β] (X : α → ℤ) (Y : β → ℤ) (k : ℤ) : (((Finset.univ.filter (fun p : α × β × Bool => k ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)).card : ℝ) / (Fintype.card (α × β × Bool) : ℝ)) ≤ (((Finset.univ.filter (fun a => k + 1 ≤ X a)).card : ℝ) / Fintype.card α) + (((Finset.univ.filter (fun a => k - 1 ≤ X a)).card : ℝ) / Fintype.card α) * (((Finset.univ.filter (fun b => k - 1 ≤ Y b)).card : ℝ) / Fintype.card β)
- Source
- Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- forest_greedy_signed_stepThe new discrepancy of the first endpoint of a greedy edge is x+1 when x<y, x-1 when x>y, and uses the fair coin to choose between these…
- forest_greedy_threshold_event_countFor two finite uniform endpoint populations and a fair tie coin, the number of greedy updates reaching an integer threshold is bounded by…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- forest_greedy_merge_large_levelsTwo independent enveloped laws remain within the Fibonacci tail envelope after a greedy step at every integer level at least four.
The proof, explained
The theorem bounds the tail probability that the greedy step of X towards Y is at least k in terms of the tail probabilities of X and Y. The argument reduces the probability bound to counting favorable outcomes in the finite product space α × β × Bool. Using a threshold counting lemma (`forest_greedy_threshold_event_count`), the event is bounded by outcomes where X ≥ k + 1 (where any choice of Y and coin suffices) plus outcomes where k - 1 ≤ X ≤ k, which require (Y, coin) to lie in an allowed set of size at most 2 * |Y ≥ k - 1|. Dividing the resulting cardinality bound by the total number of outcomes |α| * |β| * 2 completes the proof.
Define the relevant subsets of outcomes for the threshold analysis.
We enable classical logic and define the subsets: `hi` is the set of a ∈ α with X(a) ≥ k + 1; `mid` is the set of a ∈ α with k - 1 ≤ X(a) ≤ k; `lo` is the set of a ∈ α with X(a) ≥ k - 1; `ylo` is the set of b ∈ β with Y(b) ≥ k - 1; `allow` consists of pairs (b, c) ∈ β × Bool where Y(b) > k - 1, or Y(b) = k - 1 with c = true; and `ev` is the event in α × β × Bool where the greedy step is at least k.
classical let hi : Finset α := Finset.univ.filter (fun a => k + 1 ≤ X a) let mid : Finset α := Finset.univ.filter (fun a => k - 1 ≤ X a ∧ X a ≤ k) let lo : Finset α := Finset.univ.filter (fun a => k - 1 ≤ X a) let ylo : Finset β := Finset.univ.filter (fun b => k - 1 ≤ Y b) let allow : Finset (β × Bool) := Finset.univ.filter (fun p => k - 1 < Y p.1 ∨ (k - 1 = Y p.1 ∧ p.2 = true)) let ev : Finset (α × β × Bool) := Finset.univ.filter (fun p => k ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)
|mid| ≤ |lo|
Every element a ∈ α satisfying k - 1 ≤ X(a) ≤ k satisfies k - 1 ≤ X(a), so `mid ⊆ lo`. The claim follows by monotonicity of cardinality (`Finset.card_le_card`).
uses
Finset.card_le_card,Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.mem_univhave hm : mid.card ≤ lo.card := by apply Finset.card_le_card intro a ha have h : k - 1 ≤ X a ∧ X a ≤ k := (Finset.mem_filter.mp ha).2 exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, h.1⟩
|allow| ≤ 2 * |ylo|
For any pair (b, c) ∈ allow, we have Y(b) > k - 1 or Y(b) = k - 1, so in both cases Y(b) ≥ k - 1 and thus b ∈ ylo. Hence `allow ⊆ ylo ×ˢ Finset.univ`. Since |Bool| = 2, the product has cardinality 2 * |ylo|, giving |allow| ≤ 2 * |ylo| by monotonicity of cardinality.
uses
Finset.mem_filter.mp,Finset.mem_product.mpr,Finset.mem_filter.mpr,Finset.mem_univ,Finset.card_le_card,Finset.card_product,Nat.mul_commhave hs : allow.card ≤ 2 * ylo.card := by have hsub : allow ⊆ ylo ×ˢ (Finset.univ : Finset Bool) := by intro p hp have hp' : k - 1 < Y p.1 ∨ (k - 1 = Y p.1 ∧ p.2 = true) := (Finset.mem_filter.mp hp).2 apply Finset.mem_product.mpr constructor · apply Finset.mem_filter.mpr constructor · exact Finset.mem_univ _ · rcases hp' with hp' | ⟨hp', _⟩ <;> omega · exact Finset.mem_univ _ have hc := Finset.card_le_card hsub simpa [Finset.card_product, Nat.mul_comm] using hc
|ev| ≤ |hi| * |β × Bool| + |mid| * |allow|
This is the threshold event count lemma (`forest_greedy_threshold_event_count`): if X(a) ≥ k + 1, the step is at least k regardless of (b, c); if k - 1 ≤ X(a) ≤ k, the step is at least k only if (b, c) ∈ allow; and if X(a) ≤ k - 2, the step cannot reach k.
uses
forest_greedy_threshold_event_counthave hc : ev.card ≤ hi.card * Fintype.card (β × Bool) + mid.card * allow.card := by simpa [ev, hi, mid, allow] using forest_greedy_threshold_event_count α β X Y k
|ev| ≤ |hi| * (2 * |β|) + |lo| * (2 * |ylo|)
Multiplying the bounds |mid| ≤ |lo| and |allow| ≤ 2 * |ylo| gives |mid| * |allow| ≤ |lo| * (2 * |ylo|) via `Nat.mul_le_mul`. Since |β × Bool| = 2 * |β| (by `Fintype.card_prod` and `Fintype.card_bool`), substituting this product bound into the threshold event bound yields the inequality via linear arithmetic (`nlinarith`).
uses
Nat.mul_le_mul,Fintype.card_prod,Fintype.card_boolhave hmul : mid.card * allow.card ≤ lo.card * (2 * ylo.card) := Nat.mul_le_mul hm hs have hn : ev.card ≤ hi.card * (2 * Fintype.card β) + lo.card * (2 * ylo.card) := by simp only [Fintype.card_prod, Fintype.card_bool] at hc nlinarith
The event count inequality holds in the real numbers.
The inequality |ev| ≤ |hi| * (2 * |β|) + |lo| * (2 * |ylo|) is cast from ℕ to ℝ using `exact_mod_cast`.
have hr : (ev.card : ℝ) ≤ (hi.card : ℝ) * (2 * (Fintype.card β : ℝ)) + (lo.card : ℝ) * (2 * (ylo.card : ℝ)) := by exact_mod_cast hn
The cardinalities |α| and |β| and the denominator |α| * |β| * 2 are strictly positive real numbers.
Because α and β are nonempty finite types, their cardinalities are positive (`Fintype.card_pos`), so their casts to ℝ are strictly positive. The product |α| * |β| * 2 is therefore nonnegative (and positive) by `positivity`.
uses
Fintype.card_poshave hp : (0 : ℝ) < Fintype.card α := by exact_mod_cast (Fintype.card_pos (α := α)) have hq : (0 : ℝ) < Fintype.card β := by exact_mod_cast (Fintype.card_pos (α := β)) have hden : (0 : ℝ) ≤ (Fintype.card α : ℝ) * (Fintype.card β : ℝ) * 2 := by positivity
|ev| / (|α| * |β| * 2) ≤ (|hi| / |α|) + (|lo| / |α|) * (|ylo| / |β|)
Dividing both sides of the inequality from Step 6 by the positive denominator |α| * |β| * 2 preserves the inequality (`div_le_div_of_nonneg_right`). Algebraic simplification (`field_simp`), using that |α| ≠ 0 and |β| ≠ 0 from their positivity, rearranges the right-hand side into the sum and product of ratios (|hi| / |α|) + (|lo| / |α|) * (|ylo| / |β|).
uses
div_le_div_of_nonneg_right,ne_of_gthave hreal : (ev.card : ℝ) / ((Fintype.card α : ℝ) * (Fintype.card β : ℝ) * 2) ≤ (hi.card : ℝ) / Fintype.card α + ((lo.card : ℝ) / Fintype.card α) * ((ylo.card : ℝ) / Fintype.card β) := by calc _ ≤ ((hi.card : ℝ) * (2 * (Fintype.card β : ℝ)) + (lo.card : ℝ) * (2 * (ylo.card : ℝ))) / ((Fintype.card α : ℝ) * (Fintype.card β : ℝ) * 2) := div_le_div_of_nonneg_right hr hden _ = _ := by field_simp [ne_of_gt hp, ne_of_gt hq]
The ratio inequality is the theorem statement.
Unfolding the definitions of `ev`, `hi`, `lo`, and `ylo` and rewriting the total cardinality |α × β × Bool| as |α| * |β| * 2 using `Fintype.card_prod` shows that the inequality from Step 8 is exactly the theorem statement.
uses
Fintype.card_prod,Nat.cast_mul,mul_assocsimpa [ev, hi, lo, ylo, Fintype.card_prod, Nat.cast_mul, mul_assoc] using hreal
Finset.card_le_card- If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Finset.mem_product.mpr- An element belongs to a Cartesian product s ×ˢ t if and only if its first component is in s and its second is in t.
Finset.mem_filter.mp- An element x is in Finset.filter p s if and only if x ∈ s and p x holds (forward direction).
Finset.mem_filter.mpr- An element x is in Finset.filter p s if and only if x ∈ s and p x holds (reverse direction).
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
Finset.card_product- The cardinality of the Cartesian product s ×ˢ t equals |s| * |t|.
Nat.mul_comm- Multiplication of natural numbers is commutative: n * m = m * n.
forest_greedy_threshold_event_count- The number of outcomes where the greedy step is at least k is bounded by |hi| * |β × Bool| + |mid| * |allow|.
Nat.mul_le_mul- If n₁ ≤ n₂ and m₁ ≤ m₂ for natural numbers, then n₁ * m₁ ≤ n₂ * m₂.
Fintype.card_prod- The cardinality of the product type α × β is |α| * |β|.
Fintype.card_bool- The cardinality of Bool is 2.
Fintype.card_pos- A nonempty finite type has strictly positive cardinality.
div_le_div_of_nonneg_right- If a ≤ b and c ≥ 0 in an ordered group with zero, then a / c ≤ b / c.
ne_of_gt- If b < a, then a ≠ b.
Nat.cast_mul- The real cast of a product of natural numbers equals the product of their real casts.
mul_assoc- Multiplication is associative: (a * b) * c = a * (b * c).
- The algebraic simplification that separates the fraction into the sum and product of ratios in Step 8 is automated by `field_simp`.
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.
theorem forest_greedy_high_tail_step (α β : Type) [Fintype α] [Fintype β] [Nonempty α] [Nonempty β] (X : α → ℤ) (Y : β → ℤ) (k : ℤ) : (((Finset.univ.filter (fun p : α × β × Bool => k ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)).card : ℝ) / (Fintype.card (α × β × Bool) : ℝ)) ≤ (((Finset.univ.filter (fun a => k + 1 ≤ X a)).card : ℝ) / Fintype.card α) + (((Finset.univ.filter (fun a => k - 1 ≤ X a)).card : ℝ) / Fintype.card α) * (((Finset.univ.filter (fun b => k - 1 ≤ Y b)).card : ℝ) / Fintype.card β) := by classical let hi : Finset α := Finset.univ.filter (fun a => k + 1 ≤ X a) let mid : Finset α := Finset.univ.filter (fun a => k - 1 ≤ X a ∧ X a ≤ k) let lo : Finset α := Finset.univ.filter (fun a => k - 1 ≤ X a) let ylo : Finset β := Finset.univ.filter (fun b => k - 1 ≤ Y b) let allow : Finset (β × Bool) := Finset.univ.filter (fun p => k - 1 < Y p.1 ∨ (k - 1 = Y p.1 ∧ p.2 = true)) let ev : Finset (α × β × Bool) := Finset.univ.filter (fun p => k ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2) have hm : mid.card ≤ lo.card := by apply Finset.card_le_card intro a ha have h : k - 1 ≤ X a ∧ X a ≤ k := (Finset.mem_filter.mp ha).2 exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, h.1⟩ have hs : allow.card ≤ 2 * ylo.card := by have hsub : allow ⊆ ylo ×ˢ (Finset.univ : Finset Bool) := by intro p hp have hp' : k - 1 < Y p.1 ∨ (k - 1 = Y p.1 ∧ p.2 = true) := (Finset.mem_filter.mp hp).2 apply Finset.mem_product.mpr constructor · apply Finset.mem_filter.mpr constructor · exact Finset.mem_univ _ · rcases hp' with hp' | ⟨hp', _⟩ <;> omega · exact Finset.mem_univ _ have hc := Finset.card_le_card hsub simpa [Finset.card_product, Nat.mul_comm] using hc have hc : ev.card ≤ hi.card * Fintype.card (β × Bool) + mid.card * allow.card := by simpa [ev, hi, mid, allow] using forest_greedy_threshold_event_count α β X Y k have hmul : mid.card * allow.card ≤ lo.card * (2 * ylo.card) := Nat.mul_le_mul hm hs have hn : ev.card ≤ hi.card * (2 * Fintype.card β) + lo.card * (2 * ylo.card) := by simp only [Fintype.card_prod, Fintype.card_bool] at hc nlinarith have hr : (ev.card : ℝ) ≤ (hi.card : ℝ) * (2 * (Fintype.card β : ℝ)) + (lo.card : ℝ) * (2 * (ylo.card : ℝ)) := by exact_mod_cast hn have hp : (0 : ℝ) < Fintype.card α := by exact_mod_cast (Fintype.card_pos (α := α)) have hq : (0 : ℝ) < Fintype.card β := by exact_mod_cast (Fintype.card_pos (α := β)) have hden : (0 : ℝ) ≤ (Fintype.card α : ℝ) * (Fintype.card β : ℝ) * 2 := by positivity have hreal : (ev.card : ℝ) / ((Fintype.card α : ℝ) * (Fintype.card β : ℝ) * 2) ≤ (hi.card : ℝ) / Fintype.card α + ((lo.card : ℝ) / Fintype.card α) * ((ylo.card : ℝ) / Fintype.card β) := by calc _ ≤ ((hi.card : ℝ) * (2 * (Fintype.card β : ℝ)) + (lo.card : ℝ) * (2 * (ylo.card : ℝ))) / ((Fintype.card α : ℝ) * (Fintype.card β : ℝ) * 2) := div_le_div_of_nonneg_right hr hden _ = _ := by field_simp [ne_of_gt hp, ne_of_gt hq] simpa [ev, hi, lo, ylo, Fintype.card_prod, Nat.cast_mul, mul_assoc] using hreal