AFTD Auto-Formalizing Theoretical Domains

bitword_rotate_iterate_self

theoremverified

Left rotation n times fixes every nonconstant n-bit word when n is at least two.

Statement

theorem bitword_rotate_iterate_self (n x : ℕ) (hn : 2 ≤ n) (hx0 : 0 < x)
    (hx1 : x < 2 ^ n - 1) : (bitword_rotate n)^[n] x = x
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 2
  • 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.
  • bitword_rotate_iterate_cutCyclically 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.
Used by 4

The proof, explained

The proof deduces the theorem by specializing the general block-rotation lemma `bitword_rotate_iterate_cut` to a full period. Viewing the n-bit word x as split into two blocks of lengths a = n and b = 0 (with main block u = x and trivial block v = 0), rotating left by n positions cyclically swaps the blocks. Since x < 2^n - 1 implies x < 2^n, all preconditions of the lemma are satisfied, yielding (bitword_rotate n)^[n] (2^0 * x + 0) = 2^n * 0 + x. Simplifying the arithmetic expressions on both sides shows that rotating n times fixes x.

  1. x < 2 ^ n

    From the hypothesis x < 2^n - 1 (hx1), linear integer arithmetic immediately implies the weaker upper bound x < 2^n.

    line 3

      have hx : x < 2 ^ n := by omega
  2. (bitword_rotate n)^[n] (2 ^ 0 * x + 0) = 2 ^ n * 0 + x

    We specialize `bitword_rotate_iterate_cut` to parameters a = n, b = 0, u = x, and v = 0. Its preconditions are verified: 2 ≤ n is given by hn; n + 0 = n holds by linear arithmetic; u < 2^a is the bound x < 2^n established in the previous step; v < 2^b is 0 < 2^0 = 1, verified by computation; and the nonconstant word bounds 0 < 2^0 * x + 0 and 2^0 * x + 0 < 2^n - 1 simplify directly to the hypotheses 0 < x (hx0) and x < 2^n - 1 (hx1).

    lines 4–7

    uses bitword_rotate_iterate_cut

      have hh := bitword_rotate_iterate_cut hn (show n + 0 = n by omega) hx
        (show (0 : ℕ) < 2 ^ 0 by decide)
        (show 0 < 2 ^ 0 * x + 0 by simpa using hx0)
        (show 2 ^ 0 * x + 0 < 2 ^ n - 1 by simpa using hx1)
  3. (bitword_rotate n)^[n] x = x

    Simplifying the arithmetic identities 2^0 * x + 0 = x and 2^n * 0 + x = x in the equality established in the previous step completes the proof.

    line 8

      simpa using hh
bitword_rotate_iterate_cut
For an n-bit word split into two bit-strings of lengths a and b (with a + b = n), representing the value 2^b * u + v with u < 2^a and v < 2^b, rotating left a times cyclically swaps the two parts to yield 2^a * v + u, provided 2 ≤ n and the word is nonconstant (0 < 2^b * u + v < 2^n - 1).

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_self (n x : ℕ) (hn : 2 ≤ n) (hx0 : 0 < x)    (hx1 : x < 2 ^ n - 1) : (bitword_rotate n)^[n] x = x := by  have hx : x < 2 ^ n := by omega  have hh := bitword_rotate_iterate_cut hn (show n + 0 = n by omega) hx    (show (0 : ℕ) < 2 ^ 0 by decide)    (show 0 < 2 ^ 0 * x + 0 by simpa using hx0)    (show 2 ^ 0 * x + 0 < 2 ^ n - 1 by simpa using hx1)  simpa using hh
See it in the graphDiscuss this resultChallenge it