AFTD Auto-Formalizing Theoretical Domains

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

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)
See it in the graphDiscuss this resultChallenge it