brgc_word_low_ones
A rank consisting of k+1 low one-bits encodes the word with only bit k set.
Statement
theorem brgc_word_low_ones (k : ℕ) :
brgc_word (2 ^ (k + 1) - 1) = 2 ^ k- 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 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
- alpha_binary_prefix_inverse_parityThe inverse Gray rank of the prefix has the parity of the number of encoded one bits, namely the cell count.
- brgc_word_one_bit_iff_rank_reflectionTwo Gray words differ exactly in bit k if and only if their ranks differ by exclusive-or with k+1 low one-bits.
- bitword_necklace_adjacent_of_brgc_rank_reflectionIf 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…
- brgc_inverse_alpha_binary_prefix_consThe inverse Gray rank of x :: xs equals 2^xs.sum * (2^x - 1) + (2^xs.sum - 1 - brgc_inverse xs.sum (alpha_binary_prefix xs)).
The proof, explained
The proof evaluates the binary reflected Gray code function, defined by brgc_word(t) = t ^^^ (t / 2), at t = 2^(k + 1) - 1. Integer division reduces the term to (2^(k + 1) - 1) ^^^ (2^k - 1). The result 2^k is then established by bitwise extensionality: the i-th bit of 2^n - 1 is 1 exactly when i < n, so the boolean XOR of the bits of 2^(k + 1) - 1 and 2^k - 1 is 1 if and only if i = k, which matches the bit representation of 2^k.
(2^(k + 1) - 1) / 2 = 2^k - 1
Using `pow_succ` to rewrite 2^(k + 1) as 2 * 2^k and `Nat.two_pow_pos` to note that 2^k > 0, linear integer arithmetic (`omega`) computes the integer division (2^(k + 1) - 1) / 2 = (2 * 2^k - 1) / 2 = 2^k - 1.
uses
pow_succ,Nat.two_pow_poshave hpow : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega have hp : 0 < 2 ^ k := Nat.two_pow_pos _ have hd : (2 ^ (k + 1) - 1) / 2 = 2 ^ k - 1 := by omega
(2^(k + 1) - 1) ^^^ (2^k - 1) = 2^k
Unfolding the definition of `brgc_word` (which is t ^^^ (t / 2)) on 2^(k + 1) - 1 and rewriting with the division identity from the previous step simplifies the goal to showing (2^(k + 1) - 1) ^^^ (2^k - 1) = 2^k.
unfold brgc_word rw [hd]
For every bit index i, (i < k + 1) ^^ (i < k) = (k = i) as boolean values.
By `Nat.eq_of_testBit_eq`, it suffices to show that the i-th bit of (2^(k + 1) - 1) ^^^ (2^k - 1) equals the i-th bit of 2^k for any arbitrary bit index i. Simplifying with `Nat.testBit_xor`, `Nat.testBit_two_pow_sub_one`, and `Nat.testBit_two_pow` translates the bit values of 2^n - 1 and 2^k into the boolean conditions (i < n) and (k = i), reducing the goal to a boolean equation.
uses
Nat.eq_of_testBit_eq,Nat.testBit_xor,Nat.testBit_two_pow_sub_one,Nat.testBit_two_powapply Nat.eq_of_testBit_eq intro i simp only [Nat.testBit_xor, Nat.testBit_two_pow_sub_one, Nat.testBit_two_pow]
The boolean bit identity holds when i < k.
When i < k, linear arithmetic gives i < k + 1 and k ≠ i. Both conditions i < k + 1 and i < k evaluate to true, so their boolean XOR is true ^^ true = false. Since k = i is false, both sides evaluate to false.
by_cases hi : i < k · have hi' : i < k + 1 := by omega have hne : k ≠ i := by omega simp [hi, hi', hne]
The boolean bit identity holds when i = k.
When k = i, substituting i = k gives k < k + 1 (true) and k < k (false). The boolean XOR true ^^ false simplifies to true, matching the right-hand side k = k (true).
· by_cases heq : k = i · subst i simp
The boolean bit identity holds when i > k.
When ¬(i < k) and k ≠ i, linear arithmetic gives ¬(i < k + 1). Both i < k + 1 and i < k evaluate to false, so their boolean XOR false ^^ false is false, which matches the right-hand side k = i (false). This completes the case analysis and the proof.
· have hi' : ¬ i < k + 1 := by omega simp [hi, hi', heq]
pow_succ- In any monoid, a^(n+1) = a^n * a.
Nat.two_pow_pos- Powers of two are strictly positive: 2^w > 0 for all w in ℕ.
Nat.eq_of_testBit_eq- Two natural numbers are equal if their binary representations have the same bit at every position.
Nat.testBit_xor- The i-th bit of a bitwise XOR x ^^^ y is the boolean XOR of the i-th bit of x and the i-th bit of y.
Nat.testBit_two_pow_sub_one- The i-th bit of 2^n - 1 is 1 if and only if i < n.
Nat.testBit_two_pow- The m-th bit of 2^n is 1 if and only if n = m.
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_low_ones (k : ℕ) : brgc_word (2 ^ (k + 1) - 1) = 2 ^ k := by have hpow : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega have hp : 0 < 2 ^ k := Nat.two_pow_pos _ have hd : (2 ^ (k + 1) - 1) / 2 = 2 ^ k - 1 := by omega unfold brgc_word rw [hd] apply Nat.eq_of_testBit_eq intro i simp only [Nat.testBit_xor, Nat.testBit_two_pow_sub_one, Nat.testBit_two_pow] by_cases hi : i < k · have hi' : i < k + 1 := by omega have hne : k ≠ i := by omega simp [hi, hi', hne] · by_cases heq : k = i · subst i simp · have hi' : ¬ i < k + 1 := by omega simp [hi, hi', heq]