bitword_is_rotation_trans_of_nonconstant
For length at least two, cyclic-rotation equivalence is transitive when the initial word is a nonconstant n-bit word.
Statement
theorem bitword_is_rotation_trans_of_nonconstant (n x y z : ℕ) (hn : 2 ≤ n) (hx0 : 0 < x) (hx1 : x < 2 ^ n - 1) (hxy : bitword_is_rotation n x y) (hyz : bitword_is_rotation n y z) : bitword_is_rotation n x z- Source
- Rotation bookkeeping for OP-392, arXiv:2610.24758, Conjecture 1.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- bitword_is_rotationThe n-bit word y is a cyclic rotation of the n-bit word x, i.e. x and y lie in the same binary necklace.
- bitword_rotate_iterate_selfLeft rotation n times fixes every nonconstant n-bit word when n is at least two.
- 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.
- Used by 1
- brgc_necklace_first_rank_exists_of_nonconstantEvery nonconstant binary word of length at least two has a first-occurrence Gray rank in its rotation class.
The proof, explained
The proof establishes transitivity of cyclic rotation for nonconstant bitwords by composing two rotation steps of sizes $r$ and $s$ into a single rotation of size $(r + s) \bmod n$. Because any nonconstant $n$-bit word is $n$-periodic under rotation, rotating $(r + s) \bmod n$ times is identical to rotating $r + s$ times, which successively transforms $x$ to $y$ and $y$ to $z$.
There exist rotation counts $r, s < n$ such that rotating $x$ by $r$ positions gives $y$, and rotating $y$ by $s$ positions gives $z$.
By definition of `bitword_is_rotation`, the assumption that $x$ rotates to $y$ provides a witness $r < n$ such that applying `bitword_rotate n` to $x$ for $r$ iterations yields $y$. Similarly, the assumption that $y$ rotates to $z$ yields a witness $s < n$ such that applying `bitword_rotate n` to $y$ for $s$ iterations yields $z$.
obtain ⟨r, hr, hry⟩ := hxy obtain ⟨s, hs, hsz⟩ := hyz
It suffices to show that rotating $x$ by $(r + s) \bmod n$ positions yields $z$.
We choose $(r + s) \bmod n$ as the candidate rotation count from $x$ to $z$. From the hypothesis $2 \le n$, linear arithmetic (`omega`) deduces $0 < n$, which by `Nat.mod_lt` ensures $(r + s) \bmod n < n$. This leaves the goal of showing that applying the rotation $(r + s) \bmod n$ times to $x$ produces $z$.
uses
Nat.mod_ltrefine ⟨(r + s) % n, Nat.mod_lt _ (by omega), ?_⟩
The word $x$ is an $n$-periodic point under bitwise rotation: rotating $x$ by $n$ positions returns $x$.
Since $n \ge 2$ and $x$ is nonconstant ($0 < x < 2^n - 1$), the lemma `bitword_rotate_iterate_self` applies directly to show that $n$ iterations of `bitword_rotate n` on $x$ return $x$, establishing that $x$ is a periodic point of period $n$.
uses
bitword_rotate_iterate_selfhave hper : Function.IsPeriodicPt (bitword_rotate n) n x := bitword_rotate_iterate_self n x hn hx0 hx1Rotating $x$ by $r + s$ positions yields $z$.
By commutativity of addition (`Nat.add_comm`), $r + s = s + r$. Applying `Function.iterate_add_apply`, iterating the rotation $s + r$ times decomposes into iterating $r$ times followed by $s$ times. Since the first $r$ rotations turn $x$ into $y$, and the subsequent $s$ rotations turn $y$ into $z$, the combined $r + s$ rotations transform $x$ into $z$.
uses
Nat.add_comm,Function.iterate_add_applyhave hstep : (bitword_rotate n)^[r + s] x = z := by rw [Nat.add_comm, Function.iterate_add_apply, hry, hsz]
Rotating $x$ by $(r + s) \bmod n$ positions yields $z$, concluding the proof.
Using the fact that $x$ is $n$-periodic under rotation (`hper`), `hper.iterate_mod_apply` rewrites $(r + s) \bmod n$ iterations on $x$ into $r + s$ iterations on $x$. By the previous step (`hstep`), this equals $z$.
uses
hper.iterate_mod_applyrw [hper.iterate_mod_apply (r + s), hstep]
Nat.mod_lt- For any natural numbers $x$ and $y$ with $0 < y$, the remainder $x \bmod y$ is strictly less than $y$.
bitword_rotate_iterate_self- For $n \ge 2$ and any nonconstant $n$-bit word $x$ (satisfying $0 < x < 2^n - 1$), rotating $x$ cyclically $n$ times yields $x$ itself.
Nat.add_comm- Addition of natural numbers is commutative: $n + m = m + n$.
Function.iterate_add_apply- Iterating a function $m + n$ times equals iterating it $m$ times after iterating it $n$ times: $f^{m+n}(x) = f^m(f^n(x))$.
hper.iterate_mod_apply- For an $n$-periodic point $x$ of a function $f$, iterating $f$ by $m \bmod n$ times at $x$ yields the same result as iterating $f$ by $m$ times: $f^{m \bmod n}(x) = f^m(x)$.
- The theorem requires the initial word $x$ to be nonconstant ($0 < x < 2^n - 1$) because the periodicity lemma `bitword_rotate_iterate_self` is established under this hypothesis.
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_is_rotation_trans_of_nonconstant (n x y z : ℕ) (hn : 2 ≤ n) (hx0 : 0 < x) (hx1 : x < 2 ^ n - 1) (hxy : bitword_is_rotation n x y) (hyz : bitword_is_rotation n y z) : bitword_is_rotation n x z := by obtain ⟨r, hr, hry⟩ := hxy obtain ⟨s, hs, hsz⟩ := hyz refine ⟨(r + s) % n, Nat.mod_lt _ (by omega), ?_⟩ have hper : Function.IsPeriodicPt (bitword_rotate n) n x := bitword_rotate_iterate_self n x hn hx0 hx1 have hstep : (bitword_rotate n)^[r + s] x = z := by rw [Nat.add_comm, Function.iterate_add_apply, hry, hsz] rw [hper.iterate_mod_apply (r + s), hstep]