bpe_min_greedy_utility_one_eq_optimal
For any string s and merge budget k = 1, the minimum reduction in length achieved by a greedy full-merge step equals the optimal reduction achievable by any full-merge step.
Statement
theorem bpe_min_greedy_utility_one_eq_optimal (s : List ℕ) :
bpe_min_greedy_utility s 1 = bpe_optimal_full_utility s 1- Source
- arXiv:2411.08671 Greedy Byte-Pair Encoding Achieves at Least 0.361 of the Optimal Compression, line 811
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- 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.
- 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_full_stepA full Byte-Pair Encoding merge step: either the string remains unchanged, or all nonoverlapping occurrences of some pair are replaced…
- bpe_stepsExactly k applications of the specified binary relation connect the input and output strings.
- 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…
- 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_full_mergeThe string obtained by scanning left to right and replacing every available nonoverlapping occurrence of the selected pair with the given…
- bpe_pair_countThe number of occurrences of the ordered symbol pair replaced by the left-to-right nonoverlapping full merge.
- Used by 1
- op_1604_iid_greedy_bpe_budget_oneOpen Problem OP-1604 (budget k = 1 case): For a merge budget of k = 1, every alphabet size q ≥ 2, every strictly positive probability…
Read back from the Lean
For every list of natural numbers $s$, the minimum greedy BPE utility after 1 step equals the optimal full BPE utility after 1 step (that is, bpe_min_greedy_utility s 1 = bpe_optimal_full_utility s 1).
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 utility is the infimum length reduction over all greedy steps, while optimal full utility is the supremum over all full steps. The proof shows that merging any pair (a, b) reduces the string length by exactly its occurrence count in s, so every greedy step reduces the length by exactly bpe_max_pair_count s, and every full step reduces it by at most bpe_max_pair_count s. Since both a greedy step and a full step achieving this maximal reduction always exist, the set of greedy reductions is {bpe_max_pair_count s} and the set of full reductions has supremum bpe_max_pair_count s. Both the minimum greedy utility and the optimal full utility therefore equal bpe_max_pair_count s, establishing their equality.
A full merge of a pair (a, b) replacing it with z never increases the length of s: (bpe_full_merge a b z s).length ≤ s.length.
We induct on s using the induction principle tailored to bpe_full_merge. The base cases of the empty list and singletons leave the list untouched. When the head pair equals (a, b), the pair is replaced by a single token z, so the length becomes 1 + length of the merged tail; by the induction hypothesis, this is at most 1 + length of tail ≤ 2 + length of tail. When the head pair does not match, the first element is preserved and the induction hypothesis applies to the rest of the list. In both inductive branches, linear arithmetic (omega) closes the inequality.
uses
bpe_full_merge.induct,List.length_consrefine bpe_full_merge.induct a b (fun s => (bpe_full_merge a b z s).length ≤ s.length) ?_ ?_ ?_ ?_ s · simp [bpe_full_merge] · intro x simp [bpe_full_merge] · intro x y xs hxy ih have hm : bpe_full_merge a b z (x :: y :: xs) = z :: bpe_full_merge a b z xs := by simp [bpe_full_merge, hxy] rw [hm] simp only [List.length_cons] at ih ⊢ omega · intro x y xs hxy ih have hm : bpe_full_merge a b z (x :: y :: xs) = x :: bpe_full_merge a b z (y :: xs) := by simp [bpe_full_merge, hxy] rw [hm] simp only [List.length_cons] at ih ⊢ omega
The reduction in length after merging (a, b) into z equals the count of occurrences of (a, b) in s: s.length - (bpe_full_merge a b z s).length = bpe_pair_count a b s.
By structural induction on s following bpe_full_merge, base cases are trivial as both sides equal 0. When the first two elements equal (a, b), list length drops by 2 and gains 1 (for z), increasing the length reduction by 1; together with the induction hypothesis and the previous length bound, this matches 1 + bpe_pair_count a b xs. When the first two elements do not match, the head is kept, the length reduction is unchanged, and it matches the pair count on the tail.
uses
bpe_full_merge.induct,List.length_cons,bpe_min_greedy_utility_one_eq_optimal_merge_length_lerefine bpe_full_merge.induct a b (fun s => s.length - (bpe_full_merge a b z s).length = bpe_pair_count a b s) ?_ ?_ ?_ ?_ s · simp [bpe_full_merge, bpe_pair_count] · intro x simp [bpe_full_merge, bpe_pair_count] · intro x y xs hxy ih have hm : bpe_full_merge a b z (x :: y :: xs) = z :: bpe_full_merge a b z xs := by simp [bpe_full_merge, hxy] have hc : bpe_pair_count a b (x :: y :: xs) = 1 + bpe_pair_count a b xs := by simp [bpe_pair_count, hxy] rw [hm, hc] simp only [List.length_cons] at ih ⊢ have hle := bpe_min_greedy_utility_one_eq_optimal_merge_length_le a b z xs omega · intro x y xs hxy ih have hm : bpe_full_merge a b z (x :: y :: xs) = x :: bpe_full_merge a b z (y :: xs) := by simp [bpe_full_merge, hxy] have hc : bpe_pair_count a b (x :: y :: xs) = bpe_pair_count a b (y :: xs) := by simp [bpe_pair_count, hxy] rw [hm, hc] simp only [List.length_cons] at ih ⊢ have hle := bpe_min_greedy_utility_one_eq_optimal_merge_length_le a b z (y :: xs) simp only [List.length_cons] at hle omega
If the pair count of (a, b) in s is strictly positive, then (a, b) occurs as an adjacent pair in s.zip s.tail.
We induct on s using the induction principle for bpe_pair_count. The base cases have pair count 0, contradicting the positive hypothesis. If the leading pair matches (a, b), then (a, b) is the head of s.zip s.tail. If the leading pair does not match, the positive count originates in the tail y :: xs, and by the induction hypothesis (a, b) belongs to (y :: xs).zip xs, which is a sublist of the zip.
uses
bpe_pair_count.induct,List.zip_cons_cons,List.tail_cons,List.mem_cons_of_memrefine bpe_pair_count.induct a b (fun s => 0 < bpe_pair_count a b s → (a, b) ∈ s.zip s.tail) ?_ ?_ ?_ ?_ s h · simp [bpe_pair_count] · intro x simp [bpe_pair_count] · intro x y xs hxy _ _ simp [hxy] · intro x y xs hxy ih hpos have hc : bpe_pair_count a b (x :: y :: xs) = bpe_pair_count a b (y :: xs) := by simp [bpe_pair_count, hxy] rw [hc] at hpos have hmem := ih hpos simp only [List.zip_cons_cons, List.tail_cons] exact List.mem_cons_of_mem _ hmem
The pair count of any pair (a, b) in s is bounded by the maximum pair count: bpe_pair_count a b s ≤ bpe_max_pair_count s.
If the count is 0, the inequality is trivial because natural numbers are non-negative. If the count is positive, the pair belongs to s.zip s.tail, hence to its finite set conversion. Because bpe_max_pair_count s is the supremum over this finite set, Finset.le_sup immediately shows the count is bounded by the supremum.
uses
Nat.eq_zero_or_pos,Nat.zero_le,bpe_min_greedy_utility_one_eq_optimal_pair_count_pos_mem_zip,Finset.le_suprcases Nat.eq_zero_or_pos (bpe_pair_count a b s) with h0 | hpos · rw [h0]; exact Nat.zero_le _ · have hmem := bpe_min_greedy_utility_one_eq_optimal_pair_count_pos_mem_zip a b s hpos have hle := Finset.le_sup (s := (s.zip s.tail).toFinset) (f := fun p : ℕ × ℕ => bpe_pair_count p.1 p.2 s) (by simpa using hmem) simpa [bpe_max_pair_count] using hle
If the maximum pair count in s is positive, there exists a pair (a, b) whose occurrence count equals bpe_max_pair_count s.
If the finite set of adjacent pairs were empty, the supremum would be 0, contradicting the assumption that the maximum is strictly positive. Thus the set is nonempty, and by Finset.exists_mem_eq_sup, the supremum on any nonempty finite set is attained at some pair p = (a, b).
uses
Finset.nonempty_iff_ne_empty,Finset.sup_empty,Nat.lt_irrefl,Finset.exists_mem_eq_suphave hne : (s.zip s.tail).toFinset.Nonempty := by rw [Finset.nonempty_iff_ne_empty] intro he rw [bpe_max_pair_count, he, Finset.sup_empty] at h exact absurd h (Nat.lt_irrefl 0) obtain ⟨p, hp, hsup⟩ := Finset.exists_mem_eq_sup _ hne (fun p : ℕ × ℕ => bpe_pair_count p.1 p.2 s) exact ⟨p.1, p.2, by simpa [bpe_max_pair_count] using hsup.symm⟩
There exists a fresh token z not appearing in s.
We choose z = s.sum + 1. Any element of s is at most s.sum by List.le_sum_of_mem, so z cannot belong to s.
uses
List.le_sum_of_memrefine ⟨s.sum + 1, ?_⟩ intro hz have hle := List.le_sum_of_mem hz omega
Any single greedy step from s to t reduces the list length by exactly bpe_max_pair_count s.
By definition of bpe_greedy_step, either the maximum pair count is 0 and t = s (yielding length reduction 0), or a pair (a, b) with count equal to the maximum is merged. In the merge case, the length reduction equals the count of (a, b), which equals bpe_max_pair_count s.
uses
bpe_min_greedy_utility_one_eq_optimal_merge_length_subrcases h with ⟨hmax, rfl⟩ | ⟨a, b, z, hpos, hcount, hz, rfl⟩ · simp [hmax] · rw [bpe_min_greedy_utility_one_eq_optimal_merge_length_sub, hcount]
Any single full step from s to t reduces the list length by at most bpe_max_pair_count s.
By definition of bpe_full_step, either s = t (giving length reduction 0 ≤ bpe_max_pair_count s), or some pair (a, b) is merged, in which case the reduction equals bpe_pair_count a b s, which is at most bpe_max_pair_count s.
uses
bpe_min_greedy_utility_one_eq_optimal_merge_length_sub,bpe_min_greedy_utility_one_eq_optimal_pair_count_le_maxrcases h with rfl | ⟨a, b, z, hz, rfl⟩ · simp · rw [bpe_min_greedy_utility_one_eq_optimal_merge_length_sub] exact bpe_min_greedy_utility_one_eq_optimal_pair_count_le_max a b s
There exists a valid greedy step from s whose length reduction equals bpe_max_pair_count s.
If the maximum count is 0, the identity step t = s is a valid greedy step achieving reduction 0. If the maximum count is positive, we select a pair (a, b) achieving the maximum count and a fresh symbol z; merging (a, b) into z yields a valid greedy step with length reduction equal to bpe_max_pair_count s.
uses
Nat.eq_zero_or_pos,Or.inl,Or.inr,bpe_min_greedy_utility_one_eq_optimal_exists_pair_eq_max,bpe_min_greedy_utility_one_eq_optimal_exists_fresh,bpe_min_greedy_utility_one_eq_optimal_merge_length_subrcases Nat.eq_zero_or_pos (bpe_max_pair_count s) with h0 | hpos · refine ⟨s, Or.inl ⟨h0, rfl⟩, ?_⟩ simp [h0] · obtain ⟨a, b, hab⟩ := bpe_min_greedy_utility_one_eq_optimal_exists_pair_eq_max s hpos obtain ⟨z, hz⟩ := bpe_min_greedy_utility_one_eq_optimal_exists_fresh s refine ⟨bpe_full_merge a b z s, Or.inr ⟨a, b, z, hpos, hab, hz, rfl⟩, ?_⟩ rw [bpe_min_greedy_utility_one_eq_optimal_merge_length_sub, hab]
There exists a valid full step from s whose length reduction equals bpe_max_pair_count s.
If the maximum count is 0, t = s is a valid full step with reduction 0. If positive, merging the maximizing pair (a, b) using a fresh symbol z gives a valid full step whose reduction equals bpe_max_pair_count s.
uses
Nat.eq_zero_or_pos,Or.inl,Or.inr,bpe_min_greedy_utility_one_eq_optimal_exists_pair_eq_max,bpe_min_greedy_utility_one_eq_optimal_exists_fresh,bpe_min_greedy_utility_one_eq_optimal_merge_length_subrcases Nat.eq_zero_or_pos (bpe_max_pair_count s) with h0 | hpos · refine ⟨s, Or.inl rfl, ?_⟩ simp [h0] · obtain ⟨a, b, hab⟩ := bpe_min_greedy_utility_one_eq_optimal_exists_pair_eq_max s hpos obtain ⟨z, hz⟩ := bpe_min_greedy_utility_one_eq_optimal_exists_fresh s refine ⟨bpe_full_merge a b z s, Or.inr ⟨a, b, z, hz, rfl⟩, ?_⟩ rw [bpe_min_greedy_utility_one_eq_optimal_merge_length_sub, hab]
For budget k = 1, greedy utility and optimal full utility simplify to infimum and supremum over 1-step length reductions.
Unfolding bpe_min_greedy_utility and bpe_optimal_full_utility, the multi-step relation bpe_steps R 1 s t simplifies to the single transition R s t. Applying set extensionality rewrites the sets of candidate utilities to single-step length reductions.
classical unfold bpe_min_greedy_utility bpe_optimal_full_utility have hG : {u : ℕ | ∃ t, bpe_steps bpe_greedy_step 1 s t ∧ u = s.length - t.length} = {u : ℕ | ∃ t, bpe_greedy_step s t ∧ u = s.length - t.length} := by ext u; simp [bpe_steps] have hF : {u : ℕ | ∃ t, bpe_steps bpe_full_step 1 s t ∧ u = s.length - t.length} = {u : ℕ | ∃ t, bpe_full_step s t ∧ u = s.length - t.length} := by ext u; simp [bpe_steps] rw [hG, hF]
The infimum of 1-step greedy length reductions equals bpe_max_pair_count s.
The set of greedy reductions is nonempty because a greedy step always exists. For any nonempty set of natural numbers, its infimum belongs to the set (Nat.sInf_mem). Since every greedy step yields reduction exactly bpe_max_pair_count s, the infimum must equal bpe_max_pair_count s.
uses
bpe_min_greedy_utility_one_eq_optimal_exists_greedy_step,Nat.sInf_mem,Set.mem_ofPred_eq,bpe_min_greedy_utility_one_eq_optimal_greedy_sub_eq_maxhave hinf : sInf {u : ℕ | ∃ t, bpe_greedy_step s t ∧ u = s.length - t.length} = bpe_max_pair_count s := by have hne : ({u : ℕ | ∃ t, bpe_greedy_step s t ∧ u = s.length - t.length} : Set ℕ).Nonempty := by obtain ⟨t, ht, hut⟩ := bpe_min_greedy_utility_one_eq_optimal_exists_greedy_step s exact ⟨_, t, ht, hut.symm⟩ have hmem := Nat.sInf_mem hne simp only [Set.mem_ofPred_eq] at hmem obtain ⟨t, ht, heq⟩ := hmem rw [heq] exact bpe_min_greedy_utility_one_eq_optimal_greedy_sub_eq_max s t ht
The supremum of 1-step full length reductions equals bpe_max_pair_count s.
A full step achieving length reduction bpe_max_pair_count s exists, so this value belongs to the set. Moreover, every full step achieves reduction at most bpe_max_pair_count s, making it an upper bound. By antisymmetry of ≤ and the definition of supremum on bounded sets of natural numbers, the supremum equals bpe_max_pair_count s.
uses
bpe_min_greedy_utility_one_eq_optimal_exists_full_step,bpe_min_greedy_utility_one_eq_optimal_full_sub_le_max,le_antisymm,Nat.sSup_def,Nat.find_min',Nat.find_spechave hsup : sSup {u : ℕ | ∃ t, bpe_full_step s t ∧ u = s.length - t.length} = bpe_max_pair_count s := by have hMmem : bpe_max_pair_count s ∈ {u : ℕ | ∃ t, bpe_full_step s t ∧ u = s.length - t.length} := by obtain ⟨t, ht, hut⟩ := bpe_min_greedy_utility_one_eq_optimal_exists_full_step s exact ⟨t, ht, hut.symm⟩ have hbdd : ∃ n : ℕ, ∀ a ∈ {u : ℕ | ∃ t, bpe_full_step s t ∧ u = s.length - t.length}, a ≤ n := by refine ⟨bpe_max_pair_count s, ?_⟩ intro a ha obtain ⟨t, ht, rfl⟩ := ha exact bpe_min_greedy_utility_one_eq_optimal_full_sub_le_max s t ht apply le_antisymm · rw [Nat.sSup_def hbdd] exact Nat.find_min' hbdd (fun a ha => by obtain ⟨t, ht, rfl⟩ := ha exact bpe_min_greedy_utility_one_eq_optimal_full_sub_le_max s t ht) · rw [Nat.sSup_def hbdd] exact Nat.find_spec hbdd _ hMmem
bpe_min_greedy_utility s 1 = bpe_optimal_full_utility s 1.
Both utilities have been shown to equal bpe_max_pair_count s, so rewriting with both equalities establishes that they are equal.
rw [hinf, hsup]
bpe_full_merge.induct- Induction principle for bpe_full_merge: to prove a property of lists, it suffices to check the empty list, singletons, matching pairs followed by a list, and non-matching pairs followed by a list.
List.length_cons- The length of a list with an element prepended is one more than the length of the tail.
bpe_min_greedy_utility_one_eq_optimal_merge_length_le- A full merge of any pair never increases the length of the list.
bpe_pair_count.induct- Induction principle for bpe_pair_count: to prove a property of lists, it suffices to check the empty list, singletons, matching pairs followed by a list, and non-matching pairs followed by a list.
List.zip_cons_cons- Zipping two non-empty lists pairs their heads and zips their tails.
List.tail_cons- The tail of a cons list is the underlying list.
List.mem_cons_of_mem- If an element belongs to a list, it belongs to that list with any element prepended.
Nat.eq_zero_or_pos- Every natural number is either zero or strictly positive.
Nat.zero_le- Zero is less than or equal to any natural number.
bpe_min_greedy_utility_one_eq_optimal_pair_count_pos_mem_zip- If a pair has a positive count in s, it occurs as an adjacent pair in s.zip s.tail.
Finset.le_sup- Any element in a finite set evaluates under a function to at most the supremum over that set.
Finset.nonempty_iff_ne_empty- A finite set is nonempty if and only if it is distinct from the empty set.
Finset.sup_empty- The supremum of any function over the empty set is the bottom element.
Nat.lt_irrefl- Strict inequality on natural numbers is irreflexive: no number is strictly less than itself.
Finset.exists_mem_eq_sup- On any nonempty finite set, the supremum of a function is attained at some element of the set.
List.le_sum_of_mem- Any element of a list of natural numbers is less than or equal to the sum of the list.
bpe_min_greedy_utility_one_eq_optimal_merge_length_sub- The reduction in list length after a full merge of pair (a, b) equals the pair count of (a, b) in s.
bpe_min_greedy_utility_one_eq_optimal_pair_count_le_max- The pair count of any pair is at most the maximum pair count in the list.
Or.inl- Constructs a proof of a disjunction from a proof of its left disjunct.
Or.inr- Constructs a proof of a disjunction from a proof of its right disjunct.
bpe_min_greedy_utility_one_eq_optimal_exists_pair_eq_max- If the maximum pair count is positive, there exists a pair whose count equals the maximum.
bpe_min_greedy_utility_one_eq_optimal_exists_fresh- For any list of natural numbers, there exists a natural number not occurring in the list.
bpe_min_greedy_utility_one_eq_optimal_exists_greedy_step- There exists a reachable greedy step whose length reduction equals the maximum pair count.
bpe_min_greedy_utility_one_eq_optimal_exists_full_step- There exists a reachable full step whose length reduction equals the maximum pair count.
Nat.sInf_mem- The infimum of any nonempty set of natural numbers belongs to the set.
Set.mem_ofPred_eq- Membership in a set-builder comprehension is equivalent to the defining predicate.
bpe_min_greedy_utility_one_eq_optimal_greedy_sub_eq_max- Every greedy step reduces the list length by exactly the maximum pair count.
bpe_min_greedy_utility_one_eq_optimal_full_sub_le_max- Every full step reduces the list length by at most the maximum pair count.
le_antisymm- Two elements are equal if each is less than or equal to the other.
Nat.sSup_def- The supremum of a bounded set of natural numbers equals the least natural number satisfying the upper bound predicate.
Nat.find_min'- The least natural number satisfying a predicate is less than or equal to any witness satisfying the predicate.
Nat.find_spec- The least natural number chosen by Nat.find satisfies the predicate.
- On Set ℕ, sSup is defined using the least-number principle Nat.find to find the least upper bound, which requires an explicit witness that an upper bound exists.
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.
private lemma bpe_min_greedy_utility_one_eq_optimal_merge_length_le (a b z : ℕ) (s : List ℕ) : (bpe_full_merge a b z s).length ≤ s.length := by refine bpe_full_merge.induct a b (fun s => (bpe_full_merge a b z s).length ≤ s.length) ?_ ?_ ?_ ?_ s · simp [bpe_full_merge] · intro x simp [bpe_full_merge] · intro x y xs hxy ih have hm : bpe_full_merge a b z (x :: y :: xs) = z :: bpe_full_merge a b z xs := by simp [bpe_full_merge, hxy] rw [hm] simp only [List.length_cons] at ih ⊢ omega · intro x y xs hxy ih have hm : bpe_full_merge a b z (x :: y :: xs) = x :: bpe_full_merge a b z (y :: xs) := by simp [bpe_full_merge, hxy] rw [hm] simp only [List.length_cons] at ih ⊢ omegaprivate lemma bpe_min_greedy_utility_one_eq_optimal_merge_length_sub (a b z : ℕ) (s : List ℕ) : s.length - (bpe_full_merge a b z s).length = bpe_pair_count a b s := by refine bpe_full_merge.induct a b (fun s => s.length - (bpe_full_merge a b z s).length = bpe_pair_count a b s) ?_ ?_ ?_ ?_ s · simp [bpe_full_merge, bpe_pair_count] · intro x simp [bpe_full_merge, bpe_pair_count] · intro x y xs hxy ih have hm : bpe_full_merge a b z (x :: y :: xs) = z :: bpe_full_merge a b z xs := by simp [bpe_full_merge, hxy] have hc : bpe_pair_count a b (x :: y :: xs) = 1 + bpe_pair_count a b xs := by simp [bpe_pair_count, hxy] rw [hm, hc] simp only [List.length_cons] at ih ⊢ have hle := bpe_min_greedy_utility_one_eq_optimal_merge_length_le a b z xs omega · intro x y xs hxy ih have hm : bpe_full_merge a b z (x :: y :: xs) = x :: bpe_full_merge a b z (y :: xs) := by simp [bpe_full_merge, hxy] have hc : bpe_pair_count a b (x :: y :: xs) = bpe_pair_count a b (y :: xs) := by simp [bpe_pair_count, hxy] rw [hm, hc] simp only [List.length_cons] at ih ⊢ have hle := bpe_min_greedy_utility_one_eq_optimal_merge_length_le a b z (y :: xs) simp only [List.length_cons] at hle omegaprivate lemma bpe_min_greedy_utility_one_eq_optimal_pair_count_pos_mem_zip (a b : ℕ) (s : List ℕ) (h : 0 < bpe_pair_count a b s) : (a, b) ∈ s.zip s.tail := by refine bpe_pair_count.induct a b (fun s => 0 < bpe_pair_count a b s → (a, b) ∈ s.zip s.tail) ?_ ?_ ?_ ?_ s h · simp [bpe_pair_count] · intro x simp [bpe_pair_count] · intro x y xs hxy _ _ simp [hxy] · intro x y xs hxy ih hpos have hc : bpe_pair_count a b (x :: y :: xs) = bpe_pair_count a b (y :: xs) := by simp [bpe_pair_count, hxy] rw [hc] at hpos have hmem := ih hpos simp only [List.zip_cons_cons, List.tail_cons] exact List.mem_cons_of_mem _ hmemprivate lemma bpe_min_greedy_utility_one_eq_optimal_pair_count_le_max (a b : ℕ) (s : List ℕ) : bpe_pair_count a b s ≤ bpe_max_pair_count s := by rcases Nat.eq_zero_or_pos (bpe_pair_count a b s) with h0 | hpos · rw [h0]; exact Nat.zero_le _ · have hmem := bpe_min_greedy_utility_one_eq_optimal_pair_count_pos_mem_zip a b s hpos have hle := Finset.le_sup (s := (s.zip s.tail).toFinset) (f := fun p : ℕ × ℕ => bpe_pair_count p.1 p.2 s) (by simpa using hmem) simpa [bpe_max_pair_count] using hleprivate lemma bpe_min_greedy_utility_one_eq_optimal_exists_pair_eq_max (s : List ℕ) (h : 0 < bpe_max_pair_count s) : ∃ a b : ℕ, bpe_pair_count a b s = bpe_max_pair_count s := by have hne : (s.zip s.tail).toFinset.Nonempty := by rw [Finset.nonempty_iff_ne_empty] intro he rw [bpe_max_pair_count, he, Finset.sup_empty] at h exact absurd h (Nat.lt_irrefl 0) obtain ⟨p, hp, hsup⟩ := Finset.exists_mem_eq_sup _ hne (fun p : ℕ × ℕ => bpe_pair_count p.1 p.2 s) exact ⟨p.1, p.2, by simpa [bpe_max_pair_count] using hsup.symm⟩private lemma bpe_min_greedy_utility_one_eq_optimal_exists_fresh (s : List ℕ) : ∃ z : ℕ, z ∉ s := by refine ⟨s.sum + 1, ?_⟩ intro hz have hle := List.le_sum_of_mem hz omegaprivate lemma bpe_min_greedy_utility_one_eq_optimal_greedy_sub_eq_max (s t : List ℕ) (h : bpe_greedy_step s t) : s.length - t.length = bpe_max_pair_count s := by rcases h with ⟨hmax, rfl⟩ | ⟨a, b, z, hpos, hcount, hz, rfl⟩ · simp [hmax] · rw [bpe_min_greedy_utility_one_eq_optimal_merge_length_sub, hcount]private lemma bpe_min_greedy_utility_one_eq_optimal_full_sub_le_max (s t : List ℕ) (h : bpe_full_step s t) : s.length - t.length ≤ bpe_max_pair_count s := by rcases h with rfl | ⟨a, b, z, hz, rfl⟩ · simp · rw [bpe_min_greedy_utility_one_eq_optimal_merge_length_sub] exact bpe_min_greedy_utility_one_eq_optimal_pair_count_le_max a b sprivate lemma bpe_min_greedy_utility_one_eq_optimal_exists_greedy_step (s : List ℕ) : ∃ t : List ℕ, bpe_greedy_step s t ∧ s.length - t.length = bpe_max_pair_count s := by rcases Nat.eq_zero_or_pos (bpe_max_pair_count s) with h0 | hpos · refine ⟨s, Or.inl ⟨h0, rfl⟩, ?_⟩ simp [h0] · obtain ⟨a, b, hab⟩ := bpe_min_greedy_utility_one_eq_optimal_exists_pair_eq_max s hpos obtain ⟨z, hz⟩ := bpe_min_greedy_utility_one_eq_optimal_exists_fresh s refine ⟨bpe_full_merge a b z s, Or.inr ⟨a, b, z, hpos, hab, hz, rfl⟩, ?_⟩ rw [bpe_min_greedy_utility_one_eq_optimal_merge_length_sub, hab]private lemma bpe_min_greedy_utility_one_eq_optimal_exists_full_step (s : List ℕ) : ∃ t : List ℕ, bpe_full_step s t ∧ s.length - t.length = bpe_max_pair_count s := by rcases Nat.eq_zero_or_pos (bpe_max_pair_count s) with h0 | hpos · refine ⟨s, Or.inl rfl, ?_⟩ simp [h0] · obtain ⟨a, b, hab⟩ := bpe_min_greedy_utility_one_eq_optimal_exists_pair_eq_max s hpos obtain ⟨z, hz⟩ := bpe_min_greedy_utility_one_eq_optimal_exists_fresh s refine ⟨bpe_full_merge a b z s, Or.inr ⟨a, b, z, hz, rfl⟩, ?_⟩ rw [bpe_min_greedy_utility_one_eq_optimal_merge_length_sub, hab]/-- For merge budget k = 1, greedy utility equals optimal full-merge utility on any string. -/theorem bpe_min_greedy_utility_one_eq_optimal (s : List ℕ) : bpe_min_greedy_utility s 1 = bpe_optimal_full_utility s 1 := by classical unfold bpe_min_greedy_utility bpe_optimal_full_utility have hG : {u : ℕ | ∃ t, bpe_steps bpe_greedy_step 1 s t ∧ u = s.length - t.length} = {u : ℕ | ∃ t, bpe_greedy_step s t ∧ u = s.length - t.length} := by ext u; simp [bpe_steps] have hF : {u : ℕ | ∃ t, bpe_steps bpe_full_step 1 s t ∧ u = s.length - t.length} = {u : ℕ | ∃ t, bpe_full_step s t ∧ u = s.length - t.length} := by ext u; simp [bpe_steps] rw [hG, hF] have hinf : sInf {u : ℕ | ∃ t, bpe_greedy_step s t ∧ u = s.length - t.length} = bpe_max_pair_count s := by have hne : ({u : ℕ | ∃ t, bpe_greedy_step s t ∧ u = s.length - t.length} : Set ℕ).Nonempty := by obtain ⟨t, ht, hut⟩ := bpe_min_greedy_utility_one_eq_optimal_exists_greedy_step s exact ⟨_, t, ht, hut.symm⟩ have hmem := Nat.sInf_mem hne simp only [Set.mem_ofPred_eq] at hmem obtain ⟨t, ht, heq⟩ := hmem rw [heq] exact bpe_min_greedy_utility_one_eq_optimal_greedy_sub_eq_max s t ht have hsup : sSup {u : ℕ | ∃ t, bpe_full_step s t ∧ u = s.length - t.length} = bpe_max_pair_count s := by have hMmem : bpe_max_pair_count s ∈ {u : ℕ | ∃ t, bpe_full_step s t ∧ u = s.length - t.length} := by obtain ⟨t, ht, hut⟩ := bpe_min_greedy_utility_one_eq_optimal_exists_full_step s exact ⟨t, ht, hut.symm⟩ have hbdd : ∃ n : ℕ, ∀ a ∈ {u : ℕ | ∃ t, bpe_full_step s t ∧ u = s.length - t.length}, a ≤ n := by refine ⟨bpe_max_pair_count s, ?_⟩ intro a ha obtain ⟨t, ht, rfl⟩ := ha exact bpe_min_greedy_utility_one_eq_optimal_full_sub_le_max s t ht apply le_antisymm · rw [Nat.sSup_def hbdd] exact Nat.find_min' hbdd (fun a ha => by obtain ⟨t, ht, rfl⟩ := ha exact bpe_min_greedy_utility_one_eq_optimal_full_sub_le_max s t ht) · rw [Nat.sSup_def hbdd] exact Nat.find_spec hbdd _ hMmem rw [hinf, hsup]