AFTD Auto-Formalizing Theoretical Domains

brgc_necklace_first_rank_word_odd

theoremverified

For length at least two, the first nonconstant representative in Gray order has final bit one.

Statement

theorem brgc_necklace_first_rank_word_odd {n t : ℕ} (hn : 2 ≤ n)
    (ht : brgc_necklace_first_rank n t) : brgc_word t % 2 = 1
Source
Supporting arithmetic and canonical-representative lemmas for OP-392, arXiv:2610.24758, Conjecture 1.
Verified
25 Oct 2026
Axioms
Quot.soundpropext
Built on 6
  • 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_word_lt_two_powAn n-bit rank encodes an n-bit word.
  • brgc_word_div_twoThe binary reflected Gray encoding commutes with division by two.
  • 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.
  • 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.
Used by 1

The proof, explained

The proof proceeds by contradiction: if the Gray code word brgc_word t were even, its least significant bit would be zero. By brgc_word_div_two, shifting this word right by one bit yields brgc_word (t / 2) for the strictly smaller index t / 2 < t. Rotating brgc_word (t / 2) left by one position reconstructs brgc_word t, which contradicts the minimality of t as the first rank representative of its rotation class.

  1. t > 0

    Suppose for contradiction that t ≤ 0, so t = 0. Then brgc_word t = brgc_word 0 = 0, which contradicts the hypothesis that t represents a nonconstant necklace (brgc_word t ≠ 0).

    lines 3–6

      have htpos : 0 < t := by
        by_contra h
        have : t = 0 := by omega
        exact ht.2.1 (by simp [this, brgc_word])
  2. brgc_word t < 2^n

    Since t < 2^n by definition of necklace rank, brgc_word_lt_two_pow implies that brgc_word t < 2^n.

    line 7

    uses brgc_word_lt_two_pow

      have hxlt := brgc_word_lt_two_pow ht.1
  3. brgc_word t % 2 = 0 under the assumption that the theorem fails

    Assume for contradiction that brgc_word t % 2 ≠ 1. Because any natural number modulo 2 is either 0 or 1, linear integer arithmetic (omega) establishes that brgc_word t is even (brgc_word t % 2 = 0).

    lines 8–9

      by_contra hodd
      have heven : brgc_word t % 2 = 0 := by omega
  4. t / 2 < t

    Since t > 0 and 2 > 1, integer division strictly decreases t by Nat.div_lt_self.

    line 10

    uses Nat.div_lt_self

      have hsmall : t / 2 < t := Nat.div_lt_self htpos (by omega)
  5. It suffices to show that 2 * (brgc_word t / 2) % 2^n + (brgc_word t / 2) / 2^(n - 1) = brgc_word t

    By definition of the first rank representative, no strictly smaller index s < t can have a Gray code word that rotates to brgc_word t. Applying this minimality to s = t / 2 < t, it suffices to show that rotating brgc_word (t / 2) left by 1 bit produces brgc_word t, with the rotation count 1 < n valid since n ≥ 2. Using Function.iterate_one, expanding bitword_rotate, and rewriting with brgc_word_div_two, the goal reduces to verifying the 1-bit rotation formula applied to brgc_word t / 2.

    lines 11–14

    uses Function.iterate_one, brgc_word_div_two

      apply ht.2.2.2 (t / 2) hsmall
      refine ⟨1, by omega, ?_⟩
      simp only [Function.iterate_one]
      rw [bitword_rotate, ← brgc_word_div_two]
  6. 2^n = 2 * 2^(n - 1)

    Since n ≥ 2, we write n = (n - 1) + 1, expand 2^((n - 1) + 1) = 2^(n - 1) * 2 via pow_succ, and rearrange factors using linear arithmetic.

    lines 15–17

    uses pow_succ

      have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by
        conv_lhs => rw [show n = (n - 1) + 1 by omega, pow_succ]
        omega
  7. The rotation simplifies to brgc_word t + (brgc_word t / 2) / 2^(n - 1) = brgc_word t

    Because brgc_word t is even, 2 * (brgc_word t / 2) = brgc_word t. Since brgc_word t < 2^n, taking the remainder modulo 2^n leaves brgc_word t unchanged by Nat.mod_eq_of_lt. Substituting these into the first term simplifies it to brgc_word t.

    lines 18–19

    uses Nat.mod_eq_of_lt

      have hdouble : 2 * (brgc_word t / 2) = brgc_word t := by omega
      rw [hdouble, Nat.mod_eq_of_lt hxlt]
  8. The high-order bit term (brgc_word t / 2) / 2^(n - 1) vanishes, closing the contradiction

    Because brgc_word t < 2^n = 2 * 2^(n - 1), we have brgc_word t / 2 < 2^(n - 1), so dividing by 2^(n - 1) yields 0 by Nat.div_eq_of_lt. Substituting 0 gives brgc_word t + 0 = brgc_word t, which is an identity and produces the desired contradiction.

    lines 20–23

    uses Nat.div_eq_of_lt

      have hdiv : brgc_word t / 2 / 2 ^ (n - 1) = 0 := by
        apply Nat.div_eq_of_lt
        omega
      omega
brgc_word_lt_two_pow
If t < 2^n, then brgc_word t < 2^n.
Nat.div_lt_self
If 0 < n and 1 < k, then n / k < n.
Function.iterate_one
Iterating a function once is the function itself: f^[1] = f.
brgc_word_div_two
Halving the BRGC word of t equals the BRGC word of t / 2: brgc_word t / 2 = brgc_word (t / 2).
pow_succ
For any base a and exponent n, a^(n + 1) = a^n * a.
Nat.mod_eq_of_lt
If a < b, then a % b = a.
Nat.div_eq_of_lt
If a < b, then integer division yields a / b = 0.

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_word_odd {n t : ℕ} (hn : 2 ≤ n)    (ht : brgc_necklace_first_rank n t) : brgc_word t % 2 = 1 := by  have htpos : 0 < t := by    by_contra h    have : t = 0 := by omega    exact ht.2.1 (by simp [this, brgc_word])  have hxlt := brgc_word_lt_two_pow ht.1  by_contra hodd  have heven : brgc_word t % 2 = 0 := by omega  have hsmall : t / 2 < t := Nat.div_lt_self htpos (by omega)  apply ht.2.2.2 (t / 2) hsmall  refine ⟨1, by omega, ?_⟩  simp only [Function.iterate_one]  rw [bitword_rotate, ← brgc_word_div_two]  have hpow : 2 ^ n = 2 * 2 ^ (n - 1) := by    conv_lhs => rw [show n = (n - 1) + 1 by omega, pow_succ]    omega  have hdouble : 2 * (brgc_word t / 2) = brgc_word t := by omega  rw [hdouble, Nat.mod_eq_of_lt hxlt]  have hdiv : brgc_word t / 2 / 2 ^ (n - 1) = 0 := by    apply Nat.div_eq_of_lt    omega  omega
See it in the graphDiscuss this resultChallenge it