AFTD Auto-Formalizing Theoretical Domains

forest_greedy_high_tail_step

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
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.

  1. 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.

    lines 10–18

      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)
  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`).

    lines 19–23

    uses Finset.card_le_card, Finset.mem_filter.mp, Finset.mem_filter.mpr, Finset.mem_univ

      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⟩
  3. |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.

    lines 24–36

    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_comm

      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
  4. |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.

    lines 37–38

    uses forest_greedy_threshold_event_count

      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
  5. |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`).

    lines 39–42

    uses Nat.mul_le_mul, Fintype.card_prod, Fintype.card_bool

      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
  6. 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`.

    lines 43–44

      have hr : (ev.card : ℝ) ≤ (hi.card : ℝ) * (2 * (Fintype.card β : ℝ)) +
          (lo.card : ℝ) * (2 * (ylo.card : ℝ)) := by exact_mod_cast hn
  7. 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`.

    lines 45–47

    uses Fintype.card_pos

      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
  8. |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| / |β|).

    lines 48–56

    uses div_le_div_of_nonneg_right, ne_of_gt

      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]
  9. 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.

    line 57

    uses Fintype.card_prod, Nat.cast_mul, mul_assoc

      simpa [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).

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

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
See it in the graphDiscuss this resultChallenge it