brgc_necklace_order_consecutive_aperiodic_adjacent_nine
The case n = 9 (composite, with periodic necklaces that break the adjacency) of the aperiodic adjacency conjecture: consecutive aperiodic necklaces of D_9 are adjacent in Q_9.
Statement
theorem brgc_necklace_order_consecutive_aperiodic_adjacent_nine :
∀ t t' : ℕ, brgc_necklace_first_rank 9 t → brgc_necklace_first_rank 9 t' → t < t' →
(∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 9 s) →
bitword_is_aperiodic 9 (brgc_word t) → bitword_is_aperiodic 9 (brgc_word t') →
bitword_necklace_adjacent 9 (brgc_word t) (brgc_word t')- Source
- case n = 9 of brgc_necklace_order_consecutive_aperiodic_adjacent (exp 1939)
- Verified
- 29 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_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.
- 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.
- Used by 1
- brgc_necklace_first_rank_exists_of_nonconstantEvery nonconstant binary word of length at least two has a first-occurrence Gray rank in its rotation class.
The proof, explained
The theorem is proven by finite verification. First, an explicit list of 58 first-appearance ranks of necklaces of length 9 is defined, all strictly below 171. Since any rank between 171 and 511 is computationally verified to be a rotation of some rank in this list, no first rank can be 171 or greater. Thus any consecutive necklace first ranks t < t' must lie in the list with no other list elements between them, so hypercube adjacency follows from exhaustive computational check on the finite list.
Rotation is decidable
Unfolding the definition reveals a bounded existential quantifier over rotations r < n, which Lean decides automatically.
instance brgc_necklace_order_consecutive_aperiodic_adjacent_nine_dec_rot (n x y : ℕ) : Decidable (bitword_is_rotation n x y) := by unfold bitword_is_rotation infer_instance
First rank is decidable
Unfolding the definition leaves a conjunction of inequalities and bounded universal quantifiers, which Lean synthesizes instance for.
instance brgc_necklace_order_consecutive_aperiodic_adjacent_nine_dec_rank (n t : ℕ) : Decidable (brgc_necklace_first_rank n t) := by unfold brgc_necklace_first_rank infer_instance
Necklace adjacency is decidable
Unfolding the definition shows bounded existential quantifiers over rotation and bit index, which are decidable.
instance brgc_necklace_order_consecutive_aperiodic_adjacent_nine_dec_adj (n x y : ℕ) : Decidable (bitword_necklace_adjacent n x y) := by unfold bitword_necklace_adjacent infer_instance
All ranks in the list are strictly less than 171 automation
Verified by exhaustive computation over the explicit finite list of 58 ranks.
theorem brgc_necklace_order_consecutive_aperiodic_adjacent_nine_lt_171 : ∀ s ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks, s < 171 := by decide
Every necklace rank above 170 is a rotation of an earlier rank in the list automation
Decided by finite exhaustive search over all integers t from 171 to 511.
theorem brgc_necklace_order_consecutive_aperiodic_adjacent_nine_rot_bound : ∀ (t : Fin 512), 171 ≤ ↑t → brgc_word ↑t ≠ 2 ^ 9 - 1 → ∃ s ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks, bitword_is_rotation 9 (brgc_word s) (brgc_word ↑t) := by decide
A rank below 171 is a necklace first rank if and only if it belongs to the precomputed list automation
Decided by finite exhaustive search over all s < 171.
theorem brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks_iff : ∀ (s : Fin 171), brgc_necklace_first_rank 9 ↑s ↔ ↑s ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks := by decide
Adjacent pairs of aperiodic necklaces in the list are adjacent in the hypercube automation
Decided by finite exhaustive computation over all pairs of elements from the list of ranks.
theorem brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks_prop : ∀ t ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks, bitword_is_aperiodic 9 (brgc_word t) → ∀ t' ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks, t < t' → bitword_is_aperiodic 9 (brgc_word t') → (∀ s ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks, ¬ (t < s ∧ s < t')) → bitword_necklace_adjacent 9 (brgc_word t) (brgc_word t') := by decide
Main theorem holds
We show t and t' are in the list and apply the verified list property.
intro t t' ht ht' hlt hbetween hap hap' have ht'_lt : t' < 171 := by by_contra hnot have hge : 171 ≤ t' := by omega have ht'_512 : t' < 512 := ht'.1 have hne : brgc_word t' ≠ 2 ^ 9 - 1 := ht'.2.2.1 rcases brgc_necklace_order_consecutive_aperiodic_adjacent_nine_rot_bound ⟨t', ht'_512⟩ hge hne with ⟨s, hs_in, hs_rot⟩ have hs_lt_171 : s < 171 := brgc_necklace_order_consecutive_aperiodic_adjacent_nine_lt_171 s hs_in have hs_lt_t' : s < t' := by omega exact ht'.2.2.2 s hs_lt_t' hs_rot have ht_lt : t < 171 := by omega have ht_in : t ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks := (brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks_iff ⟨t, ht_lt⟩).mp ht have ht'_in : t' ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks := (brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks_iff ⟨t', ht'_lt⟩).mp ht' have hno_between : ∀ s ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks, ¬ (t < s ∧ s < t') := by intro s hs_in ⟨hts, hst'⟩ have hs_lt : s < 171 := by omega have hs_rank : brgc_necklace_first_rank 9 s := (brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks_iff ⟨s, hs_lt⟩).mpr hs_in exact hbetween s hts hst' hs_rank exact brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks_prop t ht_in hap t' ht'_in hlt hap' hno_between
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.
def brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks : List ℕ := [1, 2, 5, 6, 9, 10, 13, 14, 17, 18, 21, 22, 25, 26, 29, 30, 33, 34, 37, 38, 41, 42, 45, 46, 49, 50, 53, 54, 57, 58, 69, 70, 73, 74, 77, 78, 81, 82, 85, 86, 89, 90, 101, 102, 105, 106, 109, 110, 113, 146, 149, 150, 153, 154, 165, 166, 169, 170]instance brgc_necklace_order_consecutive_aperiodic_adjacent_nine_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_nine_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_nine_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_nine_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_nine_lt_171 : ∀ s ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks, s < 171 := by decidetheorem brgc_necklace_order_consecutive_aperiodic_adjacent_nine_rot_bound : ∀ (t : Fin 512), 171 ≤ ↑t → brgc_word ↑t ≠ 2 ^ 9 - 1 → ∃ s ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks, bitword_is_rotation 9 (brgc_word s) (brgc_word ↑t) := by decidetheorem brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks_iff : ∀ (s : Fin 171), brgc_necklace_first_rank 9 ↑s ↔ ↑s ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks := by decidetheorem brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks_prop : ∀ t ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks, bitword_is_aperiodic 9 (brgc_word t) → ∀ t' ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks, t < t' → bitword_is_aperiodic 9 (brgc_word t') → (∀ s ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks, ¬ (t < s ∧ s < t')) → bitword_necklace_adjacent 9 (brgc_word t) (brgc_word t') := by decidetheorem brgc_necklace_order_consecutive_aperiodic_adjacent_nine : ∀ t t' : ℕ, brgc_necklace_first_rank 9 t → brgc_necklace_first_rank 9 t' → t < t' → (∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 9 s) → bitword_is_aperiodic 9 (brgc_word t) → bitword_is_aperiodic 9 (brgc_word t') → bitword_necklace_adjacent 9 (brgc_word t) (brgc_word t') := by intro t t' ht ht' hlt hbetween hap hap' have ht'_lt : t' < 171 := by by_contra hnot have hge : 171 ≤ t' := by omega have ht'_512 : t' < 512 := ht'.1 have hne : brgc_word t' ≠ 2 ^ 9 - 1 := ht'.2.2.1 rcases brgc_necklace_order_consecutive_aperiodic_adjacent_nine_rot_bound ⟨t', ht'_512⟩ hge hne with ⟨s, hs_in, hs_rot⟩ have hs_lt_171 : s < 171 := brgc_necklace_order_consecutive_aperiodic_adjacent_nine_lt_171 s hs_in have hs_lt_t' : s < t' := by omega exact ht'.2.2.2 s hs_lt_t' hs_rot have ht_lt : t < 171 := by omega have ht_in : t ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks := (brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks_iff ⟨t, ht_lt⟩).mp ht have ht'_in : t' ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks := (brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks_iff ⟨t', ht'_lt⟩).mp ht' have hno_between : ∀ s ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks, ¬ (t < s ∧ s < t') := by intro s hs_in ⟨hts, hst'⟩ have hs_lt : s < 171 := by omega have hs_rank : brgc_necklace_first_rank 9 s := (brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks_iff ⟨s, hs_lt⟩).mpr hs_in exact hbetween s hts hst' hs_rank exact brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks_prop t ht_in hap t' ht'_in hlt hap' hno_between