brgc_necklace_order_consecutive_adjacent_five
The case n = 5 of the conjecture: consecutive necklaces of D_5 are adjacent in Q_5.
Statement
theorem brgc_necklace_order_consecutive_adjacent_five :
∀ t t' : ℕ, brgc_necklace_first_rank 5 t →
brgc_necklace_first_rank 5 t' → t < t' →
(∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 5 s) →
bitword_necklace_adjacent 5 (brgc_word t) (brgc_word t')- Formalizes
- arXiv:2610.24758 (Optimal single-track Gray codes from Gray-ordered necklaces), Conjecture 1 (prime case of a conjecture from 2007), Sec. 1; the case n = 5, verified by computation in the paper
- 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 establishes that consecutive necklace representatives in the 5-bit binary reflected Gray code (BRGC) order are adjacent in the hypercube $Q_5$ (up to cyclic rotation). Because any 5-bit necklace first rank is strictly less than $2^5 = 32$, the statement is first proved for the finite domain `Fin 32` by exhaustive computation using `decide`. The general theorem over $\mathbb{N}$ then follows directly by embedding the natural numbers $t, t' < 32$ into `Fin 32` and applying this finite lemma.
For all $t, t' \in \text{Fin } 32$, consecutive 5-bit necklace representatives in BRGC order are necklace-adjacent. automation
Because the domain `Fin 32` is finite and the predicates for rotation equivalence, first necklace rank, and necklace adjacency are all decidable, Lean's `decide` tactic checks every pair in `Fin 32` by finite exhaustive computation.
lemma brgc_necklace_order_consecutive_adjacent_five_fin : ∀ (t t' : Fin 32), brgc_necklace_first_rank 5 t.1 → brgc_necklace_first_rank 5 t'.1 → t.1 < t'.1 → (∀ s : Fin 32, t.1 < s.1 → s.1 < t'.1 → ¬ brgc_necklace_first_rank 5 s.1) → bitword_necklace_adjacent 5 (brgc_word t.1) (brgc_word t'.1) := by decide
Fix ranks $t, t' \in \mathbb{N}$ and assume they are consecutive necklace first ranks.
We introduce the natural numbers $t$ and $t'$, along with the hypotheses that $t$ is a necklace first rank ($ht$), $t'$ is a necklace first rank ($ht'$), $t < t'$ ($hlt$), and no intermediate rank $s$ with $t < s < t'$ is a necklace first rank ($hbetween$).
intro t t' ht ht' hlt hbetweenBoth ranks $t$ and $t'$ are strictly less than 32.
By definition of `brgc_necklace_first_rank`, any necklace first rank for $n = 5$ satisfies $t < 2^5 = 32$. We extract these upper bounds $t < 32$ and $t' < 32$ from the first components of $ht$ and $ht'$.
have ht_lt : t < 32 := ht.1 have ht'_lt : t' < 32 := ht'.1
The Gray code words of $t$ and $t'$ are necklace-adjacent in $Q_5$.
We package $t$ and $t'$ as elements of `Fin 32` using the bounds $t < 32$ and $t' < 32$, and apply `brgc_necklace_order_consecutive_adjacent_five_fin`. The intermediate condition required by the lemma holds by specializing our hypothesis $hbetween$ to any $s \in \text{Fin } 32$ lying strictly between $t$ and $t'$.
uses
brgc_necklace_order_consecutive_adjacent_five_finexact brgc_necklace_order_consecutive_adjacent_five_fin ⟨t, ht_lt⟩ ⟨t', ht'_lt⟩ ht ht' hlt (fun s hs1 hs2 => hbetween s.1 hs1 hs2)
brgc_necklace_order_consecutive_adjacent_five_fin- For any two indices $t, t' \in \text{Fin } 32$, if both are necklace first ranks in the 5-bit BRGC order with $t < t'$ and there is no necklace first rank strictly between them, then their Gray code words are necklace-adjacent in $Q_5$.
- The finite lemma `brgc_necklace_order_consecutive_adjacent_five_fin` is verified purely by exhaustive computation via `decide`, relying on the decidability instances declared in lines 1–12.
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_consecutive_adjacent_five_dec_is_rot (n x y : ℕ) : Decidable (bitword_is_rotation n x y) := inferInstanceAs (Decidable (∃ r < n, (bitword_rotate n)^[r] x = y))instance brgc_necklace_order_consecutive_adjacent_five_dec_first_rank (n t : ℕ) : Decidable (brgc_necklace_first_rank n t) := inferInstanceAs (Decidable (t < 2 ^ n ∧ brgc_word t ≠ 0 ∧ brgc_word t ≠ 2 ^ n - 1 ∧ ∀ s < t, ¬ bitword_is_rotation n (brgc_word s) (brgc_word t)))instance brgc_necklace_order_consecutive_adjacent_five_dec_adj (n x y : ℕ) : Decidable (bitword_necklace_adjacent n x y) := inferInstanceAs (Decidable (∃ r < n, ∃ i < n, (bitword_rotate n)^[r] x ^^^ y = 2 ^ i))lemma brgc_necklace_order_consecutive_adjacent_five_fin : ∀ (t t' : Fin 32), brgc_necklace_first_rank 5 t.1 → brgc_necklace_first_rank 5 t'.1 → t.1 < t'.1 → (∀ s : Fin 32, t.1 < s.1 → s.1 < t'.1 → ¬ brgc_necklace_first_rank 5 s.1) → bitword_necklace_adjacent 5 (brgc_word t.1) (brgc_word t'.1) := by decidetheorem brgc_necklace_order_consecutive_adjacent_five : ∀ t t' : ℕ, brgc_necklace_first_rank 5 t → brgc_necklace_first_rank 5 t' → t < t' → (∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 5 s) → bitword_necklace_adjacent 5 (brgc_word t) (brgc_word t') := by intro t t' ht ht' hlt hbetween have ht_lt : t < 32 := ht.1 have ht'_lt : t' < 32 := ht'.1 exact brgc_necklace_order_consecutive_adjacent_five_fin ⟨t, ht_lt⟩ ⟨t', ht'_lt⟩ ht ht' hlt (fun s hs1 hs2 => hbetween s.1 hs1 hs2)