bitword_necklace_adjacent_of_brgc_rank_reflection
If two Gray ranks differ by exclusive-or with k+1 low one-bits and k is less than the word length, their words are adjacent with rotation zero.
Statement
theorem bitword_necklace_adjacent_of_brgc_rank_reflection (n t u k : ℕ)
(hk : k < n) (h : t ^^^ u = 2 ^ (k + 1) - 1) :
bitword_necklace_adjacent n (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
Classical.choiceQuot.soundpropext- Built on 5
- 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.
- bitword_necklace_adjacentThe necklaces of the n-bit words x and y are adjacent in the necklace graph Q_n: some rotation of x differs from y in exactly one bit.
- bitword_rotateCyclic rotation of an n-bit word x (a number below 2^n) by one position: the word is shifted up and its top bit moves to the bottom.
- 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 theorem shows that if two ranks t and u differ by bitwise XOR with a mask of k+1 ones, their corresponding binary reflected Gray code words are necklace-adjacent. The proof instantiates the definition of necklace adjacency with rotation r = 0 and bit index i = k. Since the Gray code operation distributes over bitwise XOR, the difference between the two words reduces to evaluating the Gray code of 2^(k+1) - 1, which equals 2^k.
To show necklace adjacency, it suffices to prove that rotating the first word by 0 steps differs from the second word by 2^k.
Necklace adjacency requires finding a rotation amount r < n and a bit position i < n such that the r-step rotation of the first word differs from the second word by 2^i (in bitwise XOR). We choose r = 0 (which satisfies 0 < n since k < n) and i = k (which satisfies k < n by hypothesis hk).
refine ⟨0, by omega, k, hk, ?_⟩
Rotating zero times simplifies to the identity, leaving brgc_word t ^^^ brgc_word u = 2 ^ k.
Iterating a function zero times produces the identity function (Function.iterate_zero), which leaves brgc_word t unchanged (id_eq).
uses
Function.iterate_zero,id_eqsimp only [Function.iterate_zero, id_eq]The Gray words of t and u differ by exactly 2^k, completing the proof.
Because the Gray code mapping distributes over bitwise XOR (brgc_word_xor), the left-hand side brgc_word t ^^^ brgc_word u rewrites to brgc_word (t ^^^ u). By assumption h, t ^^^ u = 2^(k + 1) - 1. Finally, brgc_word_low_ones establishes that the Gray code of 2^(k + 1) - 1 is precisely 2^k.
uses
brgc_word_xor,brgc_word_low_onesrw [← brgc_word_xor, h, brgc_word_low_ones]
Function.iterate_zero- Iterating any function zero times yields the identity function: f^[0] = id.
id_eq- The identity function returns its argument unchanged: id a = a.
brgc_word_xor- The binary reflected Gray code word map preserves bitwise XOR: the Gray word of t ⊕ u is the XOR of their individual Gray words.
brgc_word_low_ones- The binary reflected Gray code of a mask of k+1 ones (2^(k+1) - 1) is a single bit at position k (2^k).
- The inequality 0 < n required for the rotation amount r = 0 is discharged automatically by omega using the hypothesis k < n.
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 bitword_necklace_adjacent_of_brgc_rank_reflection (n t u k : ℕ) (hk : k < n) (h : t ^^^ u = 2 ^ (k + 1) - 1) : bitword_necklace_adjacent n (brgc_word t) (brgc_word u) := by refine ⟨0, by omega, k, hk, ?_⟩ simp only [Function.iterate_zero, id_eq] rw [← brgc_word_xor, h, brgc_word_low_ones]