AFTD Auto-Formalizing Theoretical Domains

bitword_is_aperiodic_sanity

theoremverified

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.

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

    line 2

      refine ⟨?_, fun h => h 3 (by decide) (by decide) (by decide)⟩
  2. 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.

    lines 3–4

      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

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