brgc_inverse_concat
The inverse Gray rank of a concatenation has the prefix inverse rank followed by the suffix inverse rank, complemented exactly when the prefix has odd parity.
Statement
theorem brgc_inverse_concat {m k a b : ℕ} (ha : a < 2 ^ m) (hb : b < 2 ^ k) : brgc_inverse (m + k) (2 ^ k * a + b) = 2 ^ k * brgc_inverse m a + if brgc_inverse m a % 2 = 0 then brgc_inverse k b else 2 ^ k - 1 - brgc_inverse k b
- 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 8
- 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_inverse_lt_two_powThe inverse prefix-parity transform of an n-bit word has an n-bit rank.
- 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).
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - bitThe real embedding of a Boolean value, sending false to 0 and true to 1.
- Used by 9
- bitword_rotate_iterate_cutCyclically rotating an n-bit nonconstant word left by a positions exchanges its prefix of length a and its suffix of length b, where a+b=n.
- brgc_inverse_flip_preserves_rotation_maxToggling the last bit of an aperiodic nonconstant word that maximizes its inverse Gray rank over all rotations again maximizes that rank,…
- alpha_binary_completion_inverseCompleting the prefix to even or odd Hamming parity gives the two consecutive inverse Gray ranks 2q and 2q+1.
- alpha_lexical_lt_iff_inverse_prefixOn equal-length positive encodings, lexical order is exactly inverse Gray-rank order.
- 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…
- alpha_binary_prefix_inverse_parityThe inverse Gray rank of the prefix has the parity of the number of encoded one bits, namely the cell count.
- 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.
- brgc_inverse_alpha_binary_prefix_consThe inverse Gray rank of x :: xs equals 2^xs.sum * (2^x - 1) + (2^xs.sum - 1 - brgc_inverse xs.sum (alpha_binary_prefix xs)).
The proof, explained
The proof establishes that the inverse Gray rank distributes over concatenation by viewing concatenation as a disjoint XOR of the shifted prefix and the suffix. Applying the inverse Gray rank, which distributes over XOR, the prefix shifts to produce the prefix rank along with a mask depending on its parity, while the suffix rank remains stable. Case analysis on the parity of the prefix rank then shows that when even, the suffix rank is added directly, and when odd, it is XORed with the mask, yielding the complement.
Lemma 1: Gray inverse distributes over XOR
By induction on n. In the base case n = 0, both sides are 0. In the inductive step, using Nat.xor_div_two and the induction hypothesis, associativity and commutativity of XOR closes the goal.
induction n generalizing x y with | zero => simp [brgc_inverse] | succ n ih => change (x ^^^ y) ^^^ brgc_inverse n ((x ^^^ y) / 2) = (x ^^^ brgc_inverse n (x / 2)) ^^^ (y ^^^ brgc_inverse n (y / 2)) rw [Nat.xor_div_two, ih] ac_rfl
Lemma 2: XOR of shifted values with a bit
By expressing the arithmetic operations as bit operations and evaluating the cases b = 0 and b = 1.
have hx : 2 * x = Nat.bit false x := by simp [Nat.bit, two_mul] have hy : 2 * y + b = Nat.bit (decide (b = 1)) y := by rcases (show b = 0 ∨ b = 1 by omega) with rfl | rfl <;> simp [Nat.bit, two_mul] rw [hx, hy, Nat.xor_bit] rcases (show b = 0 ∨ b = 1 by omega) with rfl | rfl <;> simp [Nat.bit, two_mul]
Lemma 3: Inverse Gray rank with a zero appended
By definition and algebraic manipulation using brgc_aux_xor_two_mul_add_bit.
rw [brgc_inverse] have hd : 2 * x / 2 = x := by omega rw [hd] let q := brgc_inverse n x have hxq : x = q ^^^ (q / 2) := (brgc_word_inverse hx).symm have hq : q = 2 * (q / 2) + q % 2 := by omega change 2 * x ^^^ q = 2 * q + q % 2 conv_lhs => rw [hq] rw [brgc_aux_xor_two_mul_add_bit _ _ _ (Nat.mod_lt _ (by decide)), hxq, Nat.xor_xor_cancel_right]
Lemma 4: Inverse Gray rank under power-of-two shift
By induction on k, using brgc_aux_inverse_append_zero at each step.
induction k with | zero => simp | succ k ih => have hbound : 2 ^ k * a < 2 ^ (m + k) := by rw [pow_add] nlinarith [Nat.two_pow_pos k] have hword : 2 ^ (k + 1) * a = 2 * (2 ^ k * a) := by rw [pow_succ] ring have hexp : m + (k + 1) = (m + k) + 1 := by omega rw [hword, hexp, brgc_aux_inverse_append_zero hbound, ih.2, ih.1] have hpred : 2 ^ (k + 1) - 1 = 2 * (2 ^ k - 1) + 1 := by rw [pow_succ] have := Nat.two_pow_pos k omega constructor · rw [hpred, pow_succ] ring · have hmod : brgc_inverse m a % 2 < 2 := Nat.mod_lt _ (by decide) omega
Lemma 5: Disjoint-bit XOR equals addition
By comparing bits at each index i using testBit.
apply Nat.eq_of_testBit_eq intro i rw [Nat.testBit_xor, Nat.testBit_two_pow_mul, Nat.testBit_two_pow_mul_add a hb] by_cases hi : k ≤ i · have hb' : b.testBit i = false := Nat.testBit_lt_two_pow (lt_of_lt_of_le hb (Nat.pow_le_pow_right (by decide) hi)) simp [hi, hb'] · simp [hi]
Lemma 6: XOR with mask is subtraction
By comparing bits at each index i using testBit.
apply Nat.eq_of_testBit_eq intro i rw [Nat.testBit_xor, Nat.testBit_two_pow_sub_one] have heq : 2 ^ k - 1 - b = 2 ^ k - (b + 1) := by omega rw [heq, Nat.testBit_two_pow_sub_succ hb] by_cases hi : i < k · simp [hi] · have hb' : b.testBit i = false := Nat.testBit_lt_two_pow (lt_of_lt_of_le hb (Nat.pow_le_pow_right (by decide) (Nat.le_of_not_gt hi))) simp [hi, hb']
Lemma 7: Stability of inverse Gray rank
By injectivity of brgc_word and brgc_word_inverse.
apply brgc_word_injective rw [brgc_word_inverse hm, brgc_word_inverse hn]
Lemma 8: Upper bound on concatenation
By arithmetic on powers of two.
rw [pow_add] nlinarith [Nat.two_pow_pos k]
Main Theorem: Inverse Gray rank of concatenation
By decomposing concatenation as XOR, using the shift lemma and stability, and case splitting on the parity of the prefix rank.
have hb' : b < 2 ^ (m + k) := lt_of_lt_of_le hb (Nat.pow_le_pow_right (by decide) (by omega)) rw [← brgc_aux_xor_high_low a b k hb, brgc_aux_inverse_xor, (brgc_aux_inverse_shift m k a ha).1, brgc_aux_inverse_stable hb' hb] have hir : brgc_inverse k b < 2 ^ k := brgc_inverse_lt_two_pow hb rcases Nat.mod_two_eq_zero_or_one (brgc_inverse m a) with hq | hq · simp only [hq, zero_mul, add_zero, ite_true] exact brgc_aux_xor_high_low _ _ _ hir · have hq0 : brgc_inverse m a % 2 ≠ 0 := by omega simp only [hq, one_mul, show (1 : ℕ) ≠ 0 by decide, ite_false] have hmask : 2 ^ k - 1 < 2 ^ k := by have := Nat.two_pow_pos k; omega rw [← brgc_aux_xor_high_low _ _ _ hmask, Nat.xor_assoc, brgc_aux_xor_mask_sub hir, brgc_aux_xor_high_low _ _ _ (by omega)]
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_aux_inverse_xor (n x y : ℕ) : brgc_inverse n (x ^^^ y) = brgc_inverse n x ^^^ brgc_inverse n y := by induction n generalizing x y with | zero => simp [brgc_inverse] | succ n ih => change (x ^^^ y) ^^^ brgc_inverse n ((x ^^^ y) / 2) = (x ^^^ brgc_inverse n (x / 2)) ^^^ (y ^^^ brgc_inverse n (y / 2)) rw [Nat.xor_div_two, ih] ac_rfltheorem brgc_aux_xor_two_mul_add_bit (x y b : ℕ) (hb : b < 2) : (2 * x) ^^^ (2 * y + b) = 2 * (x ^^^ y) + b := by have hx : 2 * x = Nat.bit false x := by simp [Nat.bit, two_mul] have hy : 2 * y + b = Nat.bit (decide (b = 1)) y := by rcases (show b = 0 ∨ b = 1 by omega) with rfl | rfl <;> simp [Nat.bit, two_mul] rw [hx, hy, Nat.xor_bit] rcases (show b = 0 ∨ b = 1 by omega) with rfl | rfl <;> simp [Nat.bit, two_mul]theorem brgc_aux_inverse_append_zero {n x : ℕ} (hx : x < 2 ^ n) : brgc_inverse (n + 1) (2 * x) = 2 * brgc_inverse n x + brgc_inverse n x % 2 := by rw [brgc_inverse] have hd : 2 * x / 2 = x := by omega rw [hd] let q := brgc_inverse n x have hxq : x = q ^^^ (q / 2) := (brgc_word_inverse hx).symm have hq : q = 2 * (q / 2) + q % 2 := by omega change 2 * x ^^^ q = 2 * q + q % 2 conv_lhs => rw [hq] rw [brgc_aux_xor_two_mul_add_bit _ _ _ (Nat.mod_lt _ (by decide)), hxq, Nat.xor_xor_cancel_right]theorem brgc_aux_inverse_shift (m k a : ℕ) (ha : a < 2 ^ m) : brgc_inverse (m + k) (2 ^ k * a) = 2 ^ k * brgc_inverse m a + (brgc_inverse m a % 2) * (2 ^ k - 1) ∧ brgc_inverse (m + k) (2 ^ k * a) % 2 = brgc_inverse m a % 2 := by induction k with | zero => simp | succ k ih => have hbound : 2 ^ k * a < 2 ^ (m + k) := by rw [pow_add] nlinarith [Nat.two_pow_pos k] have hword : 2 ^ (k + 1) * a = 2 * (2 ^ k * a) := by rw [pow_succ] ring have hexp : m + (k + 1) = (m + k) + 1 := by omega rw [hword, hexp, brgc_aux_inverse_append_zero hbound, ih.2, ih.1] have hpred : 2 ^ (k + 1) - 1 = 2 * (2 ^ k - 1) + 1 := by rw [pow_succ] have := Nat.two_pow_pos k omega constructor · rw [hpred, pow_succ] ring · have hmod : brgc_inverse m a % 2 < 2 := Nat.mod_lt _ (by decide) omegatheorem brgc_aux_xor_high_low (a b k : ℕ) (hb : b < 2 ^ k) : (2 ^ k * a) ^^^ b = 2 ^ k * a + b := by apply Nat.eq_of_testBit_eq intro i rw [Nat.testBit_xor, Nat.testBit_two_pow_mul, Nat.testBit_two_pow_mul_add a hb] by_cases hi : k ≤ i · have hb' : b.testBit i = false := Nat.testBit_lt_two_pow (lt_of_lt_of_le hb (Nat.pow_le_pow_right (by decide) hi)) simp [hi, hb'] · simp [hi]theorem brgc_aux_xor_mask_sub {b k : ℕ} (hb : b < 2 ^ k) : (2 ^ k - 1) ^^^ b = 2 ^ k - 1 - b := by apply Nat.eq_of_testBit_eq intro i rw [Nat.testBit_xor, Nat.testBit_two_pow_sub_one] have heq : 2 ^ k - 1 - b = 2 ^ k - (b + 1) := by omega rw [heq, Nat.testBit_two_pow_sub_succ hb] by_cases hi : i < k · simp [hi] · have hb' : b.testBit i = false := Nat.testBit_lt_two_pow (lt_of_lt_of_le hb (Nat.pow_le_pow_right (by decide) (Nat.le_of_not_gt hi))) simp [hi, hb']theorem brgc_aux_inverse_stable {m n x : ℕ} (hm : x < 2 ^ m) (hn : x < 2 ^ n) : brgc_inverse m x = brgc_inverse n x := by apply brgc_word_injective rw [brgc_word_inverse hm, brgc_word_inverse hn]theorem brgc_aux_concat_bound {m k a b : ℕ} (ha : a < 2 ^ m) (hb : b < 2 ^ k) : 2 ^ k * a + b < 2 ^ (m + k) := by rw [pow_add] nlinarith [Nat.two_pow_pos k]theorem brgc_inverse_concat {m k a b : ℕ} (ha : a < 2 ^ m) (hb : b < 2 ^ k) : brgc_inverse (m + k) (2 ^ k * a + b) = 2 ^ k * brgc_inverse m a + if brgc_inverse m a % 2 = 0 then brgc_inverse k b else 2 ^ k - 1 - brgc_inverse k b := by have hb' : b < 2 ^ (m + k) := lt_of_lt_of_le hb (Nat.pow_le_pow_right (by decide) (by omega)) rw [← brgc_aux_xor_high_low a b k hb, brgc_aux_inverse_xor, (brgc_aux_inverse_shift m k a ha).1, brgc_aux_inverse_stable hb' hb] have hir : brgc_inverse k b < 2 ^ k := brgc_inverse_lt_two_pow hb rcases Nat.mod_two_eq_zero_or_one (brgc_inverse m a) with hq | hq · simp only [hq, zero_mul, add_zero, ite_true] exact brgc_aux_xor_high_low _ _ _ hir · have hq0 : brgc_inverse m a % 2 ≠ 0 := by omega simp only [hq, one_mul, show (1 : ℕ) ≠ 0 by decide, ite_false] have hmask : 2 ^ k - 1 < 2 ^ k := by have := Nat.two_pow_pos k; omega rw [← brgc_aux_xor_high_low _ _ _ hmask, Nat.xor_assoc, brgc_aux_xor_mask_sub hir, brgc_aux_xor_high_low _ _ _ (by omega)]