AFTD Auto-Formalizing Theoretical Domains

forest_greedy_enveloped_tie_bias_bound

theoremverified

For an enveloped fixed-parity law and a fair coin, the probability of a greedy increase from a positive discrepancy j is bounded by the larger of the envelope at j+1 and the average of its values at j and j+2.

Statement

theorem forest_greedy_enveloped_tie_bias_bound (β : Type) [Fintype β] [Nonempty β]
    (Y : β → ℤ) (hY : forest_greedy_law_enveloped β Y) (j : ℕ) (hj : 1 ≤ j) :
  (((Finset.univ.filter (fun p : β × Bool =>
    (j : ℤ) < Y p.1 ∨ ((j : ℤ) = Y p.1 ∧ p.2 = true))).card : ℝ) /
    (Fintype.card (β × Bool) : ℝ)) ≤
  max (forest_carpool_tail_envelope (j + 1))
    ((forest_carpool_tail_envelope j + forest_carpool_tail_envelope (j + 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 4
  • 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.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 2

The proof, explained

The proof decomposes the favorable event for a greedy increase—either Y b > j, or Y b = j with a fair coin landing true—into disjoint components and analyses its probability based on whether ties can occur. If no ties occur (|equal| = 0), the probability simplifies to the single tail probability at j + 1, bounded by the envelope at j + 1. If ties can occur (|equal| > 0), the constant parity of Y forces all values strictly greater than j to be at least j + 2; the probability then equals the arithmetic mean of the tail probabilities at j and j + 2, which is bounded by the average of the envelopes at j and j + 2. In either case, the probability is bounded by the maximum of the two quantities.

  1. Define the subsets of outcomes according to how Y compares to j.

    We partition outcomes of β into those strictly greater than j (above), equal to j (equal), at least j (lo), and at least j + 2 (hi). We also define fav ⊆ β × Bool as the favorable event where either Y b > j, or Y b = j and the coin toss lands true.

    lines 8–14

      classical
      let above : Finset β := Finset.univ.filter (fun b => (j : ℤ) < Y b)
      let equal : Finset β := Finset.univ.filter (fun b => (j : ℤ) = Y b)
      let lo : Finset β := Finset.univ.filter (fun b => (j : ℤ) ≤ Y b)
      let hi : Finset β := Finset.univ.filter (fun b => ((j + 2 : ℕ) : ℤ) ≤ Y b)
      let fav : Finset (β × Bool) := Finset.univ.filter (fun p =>
        (j : ℤ) < Y p.1 ∨ ((j : ℤ) = Y p.1 ∧ p.2 = true))
  2. The sets above and equal are disjoint, and the favorable event has size |fav| = 2|above| + |equal|.

    No outcome can satisfy both j < Y a and j = Y a, so above and equal are disjoint. Consequently, the Cartesian products above × Bool and equal × {true} are disjoint, and their union is exactly fav. Since Bool has 2 elements and {true} has 1, the size of fav is 2|above| + |equal|.

    lines 15–33

    uses Finset.disjoint_left.mpr, Finset.mem_filter.mp, Finset.mem_product, Finset.mem_product.mp, Finset.disjoint_left.mp, Finset.card_union_of_disjoint, Finset.card_product, Nat.mul_comm

      have hdis : Disjoint above equal := by
        apply Finset.disjoint_left.mpr
        intro a ha hb
        have ha' : (j : ℤ) < Y a := (Finset.mem_filter.mp ha).2
        have hb' : (j : ℤ) = Y a := (Finset.mem_filter.mp hb).2
        omega
      have hevent : fav = (above ×ˢ (Finset.univ : Finset Bool)) ∪ (equal ×ˢ {true}) := by
        ext p
        rcases p with ⟨b, c⟩
        simp [fav, above, equal, Finset.mem_product]
      have hprod_dis : Disjoint (above ×ˢ (Finset.univ : Finset Bool)) (equal ×ˢ {true}) := by
        apply Finset.disjoint_left.mpr
        intro p hp hq
        have ha : p.1 ∈ above := (Finset.mem_product.mp hp).1
        have hb : p.1 ∈ equal := (Finset.mem_product.mp hq).1
        exact (Finset.disjoint_left.mp hdis) ha hb
      have hfav : fav.card = 2 * above.card + equal.card := by
        rw [hevent, Finset.card_union_of_disjoint hprod_dis]
        simp [Finset.card_product, Nat.mul_comm]
  3. The set lo is the disjoint union of above and equal, so |lo| = |above| + |equal|.

    An integer satisfies j ≤ Y b if and only if j < Y b or j = Y b. Thus lo = above ∪ equal, and because above and equal are disjoint, the size of lo is the sum of their sizes.

    lines 34–39

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union, Finset.card_union_of_disjoint

      have hlo : lo = above ∪ equal := by
        ext b
        simp only [lo, above, equal, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union]
        omega
      have hlo_card : lo.card = above.card + equal.card := by
        rw [hlo, Finset.card_union_of_disjoint hdis]
  4. The state spaces have positive cardinality, and we extract the constant parity and tail bound hypotheses from the enveloped law.

    Because β and β × Bool are nonempty finite types, their cardinalities are strictly positive. From the assumption that Y is an enveloped greedy law, we extract that all values Y a share a constant parity modulo 2 and that the upper tail probabilities at any threshold k ≥ 1 are bounded by forest_carpool_tail_envelope(k).

    lines 40–44

    uses Fintype.card_pos

      have hp : (0 : ℝ) < Fintype.card β := by exact_mod_cast (Fintype.card_pos (α := β))
      have hpc : (0 : ℝ) < Fintype.card (β × Bool) := by
        exact_mod_cast (Fintype.card_pos (α := β × Bool))
      obtain ⟨parity, hparity⟩ := hY.1
      have htail := hY.2.2
  5. When no element has value j, the favorable count is 2|above| and above coincides with the tail at j + 1.

    We split into cases on whether |equal| = 0. When |equal| = 0, no ties can occur, so |fav| = 2|above|. Over the integers, j < Y b is equivalent to j + 1 ≤ Y b, which identifies above with the tail event at threshold j + 1. Since j ≥ 1, the tail bound hypothesis applies at threshold j + 1.

    lines 45–52

    uses Finset.mem_filter, Finset.mem_univ, true_and, Nat.cast_add, Nat.cast_one

      by_cases hzero : equal.card = 0
      · have hzeroR : (equal.card : ℝ) = 0 := by exact_mod_cast hzero
        have hfavR : (fav.card : ℝ) = 2 * (above.card : ℝ) := by exact_mod_cast (show fav.card = 2 * above.card by omega)
        have habove : above = Finset.univ.filter (fun b => ((j + 1 : ℕ) : ℤ) ≤ Y b) := by
          ext b
          simp only [above, Finset.mem_filter, Finset.mem_univ, true_and, Nat.cast_add, Nat.cast_one]
          omega
        have htail1 := htail (j + 1) (by omega)
  6. When |equal| = 0, the probability is at most the envelope at j + 1, which is at most the maximum.

    The total number of states is |β × Bool| = 2|β|. The probability |fav| / (2|β|) = 2|above| / (2|β|) simplifies to |above| / |β|. By the tail bound at j + 1, this is bounded by forest_carpool_tail_envelope(j + 1), which is at most the maximum of the envelope at j + 1 and the average via le_max_left.

    lines 53–61

    uses Fintype.card_prod, Fintype.card_bool, Nat.cast_mul, Nat.cast_ofNat, ne_of_gt, le_max_left

        have hprob : (fav.card : ℝ) / Fintype.card (β × Bool) =
            (above.card : ℝ) / Fintype.card β := by
          rw [hfavR]
          simp only [Fintype.card_prod, Fintype.card_bool, Nat.cast_mul, Nat.cast_ofNat]
          field_simp [ne_of_gt hp]
        calc
          _ = (above.card : ℝ) / Fintype.card β := hprob
          _ ≤ forest_carpool_tail_envelope (j + 1) := by simpa [habove] using htail1
          _ ≤ _ := le_max_left _ _
  7. When some element has value j, all outcomes share the parity of j, which implies above = hi.

    When |equal| ≠ 0, there is a witness b₀ with Y b₀ = j. By the constant parity property, every Y b has the same parity modulo 2 as j. Therefore, Y b > j implies Y b ≥ j + 2, meaning above is identical to the tail set hi = {b | j + 2 ≤ Y b}.

    lines 62–70

    uses Finset.card_pos.mp, Nat.pos_of_ne_zero, Finset.mem_filter.mp, Finset.mem_filter, Finset.mem_univ, true_and, Nat.cast_add, Nat.cast_ofNat

      · have hex : ∃ b, b ∈ equal := Finset.card_pos.mp (Nat.pos_of_ne_zero hzero)
        obtain ⟨b0, hb0⟩ := hex
        have hb0' : (j : ℤ) = Y b0 := (Finset.mem_filter.mp hb0).2
        have habove : above = hi := by
          ext b
          have hpar : Y b % 2 = (j : ℤ) % 2 := by rw [hparity b, ← hparity b0, ← hb0']
          simp only [above, hi, Finset.mem_filter, Finset.mem_univ, true_and, Nat.cast_add,
            Nat.cast_ofNat]
          omega
  8. When |equal| ≠ 0, |fav| = |lo| + |hi|, and we obtain the tail envelope bounds at j and j + 2.

    Using |lo| = |above| + |equal| and above = hi, we rewrite |fav| = 2|above| + |equal| as |lo| + |hi|. Since j ≥ 1 and j + 2 ≥ 1, the enveloped law tail bounds apply at thresholds j and j + 2.

    lines 71–74

        have hfav2 : fav.card = lo.card + hi.card := by rw [hlo_card, ← habove, hfav]; omega
        have hfavR : (fav.card : ℝ) = (lo.card : ℝ) + (hi.card : ℝ) := by exact_mod_cast hfav2
        have htail0 := htail j hj
        have htail2 := htail (j + 2) (by omega)
  9. When |equal| ≠ 0, the probability is bounded by the average of the envelopes at j and j + 2, which is at most the maximum.

    Dividing |fav| = |lo| + |hi| by |β × Bool| = 2|β| expresses the probability as the arithmetic mean of the tail probabilities at j and j + 2. Applying the tail bounds at j and j + 2 bounds this mean by (forest_carpool_tail_envelope(j) + forest_carpool_tail_envelope(j + 2)) / 2, which by le_max_right is at most the maximum.

    lines 75–86

    uses Fintype.card_prod, Fintype.card_bool, Nat.cast_mul, Nat.cast_ofNat, ne_of_gt, le_max_right

        have hprob : (fav.card : ℝ) / Fintype.card (β × Bool) =
            ((lo.card : ℝ) / Fintype.card β + (hi.card : ℝ) / Fintype.card β) / 2 := by
          rw [hfavR]
          simp only [Fintype.card_prod, Fintype.card_bool, Nat.cast_mul, Nat.cast_ofNat]
          field_simp [ne_of_gt hp] <;> ring
        calc
          _ = ((lo.card : ℝ) / Fintype.card β + (hi.card : ℝ) / Fintype.card β) / 2 := hprob
          _ ≤ (forest_carpool_tail_envelope j + forest_carpool_tail_envelope (j + 2)) / 2 := by
            have h0 : (lo.card : ℝ) / Fintype.card β ≤ forest_carpool_tail_envelope j := by simpa [lo] using htail0
            have h2 : (hi.card : ℝ) / Fintype.card β ≤ forest_carpool_tail_envelope (j + 2) := by simpa [hi] using htail2
            linarith
          _ ≤ _ := le_max_right _ _
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first belongs to the second.
Finset.mem_filter.mp
If an element belongs to a filtered finite set, then it belongs to the base set and satisfies the predicate.
Finset.mem_product
An element belongs to the Cartesian product of two finite sets if and only if its first component belongs to the first set and its second component belongs to the second set.
Finset.mem_product.mp
If an element belongs to the Cartesian product of two finite sets, its components belong to the respective sets.
Finset.disjoint_left.mp
If two finite sets are disjoint, any element in the first set does not belong to the second set.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_product
The cardinality of the Cartesian product of two finite sets is the product of their cardinalities.
Nat.mul_comm
Multiplication of natural numbers is commutative.
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set of that type.
true_and
The logical conjunction of True and a proposition p is equivalent to p.
Finset.mem_union
An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
Fintype.card_pos
A nonempty finite type has strictly positive cardinality.
Nat.cast_add
The coercion of a sum of natural numbers to an additive monoid with one equals the sum of their coercions.
Nat.cast_one
The coercion of 1 to an additive monoid with one equals 1.
Fintype.card_prod
The cardinality of the product of two finite types is the product of their cardinalities.
Fintype.card_bool
The type of Booleans has cardinality 2.
Nat.cast_mul
The coercion of a product of natural numbers equals the product of their coercions.
Nat.cast_ofNat
Numeric numerals coerce to their corresponding values in a numerical type.
ne_of_gt
If b < a in a preorder, then a ≠ b.
le_max_left
Any value a is less than or equal to the maximum of a and b.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
Nat.pos_of_ne_zero
A non-zero natural number is strictly positive.
le_max_right
Any value b is less than or equal to the maximum of a and b.

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_enveloped_tie_bias_bound (β : Type) [Fintype β] [Nonempty β]    (Y : β → ℤ) (hY : forest_greedy_law_enveloped β Y) (j : ℕ) (hj : 1 ≤ j) :  (((Finset.univ.filter (fun p : β × Bool =>    (j : ℤ) < Y p.1 ∨ ((j : ℤ) = Y p.1 ∧ p.2 = true))).card : ℝ) /    (Fintype.card (β × Bool) : ℝ)) ≤  max (forest_carpool_tail_envelope (j + 1))    ((forest_carpool_tail_envelope j + forest_carpool_tail_envelope (j + 2)) / 2) := by  classical  let above : Finset β := Finset.univ.filter (fun b => (j : ℤ) < Y b)  let equal : Finset β := Finset.univ.filter (fun b => (j : ℤ) = Y b)  let lo : Finset β := Finset.univ.filter (fun b => (j : ℤ) ≤ Y b)  let hi : Finset β := Finset.univ.filter (fun b => ((j + 2 : ℕ) : ℤ) ≤ Y b)  let fav : Finset (β × Bool) := Finset.univ.filter (fun p =>    (j : ℤ) < Y p.1 ∨ ((j : ℤ) = Y p.1 ∧ p.2 = true))  have hdis : Disjoint above equal := by    apply Finset.disjoint_left.mpr    intro a ha hb    have ha' : (j : ℤ) < Y a := (Finset.mem_filter.mp ha).2    have hb' : (j : ℤ) = Y a := (Finset.mem_filter.mp hb).2    omega  have hevent : fav = (above ×ˢ (Finset.univ : Finset Bool)) ∪ (equal ×ˢ {true}) := by    ext p    rcases p with ⟨b, c⟩    simp [fav, above, equal, Finset.mem_product]  have hprod_dis : Disjoint (above ×ˢ (Finset.univ : Finset Bool)) (equal ×ˢ {true}) := by    apply Finset.disjoint_left.mpr    intro p hp hq    have ha : p.1 ∈ above := (Finset.mem_product.mp hp).1    have hb : p.1 ∈ equal := (Finset.mem_product.mp hq).1    exact (Finset.disjoint_left.mp hdis) ha hb  have hfav : fav.card = 2 * above.card + equal.card := by    rw [hevent, Finset.card_union_of_disjoint hprod_dis]    simp [Finset.card_product, Nat.mul_comm]  have hlo : lo = above ∪ equal := by    ext b    simp only [lo, above, equal, Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union]    omega  have hlo_card : lo.card = above.card + equal.card := by    rw [hlo, Finset.card_union_of_disjoint hdis]  have hp : (0 : ℝ) < Fintype.card β := by exact_mod_cast (Fintype.card_pos (α := β))  have hpc : (0 : ℝ) < Fintype.card (β × Bool) := by    exact_mod_cast (Fintype.card_pos (α := β × Bool))  obtain ⟨parity, hparity⟩ := hY.1  have htail := hY.2.2  by_cases hzero : equal.card = 0  · have hzeroR : (equal.card : ℝ) = 0 := by exact_mod_cast hzero    have hfavR : (fav.card : ℝ) = 2 * (above.card : ℝ) := by exact_mod_cast (show fav.card = 2 * above.card by omega)    have habove : above = Finset.univ.filter (fun b => ((j + 1 : ℕ) : ℤ) ≤ Y b) := by      ext b      simp only [above, Finset.mem_filter, Finset.mem_univ, true_and, Nat.cast_add, Nat.cast_one]      omega    have htail1 := htail (j + 1) (by omega)    have hprob : (fav.card : ℝ) / Fintype.card (β × Bool) =        (above.card : ℝ) / Fintype.card β := by      rw [hfavR]      simp only [Fintype.card_prod, Fintype.card_bool, Nat.cast_mul, Nat.cast_ofNat]      field_simp [ne_of_gt hp]    calc      _ = (above.card : ℝ) / Fintype.card β := hprob      _ ≤ forest_carpool_tail_envelope (j + 1) := by simpa [habove] using htail1      _ ≤ _ := le_max_left _ _  · have hex : ∃ b, b ∈ equal := Finset.card_pos.mp (Nat.pos_of_ne_zero hzero)    obtain ⟨b0, hb0⟩ := hex    have hb0' : (j : ℤ) = Y b0 := (Finset.mem_filter.mp hb0).2    have habove : above = hi := by      ext b      have hpar : Y b % 2 = (j : ℤ) % 2 := by rw [hparity b, ← hparity b0, ← hb0']      simp only [above, hi, Finset.mem_filter, Finset.mem_univ, true_and, Nat.cast_add,        Nat.cast_ofNat]      omega    have hfav2 : fav.card = lo.card + hi.card := by rw [hlo_card, ← habove, hfav]; omega    have hfavR : (fav.card : ℝ) = (lo.card : ℝ) + (hi.card : ℝ) := by exact_mod_cast hfav2    have htail0 := htail j hj    have htail2 := htail (j + 2) (by omega)    have hprob : (fav.card : ℝ) / Fintype.card (β × Bool) =        ((lo.card : ℝ) / Fintype.card β + (hi.card : ℝ) / Fintype.card β) / 2 := by      rw [hfavR]      simp only [Fintype.card_prod, Fintype.card_bool, Nat.cast_mul, Nat.cast_ofNat]      field_simp [ne_of_gt hp] <;> ring    calc      _ = ((lo.card : ℝ) / Fintype.card β + (hi.card : ℝ) / Fintype.card β) / 2 := hprob      _ ≤ (forest_carpool_tail_envelope j + forest_carpool_tail_envelope (j + 2)) / 2 := by        have h0 : (lo.card : ℝ) / Fintype.card β ≤ forest_carpool_tail_envelope j := by simpa [lo] using htail0        have h2 : (hi.card : ℝ) / Fintype.card β ≤ forest_carpool_tail_envelope (j + 2) := by simpa [hi] using htail2        linarith      _ ≤ _ := le_max_right _ _
See it in the graphDiscuss this resultChallenge it