brgc_word_inverse
Encoding the n-bit inverse prefix-parity transform recovers the word.
Statement
theorem brgc_word_inverse {n x : ℕ} (hx : x < 2 ^ n) :
brgc_word (brgc_inverse n x) = x- 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 3
- 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_xorBinary reflected Gray encoding preserves bitwise exclusive-or.
- Used by 8
- lexical_degree_seventeen_class_a_counterexampleThe lexical sequences a = (3,1,1,3,3,2,2,1) and b = (3,1,1,2,1,3,2,2,1) both have degree 16, are adjacent in the source lexical order…
- brgc_inverse_prefixThe inverse Gray rank of a high-bit prefix is the corresponding high-bit prefix of the inverse rank.
- 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…
- brgc_necklace_first_rank_exists_of_nonconstantEvery nonconstant binary word of length at least two has a first-occurrence Gray rank in its rotation class.
- brgc_necklace_first_rank_min_rotationsEvery rotation of a first-occurrence representative has inverse Gray rank at least its first-occurrence rank.
- 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…
- brgc_inverse_wordThe n-bit inverse prefix-parity transform recovers an n-bit Gray rank from its encoded word.
The proof, explained
The theorem is proved by induction on n, generalizing over x. The base case n = 0 holds trivially because x < 2^0 forces x = 0. In the inductive step, expanding the recursive definition of brgc_inverse and distributing brgc_word across XOR produces brgc_word x ^^^ brgc_word (brgc_inverse n (x / 2)). Applying the induction hypothesis to x / 2 replaces the second term with x / 2. Finally, unfolding brgc_word x = x ^^^ (x / 2) yields (x ^^^ (x / 2)) ^^^ (x / 2), which simplifies to x by XOR cancellation.
The base case n = 0 holds: if x < 2^0, then brgc_word (brgc_inverse 0 x) = x.
We proceed by induction on n, generalizing over x. In the base case n = 0, the assumption x < 2^0 = 1 forces x = 0. By definition, brgc_inverse 0 0 = 0 and brgc_word 0 = 0 ^^^ (0 / 2) = 0, so both sides evaluate to 0.
uses
brgc_inverse,brgc_wordinduction n generalizing x with | zero => have : x = 0 := by simpa using hx simp [this, brgc_inverse, brgc_word]
If x < 2^(n + 1), then x / 2 < 2^n.
Rewriting 2^(n + 1) as 2^n * 2 via pow_succ, the bound x < 2^n * 2 implies x / 2 < 2^n by integer division arithmetic (handled by omega). This guarantees that the induction hypothesis applies to x / 2.
uses
pow_succ| succ n ih => have hhalf : x / 2 < 2 ^ n := by rw [pow_succ] at hx omegabrgc_word (brgc_inverse (n + 1) x) reduces to brgc_word x ^^^ (x / 2).
By definition of brgc_inverse, brgc_inverse (n + 1) x = x ^^^ brgc_inverse n (x / 2). Distributing brgc_word over XOR using brgc_word_xor yields brgc_word x ^^^ brgc_word (brgc_inverse n (x / 2)). The induction hypothesis applied to x / 2 evaluates the second term to x / 2.
uses
brgc_inverse,brgc_word_xorrw [brgc_inverse, brgc_word_xor, ih hhalf]brgc_word x ^^^ (x / 2) = x, completing the inductive step.
Unfolding brgc_word x as x ^^^ (x / 2) gives (x ^^^ (x / 2)) ^^^ (x / 2). By the associativity of XOR (Nat.xor_assoc) and the identities y ^^^ y = 0 and x ^^^ 0 = x, the two identical terms cancel, leaving x.
uses
brgc_word,Nat.xor_assocsimp only [brgc_word] simp [Nat.xor_assoc]
brgc_inverse- the recursive inverse Gray code transform: brgc_inverse 0 x = 0 and brgc_inverse (n + 1) x = x ^^^ brgc_inverse n (x / 2)
brgc_word- the binary reflected Gray code encoding of t, defined as t ^^^ (t / 2)
brgc_word_xor- the Gray code encoding distributes over bitwise XOR: brgc_word (t ^^^ u) = brgc_word t ^^^ brgc_word u
pow_succ- powers of a base satisfy a ^ (n + 1) = a ^ n * a
Nat.xor_assoc- bitwise XOR on natural numbers is associative: (x ^^^ y) ^^^ z = x ^^^ (y ^^^ z)
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_word_inverse {n x : ℕ} (hx : x < 2 ^ n) : brgc_word (brgc_inverse n x) = x := by induction n generalizing x with | zero => have : x = 0 := by simpa using hx simp [this, brgc_inverse, brgc_word] | succ n ih => have hhalf : x / 2 < 2 ^ n := by rw [pow_succ] at hx omega rw [brgc_inverse, brgc_word_xor, ih hhalf] simp only [brgc_word] simp [Nat.xor_assoc]