AFTD Auto-Formalizing Theoretical Domains

bpe_optimal_full_utility

def

The maximum total reduction in string length achieved by any k-step sequence of full Byte-Pair Encoding merges on s.

Statement

noncomputable def bpe_optimal_full_utility (s : List ℕ) (k : ℕ) : ℕ
Defined in
scout/2611-08671-greedy-byte-pair-encoding-achieves-at-least-0-361-of-the-op.md:290
Verified
13 Nov 2026
Axioms
none listed
Built on 2
  • 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.
Used by 3
  • bpe_min_greedy_utility_one_eq_optimalFor any string s and merge budget k = 1, the minimum reduction in length achieved by a greedy full-merge step equals the optimal reduction…
  • iid_greedy_bpe_approx_probGiven alphabet size q, weights p : Fin q → ℝ, merge budget k, length N, and tolerance ε : ℝ, iid_greedy_bpe_approx_prob q p k N ε is the…
  • 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

bpe_optimal_full_utility s k is defined as the supremum (in ℕ) of the set of all natural numbers u for which there exists a list t : List ℕ reachable from s in k steps of the transition relation bpe_full_step, such that u = s.length - t.length (the reduction in list length from s to t).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The supremum of length decrease achievable over all k-step full-merge sequences from string s. -/
noncomputable def bpe_optimal_full_utility (s : List ℕ) (k : ℕ) : ℕ := sSup {u : ℕ | ∃ t, bpe_steps bpe_full_step k s t ∧ u = s.length - t.length}
See it in the graphDiscuss this resultChallenge it