brgc_word_div_two
The binary reflected Gray encoding commutes with division by two.
Statement
theorem brgc_word_div_two (t : ℕ) :
brgc_word t / 2 = brgc_word (t / 2)- 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 2
- brgc_necklace_first_rank_word_oddFor length at least two, the first nonconstant representative in Gray order has final bit one.
- 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.
The proof, explained
By definition, the binary reflected Gray code word of $t$ is $t \oplus \lfloor t / 2 \rfloor$. Integer division by two shifts bits to the right by one position, which distributes over the bitwise XOR operation. Applying this distributivity property (`Nat.xor_div_two`) directly yields $(t \oplus (t / 2)) / 2 = (t / 2) \oplus ((t / 2) / 2) = \text{brgc\_word}(t / 2)$.
$\text{brgc\_word}(t) / 2 = \text{brgc\_word}(t / 2)$ for any $t \in \mathbb{N}$
By definition, the binary reflected Gray code word is $\text{brgc\_word}(t) = t \oplus (t / 2)$. Substituting this into the equation, the claim is $(t \oplus (t / 2)) / 2 = (t / 2) \oplus ((t / 2) / 2)$, which is an immediate instance of the fact that division by 2 distributes over bitwise XOR (`Nat.xor_div_two`).
uses
Nat.xor_div_twoexact Nat.xor_div_two
Nat.xor_div_two- Integer division by 2 distributes over bitwise XOR: for all $a, b \in \mathbb{N}$, $(a \oplus b) / 2 = (a / 2) \oplus (b / 2)$.
- The definition of `brgc_word` as $t \mapsto t \oplus \lfloor t / 2 \rfloor$ is unfolded definitionally, allowing `Nat.xor_div_two` to close the goal without an explicit rewriting step.
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_div_two (t : ℕ) : brgc_word t / 2 = brgc_word (t / 2) := by exact Nat.xor_div_two