AFTD Auto-Formalizing Theoretical Domains

bpe_greedy_run_length_lower_bound

theoremverified

Applying k greedy full BPE merges reduces the string length by at most a factor of 2^k: if bpe_greedy_run k s t, then s.length ≤ 2^k * t.length.

Statement

theorem bpe_greedy_run_length_lower_bound (k : ℕ) (s t : List ℕ) (h : bpe_greedy_run k s t) : s.length ≤ 2^k * t.length
Source
step towards op_1533_iid_binary_greedy_bpe_universal_rate
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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…
  • bpe_pair_countThe number of occurrences of the ordered symbol pair replaced by the left-to-right nonoverlapping full merge.
  • bpe_full_mergeThe string obtained by scanning left to right and replacing every available nonoverlapping occurrence of the selected pair with the given…
  • bpe_greedy_step_withA greedy full Byte-Pair Encoding merge step with fresh symbol z: either no adjacent pair occurs with positive count in string s and t = s,…
  • bpe_max_pair_countThe largest nonoverlapping full-merge pair count among adjacent pairs of the current string, with maximum zero for a string shorter than…

The proof, explained

The theorem is proved by induction on the number of greedy BPE steps k. The base case k = 0 is immediate because zero steps leave the string unchanged. In the induction step, a run of length k + 1 decomposes into a k-step run from s to an intermediate string u, followed by a single greedy step from u to t. By the induction hypothesis, s.length ≤ 2^k * u.length, and a helper lemma establishes that each greedy step reduces length by at most half (u.length ≤ 2 * t.length) because full pair merges replace disjoint pairs with single tokens. Combining these inequalities and simplifying powers of 2 completes the proof.

  1. For empty and singleton lists, merging leaves the string unchanged, so its length is at most twice the merged length.

    We apply the functional induction principle `bpe_full_merge.induct` on the list `s`. For the empty list `[]`, `bpe_full_merge.eq_1` simplifies the merged list to `[]`, giving `0 ≤ 2 * 0`. For a singleton `[head]`, `bpe_full_merge.eq_2` simplifies the merged list to `[head]`, giving `1 ≤ 2 * 1`. Both base cases close by simplification.

    lines 3–7

    uses bpe_full_merge.induct, bpe_full_merge.eq_1, bpe_full_merge.eq_2

      induction s using bpe_full_merge.induct a b with
      | case1 =>
        simp [bpe_full_merge.eq_1]
      | case2 head =>
        simp [bpe_full_merge.eq_2]
  2. When the string starts with the matching pair (a, b), the length bound holds by the induction hypothesis on the remaining tail.

    When `x = a` and `y = b`, rewriting with `bpe_full_merge.eq_3` and evaluating the `if` branch with `if_pos` shows that the first two elements merge into `z :: bpe_full_merge a b z xs`. Prepending two elements adds 2 to the length of `xs`, while the merged list gains 1 element. Simplifying list lengths with `List.length_cons` reduces the inequality to `xs.length + 2 ≤ 2 * ((bpe_full_merge a b z xs).length + 1)`, which follows from the induction hypothesis `xs.length ≤ 2 * (bpe_full_merge a b z xs).length` by linear arithmetic (`omega`).

    lines 8–14

    uses bpe_full_merge.eq_3, if_pos, List.length_cons

      | case3 x y xs hxy ih =>
        rw [bpe_full_merge.eq_3]
        have : (if x = a ∧ y = b then z :: bpe_full_merge a b z xs else x :: bpe_full_merge a b z (y :: xs)) =
          z :: bpe_full_merge a b z xs := if_pos hxy
        rw [this]
        simp only [List.length_cons] at *
        omega
  3. When the string starts with a pair different from (a, b), the first element is retained and the length bound holds by the induction hypothesis on the rest of the list.

    When `¬(x = a ∧ y = b)`, rewriting with `bpe_full_merge.eq_3` and evaluating the conditional with `if_neg` shows that `x` is kept and merging continues on `y :: xs`. After simplifying lengths with `List.length_cons`, the resulting inequality `xs.length + 2 ≤ 2 * ((bpe_full_merge a b z (y :: xs)).length + 1)` follows from the induction hypothesis `xs.length + 1 ≤ 2 * (bpe_full_merge a b z (y :: xs)).length` via linear arithmetic (`omega`).

    lines 15–21

    uses bpe_full_merge.eq_3, if_neg, List.length_cons

      | case4 x y xs hxy ih =>
        rw [bpe_full_merge.eq_3]
        have : (if x = a ∧ y = b then z :: bpe_full_merge a b z xs else x :: bpe_full_merge a b z (y :: xs)) =
          x :: bpe_full_merge a b z (y :: xs) := if_neg hxy
        rw [this]
        simp only [List.length_cons] at *
        omega
  4. A single greedy BPE step reduces the length of the string by at most a factor of 2.

    Case analysis on `bpe_greedy_step_with` yields two cases: either no pairs occur in `s` and `t = s`, in which case `t.length ≤ 2 * t.length` holds by linear arithmetic (`omega`); or the step performs a full merge of the most frequent pair `(a, b)`, in which case the claim follows directly from the previous lemma `bpe_greedy_run_length_lower_bound_full_merge_le`.

    lines 23–27

    uses bpe_greedy_run_length_lower_bound_full_merge_le

    lemma bpe_greedy_run_length_lower_bound_step_with_le (z : ℕ) (s t : List ℕ)
        (h : bpe_greedy_step_with z s t) : s.length ≤ 2 * t.length := by
      rcases h with ⟨-, rfl⟩ | ⟨a, b, -, -, rfl⟩
      · omega
      · exact bpe_greedy_run_length_lower_bound_full_merge_le a b z s
  5. For k = 0, zero greedy steps leave the string unchanged, so the length bound holds trivially.

    We induct on `k`, generalizing over `s` and `t`. For the base case `k = 0`, `bpe_greedy_run.eq_1` shows that `bpe_greedy_run 0 s t` means `s = t`. Substituting `s = t` simplifies the goal to `s.length ≤ 2^0 * s.length = s.length`, which holds trivially.

    lines 31–35

    uses bpe_greedy_run.eq_1

      induction k generalizing s t with
      | zero =>
        rw [bpe_greedy_run.eq_1] at h
        subst h
        simp
  6. For k + 1, decomposing the run provides an intermediate string u with bounds on |s| in terms of |u| and |u| in terms of |t|.

    By `bpe_greedy_run.eq_2`, a `(k + 1)`-step run from `s` to `t` decomposes into a `k`-step run from `s` to some intermediate list `u` and a single greedy step from `u` to `t`. The induction hypothesis applies to `s` and `u` to give `s.length ≤ 2^k * u.length`, and `bpe_greedy_run_length_lower_bound_step_with_le` applied to the final step gives `u.length ≤ 2 * t.length`.

    lines 36–40

    uses bpe_greedy_run.eq_2, bpe_greedy_run_length_lower_bound_step_with_le

      | succ k ih =>
        rw [bpe_greedy_run.eq_2] at h
        rcases h with ⟨u, hsu, hut⟩
        have h1 := ih s u hsu
        have h2 := bpe_greedy_run_length_lower_bound_step_with_le (k + 2) u t hut
  7. Chaining the inequalities yields s.length ≤ 2^(k + 1) * t.length.

    Multiplying `u.length ≤ 2 * t.length` on the left by `2^k` using `Nat.mul_le_mul_left` yields `2^k * u.length ≤ 2^k * (2 * t.length)`. Transitivity with `s.length ≤ 2^k * u.length` and simplifying `2^k * (2 * t.length) = 2^(k + 1) * t.length` via ring arithmetic completes the induction step.

    lines 41–43

    uses Nat.mul_le_mul_left

        calc s.length ≤ 2^k * u.length := h1
        _ ≤ 2^k * (2 * t.length) := Nat.mul_le_mul_left _ h2
        _ = 2^(k + 1) * t.length := by ring
bpe_full_merge.induct
Induction principle for `bpe_full_merge`: to prove a property of a list under merging adjacent pairs (a, b), it suffices to prove it for the empty list, singleton lists, a list whose head matches (a, b), and a list whose head does not match (a, b).
bpe_full_merge.eq_1
Merging in the empty list leaves it empty: `bpe_full_merge a b z [] = []`.
bpe_full_merge.eq_2
Merging in a singleton list leaves it unchanged: `bpe_full_merge a b z [head] = [head]`.
bpe_full_merge.eq_3
For a list with at least two elements, `bpe_full_merge` merges the first two if they equal (a, b) and recurses on the tail, or keeps the head and recurses on the rest otherwise.
if_pos
If a condition `c` holds, `if c then t else e` simplifies to `t`.
if_neg
If a condition `c` does not hold, `if c then t else e` simplifies to `e`.
List.length_cons
The length of `a :: as` is `as.length + 1`.
bpe_greedy_run_length_lower_bound_full_merge_le
A full BPE merge of pair (a, b) replaces non-overlapping pairs with single tokens, reducing the string length by at most half: `s.length ≤ 2 * (bpe_full_merge a b z s).length`.
bpe_greedy_run_length_lower_bound_step_with_le
A single greedy BPE step reduces string length by at most half: `s.length ≤ 2 * t.length`.
bpe_greedy_run.eq_1
A 0-step greedy BPE run leaves the string unchanged: `bpe_greedy_run 0 s t` is equivalent to `s = t`.
bpe_greedy_run.eq_2
A (k + 1)-step greedy BPE run consists of a k-step run from `s` to an intermediate string `u`, followed by a greedy step from `u` to `t`.
Nat.mul_le_mul_left
Multiplication on the left by a natural number preserves ordering: if `n ≤ m`, then `k * n ≤ k * m`.

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

lemma bpe_greedy_run_length_lower_bound_full_merge_le (a b z : ℕ) (s : List ℕ) :    s.length ≤ 2 * (bpe_full_merge a b z s).length := by  induction s using bpe_full_merge.induct a b with  | case1 =>    simp [bpe_full_merge.eq_1]  | case2 head =>    simp [bpe_full_merge.eq_2]  | case3 x y xs hxy ih =>    rw [bpe_full_merge.eq_3]    have : (if x = a ∧ y = b then z :: bpe_full_merge a b z xs else x :: bpe_full_merge a b z (y :: xs)) =      z :: bpe_full_merge a b z xs := if_pos hxy    rw [this]    simp only [List.length_cons] at *    omega  | case4 x y xs hxy ih =>    rw [bpe_full_merge.eq_3]    have : (if x = a ∧ y = b then z :: bpe_full_merge a b z xs else x :: bpe_full_merge a b z (y :: xs)) =      x :: bpe_full_merge a b z (y :: xs) := if_neg hxy    rw [this]    simp only [List.length_cons] at *    omegalemma bpe_greedy_run_length_lower_bound_step_with_le (z : ℕ) (s t : List ℕ)    (h : bpe_greedy_step_with z s t) : s.length ≤ 2 * t.length := by  rcases h with ⟨-, rfl⟩ | ⟨a, b, -, -, rfl⟩  · omega  · exact bpe_greedy_run_length_lower_bound_full_merge_le a b z s/-- Applying k greedy full BPE merges reduces the string length by at most a factor of 2^k, because each non-overlapping pair merge reduces string length by at most half. -/theorem bpe_greedy_run_length_lower_bound (k : ℕ) (s t : List ℕ) (h : bpe_greedy_run k s t) : s.length ≤ 2^k * t.length := by  induction k generalizing s t with  | zero =>    rw [bpe_greedy_run.eq_1] at h    subst h    simp  | succ k ih =>    rw [bpe_greedy_run.eq_2] at h    rcases h with ⟨u, hsu, hut⟩    have h1 := ih s u hsu    have h2 := bpe_greedy_run_length_lower_bound_step_with_le (k + 2) u t hut    calc s.length ≤ 2^k * u.length := h1    _ ≤ 2^k * (2 * t.length) := Nat.mul_le_mul_left _ h2    _ = 2^(k + 1) * t.length := by ring
See it in the graphDiscuss this resultChallenge it