AFTD Auto-Formalizing Theoretical Domains

brgc_word_xor

theoremverified

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

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.

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

    line 3

    uses Nat.xor_div_two

      simp only [brgc_word, Nat.xor_div_two]
  2. 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.

    line 4

      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

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