AFTD Auto-Formalizing Theoretical Domains

brgc_inverse_concat

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • bitThe real embedding of a Boolean value, sending false to 0 and true to 1.
Used by 9

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.

  1. 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.

    lines 3–9

      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
  2. 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.

    lines 13–17

      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]
  3. Lemma 3: Inverse Gray rank with a zero appended

    By definition and algebraic manipulation using brgc_aux_xor_two_mul_add_bit.

    lines 22–31

      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]
  4. Lemma 4: Inverse Gray rank under power-of-two shift

    By induction on k, using brgc_aux_inverse_append_zero at each step.

    lines 37–56

      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
  5. Lemma 5: Disjoint-bit XOR equals addition

    By comparing bits at each index i using testBit.

    lines 60–67

      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]
  6. Lemma 6: XOR with mask is subtraction

    By comparing bits at each index i using testBit.

    lines 71–81

      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']
  7. Lemma 7: Stability of inverse Gray rank

    By injectivity of brgc_word and brgc_word_inverse.

    lines 85–86

      apply brgc_word_injective
      rw [brgc_word_inverse hm, brgc_word_inverse hn]
  8. Lemma 8: Upper bound on concatenation

    By arithmetic on powers of two.

    lines 90–91

      rw [pow_add]
      nlinarith [Nat.two_pow_pos k]
  9. 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.

    lines 97–109

      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

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)]
See it in the graphDiscuss this resultChallenge it