brgc_necklace_first_rank_rotation_max
Rotating a first-occurrence representative right once gives a representative of maximum inverse Gray rank in its rotation class; the hypothesis that the original representative ends in one is included explicitly.
Statement
theorem brgc_necklace_first_rank_rotation_max {n t : ℕ} (hn : 2 ≤ n)
(ht : brgc_necklace_first_rank n t) (hxodd : brgc_word t % 2 = 1) :
∀ r < n,
brgc_inverse n ((bitword_rotate n)^[r]
((bitword_rotate n)^[n - 1] (brgc_word t))) ≤
brgc_inverse n ((bitword_rotate n)^[n - 1] (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 13
- 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_cutCyclically rotating an n-bit nonconstant word left by a positions exchanges its prefix of length a and its suffix of length b, where a+b=n.
- 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_concatThe inverse Gray rank of a concatenation has the prefix inverse rank followed by the suffix inverse rank, complemented exactly when the…
- brgc_inverse_lt_two_powThe inverse prefix-parity transform of an n-bit word has an n-bit rank.
- brgc_inverse_prefixThe inverse Gray rank of a high-bit prefix is the corresponding high-bit prefix of the inverse rank.
- 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_necklace_first_rank_min_rotationsEvery rotation of a first-occurrence representative has inverse Gray rank at least its first-occurrence rank.
- 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
To show that rotating a first-occurrence representative word x right by one position yields a word z of maximum inverse Gray rank in its rotation class, the development first proves two auxiliary lemmas: one computing the inverse Gray rank of a word with leading bit 1 in terms of its lower bits, and one showing that rotating such a word left by one bit sets its lowest bit to 1. Using these, the proof computes that z has rank 2^n - 1 - ⌊t / 2⌋ ≥ 2^(n - 1). For any rotation w of z, if the leading bit of w is 0, its rank is strictly below 2^(n - 1); if its leading bit is 1, rotating w once left gives a rotation of x whose rank is at least t by minimality, which by the auxiliary formulas forces the rank of w to be at most that of z.
The inverse Gray rank of 2^(n - 1) + x / 2 expands via concatenation to 2^(n - 1) + (2^(n - 1) - 1 - brgc_inverse (n - 1) (x / 2)).
Applying brgc_inverse_concat with prefix length 1, suffix length n - 1, and leading word 1, the rank of the leading 1-bit word is 1 (odd). This selects the inverted branch 2^(n - 1) - 1 - brgc_inverse (n - 1) (x / 2) via ite_false and mul_one.
uses
Nat.two_pow_pos,pow_succ,brgc_inverse_concat,mul_one,ite_falsehave hp : 0 < 2 ^ (n - 1) := Nat.two_pow_pos _ have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by conv_lhs => rw [show n = (n - 1) + 1 by omega, pow_succ] omega have hhalf : x / 2 < 2 ^ (n - 1) := by omega have hh := brgc_inverse_concat (m := 1) (k := n - 1) (a := 1) (by decide : 1 < 2 ^ 1) hhalf have hi : brgc_inverse 1 1 = 1 := rfl rw [hi] at hh simp only [mul_one, Nat.reduceMod, show (1 : ℕ) ≠ 0 by decide, ite_false] at hh rw [show 1 + (n - 1) = n by omega] at hh rw [hh]
The inverse Gray rank of 2^(n - 1) + x / 2 equals 2^n - 1 - (brgc_inverse n x) / 2.
By brgc_inverse_prefix, (brgc_inverse n x) / 2 equals brgc_inverse (n - 1) (x / 2). Substituting this into the concatenation formula and bounding by brgc_inverse_lt_two_pow, linear arithmetic over powers of 2 reduces the rank to 2^n - 1 - (brgc_inverse n x) / 2.
uses
brgc_inverse_prefix,brgc_inverse_lt_two_powhave hprefix := brgc_inverse_prefix (show 1 ≤ n by omega) hx have hprefix' : brgc_inverse n x / 2 = brgc_inverse (n - 1) (x / 2) := by simpa using hprefix have hi_bound := brgc_inverse_lt_two_pow hhalf omega
For w < 2^n with w ≥ 2^(n - 1), (2 * w) % 2^n = 2 * (w - 2^(n - 1)).
Writing 2 * w = 2^n + 2 * (w - 2^(n - 1)), modulo arithmetic distributes using Nat.add_mod and Nat.mod_self. Because 2 * (w - 2^(n - 1)) < 2^n, Nat.mod_eq_of_lt simplifies the remainder directly.
uses
Nat.two_pow_pos,pow_succ,Nat.add_mod,Nat.mod_self,zero_add,Nat.mod_mod,Nat.mod_eq_of_lthave hp : 0 < 2 ^ (n - 1) := Nat.two_pow_pos _ have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by conv_lhs => rw [show n = (n - 1) + 1 by omega, pow_succ] omega have hmod : 2 * w % 2 ^ n = 2 * (w - 2 ^ (n - 1)) := by have he : 2 * w = 2 ^ n + 2 * (w - 2 ^ (n - 1)) := by omega rw [he] simp only [Nat.add_mod, Nat.mod_self, zero_add, Nat.mod_mod] exact Nat.mod_eq_of_lt (by omega)
Rotating an n-bit word w with leading bit 1 left by one position gives 2 * (w - 2^(n - 1)) + 1.
Because 2^(n - 1) ≤ w < 2^n, integer division w / 2^(n - 1) equals 1 by Nat.div_eq_of_lt_le. Unfolding bitword_rotate and substituting the modulo and division results yields 2 * (w - 2^(n - 1)) + 1.
uses
Nat.div_eq_of_lt_lehave hd : w / 2 ^ (n - 1) = 1 := by apply Nat.div_eq_of_lt_le <;> omega simp only [bitword_rotate, hmod, hd]
The BRGC word x = brgc_word t satisfies 0 < x < 2^n - 1, and rotating it n times returns x.
Because t < 2^n, the bitwise XOR definition of the Gray code ensures x < 2^n. The necklace first-rank hypothesis excludes x = 0 and x = 2^n - 1. Rotating any such non-trivial word n times returns the original word by bitword_rotate_iterate_self.
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
Rotating x right by 1 bit (which is rotating left by n - 1 bits) yields z = 2^(n - 1) + x / 2.
Because x is odd, its lowest bit is 1, so x = 2 * (x / 2) + 1. Rotating left by n - 1 bits swaps the lower 1 bit and the upper n - 1 bits by bitword_rotate_iterate_cut, placing the 1 in the most significant position 2^(n - 1) and shifting x / 2 to the lower bits.
uses
pow_succ,bitword_rotate_iterate_cuthave hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by conv_lhs => rw [show n = (n - 1) + 1 by omega, pow_succ] omega have hhalf : brgc_word t / 2 < 2 ^ (n - 1) := by omega have hxsplit : brgc_word t = 2 ^ 1 * (brgc_word t / 2) + 1 := by norm_num; omega have hz : (bitword_rotate n)^[n - 1] (brgc_word t) = 2 ^ (n - 1) + brgc_word t / 2 := by conv_lhs => rw [hxsplit] have hh := bitword_rotate_iterate_cut hn (show n - 1 + 1 = n by omega) hhalf (by decide : 1 < 2 ^ 1) (show 0 < 2 ^ 1 * (brgc_word t / 2) + 1 by omega) (show 2 ^ 1 * (brgc_word t / 2) + 1 < 2 ^ n - 1 by rwa [← hxsplit]) simpa using hh
The inverse Gray rank of z is 2^n - 1 - t / 2, which is at least 2^(n - 1).
By brgc_aux_inverse_right_one, the inverse Gray rank of 2^(n - 1) + x / 2 is 2^n - 1 - (brgc_inverse n x) / 2. Since brgc_inverse n x = t by brgc_inverse_word, this simplifies to 2^n - 1 - t / 2. Since t < 2^n, we have t / 2 < 2^(n - 1), so this rank is at least 2^(n - 1).
uses
brgc_aux_inverse_right_one,brgc_inverse_wordhave hzr : brgc_inverse n ((bitword_rotate n)^[n - 1] (brgc_word t)) = 2 ^ n - 1 - t / 2 := by rw [hz, brgc_aux_inverse_right_one (by omega) hx, brgc_inverse_word ht.1] have htr : t / 2 < 2 ^ (n - 1) := by have htt := ht.1; omega have hlowrank : 2 ^ (n - 1) ≤ brgc_inverse n ((bitword_rotate n)^[n - 1] (brgc_word t)) := by omega
For any rotation count r < n, the rotated word w = rotate^r(z) satisfies w < 2^n.
The word w is the (r + n - 1)-th rotation of x. By bitword_is_aperiodic_of_prime_iterate_eq_mod, every rotation of the non-trivial word x is strictly less than 2^n - 1 < 2^n.
uses
bitword_is_aperiodic_of_prime_iterate_eq_mod,Function.iterate_add_applyintro r hr let w := (bitword_rotate n)^[r] ((bitword_rotate n)^[n - 1] (brgc_word t)) have hw : w < 2 ^ n := by have hh := bitword_is_aperiodic_of_prime_iterate_eq_mod n hn (brgc_word t) hx0 hx1 (r + (n - 1)) dsimp [w] rw [← Function.iterate_add_apply] omega
If the leading bit of w is 0 (w < 2^(n - 1)), then its inverse Gray rank is strictly less than 2^(n - 1), which is at most the rank of z.
When w < 2^(n - 1), its inverse Gray rank in n bits equals its rank in n - 1 bits by brgc_aux_inverse_stable. By brgc_inverse_lt_two_pow, this rank is strictly less than 2^(n - 1). Since the rank of z is at least 2^(n - 1), the required inequality holds.
uses
brgc_aux_inverse_stable,brgc_inverse_lt_two_powby_cases hwh : w < 2 ^ (n - 1) · have hstable : brgc_inverse n w = brgc_inverse (n - 1) w := brgc_aux_inverse_stable hw hwh have hwrank : brgc_inverse n w < 2 ^ (n - 1) := by rw [hstable]; exact brgc_inverse_lt_two_pow hwh change brgc_inverse n w ≤ _ omega
If the leading bit of w is 1 (w ≥ 2^(n - 1)), rotating w once left yields rotate^r(x), whose inverse Gray rank is at least t.
Rotating w once left gives the (r + n)-th rotation of x, which equals rotate^r(x) because rotating n times is the identity. Because t is a first-occurrence representative, it minimizes the inverse Gray rank among all rotations of x, so t ≤ brgc_inverse n (bitword_rotate n w) by brgc_necklace_first_rank_min_rotations.
uses
Function.iterate_add_apply,Function.iterate_succ_apply',bitword_is_aperiodic_of_prime_iterate_eq_mod,brgc_necklace_first_rank_min_rotations· have hv : bitword_rotate n w = (bitword_rotate n)^[r] (brgc_word t) := by dsimp [w] rw [← Function.iterate_add_apply, ← Function.iterate_succ_apply' (bitword_rotate n) (r + (n - 1)) (brgc_word t), show (r + (n - 1)).succ = r + n by omega, Function.iterate_add_apply, hperiod] have hvbound : bitword_rotate n w < 2 ^ n := by have hh := bitword_is_aperiodic_of_prime_iterate_eq_mod n hn (brgc_word t) hx0 hx1 r rw [hv] omega have hmin : t ≤ brgc_inverse n (bitword_rotate n w) := by rw [hv] exact brgc_necklace_first_rank_min_rotations hn ht r hr
If w ≥ 2^(n - 1), its inverse Gray rank is at most 2^n - 1 - t / 2, matching the rank of z.
By brgc_aux_rotate_high, rotating w left gives 2 * (w - 2^(n - 1)) + 1, so w = 2^(n - 1) + (bitword_rotate n w) / 2. By brgc_aux_inverse_right_one, its rank is 2^n - 1 - (brgc_inverse n (bitword_rotate n w)) / 2. Since t ≤ brgc_inverse n (bitword_rotate n w), dividing by 2 and subtracting from 2^n - 1 reverses the inequality, yielding at most 2^n - 1 - t / 2.
uses
brgc_aux_rotate_high,brgc_aux_inverse_right_one,Nat.sub_le_sub_left,Nat.div_le_div_righthave hwexpr : w = 2 ^ (n - 1) + bitword_rotate n w / 2 := by rw [brgc_aux_rotate_high (by omega) hw (by omega)] omega change brgc_inverse n w ≤ _ rw [hwexpr, brgc_aux_inverse_right_one (by omega) hvbound, hzr] exact Nat.sub_le_sub_left (Nat.div_le_div_right hmin) _
Nat.two_pow_pos- Two to any power is strictly positive.
pow_succ- In a monoid, a^(n + 1) = a^n * a.
brgc_inverse_concat- The inverse Gray rank of the concatenation of an m-bit word a and a k-bit word b equals 2^k * brgc_inverse m a plus either brgc_inverse k b (if the rank of a is even) or 2^k - 1 - brgc_inverse k b (if odd).
mul_one- Multiplying by 1 leaves an element unchanged.
ite_false- An if-then-else with condition False evaluates to the else branch.
brgc_inverse_prefix- Dividing the inverse Gray rank of an n-bit word by 2^k gives the inverse Gray rank of the prefix of length n - k.
brgc_inverse_lt_two_pow- The inverse Gray rank of an n-bit word is strictly less than 2^n.
Nat.add_mod- The remainder of a sum modulo n is the sum of the remainders modulo n.
Nat.mod_self- The remainder of n modulo n is 0.
zero_add- Adding 0 on the left is the identity.
Nat.mod_mod- Taking the remainder modulo n twice is the same as taking it once.
Nat.mod_eq_of_lt- If a < b, then a modulo b equals a.
Nat.div_eq_of_lt_le- If k * n ≤ m < (k + 1) * n, then m / n = k.
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 ≤ b and b < c, then a < c.
Nat.div_le_self- Integer division of n by any natural number is at most n.
Nat.pos_of_ne_zero- A non-zero natural number is strictly positive.
bitword_rotate_iterate_self- Rotating an n-bit word n times returns the word itself, provided 0 < x < 2^n - 1 and 2 ≤ n.
bitword_rotate_iterate_cut- Rotating an n-bit word composed of an a-bit prefix and a b-bit suffix left by a bits swaps the two parts to form 2^a * v + u.
brgc_aux_inverse_right_one- For an n-bit word with leading bit 1 and lower bits x / 2, its inverse Gray rank is 2^n - 1 - (brgc_inverse n x) / 2.
brgc_inverse_word- The inverse Gray rank of the BRGC word of index t is t.
bitword_is_aperiodic_of_prime_iterate_eq_mod- Every iterate of bit-rotation on a non-trivial word 0 < x < 2^n - 1 satisfies the modular formula 2^m * x % (2^n - 1) and remains strictly between 0 and 2^n - 1.
Function.iterate_add_apply- Applying a function iterated m + n times equals applying it m times to the n-th iterate.
brgc_aux_inverse_stable- If x < 2^m and x < 2^n, the inverse Gray rank of x is identical in m bits and n bits.
Function.iterate_succ_apply'- Applying f iterated n + 1 times equals applying f to the n-th iterate.
brgc_necklace_first_rank_min_rotations- A first-occurrence representative t minimizes the inverse Gray rank across all rotations of its BRGC word.
brgc_aux_rotate_high- Rotating an n-bit word w with leading bit 1 left by 1 bit yields 2 * (w - 2^(n - 1)) + 1.
Nat.sub_le_sub_left- For natural numbers, if n ≤ m then k - m ≤ k - n.
Nat.div_le_div_right- Integer division of natural numbers preserves inequality: if a ≤ b, then a / c ≤ b / c.
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_aux_inverse_right_one {n x : ℕ} (hn : 0 < n) (hx : x < 2 ^ n) : brgc_inverse n (2 ^ (n - 1) + x / 2) = 2 ^ n - 1 - brgc_inverse n x / 2 := by have hp : 0 < 2 ^ (n - 1) := Nat.two_pow_pos _ have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by conv_lhs => rw [show n = (n - 1) + 1 by omega, pow_succ] omega have hhalf : x / 2 < 2 ^ (n - 1) := by omega have hh := brgc_inverse_concat (m := 1) (k := n - 1) (a := 1) (by decide : 1 < 2 ^ 1) hhalf have hi : brgc_inverse 1 1 = 1 := rfl rw [hi] at hh simp only [mul_one, Nat.reduceMod, show (1 : ℕ) ≠ 0 by decide, ite_false] at hh rw [show 1 + (n - 1) = n by omega] at hh rw [hh] have hprefix := brgc_inverse_prefix (show 1 ≤ n by omega) hx have hprefix' : brgc_inverse n x / 2 = brgc_inverse (n - 1) (x / 2) := by simpa using hprefix have hi_bound := brgc_inverse_lt_two_pow hhalf omegatheorem brgc_aux_rotate_high {n w : ℕ} (hn : 0 < n) (hw : w < 2 ^ n) (hhigh : 2 ^ (n - 1) ≤ w) : bitword_rotate n w = 2 * (w - 2 ^ (n - 1)) + 1 := by have hp : 0 < 2 ^ (n - 1) := Nat.two_pow_pos _ have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by conv_lhs => rw [show n = (n - 1) + 1 by omega, pow_succ] omega have hmod : 2 * w % 2 ^ n = 2 * (w - 2 ^ (n - 1)) := by have he : 2 * w = 2 ^ n + 2 * (w - 2 ^ (n - 1)) := by omega rw [he] simp only [Nat.add_mod, Nat.mod_self, zero_add, Nat.mod_mod] exact Nat.mod_eq_of_lt (by omega) have hd : w / 2 ^ (n - 1) = 1 := by apply Nat.div_eq_of_lt_le <;> omega simp only [bitword_rotate, hmod, hd]theorem brgc_necklace_first_rank_rotation_max {n t : ℕ} (hn : 2 ≤ n) (ht : brgc_necklace_first_rank n t) (hxodd : brgc_word t % 2 = 1) : ∀ r < n, brgc_inverse n ((bitword_rotate n)^[r] ((bitword_rotate n)^[n - 1] (brgc_word t))) ≤ brgc_inverse n ((bitword_rotate n)^[n - 1] (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 have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by conv_lhs => rw [show n = (n - 1) + 1 by omega, pow_succ] omega have hhalf : brgc_word t / 2 < 2 ^ (n - 1) := by omega have hxsplit : brgc_word t = 2 ^ 1 * (brgc_word t / 2) + 1 := by norm_num; omega have hz : (bitword_rotate n)^[n - 1] (brgc_word t) = 2 ^ (n - 1) + brgc_word t / 2 := by conv_lhs => rw [hxsplit] have hh := bitword_rotate_iterate_cut hn (show n - 1 + 1 = n by omega) hhalf (by decide : 1 < 2 ^ 1) (show 0 < 2 ^ 1 * (brgc_word t / 2) + 1 by omega) (show 2 ^ 1 * (brgc_word t / 2) + 1 < 2 ^ n - 1 by rwa [← hxsplit]) simpa using hh have hzr : brgc_inverse n ((bitword_rotate n)^[n - 1] (brgc_word t)) = 2 ^ n - 1 - t / 2 := by rw [hz, brgc_aux_inverse_right_one (by omega) hx, brgc_inverse_word ht.1] have htr : t / 2 < 2 ^ (n - 1) := by have htt := ht.1; omega have hlowrank : 2 ^ (n - 1) ≤ brgc_inverse n ((bitword_rotate n)^[n - 1] (brgc_word t)) := by omega intro r hr let w := (bitword_rotate n)^[r] ((bitword_rotate n)^[n - 1] (brgc_word t)) have hw : w < 2 ^ n := by have hh := bitword_is_aperiodic_of_prime_iterate_eq_mod n hn (brgc_word t) hx0 hx1 (r + (n - 1)) dsimp [w] rw [← Function.iterate_add_apply] omega by_cases hwh : w < 2 ^ (n - 1) · have hstable : brgc_inverse n w = brgc_inverse (n - 1) w := brgc_aux_inverse_stable hw hwh have hwrank : brgc_inverse n w < 2 ^ (n - 1) := by rw [hstable]; exact brgc_inverse_lt_two_pow hwh change brgc_inverse n w ≤ _ omega · have hv : bitword_rotate n w = (bitword_rotate n)^[r] (brgc_word t) := by dsimp [w] rw [← Function.iterate_add_apply, ← Function.iterate_succ_apply' (bitword_rotate n) (r + (n - 1)) (brgc_word t), show (r + (n - 1)).succ = r + n by omega, Function.iterate_add_apply, hperiod] have hvbound : bitword_rotate n w < 2 ^ n := by have hh := bitword_is_aperiodic_of_prime_iterate_eq_mod n hn (brgc_word t) hx0 hx1 r rw [hv] omega have hmin : t ≤ brgc_inverse n (bitword_rotate n w) := by rw [hv] exact brgc_necklace_first_rank_min_rotations hn ht r hr have hwexpr : w = 2 ^ (n - 1) + bitword_rotate n w / 2 := by rw [brgc_aux_rotate_high (by omega) hw (by omega)] omega change brgc_inverse n w ≤ _ rw [hwexpr, brgc_aux_inverse_right_one (by omega) hvbound, hzr] exact Nat.sub_le_sub_left (Nat.div_le_div_right hmin) _