AFTD Auto-Formalizing Theoretical Domains

brgc_word_inverse

theoremverified

Encoding the n-bit inverse prefix-parity transform recovers the word.

Statement

theorem brgc_word_inverse {n x : ℕ} (hx : x < 2 ^ n) :
    brgc_word (brgc_inverse n x) = x
Source
Prefix-parity inverse and supporting arithmetic for OP-392, arXiv:2610.24758, Section 3 and Conjecture 1.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • brgc_inverseThe inverse prefix-parity transform on n-bit binary words, computed as the exclusive-or of all right shifts by less than n.
  • brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
  • brgc_word_xorBinary reflected Gray encoding preserves bitwise exclusive-or.
Used by 8

The proof, explained

The theorem is proved by induction on n, generalizing over x. The base case n = 0 holds trivially because x < 2^0 forces x = 0. In the inductive step, expanding the recursive definition of brgc_inverse and distributing brgc_word across XOR produces brgc_word x ^^^ brgc_word (brgc_inverse n (x / 2)). Applying the induction hypothesis to x / 2 replaces the second term with x / 2. Finally, unfolding brgc_word x = x ^^^ (x / 2) yields (x ^^^ (x / 2)) ^^^ (x / 2), which simplifies to x by XOR cancellation.

  1. The base case n = 0 holds: if x < 2^0, then brgc_word (brgc_inverse 0 x) = x.

    We proceed by induction on n, generalizing over x. In the base case n = 0, the assumption x < 2^0 = 1 forces x = 0. By definition, brgc_inverse 0 0 = 0 and brgc_word 0 = 0 ^^^ (0 / 2) = 0, so both sides evaluate to 0.

    lines 3–6

    uses brgc_inverse, brgc_word

      induction n generalizing x with
      | zero =>
        have : x = 0 := by simpa using hx
        simp [this, brgc_inverse, brgc_word]
  2. If x < 2^(n + 1), then x / 2 < 2^n.

    Rewriting 2^(n + 1) as 2^n * 2 via pow_succ, the bound x < 2^n * 2 implies x / 2 < 2^n by integer division arithmetic (handled by omega). This guarantees that the induction hypothesis applies to x / 2.

    lines 7–10

    uses pow_succ

      | succ n ih =>
        have hhalf : x / 2 < 2 ^ n := by
          rw [pow_succ] at hx
          omega
  3. brgc_word (brgc_inverse (n + 1) x) reduces to brgc_word x ^^^ (x / 2).

    By definition of brgc_inverse, brgc_inverse (n + 1) x = x ^^^ brgc_inverse n (x / 2). Distributing brgc_word over XOR using brgc_word_xor yields brgc_word x ^^^ brgc_word (brgc_inverse n (x / 2)). The induction hypothesis applied to x / 2 evaluates the second term to x / 2.

    line 11

    uses brgc_inverse, brgc_word_xor

        rw [brgc_inverse, brgc_word_xor, ih hhalf]
  4. brgc_word x ^^^ (x / 2) = x, completing the inductive step.

    Unfolding brgc_word x as x ^^^ (x / 2) gives (x ^^^ (x / 2)) ^^^ (x / 2). By the associativity of XOR (Nat.xor_assoc) and the identities y ^^^ y = 0 and x ^^^ 0 = x, the two identical terms cancel, leaving x.

    lines 12–13

    uses brgc_word, Nat.xor_assoc

        simp only [brgc_word]
        simp [Nat.xor_assoc]
brgc_inverse
the recursive inverse Gray code transform: brgc_inverse 0 x = 0 and brgc_inverse (n + 1) x = x ^^^ brgc_inverse n (x / 2)
brgc_word
the binary reflected Gray code encoding of t, defined as t ^^^ (t / 2)
brgc_word_xor
the Gray code encoding distributes over bitwise XOR: brgc_word (t ^^^ u) = brgc_word t ^^^ brgc_word u
pow_succ
powers of a base satisfy a ^ (n + 1) = a ^ n * a
Nat.xor_assoc
bitwise XOR on natural numbers is associative: (x ^^^ y) ^^^ z = x ^^^ (y ^^^ z)

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_inverse {n x : ℕ} (hx : x < 2 ^ n) :    brgc_word (brgc_inverse n x) = x := by  induction n generalizing x with  | zero =>    have : x = 0 := by simpa using hx    simp [this, brgc_inverse, brgc_word]  | succ n ih =>    have hhalf : x / 2 < 2 ^ n := by      rw [pow_succ] at hx      omega    rw [brgc_inverse, brgc_word_xor, ih hhalf]    simp only [brgc_word]    simp [Nat.xor_assoc]
See it in the graphDiscuss this resultChallenge it