AFTD Auto-Formalizing Theoretical Domains

brgc_necklace_first_rank_min_rotations

theoremverified

Every rotation of a first-occurrence representative has inverse Gray rank at least its first-occurrence rank.

Statement

theorem brgc_necklace_first_rank_min_rotations {n t : ℕ} (hn : 2 ≤ n)
    (ht : brgc_necklace_first_rank n t) :
    ∀ r < n, t ≤ brgc_inverse n ((bitword_rotate n)^[r] (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 9
  • 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_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_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_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
  • brgc_word_inverseEncoding the n-bit inverse prefix-parity transform recovers the word.
  • 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

The proof, explained

The theorem asserts that if $t$ is the first rank where its Gray code necklace occurs, any cyclic rotation of its Gray code word decodes to an inverse Gray rank at least $t$. The case of zero rotation holds trivially because decoding the encoding of $t$ recovers $t$. For a positive rotation by $r < n$ bits, if the decoded rank $s$ were strictly smaller than $t$, rotating $s$ by the remaining $n - r$ bits would recover the original word, demonstrating that $s < t$ belongs to the same necklace and contradicting the minimality of $t$.

  1. The Gray code word of rank $t$ is strictly between $0$ and $2^n - 1$, and rotating it $n$ times yields itself.

    From the hypothesis that $t$ is a first-occurrence rank, $t < 2^n$, which implies $t / 2 \le t < 2^n$ by `Nat.div_le_self` and `lt_of_le_of_lt`. Thus the Gray code word $w = t \oplus (t / 2)$ satisfies $w < 2^n$ by `Nat.xor_lt_two_pow`. Since $w \ne 0$ (by hypothesis), it is positive by `Nat.pos_of_ne_zero`. Since $w < 2^n$ and $w \ne 2^n - 1$ (by hypothesis), linear arithmetic gives $w < 2^n - 1$. Applying `bitword_rotate_iterate_self` shows that rotating $w$ by $n$ positions returns $w$.

    lines 4–8

    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
  2. For $r = 0$, the inequality $t \le \text{brgc\_inverse } n ((\text{bitword\_rotate } n)^r w)$ holds trivially.

    Fix a rotation count $r < n$. In the case $r = 0$, applying zero rotations is the identity by `Function.iterate_zero` and `id_eq`. Decoding the Gray code word of rank $t < 2^n$ gives $t$ by `brgc_inverse_word`. Hence the goal simplifies to $t \le t$, which holds by reflexivity (`le_refl`).

    lines 9–12

    uses Function.iterate_zero, id_eq, brgc_inverse_word, le_refl

      intro r hr
      by_cases hr0 : r = 0
      · subst r
        simp only [Function.iterate_zero, id_eq, brgc_inverse_word ht.1, le_refl]
  3. For $r \ne 0$, the rotated word $y = (\text{bitword\_rotate } n)^r w$ satisfies $y < 2^n$.

    Applying `bitword_is_aperiodic_of_prime_iterate_eq_mod` to $w$ and $r$ gives that $y < 2^n - 1$. Linear arithmetic then implies $y < 2^n$.

    lines 13–18

    uses bitword_is_aperiodic_of_prime_iterate_eq_mod

      · let y := (bitword_rotate n)^[r] (brgc_word t)
        have hylt : y < 2 ^ n := by
          have hh := bitword_is_aperiodic_of_prime_iterate_eq_mod n hn
            (brgc_word t) hx0 hx1 r
          dsimp [y]
          omega
  4. Assuming $t > \text{brgc\_inverse } n \, y$ contradicts the minimality of $t$ if $\text{brgc\_word } (\text{brgc\_inverse } n \, y)$ is a rotation of $w$.

    Assume for contradiction that $t \not\le \text{brgc\_inverse } n \, y$. By `Nat.lt_of_not_ge`, this means $s := \text{brgc\_inverse } n \, y < t$. By definition of $t$ being the first-occurrence rank of its necklace, no rank $s < t$ can have its Gray code word be a cyclic rotation of $w$. Thus, establishing that $\text{brgc\_word } s$ is a rotation of $w$ will yield a contradiction.

    lines 19–21

    uses Nat.lt_of_not_ge

        by_contra hnot
        have hs : brgc_inverse n y < t := Nat.lt_of_not_ge hnot
        apply ht.2.2.2 (brgc_inverse n y) hs
  5. The word $\text{brgc\_word } s$ rotates to $w$ in $n - r$ steps, deriving False.

    Because $0 < r < n$, the remaining shift count satisfies $n - r < n$. Since $y < 2^n$, the decoded and re-encoded word $\text{brgc\_word } s = \text{brgc\_word } (\text{brgc\_inverse } n \, y)$ equals $y$ by `brgc_word_inverse`. Rotating $y$ by $n - r$ steps corresponds to rotating $w$ by $r$ steps and then by $n - r$ steps; by `Function.iterate_add_apply`, this is rotating $w$ by $(n - r) + r = n$ steps. Since an $n$-step rotation returns $w$, this shows $\text{brgc\_word } s$ rotates to $w$, contradicting the minimality assumption and completing the proof.

    lines 22–25

    uses brgc_word_inverse, Function.iterate_add_apply

        refine ⟨n - r, by omega, ?_⟩
        rw [brgc_word_inverse hylt]
        change (bitword_rotate n)^[n - r] ((bitword_rotate n)^[r] (brgc_word t)) = _
        rw [← Function.iterate_add_apply, show n - r + r = n by omega, hperiod]
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 \le b$ and $b < c$, then $a < c$
Nat.div_le_self
for any natural numbers $n$ and $k$, $n / k \le n$
Nat.pos_of_ne_zero
a nonzero natural number is strictly positive
bitword_rotate_iterate_self
rotating an $n$-bit word strictly between $0$ and $2^n - 1$ by $n$ positions returns the word itself
Function.iterate_zero
iterating a function zero times is the identity function
id_eq
the identity function evaluated at $a$ returns $a$
brgc_inverse_word
for $t < 2^n$, decoding the binary reflected Gray code of rank $t$ yields $t$
le_refl
the ordering relation $\le$ is reflexive
bitword_is_aperiodic_of_prime_iterate_eq_mod
for $2 \le n$ and $0 < x < 2^n - 1$, the $m$-th cyclic rotation of $x$ equals $(2^m x) \bmod (2^n - 1)$, which lies strictly between $0$ and $2^n - 1$
Nat.lt_of_not_ge
if a natural number is not greater than or equal to another, it is strictly less
brgc_word_inverse
for $x < 2^n$, encoding the inverse Gray code of $x$ yields $x$
Function.iterate_add_apply
applying a function iterated $m + n$ times is equal to applying it $m$ times to the result of applying it $n$ times

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_necklace_first_rank_min_rotations {n t : ℕ} (hn : 2 ≤ n)    (ht : brgc_necklace_first_rank n t) :    ∀ r < n, t ≤ brgc_inverse n ((bitword_rotate n)^[r] (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  intro r hr  by_cases hr0 : r = 0  · subst r    simp only [Function.iterate_zero, id_eq, brgc_inverse_word ht.1, le_refl]  · let y := (bitword_rotate n)^[r] (brgc_word t)    have hylt : y < 2 ^ n := by      have hh := bitword_is_aperiodic_of_prime_iterate_eq_mod n hn        (brgc_word t) hx0 hx1 r      dsimp [y]      omega    by_contra hnot    have hs : brgc_inverse n y < t := Nat.lt_of_not_ge hnot    apply ht.2.2.2 (brgc_inverse n y) hs    refine ⟨n - r, by omega, ?_⟩    rw [brgc_word_inverse hylt]    change (bitword_rotate n)^[n - r] ((bitword_rotate n)^[r] (brgc_word t)) = _    rw [← Function.iterate_add_apply, show n - r + r = n by omega, hperiod]
See it in the graphDiscuss this resultChallenge it