bpe_greedy_steps_length_le
Applying k greedy full byte-pair merge steps to a string produces an output string of length at most the input string length.
Statement
theorem bpe_greedy_steps_length_le (k : ℕ) (s t : List ℕ) (h : bpe_steps bpe_greedy_step k s t) : t.length ≤ s.length- Source
- arXiv:2611.08671
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- bpe_stepsExactly k applications of the specified binary relation connect the input and output strings.
- bpe_greedy_stepA greedy full-merge step selects any most frequent adjacent pair and a fresh symbol; a string without adjacent pairs remains unchanged.
- bpe_greedy_step_length_leAny greedy full byte-pair merge step produces an output string of length at most the input string length.
Read back from the Lean
For all natural numbers $k$ and all lists of natural numbers $s$ and $t$, if $t$ can be reached from $s$ in $k$ steps of the greedy Byte Pair Encoding relation (bpe_greedy_step), then the length of $t$ is less than or equal to the length of $s$.
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
The proof proceeds by induction on the number of steps $k$, generalizing over the initial string $s$. In the base case $k = 0$, taking zero merge steps leaves the string unchanged ($s = t$), so the lengths are trivially equal. In the inductive step $k + 1$, the sequence decomposes into an initial greedy step $s \to u$ followed by $k$ steps $u \to^* t$; chaining the single-step bound $|u| \le |s|$ with the induction hypothesis $|t| \le |u|$ via transitivity of $\le$ completes the proof.
For the base case $k = 0$, $t.\text{length} \le s.\text{length}$ holds.
We proceed by induction on $k$, generalizing over the initial string $s$. In the base case $k = 0$, simplifying hypothesis $h$ with the definition of `bpe_steps` yields $s = t$. Substituting $t$ with $s$, the goal becomes $s.\text{length} \le s.\text{length}$, which holds by reflexivity of $\le$ (`le_rfl`).
uses
le_rflinduction k generalizing s with | zero => simp only [bpe_steps] at h subst h exact le_rfl
In the inductive step $k + 1$, $t.\text{length} \le s.\text{length}$ holds.
For the inductive step $k + 1$, the hypothesis that $s$ reaches $t$ in $k + 1$ steps means, by definition of `bpe_steps`, that there is an intermediate string $u$ such that $s$ takes one greedy step to $u$ and $u$ takes $k$ greedy steps to $t$. By `bpe_greedy_step_length_le`, the first step does not increase length ($u.\text{length} \le s.\text{length}$). By the induction hypothesis applied to $u$, the remaining $k$ steps satisfy $t.\text{length} \le u.\text{length}$. Chaining these two inequalities via transitivity of $\le$ (`le_trans`) completes the step.
uses
bpe_greedy_step_length_le,le_trans| succ k ih => obtain ⟨u, hsu, hut⟩ := h have h1 := bpe_greedy_step_length_le s u hsu have h2 := ih u hut exact le_trans h2 h1
le_rfl- Inequality in any preorder is reflexive: $a \le a$ for any $a$.
bpe_greedy_step_length_le- A single greedy byte-pair merge step never increases the length of the string: if $s$ steps to $t$, then $t.\text{length} \le s.\text{length}$.
le_trans- Inequality in any preorder is transitive: if $a \le b$ and $b \le c$, then $a \le c$.
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.
/-- Any sequence of k greedy BPE merge steps produces an output string of length at most the initial string length. -/theorem bpe_greedy_steps_length_le (k : ℕ) (s t : List ℕ) (h : bpe_steps bpe_greedy_step k s t) : t.length ≤ s.length := by induction k generalizing s with | zero => simp only [bpe_steps] at h subst h exact le_rfl | succ k ih => obtain ⟨u, hsu, hut⟩ := h have h1 := bpe_greedy_step_length_le s u hsu have h2 := ih u hut exact le_trans h2 h1