brgc_word_lt_two_pow
An n-bit rank encodes an n-bit word.
Statement
theorem brgc_word_lt_two_pow {n t : ℕ} (ht : t < 2 ^ n) :
brgc_word t < 2 ^ n- 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
- brgc_necklace_first_rank_unique_of_rotationTwo first-occurrence Gray ranks representing the same nonconstant necklace are equal.
- brgc_necklace_first_rank_exists_of_nonconstantEvery nonconstant binary word of length at least two has a first-occurrence Gray rank in its rotation class.
- brgc_necklace_first_rank_word_oddFor length at least two, the first nonconstant representative in Gray order has final bit one.
- brgc_inverse_rotate_tent_formulaIn inverse Gray-rank coordinates, cyclic left rotation is the two-branch integer tent map, with the rank parity carried along.
The proof, explained
The binary reflected Gray code word at rank t is defined as t ^^^ (t / 2). Since integer division satisfies t / 2 ≤ t < 2^n, both t and t / 2 are strictly bounded by 2^n. The claim then follows because the bitwise XOR of two numbers strictly less than 2^n is itself strictly less than 2^n.
brgc_word t < 2 ^ n
By definition, brgc_word t is the bitwise XOR t ^^^ (t / 2). Since integer division satisfies t / 2 ≤ t by Nat.div_le_self, chaining this with the hypothesis t < 2^n (ht) using lt_of_le_of_lt gives t / 2 < 2^n. Finally, Nat.xor_lt_two_pow applies to both t < 2^n and t / 2 < 2^n to conclude that t ^^^ (t / 2) < 2^n.
uses
Nat.xor_lt_two_pow,lt_of_le_of_lt,Nat.div_le_selfexact Nat.xor_lt_two_pow ht (lt_of_le_of_lt (Nat.div_le_self _ _) ht)
Nat.xor_lt_two_pow- the bitwise XOR of two natural numbers strictly bounded by 2^n is also strictly less than 2^n
lt_of_le_of_lt- if a ≤ b and b < c, then a < c
Nat.div_le_self- natural number division satisfies n / k ≤ n for all n and 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_lt_two_pow {n t : ℕ} (ht : t < 2 ^ n) : brgc_word t < 2 ^ n := by exact Nat.xor_lt_two_pow ht (lt_of_le_of_lt (Nat.div_le_self _ _) ht)