AFTD Auto-Formalizing Theoretical Domains

brgc_necklace_first_rank_exists_of_nonconstant

theoremverified

Every nonconstant binary word of length at least two has a first-occurrence Gray rank in its rotation class.

Statement

theorem brgc_necklace_first_rank_exists_of_nonconstant (n x : ℕ) (hn : 2 ≤ n) (hx0 : 0 < x) (hx1 : x < 2 ^ n - 1) : ∃ t, brgc_necklace_first_rank n t ∧ bitword_is_rotation n x (brgc_word t)
Source
First occurrences used in OP-392, arXiv:2610.24758, Section 3 and Conjecture 1.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 12

The proof, explained

To find a first-occurrence Gray rank in the rotation class (necklace) of a nonconstant binary word $x$, we consider the set of ranks $s$ whose Gray code word is nonconstant and in the rotation class of $x$. This set is nonempty because the Gray inverse of $x$ is a valid rank. By well-ordering, there is a minimal such rank $t$. If any strictly smaller rank $s < t$ had a Gray word that rotates to that of $t$, its Gray word could not be all-zero or all-ones (since these are fixed points under rotation), and hence it would also be nonconstant and in the rotation class of $x$, contradicting the minimality of $t$.

  1. For $n \ge 1$, powers of two are strictly positive and $2^n = 2 \cdot 2^{n-1}$.

    We establish $2^n > 0$ using `Nat.two_pow_pos`. Since $n \ge 1$, we rewrite $n$ as $(n - 1) + 1$, allowing $2^n$ to be factored as $2^{n-1} \cdot 2 = 2 \cdot 2^{n-1}$ via `pow_succ` and ring arithmetic. We also note that $2^{n-1} > 0$.

    lines 1–8

    uses Nat.two_pow_pos, pow_succ

    theorem brgc_necklace_first_rank_exists_of_nonconstant_rotate_all_ones (n : ℕ) (hn : 1 ≤ n) :
        bitword_rotate n (2 ^ n - 1) = 2 ^ n - 1 := by
      have h2n : 0 < 2 ^ n := Nat.two_pow_pos n
      have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by
        calc 2 ^ n = 2 ^ (n - 1 + 1) := by rw [show n - 1 + 1 = n by omega]
          _ = 2 ^ (n - 1) * 2 := pow_succ _ _
          _ = 2 * 2 ^ (n - 1) := by ring
      have hpos : 0 < 2 ^ (n - 1) := Nat.two_pow_pos _
  2. The all-ones binary word $2^n - 1$ is invariant under bitwise rotation: $\text{bitword\_rotate}(n, 2^n - 1) = 2^n - 1$.

    Unfolding `bitword_rotate`, the rotation of $2^n - 1$ is $(2(2^n - 1)) \bmod 2^n + (2^n - 1) / 2^{n-1}$. We rewrite $2(2^n - 1)$ as $2^n + (2^n - 2)$; modulo $2^n$, the term $2^n$ cancels by `Nat.add_mod_left`, leaving $2^n - 2$ because $2^n - 2 < 2^n$ (`Nat.mod_eq_of_lt`). The division $(2^n - 1) / 2^{n-1}$ evaluates to $1$ by `Nat.div_eq_of_lt_le` because $1 \cdot 2^{n-1} \le 2^n - 1 < 2 \cdot 2^{n-1}$. Summing $(2^n - 2) + 1$ yields $2^n - 1$.

    lines 9–19

    uses Nat.add_mod_left, Nat.mod_eq_of_lt, Nat.div_eq_of_lt_le

      unfold bitword_rotate
      have h2 : 2 * (2 ^ n - 1) = 2 ^ n + (2 ^ n - 2) := by omega
      have hmod : 2 * (2 ^ n - 1) % 2 ^ n = 2 ^ n - 2 := by
        rw [h2, Nat.add_mod_left]
        exact Nat.mod_eq_of_lt (by omega)
      have hdiv : (2 ^ n - 1) / 2 ^ (n - 1) = 1 := by
        rw [Nat.div_eq_of_lt_le]
        · omega
        · omega
      rw [hmod, hdiv]
      omega
  3. There exists a Gray code rank $s$ whose Gray word is nonconstant and belongs to the rotation class of $x$.

    We define the predicate $p(s)$ stating that $\text{brgc\_word}(s) \ne 0$, $\text{brgc\_word}(s) \ne 2^n - 1$, and $\text{brgc\_word}(s)$ is a rotation of $x$. Choosing $s = \text{brgc\_inverse}(n, x)$, the lemma `brgc_word_inverse` yields $\text{brgc\_word}(s) = x$. The nonconstancy bounds $0 < x < 2^n - 1$ ensure $x \ne 0$ and $x \ne 2^n - 1$, and $x$ is trivially a rotation of itself in $0$ steps. Thus $\text{brgc\_inverse}(n, x)$ witnesses that the predicate $p$ is satisfiable.

    lines 20–32

    uses brgc_word_inverse

    theorem brgc_necklace_first_rank_exists_of_nonconstant (n x : ℕ) (hn : 2 ≤ n) (hx0 : 0 < x) (hx1 : x < 2 ^ n - 1) : ∃ t, brgc_necklace_first_rank n t ∧ bitword_is_rotation n x (brgc_word t) := by
      classical
      let p : ℕ → Prop := fun s => brgc_word s ≠ 0 ∧ brgc_word s ≠ 2 ^ n - 1 ∧ bitword_is_rotation n x (brgc_word s)
      have hxlt : x < 2 ^ n := by omega
      have hpinv : p (brgc_inverse n x) := by
        refine ⟨?_, ?_, ?_⟩
        · rw [brgc_word_inverse hxlt]; omega
        · rw [brgc_word_inverse hxlt]; omega
        · refine ⟨0, by omega, ?_⟩
          rw [brgc_word_inverse hxlt]
          simp
      have hex : ∃ s, p s := ⟨_, hpinv⟩
  4. Let $t$ be the least rank satisfying $p$; then $p(t)$ holds and $t < 2^n$.

    Using `Nat.find`, we set $t$ to be the least rank satisfying $p$, so $p(t)$ holds by `Nat.find_spec`. By `Nat.find_min'`, $t \le \text{brgc\_inverse}(n, x)$, and since $\text{brgc\_inverse}(n, x) < 2^n$ by `brgc_inverse_lt_two_pow`, we obtain $t < 2^n$.

    lines 33–38

    uses Nat.find_spec, Nat.find_min', brgc_inverse_lt_two_pow

      let t := Nat.find hex
      have ht : p t := Nat.find_spec hex
      have htle : t ≤ brgc_inverse n x := Nat.find_min' hex hpinv
      have ht_lt : t < 2 ^ n := by
        have h2 := brgc_inverse_lt_two_pow hxlt
        omega
  5. To prove $t$ is a first Gray rank for the necklace, it suffices to derive a contradiction from assuming some $s < t$ rotates to $\text{brgc\_word}(t)$.

    We supply $t$ as the witness. The conditions $t < 2^n$, $\text{brgc\_word}(t) \ne 0$, $\text{brgc\_word}(t) \ne 2^n - 1$, and rotation equivalence to $x$ all follow from $p(t)$. It remains to show that no earlier rank $s < t$ has its Gray word rotate to $\text{brgc\_word}(t)$. Assuming for contradiction that some $s < t$ rotates to $\text{brgc\_word}(t)$, we note $s < t < 2^n$, which ensures $\text{brgc\_word}(s) < 2^n$ by `brgc_word_lt_two_pow`.

    lines 39–43

    uses brgc_word_lt_two_pow

      refine ⟨t, ?_, ht.2.2⟩
      refine ⟨ht_lt, ht.1, ht.2.1, ?_⟩
      intro s hslt hrot
      have hst : s < 2 ^ n := by omega
      have hsWlt : brgc_word s < 2 ^ n := brgc_word_lt_two_pow hst
  6. The case $\text{brgc\_word}(s) = 0$ is impossible.

    If $\text{brgc\_word}(s) = 0$, then rotating it $r$ times gives $\text{brgc\_word}(t)$. However, $0$ is a fixed point of `bitword_rotate`, so by `Function.iterate_fixed` rotating $0$ any number of times results in $0$. This would mean $\text{brgc\_word}(t) = 0$, contradicting the established condition $\text{brgc\_word}(t) \ne 0$.

    lines 44–49

    uses Function.iterate_fixed

      by_cases hs0 : brgc_word s = 0
      · obtain ⟨r, hr, hrr⟩ := hrot
        have h0 : (bitword_rotate n)^[r] 0 = 0 :=
          Function.iterate_fixed (by simp [bitword_rotate]) r
        rw [hs0, h0] at hrr
        exact ht.1 hrr.symm
  7. The case $\text{brgc\_word}(s) = 2^n - 1$ is impossible.

    If $\text{brgc\_word}(s) = 2^n - 1$, rotating it $r$ times gives $\text{brgc\_word}(t)$. By `brgc_necklace_first_rank_exists_of_nonconstant_rotate_all_ones`, $2^n - 1$ is a fixed point of rotation. By `Function.iterate_fixed`, $r$ rotations leave $2^n - 1$ unchanged, implying $\text{brgc\_word}(t) = 2^n - 1$, which contradicts $\text{brgc\_word}(t) \ne 2^n - 1$.

    lines 50–57

    uses brgc_necklace_first_rank_exists_of_nonconstant_rotate_all_ones, Function.iterate_fixed

      · by_cases hs1 : brgc_word s = 2 ^ n - 1
        · obtain ⟨r, hr, hrr⟩ := hrot
          have hfix : bitword_rotate n (2 ^ n - 1) = 2 ^ n - 1 :=
            brgc_necklace_first_rank_exists_of_nonconstant_rotate_all_ones n (by omega)
          have h0 : (bitword_rotate n)^[r] (2 ^ n - 1) = 2 ^ n - 1 :=
            Function.iterate_fixed hfix r
          rw [hs1, h0] at hrr
          exact ht.2.1 hrr.symm
  8. When $\text{brgc\_word}(s)$ is nonconstant, it satisfies $p(s)$, contradicting the minimality of $t$.

    Since $\text{brgc\_word}(s)$ is neither $0$ nor $2^n - 1$, it is strictly positive (`Nat.pos_of_ne_zero`) and strictly less than $2^n - 1$. By symmetry (`bitword_is_rotation_symm_of_nonconstant`), $\text{brgc\_word}(t)$ rotates to $\text{brgc\_word}(s)$. Since $x$ rotates to $\text{brgc\_word}(t)$, transitivity (`bitword_is_rotation_trans_of_nonconstant`) implies $x$ rotates to $\text{brgc\_word}(s)$. Thus $s$ satisfies $p(s)$, but this contradicts the minimality of $t$ (`Nat.find_min`) since $s < t$.

    lines 58–64

    uses Nat.pos_of_ne_zero, bitword_is_rotation_symm_of_nonconstant, bitword_is_rotation_trans_of_nonconstant, Nat.find_min

        · have hWs0 : 0 < brgc_word s := Nat.pos_of_ne_zero hs0
          have hWs1 : brgc_word s < 2 ^ n - 1 := by omega
          have hsym : bitword_is_rotation n (brgc_word t) (brgc_word s) :=
            bitword_is_rotation_symm_of_nonconstant n (brgc_word s) (brgc_word t) hn hWs0 hWs1 hrot
          have hxs : bitword_is_rotation n x (brgc_word s) :=
            bitword_is_rotation_trans_of_nonconstant n x (brgc_word t) (brgc_word s) hn hx0 hx1 ht.2.2 hsym
          exact Nat.find_min hex hslt ⟨hs0, hs1, hxs⟩
Nat.two_pow_pos
Powers of two are strictly positive for every natural exponent.
pow_succ
For any power $a^{n+1}$, it equals $a^n \cdot a$.
Nat.add_mod_left
Adding a multiple of $x$ does not change the remainder modulo $x$: $(x + z) \bmod x = z \bmod x$.
Nat.mod_eq_of_lt
If $a < b$, then $a \bmod b = a$.
Nat.div_eq_of_lt_le
If $k \cdot n \le m < (k + 1) \cdot n$, then $m / n = k$.
brgc_word_inverse
The binary reflected Gray code function is left-inverse to `brgc_inverse`: $\text{brgc\_word}(\text{brgc\_inverse}(n, x)) = x$ for $x < 2^n$.
Nat.find_spec
The minimal index selected by `Nat.find` satisfies the predicate.
Nat.find_min'
If $m$ satisfies the predicate, then `Nat.find` is at most $m$.
brgc_inverse_lt_two_pow
For an $n$-bit word $x < 2^n$, its Gray code inverse index is strictly less than $2^n$.
brgc_word_lt_two_pow
If rank $t < 2^n$, then its Gray code word is strictly less than $2^n$.
Function.iterate_fixed
If $x$ is a fixed point of $f$ ($f(x) = x$), then iterating $f$ any number of times preserves $x$: $f^n(x) = x$.
brgc_necklace_first_rank_exists_of_nonconstant_rotate_all_ones
Rotating the all-ones word of length $n$ by one position leaves it unchanged: $\text{bitword\_rotate}(n, 2^n - 1) = 2^n - 1$.
Nat.pos_of_ne_zero
A non-zero natural number is strictly positive.
bitword_is_rotation_symm_of_nonconstant
Rotation equivalence is symmetric on nonconstant words ($0 < x < 2^n - 1$).
bitword_is_rotation_trans_of_nonconstant
Rotation equivalence is transitive when starting from a nonconstant word $x$ ($0 < x < 2^n - 1$).
Nat.find_min
Any natural number strictly smaller than `Nat.find` fails the predicate.

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_exists_of_nonconstant_rotate_all_ones (n : ℕ) (hn : 1 ≤ n) :    bitword_rotate n (2 ^ n - 1) = 2 ^ n - 1 := by  have h2n : 0 < 2 ^ n := Nat.two_pow_pos n  have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by    calc 2 ^ n = 2 ^ (n - 1 + 1) := by rw [show n - 1 + 1 = n by omega]      _ = 2 ^ (n - 1) * 2 := pow_succ _ _      _ = 2 * 2 ^ (n - 1) := by ring  have hpos : 0 < 2 ^ (n - 1) := Nat.two_pow_pos _  unfold bitword_rotate  have h2 : 2 * (2 ^ n - 1) = 2 ^ n + (2 ^ n - 2) := by omega  have hmod : 2 * (2 ^ n - 1) % 2 ^ n = 2 ^ n - 2 := by    rw [h2, Nat.add_mod_left]    exact Nat.mod_eq_of_lt (by omega)  have hdiv : (2 ^ n - 1) / 2 ^ (n - 1) = 1 := by    rw [Nat.div_eq_of_lt_le]    · omega    · omega  rw [hmod, hdiv]  omegatheorem brgc_necklace_first_rank_exists_of_nonconstant (n x : ℕ) (hn : 2 ≤ n) (hx0 : 0 < x) (hx1 : x < 2 ^ n - 1) : ∃ t, brgc_necklace_first_rank n t ∧ bitword_is_rotation n x (brgc_word t) := by  classical  let p : ℕ → Prop := fun s => brgc_word s ≠ 0 ∧ brgc_word s ≠ 2 ^ n - 1 ∧ bitword_is_rotation n x (brgc_word s)  have hxlt : x < 2 ^ n := by omega  have hpinv : p (brgc_inverse n x) := by    refine ⟨?_, ?_, ?_⟩    · rw [brgc_word_inverse hxlt]; omega    · rw [brgc_word_inverse hxlt]; omega    · refine ⟨0, by omega, ?_⟩      rw [brgc_word_inverse hxlt]      simp  have hex : ∃ s, p s := ⟨_, hpinv⟩  let t := Nat.find hex  have ht : p t := Nat.find_spec hex  have htle : t ≤ brgc_inverse n x := Nat.find_min' hex hpinv  have ht_lt : t < 2 ^ n := by    have h2 := brgc_inverse_lt_two_pow hxlt    omega  refine ⟨t, ?_, ht.2.2⟩  refine ⟨ht_lt, ht.1, ht.2.1, ?_⟩  intro s hslt hrot  have hst : s < 2 ^ n := by omega  have hsWlt : brgc_word s < 2 ^ n := brgc_word_lt_two_pow hst  by_cases hs0 : brgc_word s = 0  · obtain ⟨r, hr, hrr⟩ := hrot    have h0 : (bitword_rotate n)^[r] 0 = 0 :=      Function.iterate_fixed (by simp [bitword_rotate]) r    rw [hs0, h0] at hrr    exact ht.1 hrr.symm  · by_cases hs1 : brgc_word s = 2 ^ n - 1    · obtain ⟨r, hr, hrr⟩ := hrot      have hfix : bitword_rotate n (2 ^ n - 1) = 2 ^ n - 1 :=        brgc_necklace_first_rank_exists_of_nonconstant_rotate_all_ones n (by omega)      have h0 : (bitword_rotate n)^[r] (2 ^ n - 1) = 2 ^ n - 1 :=        Function.iterate_fixed hfix r      rw [hs1, h0] at hrr      exact ht.2.1 hrr.symm    · have hWs0 : 0 < brgc_word s := Nat.pos_of_ne_zero hs0      have hWs1 : brgc_word s < 2 ^ n - 1 := by omega      have hsym : bitword_is_rotation n (brgc_word t) (brgc_word s) :=        bitword_is_rotation_symm_of_nonconstant n (brgc_word s) (brgc_word t) hn hWs0 hWs1 hrot      have hxs : bitword_is_rotation n x (brgc_word s) :=        bitword_is_rotation_trans_of_nonconstant n x (brgc_word t) (brgc_word s) hn hx0 hx1 ht.2.2 hsym      exact Nat.find_min hex hslt ⟨hs0, hs1, hxs⟩
See it in the graphDiscuss this resultChallenge it