gray_ordered_necklaces_is_gray_path
The list D_n of non-constant binary necklaces of length n, ordered by the rank of their first occurrences in the binary reflected Gray code, forms a Gray path in the necklace graph Q_n: consecutive necklaces in this order are adjacent in Q_n.
Statement
def gray_ordered_necklaces_is_gray_path (n : ℕ) : Prop
- Related work
- arXiv:2610.24758: Optimal single-track Gray codes from Gray-ordered necklaces
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 3
- 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,…
- 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.
- brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
Read back from the Lean
The declaration gray_ordered_necklaces_is_gray_path asserts that for a given natural number n, and for all natural numbers t and t':
If:
1. t is the first rank of a necklace in binary reflected Gray code (BRGC) order, meaning:
- t < 2^n,
- brgc_word t ≠ 0 (where brgc_word t = t ^^^ (t / 2)),
- brgc_word t ≠ 2^n - 1, and
- for all s < t, brgc_word t is not an r-step cyclic rotation (for any r < n) of brgc_word s;
2. t' is also the first rank of a necklace in BRGC order (satisfying the same four conditions);
3. t < t'; and
4. t and t' are consecutive such ranks, meaning there is no s strictly between t and t' (t < s and s < t') that satisfies the first-rank condition;
Then:
brgc_word t and brgc_word t' are necklace-adjacent, meaning there exist r < n and i < n such that rotating brgc_word t cyclically by r steps yields a word whose bitwise XOR with brgc_word t' equals 2^i (that is, some cyclic rotation of brgc_word t differs from brgc_word t' in exactly bit position i).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The list of non-constant binary necklaces ordered by first occurrence in the binary reflected Gray code forms a Gray path in the necklace graph. -/ def gray_ordered_necklaces_is_gray_path (n : ℕ) : Prop := ∀ t t' : ℕ, brgc_necklace_first_rank n t → brgc_necklace_first_rank n t' → t < t' → (∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank n s) → bitword_necklace_adjacent n (brgc_word t) (brgc_word t')