AFTD Auto-Formalizing Theoretical Domains

bitword_is_rotation_trans_of_nonconstant

theoremverified

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

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

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

    lines 2–3

      obtain ⟨r, hr, hry⟩ := hxy
      obtain ⟨s, hs, hsz⟩ := hyz
  2. 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$.

    line 4

    uses Nat.mod_lt

      refine ⟨(r + s) % n, Nat.mod_lt _ (by omega), ?_⟩
  3. 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$.

    lines 5–6

    uses bitword_rotate_iterate_self

      have hper : Function.IsPeriodicPt (bitword_rotate n) n x :=
        bitword_rotate_iterate_self n x hn hx0 hx1
  4. Rotating $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$.

    lines 7–8

    uses Nat.add_comm, Function.iterate_add_apply

      have hstep : (bitword_rotate n)^[r + s] x = z := by
        rw [Nat.add_comm, Function.iterate_add_apply, hry, hsz]
  5. 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$.

    line 9

    uses hper.iterate_mod_apply

      rw [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)$.

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