AFTD Auto-Formalizing Theoretical Domains

forest_greedy_merge_large_levels

theoremverified

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

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. 1 ≤ D and 1 ≤ D - 1

    Because D ≥ 4 by assumption, both D and D - 1 are at least 1 by linear integer arithmetic.

    lines 9–10

      have hd1 : 1 ≤ D := by omega
      have hdm : 1 ≤ D - 1 := by omega
  2. 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.

    lines 11–13

      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
  3. 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.

    lines 14–16

      have he : 0 ≤ forest_carpool_tail_envelope (D - 1) := by
        unfold forest_carpool_tail_envelope
        split_ifs <;> positivity
  4. 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.

    lines 17–21

    uses mul_le_mul

      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
  5. 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.

    lines 22–30

    uses forest_greedy_high_tail_step, Nat.cast_add, Nat.cast_one, Nat.cast_sub

      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
  6. 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.

    line 31

    uses forest_carpool_fibonacci_envelope_decay

      have hdecay := forest_carpool_fibonacci_envelope_decay D hD
  7. The 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.

    lines 32–37

    uses add_le_add, pow_two

      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
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

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

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