AFTD Auto-Formalizing Theoretical Domains

bitword_is_aperiodic

def

The n-bit word x is aperiodic (primitive): no rotation by 0 < r < n fixes it, i.e. its necklace has n distinct rotations.

Statement

def bitword_is_aperiodic (n x : ℕ) : Prop
Defined in
arXiv:2610.24758 (Optimal single-track Gray codes from Gray-ordered necklaces), Conjecture 1 and the remark after it; periodic necklaces are the exceptions at composite n
Verified
20 Oct 2026
Axioms
none listed
Built on 1
  • 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 6

Lean source view module on GitHub

/-- The `n`-bit word `x` is aperiodic: no rotation by `0 < r < n` fixes it. -/
def bitword_is_aperiodic (n x : ℕ) : Prop :=
  ∀ r, 0 < r → r < n → (bitword_rotate n)^[r] x ≠ x
See it in the graphDiscuss this resultChallenge it