brgc_necklace_order_consecutive_aperiodic_adjacent_eight
The case n = 8 (composite, with periodic necklaces that break the adjacency) of the aperiodic adjacency conjecture: consecutive aperiodic necklaces of D_8 are adjacent in Q_8.
Statement
theorem brgc_necklace_order_consecutive_aperiodic_adjacent_eight :
∀ t t' : ℕ, brgc_necklace_first_rank 8 t → brgc_necklace_first_rank 8 t' → t < t' →
(∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 8 s) →
bitword_is_aperiodic 8 (brgc_word t) → bitword_is_aperiodic 8 (brgc_word t') →
bitword_necklace_adjacent 8 (brgc_word t) (brgc_word t')- Source
- case n = 8 of brgc_necklace_order_consecutive_aperiodic_adjacent (exp 1939)
- Verified
- 20 Oct 2026
- Axioms
Quot.soundpropext- Built on 6
- 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_aperiodicThe n-bit word x is aperiodic (primitive): no rotation by 0 < r < n fixes it, i.e. its necklace has n distinct rotations.
- 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 proves the $n = 8$ case of the aperiodic adjacency conjecture for binary reflected Gray code (BRGC) necklaces: consecutive aperiodic necklaces in the hypercube $Q_8$ have adjacent representatives. Because $n = 8$ is fixed, the ranks are bounded by $2^8 = 256$, reducing the claim to a finite combinatorial check over Fin 256. After establishing decidability for bitword rotation, first rank status, adjacency, and aperiodicity, the finite case is verified entirely by computational reflection (`decide`). Finally, the general theorem over ℕ follows directly because any necklace first rank for $n = 8$ is strictly less than 256, allowing the ranks to be cast into Fin 256.
The relations of bitword rotation, being a BRGC necklace first rank, necklace adjacency, and bitword aperiodicity are all decidable on ℕ.
To verify finite instances by computation via `decide`, Lean requires `Decidable` instances for all predicates in the theorem. For `bitword_is_rotation` and `bitword_necklace_adjacent`, the conditions consist of bounded existential quantifiers (shifts $r < n$ and bit positions $i < n$). For `brgc_necklace_first_rank`, the condition is a conjunction of bounds, inequalities, and a bounded universal quantifier over $s < t$. For `bitword_is_aperiodic`, the condition $\forall r, 0 < r \to r < n \to \dots$ is rephrased via `decidable_of_iff` to put the upper bound directly on the quantifier ($\forall r < n, 0 < r \to \dots$). In each case, typeclass synthesis constructs the decision procedure from bounded quantification on ℕ.
uses
decidable_of_iffinstance brgc_necklace_order_consecutive_aperiodic_adjacent_eight_dec_rot (n x y : ℕ) : Decidable (bitword_is_rotation n x y) := by unfold bitword_is_rotation infer_instance instance brgc_necklace_order_consecutive_aperiodic_adjacent_eight_dec_rank (n t : ℕ) : Decidable (brgc_necklace_first_rank n t) := by unfold brgc_necklace_first_rank infer_instance instance brgc_necklace_order_consecutive_aperiodic_adjacent_eight_dec_adj (n x y : ℕ) : Decidable (bitword_necklace_adjacent n x y) := by unfold bitword_necklace_adjacent infer_instance instance brgc_necklace_order_consecutive_aperiodic_adjacent_eight_dec_aperiodic (n x : ℕ) : Decidable (bitword_is_aperiodic n x) := decidable_of_iff (∀ r < n, 0 < r → (bitword_rotate n)^[r] x ≠ x) ⟨ fun h r hr0 hrn => h r hrn hr0, fun h r hrn hr0 => h r hr0 hrn ⟩
Consecutive aperiodic necklace first ranks in Fin 256 have adjacent Gray codewords in the 8-cube. automation
With decidability established for all predicates and the domain restricted to the finite type Fin 256, the entire proposition is decidable. The `decide` tactic checks all configurations exhaustively by computational reflection, verifying that whenever two elements of Fin 256 are consecutive aperiodic necklace first ranks, their Gray codewords differ by a rotation and a single bit flip.
theorem brgc_necklace_order_consecutive_aperiodic_adjacent_eight_fin : ∀ (t : Fin 256), brgc_necklace_first_rank 8 ↑t → bitword_is_aperiodic 8 (brgc_word ↑t) → ∀ (t' : Fin 256), ↑t < ↑t' → brgc_necklace_first_rank 8 ↑t' → bitword_is_aperiodic 8 (brgc_word ↑t') → (∀ (s : Fin 256), ↑t < ↑s → ↑s < ↑t' → ¬brgc_necklace_first_rank 8 ↑s) → bitword_necklace_adjacent 8 (brgc_word ↑t) (brgc_word ↑t') := by decide
Fix two natural numbers $t, t'$ and assume they are consecutive aperiodic necklace first ranks with $t < t'$.
We introduce the ranks $t, t' \in ℕ$, the assumptions that they are necklace first ranks ($ht, ht'$), that $t < t'$ ($hlt$), that no necklace first rank lies strictly between them ($hbetween$), and that their Gray codewords are aperiodic ($hap, hap'$).
theorem brgc_necklace_order_consecutive_aperiodic_adjacent_eight : ∀ t t' : ℕ, brgc_necklace_first_rank 8 t → brgc_necklace_first_rank 8 t' → t < t' → (∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 8 s) → bitword_is_aperiodic 8 (brgc_word t) → bitword_is_aperiodic 8 (brgc_word t') → bitword_necklace_adjacent 8 (brgc_word t) (brgc_word t') := by intro t t' ht ht' hlt hbetween hap hap'
Both ranks satisfy $t < 256$ and $t' < 256$.
By definition of `brgc_necklace_first_rank 8`, the first condition requires the rank to be strictly less than $2^8 = 256$. Taking the first component from $ht$ and $ht'$ yields $t < 256$ (named $ht\_lt$) and $t' < 256$ (named $ht'\_lt$).
have ht_lt : t < 256 := ht.1 have ht'_lt : t' < 256 := ht'.1
The Gray codewords `brgc_word t` and `brgc_word t'` are necklace-adjacent in the 8-cube, completing the proof.
Using the bounds $ht\_lt$ and $ht'\_lt$, we package $t$ and $t'$ as elements $\langle t, ht\_lt \rangle$ and $\langle t', ht'\_lt \rangle$ of Fin 256. We then apply the finite theorem `brgc_necklace_order_consecutive_aperiodic_adjacent_eight_fin` to these finite elements, converting the consecutiveness assumption $hbetween$ on ℕ to Fin 256 by projecting each $s \in \text{Fin}(256)$ to its underlying natural number $s.1$.
uses
brgc_necklace_order_consecutive_aperiodic_adjacent_eight_finexact brgc_necklace_order_consecutive_aperiodic_adjacent_eight_fin ⟨t, ht_lt⟩ ht hap ⟨t', ht'_lt⟩ hlt ht' hap' (fun s hs1 hs2 => hbetween s.1 hs1 hs2)
decidable_of_iff- If proposition $a$ is logically equivalent to $b$ and $a$ is decidable, then $b$ is decidable.
brgc_necklace_order_consecutive_aperiodic_adjacent_eight_fin- For dimension $n = 8$, any two consecutive aperiodic BRGC necklace first ranks represented in Fin 256 have adjacent Gray codewords in the 8-cube.
- The finite case `brgc_necklace_order_consecutive_aperiodic_adjacent_eight_fin` is verified entirely by computational reflection (`decide`), exhaustively testing all candidate pairs in Fin 256 inside the Lean kernel rather than producing a human-readable deduction for each case.
- The decidability instances in lines 1–22 are formal requirements for Lean's typeclass synthesis to enable `decide` on bounded quantifiers; mathematically, decidability of these finite relations is immediate. In particular, `bitword_is_aperiodic` reorders the quantification bounds using `decidable_of_iff` so that the outer quantifier is bounded by $n$, allowing Lean to automatically synthesize its decision procedure.
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_aperiodic_adjacent_eight_dec_rot (n x y : ℕ) : Decidable (bitword_is_rotation n x y) := by unfold bitword_is_rotation infer_instanceinstance brgc_necklace_order_consecutive_aperiodic_adjacent_eight_dec_rank (n t : ℕ) : Decidable (brgc_necklace_first_rank n t) := by unfold brgc_necklace_first_rank infer_instanceinstance brgc_necklace_order_consecutive_aperiodic_adjacent_eight_dec_adj (n x y : ℕ) : Decidable (bitword_necklace_adjacent n x y) := by unfold bitword_necklace_adjacent infer_instanceinstance brgc_necklace_order_consecutive_aperiodic_adjacent_eight_dec_aperiodic (n x : ℕ) : Decidable (bitword_is_aperiodic n x) := decidable_of_iff (∀ r < n, 0 < r → (bitword_rotate n)^[r] x ≠ x) ⟨ fun h r hr0 hrn => h r hrn hr0, fun h r hrn hr0 => h r hr0 hrn ⟩theorem brgc_necklace_order_consecutive_aperiodic_adjacent_eight_fin : ∀ (t : Fin 256), brgc_necklace_first_rank 8 ↑t → bitword_is_aperiodic 8 (brgc_word ↑t) → ∀ (t' : Fin 256), ↑t < ↑t' → brgc_necklace_first_rank 8 ↑t' → bitword_is_aperiodic 8 (brgc_word ↑t') → (∀ (s : Fin 256), ↑t < ↑s → ↑s < ↑t' → ¬brgc_necklace_first_rank 8 ↑s) → bitword_necklace_adjacent 8 (brgc_word ↑t) (brgc_word ↑t') := by decidetheorem brgc_necklace_order_consecutive_aperiodic_adjacent_eight : ∀ t t' : ℕ, brgc_necklace_first_rank 8 t → brgc_necklace_first_rank 8 t' → t < t' → (∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 8 s) → bitword_is_aperiodic 8 (brgc_word t) → bitword_is_aperiodic 8 (brgc_word t') → bitword_necklace_adjacent 8 (brgc_word t) (brgc_word t') := by intro t t' ht ht' hlt hbetween hap hap' have ht_lt : t < 256 := ht.1 have ht'_lt : t' < 256 := ht'.1 exact brgc_necklace_order_consecutive_aperiodic_adjacent_eight_fin ⟨t, ht_lt⟩ ht hap ⟨t', ht'_lt⟩ hlt ht' hap' (fun s hs1 hs2 => hbetween s.1 hs1 hs2)