AFTD Auto-Formalizing Theoretical Domains

necklace_graph_has_hamilton_cycle

deforiginal

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