AFTD Auto-Formalizing Theoretical Domains

brgc_necklace_order_consecutive_aperiodic_adjacent_nine

theoremverified

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

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.

  1. Rotation is decidable

    Unfolding the definition reveals a bounded existential quantifier over rotations r < n, which Lean decides automatically.

    lines 6–10

    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
    
  2. First rank is decidable

    Unfolding the definition leaves a conjunction of inequalities and bounded universal quantifiers, which Lean synthesizes instance for.

    lines 11–15

    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
    
  3. Necklace adjacency is decidable

    Unfolding the definition shows bounded existential quantifiers over rotation and bit index, which are decidable.

    lines 16–20

    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
    
  4. All ranks in the list are strictly less than 171 automation

    Verified by exhaustive computation over the explicit finite list of 58 ranks.

    lines 28–31

    theorem brgc_necklace_order_consecutive_aperiodic_adjacent_nine_lt_171 :
        ∀ s ∈ brgc_necklace_order_consecutive_aperiodic_adjacent_nine_ranks, s < 171 := by
      decide
    
  5. 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.

    lines 32–37

    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
    
  6. 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.

    lines 38–42

    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
    
  7. 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.

    lines 43–52

    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
    
  8. Main theorem holds

    We show t and t' are in the list and apply the verified list property.

    lines 58–79

      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

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
See it in the graphDiscuss this resultChallenge it