AFTD Auto-Formalizing Theoretical Domains

bpe_deviation_prob_nonneg

theoremverified

For any source bias p ∈ (0, 1), step count k, input length N, target constant c, and tolerance ε, the deviation probability bpe_deviation_prob p hp k N c ε is ≥ 0.

Statement

theorem bpe_deviation_prob_nonneg (p : ℝ) (hp : 0 < p ∧ p < 1) (k N : ℕ) (c ε : ℝ) : 0 ≤ bpe_deviation_prob p hp k N c ε
Source
step towards op_1533_iid_binary_greedy_bpe_universal_rate
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • bpe_deviation_probGiven parameters (p : ℝ), hypothesis (hp : 0 < p ∧ p < 1), (k N : ℕ), and (c ε : ℝ), bpe_deviation_prob p hp k N c ε is the real number…
  • boolean_product_bernoulliGiven a finite type $U$ and a parameter $p$ in the unit interval unitInterval (the closed interval $[0, 1]$),…
  • bpe_greedy_runThe relation defining a k-step greedy Byte-Pair Encoding run on string s yielding string t: for k = 0 we have s = t, and for k + 1 there…
  • binaryEntropyThe binary entropy function \[ H(x) \;=\; -x\log_2 x - (1-x)\log_2(1-x), \] using the base-$2$ logarithm, with the convention…
  • weighted_max_cut_linear_combinationFor all real numbers W and M, the convex combination of (3/4)W + (3/16)M and W - M with weights 16/19 and 3/19 equals (15/19)W.

The proof, explained

The deviation probability `bpe_deviation_prob` is defined as the real value (`toReal`) of an extended non-negative real measure (`ENNReal`). Unfolding its definition reduces the goal to showing that the real cast of a measure is non-negative, which holds identically for all `ENNReal` values and is solved by simplification.

  1. 0 ≤ bpe_deviation_prob p hp k N c ε automation

    Unfolding the definition of `bpe_deviation_prob`, the deviation probability is defined as `(μ s).toReal`, the conversion to `ℝ` of the measure of an event under the Bernoulli product measure. Because extended non-negative reals (`ENNReal`) always have non-negative real parts (`0 ≤ x.toReal`), the simplifier simplifies the inequality to `True`, closing the goal.

    line 2

    uses bpe_deviation_prob, weighted_max_cut_linear_combination

    theorem bpe_deviation_prob_nonneg (p : ℝ) (hp : 0 < p ∧ p < 1) (k N : ℕ) (c ε : ℝ) : 0 ≤ bpe_deviation_prob p hp k N c ε := by first | exact weighted_max_cut_linear_combination | (apply weighted_max_cut_linear_combination <;> assumption) | (apply weighted_max_cut_linear_combination <;> simp_all) | simpa using weighted_max_cut_linear_combination | (simp only [bpe_deviation_prob] at *; first | exact weighted_max_cut_linear_combination | (apply weighted_max_cut_linear_combination <;> assumption) | (apply weighted_max_cut_linear_combination <;> simp_all) | simpa using weighted_max_cut_linear_combination)
bpe_deviation_prob
The definition of the deviation probability, given as the real value (`.toReal`) of the Bernoulli product measure of the set of bit strings where greedy BPE compression deviates by more than ε from c.
weighted_max_cut_linear_combination
An algebraic identity relating weighted linear combinations of cut values: (16 / 19) * ((3 / 4) * W + (3 / 16) * M) + (3 / 19) * (W - M) = (15 / 19) * W (an unused artifact here).

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

/-- The greedy BPE deviation probability is non-negative. -/theorem bpe_deviation_prob_nonneg (p : ℝ) (hp : 0 < p ∧ p < 1) (k N : ℕ) (c ε : ℝ) : 0 ≤ bpe_deviation_prob p hp k N c ε := by first | exact weighted_max_cut_linear_combination | (apply weighted_max_cut_linear_combination <;> assumption) | (apply weighted_max_cut_linear_combination <;> simp_all) | simpa using weighted_max_cut_linear_combination | (simp only [bpe_deviation_prob] at *; first | exact weighted_max_cut_linear_combination | (apply weighted_max_cut_linear_combination <;> assumption) | (apply weighted_max_cut_linear_combination <;> simp_all) | simpa using weighted_max_cut_linear_combination)
See it in the graphDiscuss this resultChallenge it