alpha_binary_prefix_append
Binary encoding respects concatenation and the sum of the cells is the bit length.
Statement
theorem alpha_binary_prefix_append (a b : List ℕ) :
alpha_binary_prefix (a ++ b) =
2 ^ b.sum * alpha_binary_prefix a + alpha_binary_prefix b- 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
Quot.soundpropext- Built on 1
- alpha_binary_prefixEncode each positive cell a as one followed by a-1 zero bits, concatenating the blocks.
- Used by 3
- alpha_elementary_cell_step_binary_xorAn elementary operation changes exactly the boundary bit immediately before the untouched suffix.
- 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_boundsThe encoding of a nonempty positive cell sequence has exactly sum(a) bits and starts with a one.
The proof, explained
The proof proceeds by structural induction on the list a. The base case a = [] is immediate from the definition of alpha_binary_prefix, as both sides evaluate to alpha_binary_prefix b. In the inductive step a = x :: xs, expanding the definition and applying the induction hypothesis leaves an identity of powers and products of 2. Rearranging the exponent into b.sum + (x - 1 + xs.sum) allows factoring out 2 ^ b.sum via pow_add, after which ring arithmetic closes the goal.
The identity holds for the empty list a = [].
We proceed by structural induction on the list a. In the base case a = [], the concatenation [] ++ b is simply b, and alpha_binary_prefix [] is 0 by definition. Thus, both sides simplify directly to alpha_binary_prefix b.
uses
alpha_binary_prefixinduction a with | nil => simp [alpha_binary_prefix]
In the inductive step a = x :: xs, applying the induction hypothesis reduces the goal to an algebraic identity on powers and products of 2.
For the inductive step with head x and tail xs, we push the concatenation inside using List.cons_append, expand alpha_binary_prefix on both sides according to its recursive definition, rewrite the sum of xs ++ b as xs.sum + b.sum via List.sum_append, and substitute the induction hypothesis for alpha_binary_prefix (xs ++ b). This leaves the equation 2 ^ (x - 1 + (xs.sum + b.sum)) + (2 ^ b.sum * alpha_binary_prefix xs + alpha_binary_prefix b) = 2 ^ b.sum * (2 ^ (x - 1 + xs.sum) + alpha_binary_prefix xs) + alpha_binary_prefix b.
uses
List.cons_append,alpha_binary_prefix,List.sum_append| cons x xs ih => simp only [List.cons_append, alpha_binary_prefix, List.sum_append, ih]The inductive step is completed by factoring the power of 2 and ring arithmetic.
By linear arithmetic, the exponent x - 1 + (xs.sum + b.sum) rearranges to b.sum + (x - 1 + xs.sum). Applying pow_add splits 2 ^ (b.sum + (x - 1 + xs.sum)) into 2 ^ b.sum * 2 ^ (x - 1 + xs.sum). The two sides are now identical upon distributing 2 ^ b.sum over the sum, which is verified by ring arithmetic.
uses
pow_addrw [show x - 1 + (xs.sum + b.sum) = b.sum + (x - 1 + xs.sum) by omega, pow_add] ring
alpha_binary_prefix- The binary prefix encoding function, which maps `[]` to 0 and `x :: xs` to 2^(x - 1 + xs.sum) + alpha_binary_prefix xs.
List.cons_append- Prepending an element to the first list distributes over concatenation: (a :: as) ++ bs = a :: (as ++ bs).
List.sum_append- The sum of elements in a concatenation of two lists is the sum of their respective sums: (l₁ ++ l₂).sum = l₁.sum + l₂.sum.
pow_add- Powers distribute over addition of exponents: a ^ (m + n) = a ^ m * a ^ n.
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_append (a b : List ℕ) : alpha_binary_prefix (a ++ b) = 2 ^ b.sum * alpha_binary_prefix a + alpha_binary_prefix b := by induction a with | nil => simp [alpha_binary_prefix] | cons x xs ih => simp only [List.cons_append, alpha_binary_prefix, List.sum_append, ih] rw [show x - 1 + (xs.sum + b.sum) = b.sum + (x - 1 + xs.sum) by omega, pow_add] ring