brgc_inverse_flip_preserves_cut_max
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
- 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_binary_prefix_inverse_parityThe inverse Gray rank of the prefix has the parity of the number of encoded one bits, namely the cell count.
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.
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.
uses
brgc_inverse_concat,brgc_inverse_lt_two_powrw [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
$\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$.
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]
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.
uses
Nat.one_lt_two_pow,brgc_aux_xor_high_low,Nat.xor_assoc,Nat.xor_lt_two_powtheorem 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)]
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.
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_commtheorem 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 _ _
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$.
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_boundstheorem 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
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`.
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_inversetheorem 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
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$.
uses
Nat.xor_lt_two_pow,Nat.one_lt_two_pow,congrArg,brgc_aux_concat_fliptheorem 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
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)$.
uses
brgc_aux_inverse_concat_parity_swap,brgc_aux_inverse_flip,brgc_aux_lt_of_flip_lt_of_parityby_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
$\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.
uses
Nat.div_le_div_right,Nat.le_of_lt,brgc_aux_prefix_rank,brgc_aux_inverse_fliphave 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
$\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.
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_boundshave 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
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)$.
uses
brgc_aux_word_prefix_bound,Nat.add_comm,Nat.mod_lt,Nat.two_pow_pos,Nat.div_add_mod,brgc_aux_prefix_ranklet 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
$\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)$.
uses
brgc_aux_inverse_inj,brgc_aux_inverse_concat_lt_iffrcases 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'
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.
uses
Nat.div_le_div_right,Nat.le_of_lt,brgc_aux_prefix_rankhave 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.
- The file contains several auxiliary lemmas establishing order-reflection, rank-prefix projections, XOR linearity, and parity properties of the Binary Reflected Gray Code (BRGC) inverse mapping before proving the main theorem. The proof relies on Lean's `omega` tactic to discharge routine linear inequalities and modular arithmetic constraints.
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_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