bitword_rotate_iterate_self
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
- bitword_is_rotation_trans_of_nonconstantFor length at least two, cyclic-rotation equivalence is transitive when the initial word is a nonconstant n-bit word.
- 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…
- bitword_is_rotation_symm_of_nonconstantFor length at least two, cyclic-rotation equivalence is symmetric on a nonconstant n-bit word.
- brgc_necklace_first_rank_min_rotationsEvery rotation of a first-occurrence representative has inverse Gray rank at least its first-occurrence rank.
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.
x < 2 ^ n
From the hypothesis x < 2^n - 1 (hx1), linear integer arithmetic immediately implies the weaker upper bound x < 2^n.
have hx : x < 2 ^ n := by omega
(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).
uses
bitword_rotate_iterate_cuthave 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)
(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.
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).
- To apply the block-rotation lemma `bitword_rotate_iterate_cut`, which requires splitting an n-bit word into two chunks of lengths a and b summing to n, the proof uses the degenerate split n + 0 = n. This introduces the formal expressions 2^0 * x + 0 for x and 2^n * 0 + x for the rotated word, which have no counterpart on paper where rotating an n-bit word by n bits trivially returns the word.
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_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