brgc_inverse_alpha_binary_prefix_cons
The inverse Gray rank of x :: xs equals 2^xs.sum * (2^x - 1) + (2^xs.sum - 1 - brgc_inverse xs.sum (alpha_binary_prefix xs)).
Statement
theorem brgc_inverse_alpha_binary_prefix_cons (x : ℕ) (xs : List ℕ) (hx : 0 < x)
(hxs : ∀ v ∈ xs, 0 < v) :
brgc_inverse (x :: xs).sum (alpha_binary_prefix (x :: xs)) =
2 ^ xs.sum * (2 ^ x - 1) + (2 ^ xs.sum - 1 - brgc_inverse xs.sum (alpha_binary_prefix xs))- Source
- step towards alpha_lexical_lt_iff_inverse_prefix
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
- Used by 2
- alpha_lexical_lt_iff_inverse_prefixOn equal-length positive encodings, lexical order is exactly inverse Gray-rank order.
- alpha_lexical_odd_completion_iff_rotation_max_of_primeThe proposed encoding bridge between positive lexical sequences and nonconstant odd-parity maximum-rank necklace representatives at odd…
The proof, explained
The proof calculates the inverse binary reflected Gray code (BRGC) rank of a prepended list x :: xs by decomposing its binary prefix into a high-order block 2^(x - 1) shifted by xs.sum bits plus the tail prefix. It evaluates the inverse Gray rank of the prefix block as 2^x - 1 using the fact that 2^(x - 1) is the Gray code of an all-ones word. Because 2^x - 1 is odd, the Gray code concatenation theorem selects the reversed orientation for the suffix, completing the formula.
The prefix encoding of x :: xs decomposes into a high-order block and a tail: alpha_binary_prefix (x :: xs) = 2 ^ xs.sum * 2 ^ (x - 1) + alpha_binary_prefix xs.
Unfolding alpha_binary_prefix on x :: xs yields 2 ^ (x - 1 + xs.sum) + alpha_binary_prefix xs. Commuting the exponent addition and using pow_add splits the power into 2 ^ xs.sum * 2 ^ (x - 1).
uses
alpha_binary_prefix,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]
2 ^ (x - 1) < 2 ^ x.
Since x > 0, we have x - 1 < x. By Nat.pow_lt_pow_right with base 2, 2 ^ (x - 1) < 2 ^ x.
uses
Nat.pow_lt_pow_righthave hfirst : 2 ^ (x - 1) < 2 ^ x := Nat.pow_lt_pow_right (by norm_num) (by omega)
alpha_binary_prefix xs < 2 ^ xs.sum.
Since all elements in xs are strictly positive (hxs), alpha_binary_prefix_bounds_lt establishes that the prefix value of xs is strictly bounded by 2 ^ xs.sum.
uses
alpha_binary_prefix_bounds_lthave hlt : alpha_binary_prefix xs < 2 ^ xs.sum := alpha_binary_prefix_bounds_lt xs hxsThe inverse Gray rank of the prefix block is brgc_inverse x (2 ^ (x - 1)) = 2 ^ x - 1.
By brgc_word_low_ones, the Gray code of the all-ones word 2 ^ x - 1 is 2 ^ (x - 1). Because 2 ^ x - 1 < 2 ^ x (from Nat.two_pow_pos), brgc_inverse_word inverts the Gray code, showing that brgc_inverse x (2 ^ (x - 1)) = 2 ^ x - 1.
uses
brgc_word_low_ones,brgc_inverse_word,Nat.two_pow_poshave 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)
2 ^ x - 1 is odd, that is, (2 ^ x - 1) % 2 = 1.
Because x > 0 (via Nat.pos_iff_ne_zero.mp), Nat.pow_mod implies 2 ^ x % 2 = 0. Since 1 ≤ 2 ^ x by Nat.one_le_two_pow, subtracting 1 leaves an odd number, so (2 ^ x - 1) % 2 = 1.
uses
Nat.pow_mod,Nat.pos_iff_ne_zero.mp,Nat.one_le_two_powhave hodd : (2 ^ x - 1) % 2 = 1 := by have h2 : 2 ^ x % 2 = 0 := by rw [Nat.pow_mod]; simp [Nat.pos_iff_ne_zero.mp hx] have hge : 1 ≤ 2 ^ x := Nat.one_le_two_pow omega
The inverse Gray rank of alpha_binary_prefix (x :: xs) matches the cons formula.
Rewriting with the decomposed prefix and List.sum_cons, the concatenation lemma brgc_inverse_concat decomposes the Gray rank into 2 ^ xs.sum * brgc_inverse x (2 ^ (x - 1)) plus a conditional tail rank. Substituting brgc_inverse x (2 ^ (x - 1)) = 2 ^ x - 1, and using if_neg since 2 ^ x - 1 is odd (not even), selects the reversed tail rank 2 ^ xs.sum - 1 - brgc_inverse xs.sum (alpha_binary_prefix xs).
uses
List.sum_cons,brgc_inverse_concat,if_negrw [hcons, List.sum_cons, brgc_inverse_concat hfirst hlt, hrank, if_neg (by omega)]
alpha_binary_prefix- definition of the binary prefix value of a list, expanding a cons cell x :: xs into 2 ^ (x - 1 + xs.sum) + alpha_binary_prefix xs
alpha_binary_prefix_bounds_lt- if all elements in a list a are positive, then alpha_binary_prefix a < 2 ^ a.sum
brgc_inverse_concat- the concatenated Gray rank of 2^k * a + b equals 2^k * brgc_inverse m a plus either the tail rank (if the prefix rank is even) or 2^k - 1 minus the tail rank (if odd)
brgc_inverse_word- the inverse Gray rank function inverts brgc_word: brgc_inverse n (brgc_word t) = t when t < 2^n
brgc_word_low_ones- the Gray code of 2^(k + 1) - 1 (a sequence of k + 1 ones) is 2^k
if_neg- if a condition c is false (¬c), then (if c then t else e) = e
List.sum_cons- the sum of a list starting with a is (a :: l).sum = a + l.sum
Nat.one_le_two_pow- for any natural number n, 1 ≤ 2^n
Nat.pow_lt_pow_right- for a > 1 and natural numbers m < n, a^m < a^n
Nat.pow_mod- powers commute with modulo: a^b % n = (a % n)^b % n
Nat.pos_iff_ne_zero.mp- a natural number is strictly positive only if it is nonzero
Nat.two_pow_pos- powers of two are strictly positive: 0 < 2^w for all w
pow_add- powers distribute over exponent addition: 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
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.
/-- The inverse Gray rank of a cons cell sequence is computed from the prefix block and the tail rank. -/theorem brgc_inverse_alpha_binary_prefix_cons (x : ℕ) (xs : List ℕ) (hx : 0 < x) (hxs : ∀ v ∈ xs, 0 < v) : brgc_inverse (x :: xs).sum (alpha_binary_prefix (x :: xs)) = 2 ^ xs.sum * (2 ^ x - 1) + (2 ^ xs.sum - 1 - brgc_inverse xs.sum (alpha_binary_prefix xs)) := by 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] have hfirst : 2 ^ (x - 1) < 2 ^ x := Nat.pow_lt_pow_right (by norm_num) (by omega) have hlt : alpha_binary_prefix xs < 2 ^ xs.sum := alpha_binary_prefix_bounds_lt xs hxs 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]; simp [Nat.pos_iff_ne_zero.mp hx] have hge : 1 ≤ 2 ^ x := Nat.one_le_two_pow omega rw [hcons, List.sum_cons, brgc_inverse_concat hfirst hlt, hrank, if_neg (by omega)]