iid_bpe_sharp_factor_bounds
The i.i.d. BPE sharp approximation constant c = (2 + √2)/4 lies strictly in the open unit interval (0, 1).
Statement
theorem iid_bpe_sharp_factor_bounds : 0 < iid_bpe_sharp_factor ∧ iid_bpe_sharp_factor < 1- Source
- folklore
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- iid_bpe_sharp_factorThe conjectured sharp uniform i.i.d. greedy Byte-Pair Encoding merge factor c = (2 + √2) / 4.
- 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
The real constant iid_bpe_sharp_factor is strictly greater than 0 and strictly less than 1 (that is, 0 < iid_bpe_sharp_factor ∧ iid_bpe_sharp_factor < 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
Unfolding the definition of the sharp factor c = (2 + √2)/4 reduces the statement to proving 0 < c and c < 1. The lower bound 0 < c holds immediately because all components are strictly positive. The upper bound c < 1 is verified by first establishing that √2 < 2 (by squaring both sides), from which linear arithmetic yields (2 + √2)/4 < (2 + 2)/4 = 1.
It suffices to prove 0 < (2 + √2)/4 and (2 + √2)/4 < 1
We unfold the definition of iid_bpe_sharp_factor as (2 + √2)/4 and split the conjunction into two separate goals: the lower bound and the upper bound.
unfold iid_bpe_sharp_factor constructor
0 < (2 + √2)/4 automation
The lower bound follows immediately because the constants 2 and 4, as well as √2, are strictly positive.
· positivity√2 < 2
Since 0 < 2, the equivalence Real.sqrt_lt' reduces √2 < 2 to 2 < 2², which holds since 2 < 4 by basic arithmetic.
uses
Real.sqrt_lt'· have : Real.sqrt 2 < 2 := by rw [Real.sqrt_lt' (by norm_num)] norm_num
(2 + √2)/4 < 1 automation
Linear arithmetic concludes that (2 + √2)/4 < 1 directly from the bound √2 < 2, as (2 + √2)/4 < (2 + 2)/4 = 1.
linarith
Real.sqrt_lt'- For any real number y > 0 and real number x, √x < y if and only if x < y²
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.
/-- The i.i.d. BPE sharp approximation constant c = (2 + √2)/4 lies strictly between 0 and 1. -/theorem iid_bpe_sharp_factor_bounds : 0 < iid_bpe_sharp_factor ∧ iid_bpe_sharp_factor < 1 := by unfold iid_bpe_sharp_factor constructor · positivity · have : Real.sqrt 2 < 2 := by rw [Real.sqrt_lt' (by norm_num)] norm_num linarith