AFTD Auto-Formalizing Theoretical Domains

brgc_inverse_alpha_binary_prefix_cons

theoremverified

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

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.

  1. 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).

    lines 6–8

    uses alpha_binary_prefix, 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]
  2. 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.

    line 9

    uses Nat.pow_lt_pow_right

      have hfirst : 2 ^ (x - 1) < 2 ^ x := Nat.pow_lt_pow_right (by norm_num) (by omega)
  3. 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.

    line 10

    uses alpha_binary_prefix_bounds_lt

      have hlt : alpha_binary_prefix xs < 2 ^ xs.sum := alpha_binary_prefix_bounds_lt xs hxs
  4. The 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.

    lines 11–16

    uses brgc_word_low_ones, brgc_inverse_word, Nat.two_pow_pos

      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)
  5. 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.

    lines 17–21

    uses Nat.pow_mod, Nat.pos_iff_ne_zero.mp, Nat.one_le_two_pow

      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
  6. 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).

    line 22

    uses List.sum_cons, brgc_inverse_concat, if_neg

      rw [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

/-- 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)]
See it in the graphDiscuss this resultChallenge it