brgc_word_div_pow
Taking a high-bit prefix commutes with binary reflected Gray encoding.
Statement
theorem brgc_word_div_pow (t k : ℕ) :
brgc_word t / 2 ^ k = brgc_word (t / 2 ^ k)- Source
- Prefix-parity inverse and supporting arithmetic for OP-392, arXiv:2610.24758, Section 3 and 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_inverse_prefixThe inverse Gray rank of a high-bit prefix is the corresponding high-bit prefix of the inverse rank.
- 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
The identity states that shifting a binary reflected Gray code word right by $k$ bits (integer division by $2^k$) is the same as computing the Gray code word of the shifted input. By definition, $\mathrm{brgc\_word}(t) = t \oplus (t / 2)$. Dividing by $2^k$ distributes over bitwise XOR and combines successive integer divisions, reducing both sides to $(t / 2^k) \oplus (t / D)$ with denominator $D = 2 \cdot 2^k$ on the left and $D = 2^k \cdot 2$ on the right. The proof is completed by the commutativity of multiplication.
$(t / 2^k) \oplus (t / (2 \cdot 2^k)) = (t / 2^k) \oplus (t / (2^k \cdot 2))$
Unfold the definition of $\mathrm{brgc\_word}(t) = t \oplus (t / 2)$ on both sides. On the left-hand side, division by $2^k$ distributes over bitwise XOR using Nat.xor_div_two_pow, giving $(t / 2^k) \oplus ((t / 2) / 2^k)$, and the nested division $(t / 2) / 2^k$ simplifies to $t / (2 \cdot 2^k)$ via Nat.div_div_eq_div_mul. On the right-hand side, the nested division $(t / 2^k) / 2$ simplifies to $t / (2^k \cdot 2)$ using Nat.div_div_eq_div_mul.
uses
Nat.xor_div_two_pow,Nat.div_div_eq_div_mulsimp only [brgc_word, Nat.xor_div_two_pow, Nat.div_div_eq_div_mul]$\mathrm{brgc\_word}(t) / 2^k = \mathrm{brgc\_word}(t / 2^k)$
Rewrite the denominator $2 \cdot 2^k$ on the left-hand side to $2^k \cdot 2$ using the commutativity of multiplication (Nat.mul_comm). The two sides become syntactically identical, which closes the goal.
uses
Nat.mul_commrw [Nat.mul_comm 2 (2 ^ k)]
Nat.xor_div_two_pow- Integer division by $2^n$ distributes over bitwise XOR: $(a \oplus b) / 2^n = (a / 2^n) \oplus (b / 2^n)$ for any natural numbers $a$, $b$, and $n$.
Nat.div_div_eq_div_mul- Successive integer divisions can be combined into division by the product of the divisors: $(m / n) / k = m / (n \cdot k)$ for all natural numbers $m$, $n$, and $k$.
Nat.mul_comm- Multiplication of natural numbers is commutative: $n \cdot m = m \cdot n$ for all natural numbers $n$ and $m$.
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_pow (t k : ℕ) : brgc_word t / 2 ^ k = brgc_word (t / 2 ^ k) := by simp only [brgc_word, Nat.xor_div_two_pow, Nat.div_div_eq_div_mul] rw [Nat.mul_comm 2 (2 ^ k)]