AFTD Auto-Formalizing Theoretical Domains

forest_greedy_threshold_event_count

theoremverified

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

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.

  1. Auxiliary characterization of reaching the threshold

    Unfolding the definition of greedy signed step and case splitting on the conditions.

    lines 1–6

    uses forest_greedy_signed_step

    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 <;> omega
  2. Main theorem setup and definitions

    Enable classical logic and define the subsets.

    lines 16–22

      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)
  3. Subset inclusion

    Show each event belongs to the union.

    lines 23–36

    uses forest_greedy_threshold_aux, Finset.mem_union.mpr, Finset.mem_product.mpr, Finset.mem_filter.mpr, Finset.mem_univ

      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⟩⟩
  4. Cardinality bound

    Bound cardinality by union and product formulas.

    lines 37–43

    uses Finset.card_le_card, Finset.card_union_le, Finset.card_product

      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]

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

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