AFTD Auto-Formalizing Theoretical Domains

brgc_necklace_order_consecutive_aperiodic_adjacent_eight

theoremverified

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.

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

    lines 1–22

    uses decidable_of_iff

    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_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
      ⟩
    
  2. 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.

    lines 23–34

    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
    
  3. 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'$).

    lines 35–40

    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'
  4. 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$).

    lines 41–42

      have ht_lt : t < 256 := ht.1
      have ht'_lt : t' < 256 := ht'.1
  5. 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$.

    lines 43–45

    uses brgc_necklace_order_consecutive_aperiodic_adjacent_eight_fin

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

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