brgc_word_xor
Binary reflected Gray encoding preserves bitwise exclusive-or.
Statement
theorem brgc_word_xor (t u : ℕ) :
brgc_word (t ^^^ u) = brgc_word t ^^^ brgc_word u- Source
- Supporting arithmetic and canonical-representative lemmas for OP-392, arXiv:2610.24758, Conjecture 1.
- Verified
- 25 Oct 2026
- Axioms
Quot.soundpropext- Built on 1
- brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
- Used by 4
- brgc_word_injectiveBinary reflected Gray encoding is injective on natural numbers.
- brgc_word_inverseEncoding the n-bit inverse prefix-parity transform recovers the word.
- brgc_word_one_bit_iff_rank_reflectionTwo Gray words differ exactly in bit k if and only if their ranks differ by exclusive-or with k+1 low one-bits.
- bitword_necklace_adjacent_of_brgc_rank_reflectionIf two Gray ranks differ by exclusive-or with k+1 low one-bits and k is less than the word length, their words are adjacent with rotation…
The proof, explained
The binary reflected Gray code of a natural number $n$ is defined as $n \oplus \lfloor n / 2 \rfloor$. The proof unfolds this definition and distributes division by 2 over bitwise exclusive-or. The two sides of the resulting equation contain the exact same terms combined by exclusive-or, so the equality follows immediately from the associativity and commutativity of exclusive-or.
The goal reduces to $(t \oplus u) \oplus (t / 2 \oplus u / 2) = (t \oplus t / 2) \oplus (u \oplus u / 2)$.
Unfolding the definition of `brgc_word` (which maps $n$ to $n \oplus \lfloor n / 2 \rfloor$) and applying `Nat.xor_div_two` distributes division by 2 across the exclusive-or on the left-hand side.
uses
Nat.xor_div_twosimp only [brgc_word, Nat.xor_div_two]Both sides are equal.
Both sides are exclusive-or combinations of the same four terms: $t$, $u$, $t / 2$, and $u / 2$. Because bitwise exclusive-or is associative and commutative, reordering and regrouping the terms proves the equality.
ac_rfl
Nat.xor_div_two- Integer division by 2 distributes over bitwise exclusive-or: $(a \oplus b) / 2 = (a / 2) \oplus (b / 2)$ for all natural numbers $a$ and $b$.
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_xor (t u : ℕ) : brgc_word (t ^^^ u) = brgc_word t ^^^ brgc_word u := by simp only [brgc_word, Nat.xor_div_two] ac_rfl