brgc_necklace_order_not_consecutive_adjacent_six
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.
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`).
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
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.
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
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$.
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
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.
have h4 : ∀ s, 14 < s → s < 18 → ¬ brgc_necklace_first_rank 6 s := by intro s hs1 hs2 interval_cases s · decide · decide · decide
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.
have h5 : ¬ bitword_necklace_adjacent 6 (brgc_word 14) (brgc_word 18) := by decide exact h5 (H 14 18 h1 h2 h3 h4)
- The proof relies on computational reflection (`decide`) enabled by decidability instances for word rotation, first-rank necklace membership, and necklace adjacency; the arithmetic checks and exhaustion of intermediate cases are handled automatically by `decide` and `omega`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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)