AFTD Auto-Formalizing Theoretical Domains

forest_greedy_enveloped_tie_bias_one

theoremverified

An enveloped fixed-parity law and a fair coin permit an increase from discrepancy 1 with probability at most 3/8.

Statement

theorem forest_greedy_enveloped_tie_bias_one (β : Type) [Fintype β] [Nonempty β]
    (Y : β → ℤ) (hY : forest_greedy_law_enveloped β Y) :
  (((Finset.univ.filter (fun p : β × Bool =>
    (1 : ℤ) < Y p.1 ∨ ((1 : ℤ) = Y p.1 ∧ p.2 = true))).card : ℝ) /
    (Fintype.card (β × Bool) : ℝ)) ≤ 3 / 8
Source
Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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_enveloped_tie_bias_boundFor an enveloped fixed-parity law and a fair coin, the probability of a greedy increase from a positive discrepancy j is bounded by the…
Used by 1

The proof, explained

The proof specializes the general enveloped tie-bias bound `forest_greedy_enveloped_tie_bias_bound` to initial discrepancy j = 1. Evaluating the tail envelope at arguments 1, 2, and 3 yields E(1) = 1/2, E(2) = 3/8, and E(3) = 1/4, so max(E(2), (E(1) + E(3)) / 2) simplifies directly to 3/8. Rewriting the cardinality of the product sample space β × Bool matches the goal to this simplified bound.

  1. The general tie-bias bound applies at discrepancy j = 1, giving an upper bound of max(E(2), (E(1) + E(3)) / 2).

    Specialising `forest_greedy_enveloped_tie_bias_bound` to j = 1 (where the prerequisite 1 ≤ 1 is proved by linear integer arithmetic) yields an inequality bounding the probability of discrepancy strictly greater than 1, or equal to 1 with coin flip true, by the envelope combination max(E(1+1), (E(1) + E(1+2)) / 2).

    line 6

    uses forest_greedy_enveloped_tie_bias_bound

      have h := forest_greedy_enveloped_tie_bias_bound β Y hY 1 (by omega)
  2. The envelope upper bound evaluates numerically to 3/8.

    By definition of `forest_carpool_tail_envelope` and `Nat.fib`, we have E(1) = (1/2)^1 = 1/2, E(2) = 3/8, and E(3) = (1/2)^2 = 1/4. The average (E(1) + E(3)) / 2 is (1/2 + 1/4) / 2 = 3/8, and the maximum max(3/8, 3/8) is 3/8. Evaluating these definitions reduces the upper bound in hypothesis h to 3/8.

    line 7

    uses forest_carpool_tail_envelope, Nat.fib

      norm_num [forest_carpool_tail_envelope, Nat.fib] at h
  3. The goal follows from the evaluated bound by expanding the cardinality of the product space.

    The denominator in the goal is the size of the product space β × Bool. Rewriting this cardinality via `Fintype.card_prod` and `Fintype.card_bool` as |β| * 2, and distributing casts using `Nat.cast_mul` and `Nat.cast_ofNat`, matches the left-hand side of the simplified bound h, completing the proof.

    line 8

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

      simpa only [Fintype.card_prod, Fintype.card_bool, Nat.cast_mul, Nat.cast_ofNat] using h
forest_greedy_enveloped_tie_bias_bound
For an enveloped law Y on β and any integer j ≥ 1, the probability that Y > j or that Y = j with coin flip true is at most max(E(j+1), (E(j) + E(j+2)) / 2), where E is the carpool tail envelope.
forest_carpool_tail_envelope
The tail envelope function E(k), equal to 3/8 if k = 2 and (1/2)^(fib(k)) otherwise.
Nat.fib
The n-th Fibonacci number.
Fintype.card_prod
The cardinality of the Cartesian product α × β is the product of the cardinalities of α and β.
Fintype.card_bool
The type Bool has exactly 2 elements.
Nat.cast_mul
Casting a product of natural numbers to a semiring distributes over multiplication: ↑(m * n) = ↑m * ↑n.
Nat.cast_ofNat
Casting a numeral from ℕ to another type with numeral notation preserves the numeral.

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_one (β : Type) [Fintype β] [Nonempty β]    (Y : β → ℤ) (hY : forest_greedy_law_enveloped β Y) :  (((Finset.univ.filter (fun p : β × Bool =>    (1 : ℤ) < Y p.1 ∨ ((1 : ℤ) = Y p.1 ∧ p.2 = true))).card : ℝ) /    (Fintype.card (β × Bool) : ℝ)) ≤ 3 / 8 := by  have h := forest_greedy_enveloped_tie_bias_bound β Y hY 1 (by omega)  norm_num [forest_carpool_tail_envelope, Nat.fib] at h  simpa only [Fintype.card_prod, Fintype.card_bool, Nat.cast_mul, Nat.cast_ofNat] using h
See it in the graphDiscuss this resultChallenge it