AFTD Auto-Formalizing Theoretical Domains

brgc_inverse_prefix

theoremverified

The inverse Gray rank of a high-bit prefix is the corresponding high-bit prefix of the inverse rank.

Statement

theorem brgc_inverse_prefix {n k x : ℕ} (hk : k ≤ n) (hx : x < 2 ^ n) :
    brgc_inverse n x / 2 ^ k = brgc_inverse (n - k) (x / 2 ^ k)
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 5
  • 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_word_div_powTaking a high-bit prefix commutes with binary reflected Gray encoding.
  • brgc_word_injectiveBinary reflected Gray encoding is injective on natural numbers.
  • brgc_word_inverseEncoding the n-bit inverse prefix-parity transform recovers the word.
  • brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
Used by 3

The proof, explained

The proof shows that applying the injective Gray code function brgc_word to both sides yields equal values. First, the prefix x / 2 ^ k is shown to satisfy the bound x / 2 ^ k < 2 ^ (n - k). Then, applying brgc_word to both sides, the left-hand side commutes with division by 2 ^ k via brgc_word_div_pow, and both sides evaluate to x / 2 ^ k using the left-inverse identity brgc_word_inverse.

  1. x / 2 ^ k < 2 ^ (n - k)

    We establish that the shifted prefix x / 2 ^ k fits within n - k bits. By Nat.div_lt_iff_lt_mul and the fact that 2 ^ k is positive (Nat.two_pow_pos), this inequality is equivalent to x < 2 ^ (n - k) * 2 ^ k. Using pow_add, the product 2 ^ (n - k) * 2 ^ k rewrites to 2 ^ (n - k + k), whose exponent simplifies to n via linear arithmetic (omega) because k ≤ n. This matches the hypothesis hx : x < 2 ^ n.

    lines 3–8

    uses Nat.div_lt_iff_lt_mul, Nat.two_pow_pos, pow_add

      have hprefix : x / 2 ^ k < 2 ^ (n - k) := by
        apply (Nat.div_lt_iff_lt_mul (Nat.two_pow_pos _)).mpr
        convert hx using 1
        rw [← pow_add]
        congr 1
        omega
  2. It suffices to show that brgc_word (brgc_inverse n x / 2 ^ k) = brgc_word (brgc_inverse (n - k) (x / 2 ^ k)).

    Because the Gray code function brgc_word is injective (brgc_word_injective), two values are equal if their Gray codes are equal.

    line 9

    uses brgc_word_injective

      apply brgc_word_injective
  3. The Gray codes of both sides are equal to x / 2 ^ k, closing the goal.

    On the left-hand side, brgc_word commutes with division by 2 ^ k by brgc_word_div_pow, transforming the expression into brgc_word (brgc_inverse n x) / 2 ^ k; since x < 2 ^ n, brgc_word_inverse simplifies this to x / 2 ^ k. On the right-hand side, since x / 2 ^ k < 2 ^ (n - k) by hprefix, brgc_word_inverse similarly simplifies brgc_word (brgc_inverse (n - k) (x / 2 ^ k)) directly to x / 2 ^ k. Both sides reduce to x / 2 ^ k.

    line 10

    uses brgc_word_div_pow, brgc_word_inverse

      rw [← brgc_word_div_pow, brgc_word_inverse hx, brgc_word_inverse hprefix]
Nat.div_lt_iff_lt_mul
For a positive divisor k, x / k < y is equivalent to x < y * k.
Nat.two_pow_pos
Powers of two are strictly positive: 0 < 2 ^ w for any natural number w.
pow_add
Exponents add under multiplication: a ^ (m + n) = a ^ m * a ^ n.
brgc_word_injective
The binary reflected Gray code function brgc_word is injective.
brgc_word_div_pow
The Gray code function commutes with division by 2 ^ k: brgc_word t / 2 ^ k = brgc_word (t / 2 ^ k).
brgc_word_inverse
For any x < 2 ^ n, brgc_word is a left inverse to brgc_inverse n: brgc_word (brgc_inverse n x) = x.

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_inverse_prefix {n k x : ℕ} (hk : k ≤ n) (hx : x < 2 ^ n) :    brgc_inverse n x / 2 ^ k = brgc_inverse (n - k) (x / 2 ^ k) := by  have hprefix : x / 2 ^ k < 2 ^ (n - k) := by    apply (Nat.div_lt_iff_lt_mul (Nat.two_pow_pos _)).mpr    convert hx using 1    rw [← pow_add]    congr 1    omega  apply brgc_word_injective  rw [← brgc_word_div_pow, brgc_word_inverse hx, brgc_word_inverse hprefix]
See it in the graphDiscuss this resultChallenge it