AFTD Auto-Formalizing Theoretical Domains

alpha_binary_prefix_bounds

theoremverified

The encoding of a nonempty positive cell sequence has exactly sum(a) bits and starts with a one.

Statement

theorem alpha_binary_prefix_bounds (a : List ℕ) (hne : a ≠ [])
    (ha : ∀ v ∈ a, 0 < v) :
    2 ^ (a.sum - 1) ≤ alpha_binary_prefix a ∧ alpha_binary_prefix a < 2 ^ a.sum
Source
Run-length helpers for OP-392, arXiv:2610.24758, Conjecture 1; lexical sequences and elementary operations from arXiv:0810.5205, Definitions 1.1, Section 2, Theorem 3.1 and Corollary 3.3. No new research advance is claimed for these supporting statements.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 6

The proof, explained

The theorem establishes that the encoding alpha_binary_prefix a of any non-empty positive sequence a satisfies 2^(sum(a) - 1) ≤ alpha_binary_prefix a < 2^(sum(a)). The upper bound is proved by induction on the list: in the inductive step, the tail prefix is bounded by 2^(sum(xs)) ≤ 2^(x - 1 + sum(xs)), and adding the head term 2^(x - 1 + sum(xs)) doubles this power to 2^(x + sum(xs)) = 2^(sum(x :: xs)). The lower bound follows directly for a non-empty list x :: xs, since the leading term in alpha_binary_prefix (x :: xs) is 2^(x - 1 + sum(xs)) = 2^(sum(a) - 1), and the remaining terms are non-negative.

  1. For the empty list, the upper bound alpha_binary_prefix [] < 2 ^ [].sum holds.

    We proceed by induction on the list a. In the base case a = [], alpha_binary_prefix [] is 0 and the sum of [] is 0, so the inequality reduces to 0 < 2^0 = 1, which holds by evaluating the definitions.

    lines 1–4

    theorem alpha_binary_prefix_bounds_lt (a : List ℕ) (ha : ∀ v ∈ a, 0 < v) :
        alpha_binary_prefix a < 2 ^ a.sum := by
      induction a with
      | nil => simp [alpha_binary_prefix]
  2. In the inductive step for a = x :: xs, the head x is positive and the tail xs satisfies the induction hypothesis.

    From the hypothesis that all elements in x :: xs are positive, we obtain x > 0 and that every element of xs is positive. Applying the induction hypothesis to xs yields alpha_binary_prefix xs < 2 ^ xs.sum.

    lines 5–8

      | cons x xs ih =>
        have hx : 0 < x := ha x (by simp)
        have hxs : ∀ v ∈ xs, 0 < v := fun v hv => ha v (by simp [hv])
        have ih' : alpha_binary_prefix xs < 2 ^ xs.sum := ih hxs
  3. The prefix of the tail is strictly bounded by 2 ^ (x - 1 + xs.sum).

    Rewriting with the recursive definition of alpha_binary_prefix and List.sum_cons, the goal involves 2 ^ (x - 1 + xs.sum) + alpha_binary_prefix xs. Since x > 0, we have xs.sum ≤ x - 1 + xs.sum. By monotonicity of powers of 2 (Nat.pow_le_pow_right), 2 ^ xs.sum ≤ 2 ^ (x - 1 + xs.sum). Chaining this with the induction hypothesis using lt_of_lt_of_le gives alpha_binary_prefix xs < 2 ^ (x - 1 + xs.sum).

    lines 9–12

    uses List.sum_cons, Nat.pow_le_pow_right, lt_of_lt_of_le

        rw [alpha_binary_prefix, List.sum_cons]
        have h1 : 2 ^ xs.sum ≤ 2 ^ (x - 1 + xs.sum) :=
          Nat.pow_le_pow_right (by norm_num) (by omega)
        have h2 : alpha_binary_prefix xs < 2 ^ (x - 1 + xs.sum) := lt_of_lt_of_le ih' h1
  4. Doubling the power of 2 completes the inductive step, showing alpha_binary_prefix (x :: xs) < 2 ^ (x :: xs).sum.

    Adding 2 ^ (x - 1 + xs.sum) to both sides via Nat.add_lt_add_left produces 2 ^ (x - 1 + xs.sum) + alpha_binary_prefix xs < 2 ^ (x - 1 + xs.sum) + 2 ^ (x - 1 + xs.sum). By Nat.two_pow_succ, doubling 2 ^ (x - 1 + xs.sum) gives 2 ^ (x - 1 + xs.sum + 1), which simplifies to 2 ^ (x + xs.sum) because x > 0. Combining the strict inequality and equality via lt_of_lt_of_eq finishes the inductive step.

    lines 13–20

    uses Nat.add_lt_add_left, Nat.two_pow_succ, lt_of_lt_of_eq

        have h3 : 2 ^ (x - 1 + xs.sum) + alpha_binary_prefix xs <
            2 ^ (x - 1 + xs.sum) + 2 ^ (x - 1 + xs.sum) :=
          Nat.add_lt_add_left h2 _
        have h4 : 2 ^ (x - 1 + xs.sum) + 2 ^ (x - 1 + xs.sum) = 2 ^ (x + xs.sum) := by
          rw [← Nat.two_pow_succ]
          congr 1
          omega
        exact lt_of_lt_of_eq h3 h4
  5. To prove both bounds for a non-empty list, it suffices to prove the lower bound 2 ^ (a.sum - 1) ≤ alpha_binary_prefix a.

    Using refine, the conjunction is split into two goals. The upper bound alpha_binary_prefix a < 2 ^ a.sum is discharged immediately by the helper theorem alpha_binary_prefix_bounds_lt, leaving only the lower bound to be proved.

    lines 21–25

    uses alpha_binary_prefix_bounds_lt

    theorem alpha_binary_prefix_bounds (a : List ℕ) (hne : a ≠ [])
        (ha : ∀ v ∈ a, 0 < v) :
        2 ^ (a.sum - 1) ≤ alpha_binary_prefix a ∧ alpha_binary_prefix a < 2 ^ a.sum := by
      refine ⟨?_, alpha_binary_prefix_bounds_lt a ha⟩
  6. For any non-empty list, the lower bound 2 ^ (a.sum - 1) ≤ alpha_binary_prefix a holds.

    Since a is non-empty, we pattern match a as x :: xs. Unfolding alpha_binary_prefix and List.sum_cons gives 2 ^ (x + xs.sum - 1) ≤ 2 ^ (x - 1 + xs.sum) + alpha_binary_prefix xs. Because x > 0, the exponents x - 1 + xs.sum and x + xs.sum - 1 are equal. After rewriting the exponent, the inequality has the form 2^k ≤ 2^k + alpha_binary_prefix xs, which holds by Nat.le_add_right.

    lines 26–32

    uses List.sum_cons, Nat.le_add_right

      match a, hne with
      | x :: xs, _ =>
        rw [alpha_binary_prefix, List.sum_cons]
        have hx : 0 < x := ha x (by simp)
        have he : x - 1 + xs.sum = x + xs.sum - 1 := by omega
        rw [he]
        exact Nat.le_add_right _ _
alpha_binary_prefix_bounds_lt
For any list of positive natural numbers, its alpha-binary prefix value is strictly less than 2 raised to the sum of the list.
List.sum_cons
The sum of a list with head a and tail l equals a plus the sum of l.
Nat.pow_le_pow_right
For any base n > 0, raising n to a power is monotonic in the exponent: if i ≤ j, then n^i ≤ n^j.
lt_of_lt_of_le
Strict inequality is transitive with non-strict inequality: if a < b and b ≤ c, then a < c.
Nat.add_lt_add_left
Adding the same natural number to the left of both sides of a strict inequality preserves the inequality.
Nat.two_pow_succ
2^(n + 1) equals 2^n + 2^n.
lt_of_lt_of_eq
If a < b and b = c, then a < c.
Nat.le_add_right
Any natural number n is less than or equal to n plus any natural number k.

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

theorem alpha_binary_prefix_bounds_lt (a : List ℕ) (ha : ∀ v ∈ a, 0 < v) :    alpha_binary_prefix a < 2 ^ a.sum := by  induction a with  | nil => simp [alpha_binary_prefix]  | cons x xs ih =>    have hx : 0 < x := ha x (by simp)    have hxs : ∀ v ∈ xs, 0 < v := fun v hv => ha v (by simp [hv])    have ih' : alpha_binary_prefix xs < 2 ^ xs.sum := ih hxs    rw [alpha_binary_prefix, List.sum_cons]    have h1 : 2 ^ xs.sum ≤ 2 ^ (x - 1 + xs.sum) :=      Nat.pow_le_pow_right (by norm_num) (by omega)    have h2 : alpha_binary_prefix xs < 2 ^ (x - 1 + xs.sum) := lt_of_lt_of_le ih' h1    have h3 : 2 ^ (x - 1 + xs.sum) + alpha_binary_prefix xs <        2 ^ (x - 1 + xs.sum) + 2 ^ (x - 1 + xs.sum) :=      Nat.add_lt_add_left h2 _    have h4 : 2 ^ (x - 1 + xs.sum) + 2 ^ (x - 1 + xs.sum) = 2 ^ (x + xs.sum) := by      rw [← Nat.two_pow_succ]      congr 1      omega    exact lt_of_lt_of_eq h3 h4theorem alpha_binary_prefix_bounds (a : List ℕ) (hne : a ≠ [])    (ha : ∀ v ∈ a, 0 < v) :    2 ^ (a.sum - 1) ≤ alpha_binary_prefix a ∧ alpha_binary_prefix a < 2 ^ a.sum := by  refine ⟨?_, alpha_binary_prefix_bounds_lt a ha⟩  match a, hne with  | x :: xs, _ =>    rw [alpha_binary_prefix, List.sum_cons]    have hx : 0 < x := ha x (by simp)    have he : x - 1 + xs.sum = x + xs.sum - 1 := by omega    rw [he]    exact Nat.le_add_right _ _
See it in the graphDiscuss this resultChallenge it