brgc_inverse_word
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
- brgc_necklace_first_rank_rotation_maxRotating a first-occurrence representative right once gives a representative of maximum inverse Gray rank in its rotation class; the…
- brgc_necklace_first_rank_min_rotationsEvery rotation of a first-occurrence representative has inverse Gray rank at least its first-occurrence rank.
- 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_inverse_rotate_tent_formulaIn inverse Gray-rank coordinates, cyclic left rotation is the two-branch integer tent map, with the rank parity carried along.
- brgc_inverse_alpha_binary_prefix_consThe 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)).
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.
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.
uses
brgc_word_injective,brgc_word_inverseapply brgc_word_injective apply brgc_word_inverse
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.
uses
Nat.xor_lt_two_pow,lt_of_le_of_lt,Nat.div_le_selfexact 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
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 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)