brgc_inverse_flip_preserves_rotation_max
Toggling the last bit of an aperiodic nonconstant word that maximizes its inverse Gray rank over all rotations again maximizes that rank, for word length at least two.
Statement
theorem brgc_inverse_flip_preserves_rotation_max (n x : ℕ) (hn : 2 ≤ n)
(hx0 : 0 < x) (hx1 : x < 2 ^ n - 1)
(hap : bitword_is_aperiodic n x)
(hmax : ∀ r < n, brgc_inverse n ((bitword_rotate n)^[r] x) ≤ brgc_inverse n x) :
∀ r < n, brgc_inverse n ((bitword_rotate n)^[r] (x ^^^ 1)) ≤
brgc_inverse n (x ^^^ 1)- Formalizes
- Gray-ordered Binary Necklaces (2007), Theorem 3.6, in the equivalent convention of maximal forward Gray rank; the rotation form adds nonconstant-word hypotheses.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- bitword_is_aperiodicThe n-bit word x is aperiodic (primitive): no rotation by 0 < r < n fixes it, i.e. its necklace has n distinct rotations.
- 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.
- 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_flip_preserves_cut_maxIf an n-bit word has strictly greater inverse Gray rank than every nontrivial cyclic cut, toggling its last bit has at least as great an…
- Used by 1
- alpha_lexical_odd_completion_iff_rotation_max_of_primeThe proposed encoding bridge between positive lexical sequences and nonconstant odd-parity maximum-rank necklace representatives at odd…
The proof, explained
To show that toggling the last bit of an aperiodic word x that maximizes the inverse Gray rank over cyclic rotations again maximizes that rank, the proof splits into cases depending on whether the flipped word x ^^^ 1 is constant. If x ^^^ 1 is all zeros or all ones, it is invariant under rotation, so every rotation has the same inverse Gray rank and the inequality holds with equality. When x ^^^ 1 is nonconstant, the aperiodicity and rotation-maximality of x imply that x strictly maximizes the inverse Gray rank over all nontrivial cuts. An auxiliary preservation theorem then shows that x ^^^ 1 weakly maximizes the inverse Gray rank over all cuts, and because rotating x ^^^ 1 corresponds to swapping prefix and suffix at a cut, this bounds the rank of every rotation.
The word x strictly maximizes the inverse Gray rank over all nontrivial cuts.
From x < 2^n - 1 we have x < 2^n. Given any decomposition x = 2^b * u + v with a, b > 0, a + b = n, u < 2^a, and v < 2^b, rotating x by a steps produces the transposed word 2^a * v + u by bitword_rotate_iterate_cut. By the hypothesis that x maximizes inverse Gray rank across all rotations, the inverse Gray rank of 2^a * v + u is at most that of x. If equality held, injectivity of brgc_inverse on inputs less than 2^n (brgc_aux_inverse_inj, with the bound verified by brgc_aux_concat_bound) would force the a-th rotation of x to equal x. Because 0 < a < n, this contradicts the aperiodicity of x (hap). Thus the inequality between inverse Gray ranks is strict.
uses
bitword_rotate_iterate_cut,brgc_aux_concat_bound,brgc_aux_inverse_injhave hx : x < 2 ^ n := by omega have hstrict : ∀ a b u v : ℕ, 0 < a → 0 < b → a + b = n → u < 2 ^ a → v < 2 ^ b → x = 2 ^ b * u + v → brgc_inverse n (2 ^ a * v + u) < brgc_inverse n x := by intro a b u v ha hb hab hu hv hsplit have ha' : a < n := by omega have hrot : (bitword_rotate n)^[a] x = 2 ^ a * v + u := by rw [hsplit] exact bitword_rotate_iterate_cut hn hab hu hv (by rwa [← hsplit]) (by rwa [← hsplit]) have hle := hmax a ha' rw [hrot] at hle by_contra hnot have heq : brgc_inverse n (2 ^ a * v + u) = brgc_inverse n x := by omega have hbound : 2 ^ a * v + u < 2 ^ n := by simpa only [show b + a = n by omega] using brgc_aux_concat_bound hv hu have hfix : (bitword_rotate n)^[a] x = x := hrot.trans (brgc_aux_inverse_inj hbound hx heq) exact hap a ha ha' hfix
Toggling the lowest bit of x produces a word x ^^^ 1 that weakly maximizes inverse Gray rank over all cuts.
Applying the lemma brgc_inverse_flip_preserves_cut_max with the bound x < 2^n and the strict cut-maximality of x, any nontrivial cut x ^^^ 1 = 2^b * u + v has transposed inverse Gray rank at most that of x ^^^ 1.
uses
brgc_inverse_flip_preserves_cut_maxhave hweak := brgc_inverse_flip_preserves_cut_max n x hx hstrictEvery cyclic rotation of x ^^^ 1 has inverse Gray rank at most that of x ^^^ 1, completing the auxiliary lemma.
Let r < n be any rotation shift. If r = 0, the rotation is the identity and the inequality is immediate. If r > 0, set b = n - r and decompose x ^^^ 1 = 2^b * u + v via division by 2^b (Nat.div_add_mod), where u < 2^r by brgc_aux_word_prefix_bound and v < 2^b by Nat.mod_lt and Nat.two_pow_pos. By bitword_rotate_iterate_cut, rotating x ^^^ 1 by r positions produces the transposed word 2^r * v + u. Applying the weak cut-maximality hweak to this cut yields the desired bound.
uses
brgc_aux_word_prefix_bound,Nat.mod_lt,Nat.two_pow_pos,Nat.div_add_mod,bitword_rotate_iterate_cutintro r hr by_cases hr0 : r = 0 · subst r simp · let b := n - r let u := (x ^^^ 1) / 2 ^ b let v := (x ^^^ 1) % 2 ^ b have hb : 0 < b := by dsimp [b]; omega have hab : r + b = n := by dsimp [b]; omega have hu : u < 2 ^ r := by apply brgc_aux_word_prefix_bound simpa only [hab] using (show x ^^^ 1 < 2 ^ n by omega) have hv : v < 2 ^ b := Nat.mod_lt _ (Nat.two_pow_pos _) have hsplit : x ^^^ 1 = 2 ^ b * u + v := (Nat.div_add_mod (x ^^^ 1) (2 ^ b)).symm have hrot : (bitword_rotate n)^[r] (x ^^^ 1) = 2 ^ r * v + u := by rw [hsplit] exact bitword_rotate_iterate_cut hn hab hu hv (by rwa [← hsplit]) (by rwa [← hsplit]) rw [hrot] exact hweak r b u v (by omega) hb hab hu hv hsplit
The all-ones word 2^n - 1 of length n > 0 is fixed under cyclic rotation.
The definition of rotation bitword_rotate n maps y to (2 * y % 2^n) + y / 2^(n - 1). For y = 2^n - 1, write 2 * (2^n - 1) = 2^n + (2^n - 2); reducing modulo 2^n yields 2^n - 2 by Nat.add_mod, Nat.mod_self, zero_add, Nat.mod_mod, and Nat.mod_eq_of_lt. The quotient (2^n - 1) / 2^(n - 1) is 1 by Nat.div_eq_of_lt_le, using 2^n = 2 * 2^(n - 1) from pow_succ and Nat.two_pow_pos. Adding the remainder and quotient gives (2^n - 2) + 1 = 2^n - 1.
uses
Nat.two_pow_pos,pow_succ,Nat.add_mod,Nat.mod_self,zero_add,Nat.mod_mod,Nat.mod_eq_of_lt,Nat.div_eq_of_lt_lehave hp : 2 ^ (n - 1) > 0 := 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 * (2 ^ n - 1) % 2 ^ n = 2 ^ n - 2 := by have he : 2 * (2 ^ n - 1) = 2 ^ n + (2 ^ n - 2) := 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 : (2 ^ n - 1) / 2 ^ (n - 1) = 1 := by apply Nat.div_eq_of_lt_le <;> omega simp only [bitword_rotate, hmod, hd] omega
Rotation-maximality holds in the degenerate case x ^^^ 1 = 0.
If x ^^^ 1 = 0, then 0 is a fixed point of bitword_rotate n. Every r-th rotation of 0 is therefore 0 itself, and applying brgc_inverse n yields equal values, which gives the inequality by congrArg and le_of_eq.
uses
le_of_eq,congrArgby_cases hy0 : x ^^^ 1 = 0 · have hfix : Function.IsFixedPt (bitword_rotate n) (x ^^^ 1) := by simp [Function.IsFixedPt, hy0, bitword_rotate] intro r hr exact le_of_eq (congrArg (brgc_inverse n) (hfix.iterate r))
Rotation-maximality holds in the degenerate case x ^^^ 1 = 2^n - 1.
If x ^^^ 1 = 2^n - 1, then by brgc_aux_rotate_all_ones, 2^n - 1 is a fixed point of bitword_rotate n. Any r-th rotation is thus 2^n - 1, so the inverse Gray rank is unchanged, yielding the inequality by congrArg and le_of_eq.
uses
brgc_aux_rotate_all_ones,le_of_eq,congrArgby_cases hy1 : x ^^^ 1 = 2 ^ n - 1 · have hfix : Function.IsFixedPt (bitword_rotate n) (x ^^^ 1) := by rw [Function.IsFixedPt, hy1] exact brgc_aux_rotate_all_ones n (by omega) intro r hr exact le_of_eq (congrArg (brgc_inverse n) (hfix.iterate r))
Rotation-maximality holds in the general case where x ^^^ 1 is nonconstant.
Since x ^^^ 1 is neither 0 nor 2^n - 1, and x ^^^ 1 < 2^n by Nat.xor_lt_two_pow and Nat.one_lt_two_pow, x ^^^ 1 is strictly between 0 and 2^n - 1. The auxiliary theorem brgc_aux_flip_preserves_rotation_max directly applies to conclude that x ^^^ 1 maximizes the inverse Gray rank over all rotations.
uses
Nat.xor_lt_two_pow,Nat.one_lt_two_pow,brgc_aux_flip_preserves_rotation_maxhave hylt : x ^^^ 1 < 2 ^ n := Nat.xor_lt_two_pow (by omega) (Nat.one_lt_two_pow (by omega)) exact brgc_aux_flip_preserves_rotation_max n x hn hx0 hx1 (by omega) (by omega) hap hmax
bitword_rotate_iterate_cut- Rotating an n-bit word decomposed as 2^b * u + v (with a + b = n, u < 2^a, v < 2^b) by a positions cyclically swaps the prefix and suffix to produce 2^a * v + u.
brgc_aux_concat_bound- The concatenation 2^k * a + b of two bitwords of lengths m and k is strictly bounded by 2^(m + k).
brgc_aux_inverse_inj- The inverse Gray code ranking function brgc_inverse n is injective on integers strictly less than 2^n.
brgc_inverse_flip_preserves_cut_max- If an n-bit word x strictly maximizes inverse Gray rank over all nontrivial cut decompositions, then toggling its lowest bit produces a word that weakly maximizes inverse Gray rank over all cuts.
brgc_aux_word_prefix_bound- Integer division of a word strictly less than 2^(m + k) by 2^k yields a value strictly less than 2^m.
Nat.mod_lt- The remainder of integer division by a positive number is strictly less than the divisor.
Nat.two_pow_pos- Any power of two is strictly positive.
Nat.div_add_mod- Any natural number m equals n * (m / n) + m % n.
pow_succ- For any element a of a monoid, a^(n+1) = a^n * a.
Nat.add_mod- The modulo operation distributes over addition: (a + b) % n = (a % n + b % n) % n.
Nat.mod_self- Any natural number modulo itself is zero.
zero_add- Zero is the left identity for addition: 0 + a = a.
Nat.mod_mod- Taking the remainder modulo n twice is equivalent to taking it once.
Nat.mod_eq_of_lt- If a < b, then a % b = a.
Nat.div_eq_of_lt_le- If k * n ≤ m and m < (k + 1) * n, then m / n = k.
le_of_eq- Equality implies weak inequality in a preorder.
congrArg- A function applied to equal arguments produces equal results.
brgc_aux_rotate_all_ones- Rotating the all-ones word 2^n - 1 of length n > 0 leaves it invariant.
Nat.xor_lt_two_pow- The bitwise XOR of two numbers each less than 2^n is strictly less than 2^n.
Nat.one_lt_two_pow- For any nonzero n, 1 < 2^n.
brgc_aux_flip_preserves_rotation_max- For an aperiodic nonconstant word x of length n ≥ 2 whose flipped version x ^^^ 1 is also nonconstant, if x maximizes inverse Gray rank under all rotations, then so does x ^^^ 1.
- The proof is organized as three results: the auxiliary lemma `brgc_aux_flip_preserves_rotation_max` handles nonconstant words using a cut-decomposition argument; `brgc_aux_rotate_all_ones` establishes that the all-ones word is a fixed point of rotation; and the main theorem `brgc_inverse_flip_preserves_rotation_max` combines these with the trivial fixed-point property of the all-zeros word.
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_flip_preserves_rotation_max (n x : ℕ) (hn : 2 ≤ n) (hx0 : 0 < x) (hx1 : x < 2 ^ n - 1) (hy0 : 0 < x ^^^ 1) (hy1 : x ^^^ 1 < 2 ^ n - 1) (hap : bitword_is_aperiodic n x) (hmax : ∀ r < n, brgc_inverse n ((bitword_rotate n)^[r] x) ≤ brgc_inverse n x) : ∀ r < n, brgc_inverse n ((bitword_rotate n)^[r] (x ^^^ 1)) ≤ brgc_inverse n (x ^^^ 1) := by have hx : x < 2 ^ n := by omega have hstrict : ∀ a b u v : ℕ, 0 < a → 0 < b → a + b = n → u < 2 ^ a → v < 2 ^ b → x = 2 ^ b * u + v → brgc_inverse n (2 ^ a * v + u) < brgc_inverse n x := by intro a b u v ha hb hab hu hv hsplit have ha' : a < n := by omega have hrot : (bitword_rotate n)^[a] x = 2 ^ a * v + u := by rw [hsplit] exact bitword_rotate_iterate_cut hn hab hu hv (by rwa [← hsplit]) (by rwa [← hsplit]) have hle := hmax a ha' rw [hrot] at hle by_contra hnot have heq : brgc_inverse n (2 ^ a * v + u) = brgc_inverse n x := by omega have hbound : 2 ^ a * v + u < 2 ^ n := by simpa only [show b + a = n by omega] using brgc_aux_concat_bound hv hu have hfix : (bitword_rotate n)^[a] x = x := hrot.trans (brgc_aux_inverse_inj hbound hx heq) exact hap a ha ha' hfix have hweak := brgc_inverse_flip_preserves_cut_max n x hx hstrict intro r hr by_cases hr0 : r = 0 · subst r simp · let b := n - r let u := (x ^^^ 1) / 2 ^ b let v := (x ^^^ 1) % 2 ^ b have hb : 0 < b := by dsimp [b]; omega have hab : r + b = n := by dsimp [b]; omega have hu : u < 2 ^ r := by apply brgc_aux_word_prefix_bound simpa only [hab] using (show x ^^^ 1 < 2 ^ n by omega) have hv : v < 2 ^ b := Nat.mod_lt _ (Nat.two_pow_pos _) have hsplit : x ^^^ 1 = 2 ^ b * u + v := (Nat.div_add_mod (x ^^^ 1) (2 ^ b)).symm have hrot : (bitword_rotate n)^[r] (x ^^^ 1) = 2 ^ r * v + u := by rw [hsplit] exact bitword_rotate_iterate_cut hn hab hu hv (by rwa [← hsplit]) (by rwa [← hsplit]) rw [hrot] exact hweak r b u v (by omega) hb hab hu hv hsplittheorem brgc_aux_rotate_all_ones (n : ℕ) (hn : 0 < n) : bitword_rotate n (2 ^ n - 1) = 2 ^ n - 1 := by have hp : 2 ^ (n - 1) > 0 := 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 * (2 ^ n - 1) % 2 ^ n = 2 ^ n - 2 := by have he : 2 * (2 ^ n - 1) = 2 ^ n + (2 ^ n - 2) := 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 : (2 ^ n - 1) / 2 ^ (n - 1) = 1 := by apply Nat.div_eq_of_lt_le <;> omega simp only [bitword_rotate, hmod, hd] omegatheorem brgc_inverse_flip_preserves_rotation_max (n x : ℕ) (hn : 2 ≤ n) (hx0 : 0 < x) (hx1 : x < 2 ^ n - 1) (hap : bitword_is_aperiodic n x) (hmax : ∀ r < n, brgc_inverse n ((bitword_rotate n)^[r] x) ≤ brgc_inverse n x) : ∀ r < n, brgc_inverse n ((bitword_rotate n)^[r] (x ^^^ 1)) ≤ brgc_inverse n (x ^^^ 1) := by by_cases hy0 : x ^^^ 1 = 0 · have hfix : Function.IsFixedPt (bitword_rotate n) (x ^^^ 1) := by simp [Function.IsFixedPt, hy0, bitword_rotate] intro r hr exact le_of_eq (congrArg (brgc_inverse n) (hfix.iterate r)) by_cases hy1 : x ^^^ 1 = 2 ^ n - 1 · have hfix : Function.IsFixedPt (bitword_rotate n) (x ^^^ 1) := by rw [Function.IsFixedPt, hy1] exact brgc_aux_rotate_all_ones n (by omega) intro r hr exact le_of_eq (congrArg (brgc_inverse n) (hfix.iterate r)) have hylt : x ^^^ 1 < 2 ^ n := Nat.xor_lt_two_pow (by omega) (Nat.one_lt_two_pow (by omega)) exact brgc_aux_flip_preserves_rotation_max n x hn hx0 hx1 (by omega) (by omega) hap hmax