AFTD Auto-Formalizing Theoretical Domains

brgc_inverse_flip_preserves_rotation_max

theoremverifiedformalization

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

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.

  1. 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.

    lines 8–25

    uses bitword_rotate_iterate_cut, brgc_aux_concat_bound, brgc_aux_inverse_inj

      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
  2. 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.

    line 26

    uses brgc_inverse_flip_preserves_cut_max

      have hweak := brgc_inverse_flip_preserves_cut_max n x hx hstrict
  3. Every 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.

    lines 27–46

    uses brgc_aux_word_prefix_bound, Nat.mod_lt, Nat.two_pow_pos, Nat.div_add_mod, bitword_rotate_iterate_cut

      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 hsplit
  4. 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.

    lines 50–62

    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_le

      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]
      omega
  5. 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.

    lines 70–74

    uses le_of_eq, congrArg

      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))
  6. 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.

    lines 75–80

    uses brgc_aux_rotate_all_ones, le_of_eq, congrArg

      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))
  7. 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.

    lines 81–83

    uses Nat.xor_lt_two_pow, Nat.one_lt_two_pow, brgc_aux_flip_preserves_rotation_max

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it