brgc_word_eq_zero_iff
The zero word is encoded exactly by rank zero.
Statement
theorem brgc_word_eq_zero_iff (t : ℕ) : brgc_word t = 0 ↔ t = 0- 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 1
- brgc_word_injectiveBinary reflected Gray encoding is injective on natural numbers.
The proof, explained
The proof establishes the equivalence in two directions. In the forward direction, by definition brgc_word t = t ^^^ (t / 2), so vanishing XOR implies t = t / 2; if t were non-zero, t / 2 would be strictly less than t, a contradiction that forces t = 0. In the reverse direction, brgc_word 0 = 0 ^^^ (0 / 2) = 0 holds immediately by definition.
If brgc_word t = 0, then t = t / 2.
To prove the bi-implication, we split it into forward and reverse directions. In the forward direction, we assume brgc_word t = 0. By definition, brgc_word t = t ^^^ (t / 2). Since the bitwise XOR of t and t / 2 is zero, Nat.eq_of_xor_eq_zero implies that t = t / 2.
uses
Nat.eq_of_xor_eq_zeroconstructor · intro h have hsame : t = t / 2 := Nat.eq_of_xor_eq_zero h
t = 0
We assume for contradiction that t ≠ 0. Then t is strictly positive by Nat.pos_of_ne_zero. Because 1 < 2, dividing t by 2 strictly decreases it (t / 2 < t) by Nat.div_lt_self. This contradicts t = t / 2, which omega uses to finish the contradiction.
uses
Nat.pos_of_ne_zero,Nat.div_lt_selfby_contra hn have := Nat.div_lt_self (Nat.pos_of_ne_zero hn) (show 1 < 2 by decide) omega
If t = 0, then brgc_word t = 0.
For the reverse direction, we assume t = 0. Substituting 0 for t evaluates brgc_word 0 to 0 ^^^ (0 / 2) = 0, which holds by definition and reflexivity.
· rintro rfl rfl
Nat.eq_of_xor_eq_zero- If the bitwise XOR of two natural numbers is zero, the two numbers are equal.
Nat.div_lt_self- A strictly positive natural number divided by an integer greater than 1 is strictly less than itself.
Nat.pos_of_ne_zero- A natural number that is not zero is strictly positive.
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_eq_zero_iff (t : ℕ) : brgc_word t = 0 ↔ t = 0 := by constructor · intro h have hsame : t = t / 2 := Nat.eq_of_xor_eq_zero h by_contra hn have := Nat.div_lt_self (Nat.pos_of_ne_zero hn) (show 1 < 2 by decide) omega · rintro rfl rfl