AFTD Auto-Formalizing Theoretical Domains

forest_greedy_refined_tail_step

theoremverified

For two independent uniform finite integer laws and a fair tie coin, the probability that a greedy update reaches threshold k is bounded by the first-law tail at k+1 plus the mass between k-1 and k times the chance that the partner-coin pair permits an increase from k-1.

Statement

theorem forest_greedy_refined_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 a => k + 1 ≤ X a)).card : ℝ) / Fintype.card α)) *
  (((Finset.univ.filter (fun p : β × Bool =>
    k - 1 < Y p.1 ∨ (k - 1 = Y p.1 ∧ p.2 = true))).card : ℝ) /
    (Fintype.card (β × Bool) : ℝ))
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

The proof, explained

The probability that a greedy step reaches threshold k is bounded by decomposing the space of the first random variable X into an upper tail (X ≥ k + 1) and a middle interval (k - 1 ≤ X ≤ k). By the combinatorial bound `forest_greedy_threshold_event_count`, any outcome in the upper tail guarantees an update of at least k, whereas outcomes in the middle interval reach k only if the partner variable and coin permit an increase. Expressing the middle interval's probability as the difference of upper tails ℙ(X ≥ k - 1) - ℙ(X ≥ k + 1) and dividing by the total number of outcomes yields the desired inequality.

  1. Introduce notation for the upper tail, middle interval, lower tail, partner-coin condition, and the step event.

    Under classical logic, we define the relevant subsets: `hi` for outcomes where X ≥ k + 1, `mid` for k - 1 ≤ X ≤ k, `lo` for X ≥ k - 1, `allow` for partner pairs (Y, coin) that allow an increase from k - 1, and `ev` for the triples where the greedy step reaches at least k.

    lines 13–20

      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 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. The lower tail `lo` is the union of `hi` and `mid`.

    By unfolding definitions, an element satisfies X ≥ k - 1 if and only if either X ≥ k + 1 or k - 1 ≤ X ≤ k. Integer linear arithmetic (`omega`) confirms this logical equivalence.

    lines 21–24

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union

      have heq : lo = hi ∪ mid := by
        ext a
        simp only [lo, hi, mid, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union]
        omega
  3. The sets `hi` and `mid` are disjoint.

    Using `Finset.disjoint_left.mpr`, we assume an element belongs to both `hi` and `mid`. This would require X ≥ k + 1 and X ≤ k simultaneously, which integer linear arithmetic (`omega`) recognizes as impossible.

    lines 25–30

    uses Finset.disjoint_left.mpr, Finset.mem_filter.mp

      have hd : Disjoint hi mid := by
        apply Finset.disjoint_left.mpr
        intro a ha hb
        have hh : k + 1 ≤ X a := (Finset.mem_filter.mp ha).2
        have hm : k - 1 ≤ X a ∧ X a ≤ k := (Finset.mem_filter.mp hb).2
        omega
  4. The cardinality of `lo` is the sum of the cardinalities of `hi` and `mid`.

    Since `lo` is the disjoint union of `hi` and `mid`, `Finset.card_union_of_disjoint` asserts that |lo| = |hi| + |mid|.

    line 31

    uses Finset.card_union_of_disjoint

      have hpart : lo.card = hi.card + mid.card := by rw [heq, Finset.card_union_of_disjoint hd]
  5. The number of event outcomes |ev| is bounded by |hi| · |β × Bool| + |mid| · |allow|.

    This counting bound is provided by `forest_greedy_threshold_event_count`: outcomes with X ≥ k + 1 always produce an update at least k regardless of the partner pair, while outcomes with k - 1 ≤ X ≤ k only reach k if the partner pair belongs to `allow`.

    lines 32–33

    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
  6. The counting bound, the partition formula, and the sample space sizes are transferred to positive real numbers.

    We cast the counting inequality and the partition identity |lo| = |hi| + |mid| from ℕ to ℝ using `exact_mod_cast`. Because α and β × Bool are nonempty finite types, their sizes are strictly positive real numbers by `Fintype.card_pos`.

    lines 34–39

    uses Fintype.card_pos

      have hr : (ev.card : ℝ) ≤ (hi.card : ℝ) * (Fintype.card (β × Bool) : ℝ) +
          (mid.card : ℝ) * (allow.card : ℝ) := by exact_mod_cast hc
      have hpartR : (lo.card : ℝ) = (hi.card : ℝ) + (mid.card : ℝ) := by exact_mod_cast hpart
      have hp : (0 : ℝ) < Fintype.card α := by exact_mod_cast (Fintype.card_pos (α := α))
      have hq : (0 : ℝ) < Fintype.card (β × Bool) := by
        exact_mod_cast (Fintype.card_pos (α := β × Bool))
  7. Dividing by the total number of outcomes yields the tail bound with normalized probabilities.

    Dividing both sides of the counting bound by |α| · |β × Bool| preserves inequality via `div_le_div_of_nonneg_right`, since the denominator is strictly positive by `mul_pos` and `le_of_lt`. Rewriting |mid| as |lo| - |hi| using |lo| = |hi| + |mid| (`hpartR`) and clearing denominators (`field_simp`, `ring` using `ne_of_gt`) simplifies the right-hand side to the desired sum of probabilities.

    lines 40–49

    uses div_le_div_of_nonneg_right, le_of_lt, mul_pos, ne_of_gt

      have hreal : (ev.card : ℝ) / ((Fintype.card α : ℝ) * Fintype.card (β × Bool)) ≤
          (hi.card : ℝ) / Fintype.card α +
          ((lo.card : ℝ) / Fintype.card α - (hi.card : ℝ) / Fintype.card α) *
            ((allow.card : ℝ) / Fintype.card (β × Bool)) := by
        calc
          _ ≤ ((hi.card : ℝ) * (Fintype.card (β × Bool) : ℝ) +
              (mid.card : ℝ) * (allow.card : ℝ)) /
              ((Fintype.card α : ℝ) * Fintype.card (β × Bool)) :=
            div_le_div_of_nonneg_right hr (le_of_lt (mul_pos hp hq))
          _ = _ := by rw [hpartR]; field_simp [ne_of_gt hp, ne_of_gt hq] <;> ring
  8. The main probability inequality holds.

    We express the product size |α| · |β × Bool| as |α × β × Bool| using `Fintype.card_prod` and `Nat.cast_mul`, which simplifies the normalized counts to the probabilities stated in the theorem.

    line 50

    uses Fintype.card_prod, Nat.cast_mul

      simpa [ev, hi, lo, allow, Fintype.card_prod, Nat.cast_mul] using hreal
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_filter.mp
If an element belongs to a filtered finset, then it belongs to the base set and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
true_and
The proposition True ∧ p is equivalent to p.
Finset.mem_union
An element belongs to the union of two finsets if and only if it belongs to at least one of them.
Finset.disjoint_left.mpr
Two finsets are disjoint if every element of the first does not belong to the second.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finsets is the sum of their cardinalities.
forest_greedy_threshold_event_count
The count of outcomes where the greedy step is at least k is bounded by the upper tail count times all partner pairs plus the middle count times the partner pairs permitting an increase.
Fintype.card_pos
A nonempty finite type has strictly positive cardinality.
div_le_div_of_nonneg_right
Dividing both sides of an inequality by a non-negative quantity preserves the inequality.
le_of_lt
A strict inequality implies the corresponding non-strict inequality.
mul_pos
The product of two strictly positive numbers is strictly positive.
ne_of_gt
If a number is strictly greater than another, they are not equal.
Fintype.card_prod
The cardinality of a Cartesian product of two finite types is the product of their cardinalities.
Nat.cast_mul
The cast of a product of natural numbers into a ring or field equals the product of their casts.

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_refined_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 a => k + 1 ≤ X a)).card : ℝ) / Fintype.card α)) *  (((Finset.univ.filter (fun p : β × Bool =>    k - 1 < Y p.1 ∨ (k - 1 = Y p.1 ∧ p.2 = true))).card : ℝ) /    (Fintype.card (β × Bool) : ℝ)) := 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 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 heq : lo = hi ∪ mid := by    ext a    simp only [lo, hi, mid, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union]    omega  have hd : Disjoint hi mid := by    apply Finset.disjoint_left.mpr    intro a ha hb    have hh : k + 1 ≤ X a := (Finset.mem_filter.mp ha).2    have hm : k - 1 ≤ X a ∧ X a ≤ k := (Finset.mem_filter.mp hb).2    omega  have hpart : lo.card = hi.card + mid.card := by rw [heq, Finset.card_union_of_disjoint hd]  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 hr : (ev.card : ℝ) ≤ (hi.card : ℝ) * (Fintype.card (β × Bool) : ℝ) +      (mid.card : ℝ) * (allow.card : ℝ) := by exact_mod_cast hc  have hpartR : (lo.card : ℝ) = (hi.card : ℝ) + (mid.card : ℝ) := by exact_mod_cast hpart  have hp : (0 : ℝ) < Fintype.card α := by exact_mod_cast (Fintype.card_pos (α := α))  have hq : (0 : ℝ) < Fintype.card (β × Bool) := by    exact_mod_cast (Fintype.card_pos (α := β × Bool))  have hreal : (ev.card : ℝ) / ((Fintype.card α : ℝ) * Fintype.card (β × Bool)) ≤      (hi.card : ℝ) / Fintype.card α +      ((lo.card : ℝ) / Fintype.card α - (hi.card : ℝ) / Fintype.card α) *        ((allow.card : ℝ) / Fintype.card (β × Bool)) := by    calc      _ ≤ ((hi.card : ℝ) * (Fintype.card (β × Bool) : ℝ) +          (mid.card : ℝ) * (allow.card : ℝ)) /          ((Fintype.card α : ℝ) * Fintype.card (β × Bool)) :=        div_le_div_of_nonneg_right hr (le_of_lt (mul_pos hp hq))      _ = _ := by rw [hpartR]; field_simp [ne_of_gt hp, ne_of_gt hq] <;> ring  simpa [ev, hi, lo, allow, Fintype.card_prod, Nat.cast_mul] using hreal
See it in the graphDiscuss this resultChallenge it