AFTD Auto-Formalizing Theoretical Domains

brgc_necklace_order_not_consecutive_adjacent_six

theoremverified

Primality cannot be dropped from the adjacency conjecture: at n = 6 the consecutive necklaces 001001 and 011011 of D_6 (both periodic) are not adjacent in Q_6. This is the smallest n where it fails.

Statement

theorem brgc_necklace_order_not_consecutive_adjacent_six :
    ¬ ∀ t t' : ℕ, brgc_necklace_first_rank 6 t → brgc_necklace_first_rank 6 t' → t < t' →
      (∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 6 s) →
      bitword_necklace_adjacent 6 (brgc_word t) (brgc_word t')
Source
arXiv:2610.24758 (Optimal single-track Gray codes from Gray-ordered necklaces), Conjecture 1 and the remark after it; the paper names n = 9, 15, 21; n = 6 is the smallest failure (exp 1938)
Verified
20 Oct 2026
Axioms
Quot.soundpropext
Built on 5
  • brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
  • 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.
  • 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.
  • bitword_rotateCyclic rotation of an n-bit word x (a number below 2^n) by one position: the word is shifted up and its top bit moves to the bottom.

The proof, explained

The theorem disproves the consecutive necklace adjacency conjecture for dimension $n = 6$ by counterexample. Assuming for contradiction that any two consecutive first-rank necklace representatives in the binary reflected Gray code (BRGC) order are adjacent in the hypercube $Q_6$, the proof exhibits the ranks $t = 14$ and $t' = 18$. A finite case exhaustion over the intermediate ranks 15, 16, and 17 confirms that 14 and 18 are consecutive first-rank representatives, corresponding to the periodic 6-bit necklaces $001001_2$ and $011011_2$. Finally, computational reflection verifies that these two necklaces are not adjacent in $Q_6$ under any cyclic shift, contradicting the assumption.

  1. The relations of bitword rotation, being a first-rank necklace representative, and necklace adjacency are all decidable.

    For each of the three relations, unfolding its definition reveals only bounded quantifiers (existential over rotations $r < n$ and bit flips $i < n$, and universal over earlier ranks $s < t$) and decidable comparisons. Lean's typeclass inference (`infer_instance`) automatically synthesizes `Decidable` instances for each, enabling subsequent proofs by computational reflection (`decide`).

    lines 1–15

    instance brgc_necklace_order_not_consecutive_adjacent_six_dec_rot (n x y : ℕ) :
        Decidable (bitword_is_rotation n x y) := by
      unfold bitword_is_rotation
      infer_instance
    
    instance brgc_necklace_order_not_consecutive_adjacent_six_dec_first_rank (n t : ℕ) :
        Decidable (brgc_necklace_first_rank n t) := by
      unfold brgc_necklace_first_rank
      infer_instance
    
    instance brgc_necklace_order_not_consecutive_adjacent_six_dec_adj (n x y : ℕ) :
        Decidable (bitword_necklace_adjacent n x y) := by
      unfold bitword_necklace_adjacent
      infer_instance
    
  2. It suffices to derive a contradiction from the assumption that consecutive first-rank necklace representatives are adjacent.

    We assume the negation of the theorem (hypothesis $H$): for any two consecutive first-rank necklace representatives $t < t'$ at dimension 6, their corresponding BRGC words are adjacent in the hypercube.

    lines 16–20

    theorem brgc_necklace_order_not_consecutive_adjacent_six :
        ¬ ∀ t t' : ℕ, brgc_necklace_first_rank 6 t → brgc_necklace_first_rank 6 t' → t < t' →
          (∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 6 s) →
          bitword_necklace_adjacent 6 (brgc_word t) (brgc_word t') := by
      intro H
  3. The ranks 14 and 18 are first-rank necklace representatives, with $14 < 18$.

    Evaluating the definition `brgc_necklace_first_rank` by computation (`decide`) establishes that both 14 and 18 are the earliest ranks in the BRGC order for their respective necklaces, and linear arithmetic (`omega`) confirms $14 < 18$.

    lines 21–23

      have h1 : brgc_necklace_first_rank 6 14 := by decide
      have h2 : brgc_necklace_first_rank 6 18 := by decide
      have h3 : 14 < 18 := by omega
  4. The ranks 14 and 18 are consecutive first-rank necklace representatives, with no other first ranks in between.

    We introduce an arbitrary integer $s$ satisfying $14 < s < 18$. The tactic `interval_cases` reduces this to the three possibilities $s = 15$, $s = 16$, and $s = 17$. For each case, `decide` computes that $s$ fails the first-rank condition because its BRGC word is a rotation of a word that appeared at an earlier rank.

    lines 24–29

      have h4 : ∀ s, 14 < s → s < 18 → ¬ brgc_necklace_first_rank 6 s := by
        intro s hs1 hs2
        interval_cases s
        · decide
        · decide
        · decide
  5. The necklaces at ranks 14 and 18 are not adjacent, contradicting the assumption and completing the proof.

    The BRGC words at ranks 14 and 18 are $001001_2$ and $011011_2$. Direct computation (`decide`) confirms that no cyclic shift of $001001_2$ differs from $011011_2$ in exactly one bit, so the necklaces are not adjacent. Applying the assumed adjacency property $H$ to $t = 14$ and $t' = 18$ asserts they must be adjacent, which produces a contradiction.

    lines 30–31

      have h5 : ¬ bitword_necklace_adjacent 6 (brgc_word 14) (brgc_word 18) := by decide
      exact h5 (H 14 18 h1 h2 h3 h4)

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

instance brgc_necklace_order_not_consecutive_adjacent_six_dec_rot (n x y : ℕ) :    Decidable (bitword_is_rotation n x y) := by  unfold bitword_is_rotation  infer_instanceinstance brgc_necklace_order_not_consecutive_adjacent_six_dec_first_rank (n t : ℕ) :    Decidable (brgc_necklace_first_rank n t) := by  unfold brgc_necklace_first_rank  infer_instanceinstance brgc_necklace_order_not_consecutive_adjacent_six_dec_adj (n x y : ℕ) :    Decidable (bitword_necklace_adjacent n x y) := by  unfold bitword_necklace_adjacent  infer_instancetheorem brgc_necklace_order_not_consecutive_adjacent_six :    ¬ ∀ t t' : ℕ, brgc_necklace_first_rank 6 t → brgc_necklace_first_rank 6 t' → t < t' →      (∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 6 s) →      bitword_necklace_adjacent 6 (brgc_word t) (brgc_word t') := by  intro H  have h1 : brgc_necklace_first_rank 6 14 := by decide  have h2 : brgc_necklace_first_rank 6 18 := by decide  have h3 : 14 < 18 := by omega  have h4 : ∀ s, 14 < s → s < 18 → ¬ brgc_necklace_first_rank 6 s := by    intro s hs1 hs2    interval_cases s    · decide    · decide    · decide  have h5 : ¬ bitword_necklace_adjacent 6 (brgc_word 14) (brgc_word 18) := by decide  exact h5 (H 14 18 h1 h2 h3 h4)
See it in the graphDiscuss this resultChallenge it