AFTD Auto-Formalizing Theoretical Domains

brgc_inverse_word

theoremverified

The n-bit inverse prefix-parity transform recovers an n-bit Gray rank from its encoded word.

Statement

theorem brgc_inverse_word {n t : ℕ} (ht : t < 2 ^ n) :
    brgc_inverse n (brgc_word t) = t
Source
Prefix-parity inverse and supporting arithmetic for OP-392, arXiv:2610.24758, Section 3 and Conjecture 1.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
  • brgc_word_injectiveBinary reflected Gray encoding is injective on natural numbers.
  • brgc_word_inverseEncoding the n-bit inverse prefix-parity transform recovers the word.
Used by 5

The proof, explained

To show that the inverse Gray transform recovers t from its Gray code brgc_word t, we apply the injectivity of brgc_word, which reduces the problem to showing that applying brgc_word to both sides yields equal values. By brgc_word_inverse, the composition brgc_word (brgc_inverse n x) simplifies to x whenever x < 2 ^ n, leaving only the requirement that brgc_word t < 2 ^ n. This bound follows because brgc_word t is the bitwise XOR of t and t / 2, both of which are strictly bounded by 2 ^ n.

  1. It suffices to show that brgc_word t < 2 ^ n.

    Because brgc_word is injective (brgc_word_injective), the target equality brgc_inverse n (brgc_word t) = t holds if their images under brgc_word are equal. By brgc_word_inverse, brgc_word (brgc_inverse n x) = x holds for any x < 2 ^ n. Setting x = brgc_word t reduces the identity to proving that brgc_word t < 2 ^ n.

    lines 3–4

    uses brgc_word_injective, brgc_word_inverse

      apply brgc_word_injective
      apply brgc_word_inverse
  2. brgc_word t < 2 ^ n

    By definition, brgc_word t is the bitwise XOR t ^^^ (t / 2). The assumption ht gives t < 2 ^ n. Since t / 2 ≤ t by Nat.div_le_self, transitivity via lt_of_le_of_lt implies that t / 2 < 2 ^ n as well. Finally, Nat.xor_lt_two_pow concludes that the bitwise XOR of these two numbers is strictly less than 2 ^ n.

    line 5

    uses Nat.xor_lt_two_pow, lt_of_le_of_lt, Nat.div_le_self

      exact Nat.xor_lt_two_pow ht (lt_of_le_of_lt (Nat.div_le_self _ _) ht)
brgc_word_injective
The Gray-code encoding function brgc_word is injective: if brgc_word x = brgc_word y, then x = y.
brgc_word_inverse
For any n-bit integer x < 2 ^ n, the Gray-code word of the inverse transform of x is x; that is, brgc_word is a left inverse of brgc_inverse n on inputs below 2 ^ n.
Nat.xor_lt_two_pow
The bitwise XOR of two natural numbers strictly less than 2 ^ n is also strictly less than 2 ^ n.
lt_of_le_of_lt
If a ≤ b and b < c, then a < c (strict inequality is preserved by transitivity with a non-strict inequality).
Nat.div_le_self
Integer division of a natural number n by any k satisfies n / k ≤ 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 brgc_inverse_word {n t : ℕ} (ht : t < 2 ^ n) :    brgc_inverse n (brgc_word t) = t := by  apply brgc_word_injective  apply brgc_word_inverse  exact Nat.xor_lt_two_pow ht (lt_of_le_of_lt (Nat.div_le_self _ _) ht)
See it in the graphDiscuss this resultChallenge it