AFTD Auto-Formalizing Theoretical Domains

op_1604_iid_greedy_bpe_budget_one

theoremverifiedformalization

Open Problem OP-1604 (budget k = 1 case): For a merge budget of k = 1, every alphabet size q ≥ 2, every strictly positive probability vector p on Fin q summing to 1, and every tolerance ε > 0, the greedy BPE approximation probability iid_greedy_bpe_approx_prob q p 1 N ε tends to 1 as string length N tends to infinity.

Statement

theorem op_1604_iid_greedy_bpe_budget_one
    (q : ℕ) (hq : 2 ≤ q) (p : Fin q → ℝ) (hp_pos : ∀ i, 0 < p i) (hp_sum : ∑ i, p i = 1)
    (ε : ℝ) (hε : 0 < ε) :
    Filter.Tendsto (fun N : ℕ => iid_greedy_bpe_approx_prob q p 1 N ε) Filter.atTop (nhds 1)
Formalizes
arXiv:2411.08671 Greedy Byte-Pair Encoding Achieves at Least 0.361 of the Optimal Compression, Section 4.3; open problem OP-1604
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • bpe_min_greedy_utility_one_eq_optimalFor any string s and merge budget k = 1, the minimum reduction in length achieved by a greedy full-merge step equals the optimal reduction…
  • iid_greedy_bpe_approx_probGiven alphabet size q, weights p : Fin q → ℝ, merge budget k, length N, and tolerance ε : ℝ, iid_greedy_bpe_approx_prob q p k N ε is the…
  • iid_word_measureGiven natural numbers q and N, and real weights p : Fin q → ℝ, iid_word_measure q N p is the product measure on words Fin N → Fin q…
  • iid_bpe_sharp_factor_boundsThe i.i.d. BPE sharp approximation constant c = (2 + √2)/4 lies strictly in the open unit interval (0, 1).
  • iid_bpe_sharp_factorThe conjectured sharp uniform i.i.d. greedy Byte-Pair Encoding merge factor c = (2 + √2) / 4.
  • bpe_optimal_full_utilityThe maximum total reduction in string length achieved by any k-step sequence of full Byte-Pair Encoding merges on s.
  • bpe_min_greedy_utilityThe minimum total reduction in string length achieved by any k-step greedy Byte-Pair Encoding merge run on s under arbitrary tie-breaking.

Read back from the Lean

For every natural number $q$ such that $2 \le q$, every strictly positive probability vector $p : \mathrm{Fin}\;q \to \mathbb{R}$ (satisfying $0 < p(i)$ for all $i$ and $\sum_{i} p(i) = 1$), and every real number $\varepsilon > 0$: As the word length $N \to \infty$ along Filter.atTop, the probability (under the i.i.d. product measure of words of length $N$ drawn according to $p$) that a word $w$ satisfies $$\mathrm{bpe\_min\_greedy\_utility}(w, 1) \ge \left(\frac{2 + \sqrt{2}}{4} - \varepsilon\right) \cdot \mathrm{bpe\_optimal\_full\_utility}(w, 1)$$ tends to $1$ (in the topology of $\mathbb{R}$, i.e., nhds 1). Here, the utilities are measured in terms of word length reduction: - $\mathrm{bpe\_min\_greedy\_utility}(w, 1)$ is the infimum over all reachable strings $t$ via 1 greedy BPE merge step of the length reduction $N - \mathrm{length}(t)$. - $\mathrm{bpe\_optimal\_full\_utility}(w, 1)$ is the supremum over all reachable strings $t$ via 1 general BPE merge step of the length reduction $N - \mathrm{length}(t)$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

For a merge budget of k = 1, greedy BPE selects the most frequent adjacent pair in the string, which achieves the exact optimal utility for a single merge. Because the theoretical BPE sharp factor is strictly less than 1 and the tolerance ε > 0, the target ratio is strictly less than 1; combined with the non-negativity of utility, every string trivially satisfies the approximation condition. Consequently, the approximating event is the entire space of words, so its probability under the i.i.d. product measure is identically 1 for every string length N. Being a constant sequence, this probability converges to 1 as N tends to infinity.

  1. The single-letter marginal distribution is a probability measure.

    The marginal distribution on characters Fin q is defined as the discrete measure ∑ j, p j • Dirac j. To show it is a probability measure, it suffices to verify that the measure of the universal set is 1. Evaluating the finite sum of scaled Dirac measures on Set.univ reduces to ∑ j, p j * 1. Pulling the sum into ENNReal.ofReal using the non-negativity of each p j and applying the assumption ∑ j, p j = 1 shows the total measure is 1.

    lines 7–15

    uses MeasureTheory.Measure.coe_finsetSum, Finset.sum_apply, MeasureTheory.Measure.smul_apply, smul_eq_mul, MeasureTheory.Measure.dirac_apply, Set.indicator_of_mem, Set.mem_univ, Pi.one_apply, mul_one, ENNReal.ofReal_sum_of_nonneg, le_of_lt, ENNReal.ofReal_one

      have hmarg : MeasureTheory.IsProbabilityMeasure
          (∑ j, ENNReal.ofReal (p j) • MeasureTheory.Measure.dirac (j : Fin q)) := by
        refine ⟨?_⟩
        rw [MeasureTheory.Measure.coe_finsetSum]
        simp only [Finset.sum_apply, MeasureTheory.Measure.smul_apply, smul_eq_mul]
        simp only [MeasureTheory.Measure.dirac_apply, Set.indicator_of_mem, Set.mem_univ,
          Pi.one_apply, mul_one]
        rw [← ENNReal.ofReal_sum_of_nonneg (fun i _ => le_of_lt (hp_pos i)), hp_sum,
          ENNReal.ofReal_one]
  2. For every string length N, the greedy BPE approximation probability equals 1.

    Fixing an arbitrary string length N, the product measure iid_word_measure q N p is a probability measure because each coordinate marginal is one. Unfolding the definition of iid_greedy_bpe_approx_prob, the approximating event consists of all words w whose greedy utility is at least (c - ε) times their optimal utility, where c is the sharp BPE factor. For budget k = 1, greedy utility equals optimal utility (bpe_min_greedy_utility_one_eq_optimal). Since c < 1 (iid_bpe_sharp_factor_bounds.2) and ε > 0, the factor satisfies c - ε < 1. Because utility is non-negative, any value u ≥ 0 satisfies u ≥ (c - ε) * u, so every word satisfies the inequality and the event is the entire space Set.univ. Since the word measure is a probability measure, the measure of Set.univ is 1, so the probability is 1.

    lines 17–38

    uses MeasureTheory.Measure.pi.instIsProbabilityMeasure, Set.mem_ofPred_eq, Set.mem_univ, iff_true, bpe_min_greedy_utility_one_eq_optimal, iid_bpe_sharp_factor_bounds.2, MeasureTheory.measure_univ, ENNReal.toReal_one

      have hprob : ∀ N : ℕ, iid_greedy_bpe_approx_prob q p 1 N ε = 1 := by
        intro N
        haveI : MeasureTheory.IsProbabilityMeasure (iid_word_measure q N p) := by
          rw [iid_word_measure]
          exact MeasureTheory.Measure.pi.instIsProbabilityMeasure _
        unfold iid_greedy_bpe_approx_prob
        have huniv : {w : Fin N → Fin q |
            (bpe_min_greedy_utility (List.ofFn fun i => (w i : ℕ)) 1 : ℝ) ≥
              (iid_bpe_sharp_factor - ε) * (bpe_optimal_full_utility (List.ofFn fun i => (w i : ℕ)) 1 : ℝ)}
            = Set.univ := by
          ext w
          simp only [Set.mem_ofPred_eq, Set.mem_univ, iff_true]
          -- Greedy and optimal agree for one merge.
          rw [bpe_min_greedy_utility_one_eq_optimal]
          have hc : iid_bpe_sharp_factor - ε < 1 := by
            have := iid_bpe_sharp_factor_bounds.2
            linarith
          have hu : (0:ℝ) ≤ (bpe_optimal_full_utility (List.ofFn fun i => (w i : ℕ)) 1 : ℝ) := by
            positivity
          nlinarith
        rw [huniv, MeasureTheory.measure_univ]
        exact ENNReal.toReal_one
  3. The greedy BPE approximation probability tends to 1 as string length N tends to infinity.

    Since the greedy BPE approximation probability is identically 1 for all N, the sequence is constant. A constant sequence converges to its constant value, so the limit as N → ∞ is 1 (tendsto_const_nhds).

    lines 39–40

    uses tendsto_const_nhds

      simp only [hprob]
      exact tendsto_const_nhds
MeasureTheory.Measure.coe_finsetSum
Evaluating a finite sum of measures on a set equals the sum of the individual measures evaluated on that set.
Finset.sum_apply
Evaluating a pointwise finite sum of functions at a point equals the sum of each function evaluated at that point.
MeasureTheory.Measure.smul_apply
Evaluating a scalar-multiplied measure on a set equals the scalar times the measure of the set.
smul_eq_mul
Scalar multiplication of elements in a ring or monoid acting on itself is standard multiplication.
MeasureTheory.Measure.dirac_apply
The Dirac measure at a point evaluated on a set is the indicator of that set at the point.
Set.indicator_of_mem
The indicator function of a set evaluated at a point in that set takes the value of the underlying function at that point.
Set.mem_univ
Every element of a type belongs to the universal set of that type.
Pi.one_apply
Evaluating the constant function 1 at any argument gives 1.
mul_one
Multiplying any element by 1 on the right yields the element itself.
ENNReal.ofReal_sum_of_nonneg
The embedding from non-negative reals into extended non-negative reals preserves finite sums.
le_of_lt
A strict inequality implies the corresponding non-strict inequality.
ENNReal.ofReal_one
The extended non-negative real corresponding to the real number 1 is 1.
MeasureTheory.Measure.pi.instIsProbabilityMeasure
A finite product of probability measures is a probability measure.
Set.mem_ofPred_eq
Membership of an element in a set defined by a predicate is equivalent to the predicate holding for that element.
iff_true
A proposition is equivalent to True if and only if the proposition holds.
bpe_min_greedy_utility_one_eq_optimal
For any string, the greedy BPE utility for a single merge equals the optimal utility for a single merge.
iid_bpe_sharp_factor_bounds.2
The theoretical sharp approximation factor for BPE is strictly less than 1.
MeasureTheory.measure_univ
In any probability space, the measure of the entire space is 1.
ENNReal.toReal_one
Converting the extended non-negative real number 1 to a real number yields 1.
tendsto_const_nhds
A constant sequence converges to that constant value along any filter.

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 approximation probability tends to 1 for merge budget k = 1. -/theorem op_1604_iid_greedy_bpe_budget_one    (q : ℕ) (hq : 2 ≤ q) (p : Fin q → ℝ) (hp_pos : ∀ i, 0 < p i) (hp_sum : ∑ i, p i = 1)    (ε : ℝ) (hε : 0 < ε) :    Filter.Tendsto (fun N : ℕ => iid_greedy_bpe_approx_prob q p 1 N ε) Filter.atTop (nhds 1) := by  -- Each marginal of the i.i.d. product measure is a probability measure.  have hmarg : MeasureTheory.IsProbabilityMeasure      (∑ j, ENNReal.ofReal (p j) • MeasureTheory.Measure.dirac (j : Fin q)) := by    refine ⟨?_⟩    rw [MeasureTheory.Measure.coe_finsetSum]    simp only [Finset.sum_apply, MeasureTheory.Measure.smul_apply, smul_eq_mul]    simp only [MeasureTheory.Measure.dirac_apply, Set.indicator_of_mem, Set.mem_univ,      Pi.one_apply, mul_one]    rw [← ENNReal.ofReal_sum_of_nonneg (fun i _ => le_of_lt (hp_pos i)), hp_sum,      ENNReal.ofReal_one]  -- For budget k = 1 the approximating event is the whole space, so the probability is 1.  have hprob : ∀ N : ℕ, iid_greedy_bpe_approx_prob q p 1 N ε = 1 := by    intro N    haveI : MeasureTheory.IsProbabilityMeasure (iid_word_measure q N p) := by      rw [iid_word_measure]      exact MeasureTheory.Measure.pi.instIsProbabilityMeasure _    unfold iid_greedy_bpe_approx_prob    have huniv : {w : Fin N → Fin q |        (bpe_min_greedy_utility (List.ofFn fun i => (w i : ℕ)) 1 : ℝ) ≥          (iid_bpe_sharp_factor - ε) * (bpe_optimal_full_utility (List.ofFn fun i => (w i : ℕ)) 1 : ℝ)}        = Set.univ := by      ext w      simp only [Set.mem_ofPred_eq, Set.mem_univ, iff_true]      -- Greedy and optimal agree for one merge.      rw [bpe_min_greedy_utility_one_eq_optimal]      have hc : iid_bpe_sharp_factor - ε < 1 := by        have := iid_bpe_sharp_factor_bounds.2        linarith      have hu : (0:ℝ) ≤ (bpe_optimal_full_utility (List.ofFn fun i => (w i : ℕ)) 1 : ℝ) := by        positivity      nlinarith    rw [huniv, MeasureTheory.measure_univ]    exact ENNReal.toReal_one  simp only [hprob]  exact tendsto_const_nhds
See it in the graphDiscuss this resultChallenge it