forest_greedy_threshold_event_count
For two finite uniform endpoint populations and a fair tie coin, the number of greedy updates reaching an integer threshold is bounded by the sum of the already-high endpoint count and the product of the near-threshold endpoint count and the eligible partner-coin count.
Statement
theorem forest_greedy_threshold_event_count (α β : Type) [Fintype α] [Fintype β] (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 ≤ ((Finset.univ.filter (fun a => k + 1 ≤ X a)).card * Fintype.card (β × Bool)) + ((Finset.univ.filter (fun a => k - 1 ≤ X a ∧ X a ≤ k)).card * (Finset.univ.filter (fun p : β × Bool => k - 1 < Y p.1 ∨ (k - 1 = Y p.1 ∧ p.2 = true))).card)
- Source
- Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- 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 3
- forest_greedy_envelope_preserved_by_independent_mergeIndependent symmetric finite uniform discrepancy laws of fixed parity that satisfy the envelope still satisfy it after one greedy step…
- forest_greedy_high_tail_stepFor 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…
- forest_greedy_refined_tail_stepFor two independent uniform finite integer laws and a fair tie coin, the probability that a greedy update reaches threshold k is bounded…
The proof, explained
The proof bounds the number of configuration tuples reaching threshold k by showing they are covered by two sets: one where the first coordinate is already at least k+1, and one where it is near k (between k-1 and k) and the partner and coin allow an increase. The cardinality of the event set is then bounded by the union bound and product rule for finite sets.
Auxiliary characterization of reaching the threshold
Unfolding the definition of greedy signed step and case splitting on the conditions.
uses
forest_greedy_signed_stepprivate lemma forest_greedy_threshold_aux (x y k : ℤ) (coin : Bool) (h : k ≤ forest_greedy_signed_step x y coin) : k + 1 ≤ x ∨ (k - 1 ≤ x ∧ x ≤ k ∧ (k - 1 < y ∨ (k - 1 = y ∧ coin = true))) := by unfold forest_greedy_signed_step at h split_ifs at h <;> simp_all <;> omega
Main theorem setup and definitions
Enable classical logic and define the subsets.
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 allow : Finset (β × Bool) := Finset.univ.filter (fun p => k - 1 < Y p.1 ∨ (k - 1 = Y p.1 ∧ p.2 = true)) let events : Finset (α × β × Bool) := Finset.univ.filter (fun p => k ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)
Subset inclusion
Show each event belongs to the union.
uses
forest_greedy_threshold_aux,Finset.mem_union.mpr,Finset.mem_product.mpr,Finset.mem_filter.mpr,Finset.mem_univhave hsub : events ⊆ (hi ×ˢ Finset.univ) ∪ (mid ×ˢ allow) := by intro p hp have hp' : k ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2 := by simpa [events] using hp rcases forest_greedy_threshold_aux (X p.1) (Y p.2.1) k p.2.2 hp' with hhi | ⟨hlo,hupper,hallow⟩ · apply Finset.mem_union.mpr left apply Finset.mem_product.mpr exact ⟨Finset.mem_filter.mpr ⟨Finset.mem_univ _, hhi⟩, Finset.mem_univ _⟩ · apply Finset.mem_union.mpr right apply Finset.mem_product.mpr exact ⟨Finset.mem_filter.mpr ⟨Finset.mem_univ _, ⟨hlo, hupper⟩⟩, Finset.mem_filter.mpr ⟨Finset.mem_univ _, hallow⟩⟩
Cardinality bound
Bound cardinality by union and product formulas.
uses
Finset.card_le_card,Finset.card_union_le,Finset.card_producthave hc := Finset.card_le_card hsub have hu := Finset.card_union_le (hi ×ˢ (Finset.univ : Finset (β × Bool))) (mid ×ˢ allow) calc _ = events.card := rfl _ ≤ ((hi ×ˢ Finset.univ) ∪ (mid ×ˢ allow)).card := hc _ ≤ (hi ×ˢ (Finset.univ : Finset (β × Bool))).card + (mid ×ˢ allow).card := hu _ = _ := by simp [hi, mid, allow, Finset.card_product]
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.
private lemma forest_greedy_threshold_aux (x y k : ℤ) (coin : Bool) (h : k ≤ forest_greedy_signed_step x y coin) : k + 1 ≤ x ∨ (k - 1 ≤ x ∧ x ≤ k ∧ (k - 1 < y ∨ (k - 1 = y ∧ coin = true))) := by unfold forest_greedy_signed_step at h split_ifs at h <;> simp_all <;> omegatheorem forest_greedy_threshold_event_count (α β : Type) [Fintype α] [Fintype β] (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 ≤ ((Finset.univ.filter (fun a => k + 1 ≤ X a)).card * Fintype.card (β × Bool)) + ((Finset.univ.filter (fun a => k - 1 ≤ X a ∧ X a ≤ k)).card * (Finset.univ.filter (fun p : β × Bool => k - 1 < Y p.1 ∨ (k - 1 = Y p.1 ∧ p.2 = true))).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 allow : Finset (β × Bool) := Finset.univ.filter (fun p => k - 1 < Y p.1 ∨ (k - 1 = Y p.1 ∧ p.2 = true)) let events : Finset (α × β × Bool) := Finset.univ.filter (fun p => k ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2) have hsub : events ⊆ (hi ×ˢ Finset.univ) ∪ (mid ×ˢ allow) := by intro p hp have hp' : k ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2 := by simpa [events] using hp rcases forest_greedy_threshold_aux (X p.1) (Y p.2.1) k p.2.2 hp' with hhi | ⟨hlo,hupper,hallow⟩ · apply Finset.mem_union.mpr left apply Finset.mem_product.mpr exact ⟨Finset.mem_filter.mpr ⟨Finset.mem_univ _, hhi⟩, Finset.mem_univ _⟩ · apply Finset.mem_union.mpr right apply Finset.mem_product.mpr exact ⟨Finset.mem_filter.mpr ⟨Finset.mem_univ _, ⟨hlo, hupper⟩⟩, Finset.mem_filter.mpr ⟨Finset.mem_univ _, hallow⟩⟩ have hc := Finset.card_le_card hsub have hu := Finset.card_union_le (hi ×ˢ (Finset.univ : Finset (β × Bool))) (mid ×ˢ allow) calc _ = events.card := rfl _ ≤ ((hi ×ˢ Finset.univ) ∪ (mid ×ˢ allow)).card := hc _ ≤ (hi ×ˢ (Finset.univ : Finset (β × Bool))).card + (mid ×ˢ allow).card := hu _ = _ := by simp [hi, mid, allow, Finset.card_product]