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
- brgc_inverse_flip_preserves_rotation_maxToggling the last bit of an aperiodic nonconstant word that maximizes its inverse Gray rank over all rotations again maximizes that rank,…
- bitword_is_aperiodic_of_primeFor prime n, every n-bit word other than 0^n and 1^n is aperiodic.
- brgc_necklace_order_consecutive_aperiodic_adjacent_sixThe case n = 6 (composite, with periodic necklaces that break the adjacency) of the aperiodic adjacency conjecture: consecutive aperiodic…
- brgc_necklace_order_consecutive_aperiodic_adjacent_eightThe case n = 8 (composite, with periodic necklaces that break the adjacency) of the aperiodic adjacency conjecture: consecutive aperiodic…
- brgc_necklace_order_consecutive_aperiodic_adjacent_nineThe case n = 9 (composite, with periodic necklaces that break the adjacency) of the aperiodic adjacency conjecture: consecutive aperiodic…
- bitword_is_aperiodic_sanitySanity check: the 6-bit word 001011 is aperiodic, while 001001 is fixed by rotation by 3.
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