brgc_necklace_first_rank_unique_of_rotation
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.
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.
uses
lt_trichotomyrcases lt_trichotomy t u with hlt | heq | hgt
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.
· exfalso have := hu.2.2.2 t hlt exact this h
The case t = u holds immediately.
The goal t = u is given directly by the case hypothesis.
· exact heqIn 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.
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
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.
uses
bitword_is_rotation_symm_of_nonconstanthave 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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