alpha_binary_prefix_bounds
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
- alpha_binary_prefixEncode each positive cell a as one followed by a-1 zero bits, concatenating the blocks.
- alpha_binary_prefix_appendBinary encoding respects concatenation and the sum of the cells is the bit length.
- Used by 6
- lexical_degree_seventeen_class_a_counterexampleThe lexical sequences a = (3,1,1,3,3,2,2,1) and b = (3,1,1,2,1,3,2,2,1) both have degree 16, are adjacent in the source lexical order…
- alpha_binary_completion_inverseCompleting the prefix to even or odd Hamming parity gives the two consecutive inverse Gray ranks 2q and 2q+1.
- alpha_lexical_lt_iff_inverse_prefixOn equal-length positive encodings, lexical order is exactly inverse Gray-rank order.
- alpha_lexical_odd_completion_iff_rotation_max_of_primeThe proposed encoding bridge between positive lexical sequences and nonconstant odd-parity maximum-rank necklace representatives at odd…
- alpha_binary_prefix_inverse_parityThe inverse Gray rank of the prefix has the parity of the number of encoded one bits, namely the cell count.
- brgc_inverse_alpha_binary_prefix_consThe inverse Gray rank of x :: xs equals 2^xs.sum * (2^x - 1) + (2^xs.sum - 1 - brgc_inverse xs.sum (alpha_binary_prefix xs)).
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.
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.
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]
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.
| 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 hxsThe 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).
uses
List.sum_cons,Nat.pow_le_pow_right,lt_of_lt_of_lerw [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
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.
uses
Nat.add_lt_add_left,Nat.two_pow_succ,lt_of_lt_of_eqhave 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
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.
uses
alpha_binary_prefix_bounds_lttheorem 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⟩
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.
uses
List.sum_cons,Nat.le_add_rightmatch 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
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.
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 _ _