brgc_necklace_first_rank_word_odd
For length at least two, the first nonconstant representative in Gray order has final bit one.
Statement
theorem brgc_necklace_first_rank_word_odd {n t : ℕ} (hn : 2 ≤ n)
(ht : brgc_necklace_first_rank n t) : brgc_word t % 2 = 1- Source
- Supporting arithmetic and canonical-representative lemmas for OP-392, arXiv:2610.24758, Conjecture 1.
- Verified
- 25 Oct 2026
- Axioms
Quot.soundpropext- Built on 6
- 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.
- brgc_word_div_twoThe binary reflected Gray encoding commutes with division by two.
- 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.
- 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.
- Used by 1
- brgc_necklace_first_rank_mod_fourFor length at least two, each first-occurrence rank of a nonconstant necklace is congruent to one or two modulo four.
The proof, explained
The proof proceeds by contradiction: if the Gray code word brgc_word t were even, its least significant bit would be zero. By brgc_word_div_two, shifting this word right by one bit yields brgc_word (t / 2) for the strictly smaller index t / 2 < t. Rotating brgc_word (t / 2) left by one position reconstructs brgc_word t, which contradicts the minimality of t as the first rank representative of its rotation class.
t > 0
Suppose for contradiction that t ≤ 0, so t = 0. Then brgc_word t = brgc_word 0 = 0, which contradicts the hypothesis that t represents a nonconstant necklace (brgc_word t ≠ 0).
have htpos : 0 < t := by by_contra h have : t = 0 := by omega exact ht.2.1 (by simp [this, brgc_word])
brgc_word t < 2^n
Since t < 2^n by definition of necklace rank, brgc_word_lt_two_pow implies that brgc_word t < 2^n.
uses
brgc_word_lt_two_powhave hxlt := brgc_word_lt_two_pow ht.1brgc_word t % 2 = 0 under the assumption that the theorem fails
Assume for contradiction that brgc_word t % 2 ≠ 1. Because any natural number modulo 2 is either 0 or 1, linear integer arithmetic (omega) establishes that brgc_word t is even (brgc_word t % 2 = 0).
by_contra hodd have heven : brgc_word t % 2 = 0 := by omega
t / 2 < t
Since t > 0 and 2 > 1, integer division strictly decreases t by Nat.div_lt_self.
uses
Nat.div_lt_selfhave hsmall : t / 2 < t := Nat.div_lt_self htpos (by omega)
It suffices to show that 2 * (brgc_word t / 2) % 2^n + (brgc_word t / 2) / 2^(n - 1) = brgc_word t
By definition of the first rank representative, no strictly smaller index s < t can have a Gray code word that rotates to brgc_word t. Applying this minimality to s = t / 2 < t, it suffices to show that rotating brgc_word (t / 2) left by 1 bit produces brgc_word t, with the rotation count 1 < n valid since n ≥ 2. Using Function.iterate_one, expanding bitword_rotate, and rewriting with brgc_word_div_two, the goal reduces to verifying the 1-bit rotation formula applied to brgc_word t / 2.
uses
Function.iterate_one,brgc_word_div_twoapply ht.2.2.2 (t / 2) hsmall refine ⟨1, by omega, ?_⟩ simp only [Function.iterate_one] rw [bitword_rotate, ← brgc_word_div_two]
2^n = 2 * 2^(n - 1)
Since n ≥ 2, we write n = (n - 1) + 1, expand 2^((n - 1) + 1) = 2^(n - 1) * 2 via pow_succ, and rearrange factors using linear arithmetic.
uses
pow_succhave hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by conv_lhs => rw [show n = (n - 1) + 1 by omega, pow_succ] omega
The rotation simplifies to brgc_word t + (brgc_word t / 2) / 2^(n - 1) = brgc_word t
Because brgc_word t is even, 2 * (brgc_word t / 2) = brgc_word t. Since brgc_word t < 2^n, taking the remainder modulo 2^n leaves brgc_word t unchanged by Nat.mod_eq_of_lt. Substituting these into the first term simplifies it to brgc_word t.
uses
Nat.mod_eq_of_lthave hdouble : 2 * (brgc_word t / 2) = brgc_word t := by omega rw [hdouble, Nat.mod_eq_of_lt hxlt]
The high-order bit term (brgc_word t / 2) / 2^(n - 1) vanishes, closing the contradiction
Because brgc_word t < 2^n = 2 * 2^(n - 1), we have brgc_word t / 2 < 2^(n - 1), so dividing by 2^(n - 1) yields 0 by Nat.div_eq_of_lt. Substituting 0 gives brgc_word t + 0 = brgc_word t, which is an identity and produces the desired contradiction.
uses
Nat.div_eq_of_lthave hdiv : brgc_word t / 2 / 2 ^ (n - 1) = 0 := by apply Nat.div_eq_of_lt omega omega
brgc_word_lt_two_pow- If t < 2^n, then brgc_word t < 2^n.
Nat.div_lt_self- If 0 < n and 1 < k, then n / k < n.
Function.iterate_one- Iterating a function once is the function itself: f^[1] = f.
brgc_word_div_two- Halving the BRGC word of t equals the BRGC word of t / 2: brgc_word t / 2 = brgc_word (t / 2).
pow_succ- For any base a and exponent n, a^(n + 1) = a^n * a.
Nat.mod_eq_of_lt- If a < b, then a % b = a.
Nat.div_eq_of_lt- If a < b, then integer division yields a / b = 0.
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_word_odd {n t : ℕ} (hn : 2 ≤ n) (ht : brgc_necklace_first_rank n t) : brgc_word t % 2 = 1 := by have htpos : 0 < t := by by_contra h have : t = 0 := by omega exact ht.2.1 (by simp [this, brgc_word]) have hxlt := brgc_word_lt_two_pow ht.1 by_contra hodd have heven : brgc_word t % 2 = 0 := by omega have hsmall : t / 2 < t := Nat.div_lt_self htpos (by omega) apply ht.2.2.2 (t / 2) hsmall refine ⟨1, by omega, ?_⟩ simp only [Function.iterate_one] rw [bitword_rotate, ← brgc_word_div_two] have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by conv_lhs => rw [show n = (n - 1) + 1 by omega, pow_succ] omega have hdouble : 2 * (brgc_word t / 2) = brgc_word t := by omega rw [hdouble, Nat.mod_eq_of_lt hxlt] have hdiv : brgc_word t / 2 / 2 ^ (n - 1) = 0 := by apply Nat.div_eq_of_lt omega omega