brgc_necklace_order_consecutive_adjacent_seven
The case n = 7 of the conjecture: consecutive necklaces of D_7 are adjacent in Q_7.
Statement
theorem brgc_necklace_order_consecutive_adjacent_seven :
∀ t t' : ℕ, brgc_necklace_first_rank 7 t →
brgc_necklace_first_rank 7 t' → t < t' →
(∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 7 s) →
bitword_necklace_adjacent 7 (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 = 7, 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 conjecture for $n = 7$ states that consecutive necklace representatives in the binary reflected Gray code order are adjacent in the hypercube up to rotation. Because the search space is bounded by $2^7 = 128$, the finite version is a decidable proposition checked by kernel evaluation. The main theorem then reduces the general statement for natural numbers to this finite lemma by extracting the bound $t, t' < 128$ from the definition of first rank.
The consecutive necklace adjacency condition holds for all ranks restricted to `Fin 128`. automation
Since `Fin 128` is a finite type and all predicates involved (being a first rank, rotation equivalence, and necklace adjacency) are decidable, the assertion is a finite combinatorial statement. Lean's kernel verifies it by exhaustive evaluation over all pairs in `Fin 128`.
decide +kernelIntroduce the ranks $t, t' \in \mathbb{N}$ along with the hypotheses that they are first ranks, that $t < t'$, and that no first rank occurs strictly between them.
Fix natural numbers $t$ and $t'$, assume $t$ and $t'$ are first ranks of necklaces (`ht` and `ht'`), assume $t < t'$ (`hlt`), and assume that no integer $s$ strictly between $t$ and $t'$ is a first rank (`hbetween`).
intro t t' ht ht' hlt hbetweenBoth $t$ and $t'$ are strictly less than 128.
By definition, being a first rank for $n = 7$ requires being strictly less than $2^7 = 128$. Extracting the first component of `ht` and `ht'` yields $t < 128$ and $t' < 128$.
have ht_lt : t < 128 := ht.1 have ht'_lt : t' < 128 := ht'.1
The Gray code words of $t$ and $t'$ are necklace-adjacent in $Q_7$.
Package $t$ and $t'$ as elements of `Fin 128` using the bounds $t < 128$ and $t' < 128$. The hypothesis that no rank between them is a first rank applies in particular to all elements of `Fin 128` between $t$ and $t'$. Applying the finite lemma `brgc_necklace_order_consecutive_adjacent_seven_fin` concludes the proof.
uses
brgc_necklace_order_consecutive_adjacent_seven_finexact brgc_necklace_order_consecutive_adjacent_seven_fin ⟨t, ht_lt⟩ ⟨t', ht'_lt⟩ ht ht' hlt (fun s hs1 hs2 => hbetween s.1 hs1 hs2)
brgc_necklace_order_consecutive_adjacent_seven_fin- For indices restricted to the finite type Fin 128, any two consecutive first ranks in the binary reflected Gray code represent adjacent necklaces in the 7-cube.
- The finite case (lemma `brgc_necklace_order_consecutive_adjacent_seven_fin`) is proved by kernel evaluation (`decide +kernel`), which exhaustively checks all pairs of ranks in Fin 128.
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_seven_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_seven_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_seven_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_seven_fin : ∀ (t t' : Fin 128), brgc_necklace_first_rank 7 t.1 → brgc_necklace_first_rank 7 t'.1 → t.1 < t'.1 → (∀ s : Fin 128, t.1 < s.1 → s.1 < t'.1 → ¬ brgc_necklace_first_rank 7 s.1) → bitword_necklace_adjacent 7 (brgc_word t.1) (brgc_word t'.1) := by decide +kerneltheorem brgc_necklace_order_consecutive_adjacent_seven : ∀ t t' : ℕ, brgc_necklace_first_rank 7 t → brgc_necklace_first_rank 7 t' → t < t' → (∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 7 s) → bitword_necklace_adjacent 7 (brgc_word t) (brgc_word t') := by intro t t' ht ht' hlt hbetween have ht_lt : t < 128 := ht.1 have ht'_lt : t' < 128 := ht'.1 exact brgc_necklace_order_consecutive_adjacent_seven_fin ⟨t, ht_lt⟩ ⟨t', ht'_lt⟩ ht ht' hlt (fun s hs1 hs2 => hbetween s.1 hs1 hs2)