AFTD Auto-Formalizing Theoretical Domains

brgc_word_injective

theoremverified

Binary reflected Gray encoding is injective on natural numbers.

Statement

theorem brgc_word_injective : Function.Injective brgc_word
Source
Supporting arithmetic and canonical-representative lemmas for OP-392, arXiv:2610.24758, Conjecture 1.
Verified
25 Oct 2026
Axioms
Quot.soundpropext
Built on 3
  • brgc_word_xorBinary reflected Gray encoding preserves bitwise exclusive-or.
  • brgc_word_eq_zero_iffThe zero word is encoded exactly by rank zero.
  • brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
Used by 5
  • brgc_inverse_prefixThe inverse Gray rank of a high-bit prefix is the corresponding high-bit prefix of the inverse rank.
  • brgc_inverse_concatThe inverse Gray rank of a concatenation has the prefix inverse rank followed by the suffix inverse rank, complemented exactly when the…
  • brgc_local_reflection_generator_obstructionTwo strict maximum-rank primitive generators whose proposed local generator reflection is not maximum-rank; an obstruction to a naive…
  • 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.
  • brgc_inverse_wordThe n-bit inverse prefix-parity transform recovers an n-bit Gray rank from its encoded word.

The proof, explained

To show that the binary reflected Gray code is injective, assume brgc_word t = brgc_word u for natural numbers t and u. Proving t = u reduces to showing that t ^^^ u = 0, which by the characterization of zero Gray codes is equivalent to brgc_word (t ^^^ u) = 0. Because Gray encoding distributes over bitwise XOR, this word evaluates to brgc_word t ^^^ brgc_word u = brgc_word u ^^^ brgc_word u = 0, completing the proof.

  1. To prove injectivity, assume given natural numbers t and u such that brgc_word t = brgc_word u; it suffices to show t = u.

    By definition, a function is injective if equal outputs imply equal inputs. We fix arbitrary natural numbers t and u and assume the hypothesis h that their Gray code words are equal.

    line 2

      intro t u h
  2. It suffices to prove that brgc_word (t ^^^ u) = 0.

    Two natural numbers are equal whenever their bitwise XOR is zero (Nat.eq_of_xor_eq_zero). In turn, by the forward implication of brgc_word_eq_zero_iff, a number is zero whenever its Gray code is zero. Applying these two reductions in succession reduces t = u to brgc_word (t ^^^ u) = 0.

    lines 3–4

    uses Nat.eq_of_xor_eq_zero, brgc_word_eq_zero_iff

      apply Nat.eq_of_xor_eq_zero
      apply (brgc_word_eq_zero_iff _).mp
  3. brgc_word (t ^^^ u) = 0, completing the proof that t = u.

    Since the Gray code preserves bitwise XOR (brgc_word_xor), brgc_word (t ^^^ u) expands to brgc_word t ^^^ brgc_word u. Substituting the equality brgc_word t = brgc_word u from hypothesis h yields brgc_word u ^^^ brgc_word u, which evaluates to 0 by Nat.xor_self.

    line 5

    uses brgc_word_xor, Nat.xor_self

      rw [brgc_word_xor, h, Nat.xor_self]
Nat.eq_of_xor_eq_zero
If the bitwise XOR of two natural numbers is 0, then the numbers are equal: x ^^^ y = 0 implies x = y.
brgc_word_eq_zero_iff
A natural number's binary reflected Gray code is zero if and only if the number itself is zero.
brgc_word_xor
The binary reflected Gray code distributes over bitwise XOR: brgc_word (t ^^^ u) = brgc_word t ^^^ brgc_word u.
Nat.xor_self
The bitwise XOR of any natural number with itself is zero: x ^^^ x = 0.

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_injective : Function.Injective brgc_word := by  intro t u h  apply Nat.eq_of_xor_eq_zero  apply (brgc_word_eq_zero_iff _).mp  rw [brgc_word_xor, h, Nat.xor_self]
See it in the graphDiscuss this resultChallenge it