forest_greedy_merge_large_levels
Two independent enveloped laws remain within the Fibonacci tail envelope after a greedy step at every integer level at least four.
Statement
theorem forest_greedy_merge_large_levels (α β : Type) [Fintype α] [Fintype β] [Nonempty α] [Nonempty β] (X : α → ℤ) (Y : β → ℤ) (hX : forest_greedy_law_enveloped α X) (hY : forest_greedy_law_enveloped β Y) (D : ℕ) (hD : 4 ≤ D) : (((Finset.univ.filter (fun p : α × β × Bool => (D : ℤ) ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)).card : ℝ) / (Fintype.card (α × β × Bool) : ℝ)) ≤ forest_carpool_tail_envelope D
- Source
- Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_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.
- 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_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.
- Used by 1
- 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…
The proof, explained
To bound the tail probability of the greedy signed step at level D ≥ 4, the argument first applies a high-tail recurrence lemma (forest_greedy_high_tail_step) that bounds the tail probability at D by ℙ(X ≥ D + 1) + ℙ(X ≥ D - 1) * ℙ(Y ≥ D - 1). Because X and Y are enveloped laws, these tails are bounded by the tail envelope at D + 1 and D - 1, bounding their product by the square of the envelope at D - 1. The result then follows from the Fibonacci decay property (forest_carpool_fibonacci_envelope_decay), which ensures that envelope(D + 1) + envelope(D - 1)^2 ≤ envelope(D) for all D ≥ 4.
1 ≤ D and 1 ≤ D - 1
Because D ≥ 4 by assumption, both D and D - 1 are at least 1 by linear integer arithmetic.
have hd1 : 1 ≤ D := by omega have hdm : 1 ≤ D - 1 := by omega
The upper tails of X at level D + 1, and of both X and Y at level D - 1, are bounded by the tail envelope at those levels
By the assumption that X and Y are enveloped laws (hX and hY), their probability of exceeding any integer level k ≥ 1 is at most the tail envelope at k. Specializing this condition to D + 1 for X, and to D - 1 for both X and Y, yields the respective bounds.
have hxp := hX.2.2 (D + 1) (by omega) have hxm := hX.2.2 (D - 1) hdm have hym := hY.2.2 (D - 1) hdm
The tail envelope at level D - 1 is non-negative
Unfolding the definition of the tail envelope, it evaluates to either 3/8 (when D - 1 = 2) or (1/2)^(fib(D - 1)), both of which are strictly positive real numbers.
have he : 0 ≤ forest_carpool_tail_envelope (D - 1) := by unfold forest_carpool_tail_envelope split_ifs <;> positivity
The product of the tails ℙ(X ≥ D - 1) and ℙ(Y ≥ D - 1) is bounded by the square of the envelope at level D - 1
Because probabilities and the envelope value are non-negative, multiplying the two tail bounds for X and Y at level D - 1 preserves the inequality via mul_le_mul.
uses
mul_le_mulhave hproduct : (((Finset.univ.filter (fun a => ((D - 1 : ℕ) : ℤ) ≤ X a)).card : ℝ) / Fintype.card α) * (((Finset.univ.filter (fun b => ((D - 1 : ℕ) : ℤ) ≤ Y b)).card : ℝ) / Fintype.card β) ≤ forest_carpool_tail_envelope (D - 1) * forest_carpool_tail_envelope (D - 1) := mul_le_mul hxm hym (by positivity) he
The probability that the greedy step is at least D is at most ℙ(X ≥ D + 1) + ℙ(X ≥ D - 1) * ℙ(Y ≥ D - 1)
Applying the general greedy step inequality forest_greedy_high_tail_step at integer level D bounds the step's tail by ℙ(X ≥ D + 1) + ℙ(X ≥ D - 1) * ℙ(Y ≥ D - 1), using cast lemmas (Nat.cast_add, Nat.cast_one, Nat.cast_sub) to express the integer offsets D + 1 and D - 1 as casts of natural numbers.
uses
forest_greedy_high_tail_step,Nat.cast_add,Nat.cast_one,Nat.cast_subhave hstep := forest_greedy_high_tail_step α β X Y (D : ℤ) have hstep' : (((Finset.univ.filter (fun p : α × β × Bool => (D : ℤ) ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)).card : ℝ) / (Fintype.card (α × β × Bool) : ℝ)) ≤ (((Finset.univ.filter (fun a => ((D + 1 : ℕ) : ℤ) ≤ X a)).card : ℝ) / Fintype.card α) + (((Finset.univ.filter (fun a => ((D - 1 : ℕ) : ℤ) ≤ X a)).card : ℝ) / Fintype.card α) * (((Finset.univ.filter (fun b => ((D - 1 : ℕ) : ℤ) ≤ Y b)).card : ℝ) / Fintype.card β) := by simpa only [Nat.cast_add, Nat.cast_one, Nat.cast_sub hd1] using hstep
The tail envelope satisfies envelope(D + 1) + envelope(D - 1)^2 ≤ envelope(D)
This is the Fibonacci decay property of the envelope (forest_carpool_fibonacci_envelope_decay), which holds for all levels D ≥ 4.
uses
forest_carpool_fibonacci_envelope_decayhave hdecay := forest_carpool_fibonacci_envelope_decay D hDThe probability that the greedy step is at least D is at most envelope(D)
A transitive chain of inequalities combines the results: the tail probability of the greedy step is bounded by ℙ(X ≥ D + 1) + ℙ(X ≥ D - 1) * ℙ(Y ≥ D - 1), which is bounded by envelope(D + 1) + envelope(D - 1) * envelope(D - 1) using add_le_add, which is in turn bounded by envelope(D) using pow_two and the decay inequality.
uses
add_le_add,pow_twocalc _ ≤ _ := hstep' _ ≤ forest_carpool_tail_envelope (D + 1) + forest_carpool_tail_envelope (D - 1) * forest_carpool_tail_envelope (D - 1) := add_le_add hxp hproduct _ ≤ _ := by simpa [pow_two] using hdecay
mul_le_mul- if a ≤ b and c ≤ d with 0 ≤ c and 0 ≤ b, then a * c ≤ b * d
forest_greedy_high_tail_step- the probability that the greedy signed step between independent laws X and Y is at least k is at most ℙ(X ≥ k + 1) + ℙ(X ≥ k - 1) * ℙ(Y ≥ k - 1)
Nat.cast_add- the cast of a sum of natural numbers equals the sum of their casts
Nat.cast_one- the cast of 1 from natural numbers equals 1
Nat.cast_sub- for natural numbers m ≤ n, the cast of their difference n - m equals the difference of their casts ↑n - ↑m
forest_carpool_fibonacci_envelope_decay- for any level k ≥ 4, the tail envelope satisfies the decay condition envelope(k + 1) + envelope(k - 1)^2 ≤ envelope(k)
add_le_add- if a ≤ b and c ≤ d, then a + c ≤ b + d
pow_two- the square of an element a in a monoid equals a * a
- Lines 23–30 reconcile natural number arithmetic (such as D - 1 in ℕ) with integer arithmetic (D - 1 in ℤ) via explicit cast lemmas (Nat.cast_sub, etc.), which is purely formal bookkeeping with no counterpart in paper mathematics.
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.
theorem forest_greedy_merge_large_levels (α β : Type) [Fintype α] [Fintype β] [Nonempty α] [Nonempty β] (X : α → ℤ) (Y : β → ℤ) (hX : forest_greedy_law_enveloped α X) (hY : forest_greedy_law_enveloped β Y) (D : ℕ) (hD : 4 ≤ D) : (((Finset.univ.filter (fun p : α × β × Bool => (D : ℤ) ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)).card : ℝ) / (Fintype.card (α × β × Bool) : ℝ)) ≤ forest_carpool_tail_envelope D := by have hd1 : 1 ≤ D := by omega have hdm : 1 ≤ D - 1 := by omega have hxp := hX.2.2 (D + 1) (by omega) have hxm := hX.2.2 (D - 1) hdm have hym := hY.2.2 (D - 1) hdm have he : 0 ≤ forest_carpool_tail_envelope (D - 1) := by unfold forest_carpool_tail_envelope split_ifs <;> positivity have hproduct : (((Finset.univ.filter (fun a => ((D - 1 : ℕ) : ℤ) ≤ X a)).card : ℝ) / Fintype.card α) * (((Finset.univ.filter (fun b => ((D - 1 : ℕ) : ℤ) ≤ Y b)).card : ℝ) / Fintype.card β) ≤ forest_carpool_tail_envelope (D - 1) * forest_carpool_tail_envelope (D - 1) := mul_le_mul hxm hym (by positivity) he have hstep := forest_greedy_high_tail_step α β X Y (D : ℤ) have hstep' : (((Finset.univ.filter (fun p : α × β × Bool => (D : ℤ) ≤ forest_greedy_signed_step (X p.1) (Y p.2.1) p.2.2)).card : ℝ) / (Fintype.card (α × β × Bool) : ℝ)) ≤ (((Finset.univ.filter (fun a => ((D + 1 : ℕ) : ℤ) ≤ X a)).card : ℝ) / Fintype.card α) + (((Finset.univ.filter (fun a => ((D - 1 : ℕ) : ℤ) ≤ X a)).card : ℝ) / Fintype.card α) * (((Finset.univ.filter (fun b => ((D - 1 : ℕ) : ℤ) ≤ Y b)).card : ℝ) / Fintype.card β) := by simpa only [Nat.cast_add, Nat.cast_one, Nat.cast_sub hd1] using hstep have hdecay := forest_carpool_fibonacci_envelope_decay D hD calc _ ≤ _ := hstep' _ ≤ forest_carpool_tail_envelope (D + 1) + forest_carpool_tail_envelope (D - 1) * forest_carpool_tail_envelope (D - 1) := add_le_add hxp hproduct _ ≤ _ := by simpa [pow_two] using hdecay