brgc_inverse_rotate_tent_formula
In inverse Gray-rank coordinates, cyclic left rotation is the two-branch integer tent map, with the rank parity carried along.
Statement
theorem brgc_inverse_rotate_tent_formula (n t : ℕ) (hn : 2 ≤ n) (ht : t < 2 ^ n) : brgc_inverse n (bitword_rotate n (brgc_word t)) = if t < 2 ^ (n - 1) then 2 * t + t % 2 else 2 * (2 ^ n - 1 - t) + t % 2
- Source
- Arithmetic reformulation of cyclic rotation and the prefix-parity inverse used in OP-392, arXiv:2610.24758, Section 3 and Conjecture 1.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- 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_wordThe n-bit inverse prefix-parity transform recovers an n-bit Gray rank from its encoded word.
- 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_prefixThe inverse Gray rank of a high-bit prefix is the corresponding high-bit prefix of the inverse rank.
- bitword_rotateCyclic rotation of an n-bit word x (a number below 2^n) by one position: the word is shifted up and its top bit moves to the bottom.
- brgc_word_div_twoThe binary reflected Gray encoding commutes with division by two.
- brgc_word_lt_two_powAn n-bit rank encodes an n-bit word.
- brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
- brgc_inverse_lt_two_powThe inverse prefix-parity transform of an n-bit word has an n-bit rank.
- brgc_word_div_powTaking a high-bit prefix commutes with binary reflected Gray encoding.
- Used by 1
- alpha_lexical_terminal_predecessor_simple_star_obstructionThe two displayed lexical sequences are adjacent among sequences of degree 19 and have meet f=(2,1,1). The later sequence has a lexical…
The proof, explained
The proof splits into two cases according to whether the Gray rank t lies in the lower half [0, 2^(n - 1)) or the upper half [2^(n - 1), 2^n). In each case, rotating the n-bit Gray codeword brgc_word(t) cyclically to the left shifts its lower bits and wraps its leading bit (0 or 1) into the least significant bit position. The inverse Gray rank of the rotated word is computed using the concatenation formula `brgc_inverse_concat`, which reduces the rank of an n-bit word to the rank of its (n - 1)-bit prefix and a parity-dependent adjustment from its 1-bit suffix. A parity case split on t % 2 shows that the suffix adjustment always evaluates to t % 2, matching the two branches of the integer tent map.
The proof splits into two cases: t < 2^(n - 1) and t ≥ 2^(n - 1).
The tactic `split_ifs` introduces the case distinction on whether t < 2^(n - 1), corresponding to the two branches of the tent map definition on the right-hand side.
split_ifs with hlt
When t < 2^(n - 1), cyclic left rotation of brgc_word(t) is simply doubling: 2 * brgc_word(t).
Because t < 2^(n - 1), the codeword w = brgc_word(t) satisfies w < 2^(n - 1) by `brgc_word_lt_two_pow`, so its leading bit ⌊w / 2^(n - 1)⌋ is 0 by `Nat.div_eq_of_lt`. Furthermore, 2 * w < 2^n (since 2^n = 2 * 2^(n - 1) by `pow_succ'`, `mul_comm`, and `Nat.sub_add_cancel`), meaning (2 * w) % 2^n = 2 * w by `Nat.mod_eq_of_lt`. By definition of `bitword_rotate`, the rotated word is (2 * w) % 2^n + ⌊w / 2^(n - 1)⌋ = 2 * w + 0 = 2 * w using `add_zero`.
uses
brgc_word_lt_two_pow,Nat.div_eq_of_lt,Nat.sub_add_cancel,pow_succ',mul_comm,Nat.mod_eq_of_lt,add_zero· have hw : brgc_word t < 2 ^ (n - 1) := brgc_word_lt_two_pow hlt have hrot : bitword_rotate n (brgc_word t) = 2 * brgc_word t := by dsimp [bitword_rotate] have hdiv : brgc_word t / 2 ^ (n - 1) = 0 := Nat.div_eq_of_lt hw have h2w : 2 * brgc_word t < 2 ^ n := by have : 2 ^ n = 2 * 2 ^ (n - 1) := by conv_lhs => rw [← Nat.sub_add_cancel (by omega : 1 ≤ n)] rw [pow_succ', mul_comm] omega have hmod : 2 * brgc_word t % 2 ^ n = 2 * brgc_word t := Nat.mod_eq_of_lt h2w rw [hdiv, hmod, add_zero] rw [hrot]
The Gray rank of 2 * brgc_word(t) reduces to 2 * t + (if t % 2 = 0 then 0 else 1).
We express 2 * w as 2^1 * w + 0, which concatenates an (n - 1)-bit prefix w with a 1-bit suffix 0. Applying `brgc_inverse_concat` with (n - 1) + 1 = n (via `Nat.sub_add_cancel`), the rank decomposes into 2 * brgc_inverse(n - 1, w) plus an adjustment: brgc_inverse(1, 0) if the prefix rank is even, and 2^1 - 1 - brgc_inverse(1, 0) if odd. Since brgc_inverse(n - 1, w) = t by `brgc_inverse_word` and brgc_inverse(1, 0) = 0 by definition, this simplifies directly.
uses
brgc_inverse_concat,Nat.sub_add_cancel,brgc_inverse_wordhave hsplit : 2 * brgc_word t = 2 ^ 1 * brgc_word t + 0 := by simp have hconcat := @brgc_inverse_concat (n - 1) 1 (brgc_word t) 0 hw (by decide) have hnm : n - 1 + 1 = n := Nat.sub_add_cancel (by omega) rw [hnm] at hconcat rw [hsplit, hconcat] have hinv : brgc_inverse (n - 1) (brgc_word t) = t := brgc_inverse_word hlt rw [hinv] have hinv0 : brgc_inverse 1 0 = 0 := rfl rw [hinv0]
For t < 2^(n - 1), the inverse Gray rank is 2 * t + t % 2.
By `Nat.mod_two_eq_zero_or_one`, t % 2 is either 0 or 1. If t % 2 = 0, the even branch is taken via `if_pos`, giving 2 * t + 0 = 2 * t + t % 2. If t % 2 = 1, the odd branch is taken via `if_neg`, giving 2 * t + (2 - 1 - 0) = 2 * t + 1 = 2 * t + t % 2. Both branches are closed by linear arithmetic (`omega`).
uses
Nat.mod_two_eq_zero_or_one,if_pos,if_neghave hmod2 : t % 2 = 0 ∨ t % 2 = 1 := Nat.mod_two_eq_zero_or_one t rcases hmod2 with h0 | h1 · rw [if_pos h0, h0] omega · rw [if_neg (by omega), h1] omega
When t ≥ 2^(n - 1), the leading bit of both t and brgc_word(t) is 1, and the remainder v = brgc_word(t) % 2^(n - 1) satisfies v < 2^(n - 1).
Since 2^(n - 1) ≤ t < 2^n, division gives t / 2^(n - 1) = 1 via `Nat.div_eq_sub_div`, `Nat.div_eq_of_lt`, and `zero_add`. By `brgc_word_div_pow`, the leading bit of brgc_word(t) is brgc_word(t / 2^(n - 1)) = brgc_word(1) = 1. The remainder v = brgc_word(t) % 2^(n - 1) is strictly less than 2^(n - 1) by `Nat.mod_lt` (with 2^(n - 1) > 0 by `Nat.two_pow_pos`). The power identity 2^n = 2 * 2^(n - 1) is established using `Nat.sub_add_cancel`, `pow_succ'`, and `mul_comm`.
uses
Nat.sub_add_cancel,pow_succ',mul_comm,Nat.two_pow_pos,Nat.div_eq_sub_div,Nat.div_eq_of_lt,zero_add,brgc_word_div_pow,Nat.mod_lt· have ht1 : 2 ^ (n - 1) ≤ t := by omega have h2n : 2 ^ n = 2 * 2 ^ (n - 1) := by conv_lhs => rw [← Nat.sub_add_cancel (by omega : 1 ≤ n)] rw [pow_succ', mul_comm] have hb : 0 < 2 ^ (n - 1) := Nat.two_pow_pos _ have ht_sub : t - 2 ^ (n - 1) < 2 ^ (n - 1) := by omega have htdiv : t / 2 ^ (n - 1) = 1 := by rw [Nat.div_eq_sub_div hb ht1, Nat.div_eq_of_lt ht_sub, zero_add] have hdiv : brgc_word t / 2 ^ (n - 1) = 1 := by rw [brgc_word_div_pow, htdiv] rfl have hv : brgc_word t % 2 ^ (n - 1) < 2 ^ (n - 1) := Nat.mod_lt _ hb
When t ≥ 2^(n - 1), cyclic left rotation of brgc_word(t) equals 2 * v + 1, where v = brgc_word(t) % 2^(n - 1).
By division decomposition (`Nat.div_add_mod` and `mul_one`), brgc_word(t) = 2^(n - 1) + v, so 2 * brgc_word(t) = 2^n + 2 * v. In the definition of `bitword_rotate`, modulo 2^n drops the 2^n term by `Nat.add_mod_left`, leaving 2 * v by `Nat.mod_eq_of_lt` (since 2 * v < 2^n). Adding the rotated-out leading bit ⌊brgc_word(t) / 2^(n - 1)⌋ = 1 produces 2 * v + 1.
uses
Nat.div_add_mod,mul_one,Nat.add_mod_left,Nat.mod_eq_of_lthave hrot : bitword_rotate n (brgc_word t) = 2 * (brgc_word t % 2 ^ (n - 1)) + 1 := by dsimp [bitword_rotate] rw [hdiv] have hdecomp : brgc_word t = 2 ^ (n - 1) + brgc_word t % 2 ^ (n - 1) := by have h := Nat.div_add_mod (brgc_word t) (2 ^ (n - 1)) rw [hdiv, mul_one] at h exact h.symm have h2w : 2 * brgc_word t = 2 ^ n + 2 * (brgc_word t % 2 ^ (n - 1)) := by calc 2 * brgc_word t = 2 * (2 ^ (n - 1) + brgc_word t % 2 ^ (n - 1)) := by rw [← hdecomp] _ = 2 * 2 ^ (n - 1) + 2 * (brgc_word t % 2 ^ (n - 1)) := by ring _ = 2 ^ n + 2 * (brgc_word t % 2 ^ (n - 1)) := by rw [← h2n] rw [h2w, Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)]
The (n - 1)-bit Gray rank of the remainder v is 2^n - 1 - t.
Decomposing brgc_word(t) = 2^(n - 1) * 1 + v (using `Nat.div_add_mod`) views it as the concatenation of a 1-bit word 1 and the (n - 1)-bit word v. Applying `brgc_inverse_concat` for 1 + (n - 1) = n expresses t = brgc_inverse(n, brgc_word(t)) (via `brgc_inverse_word`). Since brgc_inverse(1, 1) = 1 is odd, the reflected branch applies: t = 2^(n - 1) + (2^(n - 1) - 1 - brgc_inverse(n - 1, v)). Knowing brgc_inverse(n - 1, v) < 2^(n - 1) by `brgc_inverse_lt_two_pow`, linear arithmetic (`omega`) solves for brgc_inverse(n - 1, v) = 2^n - 1 - t.
uses
brgc_inverse_concat,Nat.div_add_mod,brgc_inverse_word,brgc_inverse_lt_two_powhave hconcat1 := @brgc_inverse_concat 1 (n - 1) 1 (brgc_word t % 2 ^ (n - 1)) (by decide) hv have h1n : 1 + (n - 1) = n := by omega rw [h1n] at hconcat1 have hsplit1 : brgc_word t = 2 ^ (n - 1) * 1 + brgc_word t % 2 ^ (n - 1) := by have h := Nat.div_add_mod (brgc_word t) (2 ^ (n - 1)) rw [hdiv] at h omega rw [← hsplit1, brgc_inverse_word ht] at hconcat1 have hinv1 : brgc_inverse 1 1 = 1 := rfl rw [hinv1] at hconcat1 norm_num at hconcat1 have hI_lt : brgc_inverse (n - 1) (brgc_word t % 2 ^ (n - 1)) < 2 ^ (n - 1) := brgc_inverse_lt_two_pow hv have hI_val : brgc_inverse (n - 1) (brgc_word t % 2 ^ (n - 1)) = 2 ^ n - 1 - t := by omega
The Gray rank of the rotated word 2 * v + 1 reduces to 2 * (2^n - 1 - t) plus an adjustment depending on the parity of 2^n - 1 - t.
Writing 2 * v + 1 as 2^1 * v + 1, `brgc_inverse_concat` with prefix length n - 1 and suffix length 1 expresses the rank in terms of brgc_inverse(n - 1, v) = 2^n - 1 - t and brgc_inverse(1, 1) = 1. If 2^n - 1 - t is even, the direct branch adds brgc_inverse(1, 1) = 1; if odd, the reflected branch adds 2^1 - 1 - 1 = 0.
uses
brgc_inverse_concathave hsplit2 : bitword_rotate n (brgc_word t) = 2 ^ 1 * (brgc_word t % 2 ^ (n - 1)) + 1 := by rw [hrot] ring have hconcat2 := @brgc_inverse_concat (n - 1) 1 (brgc_word t % 2 ^ (n - 1)) 1 hv (by decide) have hnm : n - 1 + 1 = n := by omega rw [hnm] at hconcat2 rw [hsplit2, hconcat2] rw [hI_val, hinv1]
For t ≥ 2^(n - 1), the inverse Gray rank is 2 * (2^n - 1 - t) + t % 2.
Because n ≥ 2, 2^n - 1 is odd, so 2^n - 1 - t and t have opposite parities. By `Nat.mod_two_eq_zero_or_one`, t % 2 is 0 or 1. If t % 2 = 0, then 2^n - 1 - t is odd, so `if_neg` selects the adjustment 0 = t % 2. If t % 2 = 1, then 2^n - 1 - t is even, so `if_pos` selects the adjustment 1 = t % 2. Linear arithmetic (`omega`) completes both branches.
uses
Nat.mod_two_eq_zero_or_one,if_neg,if_poshave htmod : t % 2 = 0 ∨ t % 2 = 1 := Nat.mod_two_eq_zero_or_one t rcases htmod with h0 | h1 · have hodd : (2 ^ n - 1 - t) % 2 = 1 := by omega rw [if_neg (by omega), h0] omega · have heven : (2 ^ n - 1 - t) % 2 = 0 := by omega rw [if_pos heven, h1] omega
brgc_word_lt_two_pow- If t < 2^n, then brgc_word(t) < 2^n.
Nat.div_eq_of_lt- If a < b, then a / b = 0.
Nat.sub_add_cancel- If m ≤ n, then n - m + m = n.
pow_succ'- In a monoid, a^(n + 1) = a * a^n.
mul_comm- Multiplication is commutative: a * b = b * a.
Nat.mod_eq_of_lt- If a < b, then a % b = a.
add_zero- a + 0 = a.
brgc_inverse_concat- For a < 2^m and b < 2^k, the inverse Gray rank of 2^k * a + b decomposes into 2^k * brgc_inverse(m, a) plus an adjustment: brgc_inverse(k, b) if the prefix rank is even, and 2^k - 1 - brgc_inverse(k, b) if odd.
brgc_inverse_word- For t < 2^n, the inverse Gray rank of brgc_word(t) is t.
Nat.mod_two_eq_zero_or_one- For any natural number n, n % 2 = 0 or n % 2 = 1.
if_pos- If condition c holds, then (if c then t else e) = t.
if_neg- If condition c is false, then (if c then t else e) = e.
Nat.two_pow_pos- For any natural number w, 2^w > 0.
Nat.div_eq_sub_div- If 0 < b ≤ a, then a / b = (a - b) / b + 1.
zero_add- 0 + a = a.
brgc_word_div_pow- For all t and k, ⌊brgc_word(t) / 2^k⌋ = brgc_word(⌊t / 2^k⌋).
Nat.mod_lt- If y > 0, then x % y < y.
Nat.div_add_mod- The division algorithm: n * (m / n) + m % n = m.
mul_one- a * 1 = a.
Nat.add_mod_left- (x + z) % x = z % x.
brgc_inverse_lt_two_pow- If x < 2^n, then brgc_inverse(n, x) < 2^n.
- The proof relies extensively on the `omega` tactic to discharge linear arithmetic subgoals involving powers of 2 and parities, and uses `decide` to verify small constant inequalities such as 0 < 2¹ and 1 < 2¹.
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_rotate_tent_formula (n t : ℕ) (hn : 2 ≤ n) (ht : t < 2 ^ n) : brgc_inverse n (bitword_rotate n (brgc_word t)) = if t < 2 ^ (n - 1) then 2 * t + t % 2 else 2 * (2 ^ n - 1 - t) + t % 2 := by split_ifs with hlt · have hw : brgc_word t < 2 ^ (n - 1) := brgc_word_lt_two_pow hlt have hrot : bitword_rotate n (brgc_word t) = 2 * brgc_word t := by dsimp [bitword_rotate] have hdiv : brgc_word t / 2 ^ (n - 1) = 0 := Nat.div_eq_of_lt hw have h2w : 2 * brgc_word t < 2 ^ n := by have : 2 ^ n = 2 * 2 ^ (n - 1) := by conv_lhs => rw [← Nat.sub_add_cancel (by omega : 1 ≤ n)] rw [pow_succ', mul_comm] omega have hmod : 2 * brgc_word t % 2 ^ n = 2 * brgc_word t := Nat.mod_eq_of_lt h2w rw [hdiv, hmod, add_zero] rw [hrot] have hsplit : 2 * brgc_word t = 2 ^ 1 * brgc_word t + 0 := by simp have hconcat := @brgc_inverse_concat (n - 1) 1 (brgc_word t) 0 hw (by decide) have hnm : n - 1 + 1 = n := Nat.sub_add_cancel (by omega) rw [hnm] at hconcat rw [hsplit, hconcat] have hinv : brgc_inverse (n - 1) (brgc_word t) = t := brgc_inverse_word hlt rw [hinv] have hinv0 : brgc_inverse 1 0 = 0 := rfl rw [hinv0] have hmod2 : t % 2 = 0 ∨ t % 2 = 1 := Nat.mod_two_eq_zero_or_one t rcases hmod2 with h0 | h1 · rw [if_pos h0, h0] omega · rw [if_neg (by omega), h1] omega · have ht1 : 2 ^ (n - 1) ≤ t := by omega have h2n : 2 ^ n = 2 * 2 ^ (n - 1) := by conv_lhs => rw [← Nat.sub_add_cancel (by omega : 1 ≤ n)] rw [pow_succ', mul_comm] have hb : 0 < 2 ^ (n - 1) := Nat.two_pow_pos _ have ht_sub : t - 2 ^ (n - 1) < 2 ^ (n - 1) := by omega have htdiv : t / 2 ^ (n - 1) = 1 := by rw [Nat.div_eq_sub_div hb ht1, Nat.div_eq_of_lt ht_sub, zero_add] have hdiv : brgc_word t / 2 ^ (n - 1) = 1 := by rw [brgc_word_div_pow, htdiv] rfl have hv : brgc_word t % 2 ^ (n - 1) < 2 ^ (n - 1) := Nat.mod_lt _ hb have hrot : bitword_rotate n (brgc_word t) = 2 * (brgc_word t % 2 ^ (n - 1)) + 1 := by dsimp [bitword_rotate] rw [hdiv] have hdecomp : brgc_word t = 2 ^ (n - 1) + brgc_word t % 2 ^ (n - 1) := by have h := Nat.div_add_mod (brgc_word t) (2 ^ (n - 1)) rw [hdiv, mul_one] at h exact h.symm have h2w : 2 * brgc_word t = 2 ^ n + 2 * (brgc_word t % 2 ^ (n - 1)) := by calc 2 * brgc_word t = 2 * (2 ^ (n - 1) + brgc_word t % 2 ^ (n - 1)) := by rw [← hdecomp] _ = 2 * 2 ^ (n - 1) + 2 * (brgc_word t % 2 ^ (n - 1)) := by ring _ = 2 ^ n + 2 * (brgc_word t % 2 ^ (n - 1)) := by rw [← h2n] rw [h2w, Nat.add_mod_left, Nat.mod_eq_of_lt (by omega)] have hconcat1 := @brgc_inverse_concat 1 (n - 1) 1 (brgc_word t % 2 ^ (n - 1)) (by decide) hv have h1n : 1 + (n - 1) = n := by omega rw [h1n] at hconcat1 have hsplit1 : brgc_word t = 2 ^ (n - 1) * 1 + brgc_word t % 2 ^ (n - 1) := by have h := Nat.div_add_mod (brgc_word t) (2 ^ (n - 1)) rw [hdiv] at h omega rw [← hsplit1, brgc_inverse_word ht] at hconcat1 have hinv1 : brgc_inverse 1 1 = 1 := rfl rw [hinv1] at hconcat1 norm_num at hconcat1 have hI_lt : brgc_inverse (n - 1) (brgc_word t % 2 ^ (n - 1)) < 2 ^ (n - 1) := brgc_inverse_lt_two_pow hv have hI_val : brgc_inverse (n - 1) (brgc_word t % 2 ^ (n - 1)) = 2 ^ n - 1 - t := by omega have hsplit2 : bitword_rotate n (brgc_word t) = 2 ^ 1 * (brgc_word t % 2 ^ (n - 1)) + 1 := by rw [hrot] ring have hconcat2 := @brgc_inverse_concat (n - 1) 1 (brgc_word t % 2 ^ (n - 1)) 1 hv (by decide) have hnm : n - 1 + 1 = n := by omega rw [hnm] at hconcat2 rw [hsplit2, hconcat2] rw [hI_val, hinv1] have htmod : t % 2 = 0 ∨ t % 2 = 1 := Nat.mod_two_eq_zero_or_one t rcases htmod with h0 | h1 · have hodd : (2 ^ n - 1 - t) % 2 = 1 := by omega rw [if_neg (by omega), h0] omega · have heven : (2 ^ n - 1 - t) % 2 = 0 := by omega rw [if_pos heven, h1] omega