AFTD Auto-Formalizing Theoretical Domains

brgc_necklace_order_consecutive_adjacent_five

theoremverifiedformalization

The case n = 5 of the conjecture: consecutive necklaces of D_5 are adjacent in Q_5.

Statement

theorem brgc_necklace_order_consecutive_adjacent_five :
    ∀ t t' : ℕ, brgc_necklace_first_rank 5 t →
      brgc_necklace_first_rank 5 t' → t < t' →
      (∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 5 s) →
      bitword_necklace_adjacent 5 (brgc_word t) (brgc_word t')
Formalizes
arXiv:2610.24758 (Optimal single-track Gray codes from Gray-ordered necklaces), Conjecture 1 (prime case of a conjecture from 2007), Sec. 1; the case n = 5, verified by computation in the paper
Verified
20 Oct 2026
Axioms
Quot.soundpropext
Built on 5
  • 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_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 establishes that consecutive necklace representatives in the 5-bit binary reflected Gray code (BRGC) order are adjacent in the hypercube $Q_5$ (up to cyclic rotation). Because any 5-bit necklace first rank is strictly less than $2^5 = 32$, the statement is first proved for the finite domain `Fin 32` by exhaustive computation using `decide`. The general theorem over $\mathbb{N}$ then follows directly by embedding the natural numbers $t, t' < 32$ into `Fin 32` and applying this finite lemma.

  1. For all $t, t' \in \text{Fin } 32$, consecutive 5-bit necklace representatives in BRGC order are necklace-adjacent. automation

    Because the domain `Fin 32` is finite and the predicates for rotation equivalence, first necklace rank, and necklace adjacency are all decidable, Lean's `decide` tactic checks every pair in `Fin 32` by finite exhaustive computation.

    lines 14–19

    lemma brgc_necklace_order_consecutive_adjacent_five_fin :
        ∀ (t t' : Fin 32), brgc_necklace_first_rank 5 t.1 →
          brgc_necklace_first_rank 5 t'.1 → t.1 < t'.1 →
          (∀ s : Fin 32, t.1 < s.1 → s.1 < t'.1 → ¬ brgc_necklace_first_rank 5 s.1) →
          bitword_necklace_adjacent 5 (brgc_word t.1) (brgc_word t'.1) := by
      decide
  2. Fix ranks $t, t' \in \mathbb{N}$ and assume they are consecutive necklace first ranks.

    We introduce the natural numbers $t$ and $t'$, along with the hypotheses that $t$ is a necklace first rank ($ht$), $t'$ is a necklace first rank ($ht'$), $t < t'$ ($hlt$), and no intermediate rank $s$ with $t < s < t'$ is a necklace first rank ($hbetween$).

    line 26

      intro t t' ht ht' hlt hbetween
  3. Both ranks $t$ and $t'$ are strictly less than 32.

    By definition of `brgc_necklace_first_rank`, any necklace first rank for $n = 5$ satisfies $t < 2^5 = 32$. We extract these upper bounds $t < 32$ and $t' < 32$ from the first components of $ht$ and $ht'$.

    lines 27–28

      have ht_lt : t < 32 := ht.1
      have ht'_lt : t' < 32 := ht'.1
  4. The Gray code words of $t$ and $t'$ are necklace-adjacent in $Q_5$.

    We package $t$ and $t'$ as elements of `Fin 32` using the bounds $t < 32$ and $t' < 32$, and apply `brgc_necklace_order_consecutive_adjacent_five_fin`. The intermediate condition required by the lemma holds by specializing our hypothesis $hbetween$ to any $s \in \text{Fin } 32$ lying strictly between $t$ and $t'$.

    lines 29–30

    uses brgc_necklace_order_consecutive_adjacent_five_fin

      exact brgc_necklace_order_consecutive_adjacent_five_fin ⟨t, ht_lt⟩ ⟨t', ht'_lt⟩ ht ht' hlt
        (fun s hs1 hs2 => hbetween s.1 hs1 hs2)
brgc_necklace_order_consecutive_adjacent_five_fin
For any two indices $t, t' \in \text{Fin } 32$, if both are necklace first ranks in the 5-bit BRGC order with $t < t'$ and there is no necklace first rank strictly between them, then their Gray code words are necklace-adjacent in $Q_5$.

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_adjacent_five_dec_is_rot (n x y : ℕ) :    Decidable (bitword_is_rotation n x y) :=  inferInstanceAs (Decidable (∃ r < n, (bitword_rotate n)^[r] x = y))instance brgc_necklace_order_consecutive_adjacent_five_dec_first_rank (n t : ℕ) :    Decidable (brgc_necklace_first_rank n t) :=  inferInstanceAs (Decidable (t < 2 ^ n ∧ brgc_word t ≠ 0 ∧ brgc_word t ≠ 2 ^ n - 1 ∧    ∀ s < t, ¬ bitword_is_rotation n (brgc_word s) (brgc_word t)))instance brgc_necklace_order_consecutive_adjacent_five_dec_adj (n x y : ℕ) :    Decidable (bitword_necklace_adjacent n x y) :=  inferInstanceAs (Decidable (∃ r < n, ∃ i < n, (bitword_rotate n)^[r] x ^^^ y = 2 ^ i))lemma brgc_necklace_order_consecutive_adjacent_five_fin :    ∀ (t t' : Fin 32), brgc_necklace_first_rank 5 t.1 →      brgc_necklace_first_rank 5 t'.1 → t.1 < t'.1 →      (∀ s : Fin 32, t.1 < s.1 → s.1 < t'.1 → ¬ brgc_necklace_first_rank 5 s.1) →      bitword_necklace_adjacent 5 (brgc_word t.1) (brgc_word t'.1) := by  decidetheorem brgc_necklace_order_consecutive_adjacent_five :    ∀ t t' : ℕ, brgc_necklace_first_rank 5 t →      brgc_necklace_first_rank 5 t' → t < t' →      (∀ s, t < s → s < t' → ¬ brgc_necklace_first_rank 5 s) →      bitword_necklace_adjacent 5 (brgc_word t) (brgc_word t') := by  intro t t' ht ht' hlt hbetween  have ht_lt : t < 32 := ht.1  have ht'_lt : t' < 32 := ht'.1  exact brgc_necklace_order_consecutive_adjacent_five_fin ⟨t, ht_lt⟩ ⟨t', ht'_lt⟩ ht ht' hlt    (fun s hs1 hs2 => hbetween s.1 hs1 hs2)
See it in the graphDiscuss this resultChallenge it