bpe_greedy_run_length_lower_bound
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.
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.
uses
bpe_full_merge.induct,bpe_full_merge.eq_1,bpe_full_merge.eq_2induction s using bpe_full_merge.induct a b with | case1 => simp [bpe_full_merge.eq_1] | case2 head => simp [bpe_full_merge.eq_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`).
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 * omegaWhen 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`).
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 * omegaA 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`.
uses
bpe_greedy_run_length_lower_bound_full_merge_lelemma 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
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.
uses
bpe_greedy_run.eq_1induction k generalizing s t with | zero => rw [bpe_greedy_run.eq_1] at h subst h simp
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`.
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 hutChaining 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.
uses
Nat.mul_le_mul_leftcalc 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`.
- Presburger linear arithmetic in the inductive cases of the helper lemma is discharged by `omega`, and polynomial arithmetic on powers of 2 in the induction step is discharged by `ring`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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