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
- brgc_necklace_order_not_consecutive_adjacent_sixPrimality cannot be dropped from the adjacency conjecture: at n = 6 the consecutive necklaces 001001 and 011011 of D_6 (both periodic) are…
- brgc_necklace_order_consecutive_adjacent_sevenThe case n = 7 of the conjecture: consecutive necklaces of D_7 are adjacent in Q_7.
- necklace_graph_has_hamilton_cycleThere exists an indexing cycle of the non-constant necklaces of length n such that the first m = (2^n - 2) / n values are distinct valid…
- bitword_necklace_adjacent_three_one_threeSanity check: 100 is a rotation of 001, and the necklaces of 001 and 011 are adjacent in Q_3.
- brgc_necklace_order_consecutive_adjacent_fiveThe case n = 5 of the conjecture: consecutive necklaces of D_5 are adjacent in Q_5.
- 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…
- gray_ordered_necklaces_is_gray_pathThe list D_n of non-constant binary necklaces of length n, ordered by the rank of their first occurrences in the binary reflected Gray…
- bitword_necklace_adjacent_of_brgc_rank_reflectionIf two Gray ranks differ by exclusive-or with k+1 low one-bits and k is less than the word length, their words are adjacent with rotation…
- 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…
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