AFTD Auto-Formalizing Theoretical Domains

gray_ordered_necklaces_is_gray_path

deforiginal

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