AFTD Auto-Formalizing Theoretical Domains

iid_bpe_sharp_factor_bounds

theoremverified

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.

  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.

    lines 3–4

      unfold iid_bpe_sharp_factor
      constructor
  2. 0 < (2 + √2)/4 automation

    The lower bound follows immediately because the constants 2 and 4, as well as √2, are strictly positive.

    line 5

      · positivity
  3. √2 < 2

    Since 0 < 2, the equivalence Real.sqrt_lt' reduces √2 < 2 to 2 < 2², which holds since 2 < 4 by basic arithmetic.

    lines 6–8

    uses Real.sqrt_lt'

      · have : Real.sqrt 2 < 2 := by
          rw [Real.sqrt_lt' (by norm_num)]
          norm_num
  4. (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.

    line 9

        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

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