alpha_binary_prefix_inverse_parity
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
- 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.
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.
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.
uses
List.sum_nil,List.length_nilinduction a with | nil => simp only [List.sum_nil, List.length_nil, alpha_binary_prefix] decide
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.
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]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).
uses
pow_addhave 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]
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.
uses
Nat.pow_lt_pow_right,alpha_binary_prefix_bounds,brgc_inverse_concathave 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]
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).
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_neghave 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)]
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.
rcases xs with _ | ⟨y, ys⟩ · simp [alpha_binary_prefix, hodd]
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.
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
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.
uses
brgc_inverse_lt_two_pow,alpha_binary_prefix_bounds,Nat.add_modhave 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
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_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