bitword_rotate
def
Cyclic 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.
Statement
def bitword_rotate (n x : ℕ) : ℕ- 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; cyclic shift of words
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Used by 29
- alpha_lexical_odd_completion_iff_rotation_maxFor any length n at least three, a nonempty positive sequence of sum n−1 is lexical if and only if its odd-parity binary completion is…
- 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…
- bitword_is_aperiodicThe n-bit word x is aperiodic (primitive): no rotation by 0 < r < n fixes it, i.e. its necklace has n distinct rotations.
- brgc_necklace_order_consecutive_adjacent_sevenThe case n = 7 of the conjecture: consecutive necklaces of D_7 are adjacent in Q_7.
- lexical_degree_seventeen_class_a_counterexampleThe lexical sequences a = (3,1,1,3,3,2,2,1) and b = (3,1,1,2,1,3,2,2,1) both have degree 16, are adjacent in the source lexical order…
- bitword_rotate_iterate_cutCyclically rotating an n-bit nonconstant word left by a positions exchanges its prefix of length a and its suffix of length b, where a+b=n.
- 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_rotation_trans_of_nonconstantFor length at least two, cyclic-rotation equivalence is transitive when the initial word is a nonconstant n-bit word.
- brgc_local_reflection_generator_obstructionTwo strict maximum-rank primitive generators whose proposed local generator reflection is not maximum-rank; an obstruction to a naive…
- bitword_rotate_three_fourSanity check: rotating the 3-bit words 100 and 011 gives 001 and 110.
- bitword_is_rotationThe 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.
- 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…
- alpha_lexical_odd_completion_iff_rotation_max_of_primeThe proposed encoding bridge between positive lexical sequences and nonconstant odd-parity maximum-rank necklace representatives at odd…
- bitword_is_aperiodic_of_primeFor prime n, every n-bit word other than 0^n and 1^n is aperiodic.
- bitword_rotate_iterate_selfLeft rotation n times fixes every nonconstant n-bit word when n is at least two.
- 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…
- alpha_lexical_terminal_predecessor_simple_star_obstructionThe two displayed lexical sequences are adjacent among sequences of degree 19 and have meet f=(2,1,1). The later sequence has a lexical…
- brgc_necklace_first_rank_word_oddFor length at least two, the first nonconstant representative in Gray order has final bit one.
- bitword_necklace_adjacentThe 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.
- alpha_lexical_example_elevenKernel-checked encoding of the length-eleven example in arXiv:0810.5205, Example 3.2, including its one-bit completed words and the…
- 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_inverse_rotate_tent_formulaIn inverse Gray-rank coordinates, cyclic left rotation is the two-branch integer tent map, with the rank parity carried along.
- 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
/-- Cyclic 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. -/ def bitword_rotate (n x : ℕ) : ℕ := (2 * x) % 2 ^ n + x / 2 ^ (n - 1)