AFTD Auto-Formalizing Theoretical Domains

alpha_binary_prefix_inverse_parity

theoremverified

The inverse Gray rank of the prefix has the parity of the number of encoded one bits, namely the cell count.

Statement

theorem alpha_binary_prefix_inverse_parity (a : List ℕ)
    (ha : ∀ v ∈ a, 0 < v) :
    brgc_inverse a.sum (alpha_binary_prefix a) % 2 = a.length % 2
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 9
  • 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.
  • 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_wordThe n-bit inverse prefix-parity transform recovers an n-bit Gray rank from its encoded word.
  • brgc_word_low_onesA rank consisting of k+1 low one-bits encodes the word with only bit k set.
  • brgc_inverse_lt_two_powThe inverse prefix-parity transform of an n-bit word has an n-bit rank.
  • 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…
  • brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
Used by 2

The proof, explained

The theorem is proved by induction on the list of positive run lengths a. In the inductive step a = x :: xs, the prefix encoding splits into a concatenation of 2 ^ (x - 1) and alpha_binary_prefix xs. By the concatenation formula for the inverse Gray code, the lower part is reflected because the Gray rank of 2 ^ (x - 1) is 2 ^ x - 1, which is odd. Because xs is non-empty and its elements positive, 2 ^ xs.sum is even, so this reflection negates the parity (E - 1 - R ≡ R + 1 mod 2), transforming the induction hypothesis parity of xs into the parity of x :: xs.

  1. The base case holds for the empty list: both the inverse Gray rank and the list length are 0 modulo 2.

    We induct on the list a. When a is empty, its sum, length, and prefix encoding are all 0. Since brgc_inverse 0 0 is 0 by definition, both sides evaluate to 0 modulo 2.

    lines 4–7

    uses List.sum_nil, List.length_nil

      induction a with
      | nil =>
        simp only [List.sum_nil, List.length_nil, alpha_binary_prefix]
        decide
  2. For a non-empty list x :: xs, the head x and all elements of xs are strictly positive, and the sum and length rewrite to x + xs.sum and xs.length + 1.

    In the inductive step with list x :: xs and induction hypothesis ih on xs, the assumption that all elements in x :: xs are positive yields 0 < x and 0 < v for all v in xs. Rewriting with List.sum_cons and List.length_cons expresses the total sum and length in terms of x and xs.

    lines 8–11

    uses List.mem_cons_of_mem, List.sum_cons, List.length_cons

      | cons x xs ih =>
        have hx : 0 < x := ha x (by simp)
        have hxs : ∀ v ∈ xs, 0 < v := fun v hv => ha v (List.mem_cons_of_mem _ hv)
        rw [List.sum_cons, List.length_cons]
  3. The prefix encoding decomposes into a shifted power plus the prefix encoding of the tail: alpha_binary_prefix (x :: xs) = 2 ^ xs.sum * 2 ^ (x - 1) + alpha_binary_prefix xs.

    By definition, alpha_binary_prefix (x :: xs) is 2 ^ (x - 1 + xs.sum) + alpha_binary_prefix xs. Commuting the sum in the exponent and applying pow_add factors the first term into 2 ^ xs.sum * 2 ^ (x - 1).

    lines 12–15

    uses pow_add

        have hcons : alpha_binary_prefix (x :: xs) = 2 ^ xs.sum * 2 ^ (x - 1) + alpha_binary_prefix xs := by
          simp only [alpha_binary_prefix]
          rw [show x - 1 + xs.sum = xs.sum + (x - 1) by omega, pow_add]
        rw [hcons]
  4. The inverse Gray rank of the concatenation expands into a scaled higher rank plus a reflected or direct lower rank.

    Since x > 0, we have 2 ^ (x - 1) < 2 ^ x. The lower part alpha_binary_prefix xs is bounded by 2 ^ xs.sum (vacuously if xs is empty, or by alpha_binary_prefix_bounds if xs is non-empty). Applying brgc_inverse_concat decomposes the inverse Gray rank into 2 ^ xs.sum * brgc_inverse x (2 ^ (x - 1)) plus a conditional term depending on the parity of the higher rank.

    lines 16–23

    uses Nat.pow_lt_pow_right, alpha_binary_prefix_bounds, brgc_inverse_concat

        have hfirst : 2 ^ (x - 1) < 2 ^ x := by
          apply Nat.pow_lt_pow_right (by norm_num) (by omega)
        have hlt : alpha_binary_prefix xs < 2 ^ xs.sum := by
          rcases xs with _ | ⟨y, ys⟩
          · simp [alpha_binary_prefix]
          · exact (alpha_binary_prefix_bounds (y :: ys) (by simp) (fun v hv => hxs v (by simp [hv]))).2
        rw [brgc_inverse_concat (m := x) (k := xs.sum) (a := 2 ^ (x - 1))
          (b := alpha_binary_prefix xs) hfirst hlt]
  5. The higher-order inverse Gray rank is 2 ^ x - 1, which is odd, selecting the reflected branch.

    The Gray codeword of 2 ^ x - 1 is 2 ^ (x - 1) by brgc_word_low_ones, so its inverse rank is 2 ^ x - 1. Because x > 0, 2 ^ x is even, which makes 2 ^ x - 1 odd ((2 ^ x - 1) % 2 = 1). Since the rank is odd, the conditional test for even parity is false (if_neg), selecting the reflected branch 2 ^ xs.sum - 1 - brgc_inverse xs.sum (alpha_binary_prefix xs).

    lines 24–38

    uses brgc_word_low_ones, brgc_inverse_word, Nat.two_pow_pos, Nat.pow_mod, Nat.pos_iff_ne_zero.mp, Nat.one_le_two_pow, if_neg

        have hrank : brgc_inverse x (2 ^ (x - 1)) = 2 ^ x - 1 := by
          have hw : brgc_word (2 ^ x - 1) = 2 ^ (x - 1) := by
            have h := brgc_word_low_ones (x - 1)
            rwa [show x - 1 + 1 = x by omega] at h
          rw [← hw]
          exact brgc_inverse_word (by have := Nat.two_pow_pos x; omega)
        have hodd : (2 ^ x - 1) % 2 = 1 := by
          have h2 : 2 ^ x % 2 = 0 := by
            rw [Nat.pow_mod]
            have : 2 % 2 = 0 := by norm_num
            rw [this]
            simp [Nat.pos_iff_ne_zero.mp hx]
          have hge : 1 ≤ 2 ^ x := Nat.one_le_two_pow
          omega
        rw [hrank, if_neg (by rw [hodd]; norm_num)]
  6. When the tail xs is empty, both sides evaluate directly to 1 modulo 2.

    When xs = [], xs.sum = 0, 2 ^ 0 = 1, and alpha_binary_prefix [] = 0. The expression simplifies to (1 * (2 ^ x - 1) + 0) % 2 = 1, matching (0 + 1) % 2 = 1.

    lines 39–40

        rcases xs with _ | ⟨y, ys⟩
        · simp [alpha_binary_prefix, hodd]
  7. When xs is non-empty, the scaling factor E = 2 ^ xs.sum is even, so E * (2 ^ x - 1) is 0 modulo 2.

    Writing xs as y :: ys, since y > 0, the sum xs.sum is strictly positive. Factoring out 2 with pow_succ shows that E = 2 ^ xs.sum is even (E % 2 = 0). Therefore, by modular multiplication (Nat.mul_mod), the product E * (2 ^ x - 1) is 0 modulo 2.

    lines 41–56

    uses List.sum_cons, pow_succ, Nat.mul_mod

        · have hy : 0 < y := hxs y (by simp)
          have hk : 0 < (y :: ys).sum := by
            rw [List.sum_cons]; omega
          set E := 2 ^ (y :: ys).sum with hEdef
          set R := brgc_inverse (y :: ys).sum (alpha_binary_prefix (y :: ys)) with hRdef
          have hEeven : E % 2 = 0 := by
            rw [hEdef]
            have h2 : 2 ^ (y :: ys).sum = 2 ^ ((y :: ys).sum - 1) * 2 := by
              rw [← pow_succ]
              congr 1
              omega
            rw [h2, Nat.mul_mod]
            simp
          have hEmul : (E * (2 ^ x - 1)) % 2 = 0 := by
            rw [Nat.mul_mod, hEeven]
            simp
  8. The reflection reverses the parity of the lower rank, which matches xs.length + 1 modulo 2 by the induction hypothesis.

    Let R = brgc_inverse xs.sum (alpha_binary_prefix xs). Since R < E by brgc_inverse_lt_two_pow and E is even with E ≥ 2, we have (E - 1 - R) % 2 = (E - (R + 1)) % 2 = (R + 1) % 2. By the induction hypothesis, R % 2 = xs.length % 2. Adding the even term E * (2 ^ x - 1) gives (0 + R + 1) % 2 = (xs.length + 1) % 2, completing the induction.

    lines 57–69

    uses brgc_inverse_lt_two_pow, alpha_binary_prefix_bounds, Nat.add_mod

          have hRlt : R < E := by
            rw [hRdef, hEdef]
            apply brgc_inverse_lt_two_pow
            exact (alpha_binary_prefix_bounds (y :: ys) (by simp)
              (fun v hv => hxs v (by simp [hv]))).2
          have hsub : (E - 1 - R) % 2 = (R + 1) % 2 := by
            have hE2 : 2 ≤ E := by omega
            have h1 : E - 1 - R = E - (R + 1) := by omega
            rw [h1]
            omega
          have ih' : R % 2 = (y :: ys).length % 2 := ih (fun v hv => hxs v (by simp [hv]))
          rw [Nat.add_mod, hEmul, hsub]
          omega
List.sum_nil
The sum of the elements in the empty list is 0.
List.length_nil
The length of the empty list is 0.
List.mem_cons_of_mem
If an element belongs to a list, it also belongs to the list formed by prepending any head.
List.sum_cons
The sum of a list `a :: l` is `a + l.sum`.
List.length_cons
The length of a list `a :: as` is `as.length + 1`.
pow_add
Exponentiation distributes over addition in the exponent: `a ^ (m + n) = a ^ m * a ^ n`.
Nat.pow_lt_pow_right
For a base greater than 1, a strictly smaller exponent yields a strictly smaller power.
alpha_binary_prefix_bounds
For a non-empty list of positive integers, the prefix encoding is bounded above by `2 ^ a.sum` (and below by `2 ^ (a.sum - 1)`).
brgc_inverse_concat
The inverse Gray rank of an (m + k)-bit concatenation `2 ^ k * a + b` is `2 ^ k * rank(a) + rank(b)` if `rank(a)` is even, and `2 ^ k * rank(a) + (2 ^ k - 1 - rank(b))` if `rank(a)` is odd.
brgc_word_low_ones
The Gray codeword of `2 ^ (k + 1) - 1` is `2 ^ k`.
Nat.two_pow_pos
Powers of 2 are strictly positive: `0 < 2 ^ w`.
brgc_inverse_word
The inverse Gray rank of the Gray codeword of `t` is `t`, provided `t < 2 ^ n`.
Nat.pow_mod
The modulus of a power equals the power of the modulus: `a ^ b % n = (a % n) ^ b % n`.
Nat.pos_iff_ne_zero.mp
A strictly positive natural number is non-zero.
Nat.one_le_two_pow
Powers of 2 are at least 1: `1 ≤ 2 ^ n`.
if_neg
A conditional expression `if c then t else e` reduces to `e` when the condition `c` is false.
pow_succ
A power `a ^ (n + 1)` equals `a ^ n * a`.
Nat.mul_mod
Multiplication commutes with modulo: `(a * b) % n = (a % n * (b % n)) % n`.
brgc_inverse_lt_two_pow
The inverse Gray rank of an n-bit word is strictly less than `2 ^ n`.
Nat.add_mod
Addition commutes with modulo: `(a + b) % n = (a % n + b % n) % 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_inverse_parity (a : List ℕ)    (ha : ∀ v ∈ a, 0 < v) :    brgc_inverse a.sum (alpha_binary_prefix a) % 2 = a.length % 2 := by  induction a with  | nil =>    simp only [List.sum_nil, List.length_nil, alpha_binary_prefix]    decide  | cons x xs ih =>    have hx : 0 < x := ha x (by simp)    have hxs : ∀ v ∈ xs, 0 < v := fun v hv => ha v (List.mem_cons_of_mem _ hv)    rw [List.sum_cons, List.length_cons]    have hcons : alpha_binary_prefix (x :: xs) = 2 ^ xs.sum * 2 ^ (x - 1) + alpha_binary_prefix xs := by      simp only [alpha_binary_prefix]      rw [show x - 1 + xs.sum = xs.sum + (x - 1) by omega, pow_add]    rw [hcons]    have hfirst : 2 ^ (x - 1) < 2 ^ x := by      apply Nat.pow_lt_pow_right (by norm_num) (by omega)    have hlt : alpha_binary_prefix xs < 2 ^ xs.sum := by      rcases xs with _ | ⟨y, ys⟩      · simp [alpha_binary_prefix]      · exact (alpha_binary_prefix_bounds (y :: ys) (by simp) (fun v hv => hxs v (by simp [hv]))).2    rw [brgc_inverse_concat (m := x) (k := xs.sum) (a := 2 ^ (x - 1))      (b := alpha_binary_prefix xs) hfirst hlt]    have hrank : brgc_inverse x (2 ^ (x - 1)) = 2 ^ x - 1 := by      have hw : brgc_word (2 ^ x - 1) = 2 ^ (x - 1) := by        have h := brgc_word_low_ones (x - 1)        rwa [show x - 1 + 1 = x by omega] at h      rw [← hw]      exact brgc_inverse_word (by have := Nat.two_pow_pos x; omega)    have hodd : (2 ^ x - 1) % 2 = 1 := by      have h2 : 2 ^ x % 2 = 0 := by        rw [Nat.pow_mod]        have : 2 % 2 = 0 := by norm_num        rw [this]        simp [Nat.pos_iff_ne_zero.mp hx]      have hge : 1 ≤ 2 ^ x := Nat.one_le_two_pow      omega    rw [hrank, if_neg (by rw [hodd]; norm_num)]    rcases xs with _ | ⟨y, ys⟩    · simp [alpha_binary_prefix, hodd]    · have hy : 0 < y := hxs y (by simp)      have hk : 0 < (y :: ys).sum := by        rw [List.sum_cons]; omega      set E := 2 ^ (y :: ys).sum with hEdef      set R := brgc_inverse (y :: ys).sum (alpha_binary_prefix (y :: ys)) with hRdef      have hEeven : E % 2 = 0 := by        rw [hEdef]        have h2 : 2 ^ (y :: ys).sum = 2 ^ ((y :: ys).sum - 1) * 2 := by          rw [← pow_succ]          congr 1          omega        rw [h2, Nat.mul_mod]        simp      have hEmul : (E * (2 ^ x - 1)) % 2 = 0 := by        rw [Nat.mul_mod, hEeven]        simp      have hRlt : R < E := by        rw [hRdef, hEdef]        apply brgc_inverse_lt_two_pow        exact (alpha_binary_prefix_bounds (y :: ys) (by simp)          (fun v hv => hxs v (by simp [hv]))).2      have hsub : (E - 1 - R) % 2 = (R + 1) % 2 := by        have hE2 : 2 ≤ E := by omega        have h1 : E - 1 - R = E - (R + 1) := by omega        rw [h1]        omega      have ih' : R % 2 = (y :: ys).length % 2 := ih (fun v hv => hxs v (by simp [hv]))      rw [Nat.add_mod, hEmul, hsub]      omega
See it in the graphDiscuss this resultChallenge it