AFTD Auto-Formalizing Theoretical Domains

bitword_is_rotation

def

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

Statement

def bitword_is_rotation (n x y : ℕ) : Prop
Defined in
arXiv:2610.24758 (Optimal single-track Gray codes from Gray-ordered necklaces), Conjecture 1 (prime case of a conjecture from 2007), Sec. 1; necklaces as classes under cyclic shift
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 15

Lean source view module on GitHub

/-- The 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. -/
def bitword_is_rotation (n x y : ℕ) : Prop := ∃ r < n, (bitword_rotate n)^[r] x = y
See it in the graphDiscuss this resultChallenge it