bitword_rotate_iterate_cut
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
- 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,…
- brgc_necklace_first_rank_rotation_maxRotating a first-occurrence representative right once gives a representative of maximum inverse Gray rank in its rotation class; the…
- alpha_lexical_odd_completion_iff_rotation_max_of_primeThe proposed encoding bridge between positive lexical sequences and nonconstant odd-parity maximum-rank necklace representatives at odd…
- bitword_rotate_iterate_selfLeft rotation n times fixes every nonconstant n-bit word when n is at least two.
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.
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.
uses
bitword_is_aperiodic_of_prime_iterate_eq_modobtain ⟨heq, hpos, _⟩ := bitword_is_aperiodic_of_prime_iterate_eq_mod n hn (2 ^ b * u + v) h0 h1 a2^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).
uses
pow_add,Nat.two_pow_poshave 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
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).
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
(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).
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
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.
uses
brgc_aux_concat_boundhave 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
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.
uses
Nat.mod_selfhave 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
(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.
uses
Nat.mod_eq_of_ltrwa [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
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 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