AFTD Auto-Formalizing Theoretical Domains

bitword_necklace_adjacent

def

The necklaces of the n-bit words x and y are adjacent in the necklace graph Q_n: some rotation of x differs from y in exactly one bit.

Statement

def bitword_necklace_adjacent (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; the necklace graph Q_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 10

Lean source view module on GitHub

/-- The necklaces of the n-bit words x and y are adjacent in the necklace graph Q_n: some rotation of x differs from y in exactly one bit. -/
def bitword_necklace_adjacent (n x y : ℕ) : Prop :=
  ∃ r < n, ∃ i < n, (bitword_rotate n)^[r] x ^^^ y = 2 ^ i
See it in the graphDiscuss this resultChallenge it