AFTD Auto-Formalizing Theoretical Domains

brgc_inverse_flip_preserves_cut_max

theoremverifiedformalization

If 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 inverse Gray rank as every nontrivial cyclic cut of the toggled word.

Statement

theorem brgc_inverse_flip_preserves_cut_max (n x : ℕ) (hx : x < 2 ^ n)
    (hstrict : ∀ a b u v : ℕ, 0 < a → 0 < b → a + b = n →
      u < 2 ^ a → v < 2 ^ b → x = 2 ^ b * u + v →
      brgc_inverse n (2 ^ a * v + u) < brgc_inverse n x) :
    ∀ a b u v : ℕ, 0 < a → 0 < b → a + b = n →
      u < 2 ^ a → v < 2 ^ b → x ^^^ 1 = 2 ^ b * u + v →
      brgc_inverse n (2 ^ a * v + u) ≤ brgc_inverse n (x ^^^ 1)
Formalizes
Gray-ordered Binary Necklaces (2007), Theorem 3.6, in the equivalent convention of maximal forward Gray rank; the rotation form adds nonconstant-word hypotheses.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • 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_concatThe inverse Gray rank of a concatenation has the prefix inverse rank followed by the suffix inverse rank, complemented exactly when the…
  • brgc_inverse_lt_two_powThe inverse prefix-parity transform of an n-bit word has an n-bit rank.
  • brgc_inverse_prefixThe inverse Gray rank of a high-bit prefix is the corresponding high-bit prefix of the inverse rank.
  • brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
  • brgc_word_inverseEncoding the n-bit inverse prefix-parity transform recovers the word.
Used by 3

The proof, explained

The theorem is proved by contradiction: assuming that toggling the last bit of $x$ produces a cyclic cut with strictly greater inverse Gray code rank, we show that this cut's rank would also strictly exceed that of $x$. Because cyclic cuts preserve the parity of the inverse Gray code rank, the cut's rank and the flipped rank have identical parities, forcing the high-bit rank quotient of $x$ to be trapped between and equal to one of the ranks of the suffix $v$ or its toggle $v \oplus 1$. Since the high-bit rank must equal one of these values, the reflected Gray code suffix-ordering rule implies that the rank of the prefix $u$ is strictly less than that of the remainder $z = x \bmod 2^a$. Finally, applying the assumed strict cut maximality of $x$ to the cut formed by this remainder yields the reverse inequality $\text{rank}_a(z) \le \text{rank}_a(u)$, reaching a contradiction.

  1. For $a < 2^m$ and $b, c < 2^k$, the inverse Gray rank of $2^k a + b$ is strictly less than that of $2^k a + c$ if and only if $\text{rank}_k(b) < \text{rank}_k(c)$ when the prefix rank $\text{rank}_m(a)$ is even, and $\text{rank}_k(c) < \text{rank}_k(b)$ when $\text{rank}_m(a)$ is odd.

    Rewriting both ranks using the concatenation formula `brgc_inverse_concat` splits into two cases based on the parity of $\text{rank}_m(a)$: an even prefix rank preserves the suffix ordering, while an odd prefix rank inverts it through the reflection $2^k - 1 - \text{rank}_k(\cdot)$. Linear arithmetic simplifies each case.

    lines 6–9

    uses brgc_inverse_concat, brgc_inverse_lt_two_pow

      rw [brgc_inverse_concat ha hb, brgc_inverse_concat ha hc]
      have hb' := brgc_inverse_lt_two_pow hb
      have hc' := brgc_inverse_lt_two_pow hc
      split_ifs <;> omega
  2. $\text{rank}_n(0) = 0$, $\text{rank}_n(1) = 1$ for $n > 0$, and toggling the last bit toggles the last bit of the inverse Gray rank: $\text{rank}_n(x \oplus 1) = \text{rank}_n(x) \oplus 1$.

    The base cases follow by induction and rewriting for positive $n = k + 1$. The flip identity follows from the XOR-linearity of `brgc_inverse` together with $\text{rank}_n(1) = 1$.

    lines 10–23

    uses Nat.exists_eq_succ_of_ne_zero, brgc_aux_inverse_xor, brgc_aux_inverse_one

    @[simp] theorem brgc_aux_inverse_zero (n : ℕ) : brgc_inverse n 0 = 0 := by
      induction n with
      | zero => rfl
      | succ n ih => simp [brgc_inverse, ih]
    
    theorem brgc_aux_inverse_one {n : ℕ} (hn : 0 < n) : brgc_inverse n 1 = 1 := by
      obtain ⟨n, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n ≠ 0)
      simp [brgc_inverse]
    
    theorem brgc_aux_inverse_flip {n : ℕ} (hn : 0 < n) (x : ℕ) :
        brgc_inverse n (x ^^^ 1) = brgc_inverse n x ^^^ 1 := by
      rw [brgc_aux_inverse_xor, brgc_aux_inverse_one hn]
    
  3. Toggling the last bit of a concatenated word $2^k a + b$ (with $k > 0$ and $b < 2^k$) affects only the lower block: $(2^k a + b) \oplus 1 = 2^k a + (b \oplus 1)$.

    Since $b < 2^k$ and $1 < 2^k$, the high-order bits $2^k a$ are bitwise orthogonal to both $b$ and 1, so the operations combine associatively and simplify back to addition.

    lines 24–29

    uses Nat.one_lt_two_pow, brgc_aux_xor_high_low, Nat.xor_assoc, Nat.xor_lt_two_pow

    theorem brgc_aux_concat_flip {k a b : ℕ} (hk : 0 < k) (hb : b < 2 ^ k) :
        (2 ^ k * a + b) ^^^ 1 = 2 ^ k * a + (b ^^^ 1) := by
      have h1 : 1 < 2 ^ k := Nat.one_lt_two_pow (by omega)
      rw [← brgc_aux_xor_high_low a b k hb, Nat.xor_assoc,
        brgc_aux_xor_high_low a (b ^^^ 1) k (Nat.xor_lt_two_pow hb h1)]
    
  4. The parity of $\text{rank}_{m+k}(2^k a + b)$ equals the XOR of the parities of $\text{rank}_m(a)$ and $\text{rank}_k(b)$, and is invariant under swapping the two blocks: $\text{rank}_{m+k}(2^k a + b) \equiv \text{rank}_{k+m}(2^m b + a) \pmod 2$.

    Expressing the concatenation as a bitwise XOR and applying XOR-linearity of `brgc_inverse` decomposes the rank modulo 2 into the XOR of the components. The parity swap invariance then follows from the commutativity of XOR.

    lines 30–47

    uses lt_of_lt_of_le, Nat.pow_le_pow_right, brgc_aux_xor_high_low, brgc_aux_inverse_xor, Nat.xor_mod_two_pow, brgc_aux_inverse_shift, brgc_aux_inverse_stable, brgc_aux_inverse_concat_mod_two, Nat.xor_comm

    theorem brgc_aux_inverse_concat_mod_two {m k a b : ℕ} (ha : a < 2 ^ m) (hb : b < 2 ^ k) :
        brgc_inverse (m + k) (2 ^ k * a + b) % 2 =
          (brgc_inverse m a % 2) ^^^ (brgc_inverse k b % 2) := 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]
      rw [show (brgc_inverse (m + k) (2 ^ k * a) ^^^ brgc_inverse (m + k) b) % 2 =
          brgc_inverse (m + k) (2 ^ k * a) % 2 ^^^ brgc_inverse (m + k) b % 2 from
            Nat.xor_mod_two_pow (n := 1)]
      rw [(brgc_aux_inverse_shift m k a ha).2, brgc_aux_inverse_stable hb' hb]
    
    theorem brgc_aux_inverse_concat_parity_swap {m k a b : ℕ}
        (ha : a < 2 ^ m) (hb : b < 2 ^ k) :
        brgc_inverse (m + k) (2 ^ k * a + b) % 2 =
          brgc_inverse (k + m) (2 ^ m * b + a) % 2 := by
      rw [brgc_aux_inverse_concat_mod_two ha hb, brgc_aux_inverse_concat_mod_two hb ha]
      exact Nat.xor_comm _ _
    
  5. Toggling the last bit of $q$ produces a value within distance 1 of $q$ and with opposite parity; consequently, if $q \oplus 1 < r$ and $r$ has the same parity as $q \oplus 1$, then $q < r$.

    For even $q$, $q \oplus 1 = q + 1$; for odd $q$, $q \oplus 1 = q - 1$. In either case $|(q \oplus 1) - q| \le 1$ and the parity alternates. If $q \oplus 1 < r$ and they share parity, then $q \oplus 1 \le r - 2$, which implies $q \le (q \oplus 1) + 1 < r$.

    lines 48–61

    uses Nat.mod_two_eq_zero_or_one, Nat.xor_one_of_even, Nat.even_iff.mpr, Nat.odd_iff.mpr, Nat.xor_one_of_odd, brgc_aux_xor_one_bounds

    theorem brgc_aux_xor_one_bounds (q : ℕ) :
        q ≤ (q ^^^ 1) + 1 ∧ (q ^^^ 1) ≤ q + 1 ∧ (q ^^^ 1) % 2 ≠ q % 2 := by
      rcases Nat.mod_two_eq_zero_or_one q with hq | hq
      · rw [Nat.xor_one_of_even (Nat.even_iff.mpr hq)]
        omega
      · have ho : Odd q := Nat.odd_iff.mpr hq
        rw [Nat.xor_one_of_odd ho]
        omega
    
    theorem brgc_aux_lt_of_flip_lt_of_parity (q r : ℕ) (h : q ^^^ 1 < r)
        (hp : r % 2 = (q ^^^ 1) % 2) : q < r := by
      obtain ⟨h1, h2, h3⟩ := brgc_aux_xor_one_bounds q
      omega
    
  6. The prefix projection satisfies $\text{rank}_{m+k}(2^k a + b) / 2^k = \text{rank}_m(a)$, the word prefix satisfies $x / 2^k < 2^m$ when $x < 2^{m+k}$, and the inverse Gray code map $\text{rank}_n$ is injective.

    The prefix identity follows from `brgc_inverse_prefix` and integer division on $2^k a + b$. The word bound follows by multiplying through by $2^k$. Injectivity follows because the encoding map `brgc_word` is a left inverse to `brgc_inverse`.

    lines 62–79

    uses brgc_inverse_prefix, brgc_aux_concat_bound, Nat.mul_add_div, Nat.two_pow_pos, Nat.div_eq_of_lt, Nat.div_lt_iff_lt_mul, pow_add, congrArg, brgc_word_inverse

    theorem brgc_aux_prefix_rank {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 := by
      have hh := brgc_inverse_prefix (show k ≤ m + k by omega) (brgc_aux_concat_bound ha hb)
      have hdiv : (2 ^ k * a + b) / 2 ^ k = a := by
        rw [Nat.mul_add_div (Nat.two_pow_pos _), Nat.div_eq_of_lt hb]
        omega
      simpa [hdiv] using hh
    
    theorem brgc_aux_word_prefix_bound {m k x : ℕ} (hx : x < 2 ^ (m + k)) :
        x / 2 ^ k < 2 ^ m := by
      apply (Nat.div_lt_iff_lt_mul (Nat.two_pow_pos _)).mpr
      rwa [← pow_add]
    
    theorem brgc_aux_inverse_inj {n x y : ℕ} (hx : x < 2 ^ n) (hy : y < 2 ^ n)
        (h : brgc_inverse n x = brgc_inverse n y) : x = y := by
      have hh := congrArg brgc_word h
      rwa [brgc_word_inverse hx, brgc_word_inverse hy] at hh
    
  7. Decompose $x$ as $2^b u + (v \oplus 1)$ corresponding to the cut of $x \oplus 1 = 2^b u + v$.

    Fix an arbitrary non-trivial cut of $x \oplus 1$ into prefix $u$ of length $a$ and suffix $v$ of length $b$ (with $a, b > 0$ and $a + b = n$). Toggling the last bit on both sides via `brgc_aux_concat_flip` yields $x = 2^b u + (v \oplus 1)$, with $v \oplus 1 < 2^b$ because $b > 0$.

    lines 80–93

    uses Nat.xor_lt_two_pow, Nat.one_lt_two_pow, congrArg, brgc_aux_concat_flip

    theorem brgc_inverse_flip_preserves_cut_max (n x : ℕ) (hx : x < 2 ^ n)
        (hstrict : ∀ a b u v : ℕ, 0 < a → 0 < b → a + b = n →
          u < 2 ^ a → v < 2 ^ b → x = 2 ^ b * u + v →
          brgc_inverse n (2 ^ a * v + u) < brgc_inverse n x) :
        ∀ a b u v : ℕ, 0 < a → 0 < b → a + b = n →
          u < 2 ^ a → v < 2 ^ b → x ^^^ 1 = 2 ^ b * u + v →
          brgc_inverse n (2 ^ a * v + u) ≤ brgc_inverse n (x ^^^ 1) := by
      intro a b u v ha hb hab hu hv hsplit
      have hn : 0 < n := by omega
      have hvf : v ^^^ 1 < 2 ^ b :=
        Nat.xor_lt_two_pow hv (Nat.one_lt_two_pow (by omega))
      have hxsplit : x = 2 ^ b * u + (v ^^^ 1) := by
        have hh := congrArg (fun z : ℕ => z ^^^ 1) hsplit
        simpa [brgc_aux_concat_flip hb hv] using hh
  8. Assuming for contradiction that the cut $2^a v + u$ of $x \oplus 1$ has strictly greater inverse Gray rank than $x \oplus 1$, its rank also strictly exceeds that of $x$, while the rank of $2^a (v \oplus 1) + u$ is strictly less than that of $x$.

    Suppose $\text{rank}_n(x \oplus 1) < \text{rank}_n(2^a v + u)$. Since $x = 2^b u + (v \oplus 1)$, the cut maximality hypothesis for $x$ implies $\text{rank}_n(2^a (v \oplus 1) + u) < \text{rank}_n(x)$. Furthermore, cyclic cuts preserve rank parity by `brgc_aux_inverse_concat_parity_swap`, so $\text{rank}_n(2^a v + u) \equiv \text{rank}_n(x \oplus 1) \equiv \text{rank}_n(x) \oplus 1 \pmod 2$. Since $\text{rank}_n(x) \oplus 1 < \text{rank}_n(2^a v + u)$ and their parities match, `brgc_aux_lt_of_flip_lt_of_parity` implies $\text{rank}_n(x) < \text{rank}_n(2^a v + u)$.

    lines 94–105

    uses brgc_aux_inverse_concat_parity_swap, brgc_aux_inverse_flip, brgc_aux_lt_of_flip_lt_of_parity

      by_contra hnot
      have hbad : brgc_inverse n (x ^^^ 1) < brgc_inverse n (2 ^ a * v + u) := by omega
      have hlow := hstrict a b u (v ^^^ 1) ha hb hab hu hvf hxsplit
      have hpar : brgc_inverse n (2 ^ a * v + u) % 2 =
          (brgc_inverse n x ^^^ 1) % 2 := by
        calc
          _ = brgc_inverse n (2 ^ b * u + v) % 2 := by
            simpa only [hab, show b + a = n by omega] using (brgc_aux_inverse_concat_parity_swap hu hv).symm
          _ = brgc_inverse n (x ^^^ 1) % 2 := by rw [hsplit]
          _ = _ := by rw [brgc_aux_inverse_flip hn]
      have hhigh : brgc_inverse n x < brgc_inverse n (2 ^ a * v + u) :=
        brgc_aux_lt_of_flip_lt_of_parity _ _ (by simpa [brgc_aux_inverse_flip hn] using hbad) hpar
  9. $\text{rank}_b(v) \oplus 1 \le \text{rank}_n(x) / 2^a \le \text{rank}_b(v)$.

    Dividing the inequalities $\text{rank}_n(2^a (v \oplus 1) + u) < \text{rank}_n(x)$ and $\text{rank}_n(x) < \text{rank}_n(2^a v + u)$ by $2^a$ using `Nat.div_le_div_right`, and evaluating the high-bit quotients via `brgc_aux_prefix_rank`, gives $\text{rank}_b(v \oplus 1) \le \text{rank}_n(x) / 2^a \le \text{rank}_b(v)$. Rewriting $\text{rank}_b(v \oplus 1)$ as $\text{rank}_b(v) \oplus 1$ by `brgc_aux_inverse_flip` establishes the bounds.

    lines 106–118

    uses Nat.div_le_div_right, Nat.le_of_lt, brgc_aux_prefix_rank, brgc_aux_inverse_flip

      have hqlo : brgc_inverse b (v ^^^ 1) ≤ brgc_inverse n x / 2 ^ a := by
        have hh := Nat.div_le_div_right (Nat.le_of_lt hlow) (c := 2 ^ a)
        have he := brgc_aux_prefix_rank hvf hu
        have hba : b + a = n := by omega
        rw [hba] at he
        rwa [he] at hh
      have hqhi : brgc_inverse n x / 2 ^ a ≤ brgc_inverse b v := by
        have hh := Nat.div_le_div_right (Nat.le_of_lt hhigh) (c := 2 ^ a)
        have he := brgc_aux_prefix_rank hv hu
        have hba : b + a = n := by omega
        rw [hba] at he
        rwa [he] at hh
      rw [brgc_aux_inverse_flip hb] at hqlo
  10. $\text{rank}_b(v)$ is odd, $\text{rank}_b(v \oplus 1)$ is even, and $\text{rank}_n(x) / 2^a$ equals either $\text{rank}_b(v \oplus 1)$ or $\text{rank}_b(v)$.

    If $\text{rank}_b(v)$ were even, then $\text{rank}_b(v) \oplus 1 = \text{rank}_b(v) + 1$, contradicting the previous lower bound. Thus $\text{rank}_b(v)$ is odd, which in turn means $\text{rank}_b(v \oplus 1) = \text{rank}_b(v) - 1$ is even. Because $\text{rank}_n(x) / 2^a$ is an integer trapped between $\text{rank}_b(v) - 1$ and $\text{rank}_b(v)$, it must be equal to one of these two values.

    lines 119–131

    uses Nat.mod_two_eq_zero_or_one, Nat.xor_one_of_even, Nat.even_iff.mpr, brgc_aux_inverse_flip, Nat.xor_one_of_odd, Nat.odd_iff.mpr, brgc_aux_xor_one_bounds

      have hvodd : brgc_inverse b v % 2 = 1 := by
        rcases Nat.mod_two_eq_zero_or_one (brgc_inverse b v) with heven | hodd
        · rw [Nat.xor_one_of_even (Nat.even_iff.mpr heven)] at hqlo
          omega
        · exact hodd
      have hvfpar : brgc_inverse b (v ^^^ 1) % 2 = 0 := by
        rw [brgc_aux_inverse_flip hb, Nat.xor_one_of_odd (Nat.odd_iff.mpr hvodd)]
        omega
      have hqc : brgc_inverse n x / 2 ^ a = brgc_inverse b (v ^^^ 1) ∨
          brgc_inverse n x / 2 ^ a = brgc_inverse b v := by
        rw [brgc_aux_inverse_flip hb]
        obtain ⟨h1, h2, _⟩ := brgc_aux_xor_one_bounds (brgc_inverse b v)
        omega
  11. Decompose $x$ as $2^a e + z$ with $e = x / 2^a < 2^b$, $z = x \bmod 2^a < 2^a$, and $\text{rank}_n(x) / 2^a = \text{rank}_b(e)$.

    We perform division of $x$ by $2^a$, defining $e = x / 2^a$ and $z = x \bmod 2^a$. Then $e < 2^b$ by `brgc_aux_word_prefix_bound` and $z < 2^a$ by `Nat.mod_lt`. Applying `brgc_aux_prefix_rank` shows that the high-bit rank quotient $\text{rank}_n(x) / 2^a$ is exactly $\text{rank}_b(e)$.

    lines 132–142

    uses brgc_aux_word_prefix_bound, Nat.add_comm, Nat.mod_lt, Nat.two_pow_pos, Nat.div_add_mod, brgc_aux_prefix_rank

      let e := x / 2 ^ a
      let z := x % 2 ^ a
      have he : e < 2 ^ b := by
        apply brgc_aux_word_prefix_bound
        simpa [Nat.add_comm b a, hab] using hx
      have hz : z < 2 ^ a := Nat.mod_lt _ (Nat.two_pow_pos _)
      have hxez : x = 2 ^ a * e + z := (Nat.div_add_mod x (2 ^ a)).symm
      have hqe : brgc_inverse n x / 2 ^ a = brgc_inverse b e := by
        rw [hxez]
        simpa only [show b + a = n by omega] using brgc_aux_prefix_rank he hz
      have hue : brgc_inverse a u < brgc_inverse a z := by
  12. $\text{rank}_a(u) < \text{rank}_a(z)$.

    By the two-way alternative, $\text{rank}_b(e)$ equals either $\text{rank}_b(v \oplus 1)$ or $\text{rank}_b(v)$, so by injectivity of `brgc_inverse`, $e = v \oplus 1$ or $e = v$. If $e = v \oplus 1$, the inequality `hlow` compares two concatenations with prefix $v \oplus 1$; since $\text{rank}_b(v \oplus 1)$ is even, `brgc_aux_inverse_concat_lt_iff` preserves suffix order, yielding $\text{rank}_a(u) < \text{rank}_a(z)$. If $e = v$, `hhigh` compares two concatenations with prefix $v$; since $\text{rank}_b(v)$ is odd, the suffix order is reversed, again yielding $\text{rank}_a(u) < \text{rank}_a(z)$.

    lines 143–155

    uses brgc_aux_inverse_inj, brgc_aux_inverse_concat_lt_iff

        rcases hqc with hc | hc
        · have heq : e = v ^^^ 1 := brgc_aux_inverse_inj he hvf (hqe.symm.trans hc)
          have hh : brgc_inverse (b + a) (2 ^ a * (v ^^^ 1) + u) <
              brgc_inverse (b + a) (2 ^ a * (v ^^^ 1) + z) := by
            simpa [show b + a = n by omega, hxez, heq] using hlow
          have hh' := (brgc_aux_inverse_concat_lt_iff hvf hu hz).mp hh
          simpa [hvfpar] using hh'
        · have heq : e = v := brgc_aux_inverse_inj he hv (hqe.symm.trans hc)
          have hh : brgc_inverse (b + a) (2 ^ a * v + z) <
              brgc_inverse (b + a) (2 ^ a * v + u) := by
            simpa [show b + a = n by omega, hxez, heq] using hhigh
          have hh' := (brgc_aux_inverse_concat_lt_iff hv hz hu).mp hh
          simpa [hvodd] using hh'
  13. The strict cut maximality of $x$ applied to the cut $2^b z + e$ produces $\text{rank}_a(z) \le \text{rank}_a(u)$, yielding a contradiction.

    Applying the strict cyclic cut maximality hypothesis to $x = 2^a e + z$ (prefix $e$ of length $b$, suffix $z$ of length $a$) gives $\text{rank}_n(2^b z + e) < \text{rank}_n(x)$. Dividing both sides by $2^b$ via `Nat.div_le_div_right` and evaluating the quotients via `brgc_aux_prefix_rank` yields $\text{rank}_a(z) \le \text{rank}_a(u)$. This contradicts $\text{rank}_a(u) < \text{rank}_a(z)$, completing the proof by contradiction.

    lines 156–164

    uses Nat.div_le_div_right, Nat.le_of_lt, brgc_aux_prefix_rank

      have hnew := hstrict b a e z hb ha (by omega) he hz hxez
      have hdiv := Nat.div_le_div_right (Nat.le_of_lt hnew) (c := 2 ^ b)
      have he1 : brgc_inverse n (2 ^ b * z + e) / 2 ^ b = brgc_inverse a z := by
        simpa only [hab] using brgc_aux_prefix_rank hz he
      have he2 : brgc_inverse n x / 2 ^ b = brgc_inverse a u := by
        rw [hxsplit]
        simpa only [hab] using brgc_aux_prefix_rank hu hvf
      rw [he1, he2] at hdiv
      omega
brgc_inverse_concat
The inverse Gray code rank of a concatenated word $2^k a + b$ equals $2^k \cdot \text{rank}_m(a)$ plus either $\text{rank}_k(b)$ or $(2^k - 1 - \text{rank}_k(b))$, depending on whether the prefix rank $\text{rank}_m(a)$ is even or odd.
brgc_inverse_lt_two_pow
If $x < 2^n$, then its inverse Gray code rank satisfies $\text{rank}_n(x) < 2^n$.
Nat.exists_eq_succ_of_ne_zero
Every non-zero natural number is the successor of some natural number.
brgc_aux_inverse_xor
The inverse Gray code mapping distributes over bitwise XOR: $\text{rank}_n(x \oplus y) = \text{rank}_n(x) \oplus \text{rank}_n(y)$.
brgc_aux_inverse_one
For any $n > 0$, the inverse Gray code rank of 1 is 1.
Nat.one_lt_two_pow
For any non-zero natural number $n$, $1 < 2^n$.
brgc_aux_xor_high_low
For $b < 2^k$, $(2^k a) \oplus b = 2^k a + b$.
Nat.xor_assoc
Bitwise XOR on natural numbers is associative.
Nat.xor_lt_two_pow
If $x < 2^n$ and $y < 2^n$, then their bitwise XOR satisfies $x \oplus y < 2^n$.
lt_of_lt_of_le
If $a < b$ and $b \le c$, then $a < c$.
Nat.pow_le_pow_right
For $n > 0$, if $i \le j$ then $n^i \le n^j$.
Nat.xor_mod_two_pow
Modulo powers of two distributes over bitwise XOR: $(a \oplus b) \bmod 2^n = (a \bmod 2^n) \oplus (b \bmod 2^n)$.
brgc_aux_inverse_shift
The inverse Gray rank of $2^k a$ expands with a shift by $2^k$ and preserves the parity of $\text{rank}_m(a)$.
brgc_aux_inverse_stable
If $x < 2^m$ and $x < 2^n$, then its inverse Gray rank is independent of word length: $\text{rank}_m(x) = \text{rank}_n(x)$.
brgc_aux_inverse_concat_mod_two
The parity of the inverse Gray rank of $2^k a + b$ is the XOR of the parities of $\text{rank}_m(a)$ and $\text{rank}_k(b)$.
Nat.xor_comm
Bitwise XOR on natural numbers is commutative.
Nat.mod_two_eq_zero_or_one
Every natural number modulo 2 is either 0 or 1.
Nat.xor_one_of_even
Bitwise XOR with 1 increments an even natural number by 1.
Nat.even_iff.mpr
A natural number with remainder 0 modulo 2 is even.
Nat.odd_iff.mpr
A natural number with remainder 1 modulo 2 is odd.
Nat.xor_one_of_odd
Bitwise XOR with 1 decrements an odd natural number by 1.
brgc_aux_xor_one_bounds
Toggling the last bit of $q$ produces a value within distance 1 of $q$ and with opposite parity.
brgc_inverse_prefix
Dividing the inverse Gray rank of $x$ by $2^k$ equals the inverse Gray rank of $x / 2^k$ at length $n - k$.
brgc_aux_concat_bound
If $a < 2^m$ and $b < 2^k$, then $2^k a + b < 2^{m+k}$.
Nat.mul_add_div
For $m > 0$, $(m x + y) / m = x + y / m$.
Nat.two_pow_pos
Powers of two are strictly positive.
Nat.div_eq_of_lt
If $a < b$, then the integer quotient $a / b$ is 0.
Nat.div_lt_iff_lt_mul
For $k > 0$, $x / k < y$ if and only if $x < y \cdot k$.
pow_add
Powers of the same base add under multiplication: $a^{m+n} = a^m \cdot a^n$.
congrArg
Applying a function to both sides of an equality preserves the equality.
brgc_word_inverse
The Gray code word encoding function `brgc_word` inverts `brgc_inverse` on inputs less than $2^n$.
brgc_aux_concat_flip
Toggling the last bit of a concatenated word $2^k a + b$ (with $k > 0$ and $b < 2^k$) is equivalent to toggling the last bit of the low block $b$.
brgc_aux_inverse_concat_parity_swap
The parity of the inverse Gray code rank of a concatenated word $2^k a + b$ is invariant under swapping the two blocks to $2^m b + a$.
brgc_aux_inverse_flip
Toggling the last bit of an $n$-bit word toggles the last bit of its inverse Gray code rank.
brgc_aux_lt_of_flip_lt_of_parity
If $q \oplus 1 < r$ and $r$ has the same parity as $q \oplus 1$, then $q < r$.
Nat.div_le_div_right
Division of natural numbers by a positive divisor preserves weak inequality.
Nat.le_of_lt
A strict inequality between natural numbers implies the corresponding non-strict inequality.
brgc_aux_prefix_rank
Dividing the inverse Gray code rank of $2^k a + b$ by $2^k$ equals the inverse Gray code rank of the prefix $a$.
brgc_aux_word_prefix_bound
If $x < 2^{m+k}$, then the integer quotient $x / 2^k$ is strictly less than $2^m$.
Nat.add_comm
Addition of natural numbers is commutative.
Nat.mod_lt
The remainder modulo a positive divisor is strictly less than the divisor.
Nat.div_add_mod
Division with remainder reconstructs the original number: $n (m / n) + (m \bmod n) = m$.
brgc_aux_inverse_inj
The inverse Gray code mapping on words of length $n$ is injective.
brgc_aux_inverse_concat_lt_iff
Comparing two concatenated words with the same prefix preserves the suffix comparison when the prefix rank is even, and reverses it when the prefix rank is odd.

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_concat_lt_iff {m k a b c : ℕ}    (ha : a < 2 ^ m) (hb : b < 2 ^ k) (hc : c < 2 ^ k) :    brgc_inverse (m + k) (2 ^ k * a + b) < brgc_inverse (m + k) (2 ^ k * a + c) ↔      if brgc_inverse m a % 2 = 0 then brgc_inverse k b < brgc_inverse k c      else brgc_inverse k c < brgc_inverse k b := by  rw [brgc_inverse_concat ha hb, brgc_inverse_concat ha hc]  have hb' := brgc_inverse_lt_two_pow hb  have hc' := brgc_inverse_lt_two_pow hc  split_ifs <;> omega@[simp] theorem brgc_aux_inverse_zero (n : ℕ) : brgc_inverse n 0 = 0 := by  induction n with  | zero => rfl  | succ n ih => simp [brgc_inverse, ih]theorem brgc_aux_inverse_one {n : ℕ} (hn : 0 < n) : brgc_inverse n 1 = 1 := by  obtain ⟨n, rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : n ≠ 0)  simp [brgc_inverse]theorem brgc_aux_inverse_flip {n : ℕ} (hn : 0 < n) (x : ℕ) :    brgc_inverse n (x ^^^ 1) = brgc_inverse n x ^^^ 1 := by  rw [brgc_aux_inverse_xor, brgc_aux_inverse_one hn]theorem brgc_aux_concat_flip {k a b : ℕ} (hk : 0 < k) (hb : b < 2 ^ k) :    (2 ^ k * a + b) ^^^ 1 = 2 ^ k * a + (b ^^^ 1) := by  have h1 : 1 < 2 ^ k := Nat.one_lt_two_pow (by omega)  rw [← brgc_aux_xor_high_low a b k hb, Nat.xor_assoc,    brgc_aux_xor_high_low a (b ^^^ 1) k (Nat.xor_lt_two_pow hb h1)]theorem brgc_aux_inverse_concat_mod_two {m k a b : ℕ} (ha : a < 2 ^ m) (hb : b < 2 ^ k) :    brgc_inverse (m + k) (2 ^ k * a + b) % 2 =      (brgc_inverse m a % 2) ^^^ (brgc_inverse k b % 2) := 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]  rw [show (brgc_inverse (m + k) (2 ^ k * a) ^^^ brgc_inverse (m + k) b) % 2 =      brgc_inverse (m + k) (2 ^ k * a) % 2 ^^^ brgc_inverse (m + k) b % 2 from        Nat.xor_mod_two_pow (n := 1)]  rw [(brgc_aux_inverse_shift m k a ha).2, brgc_aux_inverse_stable hb' hb]theorem brgc_aux_inverse_concat_parity_swap {m k a b : ℕ}    (ha : a < 2 ^ m) (hb : b < 2 ^ k) :    brgc_inverse (m + k) (2 ^ k * a + b) % 2 =      brgc_inverse (k + m) (2 ^ m * b + a) % 2 := by  rw [brgc_aux_inverse_concat_mod_two ha hb, brgc_aux_inverse_concat_mod_two hb ha]  exact Nat.xor_comm _ _theorem brgc_aux_xor_one_bounds (q : ℕ) :    q ≤ (q ^^^ 1) + 1 ∧ (q ^^^ 1) ≤ q + 1 ∧ (q ^^^ 1) % 2 ≠ q % 2 := by  rcases Nat.mod_two_eq_zero_or_one q with hq | hq  · rw [Nat.xor_one_of_even (Nat.even_iff.mpr hq)]    omega  · have ho : Odd q := Nat.odd_iff.mpr hq    rw [Nat.xor_one_of_odd ho]    omegatheorem brgc_aux_lt_of_flip_lt_of_parity (q r : ℕ) (h : q ^^^ 1 < r)    (hp : r % 2 = (q ^^^ 1) % 2) : q < r := by  obtain ⟨h1, h2, h3⟩ := brgc_aux_xor_one_bounds q  omegatheorem brgc_aux_prefix_rank {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 := by  have hh := brgc_inverse_prefix (show k ≤ m + k by omega) (brgc_aux_concat_bound ha hb)  have hdiv : (2 ^ k * a + b) / 2 ^ k = a := by    rw [Nat.mul_add_div (Nat.two_pow_pos _), Nat.div_eq_of_lt hb]    omega  simpa [hdiv] using hhtheorem brgc_aux_word_prefix_bound {m k x : ℕ} (hx : x < 2 ^ (m + k)) :    x / 2 ^ k < 2 ^ m := by  apply (Nat.div_lt_iff_lt_mul (Nat.two_pow_pos _)).mpr  rwa [← pow_add]theorem brgc_aux_inverse_inj {n x y : ℕ} (hx : x < 2 ^ n) (hy : y < 2 ^ n)    (h : brgc_inverse n x = brgc_inverse n y) : x = y := by  have hh := congrArg brgc_word h  rwa [brgc_word_inverse hx, brgc_word_inverse hy] at hhtheorem brgc_inverse_flip_preserves_cut_max (n x : ℕ) (hx : x < 2 ^ n)    (hstrict : ∀ a b u v : ℕ, 0 < a → 0 < b → a + b = n →      u < 2 ^ a → v < 2 ^ b → x = 2 ^ b * u + v →      brgc_inverse n (2 ^ a * v + u) < brgc_inverse n x) :    ∀ a b u v : ℕ, 0 < a → 0 < b → a + b = n →      u < 2 ^ a → v < 2 ^ b → x ^^^ 1 = 2 ^ b * u + v →      brgc_inverse n (2 ^ a * v + u) ≤ brgc_inverse n (x ^^^ 1) := by  intro a b u v ha hb hab hu hv hsplit  have hn : 0 < n := by omega  have hvf : v ^^^ 1 < 2 ^ b :=    Nat.xor_lt_two_pow hv (Nat.one_lt_two_pow (by omega))  have hxsplit : x = 2 ^ b * u + (v ^^^ 1) := by    have hh := congrArg (fun z : ℕ => z ^^^ 1) hsplit    simpa [brgc_aux_concat_flip hb hv] using hh  by_contra hnot  have hbad : brgc_inverse n (x ^^^ 1) < brgc_inverse n (2 ^ a * v + u) := by omega  have hlow := hstrict a b u (v ^^^ 1) ha hb hab hu hvf hxsplit  have hpar : brgc_inverse n (2 ^ a * v + u) % 2 =      (brgc_inverse n x ^^^ 1) % 2 := by    calc      _ = brgc_inverse n (2 ^ b * u + v) % 2 := by        simpa only [hab, show b + a = n by omega] using (brgc_aux_inverse_concat_parity_swap hu hv).symm      _ = brgc_inverse n (x ^^^ 1) % 2 := by rw [hsplit]      _ = _ := by rw [brgc_aux_inverse_flip hn]  have hhigh : brgc_inverse n x < brgc_inverse n (2 ^ a * v + u) :=    brgc_aux_lt_of_flip_lt_of_parity _ _ (by simpa [brgc_aux_inverse_flip hn] using hbad) hpar  have hqlo : brgc_inverse b (v ^^^ 1) ≤ brgc_inverse n x / 2 ^ a := by    have hh := Nat.div_le_div_right (Nat.le_of_lt hlow) (c := 2 ^ a)    have he := brgc_aux_prefix_rank hvf hu    have hba : b + a = n := by omega    rw [hba] at he    rwa [he] at hh  have hqhi : brgc_inverse n x / 2 ^ a ≤ brgc_inverse b v := by    have hh := Nat.div_le_div_right (Nat.le_of_lt hhigh) (c := 2 ^ a)    have he := brgc_aux_prefix_rank hv hu    have hba : b + a = n := by omega    rw [hba] at he    rwa [he] at hh  rw [brgc_aux_inverse_flip hb] at hqlo  have hvodd : brgc_inverse b v % 2 = 1 := by    rcases Nat.mod_two_eq_zero_or_one (brgc_inverse b v) with heven | hodd    · rw [Nat.xor_one_of_even (Nat.even_iff.mpr heven)] at hqlo      omega    · exact hodd  have hvfpar : brgc_inverse b (v ^^^ 1) % 2 = 0 := by    rw [brgc_aux_inverse_flip hb, Nat.xor_one_of_odd (Nat.odd_iff.mpr hvodd)]    omega  have hqc : brgc_inverse n x / 2 ^ a = brgc_inverse b (v ^^^ 1) ∨      brgc_inverse n x / 2 ^ a = brgc_inverse b v := by    rw [brgc_aux_inverse_flip hb]    obtain ⟨h1, h2, _⟩ := brgc_aux_xor_one_bounds (brgc_inverse b v)    omega  let e := x / 2 ^ a  let z := x % 2 ^ a  have he : e < 2 ^ b := by    apply brgc_aux_word_prefix_bound    simpa [Nat.add_comm b a, hab] using hx  have hz : z < 2 ^ a := Nat.mod_lt _ (Nat.two_pow_pos _)  have hxez : x = 2 ^ a * e + z := (Nat.div_add_mod x (2 ^ a)).symm  have hqe : brgc_inverse n x / 2 ^ a = brgc_inverse b e := by    rw [hxez]    simpa only [show b + a = n by omega] using brgc_aux_prefix_rank he hz  have hue : brgc_inverse a u < brgc_inverse a z := by    rcases hqc with hc | hc    · have heq : e = v ^^^ 1 := brgc_aux_inverse_inj he hvf (hqe.symm.trans hc)      have hh : brgc_inverse (b + a) (2 ^ a * (v ^^^ 1) + u) <          brgc_inverse (b + a) (2 ^ a * (v ^^^ 1) + z) := by        simpa [show b + a = n by omega, hxez, heq] using hlow      have hh' := (brgc_aux_inverse_concat_lt_iff hvf hu hz).mp hh      simpa [hvfpar] using hh'    · have heq : e = v := brgc_aux_inverse_inj he hv (hqe.symm.trans hc)      have hh : brgc_inverse (b + a) (2 ^ a * v + z) <          brgc_inverse (b + a) (2 ^ a * v + u) := by        simpa [show b + a = n by omega, hxez, heq] using hhigh      have hh' := (brgc_aux_inverse_concat_lt_iff hv hz hu).mp hh      simpa [hvodd] using hh'  have hnew := hstrict b a e z hb ha (by omega) he hz hxez  have hdiv := Nat.div_le_div_right (Nat.le_of_lt hnew) (c := 2 ^ b)  have he1 : brgc_inverse n (2 ^ b * z + e) / 2 ^ b = brgc_inverse a z := by    simpa only [hab] using brgc_aux_prefix_rank hz he  have he2 : brgc_inverse n x / 2 ^ b = brgc_inverse a u := by    rw [hxsplit]    simpa only [hab] using brgc_aux_prefix_rank hu hvf  rw [he1, he2] at hdiv  omega
See it in the graphDiscuss this resultChallenge it