forest_greedy_envelope_preserved_by_independent_merge
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - 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
- forest_carpool_final_one_sided_fibonacci_tailFor any forest arrival sequence and any vertex, the finite uniform probability that its final greedy discrepancy is at least D is bounded…
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.
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.
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
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).
uses
Fintype.equivOfCardEq,Fintype.card_subtype,Equiv.ofFiberEquiv_map,Equiv.apply_symm_applyclassical 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
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.
unfold forest_greedy_signed_step cases c <;> split_ifs <;> first | omega | (exfalso; simp_all)
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.
uses
Finset.card_filter_add_card_filter_not,Finset.filter_filterclassical 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
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}|.
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_filterclassical 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
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.
uses
ForestGreedyMerge.exists_neg_equiv,ForestGreedyMerge.step_neg,Fintype.card_pos,Fintype.card_prod,Fintype.card_boolobtain ⟨⟨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]
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.
refine ⟨⟨(pX + 1) % 2, ?_⟩, ?_, ?_⟩ · intro p have h := hpX p.1 simp only [hZ, forest_greedy_signed_step] split_ifs <;> omega
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.
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
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).
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
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.
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_univhave 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
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.
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]
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.
uses
mul_le_mul_of_nonneg_right,mul_nonneghave 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]
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.
uses
Nat.fib_add_two,forest_carpool_fibonacci_envelope_decay,mul_le_mul_of_nonneg_left,mul_nonneghave 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.
- The base cases k = 2 and k = 3 of the envelope bound are handled by interval exhaustion and numerical calculation, whereas the general case k ≥ 4 relies on the Fibonacci envelope decay inequality.
- Several algebraic bounds in the tail probability reduction rely on non-linear arithmetic automation (nlinarith and linarith).
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.
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