AFTD Auto-Formalizing Theoretical Domains

brgc_inverse_rotate_tent_formula

theoremverified

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

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.

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

    line 2

      split_ifs with hlt
  2. 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`.

    lines 3–14

    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]
  3. 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.

    lines 15–23

    uses brgc_inverse_concat, Nat.sub_add_cancel, brgc_inverse_word

        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]
  4. 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`).

    lines 24–29

    uses Nat.mod_two_eq_zero_or_one, if_pos, if_neg

        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
  5. 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`.

    lines 30–41

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

    lines 42–53

    uses Nat.div_add_mod, mul_one, Nat.add_mod_left, Nat.mod_eq_of_lt

        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)]
  7. 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.

    lines 54–68

    uses brgc_inverse_concat, Nat.div_add_mod, brgc_inverse_word, brgc_inverse_lt_two_pow

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

    lines 69–76

    uses brgc_inverse_concat

        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]
  9. 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.

    lines 77–84

    uses Nat.mod_two_eq_zero_or_one, if_neg, if_pos

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

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