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
- 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.
- brgc_necklace_first_rank_unique_of_rotationTwo first-occurrence Gray ranks representing the same nonconstant necklace are equal.
- 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.
- bitword_is_rotation_trans_of_nonconstantFor length at least two, cyclic-rotation equivalence is transitive when the initial word is a nonconstant n-bit word.
- brgc_necklace_first_rank_exists_of_nonconstantEvery nonconstant binary word of length at least two has a first-occurrence Gray rank in its rotation class.
- brgc_necklace_first_rank_rotation_maxRotating a first-occurrence representative right once gives a representative of maximum inverse Gray rank in its rotation class; the…
- bitword_is_rotation_symm_of_nonconstantFor length at least two, cyclic-rotation equivalence is symmetric on a nonconstant n-bit word.
- brgc_necklace_order_consecutive_adjacent_fiveThe case n = 5 of the conjecture: consecutive necklaces of D_5 are adjacent in Q_5.
- brgc_necklace_first_rank_min_rotationsEvery rotation of a first-occurrence representative has inverse Gray rank at least its first-occurrence rank.
- 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_first_rank_word_oddFor length at least two, the first nonconstant representative in Gray order has final bit one.
- brgc_necklace_first_rankt is the BRGC rank of the first occurrence of a nonconstant binary necklace of length n: t < 2^n, the word g(t) is neither 0^n nor 1^n,…
- 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 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