brgc_word_one_bit_iff_rank_reflection
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.
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.
uses
brgc_word_injective,brgc_word_xor,brgc_word_low_onesconstructor · intro h apply brgc_word_injective rw [brgc_word_xor, h, brgc_word_low_ones]
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`.
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
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_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]