AFTD Auto-Formalizing Theoretical Domains

alpha_binary_completion_inverse

theoremverified

Completing the prefix to even or odd Hamming parity gives the two consecutive inverse Gray ranks 2q and 2q+1.

Statement

theorem alpha_binary_completion_inverse (a : List ℕ)
    (ha : ∀ v ∈ a, 0 < v) :
    brgc_inverse (a.sum + 1) (2 * alpha_binary_prefix a + a.length % 2) =
      2 * brgc_inverse a.sum (alpha_binary_prefix a) ∧
    brgc_inverse (a.sum + 1) (2 * alpha_binary_prefix a + (a.length + 1) % 2) =
      2 * brgc_inverse a.sum (alpha_binary_prefix a) + 1
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 6
  • alpha_binary_prefixEncode each positive cell a as one followed by a-1 zero bits, concatenating the blocks.
  • alpha_binary_prefix_boundsThe encoding of a nonempty positive cell sequence has exactly sum(a) bits and starts with a one.
  • 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_inverseThe inverse prefix-parity transform on n-bit binary words, computed as the exclusive-or of all right shifts by less than n.
  • brgc_inverse_concatThe inverse Gray rank of a concatenation has the prefix inverse rank followed by the suffix inverse rank, complemented exactly when the…
  • brgc_inverse_flip_preserves_cut_maxIf an n-bit word has strictly greater inverse Gray rank than every nontrivial cyclic cut, toggling its last bit has at least as great an…
Used by 1

The proof, explained

The proof proceeds by case analysis on whether the list a is empty or non-empty. For non-empty lists, concatenating a single bit b to the binary prefix is analyzed using the Gray code concatenation theorem brgc_inverse_concat, which reflects the suffix rank whenever the prefix's inverse rank is odd. Using alpha_binary_prefix_inverse_parity, this reflection condition coincides with the parity of the list length |a| mod 2. A case split on whether |a| is even or odd then confirms that completing with bit |a| mod 2 always produces inverse rank 2q, while completing with (|a| + 1) mod 2 produces 2q + 1.

  1. The theorem holds when the input list a is empty.

    When a = [], the sum and length are both 0, and the prefix encoding is 0. Unfolding the definitions of alpha_binary_prefix and brgc_inverse reduces the two equations to brgc_inverse 1 0 = 0 and brgc_inverse 1 1 = 1, both of which evaluate to 0 = 0 and 1 = 1.

    lines 7–8

      cases a with
      | nil => simp [alpha_binary_prefix, brgc_inverse]
  2. For a non-empty list v :: rest, the binary prefix is strictly bounded by 2^(sum a) and its inverse Gray rank has parity (|a| mod 2).

    By alpha_binary_prefix_bounds, the binary prefix of a is strictly less than 2^(sum a), verifying that it fits in sum a bits. By alpha_binary_prefix_inverse_parity, the parity of the inverse Gray rank of this prefix modulo 2 equals the list length modulo 2.

    lines 9–13

    uses alpha_binary_prefix_bounds, alpha_binary_prefix_inverse_parity

      | cons v rest =>
        have hp : alpha_binary_prefix (v :: rest) < 2 ^ (v :: rest).sum :=
          (alpha_binary_prefix_bounds _ (by simp) ha).2
        have hpar : brgc_inverse (v :: rest).sum (alpha_binary_prefix (v :: rest)) % 2
            = (v :: rest).length % 2 := alpha_binary_prefix_inverse_parity _ ha
  3. Appending any bit b < 2 to the prefix yields inverse Gray rank 2q + b when |a| is even, and 2q + (1 - b) when |a| is odd, where q is the inverse Gray rank of the prefix.

    Applying brgc_inverse_concat with block length k = 1 decomposes the inverse rank of 2 * prefix + b into 2q plus a single-bit rank, which is either brgc_inverse 1 b or 2 - 1 - brgc_inverse 1 b depending on whether q is even or odd. Substituting the length parity for the parity of q and checking the two values b = 0 and b = 1 shows that this added term simplifies to b when |a| is even and to 1 - b when |a| is odd.

    lines 14–26

    uses brgc_inverse_concat

        have key : ∀ b : ℕ, b < 2 →
            brgc_inverse ((v :: rest).sum + 1) (2 * alpha_binary_prefix (v :: rest) + b)
              = 2 * brgc_inverse (v :: rest).sum (alpha_binary_prefix (v :: rest)) +
                (if (v :: rest).length % 2 = 0 then b else 1 - b) := by
          intro b hb
          have hc := brgc_inverse_concat (m := (v :: rest).sum) (k := 1)
            (a := alpha_binary_prefix (v :: rest)) (b := b) hp hb
          rw [hpar] at hc
          rcases (by omega : b = 0 ∨ b = 1) with rfl | rfl
          · simpa using hc
          · have h11 : brgc_inverse 1 1 = 1 := by rfl
            rw [h11] at hc
            simpa using hc
  4. When |a| is even, completing with |a| mod 2 = 0 yields inverse rank 2q, and completing with (|a| + 1) mod 2 = 1 yields 2q + 1.

    By Nat.mod_lt, the length modulo 2 is either 0 or 1. In the even case (|a| mod 2 = 0), we also have (|a| + 1) mod 2 = 1. Evaluating the key lemma at b = 0 and taking the true branch via if_pos yields 2q + 0 = 2q for the first equation; evaluating at b = 1 via if_pos yields 2q + 1 for the second equation.

    lines 27–32

    uses Nat.mod_lt, if_pos

        have hb2 : (v :: rest).length % 2 < 2 := Nat.mod_lt _ (by norm_num)
        rcases (by omega : (v :: rest).length % 2 = 0 ∨ (v :: rest).length % 2 = 1) with hc | hc
        · have h2 : ((v :: rest).length + 1) % 2 = 1 := by omega
          constructor
          · rw [hc, key 0 (by norm_num), if_pos hc]; simp
          · rw [h2, key 1 (by norm_num), if_pos hc]
  5. When |a| is odd, completing with |a| mod 2 = 1 yields inverse rank 2q, and completing with (|a| + 1) mod 2 = 0 yields 2q + 1.

    In the odd case (|a| mod 2 = 1), we have (|a| + 1) mod 2 = 0. Evaluating the key lemma at b = 1 and selecting the false branch via if_neg yields 2q + (1 - 1) = 2q for the first equation; evaluating at b = 0 via if_neg yields 2q + (1 - 0) = 2q + 1 for the second equation.

    lines 33–36

    uses if_neg

        · have h2 : ((v :: rest).length + 1) % 2 = 0 := by omega
          constructor
          · rw [hc, key 1 (by norm_num), if_neg (by omega : ¬ (v :: rest).length % 2 = 0)]; simp
          · rw [h2, key 0 (by norm_num), if_neg (by omega : ¬ (v :: rest).length % 2 = 0)]
alpha_binary_prefix_bounds
For any non-empty list of positive natural numbers, its binary prefix encoding is strictly less than 2 raised to the sum of the list elements (and at least 2^(sum - 1)).
alpha_binary_prefix_inverse_parity
For any list of positive natural numbers, the parity of the inverse Gray code rank of its binary prefix encoding equals the parity of the length of the list.
brgc_inverse_concat
The inverse Gray code rank of an (m + k)-bit concatenation 2^k * a + b is 2^k times the inverse Gray rank of the prefix a, plus either the inverse Gray rank of the suffix b (if the prefix rank is even) or its reflection 2^k - 1 - rank(b) (if the prefix rank is odd).
Nat.mod_lt
For any natural numbers x and y with y > 0, the remainder x % y is strictly less than y.
if_pos
If a condition c is true, then the conditional expression if c then t else e simplifies to the then-branch t.
if_neg
If a condition c is false, then the conditional expression if c then t else e simplifies to the else-branch e.

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_completion_inverse (a : List ℕ)    (ha : ∀ v ∈ a, 0 < v) :    brgc_inverse (a.sum + 1) (2 * alpha_binary_prefix a + a.length % 2) =      2 * brgc_inverse a.sum (alpha_binary_prefix a) ∧    brgc_inverse (a.sum + 1) (2 * alpha_binary_prefix a + (a.length + 1) % 2) =      2 * brgc_inverse a.sum (alpha_binary_prefix a) + 1 := by  cases a with  | nil => simp [alpha_binary_prefix, brgc_inverse]  | cons v rest =>    have hp : alpha_binary_prefix (v :: rest) < 2 ^ (v :: rest).sum :=      (alpha_binary_prefix_bounds _ (by simp) ha).2    have hpar : brgc_inverse (v :: rest).sum (alpha_binary_prefix (v :: rest)) % 2        = (v :: rest).length % 2 := alpha_binary_prefix_inverse_parity _ ha    have key : ∀ b : ℕ, b < 2 →        brgc_inverse ((v :: rest).sum + 1) (2 * alpha_binary_prefix (v :: rest) + b)          = 2 * brgc_inverse (v :: rest).sum (alpha_binary_prefix (v :: rest)) +            (if (v :: rest).length % 2 = 0 then b else 1 - b) := by      intro b hb      have hc := brgc_inverse_concat (m := (v :: rest).sum) (k := 1)        (a := alpha_binary_prefix (v :: rest)) (b := b) hp hb      rw [hpar] at hc      rcases (by omega : b = 0 ∨ b = 1) with rfl | rfl      · simpa using hc      · have h11 : brgc_inverse 1 1 = 1 := by rfl        rw [h11] at hc        simpa using hc    have hb2 : (v :: rest).length % 2 < 2 := Nat.mod_lt _ (by norm_num)    rcases (by omega : (v :: rest).length % 2 = 0 ∨ (v :: rest).length % 2 = 1) with hc | hc    · have h2 : ((v :: rest).length + 1) % 2 = 1 := by omega      constructor      · rw [hc, key 0 (by norm_num), if_pos hc]; simp      · rw [h2, key 1 (by norm_num), if_pos hc]    · have h2 : ((v :: rest).length + 1) % 2 = 0 := by omega      constructor      · rw [hc, key 1 (by norm_num), if_neg (by omega : ¬ (v :: rest).length % 2 = 0)]; simp      · rw [h2, key 0 (by norm_num), if_neg (by omega : ¬ (v :: rest).length % 2 = 0)]
See it in the graphDiscuss this resultChallenge it