AFTD Auto-Formalizing Theoretical Domains

brgc_word_div_pow

theoremverified

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.

  1. $(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.

    line 3

    uses Nat.xor_div_two_pow, Nat.div_div_eq_div_mul

      simp only [brgc_word, Nat.xor_div_two_pow, Nat.div_div_eq_div_mul]
  2. $\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.

    line 4

    uses Nat.mul_comm

      rw [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

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)]
See it in the graphDiscuss this resultChallenge it