AFTD Auto-Formalizing Theoretical Domains

forest_greedy_envelope_preserved_by_independent_merge

theoremverified

Independent symmetric finite uniform discrepancy laws of fixed parity that satisfy the envelope still satisfy it after one greedy step using an independent fair tie coin.

Statement

theorem forest_greedy_envelope_preserved_by_independent_merge
    (α β : Type) [Fintype α] [Fintype β] [Nonempty α] [Nonempty β]
    (X : α → ℤ) (Y : β → ℤ)
    (hX : forest_greedy_law_enveloped α X)
    (hY : forest_greedy_law_enveloped β Y) :
  forest_greedy_law_enveloped (α × β × Bool)
    (fun p => forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)
Source
Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 14
  • 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_law_envelopedA finite uniform integer law has one fixed parity, is symmetric, and its positive tail at each positive integer is bounded by the forest…
  • forest_carpool_fibonacci_envelope_decayAt every level at least four the proposed tail envelope is at least the next-level envelope plus the square of the previous-level envelope.
  • 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…
  • forest_carpool_tail_envelopeThe proposed one-sided discrepancy tail envelope is 3/8 at level 2 and otherwise two to the negative Fibonacci number of the level.
  • 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.
  • 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…
  • forest_greedy_enveloped_tie_bias_oneAn enveloped fixed-parity law and a fair coin permit an increase from discrepancy 1 with probability at most 3/8.
  • forest_greedy_enveloped_tie_bias_twoAn enveloped fixed-parity law and a fair coin permit an increase from discrepancy 2 with probability at most 1/4.
  • forest_greedy_merge_fixed_parityIf the first endpoint has fixed discrepancy parity, one greedy step has fixed output parity for all partner values and tie coins.
  • forest_greedy_symmetric_mergeThe greedy update of two independent finite uniform symmetric integer laws with a fair tie coin has symmetric value counts.
  • forest_symmetric_one_tailFor any nonempty finite uniform symmetric integer law, the probability of being at least one is at most one half.
  • 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.
Used by 1

The proof, explained

To show that the greedy merge of two independent enveloped discrepancy laws X and Y remains enveloped, the argument verifies fixed parity, distribution symmetry, and tail decay. Parity is preserved because the greedy step always increments or decrements X by 1, and symmetry is preserved via a sign-reversing involution on the product space built from fiberwise bijections for X and Y together with coin inversion. For the tail envelope at threshold k, the base case k = 1 follows immediately from symmetry giving P(Z ≥ 1) ≤ 1/2. For k ≥ 2, the probability is decomposed using threshold event counting into high and middle events for X and an allow condition for Y, yielding a convex combination of tail envelopes U(k+1)(1 - s) + U(k-1)s that is bounded by U(k) using the Fibonacci decay of the envelope.

  1. Precomposing a predicate on a finite type with a permutation preserves the number of satisfying elements.

    The permutation Φ is a bijection from {p | f(Φ(p))} to {p | f(p)} with inverse Φ⁻¹. The lemma Finset.card_nbij' verifies that because Φ and its inverse map the respective filtered sets to each other and are mutual inverses, both sets have equal cardinality.

    lines 5–8

    uses Finset.card_nbij'

      refine Finset.card_nbij' Φ Φ.symm ?_ ?_ (fun p _ => Φ.symm_apply_apply p)
        (fun p _ => Φ.apply_symm_apply p)
      · intro p hp; simpa using hp
      · intro p hp; simpa using hp
  2. If a random variable on a finite type has a symmetric law, there exists a permutation of the domain that negates the variable.

    For each integer c, the symmetry hypothesis implies that the fibers {a | X(a) = c} and {b | -X(b) = c} have the same cardinality. By Fintype.equivOfCardEq, there is an equivalence between these fibers for each c. Gluing these fiberwise bijections together using Equiv.ofFiberEquiv yields an equivalence σ on the domain satisfying X(σ(a)) = -X(a).

    lines 14–22

    uses Fintype.equivOfCardEq, Fintype.card_subtype, Equiv.ofFiberEquiv_map, Equiv.apply_symm_apply

      classical
      have e : ∀ c : ℤ, {a // X a = c} ≃ {b // (fun b => -X b) b = c} := fun c =>
        Fintype.equivOfCardEq (by
          rw [Fintype.card_subtype, Fintype.card_subtype, h c]
          congr 1; ext b; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; omega)
      refine ⟨(Equiv.ofFiberEquiv e).symm, fun a => ?_⟩
      have := Equiv.ofFiberEquiv_map e ((Equiv.ofFiberEquiv e).symm a)
      simp only [Equiv.apply_symm_apply] at this
      linarith
  3. The greedy signed step is an odd function under simultaneous sign reversal of both inputs and boolean negation of the coin. automation

    Unfolding forest_greedy_signed_step shows that reversing the signs of x and y interchanges the comparison cases x < y and y < x, while flipping the coin negates the tie-breaking direction. In every branch, the output value is negated.

    lines 26–27

      unfold forest_greedy_signed_step
      cases c <;> split_ifs <;> first | omega | (exfalso; simp_all)
  4. For any integer j, the set of outcomes where X ≥ j partitions into {j ≤ X ≤ j+1} and {X ≥ j+2}.

    Applying Finset.card_filter_add_card_filter_not to {a | j ≤ X(a)} with the condition X(a) ≤ j + 1 decomposes the set into {j ≤ X ≤ j+1} and its complement within the set, which consists of all a with X(a) ≥ j + 2 since X takes integer values.

    lines 33–43

    uses Finset.card_filter_add_card_filter_not, Finset.filter_filter

      classical
      have := Finset.card_filter_add_card_filter_not
        (s := Finset.univ.filter (fun a => j ≤ X a)) (fun a => X a ≤ j + 1)
      rw [Finset.filter_filter, Finset.filter_filter] at this
      have h4 : (Finset.univ.filter (fun a => j ≤ X a ∧ X a ≤ j + 1)) =
          Finset.univ.filter (fun a => j ≤ X a ∧ X a ≤ j + 1) := rfl
      have h5 : (Finset.univ.filter (fun a => j ≤ X a ∧ ¬ X a ≤ j + 1)) =
          Finset.univ.filter (fun a => j + 2 ≤ X a) := by
        ext a; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; omega
      rw [h5] at this
      exact this
  5. The allow event in β × Bool has cardinality bounded by |{Y ≥ j+1}| + |{Y ≥ j}|.

    Every pair (b, c) with j < Y(b) or (j = Y(b) ∧ c = true) belongs to {Y ≥ j+1} × Bool or {Y = j} × {true}. The union bound and product cardinality bound this by 2|{Y ≥ j+1}| + |{Y = j}|. Partitioning {Y ≥ j} into {Y = j} and {Y ≥ j+1} rewrites this bound as |{Y ≥ j+1}| + |{Y ≥ j}|.

    lines 50–77

    uses Finset.card_le_card, Finset.card_union_le, Finset.card_product, Finset.card_univ, Fintype.card_bool, Finset.card_singleton, Finset.card_filter_add_card_filter_not, Finset.filter_filter

      classical
      have hsub : Finset.univ.filter (fun p : β × Bool => j < Y p.1 ∨ (j = Y p.1 ∧ p.2 = true)) ⊆
          ((Finset.univ.filter (fun b => j + 1 ≤ Y b)) ×ˢ (Finset.univ : Finset Bool)) ∪
          ((Finset.univ.filter (fun b => Y b = j)) ×ˢ ({true} : Finset Bool)) := by
        rintro ⟨b, c⟩ hp
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp
        simp only [Finset.mem_union, Finset.mem_product, Finset.mem_filter, Finset.mem_univ,
          true_and, Finset.mem_singleton, and_true]
        rcases hp with h | ⟨h1, h2⟩
        · left; omega
        · right; exact ⟨h1.symm, h2⟩
      have h1 := Finset.card_le_card hsub
      have h2 := Finset.card_union_le
        ((Finset.univ.filter (fun b => j + 1 ≤ Y b)) ×ˢ (Finset.univ : Finset Bool))
        ((Finset.univ.filter (fun b => Y b = j)) ×ˢ ({true} : Finset Bool))
      rw [Finset.card_product, Finset.card_product, Finset.card_univ, Fintype.card_bool,
        Finset.card_singleton] at h2
      have h3 := Finset.card_filter_add_card_filter_not
        (s := Finset.univ.filter (fun b => j ≤ Y b)) (fun b => Y b = j)
      rw [Finset.filter_filter, Finset.filter_filter] at h3
      have h4 : (Finset.univ.filter (fun b => j ≤ Y b ∧ Y b = j)) =
          Finset.univ.filter (fun b => Y b = j) := by
        ext b; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; omega
      have h5 : (Finset.univ.filter (fun b => j ≤ Y b ∧ ¬ Y b = j)) =
          Finset.univ.filter (fun b => j + 1 ≤ Y b) := by
        ext b; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; omega
      rw [h4, h5] at h3
      omega
  6. The combined state space α × β × Bool has positive cardinality |α| · |β| · 2 and carries a sign-reversing involution Φ.

    Unpacking the enveloped hypotheses on X and Y, the symmetry lemma exists_neg_equiv provides sign-reversing permutations σ on α and τ on β. Combining σ, τ, and boolean negation gives an involution Φ on α × β × Bool that satisfies Z(Φ(p)) = -Z(p) by step_neg. The non-emptiness of α and β guarantees that the total cardinality is strictly positive.

    lines 88–101

    uses ForestGreedyMerge.exists_neg_equiv, ForestGreedyMerge.step_neg, Fintype.card_pos, Fintype.card_prod, Fintype.card_bool

      obtain ⟨⟨pX, hpX⟩, hsX, htX⟩ := hX
      obtain ⟨⟨pY, hpY⟩, hsY, htY⟩ := hY
      set Z : α × β × Bool → ℤ := fun p => forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2 with hZ
      obtain ⟨σ, hσ⟩ := ForestGreedyMerge.exists_neg_equiv α X hsX
      obtain ⟨τ, hτ⟩ := ForestGreedyMerge.exists_neg_equiv β Y hsY
      let Φ : α × β × Bool ≃ α × β × Bool := σ.prodCongr (τ.prodCongr Equiv.boolNot)
      have hΦ : ∀ p, Z (Φ p) = - Z p := by
        rintro ⟨a, b, c⟩
        simp only [hZ, Φ, Equiv.prodCongr_apply, Prod.map, hσ, hτ, Equiv.boolNot_apply]
        exact ForestGreedyMerge.step_neg _ _ _
      have hA : (0 : ℝ) < Fintype.card α := by exact_mod_cast Fintype.card_pos
      have hB : (0 : ℝ) < Fintype.card β := by exact_mod_cast Fintype.card_pos
      have hcard : (Fintype.card (α × β × Bool) : ℝ) = Fintype.card α * (Fintype.card β * 2) := by
        simp [Fintype.card_prod, Fintype.card_bool]
  7. The greedy step variable Z has fixed parity (p_X + 1) mod 2. automation

    In all branches of forest_greedy_signed_step, the outcome is X(p₁) ± 1. Since X has constant parity p_X modulo 2, the result always has parity (p_X + 1) modulo 2.

    lines 102–106

      refine ⟨⟨(pX + 1) % 2, ?_⟩, ?_, ?_⟩
      · intro p
        have h := hpX p.1
        simp only [hZ, forest_greedy_signed_step]
        split_ifs <;> omega
  8. The law of Z is symmetric: for every integer z, |{Z = z}| = |{Z = -z}|.

    Precomposing the event {p | Z(p) = -z} with the bijection Φ yields {p | Z(Φ(p)) = -z} = {p | -Z(p) = -z} = {p | Z(p) = z}. By card_comp_equiv, the two sets have the same cardinality.

    lines 107–109

    uses ForestGreedyMerge.card_comp_equiv

      · intro z
        rw [← ForestGreedyMerge.card_comp_equiv Φ (fun p => Z p = -z)]
        congr 1; ext p; simp only [Finset.mem_filter, Finset.mem_univ, true_and, hΦ]; omega
  9. The tail bound holds for k = 1: P(Z ≥ 1) ≤ U(1) = 1/2.

    When k = 1, symmetry gives |{Z ≥ 1}| = |{Z ≤ -1}| via Φ and card_comp_equiv. Since the events {Z ≥ 1} and {Z ≤ -1} are disjoint subsets of the sample space, 2|{Z ≥ 1}| ≤ |α × β × Bool|. Dividing by the total size shows P(Z ≥ 1) ≤ 1/2 = U(1).

    lines 110–139

    uses Nat.lt_or_ge, ForestGreedyMerge.card_comp_equiv, Finset.card_filter_add_card_filter_not, Finset.card_le_card, Finset.card_univ, Fintype.card_pos, div_le_iff₀

      · intro k hk
        rcases Nat.lt_or_ge k 2 with hk1 | hk2
        · -- k = 1: symmetry
          have hk1' : k = 1 := by omega
          subst hk1'
          simp only [Nat.cast_one]
          have hsym : (Finset.univ.filter (fun p => (1 : ℤ) ≤ Z p)).card =
              (Finset.univ.filter (fun p => Z p ≤ -1)).card := by
            rw [← ForestGreedyMerge.card_comp_equiv Φ (fun p => Z p ≤ -1)]
            congr 1; ext p; simp only [Finset.mem_filter, Finset.mem_univ, true_and, hΦ]; omega
          have hdis := Finset.card_filter_add_card_filter_not (s := Finset.univ)
            (fun p => (1 : ℤ) ≤ Z p)
          have hsub : (Finset.univ.filter (fun p => Z p ≤ -1)) ⊆
              Finset.univ.filter (fun p => ¬ (1 : ℤ) ≤ Z p) := by
            intro p; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; omega
          have h2 := Finset.card_le_card hsub
          rw [Finset.card_univ] at hdis
          have hle : 2 * (Finset.univ.filter (fun p => (1 : ℤ) ≤ Z p)).card ≤
              Fintype.card (α × β × Bool) := by omega
          have hpos : (0 : ℝ) < Fintype.card (α × β × Bool) := by
            exact_mod_cast Fintype.card_pos
          have hU : (forest_carpool_tail_envelope 1) = 1 / 2 := by
            simp [forest_carpool_tail_envelope]
          have hle' : (2 : ℝ) * ((Finset.univ.filter (fun p => (1 : ℤ) ≤ Z p)).card : ℝ) ≤
              Fintype.card (α × β × Bool) := by exact_mod_cast hle
          have hmine : ((Finset.univ.filter (fun p => (1 : ℤ) ≤ Z p)).card : ℝ) /
              (Fintype.card (α × β × Bool) : ℝ) ≤ forest_carpool_tail_envelope 1 := by
            rw [div_le_iff₀ hpos, hU]; linarith
          convert hmine using 4
        · -- k ≥ 2
  10. For k ≥ 2, the threshold event count is bounded in terms of high and middle counts of X and the allow count of Y, and inductive envelope bounds apply.

    Applying forest_greedy_threshold_event_count bounds |{Z ≥ k}| by hi · (2B) + mid · al. Lemma mid_hi_card decomposes lo = |{X ≥ k-1}| into mid + hi, and allow_card bounds al ≤ y_k + y_lo. The envelope assumptions on X and Y supply inductive bounds for hi, lo, y_k, and y_lo at levels k+1, k-1, and k.

    lines 140–159

    uses forest_greedy_threshold_event_count, Fintype.card_prod, Fintype.card_bool, ForestGreedyMerge.mid_hi_card, ForestGreedyMerge.allow_card, Finset.card_le_card, Finset.card_le_univ

          have hcast : (((k - 1 : ℕ)) : ℤ) = (k : ℤ) - 1 := by omega
          have hev := forest_greedy_threshold_event_count α β X Y (k : ℤ)
          rw [Fintype.card_prod, Fintype.card_bool] at hev
          have hmh := ForestGreedyMerge.mid_hi_card α X ((k : ℤ) - 1)
          rw [show (k : ℤ) - 1 + 1 = k by ring, show (k : ℤ) - 1 + 2 = k + 1 by ring] at hmh
          have hal := ForestGreedyMerge.allow_card β Y ((k : ℤ) - 1)
          rw [show (k : ℤ) - 1 + 1 = k by ring] at hal
          have hylo : (Finset.univ.filter (fun b => (k : ℤ) ≤ Y b)).card ≤
              (Finset.univ.filter (fun b => (k : ℤ) - 1 ≤ Y b)).card := by
            apply Finset.card_le_card
            intro b; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; omega
          have hal2 := Finset.card_le_univ (Finset.univ.filter (fun p : β × Bool =>
              (k : ℤ) - 1 < Y p.1 ∨ ((k : ℤ) - 1 = Y p.1 ∧ p.2 = true)))
          rw [Fintype.card_prod, Fintype.card_bool] at hal2
          have eXhi := htX (k + 1) (by omega)
          have eXlo := htX (k - 1) (by omega)
          have eYk := htY k (by omega)
          have eYlo := htY (k - 1) (by omega)
          push_cast at eXhi
          simp only [hcast] at eXlo eYlo
  11. The normalized tail probability P(Z ≥ k) is at most h + m · s, where s ≤ y_lo / B.

    Dividing the event count bound by the total size 2AB expresses the tail probability as h + m · s, with normalized fractions h = hi / A, m = mid / A, and s = al / (2B). Since al ≤ y_k + y_lo and y_k ≤ y_lo, we have 2s ≤ (y_k + y_lo)/B ≤ 2 y_lo / B, so s ≤ y_lo / B.

    lines 160–204

    uses div_le_one, add_div, add_comm, div_le_div_of_nonneg_right, div_le_iff₀

          have hgoal' : ((Finset.univ.filter (fun p : α × β × Bool =>
              (k : ℤ) ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)).card : ℝ) /
              ((Fintype.card α : ℝ) * ((Fintype.card β : ℝ) * 2)) ≤ forest_carpool_tail_envelope k := by
            generalize (Finset.univ.filter (fun p : α × β × Bool =>
              (k : ℤ) ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)).card = ev at hev ⊢
            generalize (Finset.univ.filter (fun a => (k : ℤ) + 1 ≤ X a)).card = hi at hev hmh eXhi
            generalize (Finset.univ.filter (fun a => (k : ℤ) - 1 ≤ X a ∧ X a ≤ k)).card = mid at hev hmh
            generalize (Finset.univ.filter (fun a => (k : ℤ) - 1 ≤ X a)).card = lo at hmh eXlo
            generalize (Finset.univ.filter (fun p : β × Bool =>
              (k : ℤ) - 1 < Y p.1 ∨ ((k : ℤ) - 1 = Y p.1 ∧ p.2 = true))).card = al at hev hal hal2
            generalize (Finset.univ.filter (fun b => (k : ℤ) ≤ Y b)).card = yk at hal hylo eYk
            generalize (Finset.univ.filter (fun b => (k : ℤ) - 1 ≤ Y b)).card = ylo at hal hylo eYlo
            generalize (Fintype.card α) = A at hA eXhi eXlo ⊢
            generalize (Fintype.card β) = B at hB eYk eYlo hal2 hev ⊢
            have hev' : (ev : ℝ) ≤ hi * (B * 2) + mid * al := by exact_mod_cast hev
            have hmh' : (mid : ℝ) + hi = lo := by exact_mod_cast hmh
            have hal' : (al : ℝ) ≤ yk + ylo := by exact_mod_cast hal
            have hylo' : (yk : ℝ) ≤ ylo := by exact_mod_cast hylo
            have hal2' : (al : ℝ) ≤ B * 2 := by exact_mod_cast hal2
            have hAr : (0 : ℝ) < A := hA
            have hBr : (0 : ℝ) < B := hB
            set h : ℝ := hi / A with hh
            set m : ℝ := mid / A with hm
            set s : ℝ := al / (2 * B) with hs
            set lq : ℝ := lo / A with hlq
            have hm0 : 0 ≤ m := by positivity
            have hh0 : 0 ≤ h := by positivity
            have hs0 : 0 ≤ s := by positivity
            have hs1 : s ≤ 1 := by
              rw [hs, div_le_one (by positivity)]; linarith
            have hhm : h + m = lq := by
              rw [hh, hm, hlq, ← add_div, add_comm]; congr 1
            have hs2 : 2 * s ≤ yk / B + ylo / B := by
              rw [hs, ← add_div, show 2 * ((al : ℝ) / (2 * B)) = al / B by field_simp]
              exact div_le_div_of_nonneg_right hal' hBr.le
            have hsY : s ≤ ylo / B := by
              have : (yk : ℝ) / B ≤ ylo / B := div_le_div_of_nonneg_right hylo' hBr.le
              linarith
            have hq : (ev : ℝ) / (A * (B * 2)) ≤ h + m * s := by
              rw [div_le_iff₀ (by positivity)]
              have e1 : h * (A * (B * 2)) = hi * (B * 2) := by
                rw [hh]; field_simp
              have e2 : m * s * (A * (B * 2)) = mid * al := by
                rw [hm, hs]; field_simp
              nlinarith [e1, e2]
  12. The expression h + m · s is bounded by the convex combination U(k+1)(1 - s) + U(k-1)s.

    Because m + h = lo / A, we have h + m · s = h(1 - s) + (lo / A)s. The envelope bounds on X give h ≤ U(k+1) and lo / A ≤ U(k-1). Since s and 1 - s are both between 0 and 1, the bound follows by non-negative linear combinations.

    lines 205–210

    uses mul_le_mul_of_nonneg_right, mul_nonneg

            have hmain : h + m * s ≤ forest_carpool_tail_envelope (k + 1) * (1 - s) +
                forest_carpool_tail_envelope (k - 1) * s := by
              have hlqU : lq ≤ forest_carpool_tail_envelope (k - 1) := eXlo
              have hhU : h ≤ forest_carpool_tail_envelope (k + 1) := eXhi
              nlinarith [mul_nonneg hm0 hs0, mul_le_mul_of_nonneg_right hhU (by linarith : 0 ≤ 1 - s),
                mul_le_mul_of_nonneg_right hlqU hs0]
  13. The convex combination is at most U(k), completing the tail envelope bound for k ≥ 2.

    For k = 2 and k = 3, the envelope inequality U(k+1)(1 - s) + U(k-1)s ≤ U(k) is checked directly by numerical evaluation of U(1), U(2), U(3), and U(4). For k ≥ 4, forest_carpool_fibonacci_envelope_decay establishes U(k+1) + U(k-1)² ≤ U(k); since s ≤ y_lo / B ≤ U(k-1), the combination is at most U(k+1) + U(k-1)² ≤ U(k). Linear arithmetic concludes hgoal', and rewriting with the total cardinality completes the proof.

    lines 211–235

    uses Nat.fib_add_two, forest_carpool_fibonacci_envelope_decay, mul_le_mul_of_nonneg_left, mul_nonneg

            have hU : forest_carpool_tail_envelope (k + 1) * (1 - s) +
                forest_carpool_tail_envelope (k - 1) * s ≤ forest_carpool_tail_envelope k := by
              rcases Nat.lt_or_ge k 4 with hk4 | hk4
              · have u1 : forest_carpool_tail_envelope 1 = 1 / 2 := by
                  simp [forest_carpool_tail_envelope]
                have u2 : forest_carpool_tail_envelope 2 = 3 / 8 := by
                  simp [forest_carpool_tail_envelope]
                have u3 : forest_carpool_tail_envelope 3 = 1 / 4 := by
                  simp [forest_carpool_tail_envelope, Nat.fib_add_two]; norm_num
                have u4 : forest_carpool_tail_envelope 4 = 1 / 8 := by
                  simp [forest_carpool_tail_envelope, Nat.fib_add_two]; norm_num
                interval_cases k
                · rw [show (2 : ℕ) + 1 = 3 from rfl, show (2 : ℕ) - 1 = 1 from rfl, u1, u2, u3] at *
                  linarith
                · rw [show (3 : ℕ) + 1 = 4 from rfl, show (3 : ℕ) - 1 = 2 from rfl, u2, u3, u4] at *
                  linarith
              · have hdec := forest_carpool_fibonacci_envelope_decay k hk4
                have hU0 : 0 ≤ forest_carpool_tail_envelope (k + 1) := by
                  unfold forest_carpool_tail_envelope; split_ifs <;> positivity
                have hU1 : 0 ≤ forest_carpool_tail_envelope (k - 1) := by
                  unfold forest_carpool_tail_envelope; split_ifs <;> positivity
                nlinarith [mul_le_mul_of_nonneg_left (hsY.trans eYlo) hU1, mul_nonneg hU0 hs0]
            linarith
          rw [hcard] at *
          convert hgoal' using 4
Finset.card_nbij'
A function with an inverse between two finite sets establishes their equal cardinality.
Fintype.equivOfCardEq
Two finite types with equal cardinality are equivalent (bijective).
Fintype.card_subtype
The cardinality of a subtype equals the number of elements in the universe satisfying the predicate.
Equiv.ofFiberEquiv_map
The equivalence glued from fiber equivalences maps each fiber to its corresponding fiber.
Equiv.apply_symm_apply
Applying an equivalence to the value of its inverse returns the original element.
Finset.card_filter_add_card_filter_not
Partitioning a finset by a predicate and its negation splits its cardinality into the sum of the two parts.
Finset.filter_filter
Filtering a finset successively by two predicates is equivalent to filtering by their conjunction.
Finset.card_le_card
If one finset is a subset of another, its cardinality is less than or equal to the other's.
Finset.card_union_le
The cardinality of a union of two finsets is at most the sum of their cardinalities.
Finset.card_product
The cardinality of the Cartesian product of two finsets is the product of their cardinalities.
Finset.card_univ
The cardinality of Finset.univ on a finite type equals the Fintype cardinality of the type.
Fintype.card_bool
The cardinality of Bool is 2.
Finset.card_singleton
The cardinality of any singleton finset is 1.
ForestGreedyMerge.exists_neg_equiv
A random variable on a finite type with symmetric distribution admits a permutation negating its values.
ForestGreedyMerge.step_neg
The greedy signed step function is odd under negating both inputs and the coin.
Fintype.card_pos
Any non-empty finite type has strictly positive cardinality.
Fintype.card_prod
The cardinality of a product type is the product of the component cardinalities.
ForestGreedyMerge.card_comp_equiv
Precomposing a predicate with an equivalence on a finite type preserves the cardinality of the satisfying set.
Nat.lt_or_ge
For any natural numbers n and m, either n < m or n ≥ m.
div_le_iff₀
Dividing by a positive real number is at most a value if and only if the numerator is at most the product.
forest_greedy_threshold_event_count
Upper bound on the number of pairs achieving threshold k after a greedy step in terms of high and middle events of X and an allow condition on Y.
ForestGreedyMerge.mid_hi_card
The event {X ≥ j} partitions into the middle event {j ≤ X ≤ j+1} and the high event {X ≥ j+2}.
ForestGreedyMerge.allow_card
Upper bound on the size of the allow event in β × Bool by the sum of cardinalities {Y ≥ j+1} and {Y ≥ j}.
Finset.card_le_univ
Any finset in a finite type has cardinality at most the cardinality of the type.
div_le_one
For a positive divisor b, a / b ≤ 1 if and only if a ≤ b.
add_div
The sum of two fractions with a common denominator equals the fraction with the sum of the numerators.
add_comm
Addition in an additive commutative magma is commutative.
div_le_div_of_nonneg_right
Dividing smaller by a nonnegative number preserves inequality.
mul_nonneg
The product of two nonnegative numbers is nonnegative.
mul_le_mul_of_nonneg_right
Multiplying an inequality on the right by a nonnegative number preserves the inequality.
mul_le_mul_of_nonneg_left
Multiplying an inequality on the left by a nonnegative number preserves the inequality.
Nat.fib_add_two
The Fibonacci sequence satisfies fib(n + 2) = fib(n) + fib(n + 1).
forest_carpool_fibonacci_envelope_decay
The tail envelope satisfies U(k + 1) + U(k - 1)^2 ≤ U(k) for all k ≥ 4.

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

namespace ForestGreedyMergetheorem card_comp_equiv {γ : Type} [Fintype γ] (Φ : γ ≃ γ) (f : γ → Prop) [DecidablePred f] :    (Finset.univ.filter (fun p => f (Φ p))).card = (Finset.univ.filter f).card := by  refine Finset.card_nbij' Φ Φ.symm ?_ ?_ (fun p _ => Φ.symm_apply_apply p)    (fun p _ => Φ.apply_symm_apply p)  · intro p hp; simpa using hp  · intro p hp; simpa using hptheorem exists_neg_equiv (α : Type) [Fintype α] (X : α → ℤ)    (h : ∀ z : ℤ, (Finset.univ.filter (fun a => X a = z)).card =      (Finset.univ.filter (fun a => X a = -z)).card) :    ∃ σ : α ≃ α, ∀ a, X (σ a) = - X a := by  classical  have e : ∀ c : ℤ, {a // X a = c} ≃ {b // (fun b => -X b) b = c} := fun c =>    Fintype.equivOfCardEq (by      rw [Fintype.card_subtype, Fintype.card_subtype, h c]      congr 1; ext b; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; omega)  refine ⟨(Equiv.ofFiberEquiv e).symm, fun a => ?_⟩  have := Equiv.ofFiberEquiv_map e ((Equiv.ofFiberEquiv e).symm a)  simp only [Equiv.apply_symm_apply] at this  linariththeorem step_neg (x y : ℤ) (c : Bool) :    forest_greedy_signed_step (-x) (-y) (!c) = - forest_greedy_signed_step x y c := by  unfold forest_greedy_signed_step  cases c <;> split_ifs <;> first | omega | (exfalso; simp_all)theorem mid_hi_card (α : Type) [Fintype α] (X : α → ℤ) (j : ℤ) :    (Finset.univ.filter (fun a => j ≤ X a ∧ X a ≤ j + 1)).card +      (Finset.univ.filter (fun a => j + 2 ≤ X a)).card =    (Finset.univ.filter (fun a => j ≤ X a)).card := by  classical  have := Finset.card_filter_add_card_filter_not    (s := Finset.univ.filter (fun a => j ≤ X a)) (fun a => X a ≤ j + 1)  rw [Finset.filter_filter, Finset.filter_filter] at this  have h4 : (Finset.univ.filter (fun a => j ≤ X a ∧ X a ≤ j + 1)) =      Finset.univ.filter (fun a => j ≤ X a ∧ X a ≤ j + 1) := rfl  have h5 : (Finset.univ.filter (fun a => j ≤ X a ∧ ¬ X a ≤ j + 1)) =      Finset.univ.filter (fun a => j + 2 ≤ X a) := by    ext a; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; omega  rw [h5] at this  exact thistheorem allow_card (β : Type) [Fintype β] (Y : β → ℤ) (j : ℤ) :    (Finset.univ.filter (fun p : β × Bool =>        j < Y p.1 ∨ (j = Y p.1 ∧ p.2 = true))).card ≤      (Finset.univ.filter (fun b => j + 1 ≤ Y b)).card +      (Finset.univ.filter (fun b => j ≤ Y b)).card := by  classical  have hsub : Finset.univ.filter (fun p : β × Bool => j < Y p.1 ∨ (j = Y p.1 ∧ p.2 = true)) ⊆      ((Finset.univ.filter (fun b => j + 1 ≤ Y b)) ×ˢ (Finset.univ : Finset Bool)) ∪      ((Finset.univ.filter (fun b => Y b = j)) ×ˢ ({true} : Finset Bool)) := by    rintro ⟨b, c⟩ hp    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hp    simp only [Finset.mem_union, Finset.mem_product, Finset.mem_filter, Finset.mem_univ,      true_and, Finset.mem_singleton, and_true]    rcases hp with h | ⟨h1, h2⟩    · left; omega    · right; exact ⟨h1.symm, h2⟩  have h1 := Finset.card_le_card hsub  have h2 := Finset.card_union_le    ((Finset.univ.filter (fun b => j + 1 ≤ Y b)) ×ˢ (Finset.univ : Finset Bool))    ((Finset.univ.filter (fun b => Y b = j)) ×ˢ ({true} : Finset Bool))  rw [Finset.card_product, Finset.card_product, Finset.card_univ, Fintype.card_bool,    Finset.card_singleton] at h2  have h3 := Finset.card_filter_add_card_filter_not    (s := Finset.univ.filter (fun b => j ≤ Y b)) (fun b => Y b = j)  rw [Finset.filter_filter, Finset.filter_filter] at h3  have h4 : (Finset.univ.filter (fun b => j ≤ Y b ∧ Y b = j)) =      Finset.univ.filter (fun b => Y b = j) := by    ext b; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; omega  have h5 : (Finset.univ.filter (fun b => j ≤ Y b ∧ ¬ Y b = j)) =      Finset.univ.filter (fun b => j + 1 ≤ Y b) := by    ext b; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; omega  rw [h4, h5] at h3  omegaend ForestGreedyMergetheorem forest_greedy_envelope_preserved_by_independent_merge    (α β : Type) [Fintype α] [Fintype β] [Nonempty α] [Nonempty β]    (X : α → ℤ) (Y : β → ℤ)    (hX : forest_greedy_law_enveloped α X)    (hY : forest_greedy_law_enveloped β Y) :  forest_greedy_law_enveloped (α × β × Bool)    (fun p => forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2) := by  obtain ⟨⟨pX, hpX⟩, hsX, htX⟩ := hX  obtain ⟨⟨pY, hpY⟩, hsY, htY⟩ := hY  set Z : α × β × Bool → ℤ := fun p => forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2 with hZ  obtain ⟨σ, hσ⟩ := ForestGreedyMerge.exists_neg_equiv α X hsX  obtain ⟨τ, hτ⟩ := ForestGreedyMerge.exists_neg_equiv β Y hsY  let Φ : α × β × Bool ≃ α × β × Bool := σ.prodCongr (τ.prodCongr Equiv.boolNot)  have hΦ : ∀ p, Z (Φ p) = - Z p := by    rintro ⟨a, b, c⟩    simp only [hZ, Φ, Equiv.prodCongr_apply, Prod.map, hσ, hτ, Equiv.boolNot_apply]    exact ForestGreedyMerge.step_neg _ _ _  have hA : (0 : ℝ) < Fintype.card α := by exact_mod_cast Fintype.card_pos  have hB : (0 : ℝ) < Fintype.card β := by exact_mod_cast Fintype.card_pos  have hcard : (Fintype.card (α × β × Bool) : ℝ) = Fintype.card α * (Fintype.card β * 2) := by    simp [Fintype.card_prod, Fintype.card_bool]  refine ⟨⟨(pX + 1) % 2, ?_⟩, ?_, ?_⟩  · intro p    have h := hpX p.1    simp only [hZ, forest_greedy_signed_step]    split_ifs <;> omega  · intro z    rw [← ForestGreedyMerge.card_comp_equiv Φ (fun p => Z p = -z)]    congr 1; ext p; simp only [Finset.mem_filter, Finset.mem_univ, true_and, hΦ]; omega  · intro k hk    rcases Nat.lt_or_ge k 2 with hk1 | hk2    · -- k = 1: symmetry      have hk1' : k = 1 := by omega      subst hk1'      simp only [Nat.cast_one]      have hsym : (Finset.univ.filter (fun p => (1 : ℤ) ≤ Z p)).card =          (Finset.univ.filter (fun p => Z p ≤ -1)).card := by        rw [← ForestGreedyMerge.card_comp_equiv Φ (fun p => Z p ≤ -1)]        congr 1; ext p; simp only [Finset.mem_filter, Finset.mem_univ, true_and, hΦ]; omega      have hdis := Finset.card_filter_add_card_filter_not (s := Finset.univ)        (fun p => (1 : ℤ) ≤ Z p)      have hsub : (Finset.univ.filter (fun p => Z p ≤ -1)) ⊆          Finset.univ.filter (fun p => ¬ (1 : ℤ) ≤ Z p) := by        intro p; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; omega      have h2 := Finset.card_le_card hsub      rw [Finset.card_univ] at hdis      have hle : 2 * (Finset.univ.filter (fun p => (1 : ℤ) ≤ Z p)).card ≤          Fintype.card (α × β × Bool) := by omega      have hpos : (0 : ℝ) < Fintype.card (α × β × Bool) := by        exact_mod_cast Fintype.card_pos      have hU : (forest_carpool_tail_envelope 1) = 1 / 2 := by        simp [forest_carpool_tail_envelope]      have hle' : (2 : ℝ) * ((Finset.univ.filter (fun p => (1 : ℤ) ≤ Z p)).card : ℝ) ≤          Fintype.card (α × β × Bool) := by exact_mod_cast hle      have hmine : ((Finset.univ.filter (fun p => (1 : ℤ) ≤ Z p)).card : ℝ) /          (Fintype.card (α × β × Bool) : ℝ) ≤ forest_carpool_tail_envelope 1 := by        rw [div_le_iff₀ hpos, hU]; linarith      convert hmine using 4    · -- k ≥ 2      have hcast : (((k - 1 : ℕ)) : ℤ) = (k : ℤ) - 1 := by omega      have hev := forest_greedy_threshold_event_count α β X Y (k : ℤ)      rw [Fintype.card_prod, Fintype.card_bool] at hev      have hmh := ForestGreedyMerge.mid_hi_card α X ((k : ℤ) - 1)      rw [show (k : ℤ) - 1 + 1 = k by ring, show (k : ℤ) - 1 + 2 = k + 1 by ring] at hmh      have hal := ForestGreedyMerge.allow_card β Y ((k : ℤ) - 1)      rw [show (k : ℤ) - 1 + 1 = k by ring] at hal      have hylo : (Finset.univ.filter (fun b => (k : ℤ) ≤ Y b)).card ≤          (Finset.univ.filter (fun b => (k : ℤ) - 1 ≤ Y b)).card := by        apply Finset.card_le_card        intro b; simp only [Finset.mem_filter, Finset.mem_univ, true_and]; omega      have hal2 := Finset.card_le_univ (Finset.univ.filter (fun p : β × Bool =>          (k : ℤ) - 1 < Y p.1 ∨ ((k : ℤ) - 1 = Y p.1 ∧ p.2 = true)))      rw [Fintype.card_prod, Fintype.card_bool] at hal2      have eXhi := htX (k + 1) (by omega)      have eXlo := htX (k - 1) (by omega)      have eYk := htY k (by omega)      have eYlo := htY (k - 1) (by omega)      push_cast at eXhi      simp only [hcast] at eXlo eYlo      have hgoal' : ((Finset.univ.filter (fun p : α × β × Bool =>          (k : ℤ) ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)).card : ℝ) /          ((Fintype.card α : ℝ) * ((Fintype.card β : ℝ) * 2)) ≤ forest_carpool_tail_envelope k := by        generalize (Finset.univ.filter (fun p : α × β × Bool =>          (k : ℤ) ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)).card = ev at hev ⊢        generalize (Finset.univ.filter (fun a => (k : ℤ) + 1 ≤ X a)).card = hi at hev hmh eXhi        generalize (Finset.univ.filter (fun a => (k : ℤ) - 1 ≤ X a ∧ X a ≤ k)).card = mid at hev hmh        generalize (Finset.univ.filter (fun a => (k : ℤ) - 1 ≤ X a)).card = lo at hmh eXlo        generalize (Finset.univ.filter (fun p : β × Bool =>          (k : ℤ) - 1 < Y p.1 ∨ ((k : ℤ) - 1 = Y p.1 ∧ p.2 = true))).card = al at hev hal hal2        generalize (Finset.univ.filter (fun b => (k : ℤ) ≤ Y b)).card = yk at hal hylo eYk        generalize (Finset.univ.filter (fun b => (k : ℤ) - 1 ≤ Y b)).card = ylo at hal hylo eYlo        generalize (Fintype.card α) = A at hA eXhi eXlo ⊢        generalize (Fintype.card β) = B at hB eYk eYlo hal2 hev ⊢        have hev' : (ev : ℝ) ≤ hi * (B * 2) + mid * al := by exact_mod_cast hev        have hmh' : (mid : ℝ) + hi = lo := by exact_mod_cast hmh        have hal' : (al : ℝ) ≤ yk + ylo := by exact_mod_cast hal        have hylo' : (yk : ℝ) ≤ ylo := by exact_mod_cast hylo        have hal2' : (al : ℝ) ≤ B * 2 := by exact_mod_cast hal2        have hAr : (0 : ℝ) < A := hA        have hBr : (0 : ℝ) < B := hB        set h : ℝ := hi / A with hh        set m : ℝ := mid / A with hm        set s : ℝ := al / (2 * B) with hs        set lq : ℝ := lo / A with hlq        have hm0 : 0 ≤ m := by positivity        have hh0 : 0 ≤ h := by positivity        have hs0 : 0 ≤ s := by positivity        have hs1 : s ≤ 1 := by          rw [hs, div_le_one (by positivity)]; linarith        have hhm : h + m = lq := by          rw [hh, hm, hlq, ← add_div, add_comm]; congr 1        have hs2 : 2 * s ≤ yk / B + ylo / B := by          rw [hs, ← add_div, show 2 * ((al : ℝ) / (2 * B)) = al / B by field_simp]          exact div_le_div_of_nonneg_right hal' hBr.le        have hsY : s ≤ ylo / B := by          have : (yk : ℝ) / B ≤ ylo / B := div_le_div_of_nonneg_right hylo' hBr.le          linarith        have hq : (ev : ℝ) / (A * (B * 2)) ≤ h + m * s := by          rw [div_le_iff₀ (by positivity)]          have e1 : h * (A * (B * 2)) = hi * (B * 2) := by            rw [hh]; field_simp          have e2 : m * s * (A * (B * 2)) = mid * al := by            rw [hm, hs]; field_simp          nlinarith [e1, e2]        have hmain : h + m * s ≤ forest_carpool_tail_envelope (k + 1) * (1 - s) +            forest_carpool_tail_envelope (k - 1) * s := by          have hlqU : lq ≤ forest_carpool_tail_envelope (k - 1) := eXlo          have hhU : h ≤ forest_carpool_tail_envelope (k + 1) := eXhi          nlinarith [mul_nonneg hm0 hs0, mul_le_mul_of_nonneg_right hhU (by linarith : 0 ≤ 1 - s),            mul_le_mul_of_nonneg_right hlqU hs0]        have hU : forest_carpool_tail_envelope (k + 1) * (1 - s) +            forest_carpool_tail_envelope (k - 1) * s ≤ forest_carpool_tail_envelope k := by          rcases Nat.lt_or_ge k 4 with hk4 | hk4          · have u1 : forest_carpool_tail_envelope 1 = 1 / 2 := by              simp [forest_carpool_tail_envelope]            have u2 : forest_carpool_tail_envelope 2 = 3 / 8 := by              simp [forest_carpool_tail_envelope]            have u3 : forest_carpool_tail_envelope 3 = 1 / 4 := by              simp [forest_carpool_tail_envelope, Nat.fib_add_two]; norm_num            have u4 : forest_carpool_tail_envelope 4 = 1 / 8 := by              simp [forest_carpool_tail_envelope, Nat.fib_add_two]; norm_num            interval_cases k            · rw [show (2 : ℕ) + 1 = 3 from rfl, show (2 : ℕ) - 1 = 1 from rfl, u1, u2, u3] at *              linarith            · rw [show (3 : ℕ) + 1 = 4 from rfl, show (3 : ℕ) - 1 = 2 from rfl, u2, u3, u4] at *              linarith          · have hdec := forest_carpool_fibonacci_envelope_decay k hk4            have hU0 : 0 ≤ forest_carpool_tail_envelope (k + 1) := by              unfold forest_carpool_tail_envelope; split_ifs <;> positivity            have hU1 : 0 ≤ forest_carpool_tail_envelope (k - 1) := by              unfold forest_carpool_tail_envelope; split_ifs <;> positivity            nlinarith [mul_le_mul_of_nonneg_left (hsY.trans eYlo) hU1, mul_nonneg hU0 hs0]        linarith      rw [hcard] at *      convert hgoal' using 4
See it in the graphDiscuss this resultChallenge it