AFTD Auto-Formalizing Theoretical Domains

alpha_binary_prefix_append

theoremverified

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

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.

  1. 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.

    lines 4–5

    uses alpha_binary_prefix

      induction a with
      | nil => simp [alpha_binary_prefix]
  2. 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.

    lines 6–7

    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]
  3. 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.

    lines 8–9

    uses pow_add

        rw [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

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