brgc_necklace_first_rank_min_rotations
Every rotation of a first-occurrence representative has inverse Gray rank at least its first-occurrence rank.
Statement
theorem brgc_necklace_first_rank_min_rotations {n t : ℕ} (hn : 2 ≤ n)
(ht : brgc_necklace_first_rank n t) :
∀ r < n, t ≤ brgc_inverse n ((bitword_rotate n)^[r] (brgc_word t))- Source
- Prefix-parity inverse and supporting arithmetic for OP-392, arXiv:2610.24758, Section 3 and Conjecture 1.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- bitword_is_aperiodic_of_primeFor prime n, every n-bit word other than 0^n and 1^n is aperiodic.
- 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.
- bitword_rotate_iterate_selfLeft rotation n times fixes every nonconstant n-bit word when n is at least two.
- brgc_inverseThe inverse prefix-parity transform on n-bit binary words, computed as the exclusive-or of all right shifts by less than n.
- brgc_inverse_wordThe n-bit inverse prefix-parity transform recovers an n-bit Gray rank from its encoded word.
- 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_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
- brgc_word_inverseEncoding the n-bit inverse prefix-parity transform recovers the word.
- 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.
- Used by 1
- brgc_necklace_first_rank_rotation_maxRotating a first-occurrence representative right once gives a representative of maximum inverse Gray rank in its rotation class; the…
The proof, explained
The theorem asserts that if $t$ is the first rank where its Gray code necklace occurs, any cyclic rotation of its Gray code word decodes to an inverse Gray rank at least $t$. The case of zero rotation holds trivially because decoding the encoding of $t$ recovers $t$. For a positive rotation by $r < n$ bits, if the decoded rank $s$ were strictly smaller than $t$, rotating $s$ by the remaining $n - r$ bits would recover the original word, demonstrating that $s < t$ belongs to the same necklace and contradicting the minimality of $t$.
The Gray code word of rank $t$ is strictly between $0$ and $2^n - 1$, and rotating it $n$ times yields itself.
From the hypothesis that $t$ is a first-occurrence rank, $t < 2^n$, which implies $t / 2 \le t < 2^n$ by `Nat.div_le_self` and `lt_of_le_of_lt`. Thus the Gray code word $w = t \oplus (t / 2)$ satisfies $w < 2^n$ by `Nat.xor_lt_two_pow`. Since $w \ne 0$ (by hypothesis), it is positive by `Nat.pos_of_ne_zero`. Since $w < 2^n$ and $w \ne 2^n - 1$ (by hypothesis), linear arithmetic gives $w < 2^n - 1$. Applying `bitword_rotate_iterate_self` shows that rotating $w$ by $n$ positions returns $w$.
uses
Nat.xor_lt_two_pow,lt_of_le_of_lt,Nat.div_le_self,Nat.pos_of_ne_zero,bitword_rotate_iterate_selfhave hx : brgc_word t < 2 ^ n := Nat.xor_lt_two_pow ht.1 (lt_of_le_of_lt (Nat.div_le_self _ _) ht.1) have hx0 : 0 < brgc_word t := Nat.pos_of_ne_zero ht.2.1 have hx1 : brgc_word t < 2 ^ n - 1 := by have := ht.2.2.1; omega have hperiod := bitword_rotate_iterate_self n (brgc_word t) hn hx0 hx1
For $r = 0$, the inequality $t \le \text{brgc\_inverse } n ((\text{bitword\_rotate } n)^r w)$ holds trivially.
Fix a rotation count $r < n$. In the case $r = 0$, applying zero rotations is the identity by `Function.iterate_zero` and `id_eq`. Decoding the Gray code word of rank $t < 2^n$ gives $t$ by `brgc_inverse_word`. Hence the goal simplifies to $t \le t$, which holds by reflexivity (`le_refl`).
uses
Function.iterate_zero,id_eq,brgc_inverse_word,le_reflintro r hr by_cases hr0 : r = 0 · subst r simp only [Function.iterate_zero, id_eq, brgc_inverse_word ht.1, le_refl]
For $r \ne 0$, the rotated word $y = (\text{bitword\_rotate } n)^r w$ satisfies $y < 2^n$.
Applying `bitword_is_aperiodic_of_prime_iterate_eq_mod` to $w$ and $r$ gives that $y < 2^n - 1$. Linear arithmetic then implies $y < 2^n$.
uses
bitword_is_aperiodic_of_prime_iterate_eq_mod· let y := (bitword_rotate n)^[r] (brgc_word t) have hylt : y < 2 ^ n := by have hh := bitword_is_aperiodic_of_prime_iterate_eq_mod n hn (brgc_word t) hx0 hx1 r dsimp [y] omega
Assuming $t > \text{brgc\_inverse } n \, y$ contradicts the minimality of $t$ if $\text{brgc\_word } (\text{brgc\_inverse } n \, y)$ is a rotation of $w$.
Assume for contradiction that $t \not\le \text{brgc\_inverse } n \, y$. By `Nat.lt_of_not_ge`, this means $s := \text{brgc\_inverse } n \, y < t$. By definition of $t$ being the first-occurrence rank of its necklace, no rank $s < t$ can have its Gray code word be a cyclic rotation of $w$. Thus, establishing that $\text{brgc\_word } s$ is a rotation of $w$ will yield a contradiction.
uses
Nat.lt_of_not_geby_contra hnot have hs : brgc_inverse n y < t := Nat.lt_of_not_ge hnot apply ht.2.2.2 (brgc_inverse n y) hs
The word $\text{brgc\_word } s$ rotates to $w$ in $n - r$ steps, deriving False.
Because $0 < r < n$, the remaining shift count satisfies $n - r < n$. Since $y < 2^n$, the decoded and re-encoded word $\text{brgc\_word } s = \text{brgc\_word } (\text{brgc\_inverse } n \, y)$ equals $y$ by `brgc_word_inverse`. Rotating $y$ by $n - r$ steps corresponds to rotating $w$ by $r$ steps and then by $n - r$ steps; by `Function.iterate_add_apply`, this is rotating $w$ by $(n - r) + r = n$ steps. Since an $n$-step rotation returns $w$, this shows $\text{brgc\_word } s$ rotates to $w$, contradicting the minimality assumption and completing the proof.
uses
brgc_word_inverse,Function.iterate_add_applyrefine ⟨n - r, by omega, ?_⟩ rw [brgc_word_inverse hylt] change (bitword_rotate n)^[n - r] ((bitword_rotate n)^[r] (brgc_word t)) = _ rw [← Function.iterate_add_apply, show n - r + r = n by omega, hperiod]
Nat.xor_lt_two_pow- the bitwise XOR of two numbers strictly less than $2^n$ is strictly less than $2^n$
lt_of_le_of_lt- if $a \le b$ and $b < c$, then $a < c$
Nat.div_le_self- for any natural numbers $n$ and $k$, $n / k \le n$
Nat.pos_of_ne_zero- a nonzero natural number is strictly positive
bitword_rotate_iterate_self- rotating an $n$-bit word strictly between $0$ and $2^n - 1$ by $n$ positions returns the word itself
Function.iterate_zero- iterating a function zero times is the identity function
id_eq- the identity function evaluated at $a$ returns $a$
brgc_inverse_word- for $t < 2^n$, decoding the binary reflected Gray code of rank $t$ yields $t$
le_refl- the ordering relation $\le$ is reflexive
bitword_is_aperiodic_of_prime_iterate_eq_mod- for $2 \le n$ and $0 < x < 2^n - 1$, the $m$-th cyclic rotation of $x$ equals $(2^m x) \bmod (2^n - 1)$, which lies strictly between $0$ and $2^n - 1$
Nat.lt_of_not_ge- if a natural number is not greater than or equal to another, it is strictly less
brgc_word_inverse- for $x < 2^n$, encoding the inverse Gray code of $x$ yields $x$
Function.iterate_add_apply- applying a function iterated $m + n$ times is equal to applying it $m$ times to the result of applying it $n$ times
- The case $r = 0$ is handled separately because the rotation witness for the contradiction in the definition of `bitword_is_rotation` requires a shift count strictly less than $n$; for $r > 0$, the remaining shift $n - r$ satisfies $n - r < n$, whereas for $r = 0$, $n - r = n$ would not.
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_min_rotations {n t : ℕ} (hn : 2 ≤ n) (ht : brgc_necklace_first_rank n t) : ∀ r < n, t ≤ brgc_inverse n ((bitword_rotate n)^[r] (brgc_word t)) := by have hx : brgc_word t < 2 ^ n := Nat.xor_lt_two_pow ht.1 (lt_of_le_of_lt (Nat.div_le_self _ _) ht.1) have hx0 : 0 < brgc_word t := Nat.pos_of_ne_zero ht.2.1 have hx1 : brgc_word t < 2 ^ n - 1 := by have := ht.2.2.1; omega have hperiod := bitword_rotate_iterate_self n (brgc_word t) hn hx0 hx1 intro r hr by_cases hr0 : r = 0 · subst r simp only [Function.iterate_zero, id_eq, brgc_inverse_word ht.1, le_refl] · let y := (bitword_rotate n)^[r] (brgc_word t) have hylt : y < 2 ^ n := by have hh := bitword_is_aperiodic_of_prime_iterate_eq_mod n hn (brgc_word t) hx0 hx1 r dsimp [y] omega by_contra hnot have hs : brgc_inverse n y < t := Nat.lt_of_not_ge hnot apply ht.2.2.2 (brgc_inverse n y) hs refine ⟨n - r, by omega, ?_⟩ rw [brgc_word_inverse hylt] change (bitword_rotate n)^[n - r] ((bitword_rotate n)^[r] (brgc_word t)) = _ rw [← Function.iterate_add_apply, show n - r + r = n by omega, hperiod]