AFTD Auto-Formalizing Theoretical Domains

brgc_word_eq_zero_iff

theoremverified

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

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.

  1. 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.

    lines 2–4

    uses Nat.eq_of_xor_eq_zero

      constructor
      · intro h
        have hsame : t = t / 2 := Nat.eq_of_xor_eq_zero h
  2. 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.

    lines 5–7

    uses Nat.pos_of_ne_zero, Nat.div_lt_self

        by_contra hn
        have := Nat.div_lt_self (Nat.pos_of_ne_zero hn) (show 1 < 2 by decide)
        omega
  3. 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.

    lines 8–9

      · 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

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
See it in the graphDiscuss this resultChallenge it