bitword_is_aperiodic_sanity
Sanity check: the 6-bit word 001011 is aperiodic, while 001001 is fixed by rotation by 3.
Statement
theorem bitword_is_aperiodic_sanity : bitword_is_aperiodic 6 11 ∧ ¬ bitword_is_aperiodic 6 9- Source
- sanity check for bitword_is_aperiodic
- Verified
- 20 Oct 2026
- Axioms
propext- Built on 2
- bitword_is_aperiodicThe n-bit word x is aperiodic (primitive): no rotation by 0 < r < n fixes it, i.e. its necklace has n distinct rotations.
- 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.
The proof, explained
The theorem performs a sanity check on the definition of an aperiodic bitword: the 6-bit word 11 (binary 001011) is aperiodic, whereas 9 (binary 001001) is not. To disprove aperiodicity for 9, the proof exhibits the shift r = 3 as a counterexample, since rotating 001001 by 3 positions leaves it invariant. To establish aperiodicity for 11, the definition requires verifying that no shift r with 0 < r < 6 fixes 11, which is proved by exhaustively checking the five cases r ∈ {1, 2, 3, 4, 5} by direct computation.
The word 9 is not aperiodic, reducing the goal to proving that 11 is aperiodic.
To show that the 6-bit word 9 is not aperiodic, we assume for contradiction that it is aperiodic (hypothesis h). By definition, this assumption asserts that rotating 9 by any shift r with 0 < r < 6 never yields 9. Specializing to r = 3, we have 0 < 3 and 3 < 6, but rotating 9 (binary 001001) by 3 positions evaluates to 9. Applying h to these facts produces a contradiction. This establishes the second conjunct ¬bitword_is_aperiodic 6 9 and leaves only the first conjunct bitword_is_aperiodic 6 11 to be proved.
refine ⟨?_, fun h => h 3 (by decide) (by decide) (by decide)⟩
The word 11 is aperiodic, completing the proof of the conjunction.
To prove that 11 is aperiodic, we introduce an arbitrary rotation shift r along with the hypotheses 0 < r and r < 6. These bounds restrict r to the five integers {1, 2, 3, 4, 5}. The interval_cases tactic branches on these five possibilities, and in each case computational evaluation (decide) evaluates the rotated word (bitword_rotate 6)^[r] 11—yielding 22, 44, 25, 50, and 37 respectively—and confirms that none equals 11.
intro r h0 h6 interval_cases r <;> decide
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_aperiodic_sanity : bitword_is_aperiodic 6 11 ∧ ¬ bitword_is_aperiodic 6 9 := by refine ⟨?_, fun h => h 3 (by decide) (by decide) (by decide)⟩ intro r h0 h6 interval_cases r <;> decide