AFTD Auto-Formalizing Theoretical Domains

brgc_necklace_first_rank_unique_of_rotation

theoremverified

Two first-occurrence Gray ranks representing the same nonconstant necklace are equal.

Statement

theorem brgc_necklace_first_rank_unique_of_rotation (n t u : ℕ) (hn : 2 ≤ n) (ht : brgc_necklace_first_rank n t) (hu : brgc_necklace_first_rank n u) (h : bitword_is_rotation n (brgc_word t) (brgc_word u)) : t = u
Source
First occurrences used in OP-392, arXiv:2610.24758, Section 3 and Conjecture 1.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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,…
  • brgc_word_lt_two_powAn n-bit rank encodes an n-bit word.
  • bitword_is_rotation_symm_of_nonconstantFor length at least two, cyclic-rotation equivalence is symmetric on a nonconstant n-bit word.
  • brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
  • 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.

The proof, explained

The proof proceeds by trichotomy on the ranks t and u. If t < u, the minimality of u as a first-occurrence rank immediately contradicts the assumption that brgc_word t rotates to brgc_word u. If u < t, nonconstancy of brgc_word t ensures that rotation equivalence is symmetric, meaning brgc_word u rotates to brgc_word t, contradicting the minimality of t; thus t = u is the only possibility.

  1. It suffices to consider three cases: t < u, t = u, and u < t.

    By trichotomy on the natural numbers (lt_trichotomy), either t < u, t = u, or u < t.

    line 2

    uses lt_trichotomy

      rcases lt_trichotomy t u with hlt | heq | hgt
  2. The case t < u is impossible.

    By definition, u being a first-occurrence Gray rank means no rank s < u can have brgc_word s rotate to brgc_word u. Taking s = t contradicts the hypothesis h that brgc_word t rotates to brgc_word u.

    lines 3–5

      · exfalso
        have := hu.2.2.2 t hlt
        exact this h
  3. The case t = u holds immediately.

    The goal t = u is given directly by the case hypothesis.

    line 6

      · exact heq
  4. In the case u < t, the word brgc_word t satisfies 0 < brgc_word t < 2^n - 1.

    Because t is a first-occurrence rank, brgc_word t ≠ 0, so 0 < brgc_word t by Nat.pos_of_ne_zero. Furthermore, t < 2^n implies brgc_word t < 2^n via brgc_word_lt_two_pow, which gives brgc_word t ≤ 2^n - 1 by Nat.le_pred_of_lt. Since brgc_word t ≠ 2^n - 1 from the definition of a first-occurrence rank, lt_of_le_of_ne establishes brgc_word t < 2^n - 1.

    lines 7–12

    uses Nat.pos_of_ne_zero, brgc_word_lt_two_pow, Nat.le_pred_of_lt, lt_of_le_of_ne

      · exfalso
        have hx0 : 0 < brgc_word t := Nat.pos_of_ne_zero ht.2.1
        have hx_lt : brgc_word t < 2 ^ n := brgc_word_lt_two_pow ht.1
        have hx1 : brgc_word t < 2 ^ n - 1 := by
          have : brgc_word t ≤ 2 ^ n - 1 := Nat.le_pred_of_lt hx_lt
          exact lt_of_le_of_ne this ht.2.2.1
  5. The case u < t is impossible, concluding the proof.

    Since n ≥ 2 and 0 < brgc_word t < 2^n - 1, bitword_is_rotation_symm_of_nonconstant guarantees that rotation is symmetric, so brgc_word u rotates to brgc_word t. However, because u < t, the minimality condition on t as a first-occurrence rank requires that no rank strictly less than t can rotate to brgc_word t, yielding a contradiction.

    lines 13–15

    uses bitword_is_rotation_symm_of_nonconstant

        have hsymm := bitword_is_rotation_symm_of_nonconstant n (brgc_word t) (brgc_word u) hn hx0 hx1 h
        have := ht.2.2.2 u hgt
        exact this hsymm
lt_trichotomy
In any linear order, any two elements a and b satisfy a < b, a = b, or b < a.
Nat.pos_of_ne_zero
A non-zero natural number is strictly positive.
brgc_word_lt_two_pow
If a rank t satisfies t < 2^n, then its Gray code word satisfies brgc_word t < 2^n.
Nat.le_pred_of_lt
If n < m for natural numbers, then n ≤ m - 1.
lt_of_le_of_ne
If a ≤ b and a ≠ b in a partial order, then a < b.
bitword_is_rotation_symm_of_nonconstant
For n ≥ 2, rotation equivalence of n-bit words is symmetric on non-constant words (words strictly between 0 and 2^n - 1).

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

theorem brgc_necklace_first_rank_unique_of_rotation (n t u : ℕ) (hn : 2 ≤ n) (ht : brgc_necklace_first_rank n t) (hu : brgc_necklace_first_rank n u) (h : bitword_is_rotation n (brgc_word t) (brgc_word u)) : t = u := by  rcases lt_trichotomy t u with hlt | heq | hgt  · exfalso    have := hu.2.2.2 t hlt    exact this h  · exact heq  · exfalso    have hx0 : 0 < brgc_word t := Nat.pos_of_ne_zero ht.2.1    have hx_lt : brgc_word t < 2 ^ n := brgc_word_lt_two_pow ht.1    have hx1 : brgc_word t < 2 ^ n - 1 := by      have : brgc_word t ≤ 2 ^ n - 1 := Nat.le_pred_of_lt hx_lt      exact lt_of_le_of_ne this ht.2.2.1    have hsymm := bitword_is_rotation_symm_of_nonconstant n (brgc_word t) (brgc_word u) hn hx0 hx1 h    have := ht.2.2.2 u hgt    exact this hsymm
See it in the graphDiscuss this resultChallenge it