AFTD Auto-Formalizing Theoretical Domains

brgc_word_div_two

theoremverified

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

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)$.

  1. $\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`).

    line 3

    uses Nat.xor_div_two

      exact 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)$.

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_two (t : ℕ) :    brgc_word t / 2 = brgc_word (t / 2) := by  exact Nat.xor_div_two
See it in the graphDiscuss this resultChallenge it