AFTD Auto-Formalizing Theoretical Domains

forest_greedy_enveloped_tie_bias_two

theoremverified

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

Statement

theorem forest_greedy_enveloped_tie_bias_two (β : Type) [Fintype β] [Nonempty β]
    (Y : β → ℤ) (hY : forest_greedy_law_enveloped β Y) :
  (((Finset.univ.filter (fun p : β × Bool =>
    (2 : ℤ) < Y p.1 ∨ ((2 : ℤ) = Y p.1 ∧ p.2 = true))).card : ℝ) /
    (Fintype.card (β × Bool) : ℝ)) ≤ 1 / 4
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 theorem establishes that for an enveloped law and an independent fair coin, the probability of exceeding 2 (or equaling 2 with a true coin toss) is at most 1/4. The proof specializes the general envelope tie-bias bound at threshold j = 2, yielding an upper bound of max(E(3), (E(2) + E(4)) / 2). Evaluating the envelope definition and Fibonacci values simplifies this bound numerically to 1/4, and rewriting the cardinality of β × Bool completes the argument.

  1. The probability of exceeding discrepancy 2 (or equaling 2 with a true coin) is bounded by max(E(3), (E(2) + E(4)) / 2), where E is the carpool tail envelope.

    We apply the general tie-bias bound lemma `forest_greedy_enveloped_tie_bias_bound` with discrepancy threshold j = 2. The required precondition 1 ≤ 2 is discharged by integer linear arithmetic (`omega`).

    line 6

    uses forest_greedy_enveloped_tie_bias_bound

      have h := forest_greedy_enveloped_tie_bias_bound β Y hY 2 (by omega)
  2. The upper bound max(E(3), (E(2) + E(4)) / 2) simplifies numerically to 1/4.

    By definition of the envelope function E and the Fibonacci sequence, E(2) = 3/8, E(3) = (1/2)^(fib 3) = (1/2)^2 = 1/4, and E(4) = (1/2)^(fib 4) = (1/2)^3 = 1/8. The average (E(2) + E(4)) / 2 is (3/8 + 1/8) / 2 = 1/4, making the maximum max(1/4, 1/4) = 1/4. Numerical evaluation (`norm_num`) computes this directly and simplifies the bound in hypothesis h.

    line 7

    uses forest_carpool_tail_envelope, Nat.fib

      norm_num [forest_carpool_tail_envelope, Nat.fib] at h
  3. The probability of increasing from discrepancy 2 is at most 1/4, completing the proof.

    The denominator |β × Bool| equals |β| × |Bool| = 2|β| using the product cardinality lemma and the fact that Bool has two elements. Rewriting these cardinalities reconciles the denominator in the goal with the hypothesis h, closing the goal.

    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 greedy law and an independent fair coin, the probability of exceeding a threshold j ≥ 1 (or tying at j with a true coin toss) 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, defined as 3/8 when k = 2 and (1/2)^(fib(k)) otherwise.
Nat.fib
The Fibonacci sequence on natural numbers, defined by fib(0) = 0, fib(1) = 1, and fib(n+2) = fib(n+1) + fib(n).
Fintype.card_prod
The cardinality of the Cartesian product of two finite types is the product of their cardinalities.
Fintype.card_bool
The finite type of boolean values has cardinality 2.
Nat.cast_mul
The coercion of a product of natural numbers into a ring equals the product of the coerced factors.
Nat.cast_ofNat
The coercion of a natural numeral literal into a target type equals the numeral in that type.

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_two (β : Type) [Fintype β] [Nonempty β]    (Y : β → ℤ) (hY : forest_greedy_law_enveloped β Y) :  (((Finset.univ.filter (fun p : β × Bool =>    (2 : ℤ) < Y p.1 ∨ ((2 : ℤ) = Y p.1 ∧ p.2 = true))).card : ℝ) /    (Fintype.card (β × Bool) : ℝ)) ≤ 1 / 4 := by  have h := forest_greedy_enveloped_tie_bias_bound β Y hY 2 (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