bitword_is_rotation_symm_of_nonconstant
For length at least two, cyclic-rotation equivalence is symmetric on a nonconstant n-bit word.
Statement
theorem bitword_is_rotation_symm_of_nonconstant (n x y : ℕ) (hn : 2 ≤ n) (hx0 : 0 < x) (hx1 : x < 2 ^ n - 1) (h : bitword_is_rotation n x y) : bitword_is_rotation n y x- 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 2
- brgc_necklace_first_rank_unique_of_rotationTwo first-occurrence Gray ranks representing the same nonconstant necklace are equal.
- 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 hypothesis that x cyclically rotates to y gives an integer r with 0 ≤ r < n such that y is the r-th rotation of x. If r = 0, then x = y and the rotation relation is trivially symmetric with witness 0. If r > 0, rotating y by the complementary count n - r < n amounts to applying (n - r) + r = n rotations to x. Because x is a nonconstant word of length n ≥ 2, rotating x by n positions returns x, so n - r witnesses that x is a rotation of y.
There exists an integer r < n such that rotating x by r positions produces y, and we can distinguish the cases r = 0 and r > 0.
By definition of cyclic rotation (bitword_is_rotation), the assumption gives a shift r < n such that applying the cyclic rotation r times to x yields y. We then split on whether r = 0 or r > 0 using Nat.eq_zero_or_pos.
uses
Nat.eq_zero_or_posobtain ⟨r, hr, hry⟩ := h rcases Nat.eq_zero_or_pos r with rfl | hrpos
If r = 0, then x is a cyclic rotation of y.
When r = 0, rotating by zero positions is the identity, so y = x. Since n ≥ 2, we have 0 < n by linear arithmetic (omega). Rotating y by zero positions gives y, which equals x (simpa), so 0 witnesses that x is a rotation of y.
· exact ⟨0, by omega, by simpa using hry.symm⟩
If r > 0, rotating y by n - r positions yields x, showing that x is a cyclic rotation of y.
We provide n - r as the rotation witness. Since 0 < r < n, we have n - r < n by linear arithmetic (omega). Rotating y by n - r positions means applying n - r rotations to the r-th rotation of x. Rewriting using Function.iterate_add_apply and Nat.sub_add_cancel (via Nat.le_of_lt) shows this composite rotation is exactly n rotations on x. Since x is a nonconstant word (0 < x < 2^n - 1) of length n ≥ 2, bitword_rotate_iterate_self guarantees that rotating x by n positions returns x.
uses
Function.iterate_add_apply,Nat.sub_add_cancel,Nat.le_of_lt,bitword_rotate_iterate_self· refine ⟨n - r, by omega, ?_⟩ rw [← hry, ← Function.iterate_add_apply, Nat.sub_add_cancel (Nat.le_of_lt hr)] exact bitword_rotate_iterate_self n x hn hx0 hx1
Nat.eq_zero_or_pos- Every natural number is either zero or strictly positive.
Function.iterate_add_apply- Iterating an endofunction m + n times equals the composition of iterating it m times and iterating it n times: f^[m + n] x = f^[m] (f^[n] x).
Nat.sub_add_cancel- For natural numbers with m ≤ n, subtracting m from n and then adding m recovers n: (n - m) + m = n.
Nat.le_of_lt- A strict inequality between natural numbers implies a non-strict inequality: n < m implies n ≤ m.
bitword_rotate_iterate_self- Rotating a nonconstant word x of bit length n ≥ 2 (satisfying 0 < x < 2^n - 1) by n positions returns 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
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_symm_of_nonconstant (n x y : ℕ) (hn : 2 ≤ n) (hx0 : 0 < x) (hx1 : x < 2 ^ n - 1) (h : bitword_is_rotation n x y) : bitword_is_rotation n y x := by obtain ⟨r, hr, hry⟩ := h rcases Nat.eq_zero_or_pos r with rfl | hrpos · exact ⟨0, by omega, by simpa using hry.symm⟩ · refine ⟨n - r, by omega, ?_⟩ rw [← hry, ← Function.iterate_add_apply, Nat.sub_add_cancel (Nat.le_of_lt hr)] exact bitword_rotate_iterate_self n x hn hx0 hx1