AFTD Auto-Formalizing Theoretical Domains

brgc_necklace_first_rank_rotation_max

theoremverified

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.

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

    lines 4–15

    uses Nat.two_pow_pos, pow_succ, brgc_inverse_concat, mul_one, ite_false

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

    lines 16–19

    uses brgc_inverse_prefix, brgc_inverse_lt_two_pow

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

    lines 24–32

    uses Nat.two_pow_pos, pow_succ, Nat.add_mod, Nat.mod_self, zero_add, Nat.mod_mod, Nat.mod_eq_of_lt

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

    lines 33–35

    uses Nat.div_eq_of_lt_le

      have hd : w / 2 ^ (n - 1) = 1 := by
        apply Nat.div_eq_of_lt_le <;> omega
      simp only [bitword_rotate, hmod, hd]
  5. 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.

    lines 43–47

    uses Nat.xor_lt_two_pow, lt_of_le_of_lt, Nat.div_le_self, Nat.pos_of_ne_zero, bitword_rotate_iterate_self

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

    lines 48–60

    uses pow_succ, bitword_rotate_iterate_cut

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

    lines 61–66

    uses brgc_aux_inverse_right_one, brgc_inverse_word

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

    lines 67–74

    uses bitword_is_aperiodic_of_prime_iterate_eq_mod, Function.iterate_add_apply

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

    lines 75–79

    uses brgc_aux_inverse_stable, brgc_inverse_lt_two_pow

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

    lines 80–93

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

    lines 94–99

    uses brgc_aux_rotate_high, brgc_aux_inverse_right_one, Nat.sub_le_sub_left, Nat.div_le_div_right

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

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