brgc_inverse_prefix
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
- brgc_inverse_flip_preserves_cut_maxIf an n-bit word has strictly greater inverse Gray rank than every nontrivial cyclic cut, toggling its last bit has at least as great an…
- brgc_necklace_first_rank_rotation_maxRotating a first-occurrence representative right once gives a representative of maximum inverse Gray rank in its rotation class; the…
- brgc_inverse_rotate_tent_formulaIn inverse Gray-rank coordinates, cyclic left rotation is the two-branch integer tent map, with the rank parity carried along.
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.
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.
uses
Nat.div_lt_iff_lt_mul,Nat.two_pow_pos,pow_addhave 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
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.
uses
brgc_word_injectiveapply brgc_word_injectiveThe 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.
uses
brgc_word_div_pow,brgc_word_inverserw [← 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
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_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]