AFTD Auto-Formalizing Theoretical Domains

bpe_min_greedy_utility

def

The minimum total reduction in string length achieved by any k-step greedy Byte-Pair Encoding merge run on s under arbitrary tie-breaking.

Statement

noncomputable def bpe_min_greedy_utility (s : List ℕ) (k : ℕ) : ℕ
Defined in
scout/2611-08671-greedy-byte-pair-encoding-achieves-at-least-0-361-of-the-op.md:59
Verified
13 Nov 2026
Axioms
none listed
Built on 2
  • 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_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_min_greedy_utility s k is defined as the infimum (in ℕ, which is the minimum since the set is non-empty) of the set of all length reductions s.length - t.length over all lists t : List ℕ reachable from s in k steps of the bpe_greedy_step relation. Specifically, for a given initial list of natural numbers s and a number of steps k: 1. It considers all sequences of k transitions $s = s_0 \to s_1 \to \dots \to s_k = t$, where each step $s_i \to s_{i+1}$ satisfies bpe_greedy_step s_i s_{i+1}: - Either the maximum pair count in $s_i$ is 0 and $s_{i+1} = s_i$; - Or the maximum pair count in $s_i$ is strictly positive, and there exist natural numbers $a, b, z$ such that the pair $(a, b)$ achieves the maximum pair count in $s_i$, $z$ does not occur in $s_i$, and $s_{i+1}$ is the result of replacing all non-overlapping occurrences of the adjacent pair $(a, b)$ in $s_i$ with $z$. 2. For each such reachable list $t$, the utility is the decrease in length, s.length - t.length. 3. The function returns the minimum (sInf) such utility across all valid $k$-step greedy derivation paths starting from s.

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 infimum of length decrease achievable by any k-step greedy Byte-Pair Encoding run from string s under arbitrary tie-breaking. -/
noncomputable def bpe_min_greedy_utility (s : List ℕ) (k : ℕ) : ℕ := sInf {u : ℕ | ∃ t, bpe_steps bpe_greedy_step k s t ∧ u = s.length - t.length}
See it in the graphDiscuss this resultChallenge it