necklace_graph_has_hamilton_cycle
There 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 first-occurrence Gray code ranks of non-constant necklaces, every first-occurrence Gray code rank of a non-constant necklace of length n appears at some index i < m, and for every i < m, the necklace of cycle i is adjacent in the necklace graph to the necklace of cycle ((i + 1) % m).
Statement
def necklace_graph_has_hamilton_cycle (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
Given $n : ℕ$, necklace_graph_has_hamilton_cycle n asserts the existence of a sequence cycle : ℕ → ℕ such that, defining $m = (2^n - 2) / n$:
1. For every natural number $i < m$, cycle i is the BRGC first rank of an $n$-bit necklace (that is: cycle i < 2^n, its binary reflected Gray code word is neither $0$ nor $2^n - 1$, and for every $s < cycle i$, the Gray code word of $s$ is not a cyclic rotation of the Gray code word of cycle i);
2. For all $i, j < m$, if cycle i = cycle j, then $i = j$ (the sequence is injective on $\{0, \dots, m - 1\}$);
3. For every natural number $t$, if $t$ is the BRGC first rank of an $n$-bit necklace, then there exists some $i < m$ such that cycle i = t (the sequence surjectively covers all BRGC necklace first ranks);
4. For every natural number $i < m$, the Gray code word of cycle i and the Gray code word of cycle ((i + 1) % m) are necklace-adjacent, meaning there exist $r < n$ and $k < n$ such that rotating the Gray code word of cycle i left by $r$ positions produces a word whose bitwise XOR with the Gray code word of cycle ((i + 1) % m) equals $2^k$ (Hamming distance 1).
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 necklace graph Q_n has a Hamilton cycle visiting all non-constant binary necklaces of length n in order. -/ def necklace_graph_has_hamilton_cycle (n : ℕ) : Prop := ∃ cycle : ℕ → ℕ, let m := (2 ^ n - 2) / n (∀ i < m, brgc_necklace_first_rank n (cycle i)) ∧ (∀ i < m, ∀ j < m, cycle i = cycle j → i = j) ∧ (∀ t, brgc_necklace_first_rank n t → ∃ i < m, cycle i = t) ∧ ∀ i < m, bitword_necklace_adjacent n (brgc_word (cycle i)) (brgc_word (cycle ((i + 1) % m)))