alpha_binary_completion_inverse
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
- alpha_lexical_terminal_predecessor_simple_star_obstructionThe two displayed lexical sequences are adjacent among sequences of degree 19 and have meet f=(2,1,1). The later sequence has a lexical…
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.
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.
cases a with | nil => simp [alpha_binary_prefix, brgc_inverse]
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.
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 _ haAppending 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.
uses
brgc_inverse_concathave 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
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.
uses
Nat.mod_lt,if_poshave 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]
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.
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
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_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)]