AFTD Auto-Formalizing Theoretical Domains

brgc_word_one_bit_iff_rank_reflection

theoremverified

Two Gray words differ exactly in bit k if and only if their ranks differ by exclusive-or with k+1 low one-bits.

Statement

theorem brgc_word_one_bit_iff_rank_reflection (t u k : ℕ) :
    brgc_word t ^^^ brgc_word u = 2 ^ k ↔
      t ^^^ u = 2 ^ (k + 1) - 1
Source
Supporting arithmetic and canonical-representative lemmas for OP-392, arXiv:2610.24758, Conjecture 1.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • brgc_word_xorBinary reflected Gray encoding preserves bitwise exclusive-or.
  • brgc_word_low_onesA rank consisting of k+1 low one-bits encodes the word with only bit k set.
  • brgc_word_injectiveBinary reflected Gray encoding is injective on natural numbers.
  • brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).

The proof, explained

The proof splits the equivalence into both directions. In each direction, it uses the fact that the binary reflected Gray code function distributes over bitwise XOR and maps a sequence of $k+1$ low ones to a single bit at index $k$. The forward implication then follows from injectivity of the Gray code mapping, while the reverse implication follows by direct rewriting.

  1. If the Gray words of $t$ and $u$ differ only at bit $k$, then their ranks differ by XOR with $2^{k+1} - 1$.

    We split the equivalence into two implications and first prove the forward direction. Assume $\mathrm{brgc\_word}(t) \oplus \mathrm{brgc\_word}(u) = 2^k$. Because $\mathrm{brgc\_word}$ is injective (`brgc_word_injective`), showing $t \oplus u = 2^{k+1} - 1$ reduces to showing that their Gray words match: $\mathrm{brgc\_word}(t \oplus u) = \mathrm{brgc\_word}(2^{k+1} - 1)$. By `brgc_word_xor`, the left-hand side is $\mathrm{brgc\_word}(t) \oplus \mathrm{brgc\_word}(u)$, which is $2^k$ by hypothesis. By `brgc_word_low_ones`, the right-hand side is also $2^k$, completing this direction.

    lines 4–7

    uses brgc_word_injective, brgc_word_xor, brgc_word_low_ones

      constructor
      · intro h
        apply brgc_word_injective
        rw [brgc_word_xor, h, brgc_word_low_ones]
  2. If the ranks $t$ and $u$ differ by XOR with $2^{k+1} - 1$, then their Gray words differ only at bit $k$.

    For the reverse direction, assume $t \oplus u = 2^{k+1} - 1$. Using `brgc_word_xor` in reverse rewrites the left-hand side $\mathrm{brgc\_word}(t) \oplus \mathrm{brgc\_word}(u)$ as $\mathrm{brgc\_word}(t \oplus u)$. Substituting the assumption gives $\mathrm{brgc\_word}(2^{k+1} - 1)$, which evaluates directly to $2^k$ by `brgc_word_low_ones`.

    lines 8–9

    uses brgc_word_xor, brgc_word_low_ones

      · intro h
        rw [← brgc_word_xor, h, brgc_word_low_ones]
brgc_word_injective
The Gray code function `brgc_word` is injective: equal Gray codes imply equal ranks.
brgc_word_xor
The Gray code function distributes over bitwise XOR: `brgc_word (t ^^^ u) = brgc_word t ^^^ brgc_word u`.
brgc_word_low_ones
The Gray code of a bitmask of $k + 1$ ones ($2^{k+1} - 1$) is a single bit at position $k$ ($2^k$).

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_one_bit_iff_rank_reflection (t u k : ℕ) :    brgc_word t ^^^ brgc_word u = 2 ^ k ↔      t ^^^ u = 2 ^ (k + 1) - 1 := by  constructor  · intro h    apply brgc_word_injective    rw [brgc_word_xor, h, brgc_word_low_ones]  · intro h    rw [← brgc_word_xor, h, brgc_word_low_ones]
See it in the graphDiscuss this resultChallenge it