AFTD Auto-Formalizing Theoretical Domains

bpe_min_greedy_utility_one_eq_optimal

theoremverified

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.

  1. 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.

    lines 3–18

    uses bpe_full_merge.induct, List.length_cons

      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 ⊢
        omega
  2. 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.

    lines 23–45

    uses bpe_full_merge.induct, List.length_cons, bpe_min_greedy_utility_one_eq_optimal_merge_length_le

      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
        omega
  3. 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.

    lines 50–62

    uses bpe_pair_count.induct, List.zip_cons_cons, List.tail_cons, List.mem_cons_of_mem

      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 _ hmem
  4. 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.

    lines 66–71

    uses Nat.eq_zero_or_pos, Nat.zero_le, bpe_min_greedy_utility_one_eq_optimal_pair_count_pos_mem_zip, Finset.le_sup

      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 hle
  5. 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).

    lines 76–82

    uses Finset.nonempty_iff_ne_empty, Finset.sup_empty, Nat.lt_irrefl, Finset.exists_mem_eq_sup

      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⟩
  6. 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.

    lines 86–89

    uses List.le_sum_of_mem

      refine ⟨s.sum + 1, ?_⟩
      intro hz
      have hle := List.le_sum_of_mem hz
      omega
  7. 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.

    lines 94–96

    uses bpe_min_greedy_utility_one_eq_optimal_merge_length_sub

      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]
  8. 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.

    lines 101–104

    uses bpe_min_greedy_utility_one_eq_optimal_merge_length_sub, bpe_min_greedy_utility_one_eq_optimal_pair_count_le_max

      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 s
  9. 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.

    lines 109–115

    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_sub

      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]
  10. 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.

    lines 120–126

    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_sub

      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]
  11. 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.

    lines 131–139

      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]
  12. 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.

    lines 140–149

    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_max

      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
  13. 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.

    lines 150–166

    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_spec

      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
  14. 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.

    line 167

      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.

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

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]
See it in the graphDiscuss this resultChallenge it