brgc_necklace_first_rank_exists_of_nonconstant
Every nonconstant binary word of length at least two has a first-occurrence Gray rank in its rotation class.
Statement
theorem brgc_necklace_first_rank_exists_of_nonconstant (n x : ℕ) (hn : 2 ≤ n) (hx0 : 0 < x) (hx1 : x < 2 ^ n - 1) : ∃ t, brgc_necklace_first_rank n t ∧ bitword_is_rotation n x (brgc_word t)- 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 12
- 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_inverseThe inverse prefix-parity transform on n-bit binary words, computed as the exclusive-or of all right shifts by less than n.
- brgc_word_inverseEncoding the n-bit inverse prefix-parity transform recovers the word.
- brgc_inverse_lt_two_powThe inverse prefix-parity transform of an n-bit word has an n-bit rank.
- bitword_is_rotation_symm_of_nonconstantFor length at least two, cyclic-rotation equivalence is symmetric on a nonconstant n-bit word.
- bitword_is_rotation_trans_of_nonconstantFor length at least two, cyclic-rotation equivalence is transitive when the initial word is a nonconstant n-bit word.
- bitword_is_aperiodic_of_primeFor prime n, every n-bit word other than 0^n and 1^n is aperiodic.
- brgc_necklace_order_consecutive_aperiodic_adjacent_nineThe case n = 9 (composite, with periodic necklaces that break the adjacency) of the aperiodic adjacency conjecture: consecutive aperiodic…
- 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.
- brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
- brgc_word_lt_two_powAn n-bit rank encodes an n-bit word.
- 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
To find a first-occurrence Gray rank in the rotation class (necklace) of a nonconstant binary word $x$, we consider the set of ranks $s$ whose Gray code word is nonconstant and in the rotation class of $x$. This set is nonempty because the Gray inverse of $x$ is a valid rank. By well-ordering, there is a minimal such rank $t$. If any strictly smaller rank $s < t$ had a Gray word that rotates to that of $t$, its Gray word could not be all-zero or all-ones (since these are fixed points under rotation), and hence it would also be nonconstant and in the rotation class of $x$, contradicting the minimality of $t$.
For $n \ge 1$, powers of two are strictly positive and $2^n = 2 \cdot 2^{n-1}$.
We establish $2^n > 0$ using `Nat.two_pow_pos`. Since $n \ge 1$, we rewrite $n$ as $(n - 1) + 1$, allowing $2^n$ to be factored as $2^{n-1} \cdot 2 = 2 \cdot 2^{n-1}$ via `pow_succ` and ring arithmetic. We also note that $2^{n-1} > 0$.
uses
Nat.two_pow_pos,pow_succtheorem brgc_necklace_first_rank_exists_of_nonconstant_rotate_all_ones (n : ℕ) (hn : 1 ≤ n) : bitword_rotate n (2 ^ n - 1) = 2 ^ n - 1 := by have h2n : 0 < 2 ^ n := Nat.two_pow_pos n have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by calc 2 ^ n = 2 ^ (n - 1 + 1) := by rw [show n - 1 + 1 = n by omega] _ = 2 ^ (n - 1) * 2 := pow_succ _ _ _ = 2 * 2 ^ (n - 1) := by ring have hpos : 0 < 2 ^ (n - 1) := Nat.two_pow_pos _
The all-ones binary word $2^n - 1$ is invariant under bitwise rotation: $\text{bitword\_rotate}(n, 2^n - 1) = 2^n - 1$.
Unfolding `bitword_rotate`, the rotation of $2^n - 1$ is $(2(2^n - 1)) \bmod 2^n + (2^n - 1) / 2^{n-1}$. We rewrite $2(2^n - 1)$ as $2^n + (2^n - 2)$; modulo $2^n$, the term $2^n$ cancels by `Nat.add_mod_left`, leaving $2^n - 2$ because $2^n - 2 < 2^n$ (`Nat.mod_eq_of_lt`). The division $(2^n - 1) / 2^{n-1}$ evaluates to $1$ by `Nat.div_eq_of_lt_le` because $1 \cdot 2^{n-1} \le 2^n - 1 < 2 \cdot 2^{n-1}$. Summing $(2^n - 2) + 1$ yields $2^n - 1$.
uses
Nat.add_mod_left,Nat.mod_eq_of_lt,Nat.div_eq_of_lt_leunfold bitword_rotate have h2 : 2 * (2 ^ n - 1) = 2 ^ n + (2 ^ n - 2) := by omega have hmod : 2 * (2 ^ n - 1) % 2 ^ n = 2 ^ n - 2 := by rw [h2, Nat.add_mod_left] exact Nat.mod_eq_of_lt (by omega) have hdiv : (2 ^ n - 1) / 2 ^ (n - 1) = 1 := by rw [Nat.div_eq_of_lt_le] · omega · omega rw [hmod, hdiv] omega
There exists a Gray code rank $s$ whose Gray word is nonconstant and belongs to the rotation class of $x$.
We define the predicate $p(s)$ stating that $\text{brgc\_word}(s) \ne 0$, $\text{brgc\_word}(s) \ne 2^n - 1$, and $\text{brgc\_word}(s)$ is a rotation of $x$. Choosing $s = \text{brgc\_inverse}(n, x)$, the lemma `brgc_word_inverse` yields $\text{brgc\_word}(s) = x$. The nonconstancy bounds $0 < x < 2^n - 1$ ensure $x \ne 0$ and $x \ne 2^n - 1$, and $x$ is trivially a rotation of itself in $0$ steps. Thus $\text{brgc\_inverse}(n, x)$ witnesses that the predicate $p$ is satisfiable.
uses
brgc_word_inversetheorem brgc_necklace_first_rank_exists_of_nonconstant (n x : ℕ) (hn : 2 ≤ n) (hx0 : 0 < x) (hx1 : x < 2 ^ n - 1) : ∃ t, brgc_necklace_first_rank n t ∧ bitword_is_rotation n x (brgc_word t) := by classical let p : ℕ → Prop := fun s => brgc_word s ≠ 0 ∧ brgc_word s ≠ 2 ^ n - 1 ∧ bitword_is_rotation n x (brgc_word s) have hxlt : x < 2 ^ n := by omega have hpinv : p (brgc_inverse n x) := by refine ⟨?_, ?_, ?_⟩ · rw [brgc_word_inverse hxlt]; omega · rw [brgc_word_inverse hxlt]; omega · refine ⟨0, by omega, ?_⟩ rw [brgc_word_inverse hxlt] simp have hex : ∃ s, p s := ⟨_, hpinv⟩
Let $t$ be the least rank satisfying $p$; then $p(t)$ holds and $t < 2^n$.
Using `Nat.find`, we set $t$ to be the least rank satisfying $p$, so $p(t)$ holds by `Nat.find_spec`. By `Nat.find_min'`, $t \le \text{brgc\_inverse}(n, x)$, and since $\text{brgc\_inverse}(n, x) < 2^n$ by `brgc_inverse_lt_two_pow`, we obtain $t < 2^n$.
uses
Nat.find_spec,Nat.find_min',brgc_inverse_lt_two_powlet t := Nat.find hex have ht : p t := Nat.find_spec hex have htle : t ≤ brgc_inverse n x := Nat.find_min' hex hpinv have ht_lt : t < 2 ^ n := by have h2 := brgc_inverse_lt_two_pow hxlt omega
To prove $t$ is a first Gray rank for the necklace, it suffices to derive a contradiction from assuming some $s < t$ rotates to $\text{brgc\_word}(t)$.
We supply $t$ as the witness. The conditions $t < 2^n$, $\text{brgc\_word}(t) \ne 0$, $\text{brgc\_word}(t) \ne 2^n - 1$, and rotation equivalence to $x$ all follow from $p(t)$. It remains to show that no earlier rank $s < t$ has its Gray word rotate to $\text{brgc\_word}(t)$. Assuming for contradiction that some $s < t$ rotates to $\text{brgc\_word}(t)$, we note $s < t < 2^n$, which ensures $\text{brgc\_word}(s) < 2^n$ by `brgc_word_lt_two_pow`.
uses
brgc_word_lt_two_powrefine ⟨t, ?_, ht.2.2⟩ refine ⟨ht_lt, ht.1, ht.2.1, ?_⟩ intro s hslt hrot have hst : s < 2 ^ n := by omega have hsWlt : brgc_word s < 2 ^ n := brgc_word_lt_two_pow hst
The case $\text{brgc\_word}(s) = 0$ is impossible.
If $\text{brgc\_word}(s) = 0$, then rotating it $r$ times gives $\text{brgc\_word}(t)$. However, $0$ is a fixed point of `bitword_rotate`, so by `Function.iterate_fixed` rotating $0$ any number of times results in $0$. This would mean $\text{brgc\_word}(t) = 0$, contradicting the established condition $\text{brgc\_word}(t) \ne 0$.
uses
Function.iterate_fixedby_cases hs0 : brgc_word s = 0 · obtain ⟨r, hr, hrr⟩ := hrot have h0 : (bitword_rotate n)^[r] 0 = 0 := Function.iterate_fixed (by simp [bitword_rotate]) r rw [hs0, h0] at hrr exact ht.1 hrr.symm
The case $\text{brgc\_word}(s) = 2^n - 1$ is impossible.
If $\text{brgc\_word}(s) = 2^n - 1$, rotating it $r$ times gives $\text{brgc\_word}(t)$. By `brgc_necklace_first_rank_exists_of_nonconstant_rotate_all_ones`, $2^n - 1$ is a fixed point of rotation. By `Function.iterate_fixed`, $r$ rotations leave $2^n - 1$ unchanged, implying $\text{brgc\_word}(t) = 2^n - 1$, which contradicts $\text{brgc\_word}(t) \ne 2^n - 1$.
uses
brgc_necklace_first_rank_exists_of_nonconstant_rotate_all_ones,Function.iterate_fixed· by_cases hs1 : brgc_word s = 2 ^ n - 1 · obtain ⟨r, hr, hrr⟩ := hrot have hfix : bitword_rotate n (2 ^ n - 1) = 2 ^ n - 1 := brgc_necklace_first_rank_exists_of_nonconstant_rotate_all_ones n (by omega) have h0 : (bitword_rotate n)^[r] (2 ^ n - 1) = 2 ^ n - 1 := Function.iterate_fixed hfix r rw [hs1, h0] at hrr exact ht.2.1 hrr.symm
When $\text{brgc\_word}(s)$ is nonconstant, it satisfies $p(s)$, contradicting the minimality of $t$.
Since $\text{brgc\_word}(s)$ is neither $0$ nor $2^n - 1$, it is strictly positive (`Nat.pos_of_ne_zero`) and strictly less than $2^n - 1$. By symmetry (`bitword_is_rotation_symm_of_nonconstant`), $\text{brgc\_word}(t)$ rotates to $\text{brgc\_word}(s)$. Since $x$ rotates to $\text{brgc\_word}(t)$, transitivity (`bitword_is_rotation_trans_of_nonconstant`) implies $x$ rotates to $\text{brgc\_word}(s)$. Thus $s$ satisfies $p(s)$, but this contradicts the minimality of $t$ (`Nat.find_min`) since $s < t$.
uses
Nat.pos_of_ne_zero,bitword_is_rotation_symm_of_nonconstant,bitword_is_rotation_trans_of_nonconstant,Nat.find_min· have hWs0 : 0 < brgc_word s := Nat.pos_of_ne_zero hs0 have hWs1 : brgc_word s < 2 ^ n - 1 := by omega have hsym : bitword_is_rotation n (brgc_word t) (brgc_word s) := bitword_is_rotation_symm_of_nonconstant n (brgc_word s) (brgc_word t) hn hWs0 hWs1 hrot have hxs : bitword_is_rotation n x (brgc_word s) := bitword_is_rotation_trans_of_nonconstant n x (brgc_word t) (brgc_word s) hn hx0 hx1 ht.2.2 hsym exact Nat.find_min hex hslt ⟨hs0, hs1, hxs⟩
Nat.two_pow_pos- Powers of two are strictly positive for every natural exponent.
pow_succ- For any power $a^{n+1}$, it equals $a^n \cdot a$.
Nat.add_mod_left- Adding a multiple of $x$ does not change the remainder modulo $x$: $(x + z) \bmod x = z \bmod x$.
Nat.mod_eq_of_lt- If $a < b$, then $a \bmod b = a$.
Nat.div_eq_of_lt_le- If $k \cdot n \le m < (k + 1) \cdot n$, then $m / n = k$.
brgc_word_inverse- The binary reflected Gray code function is left-inverse to `brgc_inverse`: $\text{brgc\_word}(\text{brgc\_inverse}(n, x)) = x$ for $x < 2^n$.
Nat.find_spec- The minimal index selected by `Nat.find` satisfies the predicate.
Nat.find_min'- If $m$ satisfies the predicate, then `Nat.find` is at most $m$.
brgc_inverse_lt_two_pow- For an $n$-bit word $x < 2^n$, its Gray code inverse index is strictly less than $2^n$.
brgc_word_lt_two_pow- If rank $t < 2^n$, then its Gray code word is strictly less than $2^n$.
Function.iterate_fixed- If $x$ is a fixed point of $f$ ($f(x) = x$), then iterating $f$ any number of times preserves $x$: $f^n(x) = x$.
brgc_necklace_first_rank_exists_of_nonconstant_rotate_all_ones- Rotating the all-ones word of length $n$ by one position leaves it unchanged: $\text{bitword\_rotate}(n, 2^n - 1) = 2^n - 1$.
Nat.pos_of_ne_zero- A non-zero natural number is strictly positive.
bitword_is_rotation_symm_of_nonconstant- Rotation equivalence is symmetric on nonconstant words ($0 < x < 2^n - 1$).
bitword_is_rotation_trans_of_nonconstant- Rotation equivalence is transitive when starting from a nonconstant word $x$ ($0 < x < 2^n - 1$).
Nat.find_min- Any natural number strictly smaller than `Nat.find` fails the predicate.
- The helper lemma `brgc_necklace_first_rank_exists_of_nonconstant_rotate_all_ones` proves that the all-ones word is a fixed point under single-step bitwise cyclic rotation; this is then extended to an arbitrary number of rotations $r$ via `Function.iterate_fixed`.
- The `classical` tactic is invoked to make the predicate $p$ decidable so that `Nat.find` can be applied without requiring an explicit constructive `DecidablePred` instance.
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_exists_of_nonconstant_rotate_all_ones (n : ℕ) (hn : 1 ≤ n) : bitword_rotate n (2 ^ n - 1) = 2 ^ n - 1 := by have h2n : 0 < 2 ^ n := Nat.two_pow_pos n have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by calc 2 ^ n = 2 ^ (n - 1 + 1) := by rw [show n - 1 + 1 = n by omega] _ = 2 ^ (n - 1) * 2 := pow_succ _ _ _ = 2 * 2 ^ (n - 1) := by ring have hpos : 0 < 2 ^ (n - 1) := Nat.two_pow_pos _ unfold bitword_rotate have h2 : 2 * (2 ^ n - 1) = 2 ^ n + (2 ^ n - 2) := by omega have hmod : 2 * (2 ^ n - 1) % 2 ^ n = 2 ^ n - 2 := by rw [h2, Nat.add_mod_left] exact Nat.mod_eq_of_lt (by omega) have hdiv : (2 ^ n - 1) / 2 ^ (n - 1) = 1 := by rw [Nat.div_eq_of_lt_le] · omega · omega rw [hmod, hdiv] omegatheorem brgc_necklace_first_rank_exists_of_nonconstant (n x : ℕ) (hn : 2 ≤ n) (hx0 : 0 < x) (hx1 : x < 2 ^ n - 1) : ∃ t, brgc_necklace_first_rank n t ∧ bitword_is_rotation n x (brgc_word t) := by classical let p : ℕ → Prop := fun s => brgc_word s ≠ 0 ∧ brgc_word s ≠ 2 ^ n - 1 ∧ bitword_is_rotation n x (brgc_word s) have hxlt : x < 2 ^ n := by omega have hpinv : p (brgc_inverse n x) := by refine ⟨?_, ?_, ?_⟩ · rw [brgc_word_inverse hxlt]; omega · rw [brgc_word_inverse hxlt]; omega · refine ⟨0, by omega, ?_⟩ rw [brgc_word_inverse hxlt] simp have hex : ∃ s, p s := ⟨_, hpinv⟩ let t := Nat.find hex have ht : p t := Nat.find_spec hex have htle : t ≤ brgc_inverse n x := Nat.find_min' hex hpinv have ht_lt : t < 2 ^ n := by have h2 := brgc_inverse_lt_two_pow hxlt omega refine ⟨t, ?_, ht.2.2⟩ refine ⟨ht_lt, ht.1, ht.2.1, ?_⟩ intro s hslt hrot have hst : s < 2 ^ n := by omega have hsWlt : brgc_word s < 2 ^ n := brgc_word_lt_two_pow hst by_cases hs0 : brgc_word s = 0 · obtain ⟨r, hr, hrr⟩ := hrot have h0 : (bitword_rotate n)^[r] 0 = 0 := Function.iterate_fixed (by simp [bitword_rotate]) r rw [hs0, h0] at hrr exact ht.1 hrr.symm · by_cases hs1 : brgc_word s = 2 ^ n - 1 · obtain ⟨r, hr, hrr⟩ := hrot have hfix : bitword_rotate n (2 ^ n - 1) = 2 ^ n - 1 := brgc_necklace_first_rank_exists_of_nonconstant_rotate_all_ones n (by omega) have h0 : (bitword_rotate n)^[r] (2 ^ n - 1) = 2 ^ n - 1 := Function.iterate_fixed hfix r rw [hs1, h0] at hrr exact ht.2.1 hrr.symm · have hWs0 : 0 < brgc_word s := Nat.pos_of_ne_zero hs0 have hWs1 : brgc_word s < 2 ^ n - 1 := by omega have hsym : bitword_is_rotation n (brgc_word t) (brgc_word s) := bitword_is_rotation_symm_of_nonconstant n (brgc_word s) (brgc_word t) hn hWs0 hWs1 hrot have hxs : bitword_is_rotation n x (brgc_word s) := bitword_is_rotation_trans_of_nonconstant n x (brgc_word t) (brgc_word s) hn hx0 hx1 ht.2.2 hsym exact Nat.find_min hex hslt ⟨hs0, hs1, hxs⟩