AFTD Auto-Formalizing Theoretical Domains

brgc_necklace_order_consecutive_aperiodic_adjacent_six

theoremverified

The case n = 6 (composite, with periodic necklaces that break the adjacency) of the aperiodic adjacency conjecture: consecutive aperiodic necklaces of D_6 are adjacent in Q_6.

Statement

theorem brgc_necklace_order_consecutive_aperiodic_adjacent_six :
    ∀ t t' : ℕ, brgc_necklace_first_rank 6 t → brgc_necklace_first_rank 6 t' → t < t' →
      (∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 6 s) →
      bitword_is_aperiodic 6 (brgc_word t) → bitword_is_aperiodic 6 (brgc_word t') →
      bitword_necklace_adjacent 6 (brgc_word t) (brgc_word t')
Source
case n = 6 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 verifies that consecutive aperiodic necklaces under the Binary Reflected Gray Code order for n = 6 are adjacent in the hypercube Q_6. Because n = 6 is fixed, the universe of words has size 2^6 = 64, and every necklace representative rank is bounded by 64. After establishing that all defining relations and predicates are decidable, the finite case is proved by exhaustive computation (`decide`) over Fin 64. The general result for ℕ then follows immediately by embedding the bounded ranks into Fin 64.

  1. The predicates of bitword rotation, being a BRGC necklace first rank, bitword necklace adjacency, and bitword aperiodicity are all decidable.

    For bitword rotation, necklace first rank, and necklace adjacency, unfolding each definition reveals that all quantifiers are bounded over finite intervals (r < n, s < t, i < n) and involve decidable arithmetic operations; typeclass inference (`infer_instance`) automatically synthesizes their `Decidable` instances. For aperiodicity, the definition is converted via `decidable_of_iff` to use a bounded universal quantifier (∀ r < n), enabling automatic decidability synthesis as well.

    lines 1–22

    uses decidable_of_iff

    instance brgc_necklace_order_consecutive_aperiodic_adjacent_six_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_six_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_six_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_six_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
      ⟩
    
  2. Consecutive aperiodic necklace first ranks in the finite domain {0, ..., 63} correspond to adjacent necklaces in the 6-cube Q_6. automation

    Because the search space `Fin 64` is finite and all relevant predicates have been proven decidable, the universal quantification over all candidate rank pairs t, t' and intermediate ranks s can be verified by exhaustive computational evaluation. The `decide` tactic checks every combination.

    lines 23–30

    theorem brgc_necklace_order_consecutive_aperiodic_adjacent_six_fin :
        ∀ t t' : Fin 64,
          brgc_necklace_first_rank 6 t.1 → brgc_necklace_first_rank 6 t'.1 → t.1 < t'.1 →
          (∀ s : Fin 64, t.1 < s.1 → s.1 < t'.1 → ¬ brgc_necklace_first_rank 6 s.1) →
          bitword_is_aperiodic 6 (brgc_word t.1) → bitword_is_aperiodic 6 (brgc_word t'.1) →
          bitword_necklace_adjacent 6 (brgc_word t.1) (brgc_word t'.1) := by
      decide
    
  3. Any two necklace first ranks t < t' for n = 6 satisfy t < 64 and t' < 64.

    We introduce the hypotheses for natural numbers t and t': that both are necklace first ranks for n = 6, t < t', no rank strictly between them is a necklace first rank, and both words are aperiodic. By definition, any first rank in dimension 6 is bounded by 2^6 = 64, so we obtain the bounds t < 64 and t' < 64 directly from the first components of the respective first-rank hypotheses (`ht.1` and `ht'.1`).

    lines 31–38

    theorem brgc_necklace_order_consecutive_aperiodic_adjacent_six :
        ∀ t t' : ℕ, brgc_necklace_first_rank 6 t → brgc_necklace_first_rank 6 t' → t < t' →
          (∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 6 s) →
          bitword_is_aperiodic 6 (brgc_word t) → bitword_is_aperiodic 6 (brgc_word t') →
          bitword_necklace_adjacent 6 (brgc_word t) (brgc_word t') := by
      intro t t' ht ht' hlt hbetween hap hap'
      have ht_lt : t < 64 := ht.1
      have ht'_lt : t' < 64 := ht'.1
  4. The necklaces of `brgc_word t` and `brgc_word t'` are adjacent in Q_6.

    We instantiate the finite result `brgc_necklace_order_consecutive_aperiodic_adjacent_six_fin` with the bounded elements ⟨t, ht_lt⟩ and ⟨t', ht'_lt⟩ of `Fin 64`. The betweenness condition for elements in `Fin 64` is satisfied by restricting the assumption `hbetween` on ℕ to their underlying values, and the aperiodicity assumptions transfer directly.

    lines 39–41

    uses brgc_necklace_order_consecutive_aperiodic_adjacent_six_fin

      exact brgc_necklace_order_consecutive_aperiodic_adjacent_six_fin
        ⟨t, ht_lt⟩ ⟨t', ht'_lt⟩ ht ht' hlt
        (fun s hs1 hs2 => hbetween s.1 hs1 hs2) hap hap'
decidable_of_iff
If a proposition a is logically equivalent to b and a is decidable, then b is also decidable.
brgc_necklace_order_consecutive_aperiodic_adjacent_six_fin
For indices t, t' in Fin 64, if t < t' are consecutive necklace first ranks under the BRGC order for n = 6 and both corresponding bitwords are aperiodic, then their necklaces are adjacent in Q_6.

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

instance brgc_necklace_order_consecutive_aperiodic_adjacent_six_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_six_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_six_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_six_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_six_fin :    ∀ t t' : Fin 64,      brgc_necklace_first_rank 6 t.1 → brgc_necklace_first_rank 6 t'.1 → t.1 < t'.1 →      (∀ s : Fin 64, t.1 < s.1 → s.1 < t'.1 → ¬ brgc_necklace_first_rank 6 s.1) →      bitword_is_aperiodic 6 (brgc_word t.1) → bitword_is_aperiodic 6 (brgc_word t'.1) →      bitword_necklace_adjacent 6 (brgc_word t.1) (brgc_word t'.1) := by  decidetheorem brgc_necklace_order_consecutive_aperiodic_adjacent_six :    ∀ t t' : ℕ, brgc_necklace_first_rank 6 t → brgc_necklace_first_rank 6 t' → t < t' →      (∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 6 s) →      bitword_is_aperiodic 6 (brgc_word t) → bitword_is_aperiodic 6 (brgc_word t') →      bitword_necklace_adjacent 6 (brgc_word t) (brgc_word t') := by  intro t t' ht ht' hlt hbetween hap hap'  have ht_lt : t < 64 := ht.1  have ht'_lt : t' < 64 := ht'.1  exact brgc_necklace_order_consecutive_aperiodic_adjacent_six_fin    ⟨t, ht_lt⟩ ⟨t', ht'_lt⟩ ht ht' hlt    (fun s hs1 hs2 => hbetween s.1 hs1 hs2) hap hap'
See it in the graphDiscuss this resultChallenge it