AFTD Auto-Formalizing Theoretical Domains

bitword_rotate_iterate_cut

theoremverified

Cyclically rotating an n-bit nonconstant word left by a positions exchanges its prefix of length a and its suffix of length b, where a+b=n.

Statement

theorem bitword_rotate_iterate_cut {n a b u v : ℕ} (hn : 2 ≤ n) (hab : a + b = n)
    (hu : u < 2 ^ a) (hv : v < 2 ^ b)
    (h0 : 0 < 2 ^ b * u + v) (h1 : 2 ^ b * u + v < 2 ^ n - 1) :
    (bitword_rotate n)^[a] (2 ^ b * u + v) = 2 ^ a * v + u
Source
Prefix-parity inverse and supporting arithmetic for OP-392, arXiv:2610.24758, Section 3 and Conjecture 1.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • bitword_is_aperiodic_of_primeFor prime n, every n-bit word other than 0^n and 1^n is aperiodic.
  • 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_inverse_concatThe inverse Gray rank of a concatenation has the prefix inverse rank followed by the suffix inverse rank, complemented exactly when the…
Used by 4

The proof, explained

The proof computes the a-fold cyclic rotation of the n-bit word 2^b * u + v using the modular characterisation (bitword_rotate n)^[a] x = (2^a * x) mod (2^n - 1). Expanding 2^a * (2^b * u + v) reveals that it equals (2^n - 1) * u + (2^a * v + u), which is congruent to the swapped concatenation 2^a * v + u modulo 2^n - 1. Because 2^a * v + u < 2^n and cannot equal 2^n - 1 without forcing the positive rotated word to be 0, it is strictly less than 2^n - 1, so the modulo operation acts as the identity.

  1. The a-fold cyclic rotation of 2^b * u + v equals 2^a * (2^b * u + v) mod (2^n - 1) and is strictly positive.

    Applying bitword_is_aperiodic_of_prime_iterate_eq_mod to the word 2^b * u + v, which lies strictly between 0 and 2^n - 1, establishes that rotating a times multiplies the word by 2^a modulo 2^n - 1, and that the resulting rotated word remains strictly positive.

    lines 5–6

    uses bitword_is_aperiodic_of_prime_iterate_eq_mod

      obtain ⟨heq, hpos, _⟩ :=
        bitword_is_aperiodic_of_prime_iterate_eq_mod n hn (2 ^ b * u + v) h0 h1 a
  2. 2^a * 2^b = 2^n and (2^n - 1) + 1 = 2^n.

    The first identity rewrites 2^a * 2^b as 2^(a + b) using pow_add and substitutes the hypothesis a + b = n. The second identity follows from the strict positivity 2^n > 0 (via Nat.two_pow_pos) using linear arithmetic (omega).

    lines 7–10

    uses pow_add, Nat.two_pow_pos

      have hpow : 2 ^ a * 2 ^ b = 2 ^ n := by rw [← pow_add, hab]
      have hpred : 2 ^ n - 1 + 1 = 2 ^ n := by
        have := Nat.two_pow_pos n
        omega
  3. 2^a * (2^b * u + v) = (2^n - 1) * u + (2^a * v + u).

    Expanding the left-hand side gives (2^a * 2^b) * u + 2^a * v. Substituting 2^a * 2^b = 2^n and then 2^n = (2^n - 1) + 1, algebraic expansion and rearrangement using ring yields (2^n - 1) * u + (2^a * v + u).

    lines 11–17

      have he : 2 ^ a * (2 ^ b * u + v) =
          (2 ^ n - 1) * u + (2 ^ a * v + u) := by
        calc
          _ = (2 ^ a * 2 ^ b) * u + 2 ^ a * v := by ring
          _ = 2 ^ n * u + 2 ^ a * v := by rw [hpow]
          _ = (2 ^ n - 1 + 1) * u + 2 ^ a * v := by rw [hpred]
          _ = _ := by ring
  4. (bitword_rotate n)^[a] (2^b * u + v) = (2^a * v + u) mod (2^n - 1).

    Substituting the expansion of 2^a * (2^b * u + v) into the modulo expression, the term (2^n - 1) * u vanishes modulo 2^n - 1 (simplified by simp). Rewriting with this congruence transforms the rotation equation into (bitword_rotate n)^[a] (2^b * u + v) = (2^a * v + u) mod (2^n - 1).

    lines 18–20

      have hmod : (2 ^ a * (2 ^ b * u + v)) % (2 ^ n - 1) =
          (2 ^ a * v + u) % (2 ^ n - 1) := by rw [he]; simp
      rw [hmod] at heq
  5. 2^a * v + u < 2^n.

    Applying the concatenation bound brgc_aux_concat_bound to v < 2^b and u < 2^a gives 2^a * v + u < 2^(b + a). Since b + a = n (by omega from a + b = n), this simplifies to 2^a * v + u < 2^n.

    lines 21–23

    uses brgc_aux_concat_bound

      have hbound : 2 ^ a * v + u < 2 ^ n := by
        have hh := brgc_aux_concat_bound hv hu
        simpa only [show b + a = n by omega] using hh
  6. 2^a * v + u < 2^n - 1.

    Suppose for contradiction that 2^a * v + u ≥ 2^n - 1. Combined with the strict upper bound 2^a * v + u < 2^n, linear arithmetic forces 2^a * v + u = 2^n - 1. Substituting this equality into the rotation expression and applying Nat.mod_self implies that the rotated word equals 0, contradicting the previously established fact that it is strictly positive.

    lines 24–28

    uses Nat.mod_self

      have hlt : 2 ^ a * v + u < 2 ^ n - 1 := by
        by_contra hnot
        have hh : 2 ^ a * v + u = 2 ^ n - 1 := by omega
        rw [hh, Nat.mod_self] at heq
        omega
  7. (bitword_rotate n)^[a] (2^b * u + v) = 2^a * v + u.

    Since 2^a * v + u < 2^n - 1, taking the remainder modulo 2^n - 1 leaves 2^a * v + u unchanged (via Nat.mod_eq_of_lt), which concludes the proof.

    line 29

    uses Nat.mod_eq_of_lt

      rwa [Nat.mod_eq_of_lt hlt] at heq
bitword_is_aperiodic_of_prime_iterate_eq_mod
For an n-bit word x with 0 < x < 2^n - 1 where n ≥ 2, rotating x left by m positions produces (2^m * x) mod (2^n - 1), and the result also strictly satisfies 0 < (bitword_rotate n)^[m] x < 2^n - 1.
pow_add
Powers add when multiplying powers with the same base: a^(m + n) = a^m * a^n.
Nat.two_pow_pos
Powers of 2 are strictly positive: 0 < 2^w for every natural number w.
brgc_aux_concat_bound
Concatenating an m-bit prefix a < 2^m and a k-bit suffix b < 2^k satisfies 2^k * a + b < 2^(m + k).
Nat.mod_self
Any natural number modulo itself is zero: n % n = 0.
Nat.mod_eq_of_lt
If a natural number is strictly less than the modulus, the modulo operation leaves it unchanged: if a < b, then a % b = a.

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 bitword_rotate_iterate_cut {n a b u v : ℕ} (hn : 2 ≤ n) (hab : a + b = n)    (hu : u < 2 ^ a) (hv : v < 2 ^ b)    (h0 : 0 < 2 ^ b * u + v) (h1 : 2 ^ b * u + v < 2 ^ n - 1) :    (bitword_rotate n)^[a] (2 ^ b * u + v) = 2 ^ a * v + u := by  obtain ⟨heq, hpos, _⟩ :=    bitword_is_aperiodic_of_prime_iterate_eq_mod n hn (2 ^ b * u + v) h0 h1 a  have hpow : 2 ^ a * 2 ^ b = 2 ^ n := by rw [← pow_add, hab]  have hpred : 2 ^ n - 1 + 1 = 2 ^ n := by    have := Nat.two_pow_pos n    omega  have he : 2 ^ a * (2 ^ b * u + v) =      (2 ^ n - 1) * u + (2 ^ a * v + u) := by    calc      _ = (2 ^ a * 2 ^ b) * u + 2 ^ a * v := by ring      _ = 2 ^ n * u + 2 ^ a * v := by rw [hpow]      _ = (2 ^ n - 1 + 1) * u + 2 ^ a * v := by rw [hpred]      _ = _ := by ring  have hmod : (2 ^ a * (2 ^ b * u + v)) % (2 ^ n - 1) =      (2 ^ a * v + u) % (2 ^ n - 1) := by rw [he]; simp  rw [hmod] at heq  have hbound : 2 ^ a * v + u < 2 ^ n := by    have hh := brgc_aux_concat_bound hv hu    simpa only [show b + a = n by omega] using hh  have hlt : 2 ^ a * v + u < 2 ^ n - 1 := by    by_contra hnot    have hh : 2 ^ a * v + u = 2 ^ n - 1 := by omega    rw [hh, Nat.mod_self] at heq    omega  rwa [Nat.mod_eq_of_lt hlt] at heq
See it in the graphDiscuss this resultChallenge it