AFTD Auto-Formalizing Theoretical Domains

brgc_word_low_ones

theoremverified

A rank consisting of k+1 low one-bits encodes the word with only bit k set.

Statement

theorem brgc_word_low_ones (k : ℕ) :
    brgc_word (2 ^ (k + 1) - 1) = 2 ^ k
Source
Supporting arithmetic and canonical-representative lemmas for OP-392, arXiv:2610.24758, Conjecture 1.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • brgc_wordThe binary reflected Gray code word of rank t, read as a binary number: g(t) = t xor floor(t/2).
Used by 4

The proof, explained

The proof evaluates the binary reflected Gray code function, defined by brgc_word(t) = t ^^^ (t / 2), at t = 2^(k + 1) - 1. Integer division reduces the term to (2^(k + 1) - 1) ^^^ (2^k - 1). The result 2^k is then established by bitwise extensionality: the i-th bit of 2^n - 1 is 1 exactly when i < n, so the boolean XOR of the bits of 2^(k + 1) - 1 and 2^k - 1 is 1 if and only if i = k, which matches the bit representation of 2^k.

  1. (2^(k + 1) - 1) / 2 = 2^k - 1

    Using `pow_succ` to rewrite 2^(k + 1) as 2 * 2^k and `Nat.two_pow_pos` to note that 2^k > 0, linear integer arithmetic (`omega`) computes the integer division (2^(k + 1) - 1) / 2 = (2 * 2^k - 1) / 2 = 2^k - 1.

    lines 3–5

    uses pow_succ, Nat.two_pow_pos

      have hpow : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega
      have hp : 0 < 2 ^ k := Nat.two_pow_pos _
      have hd : (2 ^ (k + 1) - 1) / 2 = 2 ^ k - 1 := by omega
  2. (2^(k + 1) - 1) ^^^ (2^k - 1) = 2^k

    Unfolding the definition of `brgc_word` (which is t ^^^ (t / 2)) on 2^(k + 1) - 1 and rewriting with the division identity from the previous step simplifies the goal to showing (2^(k + 1) - 1) ^^^ (2^k - 1) = 2^k.

    lines 6–7

      unfold brgc_word
      rw [hd]
  3. For every bit index i, (i < k + 1) ^^ (i < k) = (k = i) as boolean values.

    By `Nat.eq_of_testBit_eq`, it suffices to show that the i-th bit of (2^(k + 1) - 1) ^^^ (2^k - 1) equals the i-th bit of 2^k for any arbitrary bit index i. Simplifying with `Nat.testBit_xor`, `Nat.testBit_two_pow_sub_one`, and `Nat.testBit_two_pow` translates the bit values of 2^n - 1 and 2^k into the boolean conditions (i < n) and (k = i), reducing the goal to a boolean equation.

    lines 8–10

    uses Nat.eq_of_testBit_eq, Nat.testBit_xor, Nat.testBit_two_pow_sub_one, Nat.testBit_two_pow

      apply Nat.eq_of_testBit_eq
      intro i
      simp only [Nat.testBit_xor, Nat.testBit_two_pow_sub_one, Nat.testBit_two_pow]
  4. The boolean bit identity holds when i < k.

    When i < k, linear arithmetic gives i < k + 1 and k ≠ i. Both conditions i < k + 1 and i < k evaluate to true, so their boolean XOR is true ^^ true = false. Since k = i is false, both sides evaluate to false.

    lines 11–14

      by_cases hi : i < k
      · have hi' : i < k + 1 := by omega
        have hne : k ≠ i := by omega
        simp [hi, hi', hne]
  5. The boolean bit identity holds when i = k.

    When k = i, substituting i = k gives k < k + 1 (true) and k < k (false). The boolean XOR true ^^ false simplifies to true, matching the right-hand side k = k (true).

    lines 15–17

      · by_cases heq : k = i
        · subst i
          simp
  6. The boolean bit identity holds when i > k.

    When ¬(i < k) and k ≠ i, linear arithmetic gives ¬(i < k + 1). Both i < k + 1 and i < k evaluate to false, so their boolean XOR false ^^ false is false, which matches the right-hand side k = i (false). This completes the case analysis and the proof.

    lines 18–19

        · have hi' : ¬ i < k + 1 := by omega
          simp [hi, hi', heq]
pow_succ
In any monoid, a^(n+1) = a^n * a.
Nat.two_pow_pos
Powers of two are strictly positive: 2^w > 0 for all w in ℕ.
Nat.eq_of_testBit_eq
Two natural numbers are equal if their binary representations have the same bit at every position.
Nat.testBit_xor
The i-th bit of a bitwise XOR x ^^^ y is the boolean XOR of the i-th bit of x and the i-th bit of y.
Nat.testBit_two_pow_sub_one
The i-th bit of 2^n - 1 is 1 if and only if i < n.
Nat.testBit_two_pow
The m-th bit of 2^n is 1 if and only if n = m.

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_word_low_ones (k : ℕ) :    brgc_word (2 ^ (k + 1) - 1) = 2 ^ k := by  have hpow : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ]; omega  have hp : 0 < 2 ^ k := Nat.two_pow_pos _  have hd : (2 ^ (k + 1) - 1) / 2 = 2 ^ k - 1 := by omega  unfold brgc_word  rw [hd]  apply Nat.eq_of_testBit_eq  intro i  simp only [Nat.testBit_xor, Nat.testBit_two_pow_sub_one, Nat.testBit_two_pow]  by_cases hi : i < k  · have hi' : i < k + 1 := by omega    have hne : k ≠ i := by omega    simp [hi, hi', hne]  · by_cases heq : k = i    · subst i      simp    · have hi' : ¬ i < k + 1 := by omega      simp [hi, hi', heq]
See it in the graphDiscuss this resultChallenge it