brgc_necklace_first_rank
def
t 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, and no smaller rank s gives a word g(s) in the same necklace. The list D_n orders the nonconstant necklaces by these ranks.
Statement
def brgc_necklace_first_rank (n t : ℕ) : 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; first occurrences and the list D_n
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 2
- brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
- 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.
- Used by 14
- 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…
- brgc_necklace_first_rank_unique_of_rotationTwo first-occurrence Gray ranks representing the same nonconstant necklace are equal.
- 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…
- 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.
- 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…
- 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_first_rank_mod_fourFor length at least two, each first-occurrence rank of a nonconstant necklace is congruent to one or two modulo four.
- 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
/-- t 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, and no smaller rank s gives a word g(s) in the same necklace. The list D_n orders the nonconstant necklaces by these ranks. -/ def brgc_necklace_first_rank (n t : ℕ) : Prop := t < 2 ^ n ∧ brgc_word t ≠ 0 ∧ brgc_word t ≠ 2 ^ n - 1 ∧ ∀ s < t, ¬ bitword_is_rotation n (brgc_word s) (brgc_word t)